use core::{
borrow::Borrow,
cmp::Ordering,
iter::{FusedIterator, Peekable},
ops::{Bound, RangeBounds},
slice
};
use crate::ordered::Ordered;
#[derive(Debug)]
pub struct Iter<'a, T>(slice::Iter<'a, T>);
impl<'a, T> Clone for Iter<'a, T> {
fn clone(&self) -> Self {
Self(self.0.clone())
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
}
}
impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
impl<'a, T> FusedIterator for Iter<'a, T> {}
#[derive(Debug)]
pub struct Cursor<'a, T> {
inner: &'a [T],
index: usize
}
impl<'a, T> Clone for Cursor<'a, T> {
fn clone(&self) -> Self {
Cursor {
inner: self.inner,
index: self.index
}
}
}
impl<'a, T> Cursor<'a, T> {
pub fn next(&mut self) -> Option<&'a T> {
let item = self.inner.get(self.index)?;
self.index += 1;
Some(item)
}
pub fn prev(&mut self) -> Option<&'a T> {
let index = self.index.checked_sub(1)?;
let item = self.inner.get(index)?;
self.index -= 1;
Some(item)
}
pub fn peek_next(&self) -> Option<&'a T> {
self.inner.get(self.index)
}
pub fn peek_prev(&self) -> Option<&'a T> {
let index = self.index.checked_sub(1)?;
let item = self.inner.get(index)?;
Some(item)
}
}
#[derive(Debug, Clone)]
pub struct Difference<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
a: Peekable<I1>,
b: Peekable<I2>
}
impl<'a, T, I1, I2> Difference<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
fn new(a: I1, b: I2) -> Self {
Difference {
a: a.peekable(),
b: b.peekable()
}
}
}
impl<'a, T, I1, I2> Iterator for Difference<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
loop {
let Some(b) = self.b.peek() else {
return self.a.next();
};
let a = self.a.peek()?;
let cmp = a.partial_cmp(b)?;
match cmp {
Ordering::Less => {
return self.a.next();
}
Ordering::Equal => {
self.a.next();
}
Ordering::Greater => {
self.b.next();
}
}
}
}
}
impl<'a, T, I1, I2> FusedIterator for Difference<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
}
#[derive(Debug, Clone)]
pub struct Intersection<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
a: Peekable<I1>,
b: Peekable<I2>
}
impl<'a, T, I1, I2> Intersection<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
fn new(a: I1, b: I2) -> Self {
Intersection {
a: a.peekable(),
b: b.peekable()
}
}
}
impl<'a, T, I1, I2> Iterator for Intersection<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
loop {
let a = self.a.peek()?;
let b = self.b.peek()?;
let cmp = a.partial_cmp(b)?;
match cmp {
Ordering::Less => {
self.a.next();
}
Ordering::Equal => {
self.b.next();
return self.a.next();
}
Ordering::Greater => {
self.b.next();
}
}
}
}
}
impl<'a, T, I1, I2> FusedIterator for Intersection<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
}
#[derive(Debug, Clone)]
pub struct Union<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
a: Peekable<I1>,
b: Peekable<I2>
}
impl<'a, T, I1, I2> Union<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
fn new(a: I1, b: I2) -> Self {
Union {
a: a.peekable(),
b: b.peekable()
}
}
}
impl<'a, T, I1, I2> Iterator for Union<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
let Some(a) = self.a.peek() else {
return self.b.next();
};
let Some(b) = self.b.peek() else {
return self.a.next();
};
let cmp = a.partial_cmp(b)?;
match cmp {
Ordering::Less => self.a.next(),
Ordering::Equal => {
self.b.next();
self.a.next()
}
Ordering::Greater => self.b.next()
}
}
}
impl<'a, T, I1, I2> FusedIterator for Union<'a, T, I1, I2>
where
T: PartialOrd + 'a,
I1: Iterator<Item = &'a T>,
I2: Iterator<Item = &'a T>
{
}
pub fn is_valid<T>(s: &[T]) -> bool
where
T: PartialOrd
{
s.windows(2).all(|w| w[0] < w[1])
}
pub fn order<T>(s: &mut [T]) -> usize
where
T: Ord
{
s.sort();
let mut i = 0usize;
let mut b = 0usize;
let l = s.len();
while i < l {
let val = &s[i];
while i + 1 < l && val == &s[i + 1] {
i += 1;
}
s.swap(i, b);
i += 1;
b += 1;
}
b
}
pub fn contains<T, Q>(s: &[T], value: &Q) -> bool
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
find_index(s, value).is_some()
}
pub fn difference<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> Difference<'a, T, I1::Iter, I2::Iter>
where
T: PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
Difference::new(a.ordered_iter(), b.ordered_iter())
}
pub fn get<'a, T, Q>(s: &'a [T], value: &Q) -> Option<&'a T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
find_index(s, value).map(|i| &s[i])
}
pub fn intersection<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> Intersection<'a, T, I1::Iter, I2::Iter>
where
T: PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
Intersection::new(a.ordered_iter(), b.ordered_iter())
}
pub fn is_disjoint<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> bool
where
T: 'a + PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
let mut ai = a.ordered_iter().peekable();
let mut bi = b.ordered_iter().peekable();
while let Some(a) = ai.peek()
&& let Some(b) = bi.peek()
{
match a.partial_cmp(b) {
Some(Ordering::Less) => {
ai.next();
}
Some(Ordering::Equal) => {
return false;
}
Some(Ordering::Greater) => {
bi.next();
}
None => {
return false;
}
}
}
true
}
pub fn is_subset<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> bool
where
T: 'a + PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
let mut ai = a.ordered_iter().peekable();
let mut bi = b.ordered_iter().peekable();
while let Some(a) = ai.peek()
&& let Some(b) = bi.peek()
{
match a.partial_cmp(b) {
Some(Ordering::Less) => {
return false;
}
Some(Ordering::Equal) => {
ai.next();
bi.next();
}
Some(Ordering::Greater) => {
bi.next();
}
None => {
return false;
}
}
}
ai.peek().is_none()
}
pub fn is_superset<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> bool
where
T: 'a + PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
is_subset(b, a)
}
pub fn iter<T>(s: &[T]) -> Iter<'_, T> {
Iter(s.iter())
}
pub fn lower_bound<'a, T, Q>(s: &'a [T], bound: Bound<&Q>) -> Cursor<'a, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
Cursor {
inner: s,
index: lower_bound_index(s, bound)
}
}
pub fn range<T, Q, R>(s: &[T], range: R) -> Iter<'_, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized,
R: RangeBounds<Q>
{
let start_bound = range.start_bound();
let end_bound = range.end_bound();
match (start_bound, end_bound) {
(Bound::Excluded(s), Bound::Excluded(e)) if s == e => {
panic!("range start and end are equal and excluded")
}
(Bound::Included(s) | Bound::Excluded(s), Bound::Included(e) | Bound::Excluded(e)) => match s.partial_cmp(&e) {
Some(Ordering::Greater) => panic!("range start is greater than range end"),
None => panic!("either range start or end is incomparable"),
_ => {}
},
_ => {}
}
let start = lower_bound_index(s, start_bound);
let end = upper_bound_index(s, end_bound);
Iter(s[start..end].iter())
}
pub fn union<'a, T, I1, I2>(a: &'a I1, b: &'a I2) -> Union<'a, T, I1::Iter, I2::Iter>
where
T: PartialOrd,
I1: Ordered<'a, T>,
I2: Ordered<'a, T>
{
Union::new(a.ordered_iter(), b.ordered_iter())
}
pub fn upper_bound<'a, T, Q>(s: &'a [T], bound: Bound<&Q>) -> Cursor<'a, T>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
Cursor {
inner: s,
index: upper_bound_index(s, bound)
}
}
fn find_index<T, Q>(s: &[T], value: &Q) -> Option<usize>
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
if s.is_empty() {
return None;
}
let lb = lower_bound_pred(s, value, PartialOrd::le);
if lb < s.len() && value == s[lb].borrow() {
Some(lb)
} else {
None
}
}
fn lower_bound_index<T, Q>(s: &[T], bound: Bound<&Q>) -> usize
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
match bound {
Bound::Included(key) => lower_bound_pred(s, key, PartialOrd::le),
Bound::Excluded(key) => lower_bound_pred(s, key, PartialOrd::lt),
Bound::Unbounded => 0
}
}
fn upper_bound_index<T, Q>(s: &[T], bound: Bound<&Q>) -> usize
where
T: Borrow<Q>,
Q: PartialOrd + ?Sized
{
match bound {
Bound::Included(key) => lower_bound_pred(s, key, PartialOrd::lt),
Bound::Excluded(key) => lower_bound_pred(s, key, PartialOrd::le),
Bound::Unbounded => s.len()
}
}
fn lower_bound_pred<T, Q, F>(s: &[T], key: &Q, mut pred: F) -> usize
where
T: Borrow<Q>,
Q: ?Sized,
F: FnMut(&Q, &Q) -> bool
{
let mut lb = 0usize;
let mut ub = s.len() + 1;
while ub - lb > 1 {
let current = (lb + ub) / 2;
if pred(key, s[current - 1].borrow()) {
ub = current;
} else {
lb = current;
}
}
lb
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_order() {
let s: &mut [i32] = &mut [5, 1, 5, 3, 1, 1];
let l = order(s);
assert_eq!(l, 3);
assert_eq!(vec![&1, &3, &5], s.iter().take(3).collect::<Vec<_>>());
}
#[test]
fn test_ordinal_range() {
let s: &[i32] = &[];
assert_eq!(Vec::<&i32>::new(), range(s, 1..2).collect::<Vec<_>>());
}
#[test]
fn test_min_range() {
let s: &[i32] = &[];
assert_eq!(Vec::<&i32>::new(), range(s, 1..=1).collect::<Vec<_>>());
assert_eq!(Vec::<&i32>::new(), range(s, 1..1).collect::<Vec<_>>());
}
#[test]
fn test_incomparable_half_unbounded_range() {
let s: &[f64] = &[0.0, 1.0];
assert_eq!(range(s, ..f64::NAN).collect::<Vec<_>>(), vec![&0.0, &1.0]);
}
#[test]
fn test_reversed_incomparable_half_unbounded_range() {
let s: &[f64] = &[0.0, 1.0];
assert_eq!(range(s, f64::NAN..).collect::<Vec<_>>(), Vec::<&f64>::new());
}
#[test]
#[should_panic]
fn test_incomparable_range() {
let s: &[f64] = &[];
let _ = range(s, 1.0..f64::NAN);
}
#[test]
#[should_panic]
fn test_reversed_incomparable_range() {
let s: &[f64] = &[];
let _ = range(s, f64::NAN..1.0);
}
#[test]
#[should_panic]
fn test_excluded_zero_range() {
let s: &[i32] = &[];
let _ = range(s, (Bound::Excluded(1), Bound::Excluded(1)));
}
#[test]
#[should_panic]
fn test_invalid_excluded_range() {
let s: &[i32] = &[];
let _ = range(s, 1..0);
}
#[test]
#[should_panic]
fn test_invalid_included_range() {
let s: &[i32] = &[];
let _ = range(s, 1..0);
}
}