Struct near_sdk::collections::TreeMap
source · pub struct TreeMap<K, V> { /* private fields */ }
Expand description
TreeMap based on AVL-tree
Runtime complexity (worst case):
get
/contains_key
: O(1) - UnorderedMap lookupinsert
/remove
: O(log(N))min
/max
: O(log(N))above
/below
: O(log(N))range
of K elements: O(Klog(N))
Implementations§
source§impl<K, V> TreeMap<K, V>
impl<K, V> TreeMap<K, V>
sourcepub fn new<S>(prefix: S) -> Selfwhere
S: IntoStorageKey,
pub fn new<S>(prefix: S) -> Selfwhere
S: IntoStorageKey,
Makes a new, empty TreeMap
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
sourcepub fn len(&self) -> u64
pub fn len(&self) -> u64
Returns the number of elements in the tree, also referred to as its size.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
tree.insert(&1, &10);
tree.insert(&2, &20);
assert_eq!(tree.len(), 2);
pub fn is_empty(&self) -> bool
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the tree, removing all elements.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
tree.insert(&1, &10);
tree.insert(&2, &20);
tree.clear();
assert_eq!(tree.len(), 0);
sourcepub fn contains_key(&self, key: &K) -> bool
pub fn contains_key(&self, key: &K) -> bool
Returns true if the map contains a given key.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.contains_key(&1), false);
tree.insert(&1, &10);
assert_eq!(tree.contains_key(&1), true);
sourcepub fn get(&self, key: &K) -> Option<V>
pub fn get(&self, key: &K) -> Option<V>
Returns the value corresponding to the key.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.get(&1), None);
tree.insert(&1, &10);
assert_eq!(tree.get(&1), Some(10));
sourcepub fn insert(&mut self, key: &K, val: &V) -> Option<V>
pub fn insert(&mut self, key: &K, val: &V) -> Option<V>
Inserts a key-value pair into the tree.
If the tree did not have this key present, None
is returned. Otherwise returns
a value. Note, the keys that have the same hash value are undistinguished by
the implementation.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.insert(&1, &10), None);
assert_eq!(tree.insert(&1, &20), Some(10));
assert_eq!(tree.contains_key(&1), true);
sourcepub fn remove(&mut self, key: &K) -> Option<V>
pub fn remove(&mut self, key: &K) -> Option<V>
Removes a key from the tree, returning the value at the key if the key was previously in the tree.
§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.remove(&1), None);
tree.insert(&1, &10);
assert_eq!(tree.remove(&1), Some(10));
assert_eq!(tree.contains_key(&1), false);
sourcepub fn higher(&self, key: &K) -> Option<K>
pub fn higher(&self, key: &K) -> Option<K>
Returns the smallest key that is strictly greater than key given as the parameter
sourcepub fn lower(&self, key: &K) -> Option<K>
pub fn lower(&self, key: &K) -> Option<K>
Returns the largest key that is strictly less than key given as the parameter
sourcepub fn ceil_key(&self, key: &K) -> Option<K>
pub fn ceil_key(&self, key: &K) -> Option<K>
Returns the smallest key that is greater or equal to key given as the parameter
§Examples
use near_sdk::collections::TreeMap;
let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let vec: Vec<u32> = vec![10, 20, 30, 40, 50];
for x in vec.iter() {
map.insert(x, &1);
}
assert_eq!(map.ceil_key(&5), Some(10));
assert_eq!(map.ceil_key(&10), Some(10));
assert_eq!(map.ceil_key(&11), Some(20));
assert_eq!(map.ceil_key(&20), Some(20));
assert_eq!(map.ceil_key(&49), Some(50));
assert_eq!(map.ceil_key(&50), Some(50));
assert_eq!(map.ceil_key(&51), None);
sourcepub fn floor_key(&self, key: &K) -> Option<K>
pub fn floor_key(&self, key: &K) -> Option<K>
Returns the largest key that is less or equal to key given as the parameter
§Examples
use near_sdk::collections::TreeMap;
let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let vec: Vec<u32> = vec![10, 20, 30, 40, 50];
for x in vec.iter() {
map.insert(x, &1);
}
assert_eq!(map.floor_key(&5), None);
assert_eq!(map.floor_key(&10), Some(10));
assert_eq!(map.floor_key(&11), Some(10));
assert_eq!(map.floor_key(&20), Some(20));
assert_eq!(map.floor_key(&49), Some(40));
assert_eq!(map.floor_key(&50), Some(50));
assert_eq!(map.floor_key(&51), Some(50));
sourcepub fn iter(&self) -> impl Iterator<Item = (K, V)> + '_
pub fn iter(&self) -> impl Iterator<Item = (K, V)> + '_
Iterate all entries in ascending order: min to max, both inclusive
sourcepub fn iter_from(&self, key: K) -> impl Iterator<Item = (K, V)> + '_
pub fn iter_from(&self, key: K) -> impl Iterator<Item = (K, V)> + '_
Iterate entries in ascending order: given key (exclusive) to max (inclusive)
§Examples
use near_sdk::collections::TreeMap;
let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50,45, 35, 25, 15, 5];
for x in &one {
map.insert(x, &42);
}
assert_eq!(
map.iter_from(29).collect::<Vec<(u32, u32)>>(),
vec![(30, 42), (35, 42), (40, 42), (45, 42), (50, 42)]
)
sourcepub fn iter_rev(&self) -> impl Iterator<Item = (K, V)> + '_
pub fn iter_rev(&self) -> impl Iterator<Item = (K, V)> + '_
Iterate all entries in descending order: max to min, both inclusive
sourcepub fn iter_rev_from(&self, key: K) -> impl Iterator<Item = (K, V)> + '_
pub fn iter_rev_from(&self, key: K) -> impl Iterator<Item = (K, V)> + '_
Iterate entries in descending order: given key (exclusive) to min (inclusive)
§Examples
use near_sdk::collections::TreeMap;
let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50,45, 35, 25, 15, 5];
for x in &one {
map.insert(x, &42);
}
assert_eq!(
map.iter_rev_from(45).collect::<Vec<(u32, u32)>>(),
vec![(40, 42), (35, 42), (30, 42), (25, 42), (20, 42), (15, 42), (10, 42), (5, 42)]
);
sourcepub fn range(
&self,
r: (Bound<K>, Bound<K>)
) -> impl Iterator<Item = (K, V)> + '_
pub fn range( &self, r: (Bound<K>, Bound<K>) ) -> impl Iterator<Item = (K, V)> + '_
Iterate entries in ascending order according to specified bounds.
§Panics
Panics if range start > end. Panics if range start == end and both bounds are Excluded.
§Examples
use near_sdk::collections::TreeMap;
use std::ops::Bound;
let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50];
let two: Vec<u32> = vec![45, 35, 25, 15];
for x in &one {
map.insert(x, &0);
}
for x in &two {
map.insert(x, &0);
}
assert_eq!(
map.range((Bound::Included(20), Bound::Excluded(30))).collect::<Vec<(u32, u32)>>(),
vec![(20, 0), (25, 0)]
);