use core::{
array,
borrow::Borrow,
iter::FusedIterator,
ops::{Bound, RangeBounds}
};
use crate::{
internal::ordered_set::{self as internal, order},
ordered::Ordered
};
type Iter<'a, T> = internal::Iter<'a, T>;
type Cursor<'a, T> = internal::Cursor<'a, T>;
type Difference<'a, T, I1, I2> = internal::Difference<'a, T, I1, I2>;
type Intersection<'a, T, I1, I2> = internal::Intersection<'a, T, I1, I2>;
type Union<'a, T, I1, I2> = internal::Union<'a, T, I1, I2>;
#[derive(Debug)]
pub struct IntoIter<T, const S: usize>(array::IntoIter<T, S>);
impl<T, const S: usize> Iterator for IntoIter<T, S> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<T, const S: usize> DoubleEndedIterator for IntoIter<T, S> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
}
}
impl<T, const S: usize> ExactSizeIterator for IntoIter<T, S> {}
impl<T, const S: usize> FusedIterator for IntoIter<T, S> {}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OrderedArraySet<T, const S: usize> {
inner: [T; S],
len: usize
}
impl<T, const S: usize> OrderedArraySet<T, S> {
pub fn new(mut items: [T; S]) -> Self
where
T: Ord
{
let len = order(&mut items);
OrderedArraySet { inner: items, len }
}
pub const fn new_unchecked(ordered_items: [T; S]) -> Self {
let len = ordered_items.len();
OrderedArraySet {
inner: ordered_items,
len
}
}
pub fn is_valid(&self) -> bool
where
T: PartialOrd
{
internal::is_valid(&self.inner[..self.len])
}
pub fn contains<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::contains(&self.inner[..self.len], value)
}
pub fn difference<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> Difference<'a, T, Iter<'a, T>, O::Iter>
where
T: PartialOrd
{
internal::difference(self, other)
}
pub fn first(&self) -> Option<&T> {
self.inner[..self.len].first()
}
pub fn get<Q>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::get(&self.inner[..self.len], value)
}
pub fn intersection<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> Intersection<'a, T, Iter<'a, T>, O::Iter>
where
T: PartialOrd
{
internal::intersection(self, other)
}
pub fn is_disjoint<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
where
T: PartialOrd
{
internal::is_disjoint(self, other)
}
pub const fn is_empty(&self) -> bool {
self.len == 0
}
pub fn is_subset<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
where
T: PartialOrd
{
internal::is_subset(self, other)
}
pub fn is_superset<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
where
T: PartialOrd
{
internal::is_superset(self, other)
}
pub fn iter(&self) -> Iter<'_, T> {
internal::iter(&self.inner[..self.len])
}
pub fn last(&self) -> Option<&T> {
self.inner[..self.len].last()
}
pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::lower_bound(&self.inner[..self.len], bound)
}
pub fn range<Q, R>(&self, range: R) -> Iter<'_, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized,
R: RangeBounds<Q>
{
internal::range(&self.inner[..self.len], range)
}
pub fn union<'a, O: Ordered<'a, T>>(&'a self, other: &'a O) -> Union<'a, T, Iter<'a, T>, O::Iter>
where
T: PartialOrd
{
internal::union(self, other)
}
pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::upper_bound(&self.inner[..self.len], bound)
}
}
impl<'a, T: 'a + PartialOrd, const S: usize> Ordered<'a, T> for OrderedArraySet<T, S> {
type Iter = Iter<'a, T>;
fn ordered_iter(&'a self) -> Iter<'a, T> {
self.iter()
}
}
impl<T, const S: usize> From<[T; S]> for OrderedArraySet<T, S>
where
T: Ord
{
fn from(value: [T; S]) -> Self {
OrderedArraySet::new(value)
}
}
impl<T, const S: usize> IntoIterator for OrderedArraySet<T, S> {
type Item = T;
type IntoIter = IntoIter<T, S>;
fn into_iter(self) -> Self::IntoIter {
let to_back = self.inner.len() - self.len;
let mut inner = self.inner.into_iter();
if to_back > 0 {
inner.nth_back(to_back - 1);
}
IntoIter(inner)
}
}
impl<'a, T, const S: usize> IntoIterator for &'a OrderedArraySet<T, S> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[cfg(test)]
mod tests {
use core::ops::Bound;
use super::*;
#[test]
fn test_new() {
let set = OrderedArraySet::new([5, 1, 3, 1]);
assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 3, 5]);
}
#[test]
fn test_contains() {
let set = OrderedArraySet::new_unchecked([1, 3, 5, 7]);
assert!(set.contains(&1));
assert!(set.contains(&5));
assert!(!set.contains(&2));
assert!(!set.contains(&8));
}
#[test]
fn test_get() {
let set = OrderedArraySet::new_unchecked([10, 20, 30]);
assert_eq!(set.get(&20), Some(&20));
assert_eq!(set.get(&15), None);
}
#[test]
fn test_first_last() {
let set = OrderedArraySet::new_unchecked([2, 4, 6, 8]);
assert_eq!(set.first(), Some(&2));
assert_eq!(set.last(), Some(&8));
let empty: OrderedArraySet<i32, 0> = OrderedArraySet::new_unchecked([]);
assert_eq!(empty.first(), None);
assert_eq!(empty.last(), None);
}
#[test]
fn test_iter() {
let set = OrderedArraySet::new_unchecked([1, 2, 3]);
let v: Vec<_> = set.iter().collect();
assert_eq!(v, vec![&1, &2, &3]);
}
#[test]
fn test_into_iter_consuming() {
let set = OrderedArraySet::new_unchecked([10, 20, 30]);
let v: Vec<_> = set.into_iter().collect();
assert_eq!(v, vec![10, 20, 30]);
}
#[test]
fn test_is_subset_superset_disjoint() {
let a = OrderedArraySet::new_unchecked([1, 2, 3]);
let b = OrderedArraySet::new_unchecked([1, 2, 3, 4, 5]);
assert!(a.is_subset(&b));
assert!(b.is_superset(&a));
let c = OrderedArraySet::new_unchecked([6, 7, 8]);
assert!(a.is_disjoint(&c));
assert!(!a.is_disjoint(&b));
}
#[test]
fn test_lower_bound() {
let set = OrderedArraySet::new_unchecked([1, 3, 5, 7]);
assert_eq!(set.lower_bound(Bound::Included(&3)).next(), Some(&3));
assert_eq!(set.lower_bound(Bound::Excluded(&3)).next(), Some(&5));
assert_eq!(set.lower_bound(Bound::Included(&4)).next(), Some(&5));
assert_eq!(set.lower_bound(Bound::Unbounded).next(), Some(&1));
assert_eq!(set.lower_bound(Bound::Included(&8)).next(), None);
}
#[test]
fn test_upper_bound() {
let set = OrderedArraySet::new_unchecked([1, 3, 5, 7]);
assert_eq!(set.upper_bound(Bound::Included(&3)).next(), Some(&5));
assert_eq!(set.upper_bound(Bound::Excluded(&3)).next(), Some(&3));
assert_eq!(set.upper_bound(Bound::Unbounded).next(), None);
}
#[test]
fn test_range() {
let set = OrderedArraySet::new_unchecked([1, 2, 3, 4, 5]);
assert_eq!(set.range(2..=4).collect::<Vec<_>>(), &[&2, &3, &4]);
assert_eq!(set.range(2..4).collect::<Vec<_>>(), &[&2, &3]);
assert_eq!(set.range(..3).collect::<Vec<_>>(), &[&1, &2]);
assert_eq!(set.range(3..).collect::<Vec<_>>(), &[&3, &4, &5]);
}
#[test]
fn test_difference() {
let a = OrderedArraySet::new_unchecked([1, 2, 3, 4, 5]);
let b = OrderedArraySet::new_unchecked([2, 4]);
let diff: Vec<_> = a.difference(&b).collect();
assert_eq!(diff, vec![&1, &3, &5]);
}
#[test]
fn test_intersection() {
let a = OrderedArraySet::new_unchecked([1, 2, 3, 4, 5]);
let b = OrderedArraySet::new_unchecked([2, 4, 6]);
let inter: Vec<_> = a.intersection(&b).collect();
assert_eq!(inter, vec![&2, &4]);
}
#[test]
fn test_union() {
let a = OrderedArraySet::new_unchecked([1, 3, 5]);
let b = OrderedArraySet::new_unchecked([2, 3, 4]);
let uni: Vec<_> = a.union(&b).collect();
assert_eq!(uni, vec![&1, &2, &3, &4, &5]);
}
#[test]
fn test_new_sorts() {
let set = OrderedArraySet::new([5, 1, 3, 2, 4]);
assert!(set.iter().is_sorted());
let v: Vec<_> = set.iter().copied().collect();
assert_eq!(v, vec![1, 2, 3, 4, 5]);
}
#[test]
fn test_is_valid() {
assert!(OrderedArraySet::new_unchecked([1, 2, 3]).iter().is_sorted());
assert!(!OrderedArraySet::new_unchecked([3, 1, 2]).iter().is_sorted());
}
}