third_party/libaddressinput/chromium/trie.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_
   6 #define THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_
   7
   8 #include <stdint.h>
   9 #include <map>
  10 #include <set>
  11 #include <vector>
  12
  13 namespace autofill {
  14
  15 // A prefix search tree. Can return all objects whose keys start with a prefix
  16 // byte sequence.
  17 //
  18 // Maps keys to multiple objects. This property is useful when mapping region
  19 // names to region objects. For example, there's a "St. Petersburg" in Florida,
  20 // and there's a "St. Petersburg" in Russia. A lookup for "St. Petersburg" key
  21 // should return two distinct objects.
  22 template <typename T>
  23 class Trie {
  24  public:
  25   Trie();
  26   ~Trie();
  27
  28   // Returns true if no data was added in AddDataForKey().
  29   bool empty() const { return data_list_.empty() && sub_nodes_.empty(); }
  30
  31   // Adds a mapping from the 0 terminated |key| to |data_item|. Can be called
  32   // with the same |key| multiple times.
  33   void AddDataForKey(const std::vector<uint8_t>& key, const T& data_item);
  34
  35   // Adds all objects whose keys start with the 0 terminated |key_prefix| to the
  36   // |results| parameter. The |results| parameter should not be NULL.
  37   void FindDataForKeyPrefix(const std::vector<uint8_t>& key_prefix,
  38                             std::set<T>* results) const;
  39
  40  private:
  41   // All objects for this node in the Trie. This field is a collection to enable
  42   // mapping the same key to multiple objects.
  43   std::set<T> data_list_;
  44
  45   // Trie sub nodes. The root Trie stores the objects for the empty key. The
  46   // children of the root Trie store the objects for the one-byte keys. The
  47   // grand-children of the root Trie store the objects for the two-byte keys,
  48   // and so on.
  49   std::map<uint8_t, Trie<T> > sub_nodes_;
  50 };
  51
  52 }  // namespace autofill
  53
  54 #endif  // THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_