pub struct TreeMap<K, V> { /* private fields */ }
Expand description

TreeMap based on AVL-tree

Runtime complexity (worst case):

  • get/contains_key: O(1) - UnorderedMap lookup
  • insert/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>

source

pub fn new<S>(prefix: S) -> Self
where S: IntoStorageKey,

Makes a new, empty TreeMap

§Examples
use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
source

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);
source

pub fn is_empty(&self) -> bool

source

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);
source

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);
source

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));
source

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);
source

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);
source

pub fn min(&self) -> Option<K>

Returns the smallest stored key from the tree

source

pub fn max(&self) -> Option<K>

Returns the largest stored key from the tree

source

pub fn higher(&self, key: &K) -> Option<K>

Returns the smallest key that is strictly greater than key given as the parameter

source

pub fn lower(&self, key: &K) -> Option<K>

Returns the largest key that is strictly less than key given as the parameter

source

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);
source

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));
source

pub fn iter(&self) -> impl Iterator<Item = (K, V)> + '_

Iterate all entries in ascending order: min to max, both inclusive

source

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)]
)
source

pub fn iter_rev(&self) -> impl Iterator<Item = (K, V)> + '_

Iterate all entries in descending order: max to min, both inclusive

source

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)]
);
source

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)]
);
source

pub fn to_vec(&self) -> Vec<(K, V)>

Helper function which creates a [Vec<(K, V)>] of all items in the TreeMap. This function collects elements from TreeMap::iter.

Trait Implementations§

source§

impl<K, V> BorshDeserialize for TreeMap<K, V>

source§

fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self, Error>

source§

fn deserialize(buf: &mut &[u8]) -> Result<Self, Error>

Deserializes this instance from a given slice of bytes. Updates the buffer to point at the remaining bytes.
source§

fn try_from_slice(v: &[u8]) -> Result<Self, Error>

Deserialize this instance from a slice of bytes.
source§

fn try_from_reader<R>(reader: &mut R) -> Result<Self, Error>
where R: Read,

source§

impl<K, V> BorshSerialize for TreeMap<K, V>

source§

fn serialize<W: Write>(&self, writer: &mut W) -> Result<(), Error>

source§

impl<K, V> Debug for TreeMap<K, V>

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl<'a, K, V> IntoIterator for &'a TreeMap<K, V>

§

type Item = (K, V)

The type of the elements being iterated over.
§

type IntoIter = Cursor<'a, K, V>

Which kind of iterator are we turning this into?
source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<K, V> Freeze for TreeMap<K, V>

§

impl<K, V> RefUnwindSafe for TreeMap<K, V>

§

impl<K, V> Send for TreeMap<K, V>
where K: Send, V: Send,

§

impl<K, V> Sync for TreeMap<K, V>
where K: Sync, V: Sync,

§

impl<K, V> Unpin for TreeMap<K, V>
where K: Unpin, V: Unpin,

§

impl<K, V> UnwindSafe for TreeMap<K, V>
where K: UnwindSafe, V: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.