Struct token_deque::Deque

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

A deque that supports removing of nodes not in front or back position, but also nodes in front and back position.

Methods

impl<T> Deque<T>

pub fn new() -> Deque<T>

Creates an empty Deque. No allocations are performed until values are added.

Examples

use token_deque::Deque;

let deque: Deque<u32> = Deque::new();

pub fn with_capacity(capacity: usize) -> Deque<T>

Create a new Deque instance with a freelist at least capacity elements deep.

Examples

use token_deque::Deque;

let deque: Deque<u32> = Deque::with_capacity(16);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted into the given Deque. Note: this only expands the size of the underlying Vec. It does not add the reserved elements to the free list.

Examples

use token_deque::Deque;

let mut l: Deque<u32> = Deque::new();
l.reserve(16);

pub fn capacity(&self) -> usize

Returns how many items could be held without resizing the internal vector. Note: this is not necesarily len() + len_freelist().

Examples

use token_deque::Deque;

let d: Deque<u8> = Deque::with_capacity(16);
assert_eq!(16, d.capacity());

pub fn len(&self) -> usize

The number of items in the deque.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

d.push_front(1);
d.push_back(2);
assert_eq!(2, d.len());

d.pop_front();
assert_eq!(1, d.len());

pub fn is_empty(&self) -> bool

True when the deque is empty.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

assert!(d.is_empty());

d.push_front(1);
assert!(!d.is_empty());

pub fn len_freelist(&self) -> usize

The number of entries on the deque's freelist.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

assert_eq!(0, d.len_freelist());

d.push_front(1);
assert_eq!(0, d.len_freelist());

d.pop_front();
assert_eq!(1, d.len_freelist());

d.push_front(2);
assert_eq!(0, d.len_freelist());

pub fn push_front(&mut self, data: T) -> Token

Insert data into the front of the deque.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

assert_eq!(Some(&10), l.get(&tok));
assert_eq!(Some(10), l.remove(&tok));

pub fn push_back(&mut self, data: T) -> Token

Insert data into the back of the deque. Returns a token that can be used to retrieve the data again using get() or remove().

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_back(10);

assert_eq!(Some(&10), l.get(&tok));
assert_eq!(Some(10), l.remove(&tok));

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

Remove the front of the deque and return it. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
l.push_back(10);
l.push_back(20);

assert_eq!(Some(10), l.pop_front());
assert_eq!(Some(20), l.pop_front());
assert_eq!(None, l.pop_front());

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

Remove the back of the deque and return it. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
l.push_front(10);
l.push_front(20);

assert_eq!(Some(10), l.pop_back());
assert_eq!(Some(20), l.pop_back());
assert_eq!(None, l.pop_back());

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

Get the front value of the deque. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_back(10);

assert_eq!(Some(&10), l.get_front());

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

Get the front value of the deque as a mutable reference. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_back(10);

l.get_front_mut().map(|i| *i += 10);

assert_eq!(Some(&20), l.get_front());

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

Get the back of the deque. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

assert_eq!(Some(&10), l.get_back());

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

Get the back of the deque as a mutable reference. If the deque is empty, None is returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

l.get_back_mut().map(|i| *i += 10);

assert_eq!(Some(&20), l.get_back());

pub fn get(&self, token: &Token) -> Option<&T>

Get a reference to the item associated with token. If the item has been removed, then None will be returned.

Examples

A valid token results in Some(&T).

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

assert_eq!(Some(&10), l.get(&tok));

An invalid token results in None.

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

// This removes the 10 we just pushed which invalidates the
// tok returned by push_front.
l.pop_front();

assert_eq!(None, l.get(&tok));

pub fn get_mut(&mut self, token: &Token) -> Option<&mut T>

Get a mutable reference to the item associted with token. If the item has been removed, then None will be returned.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

l.get_mut(&tok).map(|i| *i += 10);

assert_eq!(Some(&20), l.get(&tok));

pub fn remove(&mut self, token: &Token) -> Option<T>

Remove the item associated with the specified token from the deque. If the item has already been removed, None is returned. This consumes the token.

Examples

use token_deque::Deque;

let mut l = Deque::new();
let tok = l.push_front(10);

assert_eq!(Some(10), l.remove(&tok));
assert_eq!(None, l.remove(&tok));

pub fn iter_front(&self) -> IterFront<T>

Create an iterator over the deque starting from the front.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

d.push_back(1);
d.push_back(2);
d.push_back(3);

let v: Vec<&u8> = d.iter_front().collect();
assert_eq!(vec![&1, &2, &3], v);

pub fn drain_front(&mut self) -> DrainFront<T>

A draining iterator starting from the front position. All drained slots are moved onto the free list.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

d.push_back(1);
d.push_back(2);
d.push_back(3);

let v: Vec<u8> = d.drain_front().collect();
assert_eq!(vec![1, 2, 3], v);
assert_eq!(3, d.len_freelist());

pub fn iter_back(&self) -> IterBack<T>

Create an iterator over the deque starting from the back.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

d.push_back(1);
d.push_back(2);
d.push_back(3);

let v: Vec<&u8> = d.iter_back().collect();
assert_eq!(vec![&3, &2, &1], v);

pub fn drain_back(&mut self) -> DrainBack<T>

A draining iterator starting from the back position. All drained slots are moved onto the free list.

Examples

use token_deque::Deque;

let mut d: Deque<u8> = Deque::new();

d.push_back(1);
d.push_back(2);
d.push_back(3);

let v: Vec<u8> = d.drain_back().collect();
assert_eq!(vec![3, 2, 1], v);
assert_eq!(3, d.len_freelist());

Trait Implementations

impl<T> Debug for Deque<T> where
    T: Debug, 

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

Formats the value using the given formatter.

impl<T> Default for Deque<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T> FromIterator<T> for Deque<T>

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

Creates a value from an iterator.