License: see license.txt class HashMap (K,V,alias ImplTemp = Hash,alias hashFunction = DefaultHash): Map!(K,V); A map 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. 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)) updateFunction -> the update function to use (should be an UpdateFunction!(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. struct element ; used to implement the key/value pair stored in the hash implementation int opEquals (element e); compare 2 elements for equality. Only compares the keys. uint _hashFunction (ref element e); Function to get the hash of an element void _updateFunction (ref element orig, ref element newelem); Function to update an element according to the new element. alias Impl ; convenience alias struct cursor ; A cursor for the hash map. V value (); get the value at this cursor K key (); get the key at this cursor V value (V v); set the value at 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 int purge (int delegate(ref bool doPurge, ref V v) dg); Iterate over the values of the HashMap, telling it which ones to remove. int keypurge (int delegate(ref bool doPurge, ref K k, ref V v) dg); Iterate over the key/value pairs of the HashMap, telling it which ones to remove. int opApply (int delegate(ref K k, ref V v) dg); iterate over the collection's key/value pairs int opApply (int delegate(ref V v) dg); iterate over the collection's values this(); Instantiate the hash map HashMap 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 findValue (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 findValue (V v); find an instance of a value in the collection. Equivalent to findValue (begin, v); Runs in O(n) time. cursor find (K k); find the instance of a key in the collection. Returns end if the key is not present. Runs in average O(1) time. bool contains (V v); Returns true if the given value exists in the collection. Runs in O(n) time. HashMap 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. HashMap 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. HashMap removeAt (K key); Removes the element that has the given key. Returns true if the element was present and was removed. Runs on average in O(1) time. HashMap removeAt (K key, ref bool wasRemoved); Removes the element that has the given key. Returns true if the element was present and was removed. Runs on average in O(1) time. V opIndex (K key); Returns the value that is stored at the element which has the given key. Throws an exception if the key is not in the collection. Runs on average in O(1) time. V opIndexAssign (V value, K key); assign the given value to the element with the given key. If the key does not exist, adds the key and value to the collection. Runs on average in O(1) time. HashMap set (K key, V value); Set a key/value pair. If the key/value pair doesn't already exist, it is added. HashMap set (K key, V value, ref bool wasAdded); Set a key/value pair. If the key/value pair doesn't already exist, it is added, and the wasAdded parameter is set to true. HashMap set (KeyedIterator!(K,V) source); Set all the values from the iterator in the map. If any elements did not previously exist, they are added. HashMap set (KeyedIterator!(K,V) source, ref uint numAdded); Set all the values from the iterator in the map. If any elements did not previously exist, they are added. numAdded is set to the number of elements that were added in this operation. HashMap remove (Iterator!(K) subset); Remove all keys from the map which are in subset. HashMap remove (Iterator!(K) subset, ref uint numRemoved); Remove all keys from the map which are in subset. numRemoved is set to the number of keys that were actually removed. HashMap intersect (Iterator!(K) subset, ref uint numRemoved); This function only keeps elements that are found in subset. bool containsKey (K key); Returns true if the given key is in the collection. Runs on average in O(1) time. uint count (V v); Returns the number of elements that contain the value v Runs in O(n) time. HashMap removeAll (V v); Remove all the elements that contain the value v. Runs in O(n) time. HashMap removeAll (V v, ref uint numRemoved); Remove all the elements that contain the value v. Runs in O(n) time. Iterator!(K) keys (); return an iterator that can be used to read all the keys HashMap dup (); Make a shallow copy of the hash map. int opEquals (Object o); Compare this HashMap with another Map Returns 0 if o is not a Map object, is null, or the HashMap does not contain the same key/value pairs as the given map. Returns 1 if exactly the key/value pairs contained in the given map are in this HashMap. HashMap set (V[K] source); Set all the elements from the given associative array in the map. Any key that already exists will be overridden. returns this. HashMap set (V[K] source, ref uint numAdded); Set all the elements from the given associative array in the map. Any key that already exists will be overridden. sets numAdded to the number of key value pairs that were added. returns this. HashMap remove (K[] subset); Remove all the given keys from the map. return this. HashMap remove (K[] subset, ref uint numRemoved); Remove all the given keys from the map. return this. numRemoved is set to the number of elements removed. HashMap intersect (K[] subset); Remove all the keys that are not in the given array. returns this. HashMap intersect (K[] subset, ref uint numRemoved); Remove all the keys that are not in the given array. sets numRemoved to the number of elements removed. returns this.

(C) 2008 by Steven Schveighoffer. All rights reserved :: page rendered by CandyDoc