use core::{
borrow::Borrow,
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, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OrderedSliceSet<'a, T> {
inner: &'a [T],
len: usize
}
impl<'a, T> Clone for OrderedSliceSet<'a, T> {
fn clone(&self) -> Self {
*self
}
}
impl<'a, T> Copy for OrderedSliceSet<'a, T> {}
impl<'a, T> OrderedSliceSet<'a, T> {
pub fn new(items: &'a mut [T]) -> Self
where
T: Ord
{
let len = order(items);
OrderedSliceSet { inner: items, len }
}
pub const fn new_unchecked(ordered_items: &'a [T]) -> Self {
let len = ordered_items.len();
OrderedSliceSet {
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<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<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<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<O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
where
T: PartialOrd
{
internal::is_subset(self, other)
}
pub fn is_superset<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<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: PartialOrd> Ordered<'a, T> for OrderedSliceSet<'a, T> {
type Iter = Iter<'a, T>;
fn ordered_iter(&'a self) -> Self::Iter {
self.iter()
}
}
impl<'a, T> IntoIterator for &'a OrderedSliceSet<'a, T> {
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 mut data = [5, 1, 3, 1];
let set = OrderedSliceSet::new(&mut data);
assert_eq!(set.iter().collect::<Vec<_>>(), vec![&1, &3, &5]);
}
#[test]
fn test_contains() {
let data = [1, 3, 5, 7];
let set = OrderedSliceSet::new_unchecked(&data);
assert!(set.contains(&1));
assert!(set.contains(&7));
assert!(!set.contains(&2));
assert!(!set.contains(&8));
}
#[test]
fn test_get() {
let data = [10, 20, 30];
let set = OrderedSliceSet::new_unchecked(&data);
assert_eq!(set.get(&20), Some(&20));
assert_eq!(set.get(&15), None);
}
#[test]
fn test_first_last() {
let data = [2, 4, 6, 8];
let set = OrderedSliceSet::new_unchecked(&data);
assert_eq!(set.first(), Some(&2));
assert_eq!(set.last(), Some(&8));
let empty: &[i32] = &[];
let empty_set = OrderedSliceSet::new_unchecked(empty);
assert_eq!(empty_set.first(), None);
assert_eq!(empty_set.last(), None);
}
#[test]
fn test_iter_and_into_iter() {
let data = [1, 2, 3];
let set = OrderedSliceSet::new_unchecked(&data);
let v1: Vec<_> = set.iter().collect();
let v2: Vec<_> = set.into_iter().collect();
assert_eq!(v1, vec![&1, &2, &3]);
assert_eq!(v2, vec![&1, &2, &3]);
}
#[test]
fn test_subset_superset_disjoint() {
let a_data = [1, 2, 3];
let b_data = [1, 2, 3, 4, 5];
let c_data = [6, 7, 8];
let a = OrderedSliceSet::new_unchecked(&a_data);
let b = OrderedSliceSet::new_unchecked(&b_data);
let c = OrderedSliceSet::new_unchecked(&c_data);
assert!(a.is_subset(&b));
assert!(b.is_superset(&a));
assert!(a.is_disjoint(&c));
assert!(!a.is_disjoint(&b));
assert!(c.is_disjoint(&a));
}
#[test]
fn test_difference() {
let a_data = [1, 2, 3, 4, 5];
let b_data = [2, 4];
let a = OrderedSliceSet::new_unchecked(&a_data);
let b = OrderedSliceSet::new_unchecked(&b_data);
let diff: Vec<_> = a.difference(&b).collect();
assert_eq!(diff, vec![&1, &3, &5]);
}
#[test]
fn test_intersection() {
let a_data = [1, 2, 3, 4, 5];
let b_data = [2, 4, 6];
let a = OrderedSliceSet::new_unchecked(&a_data);
let b = OrderedSliceSet::new_unchecked(&b_data);
let inter: Vec<_> = a.intersection(&b).collect();
assert_eq!(inter, vec![&2, &4]);
}
#[test]
fn test_union() {
let a_data = [1, 3, 5];
let b_data = [2, 3, 4];
let a = OrderedSliceSet::new_unchecked(&a_data);
let b = OrderedSliceSet::new_unchecked(&b_data);
let uni: Vec<_> = a.union(&b).collect();
assert_eq!(uni, vec![&1, &2, &3, &4, &5]);
}
#[test]
fn test_lower_bound() {
let data = [1, 3, 5, 7];
let set = OrderedSliceSet::new_unchecked(&data);
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::Included(&8)).next(), None);
}
#[test]
fn test_upper_bound() {
let data = [1, 3, 5, 7];
let set = OrderedSliceSet::new_unchecked(&data);
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 data = [1, 2, 3, 4, 5];
let set = OrderedSliceSet::new_unchecked(&data);
assert_eq!(set.range(2..=4).copied().collect::<Vec<_>>(), vec![2, 3, 4]);
assert_eq!(set.range(2..4).copied().collect::<Vec<_>>(), vec![2, 3]);
assert_eq!(set.range(..3).copied().collect::<Vec<_>>(), vec![1, 2]);
assert_eq!(set.range(3..).copied().collect::<Vec<_>>(), vec![3, 4, 5]);
}
#[test]
fn test_is_valid() {
let mut sorted = [1, 2, 3, 4];
assert!(OrderedSliceSet::new(&mut sorted).iter().is_sorted());
let mut unsorted = [3, 1, 2];
assert!(OrderedSliceSet::new(&mut unsorted).iter().is_sorted());
}
}