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.
BUG=none
TEST=unittest,benchmark
git-svn-id: https://mozc.googlecode.com/svn/trunk@524 a6090854-d499-a067-5803-1114d4e51264
diff --git a/src/dictionary/system/system_dictionary.cc b/src/dictionary/system/system_dictionary.cc
index 1343b0b..9f1c415 100644
--- a/src/dictionary/system/system_dictionary.cc
+++ b/src/dictionary/system/system_dictionary.cc
@@ -296,11 +296,8 @@
void LookupValue(int id, string *value) const {
char buffer[LoudsTrie::kMaxDepth + 1];
- const char *encoded_value = value_trie_->Reverse(id, buffer);
- const size_t encoded_value_len =
- LoudsTrie::kMaxDepth - (encoded_value - buffer);
- DCHECK_EQ(encoded_value_len, strlen(encoded_value));
- codec_->DecodeValue(StringPiece(encoded_value, encoded_value_len), value);
+ const StringPiece encoded_value = value_trie_->RestoreKeyString(id, buffer);
+ codec_->DecodeValue(encoded_value, value);
}
const SystemDictionaryCodecInterface *codec_;
@@ -660,13 +657,13 @@
bool SystemDictionary::HasKey(StringPiece key) const {
string encoded_key;
codec_->EncodeKey(key, &encoded_key);
- return (key_trie_->ExactSearch(encoded_key) != -1);
+ return key_trie_->HasKey(encoded_key);
}
bool SystemDictionary::HasValue(StringPiece value) const {
string encoded_value;
codec_->EncodeValue(value, &encoded_value);
- if (value_trie_->ExactSearch(encoded_value) != -1) {
+ if (value_trie_->HasKey(encoded_value)) {
return true;
}
@@ -894,7 +891,7 @@
const KeyExpansionTable &table =
use_kana_modifier_insensitive_lookup ?
hiragana_expansion_table_ : KeyExpansionTable::GetDefaultInstance();
- key_trie_->PredictiveSearchWithKeyExpansion(lookup_key_str.c_str(), table,
+ key_trie_->PredictiveSearchWithKeyExpansion(lookup_key_str, table,
&collector);
string decoded_key, actual_key;
@@ -1060,7 +1057,7 @@
const KeyExpansionTable &table = use_kana_modifier_insensitive_lookup ?
hiragana_expansion_table_ : KeyExpansionTable::GetDefaultInstance();
key_trie_->PrefixSearchWithKeyExpansion(
- original_encoded_key.c_str(), table, &traverser);
+ original_encoded_key, table, &traverser);
}
void SystemDictionary::LookupExact(StringPiece key, Callback *callback) const {
@@ -1158,7 +1155,7 @@
const StringPiece suffix(str, pos);
string lookup_key;
codec_->EncodeValue(suffix, &lookup_key);
- value_trie_->PrefixSearch(lookup_key.c_str(), &id_collector);
+ value_trie_->PrefixSearch(lookup_key, &id_collector);
pos += Util::OneCharLen(suffix.data());
}
// Collect tokens for all IDs.
@@ -1237,7 +1234,7 @@
T13nPrefixTraverser traverser(token_array_.get(), value_trie_.get(), codec_,
frequent_pos_, original_encoded_key, callback);
key_trie_->PrefixSearchWithKeyExpansion(
- original_encoded_key.c_str(), KeyExpansionTable::GetDefaultInstance(),
+ original_encoded_key, KeyExpansionTable::GetDefaultInstance(),
&traverser);
}
@@ -1248,7 +1245,7 @@
codec_->EncodeValue(value, &lookup_key);
IdCollector id_collector;
- value_trie_->PrefixSearch(lookup_key.c_str(), &id_collector);
+ value_trie_->PrefixSearch(lookup_key, &id_collector);
const set<int> &id_set = id_collector.id_set();
const bool has_cache = (allocator != NULL &&
@@ -1313,13 +1310,10 @@
++result_itr) {
const ReverseLookupResult &reverse_result = result_itr->second;
- const char *encoded_key =
- key_trie_->Reverse(reverse_result.id_in_key_trie, buffer);
- const size_t encoded_key_len =
- LoudsTrie::kMaxDepth - (encoded_key - buffer);
- DCHECK_EQ(encoded_key_len, strlen(encoded_key));
+ const StringPiece encoded_key =
+ key_trie_->RestoreKeyString(reverse_result.id_in_key_trie, buffer);
string tokens_key;
- codec_->DecodeKey(StringPiece(encoded_key, encoded_key_len), &tokens_key);
+ codec_->DecodeKey(encoded_key, &tokens_key);
if (callback->OnKey(tokens_key) !=
SystemDictionary::Callback::TRAVERSE_CONTINUE) {
continue;
diff --git a/src/mozc_version_template.txt b/src/mozc_version_template.txt
index 09cb1d1..447058a 100644
--- a/src/mozc_version_template.txt
+++ b/src/mozc_version_template.txt
@@ -1,6 +1,6 @@
MAJOR=2
MINOR=16
-BUILD=2040
+BUILD=2041
REVISION=102
# NACL_DICTIONARY_VERSION is the target version of the system dictionary to be
# downloaded by NaCl Mozc.
diff --git a/src/storage/louds/louds.h b/src/storage/louds/louds.h
index cd3369b..74c8d9e 100644
--- a/src/storage/louds/louds.h
+++ b/src/storage/louds/louds.h
@@ -37,74 +37,115 @@
namespace storage {
namespace louds {
-// Implementation of the LOUDS (Level-Ordered Unary degree sequence).
-// LOUDS is a representation of tree by bit sequence, which supports "rank"
-// and "select" operations.
-// The representation of each node is "n 1-bits, followed by a 0-bit," where
-// n is the number of its children.
-// So, for example, if a node has two children, the erepresentation of
-// the node is "110". Another example is that a leaf is represented by "0".
-// The nodes are stored in breadth first order, and each node has its id
-// (0-origin, i.e. the root node is '0', the first child of the root is '1'
-// and so on).
-// This class provides some utilities between the "index of the bit array
-// representation" and "node id of the tree".
-// In this representation, we can think that each '1'-bit is corresponding
-// to an edge.
+// Implementation of the Level-Ordered Unary Degree Sequence (LOUDS).
+//
+// LOUDS represents a tree structure using a bit sequence. A node having N
+// children is represented by N 1's and one trailing 0. For example, "110"
+// represents a node with 2 children, while "0" represents a leaf. The bit
+// sequence starts with the representation of super-root, "10", and is followed
+// by representations of nodes in order of breadth first manner; see the
+// following example:
+//
+// 0 (super root)
+// |
+// 1 (root)
+// / \ .
+// 2 3
+// / \ .
+// 4 5
+//
+// Node: 0 1 2 3 4 5
+// LOUDS: 10 110 0 110 0 0
+//
+// This class provides basic APIs to traverse a tree structure.
class Louds {
public:
- Louds() {
- }
+ // Represents and stores location (tree node) for tree traversal. By storing
+ // instances of this class, traversal state can be restored. This class is
+ // copy-efficient.
+ class Node {
+ public:
+ // Default instance represents the root node (not the super-root).
+ Node() : edge_index_(0), node_id_(1) {}
+ Node(const Node &n) : edge_index_(n.edge_index_), node_id_(n.node_id_) {}
- void Open(const uint8 *image, int length) {
+ int node_id() const { return node_id_; }
+
+ friend bool operator==(const Node &x, const Node &y) {
+ return x.edge_index_ == y.edge_index_ && x.node_id_ == y.node_id_;
+ }
+
+ private:
+ int edge_index_;
+ int node_id_;
+ friend class Louds;
+ };
+
+ Louds() {}
+ ~Louds() {}
+
+ // Initializes this LOUDS from bit array.
+ void Init(const uint8 *image, int length) {
index_.Init(image, length);
}
- void Close() {
+
+ // Explicitly clears the internal bit array.
+ void Reset() {
index_.Reset();
}
- // Returns true, if the corresponding bit represents an edge.
- // TODO(hidehiko): Check the performance of the conversion between int and
- // bool, because this method should be invoked so many times.
- inline bool IsEdgeBit(int bit_index) const {
- return (index_.Get(bit_index) != 0);
+ // APIs for traversal (all the methods are inline for performance).
+
+ // Initializes a Node instance from node ID.
+ // Note: to get the root node, just allocate a default Node instance.
+ void InitNodeFromNodeId(int node_id, Node *node) const {
+ node->node_id_ = node_id;
+ node->edge_index_ = index_.Select1(node->node_id_);
}
- // Returns the child node id of the edge corresponding to the given bit
- // index.
- // Note: the bit at the given index must be '1'.
- inline int GetChildNodeId(int bit_index) const {
- return index_.Rank1(bit_index) + 1;
+ // Returns true if the given node is the root.
+ static bool IsRoot(const Node &node) {
+ return node.node_id_ == 1;
}
- // Returns the parent node id of the edge corresponding to the given bit
- // index.
- // Note: this takes the bit index (as the argument variable name),
- // so it is OK to pass the bit index even if the bit is '0'.
- inline int GetParentNodeId(int bit_index) const {
- return index_.Rank0(bit_index);
+ // Moves the given node to its first (most left) child. If |node| is a leaf,
+ // the resulting node becomes invalid. For example, in the above diagram of
+ // tree, moves are as follows:
+ // * node 1 -> node 2
+ // * node 3 -> node 4
+ // * node 4 -> invalid node
+ // REQUIRES: |node| is valid.
+ void MoveToFirstChild(Node *node) const {
+ node->edge_index_ = index_.Select0(node->node_id_) + 1;
+ node->node_id_ = node->edge_index_ - node->node_id_ + 1;
}
- // Returns the bit index corresponding to the node's first edge.
- inline int GetFirstEdgeBitIndex(int node_id) const {
- return index_.Select0(node_id) + 1;
+ // Moves the given node to its next (right) sibling. If there's no sibling
+ // for |node|, the resulting node becomes invalid. For example, in the above
+ // diagram of tree, moves are as follows:
+ // * node 1 -> invalid node
+ // * node 2 -> node 3
+ // * node 5 -> invalid node
+ // REQUIRES: |node| is valid.
+ static void MoveToNextSibling(Node *node) {
+ ++node->edge_index_;
+ ++node->node_id_;
}
- // Returns the bit index corresponding to "the node to its parent" edge.
- // Note: the root node has no parent, so node_id must > 0.
- inline int GetParentEdgeBitIndex(int node_id) const {
- return index_.Select1(node_id);
+ // Moves the given node to its unique parent. For example, in the above
+ // diagram of tree, moves are as follows:
+ // * node 2 -> node 1
+ // * node 3 -> node 1
+ // * node 5 -> node 3
+ // REQUIRES: |node| is valid and not root.
+ void MoveToParent(Node *node) const {
+ node->node_id_ = node->edge_index_ - node->node_id_ + 1;
+ node->edge_index_ = index_.Select1(node->node_id_);
}
- // Returns the node id for the first child node of the given node.
- // The bit_index must be the bit index of the first edge bit index of the
- // node. This method calculates the id effectively, at least more effective
- // than calculating by Rank.
- static inline int GetChildNodeId(int node_id, int bit_index) {
- // Note: node_id == Rank0(bit_index),
- // so "bit_index - node_id" == Rank1(bit_index).
- // The first child_node_id is "Rank1(bit_index) + 1".
- return bit_index - node_id + 1;
+ // Returns true if |node| is in a valid state.
+ bool IsValidNode(const Node &node) const {
+ return index_.Get(node.edge_index_) != 0;
}
private:
diff --git a/src/storage/louds/louds_trie.cc b/src/storage/louds/louds_trie.cc
index 470a31d..2417157 100644
--- a/src/storage/louds/louds_trie.cc
+++ b/src/storage/louds/louds_trie.cc
@@ -29,8 +29,6 @@
#include "storage/louds/louds_trie.h"
-#include <cstring>
-
#include "base/logging.h"
#include "base/port.h"
#include "storage/louds/louds.h"
@@ -42,7 +40,7 @@
namespace {
inline int32 ReadInt32(const uint8 *data) {
- // TODO(hidehiko): static assertion for the endian.
+ // TODO(noriyukit): static assertion for the endian.
return *reinterpret_cast<const int32*>(data);
}
} // namespace
@@ -70,18 +68,18 @@
// [3]
// In this case, [0] and [1] are not terminal (as the original words contains
// neither "" nor "a"), and [2] and [3] are terminal.
- const int trie_size = ReadInt32(image);
+ const int louds_size = ReadInt32(image);
const int terminal_size = ReadInt32(image + 4);
const int num_character_bits = ReadInt32(image + 8);
const int edge_character_size = ReadInt32(image + 12);
CHECK_EQ(num_character_bits, 8);
CHECK_GT(edge_character_size, 0);
- const uint8 *trie_image = image + 16;
- const uint8 *terminal_image = trie_image + trie_size;
+ const uint8 *louds_image = image + 16;
+ const uint8 *terminal_image = louds_image + louds_size;
const uint8 *edge_character = terminal_image + terminal_size;
- trie_.Open(trie_image, trie_size);
+ louds_.Init(louds_image, louds_size);
terminal_bit_vector_.Init(terminal_image, terminal_size);
edge_character_ = reinterpret_cast<const char*>(edge_character);
@@ -89,326 +87,190 @@
}
void LoudsTrie::Close() {
- trie_.Close();
+ louds_.Reset();
terminal_bit_vector_.Reset();
- edge_character_ = NULL;
+ edge_character_ = nullptr;
}
-namespace {
-
-// Implementation of exact search.
-class ExactSearcher {
- public:
- ExactSearcher(const Louds *trie,
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector,
- const char *edge_character)
- : trie_(trie),
- terminal_bit_vector_(terminal_bit_vector),
- edge_character_(edge_character) {
- }
-
- // Returns the ID of |key| if it's in the trie. Returns -1 if it doesn't
- // exist.
- int Search(const StringPiece key) const {
- int node_id = 1; // Node id of the root node.
- int bit_index = 2; // Bit index of the root node.
- for (StringPiece::const_iterator key_iter = key.begin();
- key_iter != key.end(); ++key_iter) {
- node_id = trie_->GetChildNodeId(bit_index); // First child node
- while (true) {
- if (!trie_->IsEdgeBit(bit_index)) {
- // No more edge at this node, meaning that key doesn't exist in this
- // trie.
- return -1;
- }
- if (edge_character_[node_id - 1] == *key_iter) {
- // Found the key character currently searching for. Continue the
- // search for the next key character by setting |bit_index| to the
- // first edge of the current node.
- bit_index = trie_->GetFirstEdgeBitIndex(node_id);
- break;
- }
- // Search the next child. Because of the louds representation, all the
- // child bits are consecutive (as all bits are output by BFS order). So
- // we can move to the next child by simply incrementing node id and bit
- // index.
- ++node_id;
- ++bit_index;
+bool LoudsTrie::Traverse(StringPiece key, Node *node) const {
+ for (auto iter = key.begin(); iter != key.end(); ++iter) {
+ // Check all the children to find an edge with label |*iter|.
+ for (louds_.MoveToFirstChild(node); ; louds_.MoveToNextSibling(node)) {
+ if (!louds_.IsValidNode(*node)) {
+ return false;
+ }
+ if (GetEdgeLabelToParentNode(*node) == *iter) {
+ break;
}
}
- // Found a node corresponding to |key|. If this node is terminal, return the
- // index corresponding to this key.
- return terminal_bit_vector_->Get(node_id - 1) ?
- terminal_bit_vector_->Rank1(node_id - 1) : -1;
}
+ return true;
+}
- private:
- const Louds *trie_;
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector_;
- const char *edge_character_;
-
- DISALLOW_COPY_AND_ASSIGN(ExactSearcher);
-};
-
-} // namespace
-
-int LoudsTrie::ExactSearch(const StringPiece key) const {
- ExactSearcher searcher(&trie_, &terminal_bit_vector_, edge_character_);
- return searcher.Search(key);
+int LoudsTrie::ExactSearch(StringPiece key) const {
+ Node node; // Root
+ if (Traverse(key, &node) && IsTerminalNode(node)) {
+ return GetKeyIdOfTerminalNode(node);
+ }
+ return -1;
}
namespace {
-// This class is the implementation of prefix search.
-class PrefixSearcher {
- public:
- PrefixSearcher(const Louds *trie,
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector,
- const char *edge_character,
- const KeyExpansionTable *key_expansion_table,
- const char *key,
- LoudsTrie::Callback *callback)
- : trie_(trie),
- terminal_bit_vector_(terminal_bit_vector),
- edge_character_(edge_character),
- key_expansion_table_(key_expansion_table),
- key_(key),
- callback_(callback) {
+// Recursively traverses the trie in DFS order and runs |callback| at terminal
+// nodes. Returns true if traversal is done to exit recursion.
+bool PrefixSearchWithKeyExpansionImpl(
+ const LoudsTrie &trie,
+ StringPiece key,
+ const KeyExpansionTable &key_expansion_table,
+ LoudsTrie::Callback *callback,
+ LoudsTrie::Node node,
+ char *key_buffer,
+ StringPiece::size_type key_len) {
+ if (trie.IsTerminalNode(node)) {
+ const LoudsTrie::Callback::ResultType result =
+ callback->Run(key_buffer, key_len, trie.GetKeyIdOfTerminalNode(node));
+ switch (result) {
+ case LoudsTrie::Callback::SEARCH_DONE:
+ return true;
+ case LoudsTrie::Callback::SEARCH_CULL:
+ return false;
+ default:
+ break;
+ }
}
- // Returns true if we shouldn't continue to search any more.
- bool Search(size_t key_index, size_t bit_index) {
- const char key_char = key_[key_index];
- if (key_char == '\0') {
- // The end of search key. Do nothing.
- return false;
- }
-
- if (!trie_->IsEdgeBit(bit_index)) {
- // This is leaf. Do nothing.
- return false;
- }
-
- // Then traverse the children.
- int child_node_id = trie_->GetChildNodeId(bit_index);
- const ExpandedKey &expanded_key =
- key_expansion_table_->ExpandKey(key_char);
- do {
- const char character = edge_character_[child_node_id - 1];
- do {
- if (expanded_key.IsHit(character)) {
- buffer_[key_index] = character;
- // Hit the annotated character to the key char.
- if (terminal_bit_vector_->Get(child_node_id - 1)) {
- // The child node is terminal, so invoke the callback.
- LoudsTrie::Callback::ResultType callback_result =
- callback_->Run(buffer_, key_index + 1,
- terminal_bit_vector_->Rank1(child_node_id - 1));
- if (callback_result != LoudsTrie::Callback::SEARCH_CONTINUE) {
- if (callback_result == LoudsTrie::Callback::SEARCH_DONE) {
- return true;
- }
- DCHECK_EQ(callback_result, LoudsTrie::Callback::SEARCH_CULL);
- // If the callback returns "culling", we do not search
- // the child, but continue to search the sibling edges.
- break;
- }
- }
-
- // Search to the next child.
- // Note: we use recursive callback, instead of the just simple loop
- // here, in order to support key-expansion (in future).
- const int child_index = trie_->GetFirstEdgeBitIndex(child_node_id);
- if (Search(key_index + 1, child_index)) {
- return true;
- }
- }
- } while (false);
-
- // Note: Because of the representation of LOUDS, the child node id is
- // consecutive. So we don't need to invoke GetChildNodeId.
- ++bit_index;
- ++child_node_id;
- } while (trie_->IsEdgeBit(bit_index));
-
+ if (key_len == key.size()) {
return false;
}
- private:
- const Louds *trie_;
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector_;
- const char *edge_character_;
- const KeyExpansionTable *key_expansion_table_;
+ const char target_char = key[key_len];
+ const ExpandedKey &chars = key_expansion_table.ExpandKey(target_char);
+ for (trie.MoveToFirstChild(&node); trie.IsValidNode(node);
+ trie.MoveToNextSibling(&node)) {
+ const char c = trie.GetEdgeLabelToParentNode(node);
+ if (chars.IsHit(c)) {
+ key_buffer[key_len] = c;
+ if (PrefixSearchWithKeyExpansionImpl(trie, key, key_expansion_table,
+ callback, node,
+ key_buffer, key_len + 1)) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
- const char *key_;
- char buffer_[LoudsTrie::kMaxDepth + 1];
- LoudsTrie::Callback *callback_;
-
- DISALLOW_COPY_AND_ASSIGN(PrefixSearcher);
-};
} // namespace
void LoudsTrie::PrefixSearchWithKeyExpansion(
- const char *key, const KeyExpansionTable &key_expansion_table,
+ StringPiece key, const KeyExpansionTable &key_expansion_table,
Callback *callback) const {
- PrefixSearcher searcher(
- &trie_, &terminal_bit_vector_, edge_character_, &key_expansion_table,
- key, callback);
-
- // The bit index of the root node is '2'.
- searcher.Search(0, 2);
+ char key_buffer[kMaxDepth + 1];
+ PrefixSearchWithKeyExpansionImpl(*this, key, key_expansion_table,
+ callback,
+ Node(), // Root
+ key_buffer, 0);
}
namespace {
-class PredictiveSearcher {
- public:
- PredictiveSearcher(const Louds *trie,
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector,
- const char *edge_character,
- const KeyExpansionTable *key_expansion_table,
- const char *key,
- LoudsTrie::Callback *callback)
- : trie_(trie),
- terminal_bit_vector_(terminal_bit_vector),
- edge_character_(edge_character),
- key_expansion_table_(key_expansion_table),
- key_(key),
- callback_(callback) {
- }
- // Returns true if we shouldn't continue to search any more.
- bool Search(size_t key_index, int node_id, size_t bit_index) {
- const char key_char = key_[key_index];
- if (key_char == '\0') {
- // Hit the end of the key. Start traverse.
- return Traverse(key_index, node_id, &bit_index);
- }
-
- if (!trie_->IsEdgeBit(bit_index)) {
- // This is leaf. Do nothing.
- return false;
- }
-
- // Then traverse the children.
- int child_node_id = trie_->GetChildNodeId(bit_index);
- const ExpandedKey &expanded_key =
- key_expansion_table_->ExpandKey(key_char);
- do {
- const char character = edge_character_[child_node_id - 1];
- if (expanded_key.IsHit(character)) {
- buffer_[key_index] = character;
- const int child_index = trie_->GetFirstEdgeBitIndex(child_node_id);
- if (Search(key_index + 1, child_node_id, child_index)) {
- return true;
- }
- }
-
- // Note: Because of the representation of LOUDS, the child node id is
- // consecutive. So we don't need to invoke GetChildNodeId.
- ++bit_index;
- ++child_node_id;
- } while (trie_->IsEdgeBit(bit_index));
-
- return false;
- }
-
- private:
- const Louds *trie_;
- const SimpleSuccinctBitVectorIndex *terminal_bit_vector_;
- const char *edge_character_;
- const KeyExpansionTable *key_expansion_table_;
-
- const char *key_;
- char buffer_[LoudsTrie::kMaxDepth + 1];
- LoudsTrie::Callback *callback_;
-
- // Returns true if the caller should NOT continue the traversing.
- // *bit_index should store the current bit index for the traversing.
- // After the invocation of Traverse is done;
- // *bit_index is the last traversed bit index if Traverse returns false, or
- // undefined if Traverse returns true.
- bool Traverse(size_t key_index, int node_id, size_t *bit_index) {
- if (terminal_bit_vector_->Get(node_id - 1)) {
- // Invoke callback, if the node is terminal.
- LoudsTrie::Callback::ResultType callback_result = callback_->Run(
- buffer_, key_index, terminal_bit_vector_->Rank1(node_id - 1));
- if (callback_result != LoudsTrie::Callback::SEARCH_CONTINUE) {
- if (callback_result == LoudsTrie::Callback::SEARCH_DONE) {
- return true;
- }
-
- // Move the bit_index to the end of this node.
- // Note that we may be able to make this operation faster by checking
- // non-zero bits.
- while (trie_->IsEdgeBit(*bit_index)) {
- ++*bit_index;
- }
+// Traverses the subtree rooted at |node| in DFS order and runs |callback| at
+// each terminal node. Returns true if traversal should be stopped.
+bool TraverseSubTree(
+ const LoudsTrie &trie,
+ const KeyExpansionTable &key_expansion_table,
+ LoudsTrie::Callback *callback,
+ LoudsTrie::Node node,
+ char *key_buffer,
+ StringPiece::size_type key_len) {
+ if (trie.IsTerminalNode(node)) {
+ const LoudsTrie::Callback::ResultType result =
+ callback->Run(key_buffer, key_len, trie.GetKeyIdOfTerminalNode(node));
+ switch (result) {
+ case LoudsTrie::Callback::SEARCH_DONE:
+ return true;
+ case LoudsTrie::Callback::SEARCH_CULL:
return false;
- }
+ default:
+ break;
}
+ }
- if (!trie_->IsEdgeBit(*bit_index)) {
- return false;
+ for (trie.MoveToFirstChild(&node); trie.IsValidNode(node);
+ trie.MoveToNextSibling(&node)) {
+ key_buffer[key_len] = trie.GetEdgeLabelToParentNode(node);
+ if (TraverseSubTree(trie, key_expansion_table, callback, node,
+ key_buffer, key_len + 1)) {
+ return true;
}
+ }
+ return false;
+}
- // Then traverse the children.
- int child_node_id = Louds::GetChildNodeId(node_id, *bit_index);
+// Recursively traverses the trie in DFS order until terminal nodes for each
+// expanded key is found. Then TraverseSubTree() is called at each terminal
+// node. Returns true if traversal should be stopped.
+bool PredictiveSearchWithKeyExpansionImpl(
+ const LoudsTrie &trie,
+ StringPiece key,
+ const KeyExpansionTable &key_expansion_table,
+ LoudsTrie::Callback *callback,
+ LoudsTrie::Node node,
+ char *key_buffer,
+ StringPiece::size_type key_len) {
+ if (key_len == key.size()) {
+ return TraverseSubTree(trie, key_expansion_table, callback, node,
+ key_buffer, key_len);
+ }
- // Because of the louds representation, all the child bits should be
- // consecutive (as all bits are output by BFS order).
- // So, we can skip the consecutive child bit index searching.
- // Note: we probably can do this more efficiently, by caching the last
- // bit index for each level.
- size_t child_bit_index = trie_->GetFirstEdgeBitIndex(child_node_id);
- do {
- buffer_[key_index] = edge_character_[child_node_id - 1];
- if (Traverse(key_index + 1, child_node_id, &child_bit_index)) {
+ const char target_char = key[key_len];
+ const ExpandedKey &chars = key_expansion_table.ExpandKey(target_char);
+ for (trie.MoveToFirstChild(&node); trie.IsValidNode(node);
+ trie.MoveToNextSibling(&node)) {
+ const char c = trie.GetEdgeLabelToParentNode(node);
+ if (chars.IsHit(c)) {
+ key_buffer[key_len] = c;
+ if (PredictiveSearchWithKeyExpansionImpl(trie, key, key_expansion_table,
+ callback, node,
+ key_buffer, key_len + 1)) {
return true;
}
- ++*bit_index;
- ++child_bit_index;
- ++child_node_id;
- } while (trie_->IsEdgeBit(*bit_index));
-
- return false;
+ }
}
+ return false;
+}
- DISALLOW_COPY_AND_ASSIGN(PredictiveSearcher);
-};
} // namespace
void LoudsTrie::PredictiveSearchWithKeyExpansion(
- const char *key, const KeyExpansionTable &key_expansion_table,
+ StringPiece key, const KeyExpansionTable &key_expansion_table,
Callback *callback) const {
- PredictiveSearcher searcher(
- &trie_, &terminal_bit_vector_, edge_character_, &key_expansion_table,
- key, callback);
-
- searcher.Search(0, 1, 2);
+ char key_buffer[kMaxDepth + 1];
+ PredictiveSearchWithKeyExpansionImpl(
+ *this, key, key_expansion_table, callback,
+ Node(), // Root
+ key_buffer, 0);
}
-const char *LoudsTrie::Reverse(int key_id, char *buffer) const {
+StringPiece LoudsTrie::RestoreKeyString(int key_id, char *buf) const {
+ // TODO(noriyukit): Check if it's really necessary to handle this case.
if (key_id < 0) {
- // Just for rx compatibility.
- buffer[0] = '\0';
- return buffer;
+ return StringPiece();
}
- // Calculate node_id from key_id.
- int node_id = terminal_bit_vector_.Select1(key_id + 1) + 1;
+ // Ensure the returned StringPiece is null-terminated.
+ char *const buf_end = buf + kMaxDepth;
+ *buf_end = '\0';
- // Terminate by '\0'.
- char *ptr = buffer + kMaxDepth;
- *ptr = '\0';
-
- // Traverse the trie from leaf to root.
- while (node_id > 1) {
- --ptr;
- *ptr = edge_character_[node_id - 1];
- const int bit_index = trie_.GetParentEdgeBitIndex(node_id);
- node_id = trie_.GetParentNodeId(bit_index);
+ // Climb up the trie to the root and fill |buf| backward.
+ char *ptr = buf_end;
+ Node node;
+ GetTerminalNodeFromKeyId(key_id, &node);
+ for (; !louds_.IsRoot(node); louds_.MoveToParent(&node)) {
+ *--ptr = GetEdgeLabelToParentNode(node);
}
- return ptr;
+ return StringPiece(ptr, buf_end - ptr);
}
} // namespace louds
diff --git a/src/storage/louds/louds_trie.h b/src/storage/louds/louds_trie.h
index e1f62c3..bf0f66f 100644
--- a/src/storage/louds/louds_trie.h
+++ b/src/storage/louds/louds_trie.h
@@ -40,16 +40,14 @@
namespace storage {
namespace louds {
-// Implementation of a trie, based on the LOUDS (Level-Ordered Unary Degree
-// Sequence) data structure.
-// The "string" this class can handle as a key is c-style string
-// (i.e. '\0'-terminated char array).
-// TODO(hidehiko): Parametrize succinct bit vector implementation.
class LoudsTrie {
public:
// The max depth of the trie.
static const size_t kMaxDepth = 256;
+ // This class stores a traversal state.
+ using Node = Louds::Node;
+
// Interface which is called back when the result is found.
class Callback {
public:
@@ -76,10 +74,8 @@
Callback() {}
};
- LoudsTrie() : edge_character_(NULL) {
- }
- ~LoudsTrie() {
- }
+ LoudsTrie() : edge_character_(nullptr) {}
+ ~LoudsTrie() {}
// Opens the binary image, and constructs the data structure.
// This method doesn't own the "data", so it is caller's reponsibility
@@ -87,56 +83,131 @@
// See .cc file for the detailed format of the binary image.
bool Open(const uint8 *data);
- // Destructs the internal data structure.
+ // Destructs the internal data structure explicitly (the destructor will do
+ // clean up too).
void Close();
- // Searches the trie for the key that exactly matches the given key. Returns
- // -1 if the key doesn't exist.
- // TODO(noriyukit): Implement a callback style method if necessary.
- int ExactSearch(const StringPiece key) const;
+ // Generic APIs for tree traversal, some of which are delegated from Louds
+ // class; see louds.h.
+
+ // Returns true if |node| is in a valid state (returns true both for terminal
+ // and non-terminal nodes).
+ bool IsValidNode(const Node &node) const { return louds_.IsValidNode(node); }
+
+ // Returns true if |node| is a terminal node.
+ bool IsTerminalNode(const Node &node) const {
+ return terminal_bit_vector_.Get(node.node_id() - 1);
+ }
+
+ // Returns the label of the edge from |node|'s parent (predecessor) to |node|.
+ char GetEdgeLabelToParentNode(const Node &node) const {
+ return edge_character_[node.node_id() - 1];
+ }
+
+ // Computes the ID of key that reaches to |node|.
+ // REQUIRES: |node| is a terminal node.
+ int GetKeyIdOfTerminalNode(const Node &node) const {
+ return terminal_bit_vector_.Rank1(node.node_id() - 1);
+ }
+
+ // Initializes a node corresponding to |key_id|.
+ // REQUIRES: |key_id| is a valid ID.
+ void GetTerminalNodeFromKeyId(int key_id, Node *node) const {
+ const int node_id = terminal_bit_vector_.Select1(key_id + 1) + 1;
+ louds_.InitNodeFromNodeId(node_id, node);
+ }
+ Node GetTerminalNodeFromKeyId(int key_id) const {
+ Node node;
+ GetTerminalNodeFromKeyId(key_id, &node);
+ return node;
+ }
+
+ // Restores the key string corresponding to |key_id|. The caller is
+ // responsible for allocating a buffer for the result StringPiece, which needs
+ // to be passed in |buf|. The returned StringPiece points to a piece of
+ // |buf|.
+ // REQUIRES: |buf| is longer than kMaxDepth + 1.
+ StringPiece RestoreKeyString(int key_id, char *buf) const;
+
+ // Methods for moving node exported from Louds class; see louds.h.
+ void MoveToFirstChild(Node *node) const {
+ louds_.MoveToFirstChild(node);
+ }
+ Node MoveToFirstChild(Node node) const {
+ MoveToFirstChild(&node);
+ return node;
+ }
+ static void MoveToNextSibling(Node *node) {
+ Louds::MoveToNextSibling(node);
+ }
+ static Node MoveToNextSibling(Node node) {
+ MoveToNextSibling(&node);
+ return node;
+ }
+
+ // Traverses a trie for |key|, starting from |node|, and modifies |node| to
+ // the destination terminal node. Here, |node| is not necessarily the root.
+ // Returns false if there's no node reachable by |key|.
+ bool Traverse(StringPiece key, Node *node) const;
+
+ // Higher level APIs.
+
+ // Returns true if |key| is in this trie.
+ bool HasKey(StringPiece key) const {
+ Node node; // Root
+ return Traverse(key, &node) && IsTerminalNode(node);
+ }
+
+ // Searches this trie for the key that exactly matches the given key. Returns
+ // -1 if such key doesn't exist.
+ // NOTE: When you only need to check if |key| is in this trie, use HasKey()
+ // method, which is more efficient.
+ int ExactSearch(StringPiece key) const;
+
+ // TODO(noriyukit): The following search methods rely on Callback. However,
+ // this results in the nested callback to implement SystemDictionary's lookup
+ // methods (i.e., inside implementations of DictionaryInterface::Callback,
+ // LoudsTrie::Callback needs to be called; see system_dictionary.cc. This is
+ // somewhat inefficient because both requires virtual method calls.
+ // Therefore, it'd be better to implement the following search methods
+ // directly in system_dictionary.cc using more generic APIs defined above.
// Searches the trie structure, and invokes callback->Run when for each word
// which is a prefix of the key is found.
- void PrefixSearch(const char *key, Callback *callback) const {
+ void PrefixSearch(StringPiece key, Callback *callback) const {
PrefixSearchWithKeyExpansion(
key, KeyExpansionTable::GetDefaultInstance(), callback);
}
- void PrefixSearchWithKeyExpansion(
- const char *key, const KeyExpansionTable &key_expansion_table,
- Callback *callback) const;
+ void PrefixSearchWithKeyExpansion(
+ StringPiece key, const KeyExpansionTable &key_expansion_table,
+ Callback *callback) const;
// Searches the trie structure, and invokes callback->Run when for each word
// which begins with key is found.
- void PredictiveSearch(const char *key, Callback *callback) const {
+ void PredictiveSearch(StringPiece key, Callback *callback) const {
PredictiveSearchWithKeyExpansion(
key, KeyExpansionTable::GetDefaultInstance(), callback);
}
+
void PredictiveSearchWithKeyExpansion(
- const char *key, const KeyExpansionTable &key_expansion_table,
+ StringPiece key, const KeyExpansionTable &key_expansion_table,
Callback *callback) const;
-
- // Traverses the trie from leaf to root and store the characters annotated to
- // the edges. The size of the buffer should be larger than kMaxDepth. Returns
- // the pointer to the first character.
- const char *Reverse(int key_id, char *buf) const;
-
private:
- // Tree-structure represented in LOUDS.
- Louds trie_;
+ Louds louds_; // Tree structure representation by LOUDS.
// Bit-vector to represent whether each node in LOUDS tree is terminal.
// This bit vector doesn't include "super root" in the LOUDS.
- // In other words, id=1 in trie_ corresponds to id=0 in terminal_bit_vector_,
- // id=10 in trie_ corresponds to id=9 in terminal_bit_vector_, and so on.
- // TODO(hidehiko): Simplify the id-mapping by introducing a bit for the
+ // In other words, id=1 in louds_ corresponds to id=0 in terminal_bit_vector_,
+ // id=10 in louds_ corresponds to id=9 in terminal_bit_vector_, and so on.
+ // TODO(noriyukit): Simplify the id-mapping by introducing a bit for the
// super root in this bit vector.
SimpleSuccinctBitVectorIndex terminal_bit_vector_;
// A sequence of characters, annotated to each edge.
// This array also doesn't have an entry for super root.
- // In other words, id=2 in trie_ corresponds to edge_character_[1].
+ // In other words, id=2 in louds_ corresponds to edge_character_[1].
const char *edge_character_;
DISALLOW_COPY_AND_ASSIGN(LoudsTrie);
diff --git a/src/storage/louds/louds_trie_test.cc b/src/storage/louds/louds_trie_test.cc
index 342baa9..6735063 100644
--- a/src/storage/louds/louds_trie_test.cc
+++ b/src/storage/louds/louds_trie_test.cc
@@ -96,6 +96,213 @@
DISALLOW_COPY_AND_ASSIGN(TestCallback);
};
+TEST_F(LoudsTrieTest, NodeBasedApis) {
+ // Create the following trie (* stands for non-terminal nodes):
+ //
+ // * Key ID
+ // a/ \b ---------
+ // 0 * a 0
+ // a/ \b \d aa 1
+ // 1 2 3 ab 2
+ // c/ \d bd 3
+ // * 4 abd 4
+ // d| abcd 5
+ // 5
+ LoudsTrieBuilder builder;
+ builder.Add("a");
+ builder.Add("aa");
+ builder.Add("ab");
+ builder.Add("abcd");
+ builder.Add("abd");
+ builder.Add("bd");
+ builder.Build();
+
+ LoudsTrie trie;
+ trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
+
+ char buf[LoudsTrie::kMaxDepth + 1]; // for RestoreKeyString().
+
+ // Walk the trie in BFS order and check properties at each node.
+
+ // Root node
+ const LoudsTrie::Node root;
+ ASSERT_TRUE(trie.IsValidNode(root));
+ EXPECT_FALSE(trie.IsTerminalNode(root));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("", &node));
+ EXPECT_EQ(root, node);
+ }
+
+ // There's no right sibling for root.
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(root)));
+
+ // Terminal node for "a".
+ const LoudsTrie::Node node_a = trie.MoveToFirstChild(root);
+ ASSERT_TRUE(trie.IsValidNode(node_a));
+ ASSERT_TRUE(trie.IsTerminalNode(node_a));
+ EXPECT_EQ('a', trie.GetEdgeLabelToParentNode(node_a));
+ EXPECT_EQ(0, trie.GetKeyIdOfTerminalNode(node_a));
+ EXPECT_EQ(node_a, trie.GetTerminalNodeFromKeyId(0));
+ EXPECT_EQ("a", trie.RestoreKeyString(0, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("a", &node));
+ EXPECT_EQ(node_a, node);
+ }
+
+ // Non-terminal node for "b".
+ const LoudsTrie::Node node_b = trie.MoveToNextSibling(node_a);
+ ASSERT_TRUE(trie.IsValidNode(node_b));
+ EXPECT_FALSE(trie.IsTerminalNode(node_b));
+ EXPECT_EQ('b', trie.GetEdgeLabelToParentNode(node_b));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("b", &node));
+ EXPECT_EQ(node_b, node);
+ }
+
+ // There's no right sibling for "b".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_b)));
+
+ // Terminal node (leaf) for "aa".
+ const LoudsTrie::Node node_aa = trie.MoveToFirstChild(node_a);
+ ASSERT_TRUE(trie.IsValidNode(node_aa));
+ ASSERT_TRUE(trie.IsTerminalNode(node_aa));
+ EXPECT_EQ('a', trie.GetEdgeLabelToParentNode(node_aa));
+ EXPECT_EQ(1, trie.GetKeyIdOfTerminalNode(node_aa));
+ EXPECT_EQ(node_aa, trie.GetTerminalNodeFromKeyId(1));
+ EXPECT_EQ("aa", trie.RestoreKeyString(1, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("aa", &node));
+ EXPECT_EQ(node_aa, node);
+ }
+
+ // There's no child for "aa".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToFirstChild(node_aa)));
+
+ // Terminal node for "ab".
+ const LoudsTrie::Node node_ab = trie.MoveToNextSibling(node_aa);
+ ASSERT_TRUE(trie.IsValidNode(node_ab));
+ ASSERT_TRUE(trie.IsTerminalNode(node_ab));
+ EXPECT_EQ('b', trie.GetEdgeLabelToParentNode(node_ab));
+ EXPECT_EQ(2, trie.GetKeyIdOfTerminalNode(node_ab));
+ EXPECT_EQ(node_ab, trie.GetTerminalNodeFromKeyId(2));
+ EXPECT_EQ("ab", trie.RestoreKeyString(2, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("ab", &node));
+ EXPECT_EQ(node_ab, node);
+ }
+
+ // There's no right sibling for "ab".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_ab)));
+
+ // Terminal node (leaf) for "bd".
+ const LoudsTrie::Node node_bd = trie.MoveToFirstChild(node_b);
+ ASSERT_TRUE(trie.IsValidNode(node_bd));
+ ASSERT_TRUE(trie.IsTerminalNode(node_bd));
+ EXPECT_EQ('d', trie.GetEdgeLabelToParentNode(node_bd));
+ EXPECT_EQ(3, trie.GetKeyIdOfTerminalNode(node_bd));
+ EXPECT_EQ(node_bd, trie.GetTerminalNodeFromKeyId(3));
+ EXPECT_EQ("bd", trie.RestoreKeyString(3, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("bd", &node));
+ EXPECT_EQ(node_bd, node);
+ }
+
+ // There is no child nor right sibling for "bd".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToFirstChild(node_bd)));
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_bd)));
+
+ // Non-terminal node for "abc".
+ const LoudsTrie::Node node_abc = trie.MoveToFirstChild(node_ab);
+ ASSERT_TRUE(trie.IsValidNode(node_abc));
+ EXPECT_FALSE(trie.IsTerminalNode(node_abc));
+ EXPECT_EQ('c', trie.GetEdgeLabelToParentNode(node_abc));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("abc", &node));
+ EXPECT_EQ(node_abc, node);
+ }
+
+ // Terminal node (leaf) for "abd".
+ const LoudsTrie::Node node_abd = trie.MoveToNextSibling(node_abc);
+ ASSERT_TRUE(trie.IsValidNode(node_abd));
+ ASSERT_TRUE(trie.IsTerminalNode(node_abd));
+ EXPECT_EQ('d', trie.GetEdgeLabelToParentNode(node_abd));
+ EXPECT_EQ(4, trie.GetKeyIdOfTerminalNode(node_abd));
+ EXPECT_EQ(node_abd, trie.GetTerminalNodeFromKeyId(4));
+ EXPECT_EQ("abd", trie.RestoreKeyString(4, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("abd", &node));
+ EXPECT_EQ(node_abd, node);
+ }
+
+ // There is no child nor right sibling for "abd".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToFirstChild(node_abd)));
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_abd)));
+
+ // Terminal node (leaf) for "abcd".
+ const LoudsTrie::Node node_abcd = trie.MoveToFirstChild(node_abc);
+ ASSERT_TRUE(trie.IsValidNode(node_abcd));
+ ASSERT_TRUE(trie.IsTerminalNode(node_abcd));
+ EXPECT_EQ('d', trie.GetEdgeLabelToParentNode(node_abcd));
+ EXPECT_EQ(5, trie.GetKeyIdOfTerminalNode(node_abcd));
+ EXPECT_EQ(node_abcd, trie.GetTerminalNodeFromKeyId(5));
+ EXPECT_EQ("abcd", trie.RestoreKeyString(5, buf));
+ {
+ LoudsTrie::Node node;
+ EXPECT_TRUE(trie.Traverse("abcd", &node));
+ EXPECT_EQ(node_abcd, node);
+ }
+
+ // There is no child nor right sibling for "abcd".
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToFirstChild(node_abcd)));
+ EXPECT_FALSE(trie.IsValidNode(trie.MoveToNextSibling(node_abcd)));
+
+ // Traverse for some non-existing keys.
+ LoudsTrie::Node node;
+ EXPECT_FALSE(trie.Traverse("x", &node));
+ EXPECT_FALSE(trie.Traverse("xyz", &node));
+}
+
+TEST_F(LoudsTrieTest, HasKey) {
+ LoudsTrieBuilder builder;
+ builder.Add("a");
+ builder.Add("abc");
+ builder.Add("abcd");
+ builder.Add("ae");
+ builder.Add("aecd");
+ builder.Add("b");
+ builder.Add("bcx");
+
+ builder.Build();
+ LoudsTrie trie;
+ trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
+
+ EXPECT_TRUE(trie.HasKey("a"));
+ EXPECT_TRUE(trie.HasKey("abc"));
+ EXPECT_TRUE(trie.HasKey("abcd"));
+ EXPECT_TRUE(trie.HasKey("ae"));
+ EXPECT_TRUE(trie.HasKey("aecd"));
+ EXPECT_TRUE(trie.HasKey("b"));
+ EXPECT_TRUE(trie.HasKey("bcx"));
+ EXPECT_FALSE(trie.HasKey(""));
+ EXPECT_FALSE(trie.HasKey("ab"));
+ EXPECT_FALSE(trie.HasKey("aa"));
+ EXPECT_FALSE(trie.HasKey("aec"));
+ EXPECT_FALSE(trie.HasKey("aecx"));
+ EXPECT_FALSE(trie.HasKey("aecdf"));
+ EXPECT_FALSE(trie.HasKey("abcdefghi"));
+ EXPECT_FALSE(trie.HasKey("bc"));
+ EXPECT_FALSE(trie.HasKey("bca"));
+ EXPECT_FALSE(trie.HasKey("bcxyz"));
+}
+
TEST_F(LoudsTrieTest, ExactSearch) {
LoudsTrieBuilder builder;
builder.Add("a");
@@ -518,7 +725,7 @@
trie.Close();
}
-TEST_F(LoudsTrieTest, Reverse) {
+TEST_F(LoudsTrieTest, RestoreKeyString) {
LoudsTrieBuilder builder;
builder.Add("aa");
builder.Add("ab");
@@ -536,17 +743,17 @@
trie.Open(reinterpret_cast<const uint8 *>(builder.image().data()));
char buffer[LoudsTrie::kMaxDepth + 1];
- EXPECT_STREQ("aa", trie.Reverse(builder.GetId("aa"), buffer));
- EXPECT_STREQ("ab", trie.Reverse(builder.GetId("ab"), buffer));
- EXPECT_STREQ("abc", trie.Reverse(builder.GetId("abc"), buffer));
- EXPECT_STREQ("abcd", trie.Reverse(builder.GetId("abcd"), buffer));
- EXPECT_STREQ("abcde", trie.Reverse(builder.GetId("abcde"), buffer));
- EXPECT_STREQ("abcdef", trie.Reverse(builder.GetId("abcdef"), buffer));
- EXPECT_STREQ("abcea", trie.Reverse(builder.GetId("abcea"), buffer));
- EXPECT_STREQ("abcef", trie.Reverse(builder.GetId("abcef"), buffer));
- EXPECT_STREQ("abd", trie.Reverse(builder.GetId("abd"), buffer));
- EXPECT_STREQ("ebd", trie.Reverse(builder.GetId("ebd"), buffer));
- EXPECT_STREQ("", trie.Reverse(-1, buffer));
+ EXPECT_EQ("aa", trie.RestoreKeyString(builder.GetId("aa"), buffer));
+ EXPECT_EQ("ab", trie.RestoreKeyString(builder.GetId("ab"), buffer));
+ EXPECT_EQ("abc", trie.RestoreKeyString(builder.GetId("abc"), buffer));
+ EXPECT_EQ("abcd", trie.RestoreKeyString(builder.GetId("abcd"), buffer));
+ EXPECT_EQ("abcde", trie.RestoreKeyString(builder.GetId("abcde"), buffer));
+ EXPECT_EQ("abcdef", trie.RestoreKeyString(builder.GetId("abcdef"), buffer));
+ EXPECT_EQ("abcea", trie.RestoreKeyString(builder.GetId("abcea"), buffer));
+ EXPECT_EQ("abcef", trie.RestoreKeyString(builder.GetId("abcef"), buffer));
+ EXPECT_EQ("abd", trie.RestoreKeyString(builder.GetId("abd"), buffer));
+ EXPECT_EQ("ebd", trie.RestoreKeyString(builder.GetId("ebd"), buffer));
+ EXPECT_EQ("", trie.RestoreKeyString(-1, buffer));
trie.Close();
}
