Homepage: https://www.gnu.org/software/emacs
Author: Stefan Monnier
A simple library of radix trees
There are many different options for how to represent radix trees in Elisp. Here I chose a very simple one. A radix-tree can be either: - a node, of the form ((PREFIX . PTREE) . RTREE) where PREFIX is a string meaning that everything that starts with PREFIX is in PTREE, and everything else in RTREE. It also has the property that everything that starts with the first letter of PREFIX but not with that whole PREFIX is not in RTREE (i.e. is not in the tree at all). - anything else is taken as the value to associate with the empty string. So every node is basically an (improper) alist where each mapping applies to a different leading letter. The main downside of this representation is that the lookup operation is slower because each level of the tree is an alist rather than some kind of array, so every level's lookup is O(N) rather than O(1). We could easily solve this by using char-tables instead of alists, but that would make every level take up a lot more memory, and it would make the resulting data structure harder to read (by a human) when printed out.