From 4b748f68b851d1eea8edf188f5778975a45c5cfb Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 28 Aug 2016 14:06:37 +0200 Subject: Solve buffer --- go/circular-buffer/README.md | 64 +++++++++ go/circular-buffer/circular_buffer.go | 48 +++++++ go/circular-buffer/circular_buffer_test.go | 209 +++++++++++++++++++++++++++++ 3 files changed, 321 insertions(+) create mode 100644 go/circular-buffer/README.md create mode 100644 go/circular-buffer/circular_buffer.go create mode 100644 go/circular-buffer/circular_buffer_test.go diff --git a/go/circular-buffer/README.md b/go/circular-buffer/README.md new file mode 100644 index 0000000..ff9b795 --- /dev/null +++ b/go/circular-buffer/README.md @@ -0,0 +1,64 @@ +# Circular Buffer + +A data structure that uses a single, fixed-size buffer as if it were connected end-to-end. + +A circular buffer, cyclic buffer or ring buffer is a data structure that +uses a single, fixed-size buffer as if it were connected end-to-end. + +A circular buffer first starts empty and of some predefined length. For +example, this is a 7-element buffer: + + [ ][ ][ ][ ][ ][ ][ ] + +Assume that a 1 is written into the middle of the buffer (exact starting +location does not matter in a circular buffer): + + [ ][ ][ ][1][ ][ ][ ] + +Then assume that two more elements are added — 2 & 3 — which get +appended after the 1: + + [ ][ ][ ][1][2][3][ ] + +If two elements are then removed from the buffer, the oldest values +inside the buffer are removed. The two elements removed, in this case, +are 1 & 2, leaving the buffer with just a 3: + + [ ][ ][ ][ ][ ][3][ ] + +If the buffer has 7 elements then it is completely full: + + [6][7][8][9][3][4][5] + +When the buffer is full an error will be raised, alerting the client +that further writes are blocked until a slot becomes free. + +The client can opt to overwrite the oldest data with a forced write. In +this case, two more elements — A & B — are added and they overwrite the +3 & 4: + + [6][7][8][9][A][B][5] + +Finally, if two elements are now removed then what would be returned is +not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the +buffer with: + + [ ][7][8][9][A][B][ ] + +To run the tests simply run the command `go test` in the exercise directory. + +If the test suite contains benchmarks, you can run these with the `-bench` +flag: + + go test -bench . + +For more detailed info about the Go track see the [help +page](http://exercism.io/languages/go). + +## Source + +Wikipedia [http://en.wikipedia.org/wiki/Circular_buffer](http://en.wikipedia.org/wiki/Circular_buffer) + +## Submitting Incomplete Problems +It's possible to submit an incomplete solution so you can see how others have completed the exercise. + diff --git a/go/circular-buffer/circular_buffer.go b/go/circular-buffer/circular_buffer.go new file mode 100644 index 0000000..b17ea2b --- /dev/null +++ b/go/circular-buffer/circular_buffer.go @@ -0,0 +1,48 @@ +package circular + +import "errors" + +const testVersion = 3 + +type Buffer struct { + v []byte // values + rpos int // read position + wpos int // write position + n int // occupied cells +} + +func NewBuffer(size int) *Buffer { + return &Buffer{v: make([]byte, size)} +} + +func (b *Buffer) ReadByte() (byte, error) { + if b.n == 0 { + return 0, errors.New("empty") + } + val := b.v[b.rpos] + b.rpos = (b.rpos + 1) % len(b.v) + b.n-- + return val, nil +} + +func (b *Buffer) WriteByte(c byte) error { + if b.n == len(b.v) { + return errors.New("full") + } + b.v[b.wpos] = c + b.wpos = (b.wpos + 1) % len(b.v) + b.n++ + return nil +} + +func (b *Buffer) Overwrite(c byte) { + if err := b.WriteByte(c); err != nil { + b.v[b.rpos] = c + b.rpos = (b.rpos + 1) % len(b.v) + } +} + +func (b *Buffer) Reset() { + b.n = 0 + b.rpos = b.wpos +} diff --git a/go/circular-buffer/circular_buffer_test.go b/go/circular-buffer/circular_buffer_test.go new file mode 100644 index 0000000..7eda50f --- /dev/null +++ b/go/circular-buffer/circular_buffer_test.go @@ -0,0 +1,209 @@ +package circular + +// Implement a circular buffer of bytes supporting both overflow-checked writes +// and unconditional, possibly overwriting, writes. +// +// type Buffer +// func NewBuffer(size int) *Buffer +// func (*Buffer) ReadByte() (byte, error) +// func (*Buffer) WriteByte(c byte) error +// func (*Buffer) Overwrite(c byte) +// func (*Buffer) Reset() // put buffer in an empty state +// +// We chose the above API so that Buffer implements io.ByteReader +// and io.ByteWriter and can be used (size permitting) as a drop in +// replacement for anything using that interface. + +import ( + "io" + "testing" +) + +const targetTestVersion = 3 + +func TestTestVersion(t *testing.T) { + if testVersion != targetTestVersion { + t.Errorf("Found testVersion = %v, want %v.", testVersion, targetTestVersion) + } +} + +// Here is one way you can have a test case verify that the expected +// interfaces are implemented. + +var _ io.ByteReader = new(Buffer) +var _ io.ByteWriter = new(Buffer) + +// testBuffer and methods support the tests, providing log and fail messages. + +type testBuffer struct { + *testing.T + b *Buffer +} + +func nb(size int, t *testing.T) testBuffer { + t.Logf("NewBuffer(%d)", size) + return testBuffer{t, NewBuffer(size)} +} + +func (tb testBuffer) read(want byte) { + switch c, err := tb.b.ReadByte(); { + case err != nil: + tb.Fatalf("ReadByte() failed unexpectedly: %v", err) + case c != want: + tb.Fatalf("ReadByte() = %c, want %c.", c, want) + } + tb.Logf("ReadByte %c", want) +} + +func (tb testBuffer) readFail() { + if c, err := tb.b.ReadByte(); err == nil { + tb.Fatalf("ReadByte() = %c, expected a failure", c) + } + tb.Log("ReadByte() fails as expected") +} + +func (tb testBuffer) write(c byte) { + if err := tb.b.WriteByte(c); err != nil { + tb.Fatalf("WriteByte(%c) failed unexpectedly: %v", c, err) + } + tb.Logf("WriteByte(%c)", c) +} + +func (tb testBuffer) writeFail(c byte) { + if err := tb.b.WriteByte(c); err == nil { + tb.Fatalf("WriteByte(%c) succeeded, expected a failure", c) + } + tb.Logf("WriteByte(%c) fails as expected", c) +} + +func (tb testBuffer) reset() { + tb.b.Reset() + tb.Log("Reset()") +} + +func (tb testBuffer) overwrite(c byte) { + tb.b.Overwrite(c) + tb.Logf("Overwrite(%c)", c) +} + +// tests. separate functions so log will have descriptive test name. + +func TestReadEmptyBuffer(t *testing.T) { + tb := nb(1, t) + tb.readFail() +} + +func TestWriteAndReadOneItem(t *testing.T) { + tb := nb(1, t) + tb.write('1') + tb.read('1') + tb.readFail() +} + +func TestWriteAndReadMultipleItems(t *testing.T) { + tb := nb(2, t) + tb.write('1') + tb.write('2') + tb.read('1') + tb.read('2') + tb.readFail() +} + +func TestReset(t *testing.T) { + tb := nb(3, t) + tb.write('1') + tb.write('2') + tb.write('3') + tb.reset() + tb.write('1') + tb.write('3') + tb.read('1') + tb.write('4') + tb.read('3') +} + +func TestAlternateWriteAndRead(t *testing.T) { + tb := nb(2, t) + tb.write('1') + tb.read('1') + tb.write('2') + tb.read('2') +} + +func TestReadOldestItem(t *testing.T) { + tb := nb(3, t) + tb.write('1') + tb.write('2') + tb.read('1') + tb.write('3') + tb.read('2') + tb.read('3') +} + +func TestWriteFullBuffer(t *testing.T) { + tb := nb(2, t) + tb.write('1') + tb.write('2') + tb.writeFail('A') +} + +func TestOverwriteFull(t *testing.T) { + tb := nb(2, t) + tb.write('1') + tb.write('2') + tb.overwrite('A') + tb.read('2') + tb.read('A') + tb.readFail() +} + +func TestOverwriteNonFull(t *testing.T) { + tb := nb(2, t) + tb.write('1') + tb.overwrite('2') + tb.read('1') + tb.read('2') + tb.readFail() +} + +func TestAlternateReadAndOverwrite(t *testing.T) { + tb := nb(5, t) + tb.write('1') + tb.write('2') + tb.write('3') + tb.read('1') + tb.read('2') + tb.write('4') + tb.read('3') + tb.write('5') + tb.write('6') + tb.write('7') + tb.write('8') + tb.overwrite('A') + tb.overwrite('B') + tb.read('6') + tb.read('7') + tb.read('8') + tb.read('A') + tb.read('B') + tb.readFail() +} + +func BenchmarkOverwrite(b *testing.B) { + c := NewBuffer(100) + b.ResetTimer() + for i := 0; i < b.N; i++ { + c.Overwrite(0) + } + b.SetBytes(int64(b.N)) +} + +func BenchmarkWriteRead(b *testing.B) { + c := NewBuffer(100) + b.ResetTimer() + for i := 0; i < b.N; i++ { + c.WriteByte(0) + c.ReadByte() + } + b.SetBytes(int64(b.N)) +} -- cgit v1.2.3