[−][src]Struct skiplist::skiplist::SkipList
SkipList provides a way of storing elements and provides efficient way to access, insert and remove nodes.
Unlike a standard linked list, the skiplist can skip ahead when trying to find a particular index.
Methods
impl<T> SkipList<T>
[src]
pub fn new() -> Self
[src]
Create a new skiplist with the default number of 16 levels.
Examples
use skiplist::SkipList; let mut skiplist: SkipList<i64> = SkipList::new();
pub fn with_capacity(capacity: usize) -> Self
[src]
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);
pub fn clear(&mut self)
[src]
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());
pub fn len(&self) -> usize
[src]
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);
pub fn is_empty(&self) -> bool
[src]
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());
pub fn insert(&mut self, value: T, index: usize)
[src]
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());
pub fn push_front(&mut self, value: T)
[src]
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);
pub fn push_back(&mut self, value: T)
[src]
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);
pub fn front(&self) -> Option<&T>
[src]
Provides a reference to the front element, or None
if the skiplist is
empty.
Examples
use skiplist::SkipList; let mut skiplist = SkipList::new(); assert!(skiplist.front().is_none()); skiplist.push_back(1); skiplist.push_back(2); assert_eq!(skiplist.front(), Some(&1));
pub fn front_mut(&mut self) -> Option<&mut T>
[src]
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!(skiplist.front().is_none()); skiplist.push_back(1); skiplist.push_back(2); assert_eq!(skiplist.front_mut(), Some(&mut 1));
pub fn back(&self) -> Option<&T>
[src]
Provides a reference to the back element, or None
if the skiplist is
empty.
Examples
use skiplist::SkipList; let mut skiplist = SkipList::new(); assert!(skiplist.back().is_none()); skiplist.push_back(1); skiplist.push_back(2); assert_eq!(skiplist.back(), Some(&2));
pub fn back_mut(&mut self) -> Option<&mut T>
[src]
Provides a reference to the back element, or None
if the skiplist is
empty.
Examples
use skiplist::SkipList; let mut skiplist = SkipList::new(); assert!(skiplist.back().is_none()); skiplist.push_back(1); skiplist.push_back(2); assert_eq!(skiplist.back_mut(), Some(&mut 2));
pub fn get(&self, index: usize) -> Option<&T>
[src]
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!(skiplist.get(0).is_none()); skiplist.extend(0..10); assert_eq!(skiplist.get(0), Some(&0)); assert!(skiplist.get(10).is_none());
pub fn get_mut(&mut self, index: usize) -> Option<&mut T>
[src]
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!(skiplist.get_mut(0).is_none()); skiplist.extend(0..10); assert_eq!(skiplist.get_mut(0), Some(&mut 0)); assert!(skiplist.get_mut(10).is_none());
pub fn pop_front(&mut self) -> Option<T>
[src]
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!(skiplist.pop_front().is_none());
pub fn pop_back(&mut self) -> Option<T>
[src]
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!(skiplist.pop_back().is_none());
pub fn remove(&mut self, index: usize) -> T
[src]
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);
pub fn retain<F>(&mut self, f: F) where
F: FnMut(&T) -> bool,
[src]
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);
ⓘImportant traits for IntoIter<T>pub fn into_iter(self) -> IntoIter<T>
[src]
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); }
ⓘImportant traits for Iter<'a, T>pub fn iter(&self) -> Iter<T>
[src]
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); }
ⓘImportant traits for IterMut<'a, T>pub fn iter_mut(&self) -> IterMut<T>
[src]
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); }
ⓘImportant traits for Iter<'a, T>pub fn range(&self, min: Bound<usize>, max: Bound<usize>) -> Iter<T>
[src]
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::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());
ⓘImportant traits for IterMut<'a, T>pub fn range_mut(&mut self, min: Bound<usize>, max: Bound<usize>) -> IterMut<T>
[src]
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
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,
[src]
T: PartialEq,
pub fn contains(&self, value: &T) -> bool
[src]
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));
pub fn dedup(&mut self)
[src]
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> Debug for SkipList<T> where
T: Debug,
[src]
T: Debug,
impl<T: PartialOrd> Default for SkipList<T>
[src]
impl<T> Display for SkipList<T> where
T: Display,
[src]
T: Display,
impl<T> Drop for SkipList<T>
[src]
impl<T> Eq for SkipList<T> where
T: Eq,
[src]
T: Eq,
impl<T> Extend<T> for SkipList<T>
[src]
fn extend<I: IntoIterator<Item = T>>(&mut self, iterable: I)
[src]
impl<T> FromIterator<T> for SkipList<T> where
T: PartialOrd,
[src]
T: PartialOrd,
fn from_iter<I>(iter: I) -> SkipList<T> where
I: IntoIterator<Item = T>,
[src]
I: IntoIterator<Item = T>,
impl<T: Hash> Hash for SkipList<T>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<T> Index<usize> for SkipList<T>
[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?
ⓘImportant traits for IntoIter<T>fn into_iter(self) -> IntoIter<T>
[src]
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?
ⓘImportant traits for Iter<'a, T>fn into_iter(self) -> Iter<'a, T>
[src]
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?
ⓘImportant traits for IterMut<'a, T>fn into_iter(self) -> IterMut<'a, T>
[src]
impl<T> Ord for SkipList<T> where
T: Ord,
[src]
T: Ord,
fn cmp(&self, other: &SkipList<T>) -> Ordering
[src]
#[must_use]
fn max(self, other: Self) -> Self
1.21.0[src]
#[must_use]
fn min(self, other: Self) -> Self
1.21.0[src]
#[must_use]
fn clamp(self, min: Self, max: Self) -> Self
[src]
impl<A, B> PartialEq<SkipList<B>> for SkipList<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.
impl<A, B> PartialOrd<SkipList<B>> for SkipList<A> where
A: PartialOrd<B>,
[src]
A: PartialOrd<B>,
fn partial_cmp(&self, other: &SkipList<B>) -> Option<Ordering>
[src]
#[must_use]
fn lt(&self, other: &Rhs) -> bool
1.0.0[src]
#[must_use]
fn le(&self, other: &Rhs) -> bool
1.0.0[src]
#[must_use]
fn gt(&self, other: &Rhs) -> bool
1.0.0[src]
#[must_use]
fn ge(&self, other: &Rhs) -> bool
1.0.0[src]
impl<T: Send> Send for SkipList<T>
[src]
impl<T: Sync> Sync for SkipList<T>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for SkipList<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> Unpin for SkipList<T>
impl<T> UnwindSafe for SkipList<T> where
T: RefUnwindSafe + UnwindSafe,
T: RefUnwindSafe + UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> ToString for T where
T: Display + ?Sized,
[src]
T: Display + ?Sized,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,