www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - NoDuplicates without using (more) templates

reply Steven Schveighoffer <schveiguy gmail.com> writes:
Adam posted this in beerconf, as an alternative to std.meta.NoDuplicates:

template NoDuplicates(T...) {
         import std.meta;
         string getIndexesCode() {
                 size_t[string] things;
                 foreach(idx, t; T)
                         things[t.mangleof] = idx;
                 string code;
                 foreach(k, v; things) {
                         if(code.length) code ~= ", ";
                         code ~= "T[" ~ cast(char) (v + '0') ~ "]";
                 }
                 return "AliasSeq!(" ~ code ~ ")";
         }
         alias NoDuplicates = mixin(getIndexesCode());
}

Now, this works only on types, because of t.mangleof. So for instance if 
you do 3.manglof, it gives "i", the mangle for int. But I figured out, 
if I combine both the mangleof and stringof, you get something that is 
bound to be unique for each value AND type.

Here's an alternate:

template NoDuplicates(T...)
{
     import std.meta : AliasSeq;

     string getIndexesCode()
     {
         size_t[string] things;
         static foreach (idx, alias t; T)
             things[t.mangleof ~ t.stringof] = idx;
         string code;
         foreach (k, v; things)
         {
             code ~= "/*" ~ k ~ "*/ T[" ~ cast(char)(v + '0') ~ "],";
         }
         return code;
     }

     // pragma(msg, getIndexesCode()); // uncomment to see the keys and 
indexes
     mixin("alias NoDuplicates = AliasSeq!(" ~ getIndexesCode() ~ ");");
}

I tested this a bit, and it works pretty well.

I think the only thing that doesn't work with this is a lambda, which 
__traits(isSame) treats specially. Any other problems with this?

Another way to solve this is just to use CTFE brute force:

template NoDuplicates(T...)
{
     import std.meta : AliasSeq;

     string getIndexesCode()
     {
         string code;
         static foreach(i; 0 .. T.length)
         {{
             bool includeit = true;
             static foreach(j; i + 1 .. T.length)
             	static if(__traits(isSame, T[i], T[j]))
                    includeit = false;
             if(includeit)
                 code ~= "T[" ~ i.stringof ~ "],";
         }}
         return code;
     }

     //pragma(msg, getIndexesCode());
     mixin("alias NoDuplicates = AliasSeq!(" ~ getIndexesCode() ~ ");");
}

I'm not sure which one would perform better. One has better complexity, 
but the other is more correct (you could possibly split out lambdas or 
other problematic things into their own sub-function). But both I think 
might be a step up over the current NoDuplicates, which is horrendously 
complicated.

-Steve
Sep 26
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 9/26/20 11:13 PM, Steven Schveighoffer wrote:


Oops, posted in wrong forum.. sorry.

-Steve
Sep 26