Home | History | Annotate | Download | only in chromium 
      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 template <typename T>
     26 Trie<T>::~Trie() {}
     27 
     28 template <typename T>
     29 void 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 
     40 template <typename T>
     41 void 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 
     78 template class Trie<const ::i18n::addressinput::RegionData*>;
     79 template class Trie<std::string>;
     80 
     81 }  // namespace autofill
     82