Model, View and Controller for a Gap Buffer based one line text field in view...

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.
+
+// This class implements a standard GapBuffer

[sky, 2010/08/31 23:19:47]

Put the comment above the class name.

[varunjain, 2010/11/18 03:45:57]

Done.

+// (http://en.wikipedia.org/wiki/Gap_buffer)
+
+#ifndef BASE_GAP_BUFFER_H_
+#define BASE_GAP_BUFFER_H_
+#pragma once
+
+#include <stdio.h>
+
+#include <string>

[sky, 2010/08/31 23:19:47]

Do you need this include?

[varunjain, 2010/11/18 03:45:57]

Done.

+#include <vector>
+#include "base/basictypes.h"

[sky, 2010/08/31 23:19:47]

newline between 15 and 16.

[varunjain, 2010/11/18 03:45:57]

Done.

+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+
+namespace base {
+
+template<class T>

[sky, 2010/08/31 23:19:47]

Is it really worth parameterizing the type? At some point we want to move views
off of wstring, and at that point we would presumably convert this too.

[varunjain, 2010/11/18 03:45:57]

my intention was exactly to avoid changes to this class when changing string
implementations. This is fairly small class and should not bloat too much due to
parameterization.

+class GapBuffer {
+ public:
+

[sky, 2010/08/31 23:19:47]

no newline here.

[varunjain, 2010/11/18 03:45:57]

Done.

+  // Constructor. The initial size of the buffer can be specified in the
+  // argument (defaults to 10).
+  explicit GapBuffer(int size)
+      : kMinResizeAmount(10) {
+    if (size < kMinResizeAmount) {
+      size = kMinResizeAmount;
+    }
+
+    buffer_.reset(new T[size]);
+    if (buffer_.get()) {

[sky, 2010/08/31 23:19:47]

We don't do checks like this. OOM triggers a crash.

[varunjain, 2010/11/18 03:45:57]

Done.

+      buffer_size_ = size;
+      gap_start_ = 0;
+      gap_end_ = buffer_size_;
+    } else {
+      LOG(INFO) << ">>error creating gap buffer\n";
+    }
+  }
+
+  // Constructor. Initializes the gap buffer with values from the input buffer.
+  GapBuffer(const T* buffer, int buffer_size)
+      : kMinResizeAmount(10) {
+    buffer_size_ = buffer_size + kMinResizeAmount;
+    buffer_.reset(new T[buffer_size_]);
+    if (buffer_.get()) {

[sky, 2010/08/31 23:19:47]

Same comment as on line 35.

[varunjain, 2010/11/18 03:45:57]

Done.

+      gap_start_ = buffer_size;
+      gap_end_ = buffer_size_;
+      memmove(buffer_.get(), buffer, sizeof(T) * buffer_size);
+    } else {
+      LOG(INFO) << ">>error creating gap buffer\n";
+    }
+  }
+
+  // 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) {

[sky, 2010/08/31 23:19:47]

Do we really need all these MoveGapFoo methods? Can't we just have MoveGapTo ?
Also, shouldn't these DCHECK if attempted to move to an invalid location?

[varunjain, 2010/11/18 03:45:57]

Since gap buffers are really only used in text editing, I meant to provide the
api to reflect the actions one might do in a text editor.
As in a text editor if you try to move the cursor (gap) out of bounds, say to a
position after the end of text then we simply move it to the end of text.

+    if (buffer_.get() && gap_start_ > 0) {

[sky, 2010/08/31 23:19:47]

Don't check buffer_.get() at all in this class.

[varunjain, 2010/11/18 03:45:57]

Done.

+      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 (buffer_.get() && 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) {
+    if (buffer_.get()) {
+      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) {
+    if (buffer_.get()) {
+      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 (buffer_.get()) {
+      if (gap_start_ < gap_end_) {
+        buffer_.get()[gap_start_] = object;

[sky, 2010/08/31 23:19:47]

buffer_[gap_start]

[varunjain, 2010/11/18 03:45:57]

Done.

+        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
+  // the element removed.
+  T RemoveFromGapStart() {
+    if (buffer_.get() && gap_start_ > 0) {
+      gap_start_--;
+      return buffer_[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 the
+  // element removed.
+  T RemoveFromGapEnd() {
+    if (buffer_.get() && gap_end_ < buffer_size_) {
+      gap_end_++;
+      return buffer_[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) { }
+
+  // Gets the contents of the buffer (removing the gap) in vector "contents".
+  void GetContents(std::vector<T>* contents) {
+    (*contents).clear();

[sky, 2010/08/31 23:19:47]

contents->

[varunjain, 2010/11/18 03:45:57]

Done.

+    int size = GetCurrentSize();
+    if (buffer_.get() && 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_.get()? buffer_size_ - (gap_end_ - gap_start_) : 0;
+  }
+
+  // Gets the size of the underlying buffer.
+  int GetBufferSize() {

[sky, 2010/08/31 23:19:47]

Is there a case where someone cares about GetBufferSize()? Seems like an
implementation detail, and if you keep public it's easy to mistake it for
GetCurrentSize.

[varunjain, 2010/11/18 03:45:57]

Done.

+    return buffer_.get()? buffer_size_ : 0;
+  }
+
+  // Gets the gap_start_ index (essentially the current cursor position).
+  int GetGapStart() {
+    return buffer_.get()? gap_start_ : 0;
+  }
+
+ 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];
+    int i;
+    for (i = 0; i < gap_start_; i++) {

[sky, 2010/08/31 23:19:47]

How come you don't memmove these two blocks?

[varunjain, 2010/11/18 03:45:57]

Done.

+      new_buffer[i] = buffer_[i];
+    }
+    for (i = 0; i < buffer_size_ - gap_end_; i++) {
+      new_buffer[new_size - i - 1] = buffer_[buffer_size_ - i - 1];
+    }
+    gap_end_ = new_size - i;
+    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_.get()[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_.get()[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.
+  const int kMinResizeAmount;

[sky, 2010/08/31 23:19:47]

This should be static.

[varunjain, 2010/11/18 03:45:57]

Done.

+};

[sky, 2010/08/31 23:19:47]

DISALLOW_COPY_AND_ASSIGN

[varunjain, 2010/11/18 03:45:57]

Done.

+
+}  // namespace
+
+#endif  // BASE_GAP_BUFFER_H_