Struct skip_list::SkipList

pub struct SkipList<K, V> { /* private fields */ }

Implementations

impl<K: Ord, V> SkipList<K, V>

pub fn new(max_level: usize) -> Self

Create a skip list with max level

Example

use skip_list::SkipList;
let mut skiplist: SkipList<i32, i32> = SkipList::new(12);

pub fn get(&self, k: &K) -> Option<&V>

Returns a reference to the value of the key in skip list or None if not exist.

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
 
skip_list.insert(1, "a");
 
assert_eq!(skip_list.get(&1), Some(&"a"));

pub fn insert(&mut self, k: K, v: V) -> Option<V>

Insert a key-value pair into skip list. If the key already exists, updates key’s value and return old value. Otherwise, None is returned.

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
 
assert_eq!(skip_list.insert(1, "a"), None);
assert_eq!(skip_list.get(&1), Some(&"a"));
assert_eq!(skip_list.insert(1, "aa"), Some("a"));
assert_eq!(skip_list.get(&1), Some(&"aa"));
 

pub fn delete(&mut self, k: &K) -> Option<V>

Deletes and returns the key’s value from skip list or None if not exist.

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
 
assert_eq!(skip_list.insert(1, "a"), None);
assert_eq!(skip_list.get(&1), Some(&"a"));
assert_eq!(skip_list.delete(&1), Some("a"));
assert_eq!(skip_list.get(&1), None);

pub fn iter(&self) -> Iter<'_, K, V>

Visit all key-value pairs in the order of keys The Iterator element type is (&K, &V).

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
assert_eq!(skip_list.insert(3, "c"), None);
assert_eq!(skip_list.insert(4, "d"), None);
assert_eq!(skip_list.insert(2, "b"), None);
assert_eq!(skip_list.insert(5, "e"), None);
assert_eq!(skip_list.insert(1, "a"), None);
 
// visit all key-value paris in the order of keys
let mut keys = vec![];
let mut values = vec![];
for (k, v) in skip_list.iter() {
    keys.push(k);
    values.push(v);
}
 
// check key sorted
assert_eq!(keys, vec![&1, &2, &3, &4, &5]);
assert_eq!(values, vec![&"a", &"b", &"c", &"d", &"e"]);

pub fn iter_mut(&self) -> IterMut<'_, K, V>

Visit all key-value pairs in the order of keys The Iterator element type is (&K, &mut V). The value is mut, can be update;

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
assert_eq!(skip_list.insert(3, 3), None);
assert_eq!(skip_list.insert(4, 4), None);
assert_eq!(skip_list.insert(2, 2), None);
assert_eq!(skip_list.insert(5, 5), None);
assert_eq!(skip_list.insert(1, 1), None);
 
for (k, v) in skip_list.iter_mut() {
    *v = k * 10;
}
// visit all key-value paris in the order of keys
let mut keys = vec![];
let mut values = vec![];
for (k, v) in skip_list.iter() {
    keys.push(k);
    values.push(v);
}
 
// check key sorted
assert_eq!(keys, vec![&1, &2, &3, &4, &5]);
assert_eq!(values, vec![&10, &20, &30, &40, &50]);

Trait Implementations

impl<K, V> Default for SkipList<K, V>

fn default() -> Self

Create a skip list with max level(12)

Example

use skip_list::SkipList;
let mut skiplist: SkipList<i32, i32> = SkipList::default();

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

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V> IntoIterator for SkipList<K, V>

fn into_iter(self) -> Self::IntoIter

Visit all key-value pairs in the order of keys The Iterator element type is (K, V).

Example

use skip_list::SkipList;
 
let mut skip_list = SkipList::default();
assert_eq!(skip_list.insert(3, "c"), None);
assert_eq!(skip_list.insert(4, "d"), None);
assert_eq!(skip_list.insert(2, "b"), None);
assert_eq!(skip_list.insert(5, "e"), None);
assert_eq!(skip_list.insert(1, "a"), None);
 
// visit all key-value paris in the order of keys
let mut keys = vec![];
let mut values = vec![];
for (k, v) in skip_list.into_iter() {
    keys.push(k);
    values.push(v);
}
 
// check key sorted
assert_eq!(keys, vec![1, 2, 3, 4, 5]);
assert_eq!(values, vec!["a", "b", "c", "d", "e"]);

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?