Home | History | Annotate | Download | only in util 
      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 
     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:
     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 
     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 
     78 TEST_F(SparseArrayStringTest, FindDoesNotFindAbsentElement) {
     79   iterator it = str_map_.find(3);
     80   ASSERT_TRUE(str_map_.end() == it);
     81 }
     82 
     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 
     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 
     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 
    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 
    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 
    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 
    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 
    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