1 files changed, 109 insertions, 0 deletions
diff --git a/third_party/libaddressinput/chromium/trie_unittest.cc b/third_party/libaddressinput/chromium/trie_unittest.cc
new file mode 100644
index 0000000..32b0bb1
--- /dev/null
+++ b/third_party/libaddressinput/chromium/trie_unittest.cc
@@ -0,0 +1,109 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/libaddressinput/chromium/trie.h"
+
+#include <stdint.h>
+#include <set>
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace autofill {
+
+namespace {
+
+std::vector<uint8_t> ToByteArray(const std::string& text) {
+  std::vector<uint8_t> result(text.length() + 1, 0);
+  result.assign(text.begin(), text.end());
+  return result;
+}
+
+}  // namespace
+
+TEST(TrieTest, EmptyTrieHasNoData) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+  trie.FindDataForKeyPrefix(ToByteArray("key"), &result);
+  EXPECT_TRUE(result.empty());
+}
+
+TEST(TrieTest, CanGetDataByExactKey) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  std::set<std::string> result;
+  trie.FindDataForKeyPrefix(ToByteArray("hello"), &result);
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, CanGetDataByPrefix) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  std::set<std::string> result;
+  trie.FindDataForKeyPrefix(ToByteArray("he"), &result);
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, KeyTooLongNoData) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  std::set<std::string> result;
+  trie.FindDataForKeyPrefix(ToByteArray("helloo"), &result);
+  EXPECT_TRUE(result.empty());
+}
+
+TEST(TrieTest, CommonPrefixFindsMultipleData) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  trie.AddDataForKey(ToByteArray("howdy"), "buddy");
+  trie.AddDataForKey(ToByteArray("foo"), "bar");
+  std::set<std::string> results;
+  trie.FindDataForKeyPrefix(ToByteArray("h"), &results);
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("buddy");
+  EXPECT_EQ(expected, results);
+}
+
+TEST(TrieTest, KeyCanBePrefixOfOtherKey) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  trie.AddDataForKey(ToByteArray("helloo"), "woorld");
+  trie.AddDataForKey(ToByteArray("hella"), "warld");
+  std::set<std::string> results;
+  trie.FindDataForKeyPrefix(ToByteArray("hello"), &results);
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("woorld");
+  EXPECT_EQ(expected, results);
+}
+
+TEST(TrieTest, AllowMutlipleKeys) {
+  Trie<std::string> trie;
+  trie.AddDataForKey(ToByteArray("hello"), "world");
+  trie.AddDataForKey(ToByteArray("hello"), "woorld");
+  std::set<std::string> results;
+  trie.FindDataForKeyPrefix(ToByteArray("hello"), &results);
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("woorld");
+  EXPECT_EQ(expected, results);
+}
+
+TEST(TrieTest, CanFindVeryLongKey) {
+  Trie<std::string> trie;
+  static const char kVeryLongKey[] = "1234567890qwertyuioasdfghj";
+  trie.AddDataForKey(ToByteArray(kVeryLongKey), "world");
+  std::set<std::string> result;
+  trie.FindDataForKeyPrefix(ToByteArray(kVeryLongKey), &result);
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+}  // namespace autofill