sparse_array_test.cc revision 5821806d5e7f356e8fa4b058a389a808ea183019 
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
10namespace re2 {
11
12static const string kNotFound = "NOT FOUND";
13
14TEST(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
58class SparseArrayStringTest : public testing::Test {
59 protected:
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
72TEST_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
78TEST_F(SparseArrayStringTest, FindDoesNotFindAbsentElement) {
79  iterator it = str_map_.find(3);
80  ASSERT_TRUE(str_map_.end() == it);
81}
82
83TEST_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
89TEST_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
97TEST(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
108typedef SparseArrayStringTest SparseArrayStringSurvivesInvalidIndexTest;
109// TODO(jyasskin): Cover invalid arguments to every method.
110
111TEST_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
118TEST_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
125TEST_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
132TEST_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
143TEST_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