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()25Trie<T>::Trie() {} 26 27 template <typename T> ~Trie()28Trie<T>::~Trie() {} 29 30 template <typename T> AddDataForKey(const std::vector<uint8_t> & key,const T & data_item)31void 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 = ¤t_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) const43void 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