tango.util.container.LinkedList

License:
BSD style:

Version:
Apr 2008: Initial release

Authors:
Kris

Since:
0.99.7

Based upon Doug Lea's Java collection package

class LinkedList(V, alias Reap = Container.reap, alias Heap = Container.DefaultCollect): IContainer!V;
List of singly-linked values

Iterator iterator ()
int opApply (scope int delegate(ref V value) dg)

V head ()
V tail ()
V head (V value)
V tail (V value)
V removeHead ()
V removeTail ()

bool contains (V value)
size_t first (V value, size_t startingIndex = 0)
size_t last (V value, size_t startingIndex = 0)

LinkedList add (V value)
LinkedList prepend (V value)
size_t prepend (IContainer!(V) e)
LinkedList append (V value)
size_t append (IContainer!(V) e)
LinkedList addAt (size_t index, V value)
size_t addAt (size_t index, IContainer!(V) e)

V get (size_t index)
bool take (ref V v)
size_t remove (V value, bool all)
bool removeAt (size_t index)
size_t removeRange (size_t fromIndex, size_t toIndex)
size_t replace (V oldElement, V newElement, bool all)
bool replaceAt (size_t index, V value)

LinkedList clear ()
LinkedList reset ()

LinkedList subset (size_t from, size_t length = size_t.max)
LinkedList dup ()

size_t size ()
bool isEmpty ()
V[] toArray (V[] dst)
LinkedList sort (Compare!(V) cmp)
LinkedList check ()


this();
Create a new empty list

this(Ref l, size_t c);
Special version of constructor needed by dup

Iterator iterator();
Return a generic iterator for contained elements

LinkedList cache(size_t chunk, size_t count = 0);
Configure the assigned allocator with the size of each allocation block (number of nodes allocated at one time) and the number of nodes to pre-populate the cache with.

Time complexity: O(n)

int opApply(scope int delegate(ref V value) dg);


size_t size();
Return the number of elements contained

LinkedList dup();
Build an independent copy of the list. The elements themselves are not cloned

bool contains(V value);
Time complexity: O(n)

V head();
Time complexity: O(1)

V tail();
Time complexity: O(n)

V get(size_t index);
Time complexity: O(n)

size_t first(V value, size_t startingIndex = 0);
Time complexity: O(n) Returns size_t.max if no element found.

size_t last(V value, size_t startingIndex = 0);
Time complexity: O(n) Returns size_t.max if no element found.

LinkedList subset(size_t from, size_t length = size_t.max);
Time complexity: O(length)

LinkedList clear();
Time complexity: O(n)

LinkedList reset();
Reset the HashMap contents and optionally configure a new heap manager. We cannot guarantee to clean up reconfigured allocators, so be sure to invoke reset() before discarding this class

Time complexity: O(n)

bool take(ref V v);
Takes the first value on the list

Time complexity: O(1)

LinkedList sort(Compare!V cmp);
Uses a merge-sort-based algorithm.

Time complexity: O(n log n)

LinkedList add(V value);
Time complexity: O(1)

LinkedList prepend(V value);
Time complexity: O(1)

size_t remove(V value, bool all = false);
Time complexity: O(n)

size_t replace(V oldElement, V newElement, bool all = false);
Time complexity: O(n)

V head(V value);
Time complexity: O(1)

V removeHead();
Time complexity: O(1)

LinkedList append(V value);
Time complexity: O(n)

V tail(V value);
Time complexity: O(n)

V removeTail();
Time complexity: O(n)

LinkedList addAt(size_t index, V value);
Time complexity: O(n)

LinkedList removeAt(size_t index);
Time complexity: O(n)

LinkedList replaceAt(size_t index, V value);
Time complexity: O(n)

size_t prepend(IContainer!V e);
Time complexity: O(number of elements in e)

size_t append(IContainer!V e);
Time complexity: O(n + number of elements in e)

size_t addAt(size_t index, IContainer!V e);
Time complexity: O(n + number of elements in e)

size_t removeRange(size_t fromIndex, size_t toIndex);
Time complexity: O(n)

V[] toArray(V[] dst = null);
Copy and return the contained set of values in an array, using the optional dst as a recipient (which is resized as necessary).

Returns a slice of dst representing the container values.

Time complexity: O(n)

bool isEmpty();
Is this container empty?

Time complexity: O(1)

LinkedList check();


size_t instances(V value);
Time complexity: O(n)

Ref firstCell();


Ref lastCell();


Ref cellAt(size_t index);


void checkIndex(size_t index);


void splice_(IContainer!V e, Ref hd, Ref tl);
Splice elements of e between hd and tl. If hd is null return new hd

Returns the count of new elements added

LinkedList clear(bool all);
Time complexity: O(n)

void increment();
new element was added

void decrement(Ref p);
element was removed

void mutate();
set was changed

struct Iterator;
List iterator

bool valid();
Did the container change underneath us?

bool next(ref V v);
Accesses the next value, and returns false when there are no further values to traverse

V* next();
Return a pointer to the next value, or null when there are no further values to traverse

void insert(V value);
Insert a new value before the node about to be iterated (or after the node that was just iterated).

bool insertPrior(V value);
Insert a new value before the value that was just iterated.

Returns true if the prior node existed and the insertion worked. False otherwise.

int opApply(scope int delegate(ref V value) dg);
Foreach support

bool remove();
Remove value at the current iterator location


Page generated by Ddoc. Copyright (c) 2008 Kris Bell. All rights reserved