use core::{
array,
borrow::Borrow,
iter::FusedIterator,
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>;
pub type IterMut<'a, K, V> = internal::IterMut<'a, K, V>;
pub type RangeMut<'a, K, V> = internal::IterMut<'a, K, V>;
pub type ValuesMut<'a, K, V> = internal::ValuesMut<'a, K, V>;
pub type CursorMut<'a, K, V> = internal::CursorMut<'a, K, V>;
#[derive(Debug, Clone)]
pub struct IntoIter<K, V, const S: usize>(array::IntoIter<(K, V), S>);
impl<K, V, const S: usize> Iterator for IntoIter<K, V, S> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<K, V, const S: usize> DoubleEndedIterator for IntoIter<K, V, S> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back()
}
}
impl<K, V, const S: usize> ExactSizeIterator for IntoIter<K, V, S> {}
impl<K, V, const S: usize> FusedIterator for IntoIter<K, V, S> {}
#[derive(Debug, Clone)]
pub struct IntoKeys<K, V, const S: usize>(IntoIter<K, V, S>);
impl<K, V, const S: usize> IntoKeys<K, V, S> {
pub fn new(iter: IntoIter<K, V, S>) -> Self {
IntoKeys(iter)
}
}
impl<K, V, const S: usize> Iterator for IntoKeys<K, V, S> {
type Item = 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<K, V, const S: usize> DoubleEndedIterator for IntoKeys<K, V, S> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(k, _)| k)
}
}
impl<K, V, const S: usize> ExactSizeIterator for IntoKeys<K, V, S> {}
impl<K, V, const S: usize> FusedIterator for IntoKeys<K, V, S> {}
#[derive(Debug, Clone)]
pub struct IntoValues<K, V, const S: usize>(IntoIter<K, V, S>);
impl<K, V, const S: usize> Iterator for IntoValues<K, V, S> {
type Item = 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<K, V, const S: usize> DoubleEndedIterator for IntoValues<K, V, S> {
fn next_back(&mut self) -> Option<Self::Item> {
self.0.next_back().map(|(_, v)| v)
}
}
impl<K, V, const S: usize> ExactSizeIterator for IntoValues<K, V, S> {}
impl<K, V, const S: usize> FusedIterator for IntoValues<K, V, S> {}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OrderedArrayMap<K, V, const S: usize> {
inner: [(K, V); S],
len: usize
}
impl<K, V, const S: usize> OrderedArrayMap<K, V, S> {
pub fn new(mut items: [(K, V); S]) -> Self
where
K: Ord
{
let len = order(&mut items);
OrderedArrayMap { inner: items, len }
}
pub const fn new_unchecked(ordered_items: [(K, V); S]) -> Self {
OrderedArrayMap {
inner: ordered_items,
len: S
}
}
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])
}
pub fn get_mut<'a, Q>(&'a mut self, key: &Q) -> Option<&'a mut V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::get_mut(&mut self.inner[..self.len], key)
}
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
internal::iter_mut(&mut self.inner[..self.len])
}
pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::lower_bound_mut(&mut self.inner[..self.len], bound)
}
pub fn range_mut<Q, R>(&mut self, range: R) -> RangeMut<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized,
R: RangeBounds<Q>
{
internal::range_mut(&mut self.inner[..self.len], range)
}
pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q>,
Q: PartialOrd + ?Sized
{
internal::upper_bound_mut(&mut self.inner[..self.len], bound)
}
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
internal::values_mut(&mut self.inner[..self.len])
}
pub fn into_keys(self) -> IntoKeys<K, V, S> {
IntoKeys(self.into_iter())
}
pub fn into_values(self) -> IntoValues<K, V, S> {
IntoValues(self.into_iter())
}
}
impl<K, V, const S: usize> From<[(K, V); S]> for OrderedArrayMap<K, V, S>
where
K: Ord
{
fn from(value: [(K, V); S]) -> Self {
OrderedArrayMap::new(value)
}
}
impl<K, V, Q, const S: usize> Index<&Q> for OrderedArrayMap<K, V, S>
where
K: Borrow<Q>,
Q: PartialOrd
{
type Output = V;
fn index(&self, key: &Q) -> &Self::Output {
self.get(key).expect("no entry found for key")
}
}
impl<K, V, const S: usize> IntoIterator for OrderedArrayMap<K, V, S> {
type Item = (K, V);
type IntoIter = IntoIter<K, V, 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, K, V, const S: usize> IntoIterator for &'a OrderedArrayMap<K, V, S> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K, V, const S: usize> IntoIterator for &'a mut OrderedArrayMap<K, V, S> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
#[cfg(test)]
mod tests {
use core::ops::Bound;
use super::*;
#[test]
fn test_new() {
let set = OrderedArrayMap::new([(5, 1), (1, 2), (3, 3), (1, 4)]);
assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![(1, 4), (3, 3), (5, 1)]);
}
#[test]
fn test_empty_map() {
let target: OrderedArrayMap<i32, i32, 0> = OrderedArrayMap::new_unchecked([]);
assert_eq!(target.get(&0), None);
assert_eq!(target.lower_bound(Bound::Included(&0)).next(), None);
assert_eq!(target.lower_bound(Bound::Included(&0)).prev(), None);
assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), None);
assert_eq!(target.lower_bound(Bound::Excluded(&0)).prev(), None);
assert_eq!(target.lower_bound(Bound::Unbounded).next(), None);
assert_eq!(target.lower_bound(Bound::Unbounded).prev(), None);
assert_eq!(target.upper_bound(Bound::Included(&0)).next(), None);
assert_eq!(target.upper_bound(Bound::Included(&0)).prev(), None);
assert_eq!(target.upper_bound(Bound::Excluded(&0)).next(), None);
assert_eq!(target.upper_bound(Bound::Excluded(&0)).prev(), None);
assert_eq!(target.upper_bound(Bound::Unbounded).next(), None);
assert_eq!(target.upper_bound(Bound::Unbounded).prev(), None);
}
#[test]
fn test_singleton_map() {
let target = OrderedArrayMap::new_unchecked([(5, 25)]);
assert_eq!(target.get(&4), None);
assert_eq!(target.get(&5), Some(&25));
assert_eq!(target.get(&6), None);
}
#[test]
fn test_map() {
let target = OrderedArrayMap::new_unchecked([(1, 1), (2, 4), (4, 16)]);
assert_eq!(target.get(&0), None);
assert_eq!(target.get(&1), Some(&1));
assert_eq!(target.get(&2), Some(&4));
assert_eq!(target.get(&3), None);
assert_eq!(target.get(&4), Some(&16));
assert_eq!(target.get(&5), None);
}
#[test]
fn test_lower_bound_included() {
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25)]);
assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&6)).next(), None);
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25), (7, 49)]);
assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&6)).next(), Some((&7, &49)));
assert_eq!(target.lower_bound(Bound::Included(&7)).next(), Some((&7, &49)));
assert_eq!(target.lower_bound(Bound::Included(&8)).next(), None);
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (3, 16), (5, 25)]);
assert_eq!(target.lower_bound(Bound::Included(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&1)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Included(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&3)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Included(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&5)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Included(&6)).next(), None);
}
#[test]
fn test_lower_bound_excluded() {
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25)]);
assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), None);
assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), None);
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (5, 25), (7, 49)]);
assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), Some((&7, &49)));
assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), Some((&7, &49)));
assert_eq!(target.lower_bound(Bound::Excluded(&7)).next(), None);
assert_eq!(target.lower_bound(Bound::Excluded(&8)).next(), None);
let target = OrderedArrayMap::new_unchecked([(1, 1), (3, 9), (3, 16), (5, 25)]);
assert_eq!(target.lower_bound(Bound::Excluded(&0)).next(), Some((&1, &1)));
assert_eq!(target.lower_bound(Bound::Excluded(&1)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&2)).next(), Some((&3, &9)));
assert_eq!(target.lower_bound(Bound::Excluded(&3)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&4)).next(), Some((&5, &25)));
assert_eq!(target.lower_bound(Bound::Excluded(&5)).next(), None);
assert_eq!(target.lower_bound(Bound::Excluded(&6)).next(), None);
}
}