The associative array that an order was guaranteed for D.

assoc.d

/**
 * The associative array that an order was guaranteed.
 *
 * Whythis library was necessary:
 * D's Associative Array has a (critical) trouble:
 *   int[string] foo = [
 *     "abc"    : 123,
 *     "k"      : 3874,
 *     "abcdef" : 0];
 *  foreach (key, value; foo) {
 *    writeln("[key : value] - ", [key : value]);
 *  }
 * Then, We(at least I) expect naturally, the above codes will output as:
 *  [key : value] - ["abc":123]
 *  [key : value] - ["k":3874]
 *  [key : value] - ["abcdef":0]
 * However, the above codes prints:
 *  [key : value] - ["abc":123]
 *  [key : value] - ["abcdef":0]
 *  [key : value] - ["k":3874]
 *
 * The result means that D's Associative Array doesn't guarantee to keep the order(insert order).
 * This class guarantee to keep the order.
 */

import std.typecons,
       std.array,
       std.conv;

class AssocTupleError : Error {
  this (string msg) {
    super(msg);
  }
}

struct TuplePair(KeyType, ValueType) {
  KeyType   key;
  ValueType value;
}

class AssocTuple(KeyType, ValueType) {
  alias         TupleType = Tuple!(KeyType, ValueType);
  private alias AssocType = ValueType[KeyType];
  private alias AssocPair = TuplePair!(KeyType, ValueType);

  private TupleType[] array;

  this() {}

  this(typeof(this) at) {
    copyCotr(at);
  }

  this(AssocType assoc) {
    foreach (key, value; assoc) {
      this.add(key, value);
    }
  }

  void copyCotr(typeof(this) at) {
    this.array = at.array;
    init;
  }

  protected this(TupleType[] array) {
    this.array = array;
  }

  void add(KeyType key, ValueType value) {
    this.array ~= tuple(key, value);
  }

  @property typeof(this) save() {
    return new typeof(this)(this);
  }

  protected void init() {
    cursor    = 0;
    emptyFlag = false;
  }

  private T[] properties(T, size_t idx)() {
    T[] propertieArray;

    foreach (tup; array) {
      propertieArray ~= tup[idx];
    }

    return propertieArray;
  }

  @property alias keys = properties!(KeyType, 0);
  @property alias values = properties!(ValueType, 1);

  /* Assign Operator Overloadings */
  // ValueType value = AssocTuple!(KeyType, ValueType)[key];
  ValueType opIndex(KeyType key) {
    SearchIndexResult sir = this.getIndex(key);

    if (sir.found) {
      return this.array[sir.index][1];
    } else {
      throw new AssocTupleError("No such a key : " ~ key.to!string);
    }
  }

  // AssocTuple!(KeyType, ValueType)[key] = value;
  void opIndexAssign(ValueType value, KeyType key) {
    SearchIndexResult sir = this.getIndex(key);

    if (sir.found) { // If found that the key already exists, overwrite it.
      this.array[sir.index] = tuple(key, value);
    } else {
      this.add(key, value);
    }
  }

  typeof(this) opBinary(string s)(typeof(this) at) if (s == "~") {
    typeof(this) newAssocTuple = new AssocTuple!(KeyType, ValueType);

    foreach (Tuple!(KeyType, ValueType) t; array) {
      auto pair = AssocPair(t[0], t[1]);
      newAssocTuple.add(pair.key, pair.value);
    }

    foreach (AssocPair pair; at) {
      newAssocTuple.add(pair.key, pair.value);
    }

    return newAssocTuple;
  }

  /* RandomAccessRange(finite) Requirements */

  @property size_t length() {
    return array.length;
  }

  private size_t cursor;
  private bool emptyFlag;

  @property bool empty() {
    if (emptyFlag) {
      emptyFlag = false;
      return true;
    }

    if (cursor == 0) {
      return array.length == 0;
    } else {
      return cursor == array.length;
    }
  }

  private AssocPair getAssocFromCursor(size_t cursor) {
    TupleType tup = array[cursor];
    return AssocPair(tup[0], tup[1]);
  }

  @property AssocPair front() {
    return getAssocFromCursor(cursor);
  }

  @property AssocPair back() {
    return getAssocFromCursor(array.length - 1 - cursor);
  }

  @property void popFront() {
    if (cursor < array.length - 1) {
      cursor++;
    } else {
      cursor = 0;
      emptyFlag = true;
    }
  }

  @property void popBack() {
    if (array.length - 1 - cursor > 0) {
      cursor++;
    } else {
      emptyFlag = true;
      cursor = 0;
    }
  }

  @property override string toString() {
    string[] strs;

    foreach (elem; this) {
      strs ~= elem.key.to!string ~ ":" ~ elem.value.to!string;
    }

    return "[" ~ strs.join(", ") ~ "]";
  }

  /* private functions */
  private struct SearchIndexResult {
    bool   found;
    size_t index;
  }

  bool contains(KeyType key) {
    return getIndex(key).found;
  }

  private SearchIndexResult getIndex(string key) {
    SearchIndexResult ret;

    foreach (i, elem; array) {
      auto tkey = elem[0];

      if (tkey == key) {
        ret.found = true;
        ret.index = i;

        break;
      }
    }

    return ret;
  }
}