Struct skiplist::skipmap::SkipMap

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, 

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

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

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

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

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

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

pub 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!(skipmap.front().is_none());

skipmap.insert(1, "Hello");
skipmap.insert(2, "World");
assert_eq!(skipmap.front(), Some((&1, &"Hello")));

pub 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!(skipmap.front().is_none());

skipmap.insert(1, "Hello");
skipmap.insert(2, "World");
assert_eq!(skipmap.front_mut(), Some((&1, &mut "Hello")));

pub 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!(skipmap.back().is_none());

skipmap.insert(1, "Hello");
skipmap.insert(2, "World");
assert_eq!(skipmap.back(), Some((&2, &"World")));

pub 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!(skipmap.back().is_none());

skipmap.insert(1, "Hello");
skipmap.insert(2, "World");
assert_eq!(skipmap.back_mut(), Some((&2, &mut "World")));

pub 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!(skipmap.get(&0).is_none());
skipmap.extend((0..10).map(|x| (x, x)));
assert_eq!(skipmap.get(&0), Some(&0));
assert!(skipmap.get(&10).is_none());

pub 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!(skipmap.get(&0).is_none());
skipmap.extend((0..10).map(|x| (x, x)));
assert_eq!(skipmap.get_mut(&0), Some(&mut 0));
assert!(skipmap.get_mut(&10).is_none());

match skipmap.get_mut(&0) {
    Some(x) => *x = 100,
    None => (),
}
assert_eq!(skipmap.get(&0), Some(&100));

pub 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!(skipmap.pop_front().is_none());

pub 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!(skipmap.pop_back().is_none());

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

pub 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!(skipmap.remove(&4).is_none());    // No more '4' left

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

Important traits for IntoIter<K, V>

impl<K, V> Iterator for IntoIter<K, V> type Item = (K, V);

pub 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);
}

Important traits for Iter<'a, K, V>

impl<'a, K, V> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

pub 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);
}

Important traits for IterMut<'a, K, V>

impl<'a, K, V> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

pub 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);
}

Important traits for Keys<'a, K, V>

impl<'a, K, V> Iterator for Keys<'a, K, V> type Item = &'a K;

pub 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);
}

Important traits for Values<'a, K, V>

impl<'a, K, V> Iterator for Values<'a, K, V> type Item = &'a V;

pub 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);
}

Important traits for Iter<'a, K, V>

impl<'a, K, V> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

pub fn range<Q>(&self, min: Bound<&Q>, max: Bound<&Q>) -> Iter<K, V> where
    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 std::collections::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, V> Debug for SkipMap<K, V> where
    K: Debug,
    V: Debug, 

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

Formats the value using the given formatter.

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

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

Returns the "default value" for a type.

impl<K, V> Display for SkipMap<K, V> where
    K: Display,
    V: Display, 

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

Formats the value using the given formatter.

impl<K, V> Drop for SkipMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V> Eq for SkipMap<K, V> where
    K: Eq,
    V: Eq, 

impl<K, V> Extend<(K, V)> for SkipMap<K, V> where
    K: Ord, 

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iterable: I)

Extends a collection with the contents of an iterator.

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

fn from_iter<I>(iter: I) -> SkipMap<K, V> where
    I: IntoIterator<Item = (K, V)>, 

Creates a value from an iterator.

impl<K: Hash, V: Hash> Hash for SkipMap<K, V>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<'a, K, V> Index<usize> for SkipMap<K, V>

type Output = V

The returned type after indexing.

fn index(&self, index: usize) -> &V

Performs the indexing (container[index]) operation.

impl<'a, K, V> IndexMut<usize> for SkipMap<K, V>

fn index_mut(&mut self, index: usize) -> &mut V

Performs the mutable indexing (container[index]) operation.

impl<K, V> IntoIterator for SkipMap<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?

Important traits for IntoIter<K, V>

impl<K, V> Iterator for IntoIter<K, V> type Item = (K, V);

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

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a SkipMap<K, V>

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?

Important traits for Iter<'a, K, V>

impl<'a, K, V> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

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

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut SkipMap<K, V>

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?

Important traits for IterMut<'a, K, V>

impl<'a, K, V> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

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

Creates an iterator from a value.

impl<K, V> Ord for SkipMap<K, V> where
    K: Ord,
    V: Ord, 

fn cmp(&self, other: &SkipMap<K, V>) -> Ordering

This method returns an [Ordering] between self and other.

#[must_use] fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use] fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use] fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<AK, AV, BK, BV> PartialEq<SkipMap<BK, BV>> for SkipMap<AK, AV> where
    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 ==.

fn ne(&self, other: &SkipMap<BK, BV>) -> bool

This method tests for !=.

impl<AK, AV, BK, BV> PartialOrd<SkipMap<BK, BV>> for SkipMap<AK, AV> where
    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.

#[must_use] fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use] fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use] fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use] fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Send, V: Send> Send for SkipMap<K, V>

impl<K: Sync, V: Sync> Sync for SkipMap<K, V>