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 <stdint.h> 8 #include <set> 9 #include <string> 10 11 #include "testing/gtest/include/gtest/gtest.h" 12 13 namespace autofill { 14 15 namespace { 16 17 std::vector<uint8_t> ToByteArray(const std::string& text) { 18 std::vector<uint8_t> result(text.length() + 1, 0); 19 result.assign(text.begin(), text.end()); 20 return result; 21 } 22 23 } // namespace 24 25 TEST(TrieTest, EmptyTrieHasNoData) { 26 Trie<std::string> trie; 27 std::set<std::string> result; 28 trie.FindDataForKeyPrefix(ToByteArray("key"), &result); 29 EXPECT_TRUE(result.empty()); 30 } 31 32 TEST(TrieTest, CanGetDataByExactKey) { 33 Trie<std::string> trie; 34 trie.AddDataForKey(ToByteArray("hello"), "world"); 35 std::set<std::string> result; 36 trie.FindDataForKeyPrefix(ToByteArray("hello"), &result); 37 std::set<std::string> expected; 38 expected.insert("world"); 39 EXPECT_EQ(expected, result); 40 } 41 42 TEST(TrieTest, CanGetDataByPrefix) { 43 Trie<std::string> trie; 44 trie.AddDataForKey(ToByteArray("hello"), "world"); 45 std::set<std::string> result; 46 trie.FindDataForKeyPrefix(ToByteArray("he"), &result); 47 std::set<std::string> expected; 48 expected.insert("world"); 49 EXPECT_EQ(expected, result); 50 } 51 52 TEST(TrieTest, KeyTooLongNoData) { 53 Trie<std::string> trie; 54 trie.AddDataForKey(ToByteArray("hello"), "world"); 55 std::set<std::string> result; 56 trie.FindDataForKeyPrefix(ToByteArray("helloo"), &result); 57 EXPECT_TRUE(result.empty()); 58 } 59 60 TEST(TrieTest, CommonPrefixFindsMultipleData) { 61 Trie<std::string> trie; 62 trie.AddDataForKey(ToByteArray("hello"), "world"); 63 trie.AddDataForKey(ToByteArray("howdy"), "buddy"); 64 trie.AddDataForKey(ToByteArray("foo"), "bar"); 65 std::set<std::string> results; 66 trie.FindDataForKeyPrefix(ToByteArray("h"), &results); 67 std::set<std::string> expected; 68 expected.insert("world"); 69 expected.insert("buddy"); 70 EXPECT_EQ(expected, results); 71 } 72 73 TEST(TrieTest, KeyCanBePrefixOfOtherKey) { 74 Trie<std::string> trie; 75 trie.AddDataForKey(ToByteArray("hello"), "world"); 76 trie.AddDataForKey(ToByteArray("helloo"), "woorld"); 77 trie.AddDataForKey(ToByteArray("hella"), "warld"); 78 std::set<std::string> results; 79 trie.FindDataForKeyPrefix(ToByteArray("hello"), &results); 80 std::set<std::string> expected; 81 expected.insert("world"); 82 expected.insert("woorld"); 83 EXPECT_EQ(expected, results); 84 } 85 86 TEST(TrieTest, AllowMutlipleKeys) { 87 Trie<std::string> trie; 88 trie.AddDataForKey(ToByteArray("hello"), "world"); 89 trie.AddDataForKey(ToByteArray("hello"), "woorld"); 90 std::set<std::string> results; 91 trie.FindDataForKeyPrefix(ToByteArray("hello"), &results); 92 std::set<std::string> expected; 93 expected.insert("world"); 94 expected.insert("woorld"); 95 EXPECT_EQ(expected, results); 96 } 97 98 TEST(TrieTest, CanFindVeryLongKey) { 99 Trie<std::string> trie; 100 static const char kVeryLongKey[] = "1234567890qwertyuioasdfghj"; 101 trie.AddDataForKey(ToByteArray(kVeryLongKey), "world"); 102 std::set<std::string> result; 103 trie.FindDataForKeyPrefix(ToByteArray(kVeryLongKey), &result); 104 std::set<std::string> expected; 105 expected.insert("world"); 106 EXPECT_EQ(expected, result); 107 } 108 109 } // namespace autofill 110
