use std::hash::Hash;
use std::mem::transmute;
use std::ops::{BitAnd, Deref};

use hashbrown::HashMap;

pub trait VecExt<Item>
{
    fn insert_at_partition_point_by_key<Key>(
        &mut self,
        item: Item,
        func: impl FnMut(&Item) -> Key,
    ) where
        Key: Ord;
}

impl<Item> VecExt<Item> for Vec<Item>
{
    fn insert_at_partition_point_by_key<Key>(
        &mut self,
        item: Item,
        mut func: impl FnMut(&Item) -> Key,
    ) where
        Key: Ord,
    {
        let key = func(&item);

        let insert_index = self.partition_point(|other_item| func(other_item) <= key);

        self.insert(insert_index, item);
    }
}

pub trait StreamingIterator
{
    type Item<'a>
    where
        Self: 'a;

    fn streaming_next(&mut self) -> Option<Self::Item<'_>>;

    fn streaming_map<NewItem, Func>(self, func: Func) -> StreamingMap<Self, Func>
    where
        Self: Sized,
        Func: FnMut(Self::Item<'_>) -> NewItem,
    {
        StreamingMap { iter: self, func }
    }

    fn streaming_find<'this, Predicate>(
        &'this mut self,
        mut predicate: Predicate,
    ) -> Option<Self::Item<'this>>
    where
        Self: Sized,
        Predicate: FnMut(&Self::Item<'this>) -> bool,
    {
        while let Some(item) = unsafe {
            transmute::<Option<Self::Item<'_>>, Option<Self::Item<'_>>>(
                self.streaming_next(),
            )
        } {
            if predicate(&item) {
                return Some(item);
            }
        }

        None
    }
}

pub struct StreamingMap<Iter, Func>
{
    iter: Iter,
    func: Func,
}

impl<Iter, Func, Item> StreamingIterator for StreamingMap<Iter, Func>
where
    Iter: StreamingIterator,
    Func: FnMut(Iter::Item<'_>) -> Item,
{
    type Item<'a>
        = Item
    where
        Iter: 'a,
        Func: 'a;

    fn streaming_next(&mut self) -> Option<Self::Item<'_>>
    {
        Some((self.func)(self.iter.streaming_next()?))
    }
}

#[derive(Debug)]
pub enum BorrowedOrOwned<'a, Value>
{
    Borrowned(&'a Value),
    Owned(Value),
}

impl<Value> Deref for BorrowedOrOwned<'_, Value>
{
    type Target = Value;

    fn deref(&self) -> &Self::Target
    {
        match self {
            Self::Borrowned(value) => value,
            Self::Owned(value) => value,
        }
    }
}

#[derive(Debug, Clone)]
pub enum Either<A, B>
{
    A(A),
    B(B),
}

impl<A, B> Iterator for Either<A, B>
where
    A: Iterator,
    B: Iterator<Item = A::Item>,
{
    type Item = A::Item;

    fn next(&mut self) -> Option<Self::Item>
    {
        match self {
            Self::A(a) => a.next(),
            Self::B(b) => b.next(),
        }
    }
}

pub trait HashMapExt<Key, Value>
{
    /// Returns true if the keys are a subset of another [`HashMap`]'s keys, i.e., `other`
    /// contains at least all the keys in `self`.
    fn keys_is_subset(&self, other: &Self) -> bool;

    /// Returns true if the keys are a superset of another [`HashMap`]'s keys, i.e.,
    /// `self` contains at least all the keys in `other`.
    fn keys_is_superset(&self, other: &Self) -> bool;
}

impl<Key, Value> HashMapExt<Key, Value> for HashMap<Key, Value>
where
    Key: Eq + Hash,
{
    fn keys_is_subset(&self, other: &Self) -> bool
    {
        if self.len() <= other.len() {
            self.keys().all(|key| other.contains_key(key))
        } else {
            false
        }
    }

    fn keys_is_superset(&self, other: &Self) -> bool
    {
        other.keys_is_subset(self)
    }
}

pub trait Array<Item>:
    AsRef<[Item]>
    + AsMut<[Item]>
    + IntoIterator<Item = Item>
    + Into<Vec<Item>>
    + Sortable<Item = Item>
    + sealed::Sealed
{
}

impl<Item, const CNT: usize> Array<Item> for [Item; CNT] {}

impl<Item, const CNT: usize> sealed::Sealed for [Item; CNT] {}

pub trait Sortable
{
    type Item;

    fn sort_by_key_b<Key, Func>(&mut self, func: Func)
    where
        Func: FnMut(&Self::Item) -> Key,
        Key: Ord;
}

impl<Item> Sortable for [Item]
{
    type Item = Item;

    fn sort_by_key_b<Key, Func>(&mut self, func: Func)
    where
        Func: FnMut(&Self::Item) -> Key,
        Key: Ord,
    {
        self.sort_by_key(func);
    }
}

impl<Item, const LENGTH: usize> Sortable for [Item; LENGTH]
{
    type Item = Item;

    fn sort_by_key_b<Key, Func>(&mut self, func: Func)
    where
        Func: FnMut(&Self::Item) -> Key,
        Key: Ord,
    {
        self.sort_by_key(func);
    }
}

impl<Item> Sortable for Vec<Item>
{
    type Item = Item;

    fn sort_by_key_b<Key, Func>(&mut self, func: Func)
    where
        Func: FnMut(&Self::Item) -> Key,
        Key: Ord,
    {
        self.sort_by_key(func);
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct BitMask<Value>
{
    mask: Value,
}

impl BitMask<u64>
{
    #[must_use]
    pub const fn new(mask: u64) -> Self
    {
        Self { mask }
    }

    #[must_use]
    pub const fn value(self) -> u64
    {
        self.mask
    }

    /// Prepares a bitfield value in the range of bits specified by this `BitMask`.
    #[must_use]
    pub const fn field_prep(self, field_value: u64) -> u64
    {
        ((field_value) << self.mask.trailing_zeros()) & (self.mask)
    }
}

impl BitAnd<u64> for BitMask<u64>
{
    type Output = u64;

    fn bitand(self, rhs: u64) -> Self::Output
    {
        self.mask & rhs
    }
}

pub trait NumberExt: Sized
{
    /// Returns a range of bits (field) specified by the provided [`BitMask`].
    #[must_use]
    fn field_get(self, field_mask: BitMask<Self>) -> Self;
}

impl NumberExt for u64
{
    fn field_get(self, field_mask: BitMask<Self>) -> Self
    {
        (field_mask & self) >> field_mask.value().trailing_zeros()
    }
}

macro_rules! gen_mask_64 {
    ($low: literal..=$high: literal) => {
        const {
            if $high <= $low {
                panic!("High bit index cannot be less than or equal to low bit index");
            }

            (((!0u64) - (1u64 << ($low)) + 1)
                & (!0u64 >> (u64::BITS as u64 - 1 - ($high))))
        }
    };
}

pub(crate) use gen_mask_64;

mod sealed
{
    pub trait Sealed {}
}

#[cfg(test)]
mod tests
{

    use super::BitMask;
    use crate::util::NumberExt;

    #[test]
    fn field_get_works()
    {
        assert_eq!(0b11011u64.field_get(BitMask::new(0b11100)), 0b00110);
    }

    #[test]
    fn bitmask_field_prep_works()
    {
        assert_eq!(BitMask::new(0b11000).field_prep(3), 0b11000);
    }
}