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