This is our main way of storing command tokens. The radix tree checks whether it itself has a specific token, in O(l) time, where l is the length of the token specified.
Why did I choose a radix tree?
There are a few alternatives, but I found a radix tree to be the best:
A giant switch statement: consider this, if an object has 7 booleans (aka, just true, false) inside, it would have 128 states. 10 booleans, 1024 states. It will get out of hand very quickly.
A binary tree: it's very hard to visualize with a binary tree, since a prefix can have more than 2 suffixes.
A normal trie: it's memory inefficient. Some nodes should be compressed into one since they all represent 1 string. Although, a normal trie is also easier to implement, so we can consider it.
Implementation
For now, let's do an on-memory, stack-based radix tree. Stack-based because its length can be pre-determined (you don't add/remove nodes during the lifetime of the program), and stack automatically manages memory for you, and stack is faster. (Note, stack-based basically means we represent the tree as an array).
Later on, we can also save the whole array onto disk, and load the thing up when the program starts. This is more beneficial when our radix tree grows larger. But again, this is a later consideration.
Oh well, a stack-based tree is actually harder to visualize compared to a normal heap-based one using malloc and stuff. It would be nice had C got the keyword constexpr from C++.
What
Why did I choose a radix tree?
There are a few alternatives, but I found a radix tree to be the best:
A giant switch statement: consider this, if an object has 7 booleans (aka, just true, false) inside, it would have 128 states. 10 booleans, 1024 states. It will get out of hand very quickly.
A binary tree: it's very hard to visualize with a binary tree, since a prefix can have more than 2 suffixes.
A normal trie: it's memory inefficient. Some nodes should be compressed into one since they all represent 1 string. Although, a normal trie is also easier to implement, so we can consider it.
Implementation
For now, let's do an on-memory, stack-based radix tree. Stack-based because its length can be pre-determined (you don't add/remove nodes during the lifetime of the program), and stack automatically manages memory for you, and stack is faster. (Note, stack-based basically means we represent the tree as an array).
Later on, we can also save the whole array onto disk, and load the thing up when the program starts. This is more beneficial when our radix tree grows larger. But again, this is a later consideration.
Request by: Huy Nguyen