1 files changed, 295 insertions, 6 deletions
diff --git a/test/gtest_unittest.cc b/test/gtest_unittest.cc
index ba39ae6..5c69b46 100644
--- a/test/gtest_unittest.cc
+++ b/test/gtest_unittest.cc
@@ -180,6 +180,19 @@ using testing::internal::kMaxRandomSeed;
 using testing::internal::kTestTypeIdInGoogleTest;
 using testing::internal::scoped_ptr;
 
+class TestingVector : public Vector<int> {
+};
+
+::std::ostream& operator<<(::std::ostream& os,
+                           const TestingVector& vector) {
+  os << "{ ";
+  for (int i = 0; i < vector.size(); i++) {
+    os << vector.GetElement(i) << " ";
+  }
+  os << "}";
+  return os;
+}
+
 // This line tests that we can define tests in an unnamed namespace.
 namespace {
 
@@ -677,6 +690,53 @@ TEST(VectorTest, GetElementOr) {
   EXPECT_EQ('x', a.GetElementOr(2, 'x'));
 }
 
+TEST(VectorTest, Swap) {
+  Vector<int> a;
+  a.PushBack(0);
+  a.PushBack(1);
+  a.PushBack(2);
+
+  // Swaps an element with itself.
+  a.Swap(0, 0);
+  ASSERT_EQ(0, a.GetElement(0));
+  ASSERT_EQ(1, a.GetElement(1));
+  ASSERT_EQ(2, a.GetElement(2));
+
+  // Swaps two different elements where the indices go up.
+  a.Swap(0, 1);
+  ASSERT_EQ(1, a.GetElement(0));
+  ASSERT_EQ(0, a.GetElement(1));
+  ASSERT_EQ(2, a.GetElement(2));
+
+  // Swaps two different elements where the indices go down.
+  a.Swap(2, 0);
+  ASSERT_EQ(2, a.GetElement(0));
+  ASSERT_EQ(0, a.GetElement(1));
+  ASSERT_EQ(1, a.GetElement(2));
+}
+
+TEST(VectorTest, Clone) {
+  // Clones an empty Vector.
+  Vector<int> a;
+  scoped_ptr<Vector<int> > empty(a.Clone());
+  EXPECT_EQ(0, empty->size());
+
+  // Clones a singleton.
+  a.PushBack(42);
+  scoped_ptr<Vector<int> > singleton(a.Clone());
+  ASSERT_EQ(1, singleton->size());
+  EXPECT_EQ(42, singleton->GetElement(0));
+
+  // Clones a Vector with more elements.
+  a.PushBack(43);
+  a.PushBack(44);
+  scoped_ptr<Vector<int> > big(a.Clone());
+  ASSERT_EQ(3, big->size());
+  EXPECT_EQ(42, big->GetElement(0));
+  EXPECT_EQ(43, big->GetElement(1));
+  EXPECT_EQ(44, big->GetElement(2));
+}
+
 // Tests Vector::Erase().
 TEST(VectorDeathTest, Erase) {
   Vector<int> a;
@@ -740,23 +800,252 @@ TEST(VectorDeathTest, Erase) {
 }
 
 // Tests the GetElement accessor.
-TEST(ListDeathTest, GetElement) {
+TEST(VectorDeathTest, GetElement) {
   Vector<int> a;
   a.PushBack(0);
   a.PushBack(1);
   a.PushBack(2);
+  const Vector<int>& b = a;
+
+  EXPECT_EQ(0, b.GetElement(0));
+  EXPECT_EQ(1, b.GetElement(1));
+  EXPECT_EQ(2, b.GetElement(2));
+  EXPECT_DEATH_IF_SUPPORTED(
+      b.GetElement(3),
+      "Invalid Vector index 3: must be in range \\[0, 2\\]\\.");
+  EXPECT_DEATH_IF_SUPPORTED(
+      b.GetElement(-1),
+      "Invalid Vector index -1: must be in range \\[0, 2\\]\\.");
+}
+
+// Tests the GetMutableElement accessor.
+TEST(VectorDeathTest, GetMutableElement) {
+  Vector<int> a;
+  a.PushBack(0);
+  a.PushBack(1);
+  a.PushBack(2);
+
+  EXPECT_EQ(0, a.GetMutableElement(0));
+  EXPECT_EQ(1, a.GetMutableElement(1));
+  EXPECT_EQ(2, a.GetMutableElement(2));
+
+  a.GetMutableElement(0) = 42;
+  EXPECT_EQ(42, a.GetMutableElement(0));
+  EXPECT_EQ(1, a.GetMutableElement(1));
+  EXPECT_EQ(2, a.GetMutableElement(2));
 
-  EXPECT_EQ(0, a.GetElement(0));
-  EXPECT_EQ(1, a.GetElement(1));
-  EXPECT_EQ(2, a.GetElement(2));
   EXPECT_DEATH_IF_SUPPORTED(
-      a.GetElement(3),
+      a.GetMutableElement(3),
       "Invalid Vector index 3: must be in range \\[0, 2\\]\\.");
   EXPECT_DEATH_IF_SUPPORTED(
-      a.GetElement(-1),
+      a.GetMutableElement(-1),
       "Invalid Vector index -1: must be in range \\[0, 2\\]\\.");
 }
 
+TEST(VectorDeathTest, Swap) {
+  Vector<int> a;
+  a.PushBack(0);
+  a.PushBack(1);
+  a.PushBack(2);
+
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.Swap(-1, 1),
+      "Invalid first swap element -1: must be in range \\[0, 2\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.Swap(3, 1),
+      "Invalid first swap element 3: must be in range \\[0, 2\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.Swap(1, -1),
+      "Invalid second swap element -1: must be in range \\[0, 2\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.Swap(1, 3),
+      "Invalid second swap element 3: must be in range \\[0, 2\\]");
+}
+
+TEST(VectorDeathTest, ShuffleRange) {
+  Vector<int> a;
+  a.PushBack(0);
+  a.PushBack(1);
+  a.PushBack(2);
+  testing::internal::Random random(1);
+
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.ShuffleRange(&random, -1, 1),
+      "Invalid shuffle range start -1: must be in range \\[0, 3\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.ShuffleRange(&random, 4, 4),
+      "Invalid shuffle range start 4: must be in range \\[0, 3\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.ShuffleRange(&random, 3, 2),
+      "Invalid shuffle range finish 2: must be in range \\[3, 3\\]");
+  EXPECT_DEATH_IF_SUPPORTED(
+      a.ShuffleRange(&random, 3, 4),
+      "Invalid shuffle range finish 4: must be in range \\[3, 3\\]");
+}
+
+class VectorShuffleTest : public Test {
+ protected:
+  static const int kVectorSize = 20;
+
+  VectorShuffleTest() : random_(1) {
+    for (int i = 0; i < kVectorSize; i++) {
+      vector_.PushBack(i);
+    }
+  }
+
+  static bool VectorIsCorrupt(const TestingVector& vector) {
+    if (kVectorSize != vector.size()) {
+      return true;
+    }
+
+    bool found_in_vector[kVectorSize] = { false };
+    for (int i = 0; i < vector.size(); i++) {
+      const int e = vector.GetElement(i);
+      if (e < 0 || e >= kVectorSize || found_in_vector[e]) {
+        return true;
+      }
+      found_in_vector[e] = true;
+    }
+
+    // Vector size is correct, elements' range is correct, no
+    // duplicate elements.  Therefore no corruption has occurred.
+    return false;
+  }
+
+  static bool VectorIsNotCorrupt(const TestingVector& vector) {
+    return !VectorIsCorrupt(vector);
+  }
+
+  static bool RangeIsShuffled(const TestingVector& vector, int begin, int end) {
+    for (int i = begin; i < end; i++) {
+      if (i != vector.GetElement(i)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  static bool RangeIsUnshuffled(
+      const TestingVector& vector, int begin, int end) {
+    return !RangeIsShuffled(vector, begin, end);
+  }
+
+  static bool VectorIsShuffled(const TestingVector& vector) {
+    return RangeIsShuffled(vector, 0, vector.size());
+  }
+
+  static bool VectorIsUnshuffled(const TestingVector& vector) {
+    return !VectorIsShuffled(vector);
+  }
+
+  testing::internal::Random random_;
+  TestingVector vector_;
+};  // class VectorShuffleTest
+
+const int VectorShuffleTest::kVectorSize;
+
+TEST_F(VectorShuffleTest, HandlesEmptyRange) {
+  // Tests an empty range at the beginning...
+  vector_.ShuffleRange(&random_, 0, 0);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+
+  // ...in the middle...
+  vector_.ShuffleRange(&random_, kVectorSize/2, kVectorSize/2);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+
+  // ...at the end...
+  vector_.ShuffleRange(&random_, kVectorSize - 1, kVectorSize - 1);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+
+  // ...and past the end.
+  vector_.ShuffleRange(&random_, kVectorSize, kVectorSize);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+}
+
+TEST_F(VectorShuffleTest, HandlesRangeOfSizeOne) {
+  // Tests a size one range at the beginning...
+  vector_.ShuffleRange(&random_, 0, 1);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+
+  // ...in the middle...
+  vector_.ShuffleRange(&random_, kVectorSize/2, kVectorSize/2 + 1);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+
+  // ...and at the end.
+  vector_.ShuffleRange(&random_, kVectorSize - 1, kVectorSize);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsUnshuffled, vector_);
+}
+
+// Because we use our own random number generator and a fixed seed,
+// we can guarantee that the following "random" tests will succeed.
+
+TEST_F(VectorShuffleTest, ShufflesEntireVector) {
+  vector_.Shuffle(&random_);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  EXPECT_FALSE(VectorIsUnshuffled(vector_)) << vector_;
+
+  // Tests the first and last elements in particular to ensure that
+  // there are no off-by-one problems in our shuffle algorithm.
+  EXPECT_NE(0, vector_.GetElement(0));
+  EXPECT_NE(kVectorSize - 1, vector_.GetElement(kVectorSize - 1));
+}
+
+TEST_F(VectorShuffleTest, ShufflesStartOfVector) {
+  const int kRangeSize = kVectorSize/2;
+
+  vector_.ShuffleRange(&random_, 0, kRangeSize);
+
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  EXPECT_PRED3(RangeIsShuffled, vector_, 0, kRangeSize);
+  EXPECT_PRED3(RangeIsUnshuffled, vector_, kRangeSize, kVectorSize);
+}
+
+TEST_F(VectorShuffleTest, ShufflesEndOfVector) {
+  const int kRangeSize = kVectorSize / 2;
+  vector_.ShuffleRange(&random_, kRangeSize, kVectorSize);
+
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  EXPECT_PRED3(RangeIsUnshuffled, vector_, 0, kRangeSize);
+  EXPECT_PRED3(RangeIsShuffled, vector_, kRangeSize, kVectorSize);
+}
+
+TEST_F(VectorShuffleTest, ShufflesMiddleOfVector) {
+  int kRangeSize = kVectorSize/3;
+  vector_.ShuffleRange(&random_, kRangeSize, 2*kRangeSize);
+
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  EXPECT_PRED3(RangeIsUnshuffled, vector_, 0, kRangeSize);
+  EXPECT_PRED3(RangeIsShuffled, vector_, kRangeSize, 2*kRangeSize);
+  EXPECT_PRED3(RangeIsUnshuffled, vector_, 2*kRangeSize, kVectorSize);
+}
+
+TEST_F(VectorShuffleTest, ShufflesRepeatably) {
+  TestingVector vector2;
+  for (int i = 0; i < kVectorSize; i++) {
+    vector2.PushBack(i);
+  }
+
+  random_.Reseed(1234);
+  vector_.Shuffle(&random_);
+  random_.Reseed(1234);
+  vector2.Shuffle(&random_);
+
+  ASSERT_PRED1(VectorIsNotCorrupt, vector_);
+  ASSERT_PRED1(VectorIsNotCorrupt, vector2);
+
+  for (int i = 0; i < kVectorSize; i++) {
+    EXPECT_EQ(vector_.GetElement(i), vector2.GetElement(i))
+        << " where i is " << i;
+  }
+}
+
 // Tests the size of the AssertHelper class.
 
 TEST(AssertHelperTest, AssertHelperIsSmall) {