www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Sparse array based on Adaptive Radix Tree implementation

There is my pre alpha implementation of sparse array
based on adaptive radix tree:

It is based on this article

And here is general information about radix tree:

Radix tree uses node with "Radix" children. For this
iplementation Radix == 256(byte capacity). Each byte
of a key for the container corresponds one level of
the tree (tree haight is equal to size of the key).
Also radix tree doesn't store keys of the data
explicitly. A key can be restored on the path to the leaf.

ART uses several optimizations few of wich
currently implemented:
  - Adaptive node size: there are Node4, Node16,
Node48, Node256 with different strategies to store
elements (implemented Node4 and Node256)
  - Collapsing nodes. Nodes with one child does not
explixitly created. Only their keys stored.
  - SIMD optimisations for fast access in nodes
other then Node256. (not implemented)

Also implemented sort of range over each element.

Is the container needed in Phobos?
Aug 21 2015