Struct skiplist::skipmap::SkipMap
[−]
[src]
pub struct SkipMap<K, V> { // some fields omitted }
The skipmap provides a way of storing element pairs such that they keys are always sorted whilst at the same time providing efficient way to access, insert and removes nodes.
A particular node can be accessed through the matching key, and since the keys are always sorted, it is also possible to access key-value pairs by index.
Note that mutable references to keys are not available at all as this could result in a node being left out of the proper ordering.
Methods
impl<K, V> SkipMap<K, V> where K: Ord
[src]
fn new() -> Self
Create a new skipmap with the default number of 16 levels.
Examples
use skiplist::SkipMap; let mut skipmap: SkipMap<i64, String> = SkipMap::new();
fn with_capacity(capacity: usize) -> Self
Constructs a new, empty skipmap with the optimal number of levels for the intended
capacity. Specifically, it uses floor(log2(capacity))
number of levels, ensuring that
only a few nodes occupy the highest level.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::with_capacity(100); skipmap.extend((0..100).map(|x| (x, x)));
fn insert(&mut self, key: K, value: V) -> Option<V>
Insert the element into the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.len(), 2); assert!(!skipmap.is_empty());
impl<K, V> SkipMap<K, V>
[src]
fn clear(&mut self)
Clears the skipmap, removing all values.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); skipmap.clear(); assert!(skipmap.is_empty());
fn len(&self) -> usize
Returns the number of elements in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.len(), 10);
fn is_empty(&self) -> bool
Returns true
if the skipmap contains no elements.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert!(skipmap.is_empty()); skipmap.insert(1, "Rust"); assert!(!skipmap.is_empty());
fn front(&self) -> Option<(&K, &V)>
Provides a reference to the front element, or None
if the skipmap is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.front(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.front(), Some((&1, &"Hello")));
fn front_mut(&self) -> Option<(&K, &mut V)>
Provides a mutable reference to the front element, or None
if the skipmap is empty.
The reference to the key remains immutable as the keys must remain sorted.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.front(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.front_mut(), Some((&1, &mut "Hello")));
fn back(&self) -> Option<(&K, &V)>
Provides a reference to the back element, or None
if the skipmap is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.back(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.back(), Some((&2, &"World")));
fn back_mut(&mut self) -> Option<(&K, &mut V)>
Provides a reference to the back element, or None
if the skipmap is empty.
The reference to the key remains immutable as the keys must remain sorted.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.back(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.back_mut(), Some((&2, &mut "World")));
fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord
Provides a reference to the element at the given index, or None
if the skipmap is empty
or the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.get(&0), None); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.get(&0), Some(&0)); assert_eq!(skipmap.get(&10), None);
fn get_mut<Q: ?Sized>(&self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord
Provides a reference to the element at the given index, or None
if the skipmap is empty
or the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.get(&0), None); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.get_mut(&0), Some(&mut 0)); assert_eq!(skipmap.get_mut(&10), None); match skipmap.get_mut(&0) { Some(x) => *x = 100, None => (), } assert_eq!(skipmap.get(&0), Some(&100));
fn pop_front(&mut self) -> Option<(K, V)>
Removes the first element and returns it, or None
if the sequence is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.pop_front(), Some((1, "Hello"))); assert_eq!(skipmap.pop_front(), Some((2, "World"))); assert_eq!(skipmap.pop_front(), None);
fn pop_back(&mut self) -> Option<(K, V)>
Removes the last element and returns it, or None
if the sequence is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.pop_back(), Some((2, "World"))); assert_eq!(skipmap.pop_back(), Some((1, "Hello"))); assert_eq!(skipmap.pop_back(), None);
fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord
Returns true if the value is contained in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert!(skipmap.contains_key(&4)); assert!(!skipmap.contains_key(&15));
fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord
Removes and returns an element with the same value or None if there are no such values in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.remove(&4), Some(4)); // Removes the last one assert_eq!(skipmap.remove(&4), None); // No more '4' left
fn remove_index(&mut self, index: &usize) -> (K, V)
Removes and returns an element with the given index.
Panics
Panics is the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.remove_index(&4), (4, 4)); assert_eq!(skipmap.remove_index(&4), (5, 5));
fn into_iter(self) -> IntoIter<K, V>
Get an owning iterator over the entries of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.into_iter() { println!("Key {}, Value: {}", k, v); }
fn iter(&self) -> Iter<K, V>
Creates an iterator over the entries of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.iter() { println!("Key: {}, Value: {}", k, v); }
fn iter_mut(&self) -> IterMut<K, V>
Creates an mutable iterator over the entries of the skipmap.
The keys cannot be modified as they must remain in order.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.iter_mut() { println!("Key: {}, Value: {}", k, v); }
fn keys(&self) -> Keys<K, V>
Creates an iterator over the keys of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for k in skipmap.keys() { println!("Key: {}", k); }
fn values(&self) -> Values<K, V>
Creates an iterator over the values of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for v in skipmap.values() { println!("Value: {}", v); }
Trait Implementations
impl<K: Send, V: Send> Send for SkipMap<K, V>
[src]
impl<K: Sync, V: Sync> Sync for SkipMap<K, V>
[src]
impl<K, V> Drop for SkipMap<K, V>
[src]
impl<K: Ord, V> Default for SkipMap<K, V>
[src]
impl<AK, AV, BK, BV> PartialEq<SkipMap<BK, BV>> for SkipMap<AK, AV> where AK: PartialEq<BK>, AV: PartialEq<BV>
[src]
This implementation of PartialEq only checks that the values are equal; it does not check for
equivalence of other features (such as the ordering function and the node levels).
Furthermore, this uses T
's implementation of PartialEq and does not use the owning
skipmap's comparison function.
fn eq(&self, other: &SkipMap<BK, BV>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &SkipMap<BK, BV>) -> bool
This method tests for !=
.
impl<K, V> Eq for SkipMap<K, V> where K: Eq, V: Eq
[src]
impl<AK, AV, BK, BV> PartialOrd<SkipMap<BK, BV>> for SkipMap<AK, AV> where AK: PartialOrd<BK>, AV: PartialOrd<BV>
[src]
fn partial_cmp(&self, other: &SkipMap<BK, BV>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<K, V> Ord for SkipMap<K, V> where K: Ord, V: Ord
[src]
fn cmp(&self, other: &SkipMap<K, V>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<K, V> Extend<(K, V)> for SkipMap<K, V> where K: Ord
[src]
fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iterable: I)
Extends a collection with the contents of an iterator. Read more
impl<'a, K, V> Index<usize> for SkipMap<K, V>
[src]
type Output = V
The returned type after indexing
fn index(&self, index: usize) -> &V
The method for the indexing (Foo[Bar]
) operation
impl<'a, K, V> IndexMut<usize> for SkipMap<K, V>
[src]
impl<K, V> Debug for SkipMap<K, V> where K: Debug, V: Debug
[src]
impl<K, V> Display for SkipMap<K, V> where K: Display, V: Display
[src]
impl<K, V> IntoIterator for SkipMap<K, V>
[src]
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. Read more
impl<'a, K, V> IntoIterator for &'a SkipMap<K, V>
[src]
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. Read more
impl<'a, K, V> IntoIterator for &'a mut SkipMap<K, V>
[src]
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. Read more
impl<K, V> FromIterator<(K, V)> for SkipMap<K, V> where K: Ord
[src]
fn from_iter<I>(iter: I) -> SkipMap<K, V> where I: IntoIterator<Item=(K, V)>
Creates a value from an iterator. Read more
impl<K: Hash, V: Hash> Hash for SkipMap<K, V>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
Feeds this value into the state given, updating the hasher as necessary.
fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher
1.3.0
Feeds a slice of this type into the state provided.