A set type implemented as an AA wrapper

mark mark at qtrac.eu
Thu Mar 12 08:51:24 UTC 2020

I use sets a lot and since I believe that D's rbtree is O(lg n) 
for add/remove/in and that D's AA is O(1) for these, I want to 
implement a set in terms of an AA.

Below is the code I've got so far. It allows for add and remove. 
However, it has three problems (that I know of):

XXX: I need to use an if on the struct to restrict T to be a type 
that supports toHash and opEquals (i.e., to be a valid AA key)

YYY: The range() method is clearly not good D style but I don't 
know how to support foreach (item; aaset) ...

ZZZ: I can't figure out how to support the in operator.

// XXX how do I write the if to ensure T is a valid AA key that 
// toHash & opEquals?
struct AAset(T) {
     private {
         alias Unit = void[0];
         enum unit = Unit.init;
         Unit[T] set;
     size_t length() const { return set.length; }
     void add(T item) { set[item] = unit; }
     bool remove(T item) { return set.remove(item); }

     // YYY is there a better way so that people can just use
     //  foreach (var; aaset)
     auto range() { return set.byKey; }

     bool opBinaryRight(string op)(T lhs) { // ZZZ doesn't work
         static if (op == "in") return lhs in set;
         else static assert(0, "operator " ~ op ~ " not 
     // TODO union(), intersection(), difference(), 

unittest {
     import std.algorithm: sort;
     import std.array: array;
     import std.range: enumerate;
     import std.stdio: writeln;
     import std.typecons: Tuple;

     alias Pair = Tuple!(int, "count", string, "word");
     auto inputs = [Pair(1, "one"), Pair(2, "two"), Pair(3, 
                    Pair(4, "four"), Pair(4, "two"), Pair(5, 
                    Pair(6, "six")];
     AAset!string words;
     assert(words.length == 0);
     foreach (pair; inputs) {
         assert(words.length == pair.count);
     auto len = words.length;
     assert(words.length == len - 1);
     auto expected = ["five", "four", "six", "three", "two"];
     foreach (i, word; words.range.array.sort.enumerate)
         assert(word == expected[i]);
     assert("Z" !in words);
     assert("three" !in words);

More information about the Digitalmars-d-learn mailing list