1116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Copyright 2014 The Chromium Authors. All rights reserved. 2116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// found in the LICENSE file. 4116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 5116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#ifndef THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ 6116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#define THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ 7116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <stdint.h> 9116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <map> 10116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <set> 11116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <vector> 12116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 13116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace autofill { 14116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 15116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// A prefix search tree. Can return all objects whose keys start with a prefix 16116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// byte sequence. 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// 18116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Maps keys to multiple objects. This property is useful when mapping region 19116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// names to region objects. For example, there's a "St. Petersburg" in Florida, 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// and there's a "St. Petersburg" in Russia. A lookup for "St. Petersburg" key 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// should return two distinct objects. 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdochtemplate <typename T> 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdochclass Trie { 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch public: 25116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Trie(); 26116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch ~Trie(); 27116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 28116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Returns true if no data was added in AddDataForKey(). 29116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch bool empty() const { return data_list_.empty() && sub_nodes_.empty(); } 30116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 31116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Adds a mapping from the 0 terminated |key| to |data_item|. Can be called 32116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // with the same |key| multiple times. 33116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void AddDataForKey(const std::vector<uint8_t>& key, const T& data_item); 34116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 35116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Adds all objects whose keys start with the 0 terminated |key_prefix| to the 36116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // |results| parameter. The |results| parameter should not be NULL. 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch void FindDataForKeyPrefix(const std::vector<uint8_t>& key_prefix, 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::set<T>* results) const; 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch private: 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // All objects for this node in the Trie. This field is a collection to enable 42116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // mapping the same key to multiple objects. 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::set<T> data_list_; 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 45116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Trie sub nodes. The root Trie stores the objects for the empty key. The 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // children of the root Trie store the objects for the one-byte keys. The 47116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // grand-children of the root Trie store the objects for the two-byte keys, 48116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // and so on. 49116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::map<uint8_t, Trie<T> > sub_nodes_; 50116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch}; 51116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 52116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} // namespace autofill 53116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 54116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#endif // THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_ 55