use core::{
borrow::Borrow,
ops::{Bound, Index, RangeBounds}
};
use crate::internal::ordered_map::{self as internal, order};
pub type Iter<'a, K, V> = internal::Iter<'a, K, V>;
pub type Keys<'a, K, V> = internal::Keys<'a, K, V>;
pub type Range<'a, K, V> = internal::Iter<'a, K, V>;
pub type Values<'a, K, V> = internal::Values<'a, K, V>;
pub type Cursor<'a, K, V> = internal::Cursor<'a, K, V>;
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OrderedSliceMap<'a, K, V> {
inner: &'a [(K, V)],
len: usize
}
impl<'a, K, V> Clone for OrderedSliceMap<'a, K, V> {
fn clone(&self) -> Self {
*self
}
}
impl<'a, K, V> Copy for OrderedSliceMap<'a, K, V> {}
impl<'a, K, V> OrderedSliceMap<'a, K, V> {
pub fn new(items: &'a mut [(K, V)]) -> Self
where
K: Ord
{
let len = order(items);
OrderedSliceMap { inner: items, len }
}
pub const fn new_unchecked(ordered_items: &'a [(K, V)]) -> Self {
OrderedSliceMap {
inner: ordered_items,
len: ordered_items.len()
}
}
pub fn is_valid(&self) -> bool
where
K: PartialOrd
{
internal::is_valid(&self.inner[..self.len])
}
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::contains_key(&self.inner[..self.len], key)
}
pub fn first_key_value(&self) -> Option<(&K, &V)> {
internal::first_key_value(&self.inner[..self.len])
}
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::get(&self.inner[..self.len], key)
}
pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::get_key_value(&self.inner[..self.len], key)
}
pub const fn is_empty(&self) -> bool {
self.len == 0
}
pub fn iter(&self) -> Iter<'_, K, V> {
internal::iter(&self.inner[..self.len])
}
pub fn keys(&self) -> Keys<'_, K, V> {
internal::keys(&self.inner[..self.len])
}
pub fn last_key_value(&self) -> Option<(&K, &V)> {
internal::last_key_value(&self.inner[..self.len])
}
pub const fn len(&self) -> usize {
self.len
}
pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::lower_bound(&self.inner[..self.len], bound)
}
pub fn range<Q, R>(&self, range: R) -> Range<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized,
R: RangeBounds<Q>
{
internal::range(&self.inner[..self.len], range)
}
pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::upper_bound(&self.inner[..self.len], bound)
}
pub fn values(&self) -> Values<'_, K, V> {
internal::values(&self.inner[..self.len])
}
}
impl<'a, K, V> IntoIterator for &'a OrderedSliceMap<'a, K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K, V, Q> Index<&Q> for OrderedSliceMap<'a, K, V>
where
K: Borrow<Q>,
Q: Ord
{
type Output = V;
fn index(&self, key: &Q) -> &Self::Output {
self.get(key).expect("no entry found for key")
}
}
#[cfg(test)]
mod tests {
use core::ops::Bound;
use super::*;
#[test]
fn test_get() {
let data = [(1, 'a'), (3, 'c'), (5, 'e')];
let map = OrderedSliceMap::new_unchecked(&data);
assert_eq!(map.get(&0), None);
assert_eq!(map.get(&1), Some(&'a'));
assert_eq!(map.get(&2), None);
assert_eq!(map.get(&3), Some(&'c'));
assert_eq!(map.get(&5), Some(&'e'));
assert_eq!(map.get(&6), None);
}
#[test]
fn test_contains_key() {
let data = [(2, 4), (4, 16), (6, 36)];
let map = OrderedSliceMap::new_unchecked(&data);
assert!(map.contains_key(&2));
assert!(map.contains_key(&4));
assert!(!map.contains_key(&3));
assert!(!map.contains_key(&7));
}
#[test]
fn test_first_last() {
let data = [(1, 1), (2, 4), (3, 9)];
let map = OrderedSliceMap::new_unchecked(&data);
assert_eq!(map.first_key_value(), Some((&1, &1)));
assert_eq!(map.last_key_value(), Some((&3, &9)));
let empty: &[(i32, i32)] = &[];
let empty_map = OrderedSliceMap::new_unchecked(empty);
assert_eq!(empty_map.first_key_value(), None);
assert_eq!(empty_map.last_key_value(), None);
}
#[test]
fn test_iter() {
let data = [(1, 'a'), (2, 'b'), (3, 'c')];
let map = OrderedSliceMap::new_unchecked(&data);
let collected: Vec<_> = map.iter().collect();
assert_eq!(collected, vec![(&1, &'a'), (&2, &'b'), (&3, &'c')]);
}
#[test]
fn test_into_iter_for_ref() {
let data = [(10, 100), (20, 200)];
let map = OrderedSliceMap::new_unchecked(&data);
let collected: Vec<_> = (&map).into_iter().collect();
assert_eq!(collected, vec![(&10, &100), (&20, &200)]);
}
#[test]
fn test_index() {
let data = [(5, 50), (10, 100)];
let map = OrderedSliceMap::new_unchecked(&data);
assert_eq!(map[&5], 50);
assert_eq!(map[&10], 100);
}
#[test]
fn test_lower_bound() {
let data = [(1, 1), (3, 9), (5, 25)];
let map = OrderedSliceMap::new_unchecked(&data);
assert_eq!(map.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
assert_eq!(map.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
assert_eq!(map.lower_bound(Bound::Unbounded).next(), Some((&1, &1)));
assert_eq!(map.lower_bound(Bound::Included(&6)).next(), None);
}
#[test]
fn test_upper_bound() {
let data = [(1, 1), (3, 9), (5, 25)];
let map = OrderedSliceMap::new_unchecked(&data);
assert_eq!(map.upper_bound(Bound::Included(&3)).next(), Some((&5, &25)));
assert_eq!(map.upper_bound(Bound::Excluded(&3)).next(), Some((&3, &9)));
assert_eq!(map.upper_bound(Bound::Unbounded).next(), None);
}
#[test]
fn test_is_valid() {
let sorted = [(1, 1), (2, 4), (3, 9)];
assert!(OrderedSliceMap::new_unchecked(&sorted).keys().is_sorted());
let unsorted = [(3, 9), (1, 1)];
assert!(!OrderedSliceMap::new_unchecked(&unsorted).keys().is_sorted());
}
}