1 // Copyright (C) 2014 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "trie.h"
16
17 #include <cassert>
18 #include <cstddef>
19 #include <map>
20 #include <queue>
21 #include <set>
22 #include <string>
23 #include <utility>
24
25 #include "stl_util.h"
26
27 namespace i18n {
28 namespace addressinput {
29
30 template <typename T>
Trie()31 Trie<T>::Trie() {}
32
33 template <typename T>
~Trie()34 Trie<T>::~Trie() {
35 STLDeleteValues(&sub_nodes_);
36 }
37
38 template <typename T>
AddDataForKey(const std::string & key,const T & data_item)39 void Trie<T>::AddDataForKey(const std::string& key, const T& data_item) {
40 Trie<T>* current_node = this;
41 for (size_t key_start = 0; key_start < key.length(); ++key_start) {
42 typename std::map<char, Trie<T>*>::const_iterator sub_node_it =
43 current_node->sub_nodes_.find(key[key_start]);
44 if (sub_node_it == current_node->sub_nodes_.end()) {
45 sub_node_it = current_node->sub_nodes_.insert(
46 std::make_pair(key[key_start], new Trie<T>)).first;
47 }
48 current_node = sub_node_it->second;
49 assert(current_node != NULL);
50 }
51 current_node->data_list_.push_back(data_item);
52 }
53
54 template <typename T>
FindDataForKeyPrefix(const std::string & key_prefix,std::set<T> * results) const55 void Trie<T>::FindDataForKeyPrefix(const std::string& key_prefix,
56 std::set<T>* results) const {
57 assert(results != NULL);
58
59 // Find the sub-trie for the key prefix.
60 const Trie<T>* current_node = this;
61 for (size_t key_prefix_start = 0; key_prefix_start < key_prefix.length();
62 ++key_prefix_start) {
63 typename std::map<char, Trie<T>*>::const_iterator sub_node_it =
64 current_node->sub_nodes_.find(key_prefix[key_prefix_start]);
65 if (sub_node_it == current_node->sub_nodes_.end()) {
66 return;
67 }
68 current_node = sub_node_it->second;
69 assert(current_node != NULL);
70 }
71
72 // Collect data from all sub-tries.
73 std::queue<const Trie<T>*> node_queue;
74 node_queue.push(current_node);
75 while (!node_queue.empty()) {
76 const Trie<T>* queue_front = node_queue.front();
77 node_queue.pop();
78
79 results->insert(
80 queue_front->data_list_.begin(), queue_front->data_list_.end());
81
82 for (typename std::map<char, Trie<T>*>::const_iterator sub_node_it =
83 queue_front->sub_nodes_.begin();
84 sub_node_it != queue_front->sub_nodes_.end();
85 ++sub_node_it) {
86 node_queue.push(sub_node_it->second);
87 }
88 }
89 }
90
91 // Separating template definitions and declarations requires defining all
92 // possible template parameters to avoid linking errors.
93 class Ruleset;
94 template class Trie<const Ruleset*>;
95 template class Trie<std::string>;
96
97 } // namespace addressinput
98 } // namespace i18n
99