Generic Gap Buffer data structure

Generic Gap Buffer data structure

BUG=none
TEST=unittest added for new GapBuffer class

[tfarina, 2010-11-18 12:03:22]

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h
File base/gap_buffer.h (right):

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode9
base/gap_buffer.h:9: #include <stdio.h>
Hum? Why do you need this here? If it is for memmove you can include string.h
instead.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode13
base/gap_buffer.h:13: #include "base/logging.h"
Do you this include here?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode27
base/gap_buffer.h:27: // Constructor. The initial size of the buffer can be
specified in the
Please, can you move the implementation of all these method to the source file?
With this is more easy to read the API of GapBuffer.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode216
base/gap_buffer.h:216: }  // namespace
// namespace base

[varunjain, 2010-11-18 17:53:44]

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h
File base/gap_buffer.h (right):

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode9
base/gap_buffer.h:9: #include <stdio.h>
On 2010/11/18 12:03:23, tfarina wrote:
> Hum? Why do you need this here? If it is for memmove you can include string.h
> instead.

removed

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode13
base/gap_buffer.h:13: #include "base/logging.h"
On 2010/11/18 12:03:23, tfarina wrote:
> Do you this include here?

I had NOTIMPLEMENTED() in one of the methods which I need this for. It somehow
got lost... but its back now.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode27
base/gap_buffer.h:27: // Constructor. The initial size of the buffer can be
specified in the
On 2010/11/18 12:03:23, tfarina wrote:
> Please, can you move the implementation of all these method to the source
file?
> With this is more easy to read the API of GapBuffer.

This is a template.. if I move the implementation to a source file linker will
not be able to generate the specific source

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode216
base/gap_buffer.h:216: }  // namespace
On 2010/11/18 12:03:23, tfarina wrote:
> // namespace base

Done.

[sky, 2010-11-18 18:26:07]

Meta comment.

I get that you're trying to implement gap buffer, but as the API stands it
exposes too much of the internals rather than an easy to use API.

I think you want at least two separate objects. One to maintain the contents of
the textfield. This can be as simple as:

class Contents {
  const string16& contents() const;
  void Remove(int offset, int count);
  void Insert(int offset, const string16& contents);
}

This is really all a consumer of this API should care about. Internally Contents
could be implemented as a gap buffer, but that's an implementation detail. So,
things like positioning the gap shouldn't even be exposed, they are done
implicitly as Remove/Insert is invoked.

You'll also care about selection, but that shouldn't be part of Contents. If you
intend for the textfield you're writing to be used by the Omnibox you'll need
the ability to mark up ranges of characters with styles. You might want that to
be part of Contents, but it can be dealt with later.

Can we have a simple API like I'm suggesting above?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h
File base/gap_buffer.h (right):

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode22
base/gap_buffer.h:22: //
You need some description of this class rather than a pointer to a wikipedia
article. At least describe the core concepts you refer to in descriptions like
buffer and gap.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode24
base/gap_buffer.h:24: template<class T>
We've trying to move all strings to string16. Could this be written only in
terms of string16?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode29
base/gap_buffer.h:29: explicit GapBuffer(int size) {
Is anyone really going to want to specify the initial buffer size? Should this
instead take no args?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode41
base/gap_buffer.h:41: GapBuffer(const T* buffer, int buffer_size) {
Use member initialize list for setting all fields.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode49
base/gap_buffer.h:49: // Moves the Gap left by "count" positions (until it hits
the start of the
Gap -> gap

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode52
base/gap_buffer.h:52: void MoveGapLeft(int count) {
Why do we have the move left/right. Can't it just be SetGapPosition() and
internally you do whatever you need to do?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode53
base/gap_buffer.h:53: if (buffer_.get() && gap_start_ > 0) {
Why do you check buffer_.get() here?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode81
base/gap_buffer.h:81: void MoveGapLeftTo(T object) {
Why is this and MoveGapRightTo needed?

[rjkroege, 2010-11-18 19:34:28]

assorted comments on an older revision.

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h
File base/gap_buffer.h (right):

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode20
base/gap_buffer.h:20: // This class implements a standard GapBuffer
I don't understand the "why" of your API.

I think that a gap buffer needs:
* MoveGapBy(int) where the int can be positive (forward) or negative (back)
* SetGapTo(unsigned) where the unsigned is a position into the contained string
* GetString which needs to be aligned with the downstream consumer's needs
(DrawStringInt) so ought to be a wstring perhaps.
* InsertRune (where rune has its plan9 meaning) and is a natural cast from
character code that you get from the event.
* A constructor taking a string.

I was (and remain) slightly doubtful that we need this to be templated and claim
that it would be easier to write without them. (Despite talking about how
important it is to learn template-fu yesterday. :-)

Please also be explicit about how you intend to handle UTF-blah because the user
of this class will want to operate in terms of character position. Based on the
wstring downstream, UTF-16 might be appropriate.

How will you manage the storage of metrics?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode49
base/gap_buffer.h:49: // Moves the Gap left by "count" positions (until it hits
the start of the
you can refactor move-left and move-right  into 1

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode141
base/gap_buffer.h:141: void GetContents(std::vector<T>* contents) {
ultimately, we'll want strings right? not a vector?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode172
base/gap_buffer.h:172: // that the buffer is already allocated. Should not be
invoked for
you should assert that the buffer has been initialized yes?

http://codereview.chromium.org/5158004/diff/4001/base/gap_buffer.h#newcode174
base/gap_buffer.h:174: // FIXME: explore more efficient resizing.
Given that this is a buffer that is backing the omnibox, I would recommend
growing it in 4kB increments.

[varunjain, 2010-11-18 20:35:19]

Hi Scott, Rob,

While I am taking care of code comments, I thought I would reply to the API
concerns you have raised..

@Scott
For a generic string data structure your API suffices. But for a gap buffer, I
think it is important to expose api for gap movement as well. You have to think
of it in terms of a textfield with a cursor. If the user moves the cursor for a
while and then inserts/deletes a char, your api will have to move the gap to the
new location at the time of insertion/deletion. Whereas, if the gap is moved
with the cursor (by exposing a MoveGapBlah API) then the cost of moving the gap
is amortized over all the cursor movements made by the user.
I am very open to changing the api... but I would request you to take into
consideration the various operations the user could perform on a textfield and
then evaluate the API I have written.

@Rob
the API that I have written is pretty much the same as yours with the following
differences:
1. Instead of moving based on the sign of the position I have two separate
methods for moving left or right. I think it is more readable and cleaner this
way but I can change it if you strongly feel about it.
2. I have two methods for moving the cursor (gap) to the first occurrence of a
particular character (in either direction). These were added for handling
Ctrl+<arrow-key>. In absence of these methods, the user will have to find the
end/beginning of word and move the gap to it. This will require getting
partial/all contents of the gap buffer creating unnecessary overhead.
3. For your InsertRune, I have 3 methods Insert(for inserting a character),
RemoveFromGapStart(for inserting backspace) and RemoveFromGapEnd(for inserting
delete). I can combine these into one if you like.

I get the feeling that you guys dont like the "Gap" exposed in the API. Is it
just a terminology issue? would it help if I called it "Cursor" in the method
names?

[Ben Goodger (Google), 2010-11-18 20:46:47]

This file should live in views/controls/textfield.

There is another effort under way to reduce the size of base/ to contain just
those system-level things that are used in many places. Since the target
audience of this API right now is just views/, we should host it there.

[sky, 2010-11-18 20:57:34]

On Thu, Nov 18, 2010 at 12:35 PM,  <varunjain@chromium.org> wrote:
> Hi Scott, Rob,
>
> While I am taking care of code comments, I thought I would reply to the API
> concerns you have raised..
>
> @Scott
> For a generic string data structure your API suffices. But for a gap buffer,
> I
> think it is important to expose api for gap movement as well.

Why? Like I said, why do you as the user of such an API care where the
gap is? Let the implementation deal with it.

> You have to
> think
> of it in terms of a textfield with a cursor. If the user moves the cursor
> for a
> while and then inserts/deletes a char, your api will have to move the gap to
> the
> new location at the time of insertion/deletion.

The API I am proposing does not explicitly move any gaps. It just
invokes insert/delete, the implementation takes care of whatever it
needs to do.

> Whereas, if the gap is moved
> with the cursor (by exposing a MoveGapBlah API) then the cost of moving the
> gap
> is amortized over all the cursor movements made by the user.

I find that hard to believe. But either way, this is hardly going to
be the expensive part of a textfield. In all honesty I wouldn't bother
designing this as a gap buffer now. I would be inclined to implement
it on top of string16. The important thing is to design a flexible API
that doesn't lock down the implementation. Your design is incredibly
specific and so mostly locks you down to a particular implementation.
If you go with what I have suggested you'll have the flexibility to
change the underlying storage without impacting users of the API.

> I am very open to changing the api... but I would request you to take into
> consideration the various operations the user could perform on a textfield
> and
> then evaluate the API I have written.

If anything the API I am proposing is more efficient than what you are
proposing. With what I'm suggesting the buffer only changes when you
need it to, not when the cursor changes.

Here's similar APIs from other platforms:

Mac:
http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundat...
Swing:
http://download.oracle.com/javase/1.4.2/docs/api/javax/swing/text/AbstractDoc...

  -Scott

> @Rob
> the API that I have written is pretty much the same as yours with the
> following
> differences:
> 1. Instead of moving based on the sign of the position I have two separate
> methods for moving left or right. I think it is more readable and cleaner
> this
> way but I can change it if you strongly feel about it.
> 2. I have two methods for moving the cursor (gap) to the first occurrence of
> a
> particular character (in either direction). These were added for handling
> Ctrl+<arrow-key>. In absence of these methods, the user will have to find
> the
> end/beginning of word and move the gap to it. This will require getting
> partial/all contents of the gap buffer creating unnecessary overhead.
> 3. For your InsertRune, I have 3 methods Insert(for inserting a character),
> RemoveFromGapStart(for inserting backspace) and RemoveFromGapEnd(for
> inserting
> delete). I can combine these into one if you like.
>
> I get the feeling that you guys dont like the "Gap" exposed in the API. Is
> it
> just a terminology issue? would it help if I called it "Cursor" in the
> method
> names?
>
> http://codereview.chromium.org/5158004/
>