Use upstream libaddressinput in Chrome.

third_party/libaddressinput/chromium/trie_unittest.cc

+// 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 <set>
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace autofill {
+
+TEST(TrieTest, EmptyTrieHasNoData) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kKey[] = {0, 1, 2};
+  trie.FindDataForKeyPrefix(kKey, 3, &result);
+
+  EXPECT_TRUE(result.empty());
+}
+
+TEST(TrieTest, CanGetDataByExactKey) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kKey[] = {1, 2, 3};
+  static const int32_t kKeySize = 3;
+  trie.AddDataForKey(kKey, kKeySize, "world");
+  trie.FindDataForKeyPrefix(kKey, kKeySize, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, CanGetDataByPrefix) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kKey[] = {1, 2, 3, 4, 5};
+  trie.AddDataForKey(kKey, 5, "world");
+
+  static const uint8_t kPrefix[] = {1, 2, 3};
+  trie.FindDataForKeyPrefix(kPrefix, 3, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, KeyTooLongNoData) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kKey[] = {1, 2, 3};
+  trie.AddDataForKey(kKey, 3, "world");
+
+  static const uint8_t kTooLong[] = {1, 2, 3, 4};
+  trie.FindDataForKeyPrefix(kTooLong, 4, &result);
+
+  EXPECT_TRUE(result.empty());
+}
+
+TEST(TrieTest, CommonPrefixFindsMultipleData) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kHello[] = {1, 2, 3};
+  trie.AddDataForKey(kHello, 3, "world");
+
+  static const uint8_t kHowdy[] = {1, 4, 5};
+  trie.AddDataForKey(kHowdy, 3, "buddy");
+
+  static const uint8_t kFoo[] = {3, 2, 1};
+  trie.AddDataForKey(kFoo, 3, "bar");
+
+  static const uint8_t kPrefix[] = {1};
+  trie.FindDataForKeyPrefix(kPrefix, 1, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("buddy");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, KeyCanBePrefixOfOtherKey) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kHello[] = {1, 2};
+  trie.AddDataForKey(kHello, 2, "world");
+
+  static const uint8_t kHelloo[] = {1, 2, 3};
+  trie.AddDataForKey(kHelloo, 3, "woorld");
+
+  static const uint8_t kHella[] = {1, 3, 4};
+  trie.AddDataForKey(kHella, 3, "warld");
+
+  trie.FindDataForKeyPrefix(kHello, 2, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("woorld");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, AllowMutlipleKeys) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kHello[] = {1, 2};
+  trie.AddDataForKey(kHello, 2, "world");
+  trie.AddDataForKey(kHello, 2, "woorld");
+
+  trie.FindDataForKeyPrefix(kHello, 2, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  expected.insert("woorld");
+  EXPECT_EQ(expected, result);
+}
+
+TEST(TrieTest, CanFindVeryLongKey) {
+  Trie<std::string> trie;
+  std::set<std::string> result;
+
+  static const uint8_t kVeryLongKey[] = {
+      9, 3, 2, 6, 7, 0, 2, 7, 9, 3, 6, 8, 9, 2, 1, 6, 1, 5, 0, 3, 5};
+  static const size_t kKeySize = sizeof kVeryLongKey;
+  trie.AddDataForKey(kVeryLongKey, kKeySize, "world");
+
+  trie.FindDataForKeyPrefix(kVeryLongKey, kKeySize, &result);
+
+  std::set<std::string> expected;
+  expected.insert("world");
+  EXPECT_EQ(expected, result);
+}
+
+}  // namespace autofill