Some components of my game engine would benefit from lookup trees. I tried to port one from Go, but either I messed up something bit that certain parts of the codes just won't execute for some reason, or the algorithm was poorly documented, and it will only optimize on one end of the binary search tree.

Looked around on dub, couldn't find anything that wouldn't introduce too much new dependencies or that was actually @nogc capable. I would be interested in some preexisting one, or some better documented ones from the web. All I can find is either very basic theory or things that already work well in my implementation, like indexing and insertion without optimization.

On Monday, 30 April 2018 at 02:21:37 UTC, solidstate1991 wrote:
> Some components of my game engine would benefit from lookup trees. I tried to port one from Go, but either I messed up something bit that certain parts of the codes just won't execute for some reason, or the algorithm was poorly documented, and it will only optimize on one end of the binary search tree.
>
> Looked around on dub, couldn't find anything that wouldn't introduce too much new dependencies or that was actually @nogc capable. I would be interested in some preexisting one, or some better documented ones from the web. All I can find is either very basic theory or things that already work well in my implementation, like indexing and insertion without optimization.

If the data involved classes then the answer is no, as there is a bug regarding destroy as it involved external finalized c function. I'm writing a DIP draft that address this.

On Monday, 30 April 2018 at 02:21:37 UTC, solidstate1991 wrote:
> Some components of my game engine would benefit from lookup trees. I tried to port one from Go, but either I messed up something bit that certain parts of the codes just won't execute for some reason, or the algorithm was poorly documented, and it will only optimize on one end of the binary search tree.
>
> Looked around on dub, couldn't find anything that wouldn't introduce too much new dependencies or that was actually @nogc capable. I would be interested in some preexisting one, or some better documented ones from the web. All I can find is either very basic theory or things that already work well in my implementation, like indexing and insertion without optimization.

https://github.com/dlang-community/containers/blob/master/src/containers/ttree.d perhaps? It's only got one transitive dependency, and that's essentially a compatibility shim for people with old versions of D.

On Monday, 30 April 2018 at 02:43:44 UTC, 12345swordy wrote:
>
> If the data involved classes then the answer is no, as there is a bug regarding destroy as it involved external finalized c function. I'm writing a DIP draft that address this.

I think I can get around that by storing the data in dynamic arrays for the while I need them, then use the tree for quicker random access.

On Monday, 30 April 2018 at 02:21:37 UTC, solidstate1991 wrote:
> Looked around on dub, couldn't find anything that wouldn't introduce too much new dependencies or that was actually @nogc capable. I would be interested in some preexisting one, or some better documented ones from the web. All I can find is either very basic theory or things that already work well in my implementation, like indexing and insertion without optimization.

There is one in dplug:core, translated from Phobos.
https://github.com/AuburnSounds/Dplug/blob/master/core/dplug/core/map.d