Making generalized Trie type in D

[Dmitry Olshansky]

Cross-posting from my GSOC list as I think we had a lack of D rox posts 
lately :)

I rarely am surprised by generic code flexibility and power these days.
But once I fleshed out last bits of generalized Trie I was amazed.

In short: it allows something like "make a multistage integer lookup 
table using these x upper bits, these y bits in the middle and those 
last z bits as final offset" as one-liner. Better yet strings and other 
keys are just as easy, and even better it's up to user to allow custom 
ways of getting X bits for any key.
And while I writing this bit-packing is on it's way to get integrated 
thus obtaining ultra-small tables (we can pack even index entries since 
we know how much bits they take exactly).

And last but no least - it's easy to strap Trie on top of some other 
container (say arrays, sets, hashtable etc.).  (currently it doesn't 
play nice with GC-ed objects, I'll fix it later)
Say book catalog that goes by first latter (or two) as Trie stage then 
as final slot uses sorted array. The advantages  of such schemes is that 
re-sorting huge arrays  can get costly, moreover insertion can 
reallocate and that might even run out of memory while duping it. On the 
other hand smaller array keep sorting bounded at acceptable level.

(In fact hashtable is a degenerate case of 1-level Trie on top of e.g. 
List, just not space-optimized and with a weird  index transform).

To give you a taste of this power, consider a simple example - keyword 
recognizer. I'm showing two version first just checks if it's a keyword. 
Second one does catalogs it to specific kind.
(sample material taken from DCT project, thanks goes to Roman Boiko)

enum keywords = [
             "abstract",
             "alias",
             "align",
             //...  all of them, except @ ones
             "__traits"
     ];

//here is bare minumum set type usable for Trie
  struct SmallMap(size_t N, V, K)
     {
         void insert(Tuple!(V, K) t){ _set.insert(t); }

         V opBinaryRight(string op, T)(T key)
             if(op == "in")
         {
             auto idx = map!"a[1]"(_set.items[]).countUntil(key);
             return idx < 0 ? V.init : _set.items[idx][0];
         }
         private:
             SmallSet!(N, Tuple!(V, K)) _set;
     }
//define how we get bits for our index
    size_t useLength(T)(T[] arr)
     {
         return arr.length > 63 ? 0 : arr.length; //need max length, 64 
- 6bits
     }

     template useLastItem(T)
     {
         size_t entity(in T[] arr){ return arr[$-1]; }
         enum bitSize = 8*T.sizeof;
     }
     //... useItemAt is similar


//now the usage:
auto keyTrie = Trie!(SetAsSlot!(SmallSet!(2,string))
                          , string
                          , assumeSize!(6, useLength)
                          , useItemAt!(0, char)
                          , useLastItem!(char)
                         )(keywords);

foreach(key; keywords)
//opIndex gives us a slot, here slot is set so test it with 'in'
         assert( key in keyTrie[key]);


And that's it. Importantly there is not a single bit of hardcoding here:
     - we choose to make Trie of sets by passing SetAsSlot for value 
type (simple Trie may just use say bool)
     - key type is string oviously
     - assumeSize takes a user define functor and "trusts" user that it 
is result indeed fits into X bit wide integer
     - the the table as constructed goes by levels: by length -> by 
first char -> by last char -> <small set>

As you can observe "alias" and "align" do collide after 3 levels passed, 
thus we go for fixed 2-slot sets at the end to resolve it and a few others.
Of course there are better ways to handle level that would prevent this 
"collision" and reduce size, it's just to show how Trie on top of Set 
works. (not to mention all keywords are ASCII alphas, hinting on better 
compression in say 6bits)

And here is how it can work with Maps as slot (the above was mapping to 
booleans in fact):

auto keywordsMap = [
             "abstract" : TokenKind.Abstract,
             "alias" : TokenKind.Alias,
             "align" : TokenKind.Align,
             //... all others, cataloged per their kind
             "__thread" : TokenKind._Thread,
             "__traits" : TokenKind._Traits,
     ];

//now the usage:
auto keyTrie = Trie!(SetAsMap!(SmallMap!(2, TokenKind, string), 
TokenKind, string)
//duplication is because not every Map type Key-Value can be derived (we 
have no standard protocol for AAs)
                          , string
                          , assumeSize!(6, useLength)
                          , useItemAt!(0, char)
                          , useLastItem!(char)
                         )(keywordsMap);

  foreach(k,v; keywordsMap)
         assert((k in keyTrie2[k]) == v);

And the only big change is the data type :

struct SmallMap(size_t N, V, K)
     {
         void insert(Tuple!(V, K) t){ _set.insert(t); }

         V opBinaryRight(string op, T)(T key)
             if(op == "in")
         {
             auto idx = map!"a[1]"(_set.items[]).countUntil(key);
             return idx < 0 ? V.init : _set.items[idx][0];
         }
         private:
             SmallSet!(N, Tuple!(V, K)) _set;
     }


P.S. Sorry that the code for Trie itself isn't presented, but you can 
find the the whole thing in my Phobos fork:
https://github.com/blackwhale/phobos/blob/gsoc-uni/std/uni.d

-- 
Dmitry Olshansky