src/third_party/libaddressinput/chromium/cpp/src/util/trie.h

   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_