Sorting, any angle ?

[iznotek]

hye, first thanks for the speed !!!
I need to reorganize keys by alphabetical order after tree dynamic creation.
Even if i could (and maybe better ?) certainly take care of this during creation ( using insert after deduce position from siblings instead of just [key]), i need also to apply it on parsed files and i would like to learn how easely walk through the tree with modification at each level ? any advice to do it the best possibly ? and maybe add it on the library if relevant ?
thanks

[biojppm]

Thanks!

The tree is ordered by insertion, and this logic is baked in the data structure. Having automated sorting at insertion time is out of question, not least because of the major speed hit of increasing insertion complexity from O(1) to log(N), not to mention all the problems around possible orderings, which would likely force the tree to be a template and increase compile times.

As you correctly identify, the best approach is if the user ensures the tree is sorted at creation.

When the tree is obtained from parsing a file, it will be ordered exactly as in the file. The library has no sorting facilities, though that is something that could be added, based both on (default) lexicographical comparison of keys or (custom) user lambdas for node comparison, having access to all node fields such as key, value, tags, etc.

But for now I can't really get to it. I'd be happy to accept a PR for this.

As a temporary solution to get you going, you could create a second tree (the destination) from the first tree (the source) using a helper sorted structure such as a std::map<csubstr, size_t> for map nodes and std::map<size_t,size_t> for seq nodes (or flat maps, which would have better performance). You would need to iterate the source tree, creating the proper sorter std::map from each container node in the source tree, then iterating the created sorter map to insert into the destination tree. At the end of visiting all the nodes in the source tree, the destination.

The above suggestion is far from optimal optimal but will definitely work. Of course, the best approach would be to implement it in place. But this is maybe tricky to do and requires careful thought.

HTH.