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 #ifndef THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ | |
6 #define THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ | |
7 | |
8 #include <stdint.h> | |
9 #include <map> | |
10 #include <set> | |
11 | |
12 namespace autofill { | |
13 | |
14 // A prefix search tree. Can return all objects whose keys start with a prefix | |
15 // byte sequence. | |
16 // | |
17 // Maps keys to multiple objects. This property is useful when mapping region | |
18 // names to region objects. For example, there's a "St. Petersburg" in Florida, | |
19 // and there's a "St. Petersburg" in Russia. A lookup for "St. Petersburg" key | |
20 // should return two distinct objects. | |
21 template <typename T> | |
22 class Trie { | |
23 public: | |
24 Trie(); | |
25 ~Trie(); | |
26 | |
27 // Returns true if no data was added in AddDataForKey(). | |
28 bool empty() const { return data_list_.empty() && sub_nodes_.empty(); } | |
29 | |
30 // Adds a mapping from |key| to |data_item|. Can be called with the same |key| | |
31 // multiple times. Does not take ownership of |key|, which should not be NULL. | |
32 void AddDataForKey(const uint8_t* key, int32_t key_size, const T& data_item); | |
Evan Stade
2014/06/27 22:44:38
a) sizes are usually size_t
b) this is a really co
please use gerrit instead
2014/06/28 22:05:21
Using std::vector<uint8_t> now.
| |
33 | |
34 // Adds all objects whose keys start with |key_prefix| to the |results| | |
35 // parameter. Does not take ownership of |key_prefix|, which should not be | |
36 // NULL. The |results| parameter should not be NULL. | |
37 void FindDataForKeyPrefix(const uint8_t* key_prefix, | |
38 int32_t key_prefix_size, | |
39 std::set<T>* results) const; | |
40 | |
41 private: | |
42 // All objects for this node in the Trie. This field is a collection to enable | |
43 // mapping the same key to multiple objects. | |
44 std::set<T> data_list_; | |
45 | |
46 // Trie sub nodes. The root Trie stores the objects for the empty key. The | |
47 // children of the root Trie store the objects for the one-byte keys. The | |
48 // grand-children of the root Trie store the objects for the two-byte keys, | |
49 // and so on. | |
50 std::map<uint8_t, Trie<T> > sub_nodes_; | |
51 }; | |
52 | |
53 } // namespace autofill | |
54 | |
55 #endif // THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ | |
OLD | NEW |