Struct nimiq_collections::unique_linked_list::UniqueLinkedList

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

A doubly-linked list with owned nodes and a unique constraint enforced by a HashMap.

As with the HashMap type, a UniqueLinkedList requires that the elements implement the Eq and Hash traits. This can frequently be achieved by using #[derive(PartialEq, Eq, Hash)]. If you implement these yourself, it is important that the following property holds:

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must be equal.

It is a logic error for an item to be modified in such a way that the item's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the set. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

The UniqueLinkedList allows pushing and popping elements at either end in amortized constant time.

Methods

impl<T> UniqueLinkedList<T> where
    T: Hash + Eq, 

pub fn new() -> Self

Creates an empty UniqueLinkedList.

Examples

use nimiq_collections::UniqueLinkedList;

let list: UniqueLinkedList<u32> = UniqueLinkedList::new();

pub fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the list.

This reuses all the nodes from other and moves them into self. After this operation, other becomes empty.

This operation computes in O(n) time and O(1) memory.

Examples

use nimiq_collections::UniqueLinkedList;

let mut list1 = UniqueLinkedList::new();
list1.push_back('a');

let mut list2 = UniqueLinkedList::new();
list2.push_back('b');
list2.push_back('c');

list1.append(&mut list2);

let mut iter = list1.iter();
assert_eq!(iter.next(), Some(&'a'));
assert_eq!(iter.next(), Some(&'b'));
assert_eq!(iter.next(), Some(&'c'));
assert!(iter.next().is_none());

assert!(list2.is_empty());

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> where
    T: Hash + Eq,  type Item = &'a T;

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

Provides a forward iterator.

Examples

use nimiq_collections::UniqueLinkedList;

let mut list: UniqueLinkedList<u32> = UniqueLinkedList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

let mut iter = list.iter();
assert_eq!(iter.next(), Some(&0));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), None);

pub fn is_empty(&self) -> bool

Returns true if the UniqueLinkedList is empty.

This operation should compute in O(1) time.

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();
assert!(dl.is_empty());

dl.push_front("foo");
assert!(!dl.is_empty());

pub fn len(&self) -> usize

Returns the length of the UniqueLinkedList.

This operation should compute in O(1) time.

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();

dl.push_front(2);
assert_eq!(dl.len(), 1);

dl.push_front(1);
assert_eq!(dl.len(), 2);

dl.push_back(3);
assert_eq!(dl.len(), 3);

pub fn clear(&mut self)

Removes all elements from the UniqueLinkedList.

This operation should compute in O(n) time.

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();

dl.push_front(2);
dl.push_front(1);
assert_eq!(dl.len(), 2);
assert_eq!(dl.front(), Some(&1));

dl.clear();
assert_eq!(dl.len(), 0);
assert_eq!(dl.front(), None);

pub fn contains<Q: ?Sized>(&self, x: &Q) -> bool where
    Rc<T>: Borrow<Q>,
    Q: Hash + Eq, 

Returns true if the UniqueLinkedList contains an element equal to the given value.

Examples

use nimiq_collections::UniqueLinkedList;

let mut list: UniqueLinkedList<u32> = UniqueLinkedList::new();

list.push_back(0);
list.push_back(1);
list.push_back(2);

assert_eq!(list.contains(&0), true);
assert_eq!(list.contains(&10), false);

pub fn remove<Q: ?Sized>(&mut self, x: &Q) -> Option<T> where
    Rc<T>: Borrow<Q>,
    Q: Hash + Eq, 

Removes and returns the element equal to the given value if present, otherwise returns None.

Examples

use nimiq_collections::UniqueLinkedList;

let mut list: UniqueLinkedList<u32> = UniqueLinkedList::new();

list.push_back(0);

assert_eq!(list.remove(&0), Some(0));
assert_eq!(list.remove(&10), None);

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

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

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();
assert_eq!(dl.front(), None);

dl.push_front(1);
assert_eq!(dl.front(), Some(&1));

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

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

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();
assert_eq!(dl.back(), None);

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

pub fn push_front(&mut self, elt: T)

Adds an element first in the list if it is not yet present in the list

This operation should compute in amortized O(1) time.

Examples

use nimiq_collections::UniqueLinkedList;

let mut dl = UniqueLinkedList::new();

dl.push_front(2);
assert_eq!(dl.front().unwrap(), &2);

dl.push_front(1);
assert_eq!(dl.front().unwrap(), &1);

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

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

This operation should compute in amortized O(1) time.

Examples

use nimiq_collections::UniqueLinkedList;

let mut d = UniqueLinkedList::new();
assert_eq!(d.pop_front(), None);

d.push_front(1);
d.push_front(3);
assert_eq!(d.pop_front(), Some(3));
assert_eq!(d.pop_front(), Some(1));
assert_eq!(d.pop_front(), None);

pub fn push_back(&mut self, elt: T)

Appends an element to the back of a list if it is not yet present in the list

Examples

use nimiq_collections::UniqueLinkedList;

let mut d = UniqueLinkedList::new();
d.push_back(1);
d.push_back(3);
assert_eq!(3, *d.back().unwrap());

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

Removes the last element from a list and returns it, or None if it is empty.

Examples

use nimiq_collections::UniqueLinkedList;

let mut d = UniqueLinkedList::new();
assert_eq!(d.pop_back(), None);
d.push_back(1);
d.push_back(3);
assert_eq!(d.pop_back(), Some(3));

Trait Implementations

impl<T> Queue<T> for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn is_empty(&self) -> bool

Returns true if the queue is empty.

fn len(&self) -> usize

Returns the length of the queue.

fn clear(&mut self)

Removes all elements from the queue.

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

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

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

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

fn dequeue_multi(&mut self, n: usize) -> Vec<T>

Removes a given number of elements from the front of the queue and returns them, or None if the queue is empty.

fn enqueue(&mut self, elt: T)

Appends an element to the back of a queue if it is not yet present in the queue.

fn append(&mut self, other: &mut Self)

Moves all elements from other to the end of the queue.

fn requeue(&mut self, elt: T)

Appends an element to the back of a queue and removes equal elements.

impl<T: Send> Send for UniqueLinkedList<T>

impl<T: Sync> Sync for UniqueLinkedList<T>

impl<T> Extend<T> for UniqueLinkedList<T> where
    T: Hash + Eq, 

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

Extends a collection with the contents of an iterator.

impl<'a, T: 'a + Copy> Extend<&'a T> for UniqueLinkedList<T> where
    T: Hash + Eq, 

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

Extends a collection with the contents of an iterator.

impl<T> IntoIterator for UniqueLinkedList<T> where
    T: Hash + Eq, 

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> where
    T: Hash + Eq,  type Item = T;

fn into_iter(self) -> IntoIter<T>

Consumes the list into an iterator yielding elements by value.

impl<'a, T> IntoIterator for &'a UniqueLinkedList<T> where
    T: Hash + Eq, 

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> where
    T: Hash + Eq,  type Item = &'a T;

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

Creates an iterator from a value.

impl<T: Clone> Clone for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Default for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn default() -> Self

Creates an empty UniqueLinkedList<T>.

impl<T: Eq> Eq for UniqueLinkedList<T> where
    T: Hash + Eq, 

impl<T: Ord> Ord for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<UniqueLinkedList<T>> for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn eq(&self, other: &Self) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: PartialOrd> PartialOrd<UniqueLinkedList<T>> for UniqueLinkedList<T> where
    T: Hash + Eq, 

fn partial_cmp(&self, other: &Self) -> 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: Debug> Debug for UniqueLinkedList<T> where
    T: Hash + Eq, 

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

Formats the value using the given formatter.

impl<T: Hash> Hash for UniqueLinkedList<T> where
    T: Hash + Eq, 

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> FromIterator<T> for UniqueLinkedList<T> where
    T: Hash + Eq, 

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

Creates a value from an iterator.