third_party/libaddressinput/chromium/trie.cc

   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 #include "third_party/libaddressinput/chromium/trie.h"
   6
   7 #include <queue>
   8 #include <string>
   9
  10 #include "base/logging.h"
  11
  12 // Separating template definitions and declarations requires defining all
  13 // possible template parameters to avoid linking errors.
  14 namespace i18n {
  15 namespace addressinput {
  16 class RegionData;
  17 }
  18 }
  19
  20 namespace autofill {
  21
  22 template <typename T>
  23 Trie<T>::Trie() {}
  24
  25 template <typename T>
  26 Trie<T>::~Trie() {}
  27
  28 template <typename T>
  29 void Trie<T>::AddDataForKey(const std::vector<uint8_t>& key,
  30                             const T& data_item) {
  31   Trie<T>* current_node = this;
  32   for (std::vector<uint8_t>::size_type i = 0; i < key.size(); ++i) {
  33     if (!key[i])
  34       break;
  35     current_node = &current_node->sub_nodes_[key[i]];
  36   }
  37   current_node->data_list_.insert(data_item);
  38 }
  39
  40 template <typename T>
  41 void Trie<T>::FindDataForKeyPrefix(const std::vector<uint8_t>& key_prefix,
  42                                    std::set<T>* results) const {
  43   DCHECK(results);
  44
  45   // Find the sub-trie for the key prefix.
  46   const Trie<T>* current_node = this;
  47   for (std::vector<uint8_t>::size_type i = 0; i < key_prefix.size(); ++i) {
  48     if (!key_prefix[i])
  49       break;
  50
  51     typename std::map<uint8_t, Trie<T> >::const_iterator sub_node_it =
  52         current_node->sub_nodes_.find(key_prefix[i]);
  53     if (sub_node_it == current_node->sub_nodes_.end())
  54       return;
  55
  56     current_node = &sub_node_it->second;
  57   }
  58
  59   // Collect data from all sub-tries.
  60   std::queue<const Trie<T>*> node_queue;
  61   node_queue.push(current_node);
  62   while (!node_queue.empty()) {
  63     const Trie<T>* queue_front = node_queue.front();
  64     node_queue.pop();
  65
  66     results->insert(queue_front->data_list_.begin(),
  67                     queue_front->data_list_.end());
  68
  69     for (typename std::map<uint8_t, Trie<T> >::const_iterator sub_node_it =
  70              queue_front->sub_nodes_.begin();
  71          sub_node_it != queue_front->sub_nodes_.end();
  72          ++sub_node_it) {
  73       node_queue.push(&sub_node_it->second);
  74     }
  75   }
  76 }
  77
  78 template class Trie<const ::i18n::addressinput::RegionData*>;
  79 template class Trie<std::string>;
  80
  81 }  // namespace autofill