1 // Copyright 2006 The RE2 Authors. All Rights Reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // Simple tests that SparseArray behaves.
6
7 #include "util/util.h"
8 #include "utest/utest.h"
9
10 namespace re2 {
11
12 static const string kNotFound = "NOT FOUND";
13
TEST(SparseArray,BasicOperations)14 TEST(SparseArray, BasicOperations) {
15 static const int n = 50;
16 SparseArray<int> set(n);
17
18 int order[n];
19 int value[n];
20 for (int i = 0; i < n; i++)
21 order[i] = i;
22 for (int i = 0; i < n; i++)
23 value[i] = rand()%1000 + 1;
24 for (int i = 1; i < n; i++) {
25 int j = rand()%i;
26 int t = order[i];
27 order[i] = order[j];
28 order[j] = t;
29 }
30
31 for (int i = 0;; i++) {
32 for (int j = 0; j < i; j++) {
33 ASSERT_TRUE(set.has_index(order[j]));
34 ASSERT_EQ(value[order[j]], set.get(order[j], -1));
35 }
36 if (i >= n)
37 break;
38 for (int j = i; j < n; j++)
39 ASSERT_FALSE(set.has_index(order[j]));
40 set.set(order[i], value[order[i]]);
41 }
42
43 int nn = 0;
44 for (SparseArray<int>::iterator i = set.begin(); i != set.end(); ++i) {
45 ASSERT_EQ(order[nn++], i->index());
46 ASSERT_EQ(value[i->index()], i->value());
47 }
48 ASSERT_EQ(nn, n);
49
50 set.clear();
51 for (int i = 0; i < n; i++)
52 ASSERT_FALSE(set.has_index(i));
53
54 ASSERT_EQ(0, set.size());
55 ASSERT_EQ(0, distance(set.begin(), set.end()));
56 }
57
58 class SparseArrayStringTest : public testing::Test {
59 protected:
SparseArrayStringTest()60 SparseArrayStringTest()
61 : str_map_(10) {
62 InsertOrUpdate(&str_map_, 1, "a");
63 InsertOrUpdate(&str_map_, 5, "b");
64 InsertOrUpdate(&str_map_, 2, "c");
65 InsertOrUpdate(&str_map_, 7, "d");
66 }
67
68 SparseArray<string> str_map_;
69 typedef SparseArray<string>::iterator iterator;
70 };
71
TEST_F(SparseArrayStringTest,FindGetsPresentElement)72 TEST_F(SparseArrayStringTest, FindGetsPresentElement) {
73 iterator it = str_map_.find(2);
74 ASSERT_TRUE(str_map_.end() != it);
75 EXPECT_EQ("c", it->second);
76 }
77
TEST_F(SparseArrayStringTest,FindDoesNotFindAbsentElement)78 TEST_F(SparseArrayStringTest, FindDoesNotFindAbsentElement) {
79 iterator it = str_map_.find(3);
80 ASSERT_TRUE(str_map_.end() == it);
81 }
82
TEST_F(SparseArrayStringTest,ContainsKey)83 TEST_F(SparseArrayStringTest, ContainsKey) {
84 EXPECT_TRUE(ContainsKey(str_map_, 1));
85 EXPECT_TRUE(ContainsKey(str_map_, 2));
86 EXPECT_FALSE(ContainsKey(str_map_, 3));
87 }
88
TEST_F(SparseArrayStringTest,InsertIfNotPresent)89 TEST_F(SparseArrayStringTest, InsertIfNotPresent) {
90 EXPECT_FALSE(ContainsKey(str_map_, 3));
91 EXPECT_TRUE(InsertIfNotPresent(&str_map_, 3, "r"));
92 EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
93 EXPECT_FALSE(InsertIfNotPresent(&str_map_, 3, "other value"));
94 EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
95 }
96
TEST(SparseArrayTest,Erase)97 TEST(SparseArrayTest, Erase) {
98 SparseArray<string> str_map(5);
99 str_map.set(1, "a");
100 str_map.set(2, "b");
101 EXPECT_EQ("a", FindWithDefault(str_map, 1, kNotFound));
102 EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
103 str_map.erase(1);
104 EXPECT_EQ("NOT FOUND", FindWithDefault(str_map, 1, kNotFound));
105 EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
106 }
107
108 typedef SparseArrayStringTest SparseArrayStringSurvivesInvalidIndexTest;
109 // TODO(jyasskin): Cover invalid arguments to every method.
110
TEST_F(SparseArrayStringSurvivesInvalidIndexTest,SetNegative)111 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNegative) {
112 EXPECT_DEBUG_DEATH(str_map_.set(-123456789, "hi"),
113 "\\(jyasskin\\) Illegal index -123456789 passed to"
114 " SparseArray\\(10\\).set\\(\\).");
115 EXPECT_EQ(4, str_map_.size());
116 }
117
TEST_F(SparseArrayStringSurvivesInvalidIndexTest,SetTooBig)118 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetTooBig) {
119 EXPECT_DEBUG_DEATH(str_map_.set(12345678, "hi"),
120 "\\(jyasskin\\) Illegal index 12345678 passed to"
121 " SparseArray\\(10\\).set\\(\\).");
122 EXPECT_EQ(4, str_map_.size());
123 }
124
TEST_F(SparseArrayStringSurvivesInvalidIndexTest,SetNew_Negative)125 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Negative) {
126 EXPECT_DEBUG_DEATH(str_map_.set_new(-123456789, "hi"),
127 "\\(jyasskin\\) Illegal index -123456789 passed to"
128 " SparseArray\\(10\\).set_new\\(\\).");
129 EXPECT_EQ(4, str_map_.size());
130 }
131
TEST_F(SparseArrayStringSurvivesInvalidIndexTest,SetNew_Existing)132 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Existing) {
133 EXPECT_DEBUG_DEATH({
134 str_map_.set_new(2, "hi");
135 EXPECT_EQ("hi", FindWithDefault(str_map_, 2, kNotFound));
136
137 // The old value for 2 is still present, but can never be removed.
138 // This risks crashing later, if the map fills up.
139 EXPECT_EQ(5, str_map_.size());
140 }, "Check failed: !has_index\\(i\\)");
141 }
142
TEST_F(SparseArrayStringSurvivesInvalidIndexTest,SetNew_TooBig)143 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_TooBig) {
144 EXPECT_DEBUG_DEATH(str_map_.set_new(12345678, "hi"),
145 "\\(jyasskin\\) Illegal index 12345678 passed to"
146 " SparseArray\\(10\\).set_new\\(\\).");
147 EXPECT_EQ(4, str_map_.size());
148 }
149
150 } // namespace re2
151