pub struct TreapMap<K, V, Rng = XorShiftRng> { /* private fields */ }
Expand description
A map based on a randomized treap.
Implementations§
Source§impl<K: Ord, V> TreapMap<K, V, XorShiftRng>
impl<K: Ord, V> TreapMap<K, V, XorShiftRng>
Sourcepub fn new() -> TreapMap<K, V, XorShiftRng>
pub 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);
}
Source§impl<K: Ord, V, Rng: Rng> TreapMap<K, V, Rng>
impl<K: Ord, V, Rng: Rng> TreapMap<K, V, Rng>
Sourcepub fn new_with_rng(rng: Rng) -> TreapMap<K, V, Rng>
pub 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");
Sourcepub fn len(&self) -> usize
pub 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);
Sourcepub fn is_empty(&self) -> bool
pub 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());
Sourcepub fn clear(&mut self)
pub 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());
Sourcepub fn get(&self, key: &K) -> Option<&V>
pub 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);
Sourcepub fn get_mut(&mut self, key: &K) -> Option<&mut V>
pub 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"));
Sourcepub fn contains_key(&self, key: &K) -> bool
pub 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);
Sourcepub fn insert(&mut self, key: K, value: V) -> Option<V>
pub 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"));
Sourcepub fn remove(&mut self, key: &K) -> Option<V>
pub 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);
Sourcepub fn iter_ordered(&self) -> OrderedIter<'_, K, V> ⓘ
pub 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§
Source§impl<K: Ord, V, Rng: Rng> Extend<(K, V)> for TreapMap<K, V, Rng>
impl<K: Ord, V, Rng: Rng> Extend<(K, V)> for TreapMap<K, V, Rng>
Source§fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Source§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.
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);
Source§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.
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));
Source§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.
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);
}