A set type implemented as an AA wrapper

[Simen Kjærås]

On Thursday, 12 March 2020 at 08:51:24 UTC, mark wrote:
> 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)

I'd suggest simply testing if an AA with that key type is valid:

     struct AAset(T) if (is(int[T]))


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

As Ferhat points out, you could use opApply for this. There's 
also the option of implenting the range primitives front, 
popFront() and empty. However, the easiest solution is the one 
you've already chosen, combined with alias this:

     struct AAset(T) if (is(int[T])) {
         // stuffs...
         auto range() { return set.byKey; }
         alias range this;
     }


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

'in' for AAs returns a pointer to the value it finds, or null if 
no item is found. This pointer does not implicitly convert to 
bool when returned from a function, so you need to compare it to 
null:

     bool opBinaryRight(string op)(T lhs) {
         static if (op == "in") return (lhs in set) != null;
         else static assert(0, "operator " ~ op ~ " not 
supported");
     }

I would also suggest using a template specialization instead of 
static if and static assert:

     bool opBinaryRight(string op : "in")(T lhs) {
         return (lhs in set) != null;
     }

--
   Simen