arrayset 3.1.1

pub mod compare;
mod into_iter;
mod iter;

use self::compare::{Compare, Difference, Intersection, SymmetricDifference, Union};
use crate::ord::map::OrdMap;
pub use into_iter::IntoIter;
pub use iter::Iter;

use core::{
    borrow::Borrow,
    cmp::{Ord, Ordering},
    fmt,
    hash::Hash,
    ops::Deref,
};

#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash, Clone, Default, Copy)]
struct ZST;

/// A heapless, ord-based array set. Operates very similarly to [`BTreeSet`],
/// but maintains its entries as a single array stored inside itself. Sorted
/// insertions are optimized and will be processed in constant time.
///
/// [`BTreeSet`]: https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
#[derive(Clone, Hash)]
pub struct OrdSet<T, const N: usize> {
    inner: OrdMap<T, ZST, N>,
}

impl<T, const N: usize> OrdSet<T, N> {
    pub fn as_slice(&self) -> &[T] {
        self.inner.keys_slice()
    }
    pub fn as_ptr(&self) -> *const T {
        self.inner.keys_ptr()
    }

    pub fn new() -> Self {
        Self::default()
    }

    pub fn len(&self) -> usize {
        self.inner.len()
    }

    pub fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self.inner.keys_slice())
    }

    pub fn first(&self) -> Option<&T> {
        self.inner.first_key_value().map(|(k, _)| k)
    }

    pub fn last(&self) -> Option<&T> {
        self.inner.last_key_value().map(|(k, _)| k)
    }
    pub fn pop_first(&mut self) -> Option<T> {
        self.inner.pop_first().map(|(k, _)| k)
    }
    pub fn pop_last(&mut self) -> Option<T> {
        self.inner.pop_last().map(|(k, _)| k)
    }

    pub fn clear(&mut self) {
        self.inner.clear()
    }

    /// Insert the value into the set.  The possible results are:
    /// * `Ok(Some(T))`: If the value already existed in the map.  This value is
    ///   not inserted, and the value is returned back to the caller.
    /// * `Ok(None)`: If the value was inserted successfully without
    ///   replacement.
    /// * `Err(T)`: If the set was full; the value is returned to the caller.
    ///
    /// # Examples
    ///
    /// ```
    /// # use arrayset::OrdSet;
    /// let mut set: OrdSet<_, 2> = Default::default();
    /// assert_eq!(
    ///     set.insert(String::from("alpha")),
    ///     Ok(None),
    /// );
    /// assert_eq!(
    ///     set.insert(String::from("alpha")),
    ///     Ok(Some(String::from("alpha"))),
    /// );
    /// assert_eq!(
    ///     set.insert(String::from("beta")),
    ///     Ok(None),
    /// );
    /// assert_eq!(
    ///     set.insert(String::from("gamma")),
    ///     Err(String::from("gamma")),
    /// );
    /// ```
    pub fn insert(&mut self, value: T) -> Result<Option<T>, T>
    where
        T: Ord,
    {
        self.inner
            .insert(value, ZST)
            .map(|ok| ok.map(|(k, _)| k))
            .map_err(|(k, _)| k)
    }

    /// Insert the value into the map.  The possible results are:
    /// * `Ok(Some(T))`: If the value already existed in the map.  This is the
    ///   value that was replaced.
    /// * `Ok(None)`: If the value was inserted successfully without
    ///   replacement.
    /// * `Err(T)`: If the set was full; the value is returned to the caller.
    ///
    /// # Examples
    ///
    /// ```
    /// # use arrayset::OrdSet;
    /// let mut map: OrdSet<_, 2> = Default::default();
    /// assert_eq!(
    ///     map.replace(String::from("alpha")),
    ///     Ok(None),
    /// );
    /// assert_eq!(
    ///     map.replace(String::from("alpha")),
    ///     Ok(Some(String::from("alpha"))),
    /// );
    /// assert_eq!(
    ///     map.replace(String::from("beta")),
    ///     Ok(None),
    /// );
    /// assert_eq!(
    ///     map.replace(String::from("gamma")),
    ///     Err(String::from("gamma")),
    /// );
    /// ```
    pub fn replace(&mut self, value: T) -> Result<Option<T>, T>
    where
        T: Ord,
    {
        self.inner
            .replace(value, ZST)
            .map(|ok| ok.map(|(k, _)| k))
            .map_err(|(k, _)| k)
    }

    pub fn contains<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.contains_key(value)
    }

    pub fn get<Q>(&self, value: &Q) -> Option<&T>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.get_key_value(value).map(|(k, _)| k)
    }

    pub fn remove<Q>(&mut self, value: &Q) -> Option<T>
    where
        T: Borrow<Q>,
        Q: Ord + ?Sized,
    {
        self.inner.remove(value).map(|(k, _)| k)
    }

    pub fn union<'a, const N2: usize>(&'a self, other: &'a OrdSet<T, N2>) -> Union<'a, T> {
        Union::new(self.as_slice(), other.as_slice())
    }

    pub fn compare<'a, const N2: usize>(&'a self, other: &'a OrdSet<T, N2>) -> Compare<'a, T> {
        Compare::new(self.as_slice(), other.as_slice())
    }

    pub fn difference<'a, const N2: usize>(
        &'a self,
        other: &'a OrdSet<T, N2>,
    ) -> Difference<'a, T> {
        Difference::new(self.as_slice(), other.as_slice())
    }

    pub fn intersection<'a, const N2: usize>(
        &'a self,
        other: &'a OrdSet<T, N2>,
    ) -> Intersection<'a, T> {
        Intersection::new(self.as_slice(), other.as_slice())
    }

    pub fn symmetric_difference<'a, const N2: usize>(
        &'a self,
        other: &'a OrdSet<T, N2>,
    ) -> SymmetricDifference<'a, T> {
        SymmetricDifference::new(self.as_slice(), other.as_slice())
    }

    pub fn is_disjoint<const N2: usize>(&self, other: &OrdSet<T, N2>) -> bool
    where
        T: Ord,
    {
        self.intersection(other).next().is_none()
    }

    pub fn is_subset<const N2: usize>(&self, other: &OrdSet<T, N2>) -> bool
    where
        T: Ord,
    {
        if self.len() > other.len() {
            return false;
        } else if self.len() == 0 {
            return true;
        } else {
            self.difference(other).next().is_none()
        }
    }
    pub fn is_superset<const N2: usize>(&self, other: &OrdSet<T, N2>) -> bool
    where
        T: Ord,
    {
        other.is_subset(self)
    }

    pub fn retain<F>(&mut self, mut f: F)
    where
        T: Ord,
        F: FnMut(&T) -> bool,
    {
        self.inner.retain(move |k, _| f(k))
    }
}

impl<T, const N: usize> Default for OrdSet<T, N> {
    fn default() -> Self {
        Self {
            inner: Default::default(),
        }
    }
}

impl<T, const N: usize> fmt::Debug for OrdSet<T, N>
where
    T: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

impl<T, const N: usize> Deref for OrdSet<T, N> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        self.as_slice()
    }
}

impl<T, const N1: usize, const N2: usize> PartialOrd<OrdSet<T, N2>> for OrdSet<T, N1>
where
    T: PartialOrd<T>,
{
    fn partial_cmp(&self, other: &OrdSet<T, N2>) -> Option<Ordering> {
        self.as_slice().partial_cmp(other.as_slice())
    }
}

impl<T, const N: usize> Ord for OrdSet<T, N>
where
    T: Ord,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.as_slice().cmp(other.as_slice())
    }
}

impl<T, const N1: usize, const N2: usize> PartialEq<OrdSet<T, N2>> for OrdSet<T, N1>
where
    T: PartialEq<T>,
{
    fn eq(&self, other: &OrdSet<T, N2>) -> bool {
        self.as_slice().eq(other.as_slice())
    }
}

impl<T, const N: usize> Eq for OrdSet<T, N> where T: Eq {}

/// Panics on overflow
impl<T, const N: usize> Extend<T> for OrdSet<T, N>
where
    T: Ord,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>,
    {
        for each in iter {
            if let Err(_) = self.insert(each) {
                panic!("set overflowed on extend");
            }
        }
    }
}

impl<'a, T, const N: usize> Extend<&'a T> for OrdSet<T, N>
where
    T: 'a + Ord + Copy,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = &'a T>,
    {
        self.extend(iter.into_iter().copied())
    }
}

/// Panics on overflow
impl<T, const N: usize> FromIterator<T> for OrdSet<T, N>
where
    T: Ord,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut set = Self::new();
        for each in iter {
            if let Err(_) = set.insert(each) {
                panic!("set overflowed on extend");
            }
        }
        set
    }
}

impl<T, const N1: usize, const N2: usize> From<[T; N1]> for OrdSet<T, N2>
where
    T: Ord,
{
    fn from(mut value: [T; N1]) -> Self {
        // We don't check the size ahead of time because duplicate values might
        // not fill the set.
        value.sort_unstable();
        let mut set = Self::new();
        for each in value {
            if let Err(_) = set.insert(each) {
                panic!("set overflowed on extend");
            }
        }
        set
    }
}

impl<T, const N: usize> IntoIterator for OrdSet<T, N> {
    type Item = T;

    type IntoIter = IntoIter<T, N>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self)
    }
}

impl<'a, T, const N: usize> IntoIterator for &'a OrdSet<T, N> {
    type Item = &'a T;

    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}