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