[−][src]Trait nimiq_collections::queue::Queue

pub trait Queue<T> {
    fn is_empty(&self) -> bool;

    fn len(&self) -> usize;

    fn clear(&mut self);

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

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

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

    fn enqueue(&mut self, elt: T);

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

    fn requeue(&mut self, elt: T);
}

A trait describing a queue functionality.

The Queue allows enqueue and dequeue operations.

Required methods

fn is_empty(&self) -> bool

Returns true if the queue is empty.

This operation should compute in O(1) time.

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

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

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

fn len(&self) -> usize

Returns the length of the queue.

This operation should compute in O(1) time.

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

let mut dl = UniqueLinkedList::new();

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

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

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

fn clear(&mut self)

Removes all elements from the queue.

This operation should compute in O(n) time.

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

let mut dl = UniqueLinkedList::new();

dl.enqueue(2);
dl.enqueue(1);
assert_eq!(dl.len(), 2);
assert_eq!(dl.peek(), Some(&2));

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

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

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

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

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

dl.enqueue(1);
assert_eq!(dl.peek(), Some(&1));

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

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

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

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

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

d.enqueue(1);
d.enqueue(3);
assert_eq!(d.dequeue(), Some(1));
assert_eq!(d.dequeue(), Some(3));
assert_eq!(d.dequeue(), None);

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.

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

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

let mut d = UniqueLinkedList::new();
assert_eq!(d.dequeue_multi(1), vec![]);

d.enqueue(1);
d.enqueue(3);
assert_eq!(d.dequeue_multi(0), vec![]);
assert_eq!(d.dequeue_multi(1), vec![1]);
assert_eq!(d.dequeue_multi(2), vec![3]);

fn enqueue(&mut self, elt: T)

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

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

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

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

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

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, Queue};

let mut queue1 = UniqueLinkedList::new();
queue1.enqueue('a');

let mut queue2 = UniqueLinkedList::new();
queue2.enqueue('b');
queue2.enqueue('c');

queue1.append(&mut queue2);

let mut iter = queue1.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!(queue2.is_empty());

fn requeue(&mut self, elt: T)

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

Examples

use nimiq_collections::{UniqueLinkedList, Queue};

let mut d = UniqueLinkedList::new();
d.enqueue(1);
d.enqueue(3);
d.requeue(1);
assert_eq!(d.dequeue(), Some(3));
assert_eq!(*d.peek().unwrap(), 1);
Loading content...

Implementors

impl<T> Queue<T> for LinkedList<T>[src]

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

Loading content...