#![deny(missing_docs)]
#![cfg_attr(test, feature(btree_cursors, assert_matches))]
#[derive(Clone)]
pub struct BTreeMap<K, V> {
len: usize,
tree: Tree<K, V>,
}
impl<K, V> Default for BTreeMap<K, V> {
fn default() -> Self {
Self::new()
}
}
const DEFAULT_BRANCH: u16 = 64;
const DEFAULT_ALLOC_UNIT: u8 = 8;
impl<K, V> BTreeMap<K, V> {
#[cfg(test)]
pub(crate) fn check(&self) {}
#[must_use]
pub fn new() -> Self {
Self::with_branch_and_unit(DEFAULT_BRANCH, DEFAULT_ALLOC_UNIT)
}
#[must_use]
pub fn with_branch_and_unit(branch: u16, allocation_unit: u8) -> Self {
assert!(branch >= 6);
assert!(branch <= 512);
assert!(allocation_unit > 0);
Self {
len: 0,
tree: Tree::new(branch, allocation_unit),
}
}
pub fn clear(&mut self) {
self.len = 0;
let (b, au) = self.tree.bau();
self.tree = Tree::new(b, au);
}
#[must_use]
pub fn len(&self) -> usize {
self.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
where
K: Ord,
{
let cursor = self.lower_bound_mut(Bound::Included(&key));
let found = if let Some(kv) = cursor.peek_next() {
kv.0 == &key
} else {
false
};
if found {
Entry::Occupied(OccupiedEntry { cursor })
} else {
Entry::Vacant(VacantEntry { key, cursor })
}
}
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
where
K: Ord,
{
if self.is_empty() {
None
} else {
let cursor = self.lower_bound_mut(Bound::Unbounded);
Some(OccupiedEntry { cursor })
}
}
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
where
K: Ord,
{
if self.is_empty() {
None
} else {
let mut cursor = self.upper_bound_mut(Bound::Unbounded);
cursor.prev();
Some(OccupiedEntry { cursor })
}
}
pub fn insert(&mut self, key: K, value: V) -> Option<V>
where
K: Ord,
{
let mut x = InsertCtx {
value: Some(value),
split: None,
};
self.tree.insert(key, &mut x);
if let Some(split) = x.split {
self.tree.new_root(split);
}
if x.value.is_none() {
self.len += 1;
}
x.value
}
pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>>
where
K: Ord,
{
match self.entry(key) {
Entry::Occupied(entry) => Err(OccupiedError { entry, value }),
Entry::Vacant(entry) => Ok(entry.insert(value)),
}
}
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.get(key).is_some()
}
pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.remove_entry(key).map(|(_k, v)| v)
}
pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let result = self.tree.remove(key)?;
self.len -= 1;
Some(result)
}
pub fn pop_first(&mut self) -> Option<(K, V)> {
let result = self.tree.pop_first()?;
self.len -= 1;
Some(result)
}
pub fn pop_last(&mut self) -> Option<(K, V)> {
let result = self.tree.pop_last()?;
self.len -= 1;
Some(result)
}
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&K, &mut V) -> bool,
K: Ord,
{
let mut c = self.lower_bound_mut(Bound::Unbounded);
while let Some((k, v)) = c.next() {
if !f(k, v) {
c.remove_prev();
}
}
}
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.tree.get(key)
}
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.tree.get_mut(key)
}
pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.tree.get_key_value(key)
}
#[must_use]
pub fn first_key_value(&self) -> Option<(&K, &V)> {
self.tree.iter().next()
}
#[must_use]
pub fn last_key_value(&self) -> Option<(&K, &V)> {
self.tree.iter().next_back()
}
pub fn append(&mut self, other: &mut BTreeMap<K, V>)
where
K: Ord,
{
let (b, au) = other.tree.bau();
let rep = Tree::new(b, au);
let tree = mem::replace(&mut other.tree, rep);
let temp = BTreeMap {
len: other.len,
tree,
};
other.len = 0;
for (k, v) in temp {
self.insert(k, v);
}
}
pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
where
K: Borrow<Q> + Ord,
{
let mut map = Self::new();
let mut from = self.lower_bound_mut(Bound::Included(key));
let mut to = map.lower_bound_mut(Bound::Unbounded);
while let Some((k, v)) = from.remove_next() {
unsafe {
to.insert_before_unchecked(k, v);
}
}
map
}
pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F>
where
K: Ord,
F: FnMut(&K, &mut V) -> bool,
{
let source = self.lower_bound_mut(Bound::Unbounded);
ExtractIf { source, pred }
}
#[must_use]
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
len: self.len,
inner: self.tree.iter(),
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
IterMut {
len: self.len,
inner: self.tree.iter_mut(),
}
}
pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
check_range(&range);
self.tree.range(&range)
}
pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V>
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
check_range(&range);
self.tree.range_mut(&range)
}
#[must_use]
pub fn keys(&self) -> Keys<'_, K, V> {
Keys(self.iter())
}
#[must_use]
pub fn values(&self) -> Values<'_, K, V> {
Values(self.iter())
}
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
ValuesMut(self.iter_mut())
}
#[must_use]
pub fn into_keys(self) -> IntoKeys<K, V> {
IntoKeys(self.into_iter())
}
#[must_use]
pub fn into_values(self) -> IntoValues<K, V> {
IntoValues(self.into_iter())
}
pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
CursorMut::lower_bound(self, bound)
}
pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
CursorMut::upper_bound(self, bound)
}
#[must_use]
pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Cursor::lower_bound(self, bound)
}
#[must_use]
pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Cursor::upper_bound(self, bound)
}
} use std::hash::{Hash, Hasher};
impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
fn hash<H: Hasher>(&self, state: &mut H) {
for elt in self {
elt.hash(state);
}
}
}
impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
fn eq(&self, other: &BTreeMap<K, V>) -> bool {
self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
}
}
impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
self.iter().partial_cmp(other.iter())
}
}
impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
self.iter().cmp(other.iter())
}
}
impl<K, V> IntoIterator for BTreeMap<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
fn into_iter(self) -> IntoIter<K, V> {
IntoIter::new(self)
}
}
impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
}
}
impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
fn into_iter(self) -> IterMut<'a, K, V> {
self.iter_mut()
}
}
impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
let mut map = BTreeMap::new();
for (k, v) in iter {
map.insert(k, v);
}
map
}
}
impl<K, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V>
where
K: Ord,
{
fn from(arr: [(K, V); N]) -> BTreeMap<K, V> {
let mut map = BTreeMap::new();
for (k, v) in arr {
map.insert(k, v);
}
map
}
}
impl<K, V> Extend<(K, V)> for BTreeMap<K, V>
where
K: Ord,
{
fn extend<T>(&mut self, iter: T)
where
T: IntoIterator<Item = (K, V)>,
{
for (k, v) in iter {
self.insert(k, v);
}
}
}
impl<'a, K, V> Extend<(&'a K, &'a V)> for BTreeMap<K, V>
where
K: Ord + Copy,
V: Copy,
{
fn extend<I>(&mut self, iter: I)
where
I: IntoIterator<Item = (&'a K, &'a V)>,
{
for (&k, &v) in iter {
self.insert(k, v);
}
}
}
impl<K, Q, V> std::ops::Index<&Q> for BTreeMap<K, V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
type Output = V;
#[inline]
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
}
}
impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
#[cfg(feature = "serde")]
use serde::{
de::{MapAccess, Visitor},
ser::SerializeMap,
Deserialize, Deserializer, Serialize,
};
#[cfg(feature = "serde")]
impl<K, V> Serialize for BTreeMap<K, V>
where
K: serde::Serialize,
V: serde::Serialize,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: serde::Serializer,
{
let mut map = serializer.serialize_map(Some(self.len()))?;
for (k, v) in self {
map.serialize_entry(k, v)?;
}
map.end()
}
}
#[cfg(feature = "serde")]
struct BTreeMapVisitor<K, V> {
marker: PhantomData<fn() -> BTreeMap<K, V>>,
}
#[cfg(feature = "serde")]
impl<K, V> BTreeMapVisitor<K, V> {
fn new() -> Self {
BTreeMapVisitor {
marker: PhantomData,
}
}
}
#[cfg(feature = "serde")]
impl<'de, K, V> Visitor<'de> for BTreeMapVisitor<K, V>
where
K: Deserialize<'de> + Ord,
V: Deserialize<'de>,
{
type Value = BTreeMap<K, V>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("BTreeMap")
}
fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
where
M: MapAccess<'de>,
{
let mut map = BTreeMap::new();
{
let mut c = map.lower_bound_mut(Bound::Unbounded);
loop {
if let Some((k, v)) = access.next_entry()? {
if let Some((pk, _)) = c.peek_prev() {
if pk >= &k {
map.insert(k, v);
break;
}
}
unsafe {
c.insert_before_unchecked(k, v);
}
} else {
return Ok(map);
}
}
}
while let Some((k, v)) = access.next_entry()? {
map.insert(k, v);
}
return Ok(map);
}
}
#[cfg(feature = "serde")]
impl<'de, K, V> Deserialize<'de> for BTreeMap<K, V>
where
K: Deserialize<'de> + Ord,
V: Deserialize<'de>,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
deserializer.deserialize_map(BTreeMapVisitor::new())
}
}
use std::{
borrow::Borrow,
cmp::Ordering,
error::Error,
fmt,
fmt::Debug,
iter::FusedIterator,
marker::PhantomData,
mem,
ops::{Bound, RangeBounds},
};
type StkVec<T> = arrayvec::ArrayVec<T, 15>;
mod vecs;
use vecs::*;
type TreeVec<K, V> = ShortVec<Tree<K, V>>;
type Split<K, V> = ((K, V), Tree<K, V>);
struct InsertCtx<K, V> {
value: Option<V>,
split: Option<Split<K, V>>,
}
fn check_range<T, R>(range: &R)
where
T: Ord + ?Sized,
R: RangeBounds<T>,
{
use Bound::{Excluded, Included};
match (range.start_bound(), range.end_bound()) {
(Included(s) | Excluded(s), Included(e)) | (Included(s), Excluded(e)) => {
assert!(e >= s, "range start is greater than range end in BTreeMap");
}
(Excluded(s), Excluded(e)) => {
assert!(
e != s,
"range start and end are equal and excluded in BTreeMap"
);
assert!(e >= s, "range start is greater than range end in BTreeMap");
}
_ => {}
}
}
#[derive(Debug, Clone)]
enum Tree<K, V> {
L(Leaf<K, V>),
NL(NonLeaf<K, V>),
}
impl<K, V> Default for Tree<K, V> {
fn default() -> Self {
Self::new(DEFAULT_BRANCH, DEFAULT_ALLOC_UNIT)
}
}
impl<K, V> Tree<K, V> {
fn new(b: u16, au: u8) -> Self {
Tree::L(Leaf::new(b, au))
}
fn bau(&self) -> (u16, u8) {
match self {
Tree::L(leaf) => leaf.bau(),
Tree::NL(nonleaf) => nonleaf.v.bau(),
}
}
fn insert(&mut self, key: K, x: &mut InsertCtx<K, V>)
where
K: Ord,
{
match self {
Tree::L(leaf) => leaf.insert(key, x),
Tree::NL(nonleaf) => nonleaf.insert(key, x),
}
}
fn new_root(&mut self, (med, right): Split<K, V>) {
let (b, au) = self.bau();
let mut nl = NonLeafInner::new(b, au);
nl.v.0.push(med);
nl.c.push(mem::take(self));
nl.c.push(right);
*self = Tree::NL(nl);
}
unsafe fn nonleaf(&mut self) -> &mut NonLeaf<K, V> {
match self {
Tree::NL(nl) => nl,
Tree::L(_) => unsafe { std::hint::unreachable_unchecked() },
}
}
unsafe fn leaf(&mut self) -> &mut Leaf<K, V> {
match self {
Tree::L(leaf) => leaf,
Tree::NL(_) => unsafe { std::hint::unreachable_unchecked() },
}
}
fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match self {
Tree::L(leaf) => leaf.remove(key),
Tree::NL(nonleaf) => nonleaf.remove(key),
}
}
fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut s = self;
loop {
match s {
Tree::L(leaf) => return leaf.get_key_value(key),
Tree::NL(nl) => match nl.v.look(key) {
Ok(i) => return Some(nl.v.0.ix(i)),
Err(i) => s = nl.c.ix(i),
},
}
}
}
fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut s = self;
loop {
match s {
Tree::L(leaf) => return leaf.get(key),
Tree::NL(nl) => match nl.v.look(key) {
Ok(i) => return Some(nl.v.0.ixv(i)),
Err(i) => s = nl.c.ix(i),
},
}
}
}
fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut s = self;
loop {
match s {
Tree::L(leaf) => return leaf.get_mut(key),
Tree::NL(nl) => match nl.v.look(key) {
Ok(i) => return Some(nl.v.0.ixmv(i)),
Err(i) => s = nl.c.ixm(i),
},
}
}
}
fn pop_first(&mut self) -> Option<(K, V)> {
match self {
Tree::L(leaf) => leaf.pop_first(),
Tree::NL(nonleaf) => nonleaf.pop_first(),
}
}
fn pop_last(&mut self) -> Option<(K, V)> {
match self {
Tree::L(leaf) => leaf.0.pop(),
Tree::NL(nonleaf) => nonleaf.pop_last(),
}
}
fn iter_mut(&mut self) -> RangeMut<'_, K, V> {
let mut x = RangeMut::new();
x.push_tree(self, true);
x
}
fn iter(&self) -> Range<'_, K, V> {
let mut x = Range::new();
x.push_tree(self, true);
x
}
fn range_mut<T, R>(&mut self, range: &R) -> RangeMut<'_, K, V>
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
let mut x = RangeMut::new();
x.push_range(self, range, true);
x
}
fn range<T, R>(&self, range: &R) -> Range<'_, K, V>
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
let mut x = Range::new();
x.push_range(self, range, true);
x
}
} impl<K, V> Default for Leaf<K, V> {
fn default() -> Self {
Self::new(DEFAULT_BRANCH, DEFAULT_ALLOC_UNIT)
}
}
#[derive(Debug, Clone)]
struct Leaf<K, V>(PairVec<K, V>);
impl<K, V> Leaf<K, V> {
fn new(b: u16, au: u8) -> Self {
Self(PairVec::new(b * 2 - 1, au))
}
fn full(&self) -> bool {
self.0.full()
}
fn b(&self) -> usize {
self.0.cap() / 2 + 1
}
fn bau(&self) -> (u16, u8) {
(self.b() as u16, self.0.au())
}
fn into_iter(mut self) -> IntoIterPairVec<K, V> {
let v = mem::take(&mut self.0);
v.into_iter()
}
fn look_to<Q>(&self, n: usize, key: &Q) -> Result<usize, usize>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.0.search_to(n, key)
}
#[inline]
fn look<Q>(&self, key: &Q) -> Result<usize, usize>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.0.search(key)
}
fn skip<Q>(&self, key: &Q) -> usize
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match self.0.search(key) {
Ok(i) | Err(i) => i,
}
}
fn skip_over<Q>(&self, key: &Q) -> usize
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match self.0.search(key) {
Ok(i) => i + 1,
Err(i) => i,
}
}
fn get_lower<Q>(&self, bound: Bound<&Q>) -> usize
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match bound {
Bound::Unbounded => 0,
Bound::Included(k) => self.skip(k),
Bound::Excluded(k) => self.skip_over(k),
}
}
fn get_upper<Q>(&self, bound: Bound<&Q>) -> usize
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match bound {
Bound::Unbounded => self.0.len(),
Bound::Included(k) => self.skip_over(k),
Bound::Excluded(k) => self.skip(k),
}
}
fn split(&mut self, r: usize) -> ((K, V), PairVec<K, V>) {
let b = self.b();
let right = self.0.split_off(b + 1, r);
let med = self.0.pop().unwrap();
(med, right)
}
fn insert(&mut self, key: K, x: &mut InsertCtx<K, V>)
where
K: Ord,
{
let mut i = match self.look(&key) {
Ok(i) => {
let value = x.value.take().unwrap();
let (k, v) = self.0.ixbm(i);
*k = key;
x.value = Some(mem::replace(v, value));
return;
}
Err(i) => i,
};
let value = x.value.take().unwrap();
if self.full() {
let b = self.b();
let r = usize::from(i > b);
let (med, mut right) = self.split(r);
if r == 1 {
i -= b + 1;
right.insert(i, (key, value));
} else {
self.0.insert(i, (key, value));
}
let right = Tree::L(Self(right));
x.split = Some((med, right));
} else {
self.0.insert(i, (key, value));
}
}
fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Some(self.0.remove(self.look(key).ok()?))
}
#[inline]
fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Some(self.0.ix(self.look(key).ok()?))
}
#[inline]
fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Some(self.0.ixv(self.look(key).ok()?))
}
#[inline]
fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
Some(self.0.ixmv(self.look(key).ok()?))
}
fn pop_first(&mut self) -> Option<(K, V)> {
if self.0.is_empty() {
return None;
}
Some(self.0.remove(0))
}
fn get_xy<T, R>(&self, range: &R) -> (usize, usize)
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
let y = match range.end_bound() {
Bound::Unbounded => self.0.len(),
Bound::Included(k) => self.skip_over(k),
Bound::Excluded(k) => self.skip(k),
};
let x = match range.start_bound() {
Bound::Unbounded => 0,
Bound::Included(k) => match self.look_to(y, k) {
Ok(i) => i,
Err(i) => i,
},
Bound::Excluded(k) => match self.look_to(y, k) {
Ok(i) => i + 1,
Err(i) => i,
},
};
(x, y)
}
fn iter_mut(&mut self) -> IterMutPairVec<'_, K, V> {
self.0.iter_mut()
}
fn iter(&self) -> IterPairVec<'_, K, V> {
self.0.iter()
}
} type NonLeaf<K, V> = Box<NonLeafInner<K, V>>;
#[derive(Debug, Clone)]
struct NonLeafInner<K, V> {
v: Leaf<K, V>,
c: TreeVec<K, V>,
}
impl<K, V> NonLeafInner<K, V> {
fn new(b: u16, au: u8) -> Box<Self> {
Box::new(Self {
v: Leaf::new(b, au),
c: TreeVec::new(b * 2, au),
})
}
fn split(&mut self, r: usize) -> ((K, V), Box<Self>) {
let b = self.v.b();
let (med, right) = self.v.split(r);
let right = Box::new(Self {
v: Leaf(right),
c: self.c.split_off(b + 1),
});
(med, right)
}
#[allow(clippy::type_complexity)]
fn into_iter(mut self) -> (IntoIterPairVec<K, V>, ShortVecIter<Tree<K, V>>) {
let v = mem::take(&mut self.v);
let c = mem::take(&mut self.c);
(v.into_iter(), c.into_iter())
}
fn remove_at(&mut self, i: usize) -> ((K, V), usize) {
if let Some(kv) = self.c.ixm(i).pop_last() {
let (kp, vp) = self.v.0.ixbm(i);
let k = mem::replace(kp, kv.0);
let v = mem::replace(vp, kv.1);
((k, v), i + 1)
} else {
self.c.remove(i);
(self.v.0.remove(i), i)
}
}
fn insert(&mut self, key: K, x: &mut InsertCtx<K, V>)
where
K: Ord,
{
match self.v.look(&key) {
Ok(i) => {
let value = x.value.take().unwrap();
let (kp, vp) = self.v.0.ixbm(i);
*kp = key;
x.value = Some(mem::replace(vp, value));
}
Err(mut i) => {
self.c.ixm(i).insert(key, x);
if let Some((med, right)) = x.split.take() {
if self.v.full() {
let b = self.v.b();
let r = usize::from(i > b);
let (pmed, mut pright) = self.split(r);
if r == 1 {
i -= b + 1;
pright.v.0.insert(i, med);
pright.c.insert(i + 1, right);
} else {
self.v.0.insert(i, med);
self.c.insert(i + 1, right);
}
x.split = Some((pmed, Tree::NL(pright)));
} else {
self.v.0.insert(i, med);
self.c.insert(i + 1, right);
}
}
}
}
}
fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
match self.v.look(key) {
Ok(i) => Some(self.remove_at(i).0),
Err(i) => self.c.ixm(i).remove(key),
}
}
fn pop_first(&mut self) -> Option<(K, V)> {
if let Some(x) = self.c.ixm(0).pop_first() {
Some(x)
} else if self.v.0.is_empty() {
None
} else {
self.c.remove(0);
Some(self.v.0.remove(0))
}
}
fn pop_last(&mut self) -> Option<(K, V)> {
let i = self.c.len();
if let Some(x) = self.c.ixm(i - 1).pop_last() {
Some(x)
} else if self.v.0.is_empty() {
None
} else {
self.c.pop();
self.v.0.pop()
}
}
} pub struct OccupiedError<'a, K, V>
where
K: 'a,
V: 'a,
{
pub entry: OccupiedEntry<'a, K, V>,
pub value: V,
}
impl<K: Debug + Ord, V: Debug> Debug for OccupiedError<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OccupiedError")
.field("key", self.entry.key())
.field("old_value", self.entry.get())
.field("new_value", &self.value)
.finish()
}
}
impl<'a, K: Debug + Ord, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"failed to insert {:?}, key {:?} already exists with value {:?}",
self.value,
self.entry.key(),
self.entry.get(),
)
}
}
impl<'a, K: Debug + Ord, V: Debug> Error for OccupiedError<'a, K, V> {}
pub enum Entry<'a, K, V> {
Vacant(VacantEntry<'a, K, V>),
Occupied(OccupiedEntry<'a, K, V>),
}
impl<'a, K, V> Entry<'a, K, V>
where
K: Ord,
{
pub fn key(&self) -> &K {
match self {
Entry::Vacant(e) => &e.key,
Entry::Occupied(e) => e.key(),
}
}
pub fn or_default(self) -> &'a mut V
where
V: Default,
{
match self {
Entry::Vacant(e) => e.insert(Default::default()),
Entry::Occupied(e) => e.into_mut(),
}
}
pub fn or_insert(self, value: V) -> &'a mut V {
match self {
Entry::Vacant(e) => e.insert(value),
Entry::Occupied(e) => e.into_mut(),
}
}
pub fn or_insert_with<F>(self, default: F) -> &'a mut V
where
F: FnOnce() -> V,
{
match self {
Entry::Vacant(e) => e.insert(default()),
Entry::Occupied(e) => e.into_mut(),
}
}
pub fn or_insert_with_key<F>(self, default: F) -> &'a mut V
where
F: FnOnce(&K) -> V,
{
match self {
Entry::Vacant(e) => {
let value = default(e.key());
e.insert(value)
}
Entry::Occupied(e) => e.into_mut(),
}
}
pub fn and_modify<F>(mut self, f: F) -> Entry<'a, K, V>
where
F: FnOnce(&mut V),
{
match &mut self {
Entry::Vacant(_e) => {}
Entry::Occupied(e) => {
let v = e.get_mut();
f(v);
}
}
self
}
}
pub struct VacantEntry<'a, K, V> {
key: K,
cursor: CursorMut<'a, K, V>,
}
impl<'a, K: Debug + Ord, V> Debug for VacantEntry<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("VacantEntry").field(self.key()).finish()
}
}
impl<'a, K, V> VacantEntry<'a, K, V>
where
K: Ord,
{
pub fn key(&self) -> &K {
&self.key
}
pub fn into_key(self) -> K {
self.key
}
pub fn insert(mut self, value: V) -> &'a mut V {
unsafe { self.cursor.insert_after_unchecked(self.key, value) };
self.cursor.into_mut()
}
}
pub struct OccupiedEntry<'a, K, V> {
cursor: CursorMut<'a, K, V>,
}
impl<K: Debug + Ord, V: Debug> Debug for OccupiedEntry<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OccupiedEntry")
.field("key", self.key())
.field("value", self.get())
.finish()
}
}
impl<'a, K, V> OccupiedEntry<'a, K, V>
where
K: Ord,
{
#[must_use]
pub fn key(&self) -> &K {
self.cursor.peek_next().unwrap().0
}
#[must_use]
pub fn remove_entry(mut self) -> (K, V) {
self.cursor.remove_next().unwrap()
}
#[must_use]
pub fn remove(self) -> V {
self.remove_entry().1
}
#[must_use]
pub fn get(&self) -> &V {
self.cursor.peek_next().unwrap().1
}
pub fn get_mut(&mut self) -> &mut V {
self.cursor.peek_next().unwrap().1
}
#[must_use]
pub fn into_mut(self) -> &'a mut V {
self.cursor.into_mut()
}
pub fn insert(&mut self, value: V) -> V {
mem::replace(self.get_mut(), value)
}
}
enum StealResultMut<'a, K, V> {
KV((&'a K, &'a mut V)), CT(&'a mut Tree<K, V>), Nothing,
}
#[derive(Debug, Default)]
pub struct IterMut<'a, K, V> {
len: usize,
inner: RangeMut<'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> {
if self.len == 0 {
None
} else {
self.len -= 1;
self.inner.next()
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
fn len(&self) -> usize {
self.len
}
}
impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len == 0 {
None
} else {
self.len -= 1;
self.inner.next_back()
}
}
}
impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
#[derive(Debug)]
struct StkMut<'a, K, V> {
v: IterMutPairVec<'a, K, V>,
c: std::slice::IterMut<'a, Tree<K, V>>,
}
#[derive(Debug, Default)]
pub struct RangeMut<'a, K, V> {
fwd_leaf: IterMutPairVec<'a, K, V>,
bck_leaf: IterMutPairVec<'a, K, V>,
fwd_stk: StkVec<StkMut<'a, K, V>>,
bck_stk: StkVec<StkMut<'a, K, V>>,
}
impl<'a, K, V> RangeMut<'a, K, V> {
fn new() -> Self {
Self {
fwd_leaf: IterMutPairVec::default(),
bck_leaf: IterMutPairVec::default(),
fwd_stk: StkVec::new(),
bck_stk: StkVec::new(),
}
}
fn push_tree(&mut self, tree: &'a mut Tree<K, V>, both: bool) {
match tree {
Tree::L(leaf) => {
self.fwd_leaf = leaf.iter_mut();
}
Tree::NL(nl) => {
let (v, mut c) = (nl.v.0.iter_mut(), nl.c.iter_mut());
let ct = c.next();
let ct_back = if both { c.next_back() } else { None };
let both = both && ct_back.is_none();
self.fwd_stk.push(StkMut { v, c });
if let Some(ct) = ct {
self.push_tree(ct, both);
}
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn push_range<T, R>(&mut self, tree: &'a mut Tree<K, V>, range: &R, both: bool)
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
match tree {
Tree::L(leaf) => {
let (x, y) = leaf.get_xy(range);
self.fwd_leaf = leaf.0.range_mut(x, y);
}
Tree::NL(nl) => {
let (x, y) = nl.v.get_xy(range);
let (v, mut c) = (nl.v.0.range_mut(x, y), nl.c[x..=y].iter_mut());
let ct = c.next();
let ct_back = if both { c.next_back() } else { None };
let both = both && ct_back.is_none();
self.fwd_stk.push(StkMut { v, c });
if let Some(ct) = ct {
self.push_range(ct, range, both);
}
if let Some(ct_back) = ct_back {
self.push_range_back(ct_back, range);
}
}
}
}
fn push_range_back<T, R>(&mut self, tree: &'a mut Tree<K, V>, range: &R)
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
match tree {
Tree::L(leaf) => {
let (x, y) = leaf.get_xy(range);
self.bck_leaf = leaf.0.range_mut(x, y);
}
Tree::NL(nl) => {
let (x, y) = nl.v.get_xy(range);
let (v, mut c) = (nl.v.0.range_mut(x, y), nl.c[x..=y].iter_mut());
let ct_back = c.next_back();
self.bck_stk.push(StkMut { v, c });
if let Some(ct_back) = ct_back {
self.push_range_back(ct_back, range);
}
}
}
}
fn push_tree_back(&mut self, tree: &'a mut Tree<K, V>) {
match tree {
Tree::L(leaf) => self.bck_leaf = leaf.iter_mut(),
Tree::NL(nl) => {
let (v, mut c) = (nl.v.0.iter_mut(), nl.c.iter_mut());
let ct_back = c.next_back();
self.bck_stk.push(StkMut { v, c });
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn steal_bck(&mut self) -> StealResultMut<'a, K, V> {
for s in &mut self.bck_stk {
if s.v.len() > s.c.len() {
return StealResultMut::KV(s.v.next().unwrap());
} else if let Some(ct) = s.c.next() {
return StealResultMut::CT(ct);
}
}
StealResultMut::Nothing
}
fn steal_fwd(&mut self) -> StealResultMut<'a, K, V> {
for s in &mut self.fwd_stk {
if s.v.len() > s.c.len() {
return StealResultMut::KV(s.v.next_back().unwrap());
} else if let Some(ct) = s.c.next_back() {
return StealResultMut::CT(ct);
}
}
StealResultMut::Nothing
}
#[cold]
fn next_inner(&mut self) -> Option<(&'a K, &'a mut V)> {
loop {
if let Some(s) = self.fwd_stk.last_mut() {
if let Some(kv) = s.v.next() {
if let Some(ct) = s.c.next() {
self.push_tree(ct, false);
}
return Some(kv);
}
self.fwd_stk.pop();
} else {
match self.steal_bck() {
StealResultMut::KV(kv) => return Some(kv),
StealResultMut::CT(ct) => {
self.push_tree(ct, false);
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
}
StealResultMut::Nothing => {
if let Some(x) = self.bck_leaf.next() {
return Some(x);
}
return None;
}
}
}
}
}
#[cold]
fn next_back_inner(&mut self) -> Option<(&'a K, &'a mut V)> {
loop {
if let Some(s) = self.bck_stk.last_mut() {
if let Some(kv) = s.v.next_back() {
if let Some(ct) = s.c.next_back() {
self.push_tree_back(ct);
}
return Some(kv);
}
self.bck_stk.pop();
} else {
match self.steal_fwd() {
StealResultMut::KV(kv) => return Some(kv),
StealResultMut::CT(ct) => {
self.push_tree_back(ct);
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
}
StealResultMut::Nothing => {
if let Some(x) = self.fwd_leaf.next_back() {
return Some(x);
}
return None;
}
}
}
}
}
}
impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
fn next(&mut self) -> Option<Self::Item> {
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
self.next_inner()
}
}
impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
self.next_back_inner()
}
}
impl<'a, K, V> FusedIterator for RangeMut<'a, K, V> {}
enum StealResultCon<K, V> {
KV((K, V)), CT(Tree<K, V>), Nothing,
}
pub struct IntoIter<K, V> {
len: usize,
inner: IntoIterInner<K, V>,
}
impl<K, V> IntoIter<K, V> {
fn new(bt: BTreeMap<K, V>) -> Self {
let mut s = Self {
len: bt.len(),
inner: IntoIterInner::new(),
};
s.inner.push_tree(bt.tree, true);
s
}
}
impl<K, V> Iterator for IntoIter<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
let result = self.inner.next()?;
self.len -= 1;
Some(result)
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
let result = self.inner.next_back()?;
self.len -= 1;
Some(result)
}
}
impl<K, V> ExactSizeIterator for IntoIter<K, V> {
fn len(&self) -> usize {
self.len
}
}
impl<K, V> FusedIterator for IntoIter<K, V> {}
struct StkCon<K, V> {
v: IntoIterPairVec<K, V>,
c: ShortVecIter<Tree<K, V>>,
}
struct IntoIterInner<K, V> {
fwd_leaf: IntoIterPairVec<K, V>,
bck_leaf: IntoIterPairVec<K, V>,
fwd_stk: StkVec<StkCon<K, V>>,
bck_stk: StkVec<StkCon<K, V>>,
}
impl<K, V> IntoIterInner<K, V> {
fn new() -> Self {
Self {
fwd_leaf: IntoIterPairVec::default(),
bck_leaf: IntoIterPairVec::default(),
fwd_stk: StkVec::new(),
bck_stk: StkVec::new(),
}
}
fn push_tree(&mut self, tree: Tree<K, V>, both: bool) {
match tree {
Tree::L(leaf) => self.fwd_leaf = leaf.into_iter(),
Tree::NL(nl) => {
let (v, mut c) = nl.into_iter();
let ct = c.next();
let ct_back = if both { c.next_back() } else { None };
let both = both && ct_back.is_none();
self.fwd_stk.push(StkCon { v, c });
if let Some(ct) = ct {
self.push_tree(ct, both);
}
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn push_tree_back(&mut self, tree: Tree<K, V>) {
match tree {
Tree::L(leaf) => self.bck_leaf = leaf.into_iter(),
Tree::NL(nl) => {
let (v, mut c) = nl.into_iter();
let ct_back = c.next_back();
self.bck_stk.push(StkCon { v, c });
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn steal_bck(&mut self) -> StealResultCon<K, V> {
for s in &mut self.bck_stk {
if s.v.len() > s.c.len() {
return StealResultCon::KV(s.v.next().unwrap());
} else if let Some(ct) = s.c.next() {
return StealResultCon::CT(ct);
}
}
StealResultCon::Nothing
}
fn steal_fwd(&mut self) -> StealResultCon<K, V> {
for s in &mut self.fwd_stk {
if s.v.len() > s.c.len() {
return StealResultCon::KV(s.v.next_back().unwrap());
} else if let Some(ct) = s.c.next_back() {
return StealResultCon::CT(ct);
}
}
StealResultCon::Nothing
}
#[cold]
fn next_inner(&mut self) -> Option<(K, V)> {
loop {
if let Some(s) = self.fwd_stk.last_mut() {
if let Some(kv) = s.v.next() {
if let Some(ct) = s.c.next() {
self.push_tree(ct, false);
}
return Some(kv);
}
self.fwd_stk.pop();
} else {
match self.steal_bck() {
StealResultCon::KV(kv) => return Some(kv),
StealResultCon::CT(ct) => {
self.push_tree(ct, false);
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
}
StealResultCon::Nothing => {
if let Some(x) = self.bck_leaf.next() {
return Some(x);
}
return None;
}
}
}
}
}
#[cold]
fn next_back_inner(&mut self) -> Option<(K, V)> {
loop {
if let Some(s) = self.bck_stk.last_mut() {
if let Some(kv) = s.v.next_back() {
if let Some(ct) = s.c.next_back() {
self.push_tree_back(ct);
}
return Some(kv);
}
self.bck_stk.pop();
} else {
match self.steal_fwd() {
StealResultCon::KV(kv) => return Some(kv),
StealResultCon::CT(ct) => {
self.push_tree_back(ct);
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
}
StealResultCon::Nothing => {
if let Some(x) = self.fwd_leaf.next_back() {
return Some(x);
}
return None;
}
}
}
}
}
}
impl<K, V> Iterator for IntoIterInner<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
self.next_inner()
}
}
impl<K, V> DoubleEndedIterator for IntoIterInner<K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
self.next_back_inner()
}
}
enum StealResult<'a, K, V> {
KV((&'a K, &'a V)), CT(&'a Tree<K, V>), Nothing,
}
#[derive(Clone, Debug, Default)]
pub struct Iter<'a, K, V> {
len: usize,
inner: Range<'a, K, V>,
}
impl<'a, K, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
if self.len == 0 {
None
} else {
self.len -= 1;
self.inner.next()
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.len, Some(self.len))
}
}
impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
fn len(&self) -> usize {
self.len
}
}
impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if self.len == 0 {
None
} else {
self.len -= 1;
self.inner.next_back()
}
}
}
impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
#[derive(Clone, Debug)]
struct Stk<'a, K, V> {
v: IterPairVec<'a, K, V>,
c: std::slice::Iter<'a, Tree<K, V>>,
}
#[derive(Clone, Debug, Default)]
pub struct Range<'a, K, V> {
fwd_leaf: IterPairVec<'a, K, V>,
bck_leaf: IterPairVec<'a, K, V>,
fwd_stk: StkVec<Stk<'a, K, V>>,
bck_stk: StkVec<Stk<'a, K, V>>,
}
impl<'a, K, V> Range<'a, K, V> {
fn new() -> Self {
Self {
fwd_leaf: IterPairVec::default(),
bck_leaf: IterPairVec::default(),
fwd_stk: StkVec::new(),
bck_stk: StkVec::new(),
}
}
fn push_tree(&mut self, tree: &'a Tree<K, V>, both: bool) {
match tree {
Tree::L(leaf) => {
self.fwd_leaf = leaf.0.iter();
}
Tree::NL(nl) => {
let (v, mut c) = (nl.v.0.iter(), nl.c.iter());
let ct = c.next();
let ct_back = if both { c.next_back() } else { None };
let both = both && ct_back.is_none();
self.fwd_stk.push(Stk { v, c });
if let Some(ct) = ct {
self.push_tree(ct, both);
}
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn push_range<T, R>(&mut self, tree: &'a Tree<K, V>, range: &R, both: bool)
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
match tree {
Tree::L(leaf) => {
let (x, y) = leaf.get_xy(range);
self.fwd_leaf = leaf.0.range(x, y);
}
Tree::NL(nl) => {
let (x, y) = nl.v.get_xy(range);
let (v, mut c) = (nl.v.0.range(x, y), nl.c[x..=y].iter());
let ct = c.next();
let ct_back = if both { c.next_back() } else { None };
let both = both && ct_back.is_none();
self.fwd_stk.push(Stk { v, c });
if let Some(ct) = ct {
self.push_range(ct, range, both);
}
if let Some(ct_back) = ct_back {
self.push_range_back(ct_back, range);
}
}
}
}
fn push_range_back<T, R>(&mut self, tree: &'a Tree<K, V>, range: &R)
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
{
match tree {
Tree::L(leaf) => {
let (x, y) = leaf.get_xy(range);
self.bck_leaf = leaf.0.range(x, y);
}
Tree::NL(nl) => {
let (x, y) = nl.v.get_xy(range);
let (v, mut c) = (nl.v.0.range(x, y), nl.c[x..=y].iter());
let ct_back = c.next_back();
self.bck_stk.push(Stk { v, c });
if let Some(ct_back) = ct_back {
self.push_range_back(ct_back, range);
}
}
}
}
fn push_tree_back(&mut self, tree: &'a Tree<K, V>) {
match tree {
Tree::L(leaf) => {
self.bck_leaf = leaf.iter();
}
Tree::NL(nl) => {
let (v, mut c) = (nl.v.0.iter(), nl.c.iter());
let ct_back = c.next_back();
self.bck_stk.push(Stk { v, c });
if let Some(ct_back) = ct_back {
self.push_tree_back(ct_back);
}
}
}
}
fn steal_bck(&mut self) -> StealResult<'a, K, V> {
for s in &mut self.bck_stk {
if s.v.len() > s.c.len() {
return StealResult::KV(s.v.next().unwrap());
} else if let Some(ct) = s.c.next() {
return StealResult::CT(ct);
}
}
StealResult::Nothing
}
fn steal_fwd(&mut self) -> StealResult<'a, K, V> {
for s in &mut self.fwd_stk {
if s.v.len() > s.c.len() {
return StealResult::KV(s.v.next_back().unwrap());
} else if let Some(ct) = s.c.next_back() {
return StealResult::CT(ct);
}
}
StealResult::Nothing
}
#[cold]
fn next_inner(&mut self) -> Option<(&'a K, &'a V)> {
loop {
if let Some(s) = self.fwd_stk.last_mut() {
if let Some(kv) = s.v.next() {
if let Some(ct) = s.c.next() {
self.push_tree(ct, false);
}
return Some(kv);
}
self.fwd_stk.pop();
} else {
match self.steal_bck() {
StealResult::KV(kv) => return Some(kv),
StealResult::CT(ct) => {
self.push_tree(ct, false);
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
}
StealResult::Nothing => {
if let Some(x) = self.bck_leaf.next() {
return Some(x);
}
return None;
}
}
}
}
}
#[cold]
fn next_back_inner(&mut self) -> Option<(&'a K, &'a V)> {
loop {
if let Some(s) = self.bck_stk.last_mut() {
if let Some(kv) = s.v.next_back() {
if let Some(ct) = s.c.next_back() {
self.push_tree_back(ct);
}
return Some(kv);
}
self.bck_stk.pop();
} else {
match self.steal_fwd() {
StealResult::KV(kv) => return Some(kv),
StealResult::CT(ct) => {
self.push_tree_back(ct);
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
}
StealResult::Nothing => {
if let Some(x) = self.fwd_leaf.next_back() {
return Some(x);
}
return None;
}
}
}
}
}
}
impl<'a, K, V> Iterator for Range<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
if let Some(x) = self.fwd_leaf.next() {
return Some(x);
}
self.next_inner()
}
}
impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
if let Some(x) = self.bck_leaf.next_back() {
return Some(x);
}
self.next_back_inner()
}
}
impl<'a, K, V> FusedIterator for Range<'a, K, V> {}
pub struct IntoKeys<K, V>(IntoIter<K, V>);
impl<K, V> Iterator for IntoKeys<K, V> {
type Item = K;
fn next(&mut self) -> Option<Self::Item> {
Some(self.0.next()?.0)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
Some(self.0.next_back()?.0)
}
}
impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<K, V> FusedIterator for IntoKeys<K, V> {}
pub struct IntoValues<K, V>(IntoIter<K, V>);
impl<K, V> Iterator for IntoValues<K, V> {
type Item = V;
fn next(&mut self) -> Option<Self::Item> {
Some(self.0.next()?.1)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
fn next_back(&mut self) -> Option<Self::Item> {
Some(self.0.next_back()?.1)
}
}
impl<K, V> ExactSizeIterator for IntoValues<K, V> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<K, V> FusedIterator for IntoValues<K, V> {}
#[derive(Debug)]
pub struct ValuesMut<'a, K, V>(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)
}
}
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> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
#[derive(Clone, Debug, Default)]
pub struct Values<'a, K, V>(Iter<'a, K, V>);
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)
}
}
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> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
#[derive(Clone, Debug, Default)]
pub struct Keys<'a, K, V>(Iter<'a, K, V>);
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)
}
}
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> {
fn len(&self) -> usize {
self.0.len()
}
}
impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
pub struct ExtractIf<'a, K, V, F>
where
F: FnMut(&K, &mut V) -> bool,
{
source: CursorMut<'a, K, V>,
pred: F,
}
impl<K, V, F> fmt::Debug for ExtractIf<'_, K, V, F>
where
K: fmt::Debug,
V: fmt::Debug,
F: FnMut(&K, &mut V) -> bool,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("ExtractIf")
.field(&self.source.peek_next())
.finish()
}
}
impl<'a, K, V, F> Iterator for ExtractIf<'a, K, V, F>
where
F: FnMut(&K, &mut V) -> bool,
{
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
loop {
let (k, v) = self.source.peek_next()?;
if (self.pred)(k, v) {
return self.source.remove_next();
}
self.source.next();
}
}
}
impl<'a, K, V, F> FusedIterator for ExtractIf<'a, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct UnorderedKeyError {}
impl fmt::Display for UnorderedKeyError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "key is not properly ordered relative to neighbors")
}
}
impl std::error::Error for UnorderedKeyError {}
pub struct CursorMut<'a, K, V>(CursorMutKey<'a, K, V>);
impl<'a, K, V> CursorMut<'a, K, V> {
fn lower_bound<Q>(map: &'a mut BTreeMap<K, V>, bound: Bound<&Q>) -> Self
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
unsafe {
let map: *mut BTreeMap<K, V> = map;
let mut s = CursorMutKey::make(map);
s.push_lower(&mut (*map).tree, bound);
Self(s)
}
}
fn upper_bound<Q>(map: &'a mut BTreeMap<K, V>, bound: Bound<&Q>) -> Self
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
unsafe {
let map: *mut BTreeMap<K, V> = map;
let mut s = CursorMutKey::make(map);
s.push_upper(&mut (*map).tree, bound);
Self(s)
}
}
pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>
where
K: Ord,
{
self.0.insert_before(key, value)
}
pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>
where
K: Ord,
{
self.0.insert_after(key, value)
}
pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
self.0.insert_before_unchecked(key, value);
}
pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
self.0.insert_after_unchecked(key, value);
}
pub fn remove_prev(&mut self) -> Option<(K, V)> {
self.0.remove_prev()
}
pub fn remove_next(&mut self) -> Option<(K, V)> {
self.0.remove_next()
}
#[allow(clippy::should_implement_trait)]
pub fn next(&mut self) -> Option<(&K, &mut V)> {
let (k, v) = self.0.next()?;
Some((&*k, v))
}
pub fn prev(&mut self) -> Option<(&K, &mut V)> {
let (k, v) = self.0.prev()?;
Some((&*k, v))
}
#[must_use]
pub fn peek_next(&self) -> Option<(&K, &mut V)> {
let (k, v) = self.0.peek_next()?;
Some((&*k, v))
}
#[must_use]
pub fn peek_prev(&self) -> Option<(&K, &mut V)> {
let (k, v) = self.0.peek_prev()?;
Some((&*k, v))
}
#[must_use]
pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V> {
self.0
}
#[must_use]
pub fn as_cursor(&self) -> Cursor<'_, K, V> {
self.0.as_cursor()
}
fn into_mut(self) -> &'a mut V {
self.0.into_mut()
}
}
pub struct CursorMutKey<'a, K, V> {
map: *mut BTreeMap<K, V>,
leaf: Option<*mut Leaf<K, V>>,
index: usize,
stack: StkVec<(*mut NonLeaf<K, V>, usize)>,
_pd: PhantomData<&'a mut BTreeMap<K, V>>,
}
unsafe impl<'a, K, V> Send for CursorMutKey<'a, K, V> {}
unsafe impl<'a, K, V> Sync for CursorMutKey<'a, K, V> {}
impl<'a, K, V> CursorMutKey<'a, K, V> {
fn make(map: *mut BTreeMap<K, V>) -> Self {
Self {
map,
leaf: None,
index: 0,
stack: StkVec::new(),
_pd: PhantomData,
}
}
fn push_lower<Q>(&mut self, mut tree: &mut Tree<K, V>, bound: Bound<&Q>)
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
loop {
match tree {
Tree::L(leaf) => {
self.index = leaf.get_lower(bound);
self.leaf = Some(leaf);
break;
}
Tree::NL(nl) => {
let ix = nl.v.get_lower(bound);
self.stack.push((nl, ix));
tree = nl.c.ixm(ix);
}
}
}
}
fn push_upper<Q>(&mut self, mut tree: &mut Tree<K, V>, bound: Bound<&Q>)
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
loop {
match tree {
Tree::L(leaf) => {
self.index = leaf.get_upper(bound);
self.leaf = Some(leaf);
break;
}
Tree::NL(nl) => {
let ix = nl.v.get_upper(bound);
self.stack.push((nl, ix));
tree = nl.c.ixm(ix);
}
}
}
}
fn push(&mut self, mut tsp: usize, mut tree: &mut Tree<K, V>) {
loop {
match tree {
Tree::L(leaf) => {
self.index = 0;
self.leaf = Some(leaf);
break;
}
Tree::NL(nl) => {
self.stack[tsp] = (nl, 0);
tree = nl.c.ixm(0);
tsp += 1;
}
}
}
}
fn push_back(&mut self, mut tsp: usize, mut tree: &mut Tree<K, V>) {
loop {
match tree {
Tree::L(leaf) => {
self.index = leaf.0.len();
self.leaf = Some(leaf);
break;
}
Tree::NL(nl) => {
let ix = nl.v.0.len();
self.stack[tsp] = (nl, ix);
tree = nl.c.ixm(ix);
tsp += 1;
}
}
}
}
pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>
where
K: Ord,
{
if let Some((prev, _)) = self.peek_prev() {
if &key <= prev {
return Err(UnorderedKeyError {});
}
}
if let Some((next, _)) = self.peek_next() {
if &key >= next {
return Err(UnorderedKeyError {});
}
}
unsafe {
self.insert_before_unchecked(key, value);
}
Ok(())
}
pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>
where
K: Ord,
{
if let Some((prev, _)) = self.peek_prev() {
if &key <= prev {
return Err(UnorderedKeyError {});
}
}
if let Some((next, _)) = self.peek_next() {
if &key >= next {
return Err(UnorderedKeyError {});
}
}
unsafe {
self.insert_after_unchecked(key, value);
}
Ok(())
}
pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
self.insert_after_unchecked(key, value);
self.index += 1;
}
pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
unsafe {
(*self.map).len += 1;
let mut leaf = self.leaf.unwrap_unchecked();
if (*leaf).full() {
let b = (*leaf).b();
let r = usize::from(self.index > b);
let (med, right) = (*leaf).split(r);
let right = Tree::L(Leaf(right));
self.index -= r * (b + 1);
let t = self.save_split(med, right, r);
leaf = (*t).leaf();
self.leaf = Some(leaf);
}
(*leaf).0.insert(self.index, (key, value));
}
}
fn save_split(&mut self, med: (K, V), tree: Tree<K, V>, r: usize) -> *mut Tree<K, V> {
unsafe {
if let Some((mut nl, mut ix)) = self.stack.pop() {
if (*nl).v.full() {
let b = (*nl).v.b();
let r = usize::from(ix > b);
let (med, right) = (*nl).split(r);
ix -= r * (b + 1);
let t = self.save_split(med, Tree::NL(right), r);
nl = (*t).nonleaf();
}
(*nl).v.0.insert(ix, med);
(*nl).c.insert(ix + 1, tree);
ix += r;
self.stack.push((nl, ix));
(*nl).c.ixm(ix)
} else {
(*self.map).tree.new_root((med, tree));
let nl = (*self.map).tree.nonleaf();
self.stack.push((nl, r));
nl.c.ixm(r)
}
}
}
pub fn remove_prev(&mut self) -> Option<(K, V)> {
self.prev()?;
self.remove_next()
}
pub fn remove_next(&mut self) -> Option<(K, V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == (*leaf).0.len() {
let mut tsp = self.stack.len();
while tsp > 0 {
tsp -= 1;
let (nl, ix) = self.stack[tsp];
if ix < (*nl).v.0.len() {
let (kv, ix) = (*nl).remove_at(ix);
self.stack[tsp] = (nl, ix);
self.push(tsp + 1, (*nl).c.ixm(ix));
(*self.map).len -= 1;
return Some(kv);
}
}
None
} else {
(*self.map).len -= 1;
Some((*leaf).0.remove(self.index))
}
}
}
#[allow(clippy::should_implement_trait)]
pub fn next(&mut self) -> Option<(&mut K, &mut V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == (*leaf).0.len() {
let mut tsp = self.stack.len();
while tsp > 0 {
tsp -= 1;
let (nl, mut ix) = self.stack[tsp];
if ix < (*nl).v.0.len() {
let kv = (*nl).v.0.ixbm(ix);
ix += 1;
self.stack[tsp] = (nl, ix);
self.push(tsp + 1, (*nl).c.ixm(ix));
return Some(kv);
}
}
None
} else {
let kv = (*leaf).0.ixbm(self.index);
self.index += 1;
Some(kv)
}
}
}
pub fn prev(&mut self) -> Option<(&mut K, &mut V)> {
unsafe {
if self.index == 0 {
let mut tsp = self.stack.len();
while tsp > 0 {
tsp -= 1;
let (nl, mut ix) = self.stack[tsp];
if ix > 0 {
ix -= 1;
let kv = (*nl).v.0.ixbm(ix);
self.stack[tsp] = (nl, ix);
self.push_back(tsp + 1, (*nl).c.ixm(ix));
return Some(kv);
}
}
None
} else {
let leaf = self.leaf.unwrap_unchecked();
self.index -= 1;
Some((*leaf).0.ixbm(self.index))
}
}
}
#[must_use]
pub fn peek_next(&self) -> Option<(&mut K, &mut V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == (*leaf).0.len() {
for (nl, ix) in self.stack.iter().rev() {
if *ix < (**nl).v.0.len() {
return Some((**nl).v.0.ixbm(*ix));
}
}
None
} else {
Some((*leaf).0.ixbm(self.index))
}
}
}
#[must_use]
pub fn peek_prev(&self) -> Option<(&mut K, &mut V)> {
unsafe {
if self.index == 0 {
for (nl, ix) in self.stack.iter().rev() {
if *ix > 0 {
return Some((**nl).v.0.ixbm(*ix - 1));
}
}
None
} else {
let leaf = self.leaf.unwrap_unchecked();
Some((*leaf).0.ixbm(self.index - 1))
}
}
}
#[must_use]
pub fn as_cursor(&self) -> Cursor<'_, K, V> {
unsafe {
let mut c = Cursor::make();
c.index = self.index;
c.leaf = Some(&*self.leaf.unwrap());
for (nl, ix) in &self.stack {
c.stack.push((&(**nl), *ix));
}
c
}
}
fn into_mut(self) -> &'a mut V {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
(*leaf).0.ixmv(self.index)
}
}
}
#[derive(Debug, Clone)]
pub struct Cursor<'a, K, V> {
leaf: Option<*const Leaf<K, V>>,
index: usize,
stack: StkVec<(*const NonLeaf<K, V>, usize)>,
_pd: PhantomData<&'a BTreeMap<K, V>>,
}
unsafe impl<'a, K, V> Send for Cursor<'a, K, V> {}
unsafe impl<'a, K, V> Sync for Cursor<'a, K, V> {}
impl<'a, K, V> Cursor<'a, K, V> {
fn make() -> Self {
Self {
leaf: None,
index: 0,
stack: StkVec::new(),
_pd: PhantomData,
}
}
fn lower_bound<Q>(bt: &'a BTreeMap<K, V>, bound: Bound<&Q>) -> Self
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut s = Self::make();
s.push_lower(&bt.tree, bound);
s
}
fn upper_bound<Q>(bt: &'a BTreeMap<K, V>, bound: Bound<&Q>) -> Self
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
let mut s = Self::make();
s.push_upper(&bt.tree, bound);
s
}
fn push_lower<Q>(&mut self, mut tree: &'a Tree<K, V>, bound: Bound<&Q>)
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
loop {
match tree {
Tree::L(leaf) => {
self.leaf = Some(leaf);
self.index = leaf.get_lower(bound);
break;
}
Tree::NL(nl) => {
let ix = nl.v.get_lower(bound);
self.stack.push((nl, ix));
tree = nl.c.ix(ix);
}
}
}
}
fn push_upper<Q>(&mut self, mut tree: &'a Tree<K, V>, bound: Bound<&Q>)
where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
loop {
match tree {
Tree::L(leaf) => {
self.leaf = Some(leaf);
self.index = leaf.get_upper(bound);
break;
}
Tree::NL(nl) => {
let ix = nl.v.get_upper(bound);
self.stack.push((nl, ix));
tree = nl.c.ix(ix);
}
}
}
}
fn push(&mut self, mut tsp: usize, mut tree: &Tree<K, V>) {
loop {
match tree {
Tree::L(leaf) => {
self.leaf = Some(leaf);
self.index = 0;
break;
}
Tree::NL(nl) => {
self.stack[tsp] = (nl, 0);
tree = nl.c.ix(0);
tsp += 1;
}
}
}
}
fn push_back(&mut self, mut tsp: usize, mut tree: &Tree<K, V>) {
loop {
match tree {
Tree::L(leaf) => {
self.leaf = Some(leaf);
self.index = leaf.0.len();
break;
}
Tree::NL(nl) => {
let ix = nl.v.0.len();
self.stack[tsp] = (nl, ix);
tree = nl.c.ix(ix);
tsp += 1;
}
}
}
}
#[allow(clippy::should_implement_trait)]
pub fn next(&mut self) -> Option<(&K, &V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == (*leaf).0.len() {
let mut tsp = self.stack.len();
while tsp > 0 {
tsp -= 1;
let (nl, mut ix) = self.stack[tsp];
if ix < (*nl).v.0.len() {
let kv = (*nl).v.0.ix(ix);
ix += 1;
self.stack[tsp] = (nl, ix);
let ct = (*nl).c.ix(ix);
self.push(tsp + 1, ct);
return Some(kv);
}
}
None
} else {
let kv = (*leaf).0.ix(self.index);
self.index += 1;
Some(kv)
}
}
}
pub fn prev(&mut self) -> Option<(&K, &V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == 0 {
let mut tsp = self.stack.len();
while tsp > 0 {
tsp -= 1;
let (nl, mut ix) = self.stack[tsp];
if ix > 0 {
ix -= 1;
let kv = (*nl).v.0.ix(ix);
self.stack[tsp] = (nl, ix);
let ct = (*nl).c.ix(ix);
self.push_back(tsp + 1, ct);
return Some(kv);
}
}
None
} else {
self.index -= 1;
Some((*leaf).0.ix(self.index))
}
}
}
#[must_use]
pub fn peek_next(&self) -> Option<(&K, &V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == (*leaf).0.len() {
for (nl, ix) in self.stack.iter().rev() {
if *ix < (**nl).v.0.len() {
return Some((**nl).v.0.ix(*ix));
}
}
None
} else {
Some((*leaf).0.ix(self.index))
}
}
}
#[must_use]
pub fn peek_prev(&self) -> Option<(&K, &V)> {
unsafe {
let leaf = self.leaf.unwrap_unchecked();
if self.index == 0 {
for (nl, ix) in self.stack.iter().rev() {
if *ix > 0 {
return Some((**nl).v.0.ix(*ix - 1));
}
}
None
} else {
Some((*leaf).0.ix(self.index - 1))
}
}
}
}
#[cfg(all(test, not(miri), feature = "cap"))]
use {cap::Cap, std::alloc};
#[cfg(all(test, not(miri), feature = "cap"))]
#[global_allocator]
static ALLOCATOR: Cap<alloc::System> = Cap::new(alloc::System, usize::max_value());
#[cfg(test)]
fn print_memory() {
#[cfg(all(test, not(miri), feature = "cap"))]
println!("Memory allocated: {} bytes", ALLOCATOR.allocated());
}
#[cfg(all(test, not(miri), not(feature = "cap")))]
use mimalloc::MiMalloc;
#[cfg(all(test, not(miri), not(feature = "cap")))]
#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;
#[cfg(test)]
mod mytests;
#[cfg(test)]
mod stdtests;