www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is there some fast and nogc capable binary search tree for D?

reply solidstate1991 <laszloszeremi outlook.com> writes:
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
next sibling parent reply 12345swordy <alexanderheistermann gmail.com> writes:
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
parent solidstate1991 <laszloszeremi outlook.com> writes:
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
prev sibling next sibling parent Neia Neutuladh <dhasenan ikeran.org> writes:
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
prev sibling parent Guillaume Piolat <first.last gmail.com> writes:
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