Struct skiplist::skiplist::SkipList [−] [src]

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

SkipList provides a way of storing elements and provides efficient way to access, insert and remove nodes.

Methods

impl<T> SkipList<T>

fn new() -> Self

Create a new skiplist with the default number of 16 levels.

Examples

use skiplist::SkipList;

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

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.

Examples

use skiplist::SkipList;

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

fn clear(&mut self)

Clears the skiplist, removing all values.

Examples

use skiplist::SkipList;

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

fn len(&self) -> usize

Returns the number of elements in the skiplist.

Examples

use skiplist::SkipList;

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

fn is_empty(&self) -> bool

Returns true if the skiplist contains no elements.

Examples

use skiplist::SkipList;

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

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

fn insert(&mut self, value: T, index: usize)

Insert the element into the skiplist at the given index, shifting all subsequent nodes down.

Panics

Panics if the insert index is greater than the length of the skiplist.

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();

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

fn push_front(&mut self, value: T)

Insert the element into the front of the skiplist.

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
skiplist.push_front(1);
skiplist.push_front(2);

fn push_back(&mut self, value: T)

Insert the element into the back of the skiplist.

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
skiplist.push_back(1);
skiplist.push_back(2);

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

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.front(), None);

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

fn front_mut(&mut self) -> Option<&mut T>

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.front(), None);

skiplist.push_back(1);
skiplist.push_back(2);
assert_eq!(skiplist.front_mut(), Some(&mut 1));

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

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.back(), None);

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

fn back_mut(&mut self) -> Option<&mut T>

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.back(), None);

skiplist.push_back(1);
skiplist.push_back(2);
assert_eq!(skiplist.back_mut(), Some(&mut 2));

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::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.get(0), None);
skiplist.extend(0..10);
assert_eq!(skiplist.get(0), Some(&0));
assert_eq!(skiplist.get(10), None);

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

Provides a mutable 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::SkipList;

let mut skiplist = SkipList::new();
assert_eq!(skiplist.get_mut(0), None);
skiplist.extend(0..10);
assert_eq!(skiplist.get_mut(0), Some(&mut 0));
assert_eq!(skiplist.get_mut(10), None);

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

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
skiplist.push_back(1);
skiplist.push_back(2);

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

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

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

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
skiplist.push_back(1);
skiplist.push_back(2);

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

fn remove(&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::SkipList;

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

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::SkipList;

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

fn into_iter(self) -> IntoIter<T>

Get an owning iterator over the entries of the skiplist.

Examples

use skiplist::SkipList;

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

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

Creates an iterator over the entries of the skiplist.

Examples

use skiplist::SkipList;

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

fn iter_mut(&self) -> IterMut<T>

Creates an mutable iterator over the entries of the skiplist.

Examples

use skiplist::SkipList;

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

fn range(&self, min: Bound<usize>, max: Bound<usize>) -> 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

#![feature(collections_bound)]
use skiplist::SkipList;
use std::collections::Bound::{Included, Unbounded};

let mut skiplist = SkipList::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());

fn range_mut(&mut self, min: Bound<usize>, max: Bound<usize>) -> IterMut<T>

Constructs a mutable 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

#![feature(collections_bound)]
use skiplist::SkipList;
use std::collections::Bound::{Included, Unbounded};

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

impl<T> SkipList<T> where T: PartialEq

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

Returns true if the value is contained in the skiplist.

Examples

use skiplist::SkipList;

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

fn dedup(&mut self)

Removes all consecutive repeated elements in the skiplist.

Examples

use skiplist::SkipList;

let mut skiplist = SkipList::new();
skiplist.push_back(0);
skiplist.push_back(0);
assert_eq!(skiplist.len(), 2);
skiplist.dedup();
assert_eq!(skiplist.len(), 1);

Trait Implementations

impl<T: Send> Send for SkipList<T>

impl<T: Sync> Sync for SkipList<T>

impl<T> Drop for SkipList<T>

fn drop(&mut self)

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

fn default() -> SkipList<T>

impl<A, B> PartialEq<SkipList<B>> for SkipList<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: &SkipList<B>) -> bool

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

impl<T> Eq for SkipList<T> where T: Eq

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

fn partial_cmp(&self, other: &SkipList<B>) -> Option<Ordering>

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

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

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

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

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

fn cmp(&self, other: &SkipList<T>) -> Ordering

impl<T> Extend<T> for SkipList<T>

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

impl<T> Index<usize> for SkipList<T>

type Output = T

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

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

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

impl<T> Display for SkipList<T> where T: Display

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

impl<T> IntoIterator for SkipList<T>

type Item = T

type IntoIter = IntoIter<T>

fn into_iter(self) -> IntoIter<T>

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

type Item = &'a T

type IntoIter = Iter<'a, T>

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

impl<'a, T> IntoIterator for &'a mut SkipList<T>

type Item = &'a mut T

type IntoIter = IterMut<'a, T>

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

impl<T> FromIterator<T> for SkipList<T> where T: PartialOrd

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

impl<T: Hash> Hash for SkipList<T>

fn hash<H: Hasher>(&self, state: &mut H)

fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher