tango.util.container.CircularList

License:
BSD style:

Version:
Apr 2008: Initial release

Authors:
Kris

Since:
0.99.7

Based upon Doug Lea's Java collection package

class CircularList(V, alias Reap = Container.reap, alias Heap = Container.DefaultCollect): IContainer!V;
Circular linked list

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

CircularList add (V element)
CircularList addAt (size_t index, V element)
CircularList append (V element)
CircularList prepend (V element)
size_t addAt (size_t index, IContainer!(V) e)
size_t append (IContainer!(V) e)
size_t prepend (IContainer!(V) e)

bool take (ref V v)
bool contains (V element)
V get (size_t index)
size_t first (V element, size_t startingIndex = 0)
size_t last (V element, size_t startingIndex = 0)

V head ()
V tail ()
V head (V element)
V tail (V element)
V removeHead ()
V removeTail ()

bool removeAt (size_t index)
size_t remove (V element, bool all)
size_t removeRange (size_t fromIndex, size_t toIndex)

size_t replace (V oldElement, V newElement, bool all)
bool replaceAt (size_t index, V element)

size_t size ()
bool isEmpty ()
V[] toArray (V[] dst)
CircularList dup ()
CircularList subset (size_t from, size_t length)
CircularList clear ()
CircularList reset ()
CircularList check ()


Examples:
auto list = new CircularList!(int);
list.add(1);
list.add(2);
list.add(3);

int i = 1;
foreach(v; list)
{
    assert(v == i);
    i++;
}

auto iter = list.iterator;
iter.next();
iter.remove();                          // delete the first item

i = 2;
foreach(v; list)
{
    assert(v == i);
    i++;
}

// test insert functionality
iter = list.iterator;
iter.next;
iter.insert(4);

int[] compareto = [2, 4, 3];
i = 0;
foreach(v; list)
{
    assert(v == compareto[i++]);
}


this();
Make an empty list

this(Ref h, size_t c);
Make an configured list

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

CircularList 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

CircularList dup();
Make an independent copy of the list. Elements themselves are not cloned

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

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

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

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

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

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

CircularList subset(size_t from, size_t length);
Time complexity: O(length)

CircularList clear();
Time complexity: O(1)

CircularList reset();
Reset the HashMap contents and optionally configure a new heap manager. This releases more memory than clear() does

Time complexity: O(n)

bool take(ref V v);
Time complexity: O(n)

Takes the last element on the list

CircularList prepend(V element);
Time complexity: O(1)

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

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

CircularList add(V element);
Time complexity: O(1)

CircularList append(V element);
Time complexity: O(1)

V tail(V element);
Time complexity: O(1)

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

CircularList addAt(size_t index, V element);
Time complexity: O(n)

CircularList replaceAt(size_t index, V element);
Time complexity: O(n)

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

size_t remove(V element, bool all);
Time complexity: O(n)

size_t replace(V oldElement, V newElement, bool all);
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(number of elements in e)

size_t addAt(size_t index, IContainer!V e);
Time complexity: O(size() + 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)

CircularList check();


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

void checkIndex(size_t i);


Ref firstCell();
return the first cell, or throw exception if empty

Ref lastCell();
return the last cell, or throw exception if empty

Ref cellAt(size_t index);
return the index'th cell, or throw exception if bad index

CircularList clear(bool all);
Time complexity: O(1)

void increment();
new element was added

void decrement(Ref p);
element was removed

void mutate();
set was changed

struct Iterator;
Iterator with no filtering

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

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

bool remove();
Remove value that was just iterated.

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

Returns:
a copy of this iterator for chaining.

Iterator reverse();
Flip the direction of next() and opApply(), and reset the termination point such that we can do another full traversal.


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