Struct stable_skiplist::ordered_skiplist::OrderedSkipList
[−]
[src]
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 folowing properties:
- Be well defined:
f(a, b)
should always return the same value - Be anti-symmetric:
f(a, b) == Greater
ifff(b, a) == Less
andf(a, b) == Equal == f(b, a)
. - By transitive: If
f(a, b) == Greater
andf(b, c) == Greater
thenf(a, c) == Greater
.
Failure to satisfy these properties can result in unexpected behaviour at best, and at worst will cause a segfault, null deref, or some other bad behaviour.
Methods
impl<T> OrderedSkipList<T> where
T: PartialOrd,
[src]
T: PartialOrd,
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();
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>
[src]
unsafe fn with_comp<F>(f: F) -> Self where
F: 'static + Fn(&T, &T) -> Ordering,
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.
Warning
The sorting function which must be well-behaved. Specifically, given some ordering
function f(a, b)
, it must satisfy the folowing properties:
- Be well defined:
f(a, b)
should always return the same value - Be anti-symmetric:
f(a, b) == Greater
ifff(b, a) == Less
andf(a, b) == Equal == f(b, a)
. - By transitive: If
f(a, b) == Greater
andf(b, c) == Greater
thenf(a, c) == Greater
.
Failure to satisfy these properties can result in unexpected behaviour at best, and at worst will cause a segfault, null deref, or some other bad behaviour.
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 })};
unsafe fn sort_by<F>(&mut self, f: F) where
F: 'static + Fn(&T, &T) -> Ordering,
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.
Warning
The sorting function which must be well-behaved. Specifically, given some ordering
function f(a, b)
, it must satisfy the folowing properties:
- Be well defined:
f(a, b)
should always return the same value - Be anti-symmetric:
f(a, b) == Greater
ifff(b, a) == Less
andf(a, b) == Equal == f(b, a)
. - By transitive: If
f(a, b) == Greater
andf(b, c) == Greater
thenf(a, c) == Greater
.
Failure to satisfy these properties can result in unexpected behaviour at best, and at worst will cause a segfault, null deref, or some other bad behaviour.
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.
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());
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);
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());
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());
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_eq!(skiplist.front(), None); skiplist.insert(1); skiplist.insert(2); assert_eq!(skiplist.front(), Some(&1));
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_eq!(skiplist.back(), None); skiplist.insert(1); skiplist.insert(2); assert_eq!(skiplist.back(), Some(&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::OrderedSkipList; let mut skiplist = OrderedSkipList::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 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_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::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_eq!(skiplist.pop_back(), None);
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));
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_eq!(skiplist.remove(&4), None); // No more '4' left
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_eq!(skiplist.remove(&15), 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_eq!(skiplist.remove_first(&4), None); // No more '4' left
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);
fn retain<F>(&mut self, f: F) where
F: FnMut(&T) -> bool,
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);
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();
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); }
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); }
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 skiplist::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: Send> Send for OrderedSkipList<T>
[src]
impl<T: Sync> Sync for OrderedSkipList<T>
[src]
impl<T> Drop for OrderedSkipList<T>
[src]
impl<T: PartialOrd> Default for OrderedSkipList<T>
[src]
fn default() -> OrderedSkipList<T>
Returns the "default value" for a type. Read more
impl<A, B> PartialEq<OrderedSkipList<B>> for OrderedSkipList<A> where
A: PartialEq<B>,
[src]
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 ==
. Read more
fn ne(&self, other: &OrderedSkipList<B>) -> bool
This method tests for !=
.
impl<T> Eq for OrderedSkipList<T> where
T: Eq,
[src]
T: Eq,
impl<A, B> PartialOrd<OrderedSkipList<B>> for OrderedSkipList<A> where
A: PartialOrd<B>,
[src]
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. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<T> Ord for OrderedSkipList<T> where
T: Ord,
[src]
T: Ord,
fn cmp(&self, other: &OrderedSkipList<T>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<T> Extend<T> for OrderedSkipList<T>
[src]
fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I)
Extends a collection with the contents of an iterator. Read more
impl<T> Index<usize> for OrderedSkipList<T>
[src]
type Output = T
The returned type after indexing
fn index(&self, index: usize) -> &T
The method for the indexing (container[index]
) operation
impl<T> Debug for OrderedSkipList<T> where
T: Debug,
[src]
T: Debug,
impl<T> Display for OrderedSkipList<T> where
T: Display,
[src]
T: Display,
impl<T> IntoIterator for OrderedSkipList<T>
[src]
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) -> IntoIter<T>
Creates an iterator from a value. Read more
impl<'a, T> IntoIterator for &'a OrderedSkipList<T>
[src]
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) -> Iter<'a, T>
Creates an iterator from a value. Read more
impl<'a, T> IntoIterator for &'a mut OrderedSkipList<T>
[src]
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) -> Iter<'a, T>
Creates an iterator from a value. Read more
impl<T> FromIterator<T> for OrderedSkipList<T> where
T: PartialOrd,
[src]
T: PartialOrd,
fn from_iter<I>(iter: I) -> OrderedSkipList<T> where
I: IntoIterator<Item = T>,
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more