2 files changed, 366 insertions, 0 deletions
diff --git a/gapbuffer/gap.go b/gapbuffer/gap.go
new file mode 100644
index 0000000..5bf9ca6
--- /dev/null
+++ b/gapbuffer/gap.go
@@ -0,0 +1,189 @@
+package gapbuffer
+
+import (
+	"errors"
+	"io"
+)
+
+// BUFSIZE is the initial size of the Buffer when calling New().
+const BUFSIZE = 64
+
+// ErrOutOfRange is returned when given position is out of range for the buffer.
+var ErrOutOfRange = errors.New("index out of range")
+
+type Buffer struct {
+	data  []byte
+	start int // gap start, is considered empty
+	end   int // gap end, holds next byte counting from before the gap
+}
+
+func New() *Buffer {
+	return &Buffer{
+		data:  make([]byte, BUFSIZE),
+		start: 0,
+		end:   BUFSIZE,
+	}
+}
+
+func (b *Buffer) Bytes() []byte {
+	buf := make([]byte, b.Len())
+	b.ReadAt(buf, 0)
+	return buf
+}
+
+// Destroy will erase the Buffer by zeroising all fields.
+func (b *Buffer) Destroy() {
+	b.start = 0
+	b.end = len(b.data)
+}
+
+// Byte returns current byte right after the gap. If the gap is at the end, the return will be 0.
+func (b *Buffer) Byte() byte {
+	if b.end >= len(b.data) {
+		return 0 // EOF
+	}
+
+	return b.data[b.end]
+}
+
+// ByteAt returns the byte at the given offset, ignoring and hiding the gap.
+func (b *Buffer) ByteAt(offset int) (byte, error) {
+	if offset >= b.start {
+		offset += b.gapLen()
+	}
+
+	if offset < 0 {
+		return 0, ErrOutOfRange
+	}
+	if offset >= len(b.data) {
+		return 0, io.EOF
+	}
+
+	return b.data[offset], nil
+}
+
+// gapLen returns the length of the gap.
+func (b *Buffer) gapLen() int {
+	return b.end - b.start
+}
+
+// Len returns the length of actual data.
+func (b *Buffer) Len() int {
+	return len(b.data) - b.gapLen()
+}
+
+// Cap returns the capacity of the Buffer, including the gap.
+func (b *Buffer) Cap() int {
+	return cap(b.data)
+}
+
+// Pos returns the current start position of the gap. This is where next write will appear.
+func (b *Buffer) Pos() int {
+	return b.start
+}
+
+// Seek is moving the gap to a given offset from origin.
+func (b *Buffer) Seek(newpos int) {
+	// out of range
+	if newpos < 0 {
+		b.Seek(0)
+		return
+	}
+	if newpos > b.Len() {
+		b.Seek(b.Len())
+		return
+	}
+
+	if newpos < b.start { // move backwards
+		for b.start > newpos {
+			b.backward()
+		}
+	} else if newpos > b.start { // move forward
+		for b.start < newpos {
+			b.forward()
+		}
+	}
+}
+
+// Forward is moving the gap one byte forward.
+func (b *Buffer) forward() {
+	if b.end >= len(b.data) {
+		return
+	}
+	b.data[b.start] = b.data[b.end]
+	b.start++
+	b.end++
+}
+
+// Backward is moving the gap one byte backwards.
+func (b *Buffer) backward() {
+	if b.start <= 0 {
+		return
+	}
+	b.data[b.end-1] = b.data[b.start-1]
+	b.start--
+	b.end--
+}
+
+// Delete will expand the gap by 1, deleting the character before the gap. Returns the byte that was deleted.
+func (b *Buffer) Delete() byte {
+	if b.start-1 < 0 {
+		return 0
+	}
+	b.start--
+	return b.data[b.start]
+}
+
+// Write writes p into the Buffer at current gap position. The Buffer will expand if needed and this is the only time any new memory allocation is done. The resizing and expanding strategy is handled by the underlying internal byte slice. Cap() will return the size of this slice.
+//
+// It will never return any other error than nil.
+func (b *Buffer) Write(p []byte) (int, error) {
+	if p == nil {
+		return 0, nil
+	}
+	for _, c := range p {
+		if b.gapLen() == 0 {
+			oldpos := b.start
+			b.Seek(cap(b.data))
+
+			b.data = append(b.data, 0)
+			exp := cap(b.data)
+			b.end += exp + 1
+
+			fill := make([]byte, exp)
+			b.data = append(b.data, fill...)
+
+			b.Seek(oldpos)
+		}
+		b.data[b.start] = c
+		b.start++
+	}
+	return len(p), nil
+}
+
+// Read implements io.Reader, returning number of bytes from the Buffer while ignoring the gap.
+func (b *Buffer) Read(p []byte) (int, error) {
+	return b.ReadAt(p, b.end)
+}
+
+// ReadAt fills p with bytes starting at offset from the Buffer, ignoring the gap. Returns number of bytes and an error.
+func (b *Buffer) ReadAt(p []byte, offset int) (n int, err error) {
+	if offset < 0 {
+		return 0, ErrOutOfRange
+	}
+	if offset >= b.Len() {
+		return 0, io.EOF
+	}
+
+	for n = 0; n < len(p) && offset < b.Len(); n++ {
+		c, err := b.ByteAt(offset)
+		if err != nil {
+			return n, err
+		}
+
+		p[n] = c
+		offset++
+	}
+
+	return n, nil
+}
diff --git a/gapbuffer/gap_test.go b/gapbuffer/gap_test.go
new file mode 100644
index 0000000..a1eadb0
--- /dev/null
+++ b/gapbuffer/gap_test.go
@@ -0,0 +1,177 @@
+package gapbuffer_test
+
+import (
+	"io"
+	"testing"
+
+	"github.com/prodhe/poe/gapbuffer"
+)
+
+const lipsum = `Fusce vitae molestie tortor. Fusce congue ornare risus vitae dignissim. Praesent volutpat erat sit amet posuere varius. Fusce id fermentum risus. In ac eros varius, fringilla erat ac, cursus odio. Nunc consectetur vitae dolor non cursus. Sed eleifend imperdiet sem sit amet rutrum. Nulla pretium et ante eu lobortis. Suspendisse porta sodales fermentum.
+
+Proin dignissim lorem sed leo aliquam rutrum. Donec vel lorem vitae dui mollis lobortis. Nam ac ornare tellus, ac venenatis nulla. Curabitur sagittis at nulla id blandit. Curabitur porta sit amet orci sed aliquam. Duis fermentum tincidunt rutrum. Morbi varius blandit velit in interdum. Cras congue pretium nisl nec interdum.
+
+Sed rutrum risus sed mauris cursus, nec viverra dolor blandit. Vestibulum commodo malesuada felis vitae varius. Nulla euismod id felis eu pulvinar. Fusce nisl mauris, pretium quis dignissim sit amet, consequat sed tortor. Vestibulum sollicitudin mi risus, vitae porta dolor semper vitae. Vestibulum tristique libero ac mauris tristique, at blandit ipsum facilisis. In mollis diam a dapibus fermentum. Phasellus laoreet diam id pretium faucibus. Orci varius natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Suspendisse ornare velit eget lorem tincidunt vehicula. Duis purus augue, finibus ut dolor nec, tempor vulputate ipsum. Ut pellentesque id sem quis luctus. Integer tristique facilisis eleifend. Sed at egestas risus.`
+
+func sliceEqual(a []byte, b []byte) bool {
+	if len(a) != len(b) {
+		return false
+	}
+	for i := range a {
+		if a[i] != b[i] {
+			return false
+		}
+	}
+	return true
+}
+
+func TestReadAt(t *testing.T) {
+	gb := gapbuffer.New()
+	gb.Write([]byte(lipsum))
+
+	var tt = []struct {
+		name      string
+		offset    int
+		len       int
+		want      int
+		wantbytes []byte
+		wanterr   error
+	}{
+		{"first", 0, 11, 11, []byte("Fusce vitae"), nil},
+		{"middle", 21, 20, 20, []byte("tortor. Fusce congue"), nil},
+		{"last", gb.Len() - 1, 1, 1, []byte("."), nil},
+		{"out of range below", -1, 0, 0, nil, gapbuffer.ErrOutOfRange},
+		{"out of range above", 9999, 0, 0, nil, io.EOF},
+	}
+
+	for _, tc := range tt {
+		b := make([]byte, tc.len)
+		gb.Seek(0)
+		n, err := gb.ReadAt(b, tc.offset)
+		if n != tc.len || err != tc.wanterr || !sliceEqual(b, tc.wantbytes) {
+			t.Errorf("seek 0: %s: expected %q %x (%d) (err: %v) (len: %d), got %q %x (%d) (err: %v) (len: %d)", tc.name, tc.wantbytes, tc.wantbytes, tc.want, tc.wanterr, tc.len, b, b, n, err, len(b))
+		}
+	}
+}
+
+func TestSeekAndPos(t *testing.T) {
+	gb := gapbuffer.New()
+	gb.Write([]byte(lipsum))
+
+	var tt = []struct {
+		name   string
+		offset int
+		want   int
+	}{
+		{"beginning", 0, 0},
+		{"middle", 25, 25},
+		{"end", len(lipsum), len(lipsum)},
+	}
+
+	for _, tc := range tt {
+		gb.Seek(tc.offset)
+		pos := gb.Pos()
+		if pos != tc.want {
+			t.Errorf("%s: set %d, expected %d, got %d", tc.name, tc.offset, tc.want, pos)
+		}
+	}
+}
+
+func TestWriteSingle(t *testing.T) {
+	var tt = []struct {
+		name       string
+		input      []byte
+		wantret    int
+		wantreterr error
+	}{
+		{"nil", nil, 0, nil},
+		{"empty", []byte{}, 0, nil},
+		{"null byte", []byte{'0'}, 1, nil},
+		{"string", []byte("gopher"), 6, nil},
+		{"control characters", []byte{'\u0011', '\u0012', '\u0013'}, 3, nil},
+	}
+
+	for _, tc := range tt {
+		b := gapbuffer.New()
+		n, err := b.Write(tc.input)
+		if n != tc.wantret {
+			t.Errorf("%s: expected %d bytes, got %d", tc.name, tc.wantret, n)
+		}
+		if err != tc.wantreterr {
+			t.Errorf("%s: expected error %v, got %v", tc.name, tc.wantreterr, err)
+		}
+	}
+}
+
+func TestWriteMulti(t *testing.T) {
+	var tt = []struct {
+		name   string
+		input1 []byte
+		offset int
+		input2 []byte
+		want   []byte
+	}{
+		{"beginning", []byte("bar"), 0, []byte("foo"), []byte("foobar")},
+		{"end", []byte("foo"), 3, []byte("bar"), []byte("foobar")},
+		{"middle", []byte("hello gopher"), 5, []byte(" you"), []byte("hello you gopher")},
+		{"expand buffer", []byte("abcdefghijklmnopqrstuvwxyz"), 8, []byte("0123456789"), []byte("abcdefgh0123456789ijklmnopqrstuvwxyz")},
+	}
+
+	for _, tc := range tt {
+		b := gapbuffer.New()
+		b.Write(tc.input1)
+		b.Seek(tc.offset)
+		b.Write(tc.input2)
+		data := b.Bytes()
+		if !sliceEqual(data, tc.want) {
+			t.Errorf("%s: wrote %q, then %q at offset %d, got %q (len: %d, cap: %d)", tc.name, tc.input1, tc.input2, tc.offset, data, b.Len(), b.Cap())
+		}
+	}
+}
+
+func TestByteAt(t *testing.T) {
+	var tt = []struct {
+		name    string
+		input   []byte
+		pos     int
+		want    byte
+		wanterr error
+	}{
+		{"first", []byte("abcdefghij"), 0, 'a', nil},
+		{"middle", []byte("abcdefghij"), 4, 'e', nil},
+		{"last", []byte("abcdefghij"), 9, 'j', nil},
+		{"lipsum", []byte(lipsum), 40, 'e', nil},
+		{"out of range below", []byte("abcdefghij"), -1, 0, gapbuffer.ErrOutOfRange},
+		{"out of range above", []byte("abcdefghij"), 999, 0, gapbuffer.ErrOutOfRange},
+	}
+
+	for _, tc := range tt {
+		b := gapbuffer.New()
+		b.Write(tc.input)
+		b.Seek(0)
+		c, err := b.ByteAt(tc.pos)
+		if c != tc.want {
+			t.Errorf("Seek(0): %s: expected %c (%x) and %v, got %c (%x) and %v", tc.name, tc.want, tc.want, tc.wanterr, c, c, err)
+		}
+	}
+
+	for _, tc := range tt {
+		b := gapbuffer.New()
+		b.Write(tc.input)
+		b.Seek(2)
+		c, err := b.ByteAt(tc.pos)
+		if c != tc.want {
+			t.Errorf("Seek(2): %s: expected %c (%x) and %v, got %c (%x) and %v", tc.name, tc.want, tc.want, tc.wanterr, c, c, err)
+		}
+	}
+
+	for _, tc := range tt {
+		b := gapbuffer.New()
+		b.Write(tc.input)
+		b.Seek(b.Len())
+		c, err := b.ByteAt(tc.pos)
+		if c != tc.want {
+			t.Errorf("Seek(len): %s: expected %c (%x) and %v, got %c (%x) and %v", tc.name, tc.want, tc.want, tc.wanterr, c, c, err)
+		}
+	}
+}