tango.util.container.SortedMap

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release

Authors:

Kris

Since:

0.99.7

Based upon Doug Lea's Java collection package

class SortedMap(K, V, alias Reap = Container.reap, alias Heap = Container.DefaultCollect) : IContainer!(V) #
RedBlack trees of (key, value) pairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Iterator iterator (bool forward)
Iterator iterator (K key, bool forward)
int opApply (int delegate (ref V value) dg)
int opApply (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) [public] #
Make an empty tree, using given Comparator for ordering
this(Comparator c, size_t n) [private] #
Special version of constructor needed by dup()
~this() #
Clean up when deleted
Iterator iterator(bool forward = true) [final] #
Return a generic iterator for contained elements
Iterator iterator(K key, bool forward) [final] #
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) [final] #
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() [final] #
Return the number of elements contained
SortedMap dup() [final] #
Create an independent copy. Does not clone elements
bool contains(V value) [final] #
Time complexity: O(log n)
int opApply(int delegate (ref V value) dg) [final] #
int opApply(int delegate (ref K key, ref V value) dg) [final] #
SortedMap comparator(Comparator c) [final] #
Use a new Comparator. Causes a reorganization
bool containsKey(K key) [final] #
Time complexity: O(log n)
bool containsPair(K key, V value) [final] #
Time complexity: O(n)
bool get(K key, ref V value) [final] #
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) [final] #
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) [final] #
Time complexity: O(n)
SortedMap clear() [final] #
Time complexity: O(n)
SortedMap reset() [final] #
Reset the SortedMap contents. This releases more memory than clear() does
Time complexity: O(n)
size_t remove(IContainer!(V) e, bool all) [final] #
size_t remove(V value, bool all = false) [final] #
Time complexity: O(n
size_t replace(V oldElement, V newElement, bool all = false) [final] #
Time complexity: O(n)
bool take(ref V v) [final] #
Time complexity: O(log n)
Takes the value associated with the least key.
bool take(K key, ref V value) [final] #
Time complexity: O(log n)
bool add(K key, V value) [final] #
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) [final] #
Time complexity: O(log n)
Returns true if inserted, false where an existing key exists and was updated instead
V opIndex(K key) [final] #
Operator retreival function
Throws NoSuchElementException where key is missing
bool removeKey(K key) [final] #
Time complexity: O(log n)
bool replacePair(K key, V oldElement, V newElement) [final] #
Time complexity: O(log n)
V[] toArray(V[] dst = null) [final] #
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() [final] #
Is this container empty? Time complexity: O(1)
SortedMap check() [final] #
void noSuchElement(char[] msg) [private] #
size_t instances(V value) [private] #
Time complexity: O(log n)
bool add_(K key, V value, bool checkOccurrence) [private, final] #
Returns true where an element is added, false where an existing key is found
SortedMap clear(bool all) [private] #
Time complexity: O(n)
void remove(Ref node) [private] #
Time complexity: O(log n)
void increment() [private] #
new element was added
void decrement(Ref p) [private] #
element was removed
void mutate() [private] #
set was changed
int compareKey(ref K fst, ref K snd) [private, static] #
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) [private, static] #
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 [private] #
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(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) [private, static] #
Ref back(Ref p) [private, static] #