Struct treap::map::TreapMap

pub struct TreapMap<K, V, Rng = XorShiftRng> {
    // some fields omitted
}

A map based on a randomized treap.

Methods

impl<K: Ord, V> TreapMap<K, V, XorShiftRng>

fn new() -> TreapMap<K, V, XorShiftRng>

Create an empty treap with the default random number generator. The XorShift random number generator is used by default since it is fast, but please note that it is not cryptographically secure.

let mut t = treap::TreapMap::new();
t.insert(5, "yellow");
if let Some(s) = t.get(&5) {
    println!("{}", s);
}

impl<K: Ord, V, Rng: Rng> TreapMap<K, V, Rng>

fn new_with_rng(rng: Rng) -> TreapMap<K, V, Rng>

Create an empty treap with a given random number generator.

 extern crate rand;

 let mut t = treap::TreapMap::new_with_rng(rand::thread_rng());
 t.insert(5, "yellow");

fn len(&self) -> usize

Return the number of elements in the treap.

let mut t = treap::TreapMap::new();
assert_eq!(t.len(), 0);
t.insert(5, 1);
assert_eq!(t.len(), 1);

fn is_empty(&self) -> bool

Return true if the treap contains no elements.

let mut t = treap::TreapMap::new();
assert!(t.is_empty());
t.insert(5, 1);
assert!(!t.is_empty());

fn clear(&mut self)

Removes all elements from the treap.

let mut t = treap::TreapMap::new();
t.insert(5, 1);
t.clear();
assert!(t.is_empty());

fn get(&self, key: &K) -> Option<&V>

Borrow the value corresponding to the given key if it exists in the treap.

let mut t = treap::TreapMap::new();
t.insert(5, "yellow");
t.insert(3, "blue");
t.insert(8, "green");
assert_eq!(t.get(&5), Some(&"yellow"));
assert_eq!(t.get(&10), None);

fn get_mut(&mut self, key: &K) -> Option<&mut V>

Return a mutable reference to the value corresponding to the given key if it exists in the treap.

let mut t = treap::TreapMap::new();
t.insert(5, "yellow");
match t.get_mut(&5) {
    Some(x) => *x = "blue",
    None => (),
}
assert_eq!(t.get(&5), Some(&"blue"));

fn contains_key(&self, key: &K) -> bool

Returns true if the key is present in the treap.

let mut t = treap::TreapMap::new();
t.insert(5, "yellow");
assert_eq!(t.contains_key(&5), true);
assert_eq!(t.contains_key(&8), false);

fn insert(&mut self, key: K, value: V) -> Option<V>

Insert a value with a given key. Returns the previous value if the key is already in the treap.

let mut t = treap::TreapMap::new();
assert_eq!(t.insert(5, "yellow"), None);
assert_eq!(t.insert(5, "blue"), Some("yellow"));

fn remove(&mut self, key: &K) -> Option<V>

Remove the given key from the treap and return the value associated with it if any.

let mut t = treap::TreapMap::new();
t.insert(5, "blue");
assert_eq!(t.remove(&5), Some("blue"));
assert_eq!(t.remove(&10), None);

fn iter_ordered(&self) -> OrderedIter<K, V>

Returns an iterator over keys and values in the treap that gives the keys in sorted order.

let mut t = treap::TreapMap::new();
t.extend((1..10).map(|x| (x, "a")));

let v: Vec<i32> = t.iter_ordered().map(|(&k, _)| k).collect();
assert_eq!(v, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);

Trait Implementations

impl<K: Ord, V, Rng: Rng> Extend<(K, V)> for TreapMap<K, V, Rng>

fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T)

impl<K: Ord, V> FromIterator<(K, V)> for TreapMap<K, V>

fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> TreapMap<K, V>

impl<K: Ord, V> Default for TreapMap<K, V>

fn default() -> TreapMap<K, V>

impl<K: Ord, V, Rng: Rng> IntoIterator for TreapMap<K, V, Rng>

Return an iterator that moves keys and values out of treap. The order is arbitrary.

let mut t = treap::TreapMap::new();
t.extend(vec![(1, "red"), (2, "blue"), (3, "green")].into_iter());

// Print keys and values in arbitrary order.
for (k, v) in t {
    println!("{}: {}", k, v);
}

type Item = (K, V)

type IntoIter = IntoIter<K, V>

fn into_iter(self) -> IntoIter<K, V>

impl<'a, K: Ord, V, Rng: Rng> IntoIterator for &'a TreapMap<K, V, Rng>

Return an iterator over keys and values in the treap. The order is arbitrary.

let mut t = treap::TreapMap::new();
t.extend(vec![(1, 200), (2, 120), (3, 330)].into_iter());

let sum = (&t).into_iter().fold(0, |s, (&k, &v)| s + k + v);
assert_eq!(sum, 656);

type Item = (&'a K, &'a V)

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

fn into_iter(self) -> Iter<'a, K, V>

impl<'a, K: Ord, V, Rng: Rng> IntoIterator for &'a mut TreapMap<K, V, Rng>

Return an mutable iterator over keys and values in the treap. The order is arbitrary.

let mut t = treap::TreapMap::new();
t.extend(vec![(1, 200), (2, 120), (3, 330)].into_iter());

for (k, v) in &mut t {
    *v += *k;
}
assert_eq!(t.get(&2), Some(&122));

type Item = (&'a K, &'a mut V)

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

fn into_iter(self) -> IterMut<'a, K, V>

impl<'a, K: Ord, V, Rng: Rng> Index<&'a K> for TreapMap<K, V, Rng>

type Output = V

fn index(&self, key: &K) -> &V

impl<'a, K: Ord, V, Rng: Rng> IndexMut<&'a K> for TreapMap<K, V, Rng>

fn index_mut(&mut self, key: &K) -> &mut V

Derived Implementations

impl<K: Clone, V: Clone, Rng: Clone> Clone for TreapMap<K, V, Rng>

fn clone(&self) -> TreapMap<K, V, Rng>

fn clone_from(&mut self, source: &Self)

impl<K: Debug, V: Debug, Rng: Debug> Debug for TreapMap<K, V, Rng>

fn fmt(&self, __arg_0: &mut Formatter) -> Result