digitalmars.D - Is there some fast and nogc capable binary search tree for D?
- solidstate1991 (11/11) Apr 29 2018 Some components of my game engine would benefit from lookup
- 12345swordy (4/17) Apr 29 2018 If the data involved classes then the answer is no, as there is a
- solidstate1991 (4/7) Apr 29 2018 I think I can get around that by storing the data in dynamic
- Neia Neutuladh (2/15) Apr 29 2018 https://github.com/dlang-community/containers/blob/master/src/containers...
- Guillaume Piolat (3/10) Apr 30 2018 There is one in dplug:core, translated from Phobos.
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.
Apr 29 2018
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.
Apr 29 2018
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.
Apr 29 2018
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/sr /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.
Apr 29 2018
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
Apr 30 2018