Update re2

third_party/re2/util/sparse_array_test.cc

-// 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