circular

README

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.

Source

Wikipedia 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.

Documentation

Overview

Package circular implements a circular buffer

Index

• Variables
• type Buffer
  • func NewBuffer(size int) *Buffer
  • func (buf *Buffer) Cap() int
  • func (buf *Buffer) Len() int
  • func (buf *Buffer) Overwrite(b byte)
  • func (buf *Buffer) ReadByte() (b byte, err error)
  • func (buf *Buffer) Reset()
  • func (buf *Buffer) WriteByte(b byte) (err error)

Variables

var ErrEmptyBuffer = errors.New("circular : Attempted to read from an empty buffer")

ErrEmptyBuffer is thrown when we try to read from a fallow buffer

var ErrFullBuffer = errors.New("circular : Attempted to write to a full buffer")

ErrFullBuffer is thrown when we try to write to a buffer at capacity

Types

type Buffer

type Buffer struct {
	// contains filtered or unexported fields
}

Buffer implements a bounded, circular buffer

func NewBuffer

func NewBuffer(size int) *Buffer

NewBuffer creates a circular buffer with capacity equal to size

func (*Buffer) Cap

func (buf *Buffer) Cap() int

Cap returns maximum capacity of this circular buffer

func (*Buffer) Len

func (buf *Buffer) Len() int

Len returns the number of occupied slots in the circular buffer

func (*Buffer) Overwrite

func (buf *Buffer) Overwrite(b byte)

Overwrite attempts to write normally, but if that's not possible, overwrites the oldest data we have

func (*Buffer) ReadByte

func (buf *Buffer) ReadByte() (b byte, err error)

ReadByte gives back the next byte in the circular buffer and increments our read head if possible

func (*Buffer) Reset

func (buf *Buffer) Reset()

Reset effectively clears out the buffers, this is done by moving the read and write heads back to 0

func (*Buffer) WriteByte

func (buf *Buffer) WriteByte(b byte) (err error)

WriteByte inserts a new byte into the circular buffer if possible, errors if full