| 105 | } |
| 106 | |
| 107 | static void TestTrieContents(const Trie& trie, const std::vector<std::string>& entries) { |
| 108 | std::unordered_map<std::string, int32_t> control; |
| 109 | auto n_entries = static_cast<int32_t>(entries.size()); |
| 110 | |
| 111 | // Build control container |
| 112 | for (int32_t i = 0; i < n_entries; ++i) { |
| 113 | auto p = control.insert({entries[i], i}); |
| 114 | ASSERT_TRUE(p.second); |
| 115 | } |
| 116 | |
| 117 | // Check all existing entries in trie |
| 118 | for (int32_t i = 0; i < n_entries; ++i) { |
| 119 | ASSERT_EQ(i, trie.Find(entries[i])) << "for string '" << entries[i] << "'"; |
| 120 | } |
| 121 | |
| 122 | auto CheckNotExists = [&control, &trie](const std::string& s) { |
| 123 | auto p = control.find(s); |
| 124 | if (p == control.end()) { |
| 125 | ASSERT_EQ(-1, trie.Find(s)) << "for string '" << s << "'"; |
| 126 | } |
| 127 | }; |
| 128 | |
| 129 | // Check potentially nonexistent strings |
| 130 | CheckNotExists(""); |
| 131 | CheckNotExists("X"); |
| 132 | CheckNotExists("abcdefxxxxxxxxxxxxxxx"); |
| 133 | |
| 134 | // Check potentially nonexistent variations of existing entries |
| 135 | for (const auto& e : entries) { |
| 136 | CheckNotExists(e + "X"); |
| 137 | if (e.size() > 0) { |
| 138 | CheckNotExists(e.substr(0, 1)); |
| 139 | auto prefix = e.substr(0, e.size() - 1); |
| 140 | CheckNotExists(prefix); |
| 141 | CheckNotExists(prefix + "X"); |
| 142 | auto split_at = e.size() / 2; |
| 143 | CheckNotExists(e.substr(0, split_at) + 'x' + e.substr(split_at + 1)); |
| 144 | } |
| 145 | } |
| 146 | } |
| 147 | |
| 148 | static void TestTrieContents(const std::vector<std::string>& entries) { |
| 149 | TrieBuilder builder; |