Struct TreapMap

Source
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>

Source

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>

Source

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");
Source

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

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());
Source

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());
Source

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

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"));
Source

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

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"));
Source

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

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]);
Source§

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

Source

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

Trait Implementations§

Source§

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

Source§

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

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

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

Source§

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

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

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

Source§

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

Returns the “default value” for a type. Read more
Source§

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)

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more
Source§

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

Source§

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

Creates a value from an iterator. Read more
Source§

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

Source§

type Output = V

The returned type after indexing.
Source§

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

Performs the indexing (container[index]) operation. Read more
Source§

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

Source§

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

Performs the mutable indexing (container[index]) operation. Read more
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.

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§

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

The type of the elements being iterated over.
Source§

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

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

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

Creates an iterator from a value. Read more
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.

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§

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

The type of the elements being iterated over.
Source§

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

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

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

Creates an iterator from a value. Read more
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.

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);
}
Source§

type Item = (K, V)

The type of the elements being iterated over.
Source§

type IntoIter = IntoIter<K, V>

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

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

Creates an iterator from a value. Read more

Auto Trait Implementations§

§

impl<K, V, Rng> Freeze for TreapMap<K, V, Rng>
where Rng: Freeze,

§

impl<K, V, Rng> RefUnwindSafe for TreapMap<K, V, Rng>

§

impl<K, V, Rng> Send for TreapMap<K, V, Rng>
where Rng: Send, K: Send, V: Send,

§

impl<K, V, Rng> Sync for TreapMap<K, V, Rng>
where Rng: Sync, K: Sync, V: Sync,

§

impl<K, V, Rng> Unpin for TreapMap<K, V, Rng>
where Rng: Unpin,

§

impl<K, V, Rng> UnwindSafe for TreapMap<K, V, Rng>
where Rng: UnwindSafe, 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> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dst: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. 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> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

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

Source§

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>,

Source§

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.