Struct skiplist::ordered_skiplist::OrderedSkipList

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

The ordered skiplist provides a way of storing elements such that they are always sorted and at the same time provides efficient way to access, insert and remove nodes. Just like SkipList, it also provides access to indices.

By default, the OrderedSkipList uses the comparison function a.partial_cmp(b).expect("Value cannot be ordered"). This allows the list to handles all types which implement Ord and PartialOrd, though it will panic if value which cannot be ordered is inserted (such as Float::nan()).

The ordered skiplist has an associated sorting function which must be well-behaved. Specifically, given some ordering function f(a, b), it must satisfy the following properties:

• Be well defined: f(a, b) should always return the same value
• Be anti-symmetric: f(a, b) == Greater iff f(b, a) == Less and f(a, b) == Equal == f(b, a).
• By transitive: If f(a, b) == Greater and f(b, c) == Greater then f(a, c) == Greater.

Failure to satisfy these properties can result in unexpected behavior at best, and at worst will cause a segfault, null deref, or some other bad behavior.

Methods

impl<T> OrderedSkipList<T> where
    T: PartialOrd, 

pub fn new() -> Self

Create a new skiplist with the default default comparison function of |&a, &b| a.cmp(b).unwrap() and the default number of 16 levels. As a result, any element which cannot be ordered will cause insertion to panic.

The comparison function can always be changed with sort_by, which has essentially no cost if done before inserting any elements.

Panic

The default comparison function will cause a panic if an element is inserted which cannot be ordered (such as Float::nan()).

Examples

use skiplist::OrderedSkipList;

let mut skiplist: OrderedSkipList<i64> = OrderedSkipList::new();

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty skiplist 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.

It uses the default comparison function of |&a, &b| a.cmp(b).unwrap() and can be changed with sort_by.

Panic

The default comparison function will cause a panic if an element is inserted which cannot be ordered (such as Float::nan()).

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::with_capacity(100);
skiplist.extend(0..100);

impl<T> OrderedSkipList<T>

pub unsafe fn with_comp<F>(f: F) -> Self where
    F: 'static + Fn(&T, &T) -> Ordering, 

Create a new skiplist using the provided function in order to determine the ordering of elements within the list. It will be generated with 16 levels.

Safety

The ordered skiplist relies on a well-behaved comparison function. Specifically, given some ordering function f(a, b), it must satisfy the following properties:

• Be well defined: f(a, b) should always return the same value
• Be anti-symmetric: f(a, b) == Greater if and only if f(b, a) == Less, and f(a, b) == Equal == f(b, a).
• By transitive: If f(a, b) == Greater and f(b, c) == Greater then f(a, c) == Greater.

Failure to satisfy these properties can result in unexpected behavior at best, and at worst will cause a segfault, null deref, or some other bad behavior.

Examples

use skiplist::OrderedSkipList;
use std::cmp::Ordering;

// Store even number before odd ones and sort as usual within same parity group.
let mut skiplist = unsafe { OrderedSkipList::with_comp(
    |a: &u64, b: &u64|
    if a%2 == b%2 {
        a.cmp(b)
    } else if a%2 == 0 {
        Ordering::Less
    } else {
        Ordering::Greater
    })};

pub unsafe fn sort_by<F>(&mut self, f: F) where
    F: 'static + Fn(&T, &T) -> Ordering, 

Change the method which determines the ordering of the elements in the skiplist.

Panics

This call will panic if the ordering of the elements will be changed as a result of this new comparison method.

As a result, sort_by is best to call if the skiplist is empty or has just a single element and may panic with 2 or more elements.

Safety

The ordered skiplist relies on a well-behaved comparison function. Specifically, given some ordering function f(a, b), it must satisfy the following properties:

• Be well defined: f(a, b) should always return the same value
• Be anti-symmetric: f(a, b) == Greater if and only if f(b, a) == Less, and f(a, b) == Equal == f(b, a).
• By transitive: If f(a, b) == Greater and f(b, c) == Greater then f(a, c) == Greater.

Failure to satisfy these properties can result in unexpected behavior at best, and at worst will cause a segfault, null deref, or some other bad behavior.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
unsafe { skiplist.sort_by(|a: &i64, b: &i64| b.cmp(a)) } // All good; skiplist empty.
skiplist.insert(0);                                      // Would still be good here.
skiplist.insert(10);
unsafe { skiplist.sort_by(|a: &i64, b: &i64| a.cmp(b)) } // Panics; order would change.

pub fn clear(&mut self)

Clears the skiplist, removing all values.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
skiplist.clear();
assert!(skiplist.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the skiplist.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
assert_eq!(skiplist.len(), 10);

pub fn is_empty(&self) -> bool

Returns true if the skiplist contains no elements.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
assert!(skiplist.is_empty());

skiplist.insert(1);
assert!(!skiplist.is_empty());

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

Insert the element into the skiplist.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();

skiplist.insert(0);
skiplist.insert(5);
assert_eq!(skiplist.len(), 2);
assert!(!skiplist.is_empty());

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

Provides a reference to the front element, or None if the skiplist is empty.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
assert!(skiplist.front().is_none());

skiplist.insert(1);
skiplist.insert(2);
assert_eq!(skiplist.front(), Some(&1));

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

Provides a reference to the back element, or None if the skiplist is empty.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
assert!(skiplist.back().is_none());

skiplist.insert(1);
skiplist.insert(2);
assert_eq!(skiplist.back(), Some(&2));

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

Provides a reference to the element at the given index, or None if the skiplist is empty or the index is out of bounds.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
assert!(skiplist.get(0).is_none());
skiplist.extend(0..10);
assert_eq!(skiplist.get(0), Some(&0));
assert!(skiplist.get(10).is_none());

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

Removes the first element and returns it, or None if the sequence is empty.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.insert(1);
skiplist.insert(2);

assert_eq!(skiplist.pop_front(), Some(1));
assert_eq!(skiplist.pop_front(), Some(2));
assert!(skiplist.pop_front().is_none());

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

Removes the last element and returns it, or None if the sequence is empty.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.insert(1);
skiplist.insert(2);

assert_eq!(skiplist.pop_back(), Some(2));
assert_eq!(skiplist.pop_back(), Some(1));
assert!(skiplist.pop_back().is_none());

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

Returns true if the value is contained in the skiplist.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
assert!(skiplist.contains(&4));
assert!(!skiplist.contains(&15));

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

Removes and returns an element with the same value or None if there are no such values in the skiplist.

If the skiplist contains multiple values with the desired value, the highest level one will be removed. This will results in a deterioration in the skiplist's performance if the skiplist contains many duplicated values which are very frequently inserted and removed. In such circumstances, the slower remove_first method is preferred.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
assert_eq!(skiplist.remove(&4), Some(4)); // Removes the last one
assert!(skiplist.remove(&4).is_none()); // No more '4' left

pub fn remove_first(&mut self, value: &T) -> Option<T>

Removes and returns an element with the same value or None if there are no such values in the skiplist.

If the skiplist contains multiple values with the desired value, the first one in the skiplist will be returned. If the skiplist contains many duplicated values which are frequently inserted and removed, this method should be preferred over remove.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
for _ in 0..10 {
    skiplist.extend(0..10);
}
assert!(skiplist.remove(&15).is_none());
for _ in 0..9 {
    for i in 0..10 {
        skiplist.remove_first(&i);
    }
}
assert_eq!(skiplist.remove_first(&4), Some(4)); // Removes the last one
assert!(skiplist.remove_first(&4).is_none()); // No more '4' left

pub fn remove_index(&mut self, index: usize) -> T

Removes and returns an element with the given index.

Panics

Panics is the index is out of bounds.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
assert_eq!(skiplist.remove_index(4), 4);
assert_eq!(skiplist.remove_index(4), 5);

pub fn retain<F>(&mut self, f: F) where
    F: FnMut(&T) -> bool, 

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. This method operates in place.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
skiplist.retain(|&x| x%2 == 0);

pub fn dedup(&mut self)

Removes all repeated elements in the skiplist using the skiplist's comparison function.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..5);
skiplist.insert(3);
skiplist.dedup();

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = T;

pub fn into_iter(self) -> IntoIter<T>

Get an owning iterator over the entries of the skiplist.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
for i in skiplist.into_iter() {
    println!("Value: {}", i);
}

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

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

Creates an iterator over the entries of the skiplist.

Examples

use skiplist::OrderedSkipList;

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
for i in skiplist.iter() {
    println!("Value: {}", i);
}

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

pub fn range(&self, min: Bound<&T>, max: Bound<&T>) -> Iter<T>

Constructs a double-ended iterator over a sub-range of elements in the skiplist, 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::OrderedSkipList;
use std::collections::Bound::{Included, Unbounded};

let mut skiplist = OrderedSkipList::new();
skiplist.extend(0..10);
for i in skiplist.range(Included(&3), Included(&7)) {
    println!("Value: {}", i);
}
assert_eq!(Some(&4), skiplist.range(Included(&4), Unbounded).next());

Trait Implementations

impl<T> Debug for OrderedSkipList<T> where
    T: Debug, 

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

Formats the value using the given formatter.

impl<T: PartialOrd> Default for OrderedSkipList<T>

fn default() -> OrderedSkipList<T>

Returns the "default value" for a type.

impl<T> Display for OrderedSkipList<T> where
    T: Display, 

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

Formats the value using the given formatter.

impl<T> Drop for OrderedSkipList<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Eq for OrderedSkipList<T> where
    T: Eq, 

impl<T> Extend<T> for OrderedSkipList<T>

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

Extends a collection with the contents of an iterator.

impl<T> FromIterator<T> for OrderedSkipList<T> where
    T: PartialOrd, 

fn from_iter<I>(iter: I) -> OrderedSkipList<T> where
    I: IntoIterator<Item = T>, 

Creates a value from an iterator.

impl<T: Hash> Hash for OrderedSkipList<T>

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<T> Index<usize> for OrderedSkipList<T>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T> IntoIterator for OrderedSkipList<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?

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = T;

fn into_iter(self) -> IntoIter<T>

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a OrderedSkipList<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?

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

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

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a mut OrderedSkipList<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?

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;

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

Creates an iterator from a value.

impl<T> Ord for OrderedSkipList<T> where
    T: Ord, 

fn cmp(&self, other: &OrderedSkipList<T>) -> 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<A, B> PartialEq<OrderedSkipList<B>> for OrderedSkipList<A> where
    A: PartialEq<B>, 

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 skiplist's comparison function.

fn eq(&self, other: &OrderedSkipList<B>) -> bool

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

fn ne(&self, other: &OrderedSkipList<B>) -> bool

This method tests for !=.

impl<A, B> PartialOrd<OrderedSkipList<B>> for OrderedSkipList<A> where
    A: PartialOrd<B>, 

fn partial_cmp(&self, other: &OrderedSkipList<B>) -> 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<T: Send> Send for OrderedSkipList<T>

impl<T: Sync> Sync for OrderedSkipList<T>