tango.util.container.SortedMap

License:
BSD style:

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

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



Page generated by Ddoc. Copyright (c) 2008 Kris Bell. All rights reserved