Struct stable_skiplist::skipmap::SkipMap
[−]
[src]
pub struct SkipMap<K, V> { /* 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]
K: Ord,
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,
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,
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,
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,
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); }
fn range<Q>(&self, min: Bound<&Q>, max: Bound<&Q>) -> Iter<K, V> where
K: Borrow<Q>,
Q: Ord,
K: Borrow<Q>,
Q: Ord,
Constructs a double-ended iterator over a sub-range of elements in the skipmap, starting
at min, and ending at max. If min is Unbounded
, then it will be treated as "negative
infinity", and if max is Unbounded
, then it will be treated as "positive infinity". Thus
range(Unbounded, Unbounded) will yield the whole collection.
Examples
use skiplist::SkipMap; use skiplist::Bound::{Included, Unbounded}; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.range(Included(&3), Included(&7)) { println!("Key: {}, Value: {}", k, v); } assert_eq!(Some((&4, &4)), skipmap.range(Included(&4), Unbounded).next());
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]
AK: PartialEq<BK>,
AV: PartialEq<BV>,
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]
K: Eq,
V: Eq,
impl<AK, AV, BK, BV> PartialOrd<SkipMap<BK, BV>> for SkipMap<AK, AV> where
AK: PartialOrd<BK>,
AV: PartialOrd<BV>,
[src]
AK: PartialOrd<BK>,
AV: PartialOrd<BV>,
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]
K: Ord,
V: Ord,
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]
K: Ord,
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 (container[index]
) operation
impl<'a, K, V> IndexMut<usize> for SkipMap<K, V>
[src]
fn index_mut(&mut self, index: usize) -> &mut V
The method for the mutable indexing (container[index]
) operation
impl<K, V> Debug for SkipMap<K, V> where
K: Debug,
V: Debug,
[src]
K: Debug,
V: Debug,
impl<K, V> Display for SkipMap<K, V> where
K: Display,
V: Display,
[src]
K: Display,
V: Display,
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]
K: Ord,
fn from_iter<I>(iter: I) -> SkipMap<K, V> where
I: IntoIterator<Item = (K, V)>,
I: IntoIterator<Item = (K, V)>,
Creates a value from an iterator. Read more