Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(287)

Side by Side Diff: third_party/libaddressinput/chromium/trie.cc

Issue 298863012: Use upstream libaddressinput in Chrome. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Fixup includes and comments for tries and ICU. Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(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 = &current_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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698