Generic Gap Buffer data structure

base/gap_buffer_unittest.cc

+// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+
+#include "base/gap_buffer.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+
+class GapBufferTester {
+ public:
+  GapBufferTester() { GapBufferTester(1, 'a'); }
+
+  GapBufferTester(int a, char b)
+      : a_(a),
+        b_(b) { }
+
+  // Overloading operator because it is required by the ElementsAreArrayMatcher.
+  bool operator==(const GapBufferTester& that) const {
+    return this->a_ == that.a_ && this->b_ == that.b_;
+  }
+
+ private:
+  int a_;
+  char b_;
+};
+
+template <class T>
+void Expectations(int current_size,
+                  int buffer_size,
+                  int contents_size,
+                  int gap_start,
+                  const T* contents_array,
+                  GapBuffer<T>* gap_buffer) {
+  std::vector<T> contents;
+  gap_buffer->GetContents(&contents);
+  EXPECT_EQ(buffer_size, gap_buffer->GetBufferSize());
+  EXPECT_EQ(current_size, gap_buffer->GetCurrentSize());
+  EXPECT_EQ(gap_start, gap_buffer->GetGapStart());
+  EXPECT_EQ(static_cast<size_t>(contents_size), contents.size());
+  EXPECT_THAT(contents,
+      testing::ElementsAreArray(contents_array, contents_size));
+}
+
+GapBufferTester* GenerateTestData(int count) {
+  GapBufferTester* data = new GapBufferTester[count];
+  for (int i = 0; i < count; i++) {
+    data[i] = GapBufferTester(i, static_cast<int>('a') + i);
+  }
+  return data;
+}
+
+TEST(GapBufferTest, InitializationTest) {
+  scoped_array<int> array;
+  GapBuffer<int> gap_buffer(20);
+  array.reset(new int[0]);
+  Expectations(0, 20, 0, 0, array.get(), &gap_buffer);
+}
+
+TEST(GapBufferTest, InsertionTest) {
+  GapBuffer<wchar_t> gap_buffer(20);
+  gap_buffer.InsertAtGapStart('a');
+  Expectations(1, 20, 1, 1, L"a", &gap_buffer);
+
+  gap_buffer.InsertAtGapStart(' ');
+  gap_buffer.InsertAtGapStart('t');
+  gap_buffer.InsertAtGapStart('e');
+  gap_buffer.InsertAtGapStart('s');
+  gap_buffer.InsertAtGapStart('t');
+  Expectations(6, 20, 6, 6, L"a test", &gap_buffer);
+}
+
+TEST(GapBufferTest, DeletionTest) {
+  scoped_array<GapBufferTester> array;
+  GapBuffer<GapBufferTester> gap_buffer(10);
+  array.reset(new GapBufferTester[0]);
+  Expectations(0, 10, 0, 0, array.get(), &gap_buffer);
+
+  // try to remove on empty buffer.
+  gap_buffer.RemoveFromGapStart();
+  gap_buffer.RemoveFromGapEnd();
+  Expectations(0, 10, 0, 0, array.get(), &gap_buffer);
+
+  // generate some test data.
+  array.reset(GenerateTestData(5));
+
+  // fill up the gap buffer.
+  for (int i = 0; i < 5; i++) {
+    gap_buffer.InsertAtGapStart(array[i]);
+  }
+  Expectations(5, 10, 5, 5, array.get(), &gap_buffer);
+
+  // move the gap around so that we can get data on either end of the gap.
+  gap_buffer.MoveGapLeft(3);
+  gap_buffer.MoveGapRight(1);
+  Expectations(5, 10, 5, 3, array.get(), &gap_buffer);
+
+  // remove some stuff.
+  gap_buffer.RemoveFromGapEnd();
+  // update the expected array.
+  array.get()[3] = array[4];
+  Expectations(4, 10, 4, 3, array.get(), &gap_buffer);
+  gap_buffer.RemoveFromGapStart();
+  // update the expected array.
+  array.get()[2] = array[3];
+  Expectations(3, 10, 3, 2, array.get(), &gap_buffer);
+  // try to remove more than available.
+  gap_buffer.RemoveFromGapEnd();
+  gap_buffer.RemoveFromGapEnd();
+  gap_buffer.RemoveFromGapEnd();
+  Expectations(2, 10, 2, 2, array.get(), &gap_buffer);
+  // now from the start.
+  gap_buffer.RemoveFromGapStart();
+  gap_buffer.RemoveFromGapStart();
+  gap_buffer.RemoveFromGapStart();
+  Expectations(0, 10, 0, 0, array.get(), &gap_buffer);
+}
+
+TEST(GapBufferTest, GapMoveTest) {
+  // generate some test data.
+  scoped_array<GapBufferTester> array;
+  array.reset(GenerateTestData(26));
+
+  GapBuffer<GapBufferTester> gap_buffer(array.get(), 26);
+  Expectations(26, 36, 26, 26, array.get(), &gap_buffer);
+
+  // Move the gap around
+  gap_buffer.MoveGapLeft(20);
+  Expectations(26, 36, 26, 6, array.get(), &gap_buffer);
+  gap_buffer.MoveGapRight(15);
+  Expectations(26, 36, 26, 21, array.get(), &gap_buffer);
+}
+
+TEST(GapBufferTest, ReziseTest) {
+  scoped_array<GapBufferTester> array;
+  GapBuffer<GapBufferTester> gap_buffer(10);
+  array.reset(new GapBufferTester[0]);
+  Expectations(0, 10, 0, 0, array.get(), &gap_buffer);
+
+  // generate some test data.
+  array.reset(GenerateTestData(1000));
+
+  // fill up the gap buffer.
+  for (int i = 0; i < 1000; i++) {
+    gap_buffer.InsertAtGapStart(array[i]);
+  }
+
+  // the buffer must have resized. It increases 10% of its current size (or 10,
+  // which ever is greater) on every resize. The final size should be 1053.
+  Expectations(1000, 1053, 1000, 1000, array.get(), &gap_buffer);
+}
+
+TEST(GapBufferTest, ConstructorTest) {
+  // generate some test data.
+  scoped_array<GapBufferTester> array;
+  array.reset(GenerateTestData(1000));
+
+  GapBuffer<GapBufferTester> gap_buffer(array.get(), 1000);
+  Expectations(1000, 1010, 1000, 1000, array.get(), &gap_buffer);
+}
+
+}  // namespace