dcollections.LinkList

License:
see license.txt

class LinkList (V,alias ImplTemp = LinkHead): List!(V);

This class implements the list interface by using Link nodes. This gives the advantage of O(1) add and removal, but no random access.

Adding elements does not affect any cursor.

Removing elements does not affect any cursor unless the cursor points to a removed element, in which case it is invalidated.

The implementation can be swapped out for another implementation of a doubly linked list. The implementation must be a struct which uses one template argument V with the following members (unless specified, members can be implemented as properties):

parameters -> data type that is passed to setup to help set up the Node. There are no specific requirements for this type.

Node -> data type that represents a Node in the list. This should be a reference type. Each Node must define the following members: V value -> the value held at this Node. Cannot be a property. Node prev -> (get only) the previous Node in the list Node next -> (get only) the next Node in the list

Node end -> (get only) An invalid Node that points just past the last valid Node. end.prev should be the last valid Node. end.next is undefined.

Node begin -> (get only) The first valid Node. begin.prev is undefined.

uint count -> (get only) The number of nodes in the list. This can be calculated in O(n) time to allow for more efficient removal of multiple nodes.

void setup(parameters p) -> set up the list. This is like a constructor.

Node remove(Node n) -> removes the given Node from the list. Returns the next Node in the list.

Node remove(Node first, Node last) -> removes the nodes from first to last, not including last. Returns last. This can run in O(n) time if count is O(1), or O(1) time if count is O(n).

Node insert(Node before, V v) -> add a new Node before the Node 'before', return a pointer to the new Node.

void clear() -> remove all nodes from the list.

void sort(CompareFunction!(V) comp) -> sort the list according to the compare function

alias Impl ;

convenience alias

alias LinkListType ;

convenience alias

struct cursor ;

A cursor for link list

V value ();: get the value pointed to by this cursor
V value (V v);: set the value pointed to by this cursor
cursor opPostInc ();: increment this cursor, returns what the cursor was before incrementing.
cursor opPostDec ();: decrement this cursor, returns what the cursor was before decrementing.
cursor opAddAssign (int inc);: increment the cursor by the given amount.

This is an O(inc) operation! You should only use this operator in the form:

++i;
cursor opSubAssign (int inc);: decrement the cursor by the given amount.

This is an O(inc) operation! You should only use this operator in the form:

--i;
bool opEquals (cursor it);: compare two cursors for equality

this();

Constructor

LinkListType clear ();

Clear the collection of all elements

uint length ();

returns number of elements in the collection

cursor begin ();

returns a cursor to the first element in the collection.

cursor end ();

returns a cursor that points just past the last element in the collection.

cursor remove (cursor it);

remove the element pointed at by the given cursor, returning an cursor that points to the next element in the collection.

Runs in O(1) time.

cursor remove (cursor first, cursor last);

remove the elements pointed at by the given cursor range, returning a cursor that points to the element that last pointed to.

Runs in O(last-first) time.

LinkListType remove (V v);

Removes the first element that has the value v. Returns true if the value was present and was removed.

Runs in O(n) time.

LinkListType remove (V v, ref bool wasRemoved);

Removes the first element that has the value v. Returns true if the value was present and was removed.

Runs in O(n) time.

cursor find (cursor it, V v);

find a given value in the collection starting at a given cursor. This is useful to iterate over all elements that have the same value.

Runs in O(n) time.

cursor find (V v);

find an instance of a value in the collection. Equivalent to find (begin, v);

Runs in O(n) time.

bool contains (V v);

Returns true if the given value exists in the collection.

Runs in O(n) time.

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

iterate over the collection's values

int purge (int delegate(ref bool doRemove, ref V value) dg);

Iterate over the collections values, specifying which ones should be removed

Use like this:

 // remove all odd values
 foreach(ref doPurge, v; &list.purge)
 {
   doPurge = ((v & 1) == 1);
 }

LinkListType add (V v);

Adds an element to the list. Returns true if the element was not already present.

Runs in O(1) time.

LinkListType add (V v, ref bool wasAdded);

Adds an element to the list. Returns true if the element was not already present.

Runs in O(1) time.

LinkListType add (Iterator!(V) coll);

Adds all the values from the given iterator into the list.

Returns this.

LinkListType add (Iterator!(V) coll, ref uint numAdded);

Adds all the values from the given iterator into the list.

Returns the number of elements added.

LinkListType add (V[] array);

Adds all the values from the given array into the list.

Returns the number of elements added.

LinkListType add (V[] array, ref uint numAdded);

Adds all the values from the given array into the list.

Returns the number of elements added.

uint count (V v);

Count the number of occurrences of v

Runs in O(n) time.

LinkListType removeAll (V v);

Remove all the occurrences of v. Returns the number of instances that were removed.

Runs in O(n) time.

LinkListType removeAll (V v, ref uint numRemoved);

Remove all the occurrences of v. Returns the number of instances that were removed.

Runs in O(n) time.

cursor insert (cursor it, V v);

insert an element at the given position. Returns a cursor to the newly inserted element.

cursor prepend (V v);

prepend an element to the first element in the list. Returns an cursor to the newly prepended element.

cursor append (V v);

append an element to the last element in the list. Returns a cursor to the newly appended element.

V back ();

return the last element in the list. Undefined if the list is empty.

V front ();

return the first element in the list. Undefined if the list is empty.

V takeFront ();

remove the first element in the list, and return its value.

Do not call this on an empty list.

V takeBack ();

remove the last element in the list, and return its value Do not call this on an empty list.

LinkListType opCat (List!(V) rhs);

Create a new list with this and the rhs concatenated together

LinkListType opCat (V[] array);

Create a new list with this and the array concatenated together

LinkListType opCat_r (V[] array);

Create a new list with the array and this list concatenated together.

LinkListType opCatAssign (List!(V) rhs);

Append the given list to the end of this list.

LinkListType opCatAssign (V[] array);

Append the given array to the end of this list.

LinkListType dup ();

duplicate the list

int opEquals (Object o);

Compare this list with another list. Returns true if both lists have the same length and all the elements are the same.

If o is null or not a List, return 0.

LinkList sort (int delegate(ref V, ref V) comp);

Sort the linked list according to the given compare function.

Runs in O(n lg(n)) time

Returns this after sorting

LinkList sort (int(* comp)(ref V, ref V));

Sort the linked list according to the given compare function.

Runs in O(n lg(n)) time

Returns this after sorting

LinkList sort ();

Sort the linked list according to the default compare function for V.

Runs in O(n lg(n)) time

Returns this

template sortX (Comparator)

Sort the linked list according to the given compare functor. This is a templatized version, and so can be used with functors, and might be inlined.

LinkList sortX (Comparator comp);: Sort the linked list according to the given compare functor. This is a templatized version, and so can be used with functors, and might be inlined.

anchorFromTitle('dcollections.LinkList', 'source/', 'html');