use core::{
cmp::Ordering,
marker::PhantomData,
};
use bitstring::BitString;
use crate::tree::{
DefaultCompare,
Tree,
TreeProperties,
};
struct TpMap<K, V>(PhantomData<*const K>, PhantomData<*const V>)
where
K: BitString + Clone,
V: Default + Clone + Eq;
impl<K, V> TreeProperties for TpMap<K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
type Key = K;
type LeafValue = V;
type LeafValueComparer = DefaultCompare;
type Value = ();
const EMPTY: bool = true;
const IGNORE_LEAFS: bool = false;
const LEAF_EMPTY: bool = false;
}
#[derive(Clone)]
pub struct Map<K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
tree: Tree<TpMap<K, V>>,
}
impl<K, V> Default for Map<K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
fn default() -> Self {
Self::new()
}
}
impl<K, V> core::fmt::Debug for Map<K, V>
where
K: BitString + Clone + core::fmt::Debug,
V: Default + Clone + Eq + core::fmt::Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K, V> Map<K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
pub const fn new() -> Self {
Self { tree: Tree::new() }
}
pub fn insert(&mut self, prefix: K, value: V) {
self.tree.set_leaf_value(prefix, value);
}
pub fn remove(&mut self, key: K) {
let mut walk = self.tree.walk_mut();
walk.goto_insert(&key);
match walk.current().node() {
None => (), Some(node) => {
match node.get_key().len().cmp(&key.len()) {
Ordering::Less => {
walk.insert(key);
walk.delete_current();
},
Ordering::Equal | Ordering::Greater => {
walk.delete_current();
},
}
},
}
}
pub fn get(&self, key: &K) -> Option<&V> {
let mut walk = self.tree.walk::<(), ()>();
walk.goto_insert(key);
match walk.current().node() {
None => None, Some(node) => {
match node.get_key().len().cmp(&key.len()) {
Ordering::Less => {
Some(node.get_leaf_value().expect("node must be a leaf"))
},
Ordering::Equal => node.get_leaf_value(),
Ordering::Greater => {
None
},
}
},
}
}
pub fn iter(&self) -> IterMap<'_, K, V> {
IterMap {
iter: self.tree.iter_leaf(),
}
}
pub fn iter_mut(&mut self) -> IterMutMap<'_, K, V> {
IterMutMap {
iter: self.tree.iter_mut_leaf(),
}
}
pub fn iter_full(&self) -> IterMapFull<'_, K, V> {
IterMapFull {
iter: self.tree.iter_leaf_full(),
}
}
}
pub struct IterMap<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
iter: crate::tree::IterLeaf<'s, TpMap<K, V>>,
}
impl<'s, K, V> Iterator for IterMap<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
type Item = (&'s K, &'s V);
fn next(&mut self) -> Option<Self::Item> {
let (node, value) = self.iter.next()?;
Some((node.get_key(), value))
}
}
pub struct IterMutMap<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
iter: crate::tree::IterMutOwnedLeaf<'s, TpMap<K, V>>,
}
impl<'s, K, V> Iterator for IterMutMap<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
type Item = (&'s K, &'s mut V);
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}
pub struct IterMapFull<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
iter: crate::tree::IterLeafFull<'s, TpMap<K, V>>,
}
impl<'s, K, V> Iterator for IterMapFull<'s, K, V>
where
K: BitString + Clone,
V: Default + Clone + Eq,
{
type Item = (K, Option<&'s V>);
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
}