License: see license.txt class TreeMap (K,V,alias ImplTemp = RBTree,alias compareFunc = DefaultCompare): Map!(K,V); Implementation of the Map interface using Red-Black trees. this allows for O(lg(n)) insertion, removal, and lookup times. It also creates a sorted set of keys. K 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)) updateFunction -> the update function to use (should be an UpdateFunction!(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 update function should be called, and the function should return false. 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 element 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. struct element ; the elements that are passed to the tree. Note that if you define a custom update or compare function, it should take element structs, not K or V. int _compareFunction (ref element e, ref element e2); Compare function used internally to compare two keys void _updateFunction (ref element orig, ref element newv); Update function used internally to update the value of a node alias Impl ; convenience alias to the implementation struct cursor ; A cursor for elements in the tree V value (); get the value in this element K key (); get the key in this element V value (V v); set 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 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 tree map using the implementation parameters given. Set members of p to their initializer values in order to use the default values defined by TreeMap. The default compare function performs K's compare. The default update function sets only the V part of the element, and leaves the K part alone. TreeMap 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 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 O(lg(n)) time. bool contains (V v); Returns true if the given value exists in the collection. Runs in O(n) time. TreeMap 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. TreeMap 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. TreeMap removeAt (K key); Removes the element that has the given key. Returns true if the element was present and was removed. Runs in O(lg(n)) time. TreeMap 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 in O(lg(n)) time. TreeMap remove (Iterator!(K) subset); Removes all the elements whose keys are in the subset. returns this. TreeMap remove (Iterator!(K) subset, ref uint numRemoved); Removes all the elements whose keys are in the subset. Sets numRemoved to the number of key/value pairs removed. returns this. TreeMap intersect (Iterator!(K) subset, ref uint numRemoved); removes all elements in the map whose keys are NOT in subset. returns this. TreeMap intersect (Iterator!(K) subset); removes all elements in the map whose keys are NOT in subset. Sets numRemoved to the number of elements removed. returns this. 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 in O(lg(n)) 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 in O(lg(n)) time. TreeMap set (K key, V value); set a key and value pair. If the pair didn't already exist, add it. returns this. TreeMap set (K key, V value, ref bool wasAdded); set a key and value pair. If the pair didn't already exist, add it. wasAdded is set to true if the pair was added. returns this. TreeMap set (KeyedIterator!(K,V) source); set all the elements from the given keyed iterator in the map. Any key that already exists will be overridden. Returns this. TreeMap set (KeyedIterator!(K,V) source, ref uint numAdded); set all the elements from the given keyed iterator in the map. Any key that already exists will be overridden. numAdded is set to the number of key/value pairs that were added. Returns this. bool containsKey (K key); Returns true if the given key is in the collection. Runs in O(lg(n)) time. uint count (V v); Returns the number of elements that contain the value v Runs in O(n) time. TreeMap removeAll (V v); Remove all the elements that contain the value v. Runs in O(n + m lg(n)) time, where m is the number of elements removed. TreeMap removeAll (V v, ref uint numRemoved); Remove all the elements that contain the value v. Runs in O(n + m lg(n)) time, where m is the number of elements removed. TreeMap dup (); Get a duplicate of this tree map int opEquals (Object o); Compare this TreeMap with another Map Returns 0 if o is not a Map object, is null, or the TreeMap 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 TreeMap. TreeMap 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. TreeMap 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. TreeMap remove (K[] subset); Remove all the given keys from the map. return this. TreeMap 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. TreeMap intersect (K[] subset); Remove all the keys that are not in the given array. returns this. TreeMap 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