Struct convenient_skiplist::SkipList

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

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

Methods

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

Important traits for IterAll<'a, T>

impl<'a, T: PartialOrd> Iterator for IterAll<'a, T> type Item = &'a T;

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

Iterator over all elements in the Skiplist.

This runs in O(logn) 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);
}

Important traits for SkipListRange<'a, T>

impl<'a, T: PartialOrd> Iterator for SkipListRange<'a, T> type Item = &'a T;

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.
}

Important traits for IterRangeWith<'a, T, F>

impl<'a, T, F> Iterator for IterRangeWith<'a, T, F> where
    T: PartialOrd,
    F: Fn(&T) -> RangeHint,  type Item = &'a T;

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.
}

Trait Implementations

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

Performs the conversion.

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> 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<SkipList<T>> for SkipList<T>

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.