Lazy range of hashes?

[Artur Skawina]

On 08/26/12 00:35, Andrej Mitrovic wrote:
> I could use something like this:
> 
> void main()
> {
>     int[string] x = ["foo":1];
>     int[string] y = ["bar":1];
>     assert("bar" in lazyHash(x, y));
> }
> 
> Essentially it would turn into lazy 'in' checks, meaning first opIn_r
> would be called for 'x', and then for 'y'.
> 
> Otherwise it might be expensive to have to create a new hash that has
> all the keys and values of other hashes. Has anyone ever implemented
> this?

By now - yes. ;)

Being able to use several overlayed mappings can be useful; the HashUnion
type below will let you merge several AAs and access them as just one
one associative array. Well, mostly; there are some quirks/features to
be aware of.

Updates will be done in-place, IOW 'aa[42]=2' will update the first found
'internal' entry with a key==42. If such a key isn't found in any mapping
then an entry will be inserted into the first (top) AA.

'remove' will remove the first matching entry - and _only_ the first one.
So if you have several overlayed AAs containing the same key, a 'remove'
will make the next one visible. (seemed more useful that way, and is more
efficient when there are no conflicting entries; looping until all keys
are really gone is trivial to implement when actually needed) 

I didn't bother to make '.keys' and '.values' lazy; not sure if the extra
complexity would be worth it.

Nesting the HashUnions is possible, which allows for interesting things, but
keep in mind that the result is then not just a simple stack of AAs.

artur

   static struct HashUnion(MAPS...) {
      MAPS mappings;

      alias typeof(mappings[0].keys[0]) IDX;
      alias typeof(mappings[0].values[0]) VAL;

      auto opBinaryRight(string op:"in")(const scope IDX idx) inout {
         foreach (aa; mappings)
            if (auto p = idx in aa)
               return p;
         return null;
      }
      // Compiler needs a non-inout clone of the above opBinaryRight:
      auto opBinaryRight(string op:"in")(const scope IDX idx) {
         foreach (aa; mappings)
            if (auto p = idx in aa)
               return p;
         return null;
      }

      auto opIndex(const scope IDX idx) inout {
         if (auto p = idx in this)
            return *p;
         else
            return mappings[$-1][idx]; // Trigger (runtime) error.
      }
      auto get(const scope IDX idx, lazy VAL missing) inout {
         if (auto p = idx in this)
            return *p;
         else
            return missing;
      }

      auto opIndexAssign(VAL a, const scope IDX idx) {
         if (auto p = idx in this)
            return *p = a;
         else
            return mappings[0][idx] = a;
      }
      auto remove(IDX idx) {
         foreach (aa; mappings)
            if (auto p = idx in aa)
               return aa.remove(idx); // Only removes first occurence.
         //return false; // Missing idx is not an error.
      }

      @property length() const {
         size_t result;
         foreach (aa; mappings)
            result += aa.length;
         return result;
      }
      @property keys() { // Could be made lazy using an ArrayUnion.
         auto result = mappings[0].keys;
         foreach (aa; mappings[1..$])
            result ~= aa.keys;
         return result;
      }
      @property values() { // Could be made lazy using an ArrayUnion.
         auto result = mappings[0].values;
         foreach (aa; mappings[1..$])
            result ~= aa.values;
         return result;
      }
      @property ref rehash() {
         foreach (i, aa; mappings)
            mappings[i] = aa.rehash;
         return this;
      }

      int opApply(scope int delegate(ref IDX, ref VAL) dg) {
         foreach (aa; mappings)
            foreach (IDX i, VAL v; aa)
               if (int result = dg(i, v))
                  return result;
         return 0;
      }
      int opApply(scope int delegate(ref VAL) dg) {
         foreach (aa; mappings)
            foreach (VAL v; aa)
               if (int result = dg(v))
                  return result;
         return 0;
      }

      int _byKey(scope int delegate(ref IDX) dg) {
         foreach (aa; mappings)
            foreach (IDX i; aa.byKey())
               if (int result = dg(i))
                  return result;
         return 0;
      }
      auto byKey() { return &_byKey; }
      int _byValue(scope int delegate(ref VAL) dg) {
         foreach (aa; mappings)
            foreach (VAL v; aa.byValue())
               if (int result = dg(v))
                  return result;
         return 0;
      }
      auto byValue() { return &_byValue; }
   }

   auto hashUnion(MAPS...)(MAPS mappings) { return HashUnion!MAPS(mappings); }

   void main() {
      auto x = ["foo":1];
      auto y = ["bar":2];
      auto z = ["zzz":3, "yyy":4];

      assert("bar" in hashUnion(x, y));
      assert("zzz" !in hashUnion(x, y));

      assert("zzz" in hashUnion(x, y, z));
      assert("zzz" in hashUnion(hashUnion(x, y), z));
      assert(*("zzz" in hashUnion(hashUnion(x, y), z)) == 3);
      assert(hashUnion(hashUnion(x, y), z)["zzz"]==3);

      auto u = hashUnion(hashUnion(x, y), z);
      assert(u["foo"]+u["bar"]+u["zzz"]==6);

      assert(u.length==4);

      import std.stdio;
      writeln(u);

      writeln(u.keys);
      writeln(u.values);

      assert(u.get("def", 666)==666);

      foreach (string i, int v; u)
         writef(" %s: %s", i, v);
      writeln();
      foreach (int v; u)
         writef(" %s", v);
      writeln();

      u["yyy"] = 42;
      foreach (string i, int v; u)
         writef(" %s: %s", i, v);
      writeln();

      u["new"] = 13;
      foreach (string i, int v; u)
         writef(" %s: %s", i, v);
      writef("\n%s\n", u);

      u.remove("yyy");
      writeln(u);

      u["one"] = 1; u["two"] = 2; u["three"] = 3;
      writeln(u);

      foreach (string i; u.byKey())
         writef(" %6s: ??", i);
      writeln();
      foreach (int v; u.byValue())
         writef("       : %2s", v);
      writeln();

      auto decapitated = hashUnion(u.mappings[1..$]);
      writeln(decapitated);
   }