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 13namespace autofill { 14 15namespace { 16 17std::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 25TEST(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 32TEST(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 42TEST(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 52TEST(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 60TEST(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 73TEST(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 86TEST(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 98TEST(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