use core::{
cmp::Ordering,
marker::PhantomData,
};
use bitstring::BitString;
use crate::tree::{
DefaultCompare,
Node,
Tree,
TreeProperties,
WalkedDirection,
};
struct TpFullMap<K: BitString + Clone, V>(PhantomData<*const K>, PhantomData<*const V>);
impl<K: BitString + Clone, V> TreeProperties for TpFullMap<K, V> {
type Key = K;
type LeafValue = ();
type LeafValueComparer = DefaultCompare;
type Value = Option<V>;
const EMPTY: bool = false;
const IGNORE_LEAFS: bool = true;
const LEAF_EMPTY: bool = true;
}
#[derive(Clone)]
pub struct FullMap<K: BitString + Clone, V> {
tree: Tree<TpFullMap<K, V>>,
}
impl<K: BitString + Clone, V> Default for FullMap<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K, V> core::fmt::Debug for FullMap<K, V>
where
K: BitString + Clone + core::fmt::Debug,
V: core::fmt::Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<K, V> FullMap<K, V>
where
K: BitString + Clone,
{
pub const fn new() -> Self {
Self { tree: Tree::new() }
}
pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
let mut walk = self.tree.walk_mut();
walk.goto_insert(&key);
if let Some(node) = walk.current().node() {
if node.get_key().len() == key.len() && node.get_value().is_some() {
return Entry::Occupied(OccupiedEntry { walk });
}
}
Entry::Vacant(VacantEntry { walk, key })
}
fn occupied<'s>(&'s mut self, key: &K) -> Option<OccupiedEntry<'s, K, V>> {
let mut walk = self.tree.walk_mut();
walk.goto_insert(key);
if let Some(node) = walk.current().node() {
if node.get_key().len() == key.len() && node.get_value().is_some() {
return Some(OccupiedEntry { walk });
}
}
None
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
self.entry(key).replace(value).1
}
pub fn remove(&mut self, key: &K) -> Option<V> {
Some(self.occupied(key)?.remove())
}
pub fn get(&self, key: &K) -> Option<&V> {
self.tree.get(key)?.get_value().as_ref()
}
pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
self.tree.get_mut(key)?.get_value_mut().as_mut()
}
pub fn most_specific(&self, key: &K) -> Option<(&K, &V)> {
self.path(key.clone()).last()
}
pub fn remove_tree(&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 path(&self, key: K) -> IterPath<'_, K, V> {
IterPath {
iter: self.tree.iter_path(key),
}
}
pub fn path_mut(&mut self, key: K) -> IterPathMut<'_, K, V> {
IterPathMut {
iter: self.tree.iter_mut_path(key).into_iter(),
}
}
pub fn iter(&self) -> IterMap<'_, K, V> {
IterMap {
iter: self.tree.iter_in_order(),
}
}
pub fn iter_mut(&mut self) -> IterMutMap<'_, K, V> {
IterMutMap {
iter: self.tree.iter_mut_in_order(),
}
}
}
pub enum Entry<'s, K: BitString + Clone, V> {
Vacant(VacantEntry<'s, K, V>),
Occupied(OccupiedEntry<'s, K, V>),
}
impl<'s, K: BitString + Clone, V> Entry<'s, K, V> {
pub fn or_insert(self, default: V) -> &'s mut V {
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(default),
}
}
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'s mut V {
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(default()),
}
}
#[inline]
pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'s mut V {
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => {
let value = default(entry.key());
entry.insert(value)
},
}
}
pub fn key(&self) -> &K {
match self {
Self::Occupied(entry) => entry.key(),
Self::Vacant(entry) => entry.key(),
}
}
pub fn and_modify<F>(mut self, f: F) -> Self
where
F: FnOnce(&mut V),
{
if let Self::Occupied(ref mut entry) = self {
f(entry.get_mut())
}
self
}
pub fn or_default(self) -> &'s mut V
where
V: Default,
{
match self {
Self::Occupied(entry) => entry.into_mut(),
Self::Vacant(entry) => entry.insert(Default::default()),
}
}
pub fn insert(self, value: V) -> &'s mut V {
match self {
Self::Occupied(entry) => {
let vref = entry.into_mut();
*vref = value;
vref
},
Self::Vacant(entry) => entry.insert(value),
}
}
pub fn set(self, value: V) -> OccupiedEntry<'s, K, V> {
self.replace(value).0
}
pub fn replace(self, value: V) -> (OccupiedEntry<'s, K, V>, Option<V>) {
match self {
Self::Occupied(mut entry) => {
let old = entry.insert(value);
(entry, Some(old))
},
Self::Vacant(entry) => {
let VacantEntry { mut walk, key } = entry;
walk.insert(key);
let node = walk
.current_mut()
.node()
.expect("after insert walk should be at a node");
*node.get_value_mut() = Some(value);
(OccupiedEntry { walk }, None)
},
}
}
}
pub struct VacantEntry<'s, K: BitString + Clone + 's, V: 's> {
walk: crate::tree::WalkMutOwned<'s, TpFullMap<K, V>, WalkedDirection>,
key: K,
}
impl<'s, K: BitString + Clone, V> VacantEntry<'s, K, V> {
pub fn key(&self) -> &K {
&self.key
}
pub fn into_key(self) -> K {
self.key
}
pub fn insert(self, value: V) -> &'s mut V {
let Self { mut walk, key } = self;
walk.insert(key);
let node = walk
.into_current_mut()
.node()
.expect("after insert walk should be at a node");
*node.get_value_mut() = Some(value);
node.get_value_mut().as_mut().expect("value can't be empty")
}
}
pub struct OccupiedEntry<'s, K: BitString + Clone + 's, V: 's> {
walk: crate::tree::WalkMutOwned<'s, TpFullMap<K, V>, WalkedDirection>,
}
impl<'s, K: BitString + Clone, V> OccupiedEntry<'s, K, V> {
fn node(&self) -> &Node<TpFullMap<K, V>> {
self.walk
.current()
.node()
.expect("OccupiedEntry should have a node")
}
fn node_mut(&mut self) -> &mut Node<TpFullMap<K, V>> {
self.walk
.current_mut()
.node()
.expect("OccupiedEntry should have a node")
}
fn node_into(self) -> &'s mut Node<TpFullMap<K, V>> {
self.walk
.into_current_mut()
.node()
.expect("OccupiedEntry should have a node")
}
pub fn get(&self) -> &V {
self.node()
.get_value()
.as_ref()
.expect("OccupiedEntry should have a value")
}
pub fn get_mut(&mut self) -> &mut V {
self.node_mut()
.get_value_mut()
.as_mut()
.expect("OccupiedEntry should have a value")
}
pub fn into_mut(self) -> &'s mut V {
self.node_into()
.get_value_mut()
.as_mut()
.expect("OccupiedEntry should have a value")
}
pub fn key(&self) -> &K {
self.node().get_key()
}
pub fn insert(&mut self, value: V) -> V {
core::mem::replace(self.get_mut(), value)
}
pub fn remove(mut self) -> V {
let value = self
.node_mut()
.get_value_mut()
.take()
.expect("OccupiedEntry should have a value");
self.walk.compact_if_empty(Option::is_none);
value
}
}
pub struct IterPath<'s, K: BitString + Clone, V> {
iter: crate::tree::IterPath<'s, TpFullMap<K, V>>,
}
impl<'s, K: BitString + Clone, V> Iterator for IterPath<'s, K, V> {
type Item = (&'s K, &'s V);
fn next(&mut self) -> Option<Self::Item> {
loop {
let node = self.iter.next()?;
if let Some(value) = node.get_value() {
return Some((node.get_key(), value));
}
}
}
}
pub struct IterPathMut<'s, K: BitString + Clone, V> {
iter: crate::tree::IterMutPath<'s, TpFullMap<K, V>>,
}
impl<'s, K: BitString + Clone, V> Iterator for IterPathMut<'s, K, V> {
type Item = (&'s K, &'s mut V);
fn next(&mut self) -> Option<Self::Item> {
loop {
let (key, value, _) = self.iter.next()?;
if let Some(value) = value {
return Some((key, value));
}
}
}
}
pub struct IterMap<'s, K: BitString + Clone, V> {
iter: crate::tree::IterInOrder<'s, TpFullMap<K, V>>,
}
impl<'s, K: BitString + Clone, V> Iterator for IterMap<'s, K, V> {
type Item = (&'s K, &'s V);
fn next(&mut self) -> Option<Self::Item> {
loop {
let node = self.iter.next()?;
if let Some(value) = node.get_value() {
return Some((node.get_key(), value));
}
}
}
}
pub struct IterMutMap<'s, K: BitString + Clone, V> {
iter: crate::tree::IterMutOwnedInOrder<'s, TpFullMap<K, V>>,
}
impl<'s, K: BitString + Clone, V> Iterator for IterMutMap<'s, K, V> {
type Item = (&'s K, &'s mut V);
fn next(&mut self) -> Option<Self::Item> {
loop {
let (key, value, _) = self.iter.next()?;
if let Some(value) = value.as_mut() {
return Some((key, value));
}
}
}
}