Refactor LOUDS trie by introducing a new API set for traversal

Louds::Node structure is introduced to represent the position in the tree during traversal.  Three basic movements are implemented: 1) go to the first child, 2) go to the next sibling, and 3) go to the parent.  This new design brings a few benefits:
* Intermediate traversal state can be saved (e.g., incremental search can be implemented).
* Similar pieces of code in ExactSearcher, PrefixSearcher and PredictiveSearcher are factored out, so new code looks more concise and intuitive.
* New APIs take StringPiece instead of const char*.

Using the new APIs, LoudsTrie::HasKey is introduced, which is a faster modification of LoudsTrie::ExactSearch to test the existence of key, where one Rank1 operation is saved compared to ExactSearch.  This is nice because HasKey is called more often than before, e.g., from LanguageAwareRewriter.

Also, in LoudsTrie::Reverse, which is renamed to LoudsTrie::RestoreKeyString, one Rank0 operation is eliminated in the loop of key string reconstruction.  Namely, N operations are saved for keys of length N.

Benchmark shows no performance regression.  Also, this is just a code refactoring, no behavior change is intended.


git-svn-id: a6090854-d499-a067-5803-1114d4e51264
6 files changed
tree: c2c9c1e493e1e41255dc6ef93cdf68b8a2b5e382
  1. src/