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 HashMap (K,V,alias Hash = Container.hash,alias Reap = Container.reap,alias Heap = Container.Collect): IContainer!(V);
    • Hash table implementation of a Map 

            Iterator iterator ()
        int opApply (int delegate(ref V value) dg)
        int opApply (int delegate(ref K key, ref V value) dg)

        bool get (K key, ref V element)
        bool keyOf (V value, ref K key)
        bool contains (V element)
        bool containsPair (K key, V element)

        bool removeKey (K key)
        bool take (ref V element)
        bool take (K key, ref V element)
        uint remove (V element, bool all)
        uint remove (IContainer!(V) e, bool all)
        uint replace (V oldElement, V newElement, bool all)
        bool replacePair (K key, V oldElement, V newElement)

        bool add (K key, V element)
        bool opIndexAssign (V element, K key)
        V    opIndex (K key)
        V*   opIn_r (K key)

        uint size ()
        bool isEmpty ()
        V[] toArray (V[] dst)
        HashMap dup ()
        HashMap clear ()
        HashMap reset ()
        uint buckets ()
        float threshold ()
        void buckets (uint cap)
        void threshold (float desired)
        Allocator allocator()


  • this(float f = Container.defaultLoadFactor);
    • Construct a HashMap instance

  • Alloc allocator ();
    • Return the configured allocator

  • Iterator iterator ();
    • Return a generic iterator for contained elements

  • int opApply (int delegate(ref K key, ref V value) dg);


  • int opApply (int delegate(ref V value) dg);


  • uint size ();
    • Return the number of elements contained

  • bool add (K key, V element);
    • Add a new element to the set. Does not add if there is an equivalent already present. Returns true where an element is added, false where it already exists (and was possibly updated).

    Time complexity: O(1) average; O(n) worst.



  • bool add (K key, V element, K(* retain)(K));
    • Add a new element to the set. Does not add if there is an equivalent already present. Returns true where an element is added, false where it already exists (and was possibly updated). This variation invokes the given retain function when the key does not already exist. You would typically use that to duplicate a char[], or whatever is required.

    Time complexity: O(1) average; O(n) worst.



  • bool get (K key, ref V element);
    • Return the element associated with key

    param:
    a key

    param:
    a value reference (where returned value will reside)

    Returns:
    whether the key is contained or not



  • V* opIn_r (K key);
    • Return the element associated with key

    param:
    a key

    Returns:
    a pointer to the located value, or null if not found



  • bool contains (V element);
    • Does this set contain the given element?

    Time complexity: O(1) average; O(n) worst



  • bool keyOf (V value, ref K key);
    • Time complexity: O(n).

  • bool containsKey (K key);
    • Time complexity: O(1) average; O(n) worst.

  • bool containsPair (K key, V element);
    • Time complexity: O(1) average; O(n) worst.

  • HashMap dup ();
    • Make an independent copy of the container. Does not clone elements

    Time complexity: O(n)



  • bool removeKey (K key);
    • Time complexity: O(1) average; O(n) worst.

  • bool replaceKey (K key, K replace);
    • Time complexity: O(1) average; O(n) worst.

  • bool replacePair (K key, V oldElement, V newElement);
    • Time complexity: O(1) average; O(n) worst.

  • bool take (ref V element);
    • Remove and expose the first element. Returns false when no more elements are contained

    Time complexity: O(n)



  • bool take (K key, ref V value);
    • Remove and expose the element associated with key

    param:
    a key

    param:
    a value reference (where returned value will reside)

    Returns:
    whether the key is contained or not

    Time complexity: O(1) average, O(n) worst



  • bool opIndexAssign (V element, K key);
    • Operator shortcut for assignment

  • V opIndex (K key);
    • Operator retreival function

    Throws NoSuchElementException where key is missing



  • uint remove (IContainer!(V) e, bool all = false);
    • Remove a set of values

  • uint remove (V element, bool all = false);
    • Removes element instances, and returns the number of elements removed

    Time complexity: O(1) average; O(n) worst



  • uint replace (V oldElement, V newElement, bool all = false);
    • Replace instances of oldElement with newElement, and returns the number of replacements

    Time complexity: O(n).



  • HashMap clear ();
    • Clears the HashMap contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.

    Time complexity: O(n)



  • HashMap reset ();
    • Reset the HashMap contents. This releases more memory than clear() does

    Time complexity: O(n)



  • uint buckets ();
    • Return the number of buckets

    Time complexity: O(1)



  • void buckets (uint cap);
    • Set the desired number of buckets in the hash table. Any value greater than or equal to one is OK.

    If different than current buckets , causes a version change

    Time complexity: O(n)



  • void buckets (uint cap, float threshold);
    • Set the number of buckets for the given threshold and resize as required

    Time complexity: O(n)



  • float threshold ();
    • Return the current load factor threshold

    The Hash table occasionally checka against the load factor resizes itself if it has gone past it.

    Time complexity: O(1)



  • void threshold (float desired);
    • Set the resize threshold , and resize as required Set the current desired load factor. Any value greater than 0 is OK. The current load is checked against it, possibly causing a resize.

    Time complexity: O(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)



  • HashMap check ();
    • Sanity check

  • uint instances (V element);
    • Count the element instances in the set (there can only be 0 or 1 instances in a Set).

    Time complexity: O(n)



  • HashMap checkLoad ();
    • Check to see if we are past load factor threshold. If so, resize so that we are at half of the desired threshold.

  • void resize (uint newCap);
    • resize table to new capacity, rehashing all elements

  • bool removeNode (Ref node, Ref* list);
    • Remove the indicated node. We need to traverse buckets for this, since we're singly-linked only. Better to save the per-node memory than to gain a little on each remove

    Used by iterators only



  • HashMap clear (bool all);
    • Clears the HashMap contents. Various attributes are retained, such as the internal table itself. Invoke reset() to drop everything.

    Time complexity: O(n)



  • void increment ();
    • new element was added

  • void decrement (Ref p);
    • element was removed

  • void mutate ();
    • set was changed

  • 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

    Copyright (c) 2008 Kris Bell. All rights reserved :: page rendered by CandyDoc