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