third_party/libaddressinput/chromium/trie_unittest.cc

   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