Struct SkipList

pub struct SkipList<T> { /* private fields */ }

Implementations

impl<T: Ord> SkipList<T>

pub fn new() -> Self

Creates a new, empty SkipList.

pub fn len(&self) -> usize

Returns the number of elements in the list.

pub fn is_empty(&self) -> bool

Wrapper for len() that returns a Boolean indicating whether the list is empty.

pub fn get<Q>(&self, key: &Q) -> Option<&T>

where Q: Ord + ?Sized, T: Borrow<Q>,

Returns the a reference to the entry associated with the search key if it exists in the list, otherwise returns None to indicate that the key is not in the list.

Represents Pugh’s canonical Search operation as described in the original paper.

pub fn contains<Q>(&self, key: &Q) -> bool

where Q: Ord + ?Sized, T: Borrow<Q>,

Returns a Boolean indicating whether the supplied search key exists in the list.

Wrapper for the public get() operation, which itself wraps the private skip_search() operation.

pub fn insert(&mut self, entry: T)

Inserts a new entry into the skip list.

Allows duplicates, where ordering is determined by insertion order such that the most recent duplicates come before older entries.

pub fn remove<Q>(&mut self, key: &Q) -> Option<T>

where Q: Ord + ?Sized, T: Borrow<Q>,

Removes and returns the value for a given key, if it exists in the list. Returns None if the key does not exist in the list.

This function does not technically adhere to Pugh’s original removal algorithm. It uses Vec::swap_remove for simplified backing list compaction with the side effect of re-ordering remaining elements. The resultant removal time is therefore O(n * height), which is O(n * log(n)) expected, and O(n^2) worst case.

pub fn get_kth(&self, k: usize) -> Option<&T>

Returns the Kth value in the list, if it exists.

pub fn range<Q, R>(&self, range: R) -> RangeIter<'_, T, Q, R>

where Q: Ord + ?Sized, T: Borrow<Q>, R: RangeBounds<Q>,

Returns an inclusive iterator over a range of values in the list from start to end.

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

Returns an iterator over borrowed values in the list.

Trait Implementations

impl<T: Ord> Default for SkipList<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T: Ord> IntoIterator for &'a SkipList<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.