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 #ifndef I18N_ADDRESSINPUT_UTIL_TRIE_H_ 16 #define I18N_ADDRESSINPUT_UTIL_TRIE_H_ 17 18 #include <libaddressinput/util/basictypes.h> 19 20 #include <list> 21 #include <map> 22 #include <set> 23 #include <string> 24 25 namespace i18n { 26 namespace addressinput { 27 28 // A prefix search tree. Can return all objects whose keys start with a prefix 29 // string. 30 // 31 // Maps keys to multiple objects. This property is useful when mapping region 32 // names to region objects. For example, there's a "St. Petersburg" in Florida, 33 // and there's a "St. Petersburg" in Russia. A lookup for "St. Petersburg" key 34 // should return two distinct objects. 35 template <typename T> 36 class Trie { 37 public: 38 Trie(); 39 40 ~Trie(); 41 42 // Adds a mapping from |key| to |data_item|. Can be called with the same |key| 43 // multiple times. 44 void AddDataForKey(const std::string& key, const T& data_item); 45 46 // Adds all objects whose keys start with |key_prefix| to the |results| 47 // parameter. The |results| parameter should not be NULL. 48 void FindDataForKeyPrefix(const std::string& key_prefix, 49 std::set<T>* results) const; 50 51 private: 52 // All objects for this node in the trie. This field is a collection to enable 53 // mapping the same key to multiple objects. 54 std::list<T> data_list_; 55 56 // Trie sub nodes. The root trie stores the objects for the empty string key. 57 // The children of the root trie store the objects for the one-letter keys. 58 // The grand-children of the root trie store the objects for the two-letter 59 // keys, and so on. 60 std::map<char, Trie<T>*> sub_nodes_; 61 62 DISALLOW_COPY_AND_ASSIGN(Trie); 63 }; 64 65 } // namespace addressinput 66 } // namespace i18n 67 68 #endif // I18N_ADDRESSINPUT_UTIL_TRIE_H_ 69