hash-map.dd

Ddoc

$(SPEC_S Associative Arrays,

        $(P Associative arrays have an index that is not necessarily an integer,
        and can be sparsely populated. The index for an associative array
        is called the $(I key), and its type is called the $(I KeyType).
        )

        $(P Associative arrays are declared by placing the $(I KeyType)
        within the [ ] of an array declaration:
        )

---------
int[string] b;    // associative array b of ints that are
                  // indexed by an array of characters.
                  // The $(I KeyType) is string
b["hello"] = 3;   // set value associated with key "hello" to 3
func(b["hello"]); // pass 3 as parameter to func()
---------

        $(P Particular keys in an associative array can be removed with the
        remove function:
        )

---------
b.$(B remove)("hello");
---------

        $(P The $(I InExpression) yields a pointer to the value
        if the key is in the associative array, or $(B null) if not:
        )

---------
int* p;
p = ("hello" $(B in) b);
if (p !is (B null))
        ...
---------

        $(P $(I KeyType)s cannot be functions or voids.
        )

        $(P The element types of an associative array cannot be functions or voids.)

<h3>Using Classes as the KeyType</h3>

        $(P Classes can be used as the $(I KeyType). For this to work,
        the class definition must override the following member functions
        of class $(D Object):)

        $(UL
        $(LI $(D hash_t toHash()))
$(V1    $(LI $(D int opEquals(Object))))
$(V2    $(LI $(D bool opEquals(Object))))
        $(LI $(D int opCmp(Object)))
        )

        $(P $(D hash_t) is an alias to an integral type.)

        $(P Note that the parameter to $(D opCmp) and $(D opEquals) is
        of type
        $(D Object), not the type of the class in which it is defined.)

        $(P For example:)

---
class Foo {
  int a, b;

  hash_t $(B toHash)() { return a + b; }

$(V1    int $(B opEquals)(Object o))$(V2    bool $(B opEquals)(Object o))
  { Foo foo = cast(Foo) o;
    return foo && a == foo.a && b == foo.b;
  }

  int $(B opCmp)(Object o)
  { Foo foo = cast(Foo) o;
    if (!foo)
      return -1;
    if (a == foo.a)
      return b - foo.b;
    return a - foo.a;
  }
}
---

        $(P The implementation may use either $(D opEquals) or $(D opCmp) or
        both. Care should be taken so that the results of
        $(D opEquals) and $(D opCmp) are consistent with each other when
        the class objects are the same or not.)

<h3>Using Structs or Unions as the KeyType</h3>

        $(P If the $(I KeyType) is a struct or union type,
        a default mechanism is used
        to compute the hash and comparisons of it based on the binary
        data within the struct value. A custom mechanism can be used
        by providing the following functions as struct members:
        )

---------
$(V2 const) hash_t $(B toHash)();
$(V1 int $(B opEquals)($(I KeyType)* s);)$(V2 const bool $(B opEquals)(ref const $(I KeyType) s);)
$(V1 int $(B opCmp)($(I KeyType)* s);)$(V2 const int $(B opCmp)(ref const $(I KeyType) s);)
---------

        $(P For example:)

$(V1
---------
import std.string;

struct MyString {
  string str;

  hash_t $(B toHash)()
  { hash_t hash;
    foreach (char c; str)
      hash = (hash * 9) + c;
    return hash;
  }

  bool $(B opEquals)(MyString* s)
  {
    return std.string.cmp(this.str, s.str) == 0;
  }

  int $(B opCmp)(MyString* s)
  {
    return std.string.cmp(this.str, s.str);
  }
}
---------
)
$(V2
---------
import std.string;

struct MyString {
  string str;

  const hash_t $(B toHash)()
  { hash_t hash;
    foreach (char c; str)
      hash = (hash * 9) + c;
    return hash;
  }

  const bool $(B opEquals)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str) == 0;
  }

  const int $(B opCmp)(ref const MyString s)
  {
    return std.string.cmp(this.str, s.str);
  }
}
---------
)


        $(P The implementation may use either $(D opEquals) or $(D opCmp) or
        both. Care should be taken so that the results of
        $(D opEquals) and $(D opCmp) are consistent with each other when
        the struct/union objects are the same or not.)

$(V2
<h3>Runtime Initialization of Immutable AAs</h3>

    $(P Immutable associative arrays are often desirable, but sometimes
        initialization must be done at runtime. This can be achieved with
        a constructor (static constructor depending on scope), 
        a buffer associative array and $(D assumeUnique):)
---------
immutable long[string] aa;

static this()
{
    import std.exception : assumeUnique;
    import std.conv : to;

    long[string] temp; // mutable buffer
    foreach(i; 0 .. 10)
    {
        temp[to!string(i)] = i;
    }

    aa = assumeUnique(temp);
}

unittest
{
    assert(aa["1"] == 1);
    assert(aa["5"] == 5);
    assert(aa["9"] == 9);
}
---------
)

<h3>Properties</h3>

Properties for associative arrays are:

    $(TABLE2 Associative Array Properties,
        $(TR $(TH Property) $(TH Description))

        $(TR
        $(TD $(B .sizeof))
        $(TD Returns the size of the reference to the associative
        array; it is 4 in 32-bit builds and 8 on 64-bit builds.
        )
        )

        $(TR
        $(TD $(B .length))
        $(TD Returns number of values in the associative array.
        Unlike for dynamic arrays, it is read-only.
        )
        )

        $(TR
        $(TD $(B .keys))
        $(TD Returns dynamic array, the elements of which are the keys in
        the associative array.
        )
        )

        $(TR
        $(TD $(B .values))
        $(TD Returns dynamic array, the elements of which are the values in
        the associative array.
        )
        )

        $(TR
        $(TD $(B .rehash))
        $(TD Reorganizes the associative array in place so that lookups
        are more efficient. rehash is effective when, for example,
        the program is done loading up a symbol table and now needs
        fast lookups in it.
        Returns a reference to the reorganized array.
        )
        )

$(V2
        $(TR
        $(TD $(B .byKey()))
        $(TD Returns a delegate suitable for use as an $(I Aggregate) to
        a $(GLINK2 statement, ForeachStatement)
        which will iterate over the keys
        of the associative array.
        )
        )

        $(TR
        $(TD $(B .byValue()))
        $(TD Returns a delegate suitable for use as an $(I Aggregate) to
        a $(GLINK2 statement, ForeachStatement)
        which will iterate over the values
        of the associative array.
        )
        )

        $(TR
        $(TD $(B .get(Key key, lazy Value defaultValue)))
        $(TD Looks up $(I key); if it exists returns corresponding $(I value)
        else evaluates and returns $(I defaultValue).
        )
        )
)
    )

<hr>
<h3>Associative Array Example: word count</h3>

        $(P Let's consider the file is ASCII encoded with LF EOL.
        In general case we should use $(I dchar c) for iteration
        over code points and functions from $(STD_UNI).
        )

---------
import std.file;         // D file I/O
import std.stdio;
import std.$(V1 ctype)$(V2 ascii);

void main (string[] args) {
  ulong totalWords, totalLines, totalChars;
  ulong[string] dictionary;

  writefln("   lines   words   bytes file");
  foreach (arg; args[1 .. $]) // for each argument except the first one
  {
    ulong wordCount, lineCount, charCount;

    $(V1 bool inWord;
    size_t wordStart;

    // read file into input buffer
    auto input = cast(string)std.file.read(arg);

    foreach (i, char c; input)
    {
      if (std.ctype.isdigit(c))
      { // c is a digit (0..9)
      }
      else if (std.ctype.isalpha(c))
      { // c is an ASCII letter (A..Z, a..z)
        if (!inWord)
        {
          wordStart = i;
          inWord = true;
          ++wordCount;
        }
      }
      else if (inWord)
      {
        auto word = input[wordStart .. i];
        ++dictionary[word];   // increment count for word
        inWord = false;
      }
      ++charCount;

      // Let's consider the file has LF EOL.
      if (c == '\n')
        ++lineCount;
    }
    if (inWord)
    {
      auto word = input[wordStart .. $];
      ++dictionary[word];
    }
)$(V2 foreach(line; File(arg).byLine())
    {
      bool inWord;
      size_t wordStart;

      void tryFinishWord(size_t wordEnd)
      {
        if (inWord)
        {
          auto word = line[wordStart .. wordEnd];
          ++dictionary[word.idup];   // increment count for word
          inWord = false;
        }
      }

      foreach (i, char c; line)
      {
        if (std.ascii.isDigit(c))
        { // c is a digit (0..9)
        }
        else if (std.ascii.isAlpha(c))
        { // c is an ASCII letter (A..Z, a..z)
          if (!inWord)
          {
            wordStart = i;
            inWord = true;
            ++wordCount;
          }
        }
        else
          tryFinishWord(i);
        ++charCount;
      }
      tryFinishWord(line.length);
      ++lineCount;
    }
)
    writefln("%8s%8s%8s %s", lineCount, wordCount, charCount, arg);
    totalWords += wordCount;
    totalLines += lineCount;
    totalChars += charCount;
  }

  if (args.length > 2)
  {
    writefln("-------------------------------------\n%8s%8s%8s total",
            totalLines, totalWords, totalChars);
  }

  write$(V1 f)ln("-------------------------------------");
  foreach (word; dictionary.keys.sort)
  {
    writefln("%3s %s", dictionary[word], word);
  }
}
---------

)

Macros:
        TITLE=Associative Arrays
        WIKI=AssociativeArrays
        DOLLAR=$
        STD_UNI=<a href="phobos/std_uni.html">std.uni</a>
        FOO=
        CATEGORY_SPEC=$0