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.
14namespace i18n {
15namespace addressinput {
16class RegionData;
17}
18}
19
20namespace autofill {
21
22template <typename T>
23Trie<T>::Trie() {}
24
25template <typename T>
26Trie<T>::~Trie() {}
27
28template <typename T>
29void 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
40template <typename T>
41void 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
78template class Trie<const ::i18n::addressinput::RegionData*>;
79template class Trie<std::string>;
80
81}  // namespace autofill
82