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