RedBlack trees of (key, value) pairs
Iterator iterator (bool forward)
Iterator iterator (K key, bool forward)
int opApply (scope int delegate (ref V value) dg)
int opApply (scope int delegate (ref K key, ref V value) dg)
bool contains (V value)
bool containsKey (K key)
bool containsPair (K key, V value)
bool keyOf (V value, ref K key)
bool get (K key, ref V value)
bool take (ref V v)
bool take (K key, ref V v)
bool removeKey (K key)
size_t remove (V value, bool all)
size_t remove (IContainer!(V) e, bool all)
bool add (K key, V value)
size_t replace (V oldElement, V newElement, bool all)
bool replacePair (K key, V oldElement, V newElement)
bool opIndexAssign (V element, K key)
K nearbyKey (K key, bool greater)
V opIndex (K key)
V* opIn_r (K key)
size_t size ()
bool isEmpty ()
V[] toArray (V[] dst)
SortedMap dup ()
SortedMap clear ()
SortedMap reset ()
SortedMap comparator (Comparator c)
- this(Comparator c = null);
- Make an empty tree, using given Comparator for ordering
- this(Comparator c, size_t n);
- Special version of constructor needed by dup()
- Iterator iterator(bool forward = true);
- Return a generic iterator for contained elements
- Iterator iterator(K key, bool forward);
- Return an iterator which return all elements matching
or greater/lesser than the key in argument. The second
argument dictates traversal direction.
Return a generic iterator for contained elements
- SortedMap cache(size_t chunk, size_t count = 0);
- Configure the assigned allocator with the size of each
allocation block (number of nodes allocated at one time)
and the number of nodes to pre-populate the cache with.
Time complexity: O(n)
- size_t size();
- Return the number of elements contained
- SortedMap dup();
- Create an independent copy. Does not clone elements
- bool contains(V value);
- Time complexity: O(log n)
- int opApply(scope int delegate(ref V value) dg);
- int opApply(scope int delegate(ref K key, ref V value) dg);
- SortedMap comparator(Comparator c);
- Use a new Comparator. Causes a reorganization
- bool containsKey(K key);
- Time complexity: O(log n)
- bool containsPair(K key, V value);
- Time complexity: O(n)
- bool get(K key, ref V value);
- Return the value associated with Key key.
param:
key a key
Returns:
whether the key is contained or not
- K nearbyKey(K key, bool after);
- Return the value of the key exactly matching the provided
key or, if none, the key just after/before it based on the
setting of the second argument
param:
key a key
param:
after indicates whether to look beyond or before
the given key, where there is no exact match
Throws:
NoSuchElementException if none found
Returns:
a pointer to the value, or null if not present
- K firstKey();
- Return the first key of the map
Throws:
NoSuchElementException where the map is empty
- K lastKey();
- Return the last key of the map
Throws:
NoSuchElementException where the map is empty
- V* opIn_r(K key);
- Return the value associated with Key key.
param:
key a key
Returns:
a pointer to the value, or null if not present
- bool keyOf(V value, ref K key);
- Time complexity: O(n)
- SortedMap clear();
- Time complexity: O(n)
- SortedMap reset();
- Reset the SortedMap contents. This releases more memory
than clear() does
Time complexity: O(n)
- size_t remove(IContainer!V e, bool all);
- size_t remove(V value, bool all = false);
- Time complexity: O(n
- size_t replace(V oldElement, V newElement, bool all = false);
- Time complexity: O(n)
- bool take(ref V v);
- Time complexity: O(log n)
Takes the value associated with the least key.
- bool take(K key, ref V value);
- Time complexity: O(log n)
- bool add(K key, V value);
- Time complexity: O(log n)
Returns true if inserted, false where an existing key
exists and was updated instead
- bool opIndexAssign(V element, K key);
- Time complexity: O(log n)
Returns true if inserted, false where an existing key
exists and was updated instead
- V opIndex(K key);
- Operator retreival function
Throws NoSuchElementException where key is missing
- bool removeKey(K key);
- Time complexity: O(log n)
- bool replacePair(K key, V oldElement, V newElement);
- Time complexity: O(log n)
- V[] toArray(V[] dst = null);
- Copy and return the contained set of values in an array,
using the optional dst as a recipient (which is resized
as necessary).
Returns a slice of dst representing the container values.
Time complexity: O(n)
- bool isEmpty();
- Is this container empty?
Time complexity: O(1)
- SortedMap check();
- void noSuchElement(immutable(char)[] msg);
- size_t instances(V value);
- Time complexity: O(log n)
- bool add_(K key, V value, bool checkOccurrence);
- Returns true where an element is added, false where an
existing key is found
- SortedMap clear(bool all);
- Time complexity: O(n)
- void remove(Ref node);
- Time complexity: O(log n)
- void increment();
- new element was added
- void decrement(Ref p);
- element was removed
- void mutate();
- set was changed
- int compareKey(ref K fst, ref K snd);
- The default key comparator
@param fst first argument
@param snd second argument
Returns:
a negative number if fst is less than snd; a
positive number if fst is greater than snd; else 0
- int compareElem(ref V fst, ref V snd);
- The default value comparator
@param fst first argument
@param snd second argument
Returns:
a negative number if fst is less than snd; a
positive number if fst is greater than snd; else 0
- struct Iterator;
- Iterator with no filtering
- bool valid();
- Did the container change underneath us?
- bool next(ref K k, ref V v);
- Accesses the next value, and returns false when
there are no further values to traverse
- V* next(ref K k);
- Return a pointer to the next value, or null when
there are no further values to traverse
- int opApply(scope int delegate(ref K key, ref V value) dg);
- Foreach support
- bool remove();
- Remove value at the current iterator location
- Iterator reverse();
- Ref fore(Ref p);
- Ref back(Ref p);