OLD | NEW |
(Empty) | |
| 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 |
| 26 template <typename T> |
| 27 Trie<T>::~Trie() {} |
| 28 |
| 29 template <typename T> |
| 30 void Trie<T>::AddDataForKey(const uint8_t* key, |
| 31 int32_t key_size, |
| 32 const T& data_item) { |
| 33 Trie<T>* current_node = this; |
| 34 for (int32_t i = 0; i < key_size; ++i) |
| 35 current_node = ¤t_node->sub_nodes_[key[i]]; |
| 36 current_node->data_list_.insert(data_item); |
| 37 } |
| 38 |
| 39 template <typename T> |
| 40 void Trie<T>::FindDataForKeyPrefix(const uint8_t* key_prefix, |
| 41 int32_t key_prefix_size, |
| 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 (int32_t i = 0; i < key_prefix_size; ++i) { |
| 48 typename std::map<uint8_t, Trie<T> >::const_iterator sub_node_it = |
| 49 current_node->sub_nodes_.find(key_prefix[i]); |
| 50 if (sub_node_it == current_node->sub_nodes_.end()) |
| 51 return; |
| 52 |
| 53 current_node = &sub_node_it->second; |
| 54 } |
| 55 |
| 56 // Collect data from all sub-tries. |
| 57 std::queue<const Trie<T>*> node_queue; |
| 58 node_queue.push(current_node); |
| 59 while (!node_queue.empty()) { |
| 60 const Trie<T>* queue_front = node_queue.front(); |
| 61 node_queue.pop(); |
| 62 |
| 63 results->insert(queue_front->data_list_.begin(), |
| 64 queue_front->data_list_.end()); |
| 65 |
| 66 for (typename std::map<uint8_t, Trie<T> >::const_iterator sub_node_it = |
| 67 queue_front->sub_nodes_.begin(); |
| 68 sub_node_it != queue_front->sub_nodes_.end(); |
| 69 ++sub_node_it) { |
| 70 node_queue.push(&sub_node_it->second); |
| 71 } |
| 72 } |
| 73 } |
| 74 |
| 75 template class Trie<const ::i18n::addressinput::RegionData*>; |
| 76 template class Trie<std::string>; |
| 77 |
| 78 } // namespace autofill |
OLD | NEW |