extra​::dlist

Structs

DList
DListIterator
MoveIterator
MutDListIterator

Traits

ListInsertion

Struct extra::dlist::DList

pub struct DList<T> {
    priv length: uint,
    priv list_head: Link<T>,
    priv list_tail: Rawlink<Node<T>>,
}

A doubly-linked list.

Methods

impl<T> DList<T>

fn new() -> DList<T>

Create an empty DList

fn rotate_forward(&mut self)

Move the last element to the front of the list.

If the list is empty, do nothing.

fn rotate_backward(&mut self)

Move the first element to the back of the list.

If the list is empty, do nothing.

fn append(&mut self, other: DList<T>)

Add all elements from other to the end of the list

O(1)

fn prepend(&mut self, other: DList<T>)

Add all elements from other to the beginning of the list

O(1)

fn insert_when(&mut self, elt: T, f: &fn(&T, &T) -> bool)

Insert elt before the first x in the list where f(x, elt) is true, or at the end.

O(N)

fn merge(&mut self, other: DList<T>, f: &fn(&T, &T) -> bool)

Merge DList other into this DList, using the function f. Iterate the both DList with a from self and b from other, and put a in the result if f(a, b) is true, else b.

O(max(N, M))

fn iter<'a>(&'a self) -> DListIterator<'a, T>

Provide a forward iterator

fn rev_iter<'a>(&'a self) -> std::iter::Invert

Provide a reverse iterator

fn mut_iter<'a>(&'a mut self) -> MutDListIterator<'a, T>

Provide a forward iterator with mutable references

fn mut_rev_iter<'a>(&'a mut self) -> std::iter::Invert

Provide a reverse iterator with mutable references

fn move_iter(self) -> MoveIterator<T>

Consume the list into an iterator yielding elements by value

fn move_rev_iter(self) -> std::iter::Invert

Consume the list into an iterator yielding elements by value, in reverse

impl<T: std::cmp::Ord> DList<T>

fn insert_ordered(&mut self, elt: T)

Insert elt sorted in ascending order

O(N)

Trait Implementations

impl<T> std::container::Container for DList<T>

fn is_empty(&self) -> bool

O(1)

fn len(&self) -> uint

O(1)

impl<T> std::container::Mutable for DList<T>

fn clear(&mut self)

Remove all elements from the DList

O(N)

impl<T> Deque<T> for DList<T>

fn front<'a>(&'a self) -> std::option::Option

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

fn front_mut<'a>(&'a mut self) -> std::option::Option

Provide a mutable reference to the front element, or None if the list is empty

fn back<'a>(&'a self) -> std::option::Option

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

fn back_mut<'a>(&'a mut self) -> std::option::Option

Provide a mutable reference to the back element, or None if the list is empty

fn push_front(&mut self, elt: T)

Add an element first in the list

O(1)

fn pop_front(&mut self) -> std::option::Option

Remove the first element and return it, or None if the list is empty

O(1)

fn push_back(&mut self, elt: T)

Add an element last in the list

O(1)

fn pop_back(&mut self) -> std::option::Option

Remove the last element and return it, or None if the list is empty

O(1)

impl<T> std::ops::Drop for DList<T>

fn drop(&mut self)

impl<A> std::iter::FromIterator for DList<A>

fn from_iterator<T: std::iter::Iterator>(iterator: &mut T) -> DList<A>

impl<A> std::iter::Extendable for DList<A>

fn extend<T: std::iter::Iterator>(&mut self, iterator: &mut T)

impl<A: std::cmp::Eq> std::cmp::Eq for DList<A>

fn eq(&self, other: &DList<A>) -> bool

fn ne(&self, other: &DList<A>) -> bool

impl<A: std::cmp::Eq + std::cmp::Ord> std::cmp::Ord for DList<A>

fn lt(&self, other: &DList<A>) -> bool

fn le(&self, other: &DList<A>) -> bool

fn gt(&self, other: &DList<A>) -> bool

fn ge(&self, other: &DList<A>) -> bool

impl<A: std::clone::Clone> std::clone::Clone for DList<A>

fn clone(&self) -> DList<A>

impl<S: Encoder, T: Encodable<S>> Encodable<S> for DList<T>

fn encode(&self, s: &mut S)

impl<D: Decoder, T: Decodable<D>> Decodable<D> for DList<T>

fn decode(d: &mut D) -> DList<T>