Struct blist::BList [] [src]

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

A skeleton implementation of a BList, based on the Space-Efficient Linked List described in Open Data Structures.

A BList is a hybrid between an array and a doubly-linked-list. It consists of arrays in a doubly-linked-list. In this way we get many of the nice properties of a LinkedList, but with improved cache properties and less allocations.

A BList's B-factor is analogous to the same factor in a BTree. It guarantees that all nodes contain B-1 and B+1 elements (except the ends). Once a position has been identified to perform an insertion or deletion, it will take amortized O(B) time to perform, with a worst-case cost of O(B^2). Insertion and deletion on either end will always take O(1) time, though (assuming it takes O(1) time to allocate an array of size B).

Methods

impl<T> BList<T>
[src]

Creates a new BList with a reasonable choice for B.

Creates a new BList with the specified B.

impl<T> BList<T>
[src]

Inserts the element at the back of the list.

Inserts the element at the front of the list.

Removes and returns an element off the back of the list. Returns None if empty.

Removes and returns an element off the front of the list. Returns None if empty.

Gets an immutable reference to the first element in the list.

Gets an immutable reference to the last element in the list.

Gets a mutable reference to the first element in the list.

Gets a mutable reference to the last element in the list.

Gets the number of elements in the list.

Returns true if the list contains no elements, or false otherwise.

Drops everything in the list.

Gets a by-reference iterator over the elements in the list.

Gets a by-mutable-reference iterator over the elements in the list.

Gets a by-value iterator over the elements in the list.

Lazily moves the contents of other to the end of self, in the sense that it makes no effort to preserve the node-size lower-bound invariant. This can have negative effects on the effeciency of the resulting list, but is otherwise much faster than a proper invariant-preserving append.

Panics

Panics if the lists have a different value of B.

Trait Implementations

impl<T: Clone> Clone for BList<T>
[src]

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<'a, T> IntoIterator for &'a BList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

impl<'a, T> IntoIterator for &'a mut BList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

impl<T> IntoIterator for BList<T>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

impl<A> FromIterator<A> for BList<A>
[src]

Creates a value from an iterator. Read more

impl<A> Extend<A> for BList<A>
[src]

Extends a collection with the contents of an iterator. Read more

impl<A: PartialEq> PartialEq for BList<A>
[src]

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

This method tests for !=.

impl<A: Eq> Eq for BList<A>
[src]

impl<A: PartialOrd> PartialOrd for BList<A>
[src]

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

impl<A: Ord> Ord for BList<A>
[src]

This method returns an Ordering between self and other. Read more

impl<A: Debug> Debug for BList<A>
[src]

Formats the value using the given formatter.

impl<A: Hash> Hash for BList<A>
[src]

Feeds this value into the given [Hasher]. Read more

Feeds a slice of this type into the given [Hasher]. Read more