Generic Gap Buffer data structure

base/gap_buffer.h

+// 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.
+
+#ifndef BASE_GAP_BUFFER_H_
+#define BASE_GAP_BUFFER_H_
+#pragma once
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+
+namespace base {
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// This class implements a standard GapBuffer
+// (http://en.wikipedia.org/wiki/Gap_buffer)
+//
+////////////////////////////////////////////////////////////////////////////////
+template<class T>
+class GapBuffer {
+ public:
+  // Constructor. The initial size of the buffer can be specified in the
+  // argument (defaults to 10).
+  explicit GapBuffer(int size) {
+    if (size < kMinResizeAmount) {
+      size = kMinResizeAmount;
+    }
+
+    buffer_.reset(new T[size]);
+    buffer_size_ = size;
+    gap_start_ = 0;
+    gap_end_ = buffer_size_;
+  }
+
+  // Constructor. Initializes the gap buffer with values from the input buffer.
+  GapBuffer(const T* buffer, int buffer_size) {
+    buffer_size_ = buffer_size + kMinResizeAmount;
+    buffer_.reset(new T[buffer_size_]);
+    gap_start_ = buffer_size;
+    gap_end_ = buffer_size_;
+    memmove(buffer_.get(), buffer, sizeof(T) * buffer_size);
+  }
+
+  // Moves the Gap left by "count" positions (until it hits the start of the
+  // buffer). The gap size remains constant. Contents from the start of the gap
+  // are moved to the end.
+  void MoveGapLeft(int count) {
+    if (buffer_.get() && gap_start_ > 0) {
+      int new_gap_start = (gap_start_ >= count)? gap_start_ - count : 0;
+      int num_elements = gap_start_ - new_gap_start;
+      memmove(buffer_.get() + gap_end_ - num_elements,
+          buffer_.get() + new_gap_start, sizeof(T) * num_elements);
+      gap_start_ = new_gap_start;
+      gap_end_ -= num_elements;
+    }
+  }
+
+  // Moves the Gap right by "count" positions (until it hits the end of the
+  // buffer). The gap size remains constant. Contents from the end of the gap
+  // are moved to the start.
+  void MoveGapRight(int count) {
+    if (gap_end_ < buffer_size_) {
+      int new_gap_end = (gap_end_ + count > buffer_size_)? buffer_size_
+          : gap_end_ + count;
+      int num_elements = new_gap_end - gap_end_;
+      memmove(buffer_.get() + gap_start_, buffer_.get() + gap_end_,
+          sizeof(T) * num_elements);
+      gap_start_ += num_elements;
+      gap_end_ = new_gap_end;
+    }
+  }
+
+  // Moves the Gap to the left until its just after the first occurrence of
+  // "object". If object is not found it moves the gap all the way to the
+  // beginning of the buffer.
+  void MoveGapLeftTo(T object) {
+    for (; gap_start_ > 0 && buffer_[gap_start_ - 1] != object;) {
+      MoveGapLeftByOne();
+    }
+  }
+
+  // Moves the Gap to the right until its just after the first occurrence of
+  // "object". If object is not found it moves the gap all the way to the end
+  // of the buffer.
+  void MoveGapRightTo(T object) {
+    for (; gap_end_ < buffer_size_ && buffer_[gap_end_] != object;) {
+      MoveGapRightByOne();
+    }
+    // Move one more space to get after the occurrence on "object".
+    MoveGapRight(1);
+  }
+
+  // Inserts one element in the gap at the beginning. Gap size decreases by one.
+  // If gap is full, it resizes the buffer_ to create gap and then inserts.
+  void InsertAtGapStart(T object) {
+    if (gap_start_ < gap_end_) {
+      buffer_[gap_start_] = object;
+      gap_start_++;
+    } else {
+      ResizeBuffer();
+      InsertAtGapStart(object);
+    }
+  }
+
+  // Removes an element from the beginning of the gap increasing the gap size
+  // by one (unless the gap is already at the beginning of the buffer). Returns
+  // a pointer to the element removed.
+  const T* RemoveFromGapStart() {
+    if (gap_start_ > 0) {
+      gap_start_--;
+      return buffer_.get() + gap_start_;
+    } else {
+      return NULL;
+    }
+  }
+
+  // Removes an element from the end of the gap increasing the gap size
+  // by one (unless the gap is already at the end of the buffer). Returns a
+  // pointer to the element removed.
+  const T* RemoveFromGapEnd() {
+    if (gap_end_ < buffer_size_) {
+      gap_end_++;
+      return buffer_.get() + gap_end_ - 1;
+    } else {
+      return NULL;
+    }
+  }
+
+  // Replaces the part of the buffer from "start" (inclusive) upto "end" with
+  // "replacement". Resizes the gap appropriately. <start-end> should not
+  // overlap with the gap.
+  // FIXME: implement this.
+  void Replace(int start, int end, T replacement) {
+    NOTIMPLEMENTED();
+  }
+
+  // Gets the contents of the buffer (removing the gap) in vector "contents".
+  void GetContents(std::vector<T>* contents) {
+    contents->clear();
+    int size = GetCurrentSize();
+    if (size) {
+      int i, j;
+      for (i = 0; i < gap_start_; i++) {
+        (*contents).push_back(buffer_[i]);
+      }
+      for (j = gap_end_; j < buffer_size_; j++, i++) {
+        (*contents).push_back(buffer_[j]);
+      }
+    }
+  }
+
+  // Gets the current number of elements in the buffer.
+  int GetCurrentSize() {
+    return buffer_size_ - (gap_end_ - gap_start_);
+  }
+
+  // Gets the size of the underlying buffer.
+  int GetBufferSize() {
+    return buffer_size_;
+  }
+
+  // Gets the gap_start_ index (essentially the current cursor position).
+  int GetGapStart() {
+    return gap_start_;
+  }
+
+ private:
+  // Increases the size of the buffer by 10% of current size. Unsafe.. assumes
+  // that the buffer is already allocated. Should not be invoked for
+  // un-initialized buffer.
+  // FIXME: explore more efficient resizing.
+  void ResizeBuffer() {
+    int size_increment = (buffer_size_ / 10.0 < kMinResizeAmount)?
+        kMinResizeAmount : buffer_size_ / 10.0;
+    int new_size = buffer_size_ + size_increment;
+    T* new_buffer = new T[new_size];
+    memmove(new_buffer, buffer_.get(), sizeof(T) * gap_start_);
+    memmove(new_buffer + gap_start_ + new_size, buffer_.get() + gap_end_,
+        sizeof(T) * (buffer_size_ - gap_end_));
+    gap_end_ = new_size - (buffer_size_ - gap_end_);
+    buffer_size_ = new_size;
+    buffer_.reset(new_buffer);
+  }
+
+  // Internal helper function. Should not be used on its own as it doesnot do
+  // any sanity checks. Use MoveGapLeft() or MoveGapLeftTo() instead.
+  void MoveGapLeftByOne() {
+    gap_start_--;
+    gap_end_--;
+    buffer_[gap_end_] = buffer_[gap_start_];
+  }
+
+  // Internal helper function. Should not be used on its own as it doesnot do
+  // any sanity checks. Use MoveGapRight() or MoveGapRightTo() instead.
+  void MoveGapRightByOne() {
+    buffer_[gap_start_] = buffer_[gap_end_];
+    gap_start_++;
+    gap_end_++;
+  }
+
+  scoped_array<T> buffer_;
+  int buffer_size_;
+  int gap_start_;
+  int gap_end_;
+
+  // In case of resizing the buffer, we will increase the length at least by
+  // kMinResizeAmount to avoid frequent resizing.
+  static const int kMinResizeAmount = 10;
+
+  DISALLOW_COPY_AND_ASSIGN(GapBuffer);
+};
+
+}  // namespace base
+
+#endif  // BASE_GAP_BUFFER_H_