dcollections.TreeMultiset

License:
see license.txt

class TreeMultiset (V,alias ImplTemp = RBDupTree,alias compareFunction = DefaultCompare): Multiset!(V);

Implementation of the Multiset interface using Red-Black trees. this allows for O(lg(n)) insertion, removal, and lookup times. It also creates a sorted set of elements. V must be comparable.

Adding an element does not invalidate any cursors.

Removing an element only invalidates the cursors that were pointing at that element.

You can replace the Tree implementation with a custom implementation, the implementation must be a struct template which can be instantiated with a single template argument V, and must implement the following members (non-function members can be properties unless otherwise specified):

parameters -> must be a struct with at least the following members: compareFunction -> the compare function to use (should be a CompareFunction!(V))

void setup(parameters p) -> initializes the tree with the given parameters.

uint count -> count of the elements in the tree

node -> must be a struct/class with the following members: V value -> the value which is pointed to by this position (cannot be a property) node next -> the next node in the tree as defined by the compare function, or end if no other nodes exist. node prev -> the previous node in the tree as defined by the compare function.

bool add(V v) -> add the given value to the tree according to the order defined by the compare function. If the element already exists in the tree, the function should add it after all equivalent elements.

node begin -> must be a node that points to the very first valid element in the tree, or end if no elements exist.

node end -> must be a node that points to just past the very last valid element.

node find(V v) -> returns a node that points to the first element in the tree that contains v, or end if the element doesn't exist.

node remove(node p) -> removes the given element from the tree, returns the next valid element or end if p was last in the tree.

void clear() -> removes all elements from the tree, sets count to 0.

uint countAll(V v) -> returns the number of elements with the given value.

node removeAll(V v) -> removes all the given values from the tree.

alias Impl ;

convenience alias

struct cursor ;

cursor for the tree multiset

V value ();: get the value in this element
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

int purge (int delegate(ref bool doPurge, ref V v) dg);

Iterate through the elements of the collection, specifying which ones should be removed.

Use like this:

 // remove all odd elements
 foreach(ref doPurge, v; &treeMultiset.purge)
 {
   doPurge = ((v % 1) == 1);
 }

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

iterate over the collection's values

this();

Instantiate the tree multiset

TreeMultiset 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(lg(n)) time.

cursor find (V v);

find the first instance of a given value in the collection. Returns end if the value is not present.

Runs in O(lg(n)) time.

bool contains (V v);

Returns true if the given value exists in the collection.

Runs in O(lg(n)) time.

TreeMultiset 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(lg(n)) time.

TreeMultiset 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(lg(n)) time.

TreeMultiset add (V v);

Adds a value to the collection. Returns this.

Runs in O(lg(n)) time.

TreeMultiset add (V v, ref bool wasAdded);

Adds a value to the collection. Sets wasAdded to true if the value was added.

Returns this.

Runs in O(lg(n)) time.

TreeMultiset add (Iterator!(V) it);

Adds all the values from the iterator to the collection.

Runs in O(m lg(n)) time, where m is the number of elements in the iterator.

TreeMultiset add (Iterator!(V) it, ref uint numAdded);

Adds all the values from the iterator to the collection. Sets numAdded to the number of values added from the iterator.

Runs in O(m lg(n)) time, where m is the number of elements in the iterator.

TreeMultiset add (V[] array);

Adds all the values from array to the collection.

Runs in O(m lg(n)) time, where m is the number of elements in array.

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

Adds all the values from array to the collection. Sets numAdded to the number of elements added from the array.

Runs in O(m lg(n)) time, where m is the number of elements in array.

uint count (V v);

Returns the number of elements in the collection that are equal to v.

Runs in O(m lg(n)) time, where m is the number of elements that are v.

TreeMultiset removeAll (V v);

Removes all the elements that are equal to v.

Runs in O(m lg(n)) time, where m is the number of elements that are v.

TreeMultiset removeAll (V v, ref uint numRemoved);

Removes all the elements that are equal to v. Sets numRemoved to the number of elements removed from the multiset.

Runs in O(m lg(n)) time, where m is the number of elements that are v.

TreeMultiset dup ();

duplicate this tree multiset

V get ();

get the most convenient element in the set. This is the element that would be iterated first. Therefore, calling remove( get ()) is guaranteed to be less than an O(n) operation.

V take ();

Remove the most convenient element from the set, and return its value. This is equivalent to remove(get()), except that only one lookup is performed.

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