use core::{
borrow::Borrow,
cmp::Ordering,
iter::FusedIterator,
ops::{Bound, RangeBounds},
slice
};
use crate::ordered::Ordered;
#[derive(Debug)]
pub struct Iter<'a, K, V>(slice::Iter<'a, (K, V)>);
impl<'a, K, V> Clone for Iter<'a, K, V> {
fn clone(&self) -> Self {
Self(self.0.clone())
}
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(k, v)| (k, v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(k, v)| (k, v))
}
}
impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
#[derive(Debug)]
pub struct Keys<'a, K, V>(slice::Iter<'a, (K, V)>);
impl<'a, K, V> Ordered<'a, K> for Keys<'a, K, V>
where
K: PartialOrd
{
type Iter = Self;
fn ordered_iter(&'a self) -> Self::Iter {
self.clone()
}
}
impl<'a, K, V> Clone for Keys<'a, K, V> {
fn clone(&self) -> Self {
Self(self.0.clone())
}
}
impl<'a, K, V> Iterator for Keys<'a, K, V> {
type Item = &'a K;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(k, _)| k)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(k, _)| k)
}
}
impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {}
impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
#[derive(Debug)]
pub struct Values<'a, K, V>(slice::Iter<'a, (K, V)>);
impl<'a, K, V> Clone for Values<'a, K, V> {
fn clone(&self) -> Self {
Self(self.0.clone())
}
}
impl<'a, K, V> Iterator for Values<'a, K, V> {
type Item = &'a V;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(_, v)| v)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(_, v)| v)
}
}
impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {}
impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
#[derive(Debug)]
pub struct Cursor<'a, K, V> {
inner: &'a [(K, V)],
index: usize
}
impl<'a, K, V> Clone for Cursor<'a, K, V> {
fn clone(&self) -> Self {
Cursor {
inner: self.inner,
index: self.index
}
}
}
impl<'a, K, V> Cursor<'a, K, V> {
pub fn next(&mut self) -> Option<(&K, &V)> {
let (k, v) = self.inner.get(self.index)?;
self.index += 1;
Some((k, v))
}
pub fn prev(&mut self) -> Option<(&K, &V)> {
let index = self.index.checked_sub(1)?;
let (k, v) = self.inner.get(index)?;
self.index -= 1;
Some((k, v))
}
pub fn peek_next(&self) -> Option<(&K, &V)> {
self.inner.get(self.index).map(|(k, v)| (k, v))
}
pub fn peek_prev(&self) -> Option<(&K, &V)> {
let index = self.index.checked_sub(1)?;
let (k, v) = self.inner.get(index)?;
Some((k, v))
}
}
#[derive(Debug)]
pub struct IterMut<'a, K, V>(slice::IterMut<'a, (K, V)>);
impl<'a, K, V> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(k, v)| (From::<&K>::from(k), v))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(k, v)| (From::<&K>::from(k), v))
}
}
impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
#[derive(Debug)]
pub struct ValuesMut<'a, K, V>(slice::IterMut<'a, (K, V)>);
impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
type Item = &'a mut V;
fn next(&mut self) -> Option<Self::Item> {
self.0.next().map(|(_, v)| v)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(_, v)| v)
}
}
impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {}
impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
#[derive(Debug)]
pub struct CursorMut<'a, K, V> {
inner: &'a mut [(K, V)],
index: usize
}
impl<'a, K, V> CursorMut<'a, K, V> {
pub fn next(&mut self) -> Option<(&K, &mut V)> {
let (k, v) = self.inner.get_mut(self.index)?;
self.index += 1;
Some((From::<&K>::from(k), v))
}
pub fn prev(&mut self) -> Option<(&K, &mut V)> {
let index = self.index.checked_sub(1)?;
let (k, v) = self.inner.get_mut(index)?;
self.index -= 1;
Some((From::<&K>::from(k), v))
}
pub fn peek_next(&mut self) -> Option<(&K, &mut V)> {
self.inner.get_mut(self.index).map(|(k, v)| (From::<&K>::from(k), v))
}
pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> {
let index = self.index.checked_sub(1)?;
let (k, v) = self.inner.get_mut(index)?;
Some((From::<&K>::from(k), v))
}
}
pub fn is_valid<K, V>(s: &[(K, V)]) -> bool
where
K: PartialOrd
{
s.windows(2).all(|w| w[0].0 < w[1].0)
}
pub fn order<K, V>(s: &mut [(K, V)]) -> usize
where
K: Ord
{
s.sort_by(|a, b| a.0.cmp(&b.0));
let mut i = 0usize;
let mut b = 0usize;
let l = s.len();
while i < l {
let val = &s[i].0;
while i + 1 < l && val == &s[i + 1].0 {
i += 1;
}
s.swap(i, b);
i += 1;
b += 1;
}
b
}
pub fn contains_key<K, V, Q>(s: &[(K, V)], key: &Q) -> bool
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
find_index(s, key).is_some()
}
pub fn first_key_value<K, V>(s: &[(K, V)]) -> Option<(&K, &V)> {
s.first().map(|(k, v)| (k, v))
}
pub fn get<'a, K, V, Q>(s: &'a [(K, V)], key: &Q) -> Option<&'a V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
find_index(s, key).map(|i| &s[i].1)
}
pub fn get_key_value<'a, K, V, Q>(s: &'a [(K, V)], key: &Q) -> Option<(&'a K, &'a V)>
where
K: Borrow<Q> + 'a,
Q: PartialOrd + ?Sized
{
find_index(s, key).map(|i| {
let (k, v) = &s[i];
(k, v)
})
}
pub fn iter<K, V>(s: &[(K, V)]) -> Iter<'_, K, V> {
Iter(s.iter())
}
pub fn keys<K, V>(s: &[(K, V)]) -> Keys<'_, K, V> {
Keys(s.iter())
}
pub fn last_key_value<K, V>(s: &[(K, V)]) -> Option<(&K, &V)> {
s.last().map(|(k, v)| (k, v))
}
pub fn lower_bound<'a, K, V, Q>(s: &'a [(K, V)], bound: Bound<&Q>) -> Cursor<'a, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
Cursor {
inner: s,
index: lower_bound_index(s, bound)
}
}
pub fn range<K, V, Q, R>(s: &[(K, V)], range: R) -> Iter<'_, K, V>
where
K: 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 upper_bound<'a, K, V, Q>(s: &'a [(K, V)], bound: Bound<&Q>) -> Cursor<'a, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
Cursor {
inner: s,
index: upper_bound_index(s, bound)
}
}
pub fn values<K, V>(s: &[(K, V)]) -> Values<'_, K, V> {
Values(s.iter())
}
pub fn get_mut<'a, K, V, Q>(s: &'a mut [(K, V)], key: &Q) -> Option<&'a mut V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
find_index(s, key).map(|i| &mut s[i].1)
}
pub fn iter_mut<K, V>(s: &mut [(K, V)]) -> IterMut<'_, K, V> {
IterMut(s.iter_mut())
}
pub fn lower_bound_mut<'a, K, V, Q>(s: &'a mut [(K, V)], bound: Bound<&Q>) -> CursorMut<'a, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
let index = lower_bound_index(s, bound);
CursorMut { inner: s, index }
}
pub fn range_mut<K, V, Q, R>(s: &mut [(K, V)], range: R) -> IterMut<'_, K, V>
where
K: 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);
IterMut(s[start..end].iter_mut())
}
pub fn upper_bound_mut<'a, K, V, Q>(s: &'a mut [(K, V)], bound: Bound<&Q>) -> CursorMut<'a, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
let index = upper_bound_index(s, bound);
CursorMut { inner: s, index }
}
pub fn values_mut<K, V>(s: &mut [(K, V)]) -> ValuesMut<'_, K, V> {
ValuesMut(s.iter_mut())
}
fn find_index<K, V, Q>(s: &[(K, V)], key: &Q) -> Option<usize>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
if s.is_empty() {
return None;
}
let lb = lower_bound_pred(s, key, PartialOrd::le);
if lb < s.len() && key == s[lb].0.borrow() {
Some(lb)
} else {
None
}
}
fn lower_bound_index<K, V, Q>(s: &[(K, V)], bound: Bound<&Q>) -> usize
where
K: 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<K, V, Q>(s: &[(K, V)], bound: Bound<&Q>) -> usize
where
K: 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<K, V, Q, F>(s: &[(K, V)], key: &Q, mut pred: F) -> usize
where
K: 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].0.borrow()) {
ub = current;
} else {
lb = current;
}
}
lb
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_ordinal_range() {
let s: &[(i32, i32)] = &[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16)];
assert_eq!(range(s, 1..=2).collect::<Vec<_>>(), vec![(&1, &1), (&2, &4)]);
assert_eq!(range(s, 1..2).collect::<Vec<_>>(), vec![(&1, &1)]);
}
#[test]
fn test_overlapped_range() {
let s: &[(i32, i32)] = &[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16)];
assert_eq!(range(s, 1..=1).collect::<Vec<_>>(), vec![(&1, &1)]);
assert_eq!(range(s, 1..1).collect::<Vec<_>>(), vec![]);
}
#[test]
fn test_incomparable_half_unbounded_range() {
let s: &[(f64, i32)] = &[(0.0, 0), (1.0, 1)];
assert_eq!(range(s, ..f64::NAN).collect::<Vec<_>>(), vec![(&0.0, &0), (&1.0, &1)]);
}
#[test]
fn test_reversed_incomparable_half_unbounded_range() {
let s: &[(f64, i32)] = &[(0.0, 0), (1.0, 1)];
assert_eq!(range(s, f64::NAN..).collect::<Vec<_>>(), vec![]);
}
#[test]
fn test_incomparable_half_unbounded_range_mut() {
let s: &mut [(f64, i32)] = &mut [(0.0, 0), (1.0, 1)];
assert_eq!(
range_mut(s, ..f64::NAN).collect::<Vec<_>>(),
vec![(&0.0, &mut 0), (&1.0, &mut 1)]
);
}
#[test]
fn test_reversed_incomparable_half_unbounded_range_mut() {
let s: &mut [(f64, i32)] = &mut [(0.0, 0), (1.0, 1)];
assert_eq!(range_mut(s, f64::NAN..).collect::<Vec<_>>(), vec![]);
}
#[test]
#[should_panic]
fn test_incomparable_range() {
let s: &[(f64, i32)] = &[];
let _ = range(s, 1.0..f64::NAN);
}
#[test]
#[should_panic]
fn test_reversed_incomparable_range() {
let s: &[(f64, i32)] = &[];
let _ = range(s, f64::NAN..1.0);
}
#[test]
#[should_panic]
fn test_both_incomparable_range() {
let s: &[(f64, i32)] = &[];
let _ = range(s, f64::NAN..f64::NAN);
}
#[test]
#[should_panic]
fn test_excluded_overlapped_range() {
let s: &[(i32, i32)] = &[];
let _ = range(s, (Bound::Excluded(1), Bound::Excluded(1)));
}
#[test]
#[should_panic]
fn test_invalid_excluded_range() {
let s: &[(i32, i32)] = &[];
let _ = range(s, 1..0);
}
#[test]
#[should_panic]
fn test_invalid_included_range() {
let s: &[(i32, i32)] = &[];
let _ = range(s, 1..0);
}
#[test]
#[should_panic]
fn test_incomparable_range_mut() {
let s: &mut [(f64, i32)] = &mut [];
let _ = range_mut(s, 1.0..f64::NAN);
}
#[test]
#[should_panic]
fn test_reversed_incomparable_range_mut() {
let s: &mut [(f64, i32)] = &mut [];
let _ = range(s, f64::NAN..1.0);
}
}