Struct SkipList

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

SkipLists are fast probabilistic data-structures that feature logarithmic time complexity for inserting elements, testing element association, removing elements, and finding ranges of elements.

use convenient_skiplist::SkipList;

// Make a new skiplist
let mut sk = SkipList::new();
for i in 0..5usize {
    // Inserts are O(log(n)) on average
    sk.insert(i);
}
// You can print the skiplist!
dbg!(&sk);
// You can check if the skiplist contains an element, O(log(n))
assert!(sk.contains(&0));
assert!(!sk.contains(&10));
assert!(sk.remove(&0)); // remove is also O(log(n))
assert!(sk == sk); // equality checking is O(n)
let from_vec = SkipList::from(vec![1usize, 2, 3].into_iter()); // From<Vec<T>> is O(nlogn)
assert_eq!(vec![1, 2, 3], from_vec.iter_all().cloned().collect::<Vec<usize>>());

Implementations

impl<T: PartialOrd + Clone> SkipList<T>

pub fn new() -> SkipList<T>

Make a new, empty SkipList. By default there is three levels.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(0usize);

assert!(sk.contains(&0));

pub fn insert(&mut self, item: T) -> bool

Insert item into the SkipList.

Returns true if the item was actually inserted (i.e. wasn’t already in the skiplist) and false otherwise.

Runs in O(logn) time.

Arguments

• item - the item to insert.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(0usize);

assert!(sk.contains(&0));

pub fn contains(&self, item: &T) -> bool

Test if item is in the skiplist. Returns true if it’s in the skiplist, false otherwise.

Runs in O(logn) time

Arguments

• item - the item we’re testing.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(0usize);

assert!(sk.contains(&0));

pub fn remove(&mut self, item: &T) -> bool

Remove item from the SkipList.

Returns true if the item was in the collection to be removed, and false otherwise.

Runs in O(logn) time.

Arguments

• item - the item to remove.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(0usize);

let removed = sk.remove(&0);
assert!(removed);

pub fn remove_at(&mut self, index: usize) -> Option<T>

Remove and return the item at index.

Runs in O(log n) time.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..5);

assert_eq!(sk.len(), 5);
assert_eq!(sk.remove_at(1), Some(1));
assert_eq!(sk.len(), 4);

pub fn len(&self) -> usize

Return the number of elements in the skiplist.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();

sk.insert(0);
assert_eq!(sk.len(), 1);

sk.insert(1);
assert_eq!(sk.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if the skiplist is empty

pub fn index_of(&self, item: &T) -> Option<usize>

Find the index of item in the SkipList.

Runs in O(logn) time.

Arguments

• item: the item to find the position of.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(1);
sk.insert(2);
sk.insert(3);

assert_eq!(sk.index_of(&1), Some(0));
assert_eq!(sk.index_of(&2), Some(1));
assert_eq!(sk.index_of(&3), Some(2));
assert_eq!(sk.index_of(&999), None);

pub fn at_index(&self, index: usize) -> Option<&T>

Get the item at the index index in the SkipList.

Runs in O(logn) time.

Arguments

• index: the index to get the item at

Example

use convenient_skiplist::SkipList;
let sk = SkipList::from(0..10);
for i in 0..10 {
    assert_eq!(Some(&i), sk.at_index(i));
}
assert_eq!(None, sk.at_index(11));

let mut sk = SkipList::new();
sk.insert('a');
sk.insert('b');
sk.insert('c');
assert_eq!(Some(&'a'), sk.at_index(0));
assert_eq!(Some(&'b'), sk.at_index(1));
assert_eq!(Some(&'c'), sk.at_index(2));
assert_eq!(None, sk.at_index(3));

pub fn peek_first(&self) -> Option<&T>

Peek at the first item in the skiplist.

Runs in constant time.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(Some(&0), sk.peek_first());

pub fn peek_last(&self) -> Option<&T>

Peek at the last item in the skiplist.

Runs in O(log n) time.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(Some(&9), sk.peek_last());

pub fn pop_max(&mut self, count: usize) -> Vec<T>

Pop count elements off of the end of the Skiplist.

Runs in O(logn * count) time, O(logn + count) space.

Memory pressure: This is implemented such that the entire region of the skiplist is cleaved off at once. So you’ll see in the worse case (i.e. all towers have maximum height ~ logn) count * logn memory deallocations.

Returns an empty vec if count == 0.

Will dealloc the whole skiplist if count >= len and start fresh.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(Some(&7), sk.at_index(7));
assert_eq!(vec![7, 8, 9], sk.pop_max(3));
assert_eq!(vec![6], sk.pop_max(1));
assert_eq!(vec![4, 5], sk.pop_max(2));
assert_eq!(vec![0, 1, 2, 3], sk.pop_max(5));

let v: Vec<u32> = Vec::new();
assert_eq!(v, sk.pop_max(1000)); // empty

pub fn pop_back(&mut self) -> Option<T>

Pop the last element off of the skiplist.

Runs in O(logn) time, O(1) space.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(Some(9), sk.pop_back());

pub fn pop_front(&mut self) -> Option<T>

Pop the first element off of the skiplist.

Runs in O(logn) time, O(1) space.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(Some(0), sk.pop_front());

pub fn pop_min(&mut self, count: usize) -> Vec<T>

Pop count elements off of the start of the Skiplist.

Runs in O(logn * count) time, O(count) space.

Memory pressure: This is implemented such that the entire region of the skiplist is cleaved off at once. So you’ll see in the worse case (i.e. all towers have maximum height ~ logn) count * logn memory deallocations.

Returns an empty vec if count == 0.

Will dealloc the whole skiplist if count >= len and start fresh.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::from(0..10);

assert_eq!(vec![0, 1, 2], sk.pop_min(3));
assert_eq!(vec![3], sk.pop_min(1));
assert_eq!(vec![4, 5], sk.pop_min(2));
assert_eq!(vec![6, 7, 8, 9], sk.pop_max(5));

let v: Vec<u32> = Vec::new();
assert_eq!(v, sk.pop_min(1000)); // empty

pub fn iter_all(&self) -> IterAll<'_, T>

Iterator over all elements in the Skiplist.

This runs in O(n) time.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
sk.insert(0usize);
sk.insert(1usize);
sk.insert(2usize);
for item in sk.iter_all() {
    println!("{:?}", item);
}

pub fn range<'a>(&'a self, start: &'a T, end: &'a T) -> SkipListRange<'a, T>

Iterator over an inclusive range of elements in the SkipList.

This runs in O(logn + k), where k is the width of range.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
for item in 0..100 {
    sk.insert(item);
}

for item in sk.range(&20, &40) {
    println!("{}", item); // First prints 20, then 21, ... and finally 40.
}

pub fn index_range<R: RangeBounds<usize>>( &self, range: R, ) -> SkipListIndexRange<'_, R, T>

Iterate over a range of indices.

This runs in O(logn + k), where k is the width of range.

This is different than SkipList::range as this operates on indices and not values.

Example

use convenient_skiplist::SkipList;
let mut sk = SkipList::new();
for c in 'a'..'z' {
    sk.insert(c);
}

for item in sk.index_range(0..5) {
    println!("{}", item); // Prints a, b, c, d, e
}

pub fn range_with<F>(&self, inclusive_fn: F) -> IterRangeWith<'_, T, F>

where F: Fn(&T) -> RangeHint,

Iterator over an inclusive range of elements in the SkipList, as defined by the inclusive_fn.

This runs in O(logn + k), where k is the width of range.

As the skiplist is ordered in an ascending way, inclusive_fn should be structured with the idea in mind that you’re going to see the smallest elements first. inclusive_fn should be designed to extract a single contiguous stretch of elements.

This iterator will find the smallest element in the range, and then return elements until it finds the first element larger than the range.

If multiple ranges are desired, you can use range_with multiple times, and simply use the last element of the previous run as the start of the next run.

Example

use convenient_skiplist::{RangeHint, SkipList};
let mut sk = SkipList::new();
for item in 0..100 {
    sk.insert(item);
}

let desired_range = sk.range_with(|&ele| {
    if ele <= 5 {
        RangeHint::SmallerThanRange
    } else if ele <= 30 {
        RangeHint::InRange
    } else {
        RangeHint::LargerThanRange
    }
});
for item in desired_range {
    println!("{}", item); // First prints 6, then 7, ... and finally 30.
}

pub fn clear(&mut self) -> usize

Clear (deallocate all entries in) the skiplist.

Returns the number of elements removed (length of bottom row).

Example

use convenient_skiplist::{RangeHint, SkipList};
let mut sk = SkipList::from(0..10);
assert_eq!(sk.clear(), 10);
assert_eq!(sk, SkipList::new());

Trait Implementations

impl<T: Clone + PartialOrd> Clone for SkipList<T>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for SkipList<T>

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

Formats the value using the given formatter.

impl<T: PartialOrd + Clone> Default for SkipList<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> Drop for SkipList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: PartialOrd + Clone, I: Iterator<Item = T>> From<I> for SkipList<T>

fn from(iter: I) -> Self

Converts to this type from the input type.

impl<T: Clone + PartialOrd> From<SkipList<T>> for Vec<T>

fn from(sk: SkipList<T>) -> Vec<T>

Converts to this type from the input type.

impl<T: PartialOrd + Clone> FromIterator<T> for SkipList<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> SkipList<T>

Creates a value from an iterator.

impl<T: PartialOrd + Clone> Index<usize> for SkipList<T>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T: PartialOrd + Clone> IntoIterator for SkipList<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialOrd + Clone> PartialEq for SkipList<T>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.