Making generalized Trie type in D

Dmitry Olshansky dmitry.olsh at gmail.com
Sun Jun 24 04:18:58 PDT 2012


On 24-Jun-12 14:50, Roman D. Boiko wrote:
> On Monday, 11 June 2012 at 18:42:14 UTC, Dmitry Olshansky wrote:
>> 0 ^ 0 = 1 while T.init P^ T.init == T.init :)
>> other are almot the same but
>> 1 ^ 1 = 0 while x P^ y == y
>> So it's not symmetric when x,y != T.init for starters ;)
>
> Just a remark that DCT no longer needs tries to be immutable, since I
> decided not to backtrack which strings affect which syntax elements.
> OTOH, it is important to be able to do updates and reads at any time
> (intermixed).
>
> Another note is that XOR makes sense only if you plan to do reverse
> transforms, or expect to pack diffs (if they will be sparse). Otherwise
> it would be more efficient to store new values directly.

Storing new values directly is no easy trick as you need crawl page 
tables all the way up to see if this value corresponds to multiple 
indexes. Well something similar happens with diff trie anyway.

But diffs are indeed very sparse, and the trie itself usually also sparse.
-- 
Dmitry Olshansky




More information about the Digitalmars-d mailing list