Struct teardown_tree___treap::map::TreapMap

pub struct TreapMap<K, V, Rng = XorShiftRng> { /* 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]);

impl<K: Ord + Clone, Rng: Rng> TreapMap<K, (), Rng>

fn delete_range(&mut self, from: K, to: K, output: &mut Vec<K>)

Trait Implementations

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

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

Formats the value using the given formatter.

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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)

Extends a collection with the contents of an iterator.

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

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

Creates a value from an iterator.

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

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

Returns the "default value" for a type.

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)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

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)

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

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)

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

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

type Output = V

The returned type after indexing

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

The method for the indexing (container[index]) operation

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

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

The method for the mutable indexing (container[index]) operation