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

$(DDOC_MODULE_MEMBERS

class SortedMap (K,V,alias Reap = Container.reap,alias Heap = Container.Collect): IContainer!(V);

RedBlack trees of (key, value) pairs

        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)
        uint remove (V value, bool all)
        uint remove (IContainer!(V) e, bool all)

        bool add (K key, V value)
        uint 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)

        uint 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, int n);

Special version of constructor needed by dup()

Alloc allocator ();

Return the configured allocator

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

uint 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 (int delegate(ref V value) dg);

int opApply (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)

uint remove (IContainer!(V) e, bool all);

uint remove (V value, bool all = false);

Time complexity: O(n )

uint 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 (char[] msg);

uint 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 (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);

anchorFromTitle('tango.util.container.SortedMap', 'source/', 'html');