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 (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) [public]
Make an empty tree, using given Comparator for ordering
~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() [@property, final, const]
Return the number of elements contained
SortedMap dup() [@property, final]
Create an independent copy. Does not clone elements
bool contains(V value) [final]
Time complexity: O(log n)
int opApply(scope int delegate(ref V value) dg) [final]
int opApply(scope 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, const]
Is this container empty? Time complexity: O(1)
SortedMap check() [final]