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>
[src]
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); }
impl<T> SkipList<T> where T: PartialEq
[src]
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>
[src]
impl<T: Sync> Sync for SkipList<T>
[src]
impl<T> Drop for SkipList<T>
[src]
impl<T: PartialOrd> Default for SkipList<T>
[src]
impl<A, B> PartialEq<SkipList<B>> for SkipList<A> where A: PartialEq<B>
[src]
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
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &SkipList<B>) -> bool
This method tests for !=
.
impl<T> Eq for SkipList<T> where T: Eq
[src]
impl<A, B> PartialOrd<SkipList<B>> for SkipList<A> where A: PartialOrd<B>
[src]
fn partial_cmp(&self, other: &SkipList<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 SkipList<T> where T: Ord
[src]
fn cmp(&self, other: &SkipList<T>) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<T> Extend<T> for SkipList<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 SkipList<T>
[src]
type Output = T
The returned type after indexing
fn index(&self, index: usize) -> &T
The method for the indexing (Foo[Bar]
) operation
impl<T> Debug for SkipList<T> where T: Debug
[src]
impl<T> Display for SkipList<T> where T: Display
[src]
impl<T> IntoIterator for SkipList<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 SkipList<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 SkipList<T>
[src]
type Item = &'a mut T
The type of the elements being iterated over.
type IntoIter = IterMut<'a, T>
Which kind of iterator are we turning this into?
fn into_iter(self) -> IterMut<'a, T>
Creates an iterator from a value. Read more
impl<T> FromIterator<T> for SkipList<T> where T: PartialOrd
[src]
fn from_iter<I>(iter: I) -> SkipList<T> where I: IntoIterator<Item=T>
Creates a value from an iterator. Read more
impl<T: Hash> Hash for SkipList<T>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
Feeds this value into the state given, updating the hasher as necessary.
fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher
1.3.0
Feeds a slice of this type into the state provided.