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. 4a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 5116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "third_party/libaddressinput/chromium/trie.h" 6116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 7116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include <stdint.h> 8a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include <set> 9a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include <string> 10a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 11116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "testing/gtest/include/gtest/gtest.h" 12a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 13116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace autofill { 14a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 15a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)namespace { 16a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdochstd::vector<uint8_t> ToByteArray(const std::string& text) { 18116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::vector<uint8_t> result(text.length() + 1, 0); 19116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch result.assign(text.begin(), text.end()); 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return result; 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} // namespace 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 25a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, EmptyTrieHasNoData) { 26a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 27a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> result; 28116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("key"), &result); 29a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_TRUE(result.empty()); 30a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 31a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 32a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, CanGetDataByExactKey) { 33a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 34116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 35a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> result; 36116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("hello"), &result); 37a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 38a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 39a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, result); 40a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 41a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 42a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, CanGetDataByPrefix) { 43a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 45a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> result; 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("he"), &result); 47a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 48a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 49a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, result); 50a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 51a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 52a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, KeyTooLongNoData) { 53a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 54116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 55a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> result; 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("helloo"), &result); 57a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_TRUE(result.empty()); 58a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 59a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 60a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, CommonPrefixFindsMultipleData) { 61a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 62116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 63116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("howdy"), "buddy"); 64116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("foo"), "bar"); 65a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> results; 66116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("h"), &results); 67a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 68a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 69a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("buddy"); 70a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, results); 71a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 72a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 73a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, KeyCanBePrefixOfOtherKey) { 74a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 75116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 76116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("helloo"), "woorld"); 77116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hella"), "warld"); 78a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> results; 79116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("hello"), &results); 80a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 81a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 82a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("woorld"); 83a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, results); 84a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 85a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 86a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, AllowMutlipleKeys) { 87a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 88116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "world"); 89116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray("hello"), "woorld"); 90a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> results; 91116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray("hello"), &results); 92a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 93a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 94a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("woorld"); 95a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, results); 96a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 97a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 98a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TEST(TrieTest, CanFindVeryLongKey) { 99a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) Trie<std::string> trie; 100a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) static const char kVeryLongKey[] = "1234567890qwertyuioasdfghj"; 101116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.AddDataForKey(ToByteArray(kVeryLongKey), "world"); 102a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> result; 103116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch trie.FindDataForKeyPrefix(ToByteArray(kVeryLongKey), &result); 104a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::set<std::string> expected; 105a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) expected.insert("world"); 106a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) EXPECT_EQ(expected, result); 107a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 108a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 109116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} // namespace autofill 110