dcollections.HashMultiset

License:
see license.txt

$(DDOC_MODULE_MEMBERS

class HashMultiset (V,alias ImplTemp = HashDup,alias hashFunction = DefaultHash): Multiset!(V);

A multi-set implementation which uses a Hash to have near O(1) insertion, deletion and lookup time.

Adding an element might invalidate cursors depending on the implementation.

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

(non-function members can be properties unless otherwise specified):

You can replace the Hash implementation with a custom implementation, the Hash 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 get/set properties unless otherwise specified):

parameters -> must be a struct with at least the following members: hashFunction -> the hash function to use (should be a HashFunction!(V))

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

uint count -> count of the elements in the hash

position -> must be a struct/class with the following member: ptr -> must define the following member: value -> the value which is pointed to by this position (cannot be a property) position next -> next position in the hash map position prev -> previous position in the hash map

bool add(V v) -> add the given value to the hash. The hash of the value will be given by hashFunction(v). If the value already exists in the hash, this should call updateFunction(v) and should not increment count.

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

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

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

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

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

uint removeAll(V v) -> remove all instances of the given value, returning how many were removed.

uint countAll(V v) -> returns the number of instances of the given value in the hash.

void copyTo(ref Hash h) -> make a duplicate copy of this hash into the target h.

alias Impl ;

an alias the the implementation template instantiation.

struct cursor ;

A cursor for the hash multiset.

V value ();: get the value at this position
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 all the elements of the multiset, indicating which elements should be removed

Use like this:

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

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

iterate over the collection's values

this();

Instantiate the hash map using the default implementation parameters.

HashMultiset 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 on average in O(1) time.

cursor find (V v);

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

Runs in average O(1) time.

cursor find (cursor it, V v);

find the next cursor that points to a V value.

Returns end if no more instances of v exist in the collection.

bool contains (V v);

Returns true if the given value exists in the collection.

Runs in average O(1) time.

HashMultiset 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.

HashMultiset 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.

HashMultiset add (V v);

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

Runs on average in O(1) time.

HashMultiset add (V v, ref bool wasAdded);

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

Runs on average in O(1) time.

HashMultiset add (Iterator!(V) it);

Adds all the elements from it to the set. Returns the number of elements added.

Runs on average in O(1) + O(m) time, where m is the number of elements in the iterator.

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

Adds all the elements from it to the set. Returns the number of elements added.

Runs on average in O(1) + O(m) time, where m is the number of elements in the iterator.

HashMultiset add (V[] array);

Adds all the elements from the array to the set. Returns the number of elements added.

Runs on average in O(1) * O(m) time, where m is the array length.

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

Adds all the elements from the array to the set. Returns the number of elements added.

Runs on average in O(1) * O(m) time, where m is the array length.

uint count (V v);

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

Runs on average in O(m * 1) time, where m is the number of elements that are v.

HashMultiset removeAll (V v);

Removes all the elements that are equal to v.

Runs on average in O(m * 1) time, where m is the number of elements that are v.

HashMultiset removeAll (V v, ref uint numRemoved);

Removes all the elements that are equal to v.

Runs on average in O(m * 1) time, where m is the number of elements that are v.

HashMultiset dup ();

make a shallow copy of this hash mulitiset.

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.HashMultiset', 'source/', 'html');