use core::{borrow::Borrow, fmt, fmt::Formatter, hash::Hash, iter::FromIterator};

use crate::{map, FromIndex, Ham, IntoIndex, Key};

/// A [hash set] implemented as a `Ham` where the value is `()`.
///
/// As with the [`Ham`] type, a `HashArrSet` requires that the elements
/// implement the [`Eq`], [`Hash`], [`IntoIndex`] and [`FromIndex`] traits.
/// This can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`
/// for `Eq` and `Hash`, and implementing the other two yourself.
/// If you implement `Eq` and `Hash` yourself, it is important that the following
/// property holds:
///
/// ```text
/// k1 == k2 -> hash(k1) == hash(k2)
/// ```
///
/// In other words, if two keys are equal, their hashes must be equal.
///
/// It is a logic error for an item to be modified in such a way that the
/// item's hash, as determined by the [`Hash`] trait, or its equality, as
/// determined by the [`Eq`] trait, changes while it is in the set. This is
/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or
/// unsafe code. The behavior resulting from such a logic error is not
/// specified, but will not result in undefined behavior. This could include
/// panics, incorrect results, aborts, memory leaks, and non-termination.
///
/// # Examples
///
/// ```
/// use hash_arr_map::HashArrSet;
///
/// // Type inference lets us omit an explicit type signature (which
/// // would be `HashArrSet<i32>` in this example).
/// let mut primes = HashArrSet::new();
///
/// // Add some primes.
/// primes.insert(1);
/// primes.insert(2);
/// primes.insert(3);
/// primes.insert(5);
/// primes.insert(7);
///
/// // Check for a specific one.
/// if !primes.contains(&6) {
///     println!("We have {} primes, but 6 isn't one.", primes.len());
/// }
///
/// // Actually, 1 isn't a prime
/// primes.remove(&1);
///
/// // Iterate over everything.
/// for prime in &primes {
///     println!("{}", prime);
/// }
/// ```
///
/// The easiest way to use `HashArrSet` with a custom type is to derive
/// [`Eq`] and [`Hash`], then implement [`IntoIndex`] and [`FromIndex`]
/// manually. We must also derive [`PartialEq`], this will in the
/// future be implied by [`Eq`].
///
/// ```
/// use core::num::NonZeroUsize;
///
/// use hash_arr_map::{FromIndex, HashArrSet, Idx, IntoIndex};
///
/// #[derive(Hash, Eq, PartialEq, Debug)]
/// struct Price {
///     dollars: u8,
///     cents: u8,
/// }
///
/// impl IntoIndex for Price {
///     fn into_index(&self) -> Option<Idx<Self>> {
///         unsafe { Idx::from_usize(((self.cents as usize) << 8) + self.dollars as usize) }
///     }
/// }
///
/// impl FromIndex for Price {
///     fn from_index(idx: Idx<Self>) -> Self {
///         Self {
///             dollars: idx.get().get() as u8,
///             cents: (idx.get().get() >> 8) as u8,
///         }
///     }
/// }
///
/// let mut prices = HashArrSet::new();
///
/// prices.insert(Price {
///     dollars: 3,
///     cents: 50,
/// });
/// prices.insert(Price {
///     dollars: 5,
///     cents: 99,
/// });
/// prices.insert(Price {
///     dollars: 9,
///     cents: 99,
/// });
/// prices.insert(Price {
///     dollars: 5,
///     cents: 99,
/// });
///
/// // We only have 3 unique prices:
/// assert_eq!(prices.len(), 3);
///
/// // Use derived implementation to print the prices.
/// for x in &prices {
///     println!("{:?}", x);
/// }
/// ```
///
/// A `HashArrSet` with fixed list of elements can be initialized from an array:
///
/// ```
/// use hash_arr_map::HashArrSet;
///
/// let primes: HashArrSet<u64> = [2, 3, 5, 7, 11, 13, 17, 18].iter().copied().collect();
/// // use the values stored in the set
/// ```
///
/// [`RefCell`]: core::cell::RefCell
/// [`Cell`]: core::cell::Cell
#[cfg_attr(feature = "gc", derive(gc::Trace))]
#[derive(Clone)]
pub struct HashArrSet<T> {
    inner: Ham<T, ()>,
}

impl<T> PartialEq for HashArrSet<T>
where
    T: FromIndex + Hash + Eq,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            false
        } else {
            self.iter().all(|key| other.contains(&key))
        }
    }
}

impl<T> Eq for HashArrSet<T> where T: FromIndex + Hash + Eq {}

impl<T: FromIndex + fmt::Debug> fmt::Debug for HashArrSet<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

#[cfg(feature = "std")]
impl<K> Default for HashArrSet<K> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(feature = "std")]
impl<K> HashArrSet<K> {
    /// Creates an empty `HashArrSet`.
    ///
    /// It is created with a capacity of 0, so it will not allocate until
    /// inserted into.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use hash_arr_map::HashArrSet;
    /// let set: HashArrSet<i32> = HashArrSet::new();
    /// ```
    #[must_use]
    #[inline]
    pub fn new() -> Self {
        Self::from_inner(Ham::new())
    }

    /// Creates an empty `HashArrSet` with the specified capacities.
    ///
    /// The set will be able to hold at least the amount of elements
    /// in each section without reallocating.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use hash_arr_map::HashArrSet;
    /// let set: HashArrSet<i32> = HashArrSet::with_capacity(5, 10);
    /// assert!(set.capacity().0 >= 5 && set.capacity().1 >= 10);
    /// ```
    #[must_use]
    #[inline]
    pub fn with_capacity(array_part: usize, hash_part: usize) -> Self {
        Self::from_inner(Ham::with_capacity(array_part, hash_part))
    }
}

impl<K> HashArrSet<K> {
    /// Creates a new `Ham` with a specific seed.
    #[must_use]
    #[inline]
    pub const fn with_seed(seed: u64) -> Self {
        Self::from_inner(Ham::with_seed(seed))
    }

    /// Creates a new `Ham` with a specific capacity and a specific seed.
    #[must_use]
    #[inline]
    pub fn with_capacity_and_seed(array_part: usize, hash_part: usize, seed: u64) -> Self {
        Self::from_inner(Ham::with_capacity_and_seed(array_part, hash_part, seed))
    }

    #[must_use]
    #[inline]
    pub const fn from_inner(inner: Ham<K, ()>) -> Self {
        Self { inner }
    }

    #[must_use]
    #[inline]
    pub fn contains<Q: ?Sized>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        self.inner.contains_key(key)
    }

    #[inline]
    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        self.inner.remove(key).is_some()
    }

    #[inline]
    pub fn clear(&mut self) {
        self.inner.clear();
    }

    #[inline]
    pub const fn len(&self) -> usize {
        self.inner.len()
    }

    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[inline]
    pub fn capacity(&self) -> (usize, usize) {
        self.inner.capacity()
    }
}

impl<K: FromIndex + Hash + Eq> HashArrSet<K> {
    #[must_use]
    #[inline]
    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<Key<'_, K>>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        self.inner.get_key_value(key).map(|v| v.0)
    }

    #[inline]
    pub fn take<Q: ?Sized>(&mut self, key: &Q) -> Option<K>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        self.inner.remove_entry(key).map(|v| v.0)
    }
}

impl<K: FromIndex> HashArrSet<K> {
    #[inline]
    pub fn iter(&self) -> Iter<'_, K> {
        Iter {
            inner: self.inner.keys(),
        }
    }
}

impl<K: IntoIndex + FromIndex + Hash + Eq> HashArrSet<K> {
    /// Insert `key` into the table.
    ///
    /// Returns `true` if it was already in the table
    #[inline]
    pub fn insert(&mut self, key: K) -> bool {
        self.inner.insert(key, ()).is_some()
    }

    #[inline]
    pub fn force_rehash(&mut self) {
        self.inner.force_rehash();
    }

    #[inline]
    pub fn shrink_to_fit(&mut self) {
        self.inner.shrink_to_fit();
    }
}

impl<'a, K: FromIndex> IntoIterator for &'a HashArrSet<K> {
    type Item = Key<'a, K>;
    type IntoIter = Iter<'a, K>;
    fn into_iter(self) -> Iter<'a, K> {
        self.iter()
    }
}

pub struct Iter<'a, K> {
    inner: map::Keys<'a, K, ()>,
}

impl<'a, K: 'a + FromIndex> Iterator for Iter<'a, K> {
    type Item = Key<'a, K>;
    fn next(&mut self) -> Option<Key<'a, K>> {
        self.inner.next()
    }
}

impl<K: FromIndex> IntoIterator for HashArrSet<K> {
    type Item = K;
    type IntoIter = IntoIter<K>;
    fn into_iter(self) -> IntoIter<K> {
        let HashArrSet { inner } = self;

        IntoIter {
            inner: inner.into_iter(),
        }
    }
}

pub struct IntoIter<K> {
    inner: map::IntoIter<K, ()>,
}

impl<K: FromIndex> Iterator for IntoIter<K> {
    type Item = K;
    fn next(&mut self) -> Option<K> {
        self.inner.next().map(|v| v.0)
    }
}

#[cfg(feature = "std")]
impl<K> FromIterator<K> for HashArrSet<K>
where
    K: IntoIndex + FromIndex + Hash + Eq,
{
    #[inline]
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = K>,
    {
        let mut set = HashArrSet::new();
        set.extend(iter);
        set
    }
}

impl<K> Extend<K> for HashArrSet<K>
where
    K: IntoIndex + FromIndex + Hash + Eq,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = K>,
    {
        for item in iter.into_iter() {
            self.insert(item);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_array_part() {
        // This checks that all the elements are inserted into the
        // array part without using the hash.
        let mut set = HashArrSet::<u32>::with_seed(0);

        for i in 1..=15 {
            set.insert(i);
        }

        assert_eq!(
            alloc::format!("{:?}", set),
            "{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}"
        );
    }
}