Avatar of paulfioravanti

paulfioravanti's solution

to Circular Buffer in the Ruby Track

Published at May 20 2019 · 0 comments
Instructions
Test suite
Solution

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.

When the buffer is full, 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]

3 & 4 have been replaced by A & B making 5 now the oldest data in the buffer. Finally, if two elements are removed then what would be returned is 5 & 6 yielding the buffer:

[ ][7][8][9][A][B][ ]

Because there is space available, if the client again uses overwrite to store C & D then the space where 5 & 6 were stored previously will be used not the location of 7 & 8. 7 is still the oldest element and the buffer is once again full.

[D][7][8][9][A][B][C]

For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby circular_buffer_test.rb

To include color from the command line:

ruby -r minitest/pride circular_buffer_test.rb

Source

Wikipedia http://en.wikipedia.org/wiki/Circular_buffer

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

circular_buffer_test.rb

require 'minitest/autorun'
require_relative 'circular_buffer'

class CircularBufferTest < Minitest::Test
  def test_read_empty_buffer_throws_buffer_empty_exception
    buffer = CircularBuffer.new(1)
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end

  def test_write_and_read_back_one_item
    skip
    buffer = CircularBuffer.new(1)
    buffer.write '1'
    assert_equal '1', buffer.read
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end

  def test_write_and_read_back_multiple_items
    skip
    buffer = CircularBuffer.new(2)
    buffer.write '1'
    buffer.write '2'
    assert_equal '1', buffer.read
    assert_equal '2', buffer.read
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end

  def test_clearing_buffer
    skip
    buffer = CircularBuffer.new(3)
    ('1'..'3').each { |i| buffer.write i }
    buffer.clear
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
    buffer.write '1'
    buffer.write '2'
    assert_equal '1', buffer.read
    buffer.write '3'
    assert_equal '2', buffer.read
  end

  def test_alternate_write_and_read
    skip
    buffer = CircularBuffer.new(2)
    buffer.write '1'
    assert_equal '1', buffer.read
    buffer.write '2'
    assert_equal '2', buffer.read
  end

  def test_reads_back_oldest_item
    skip
    buffer = CircularBuffer.new(3)
    buffer.write '1'
    buffer.write '2'
    buffer.read
    buffer.write '3'
    assert_equal '2', buffer.read
    assert_equal '3', buffer.read
  end

  def test_writing_to_a_full_buffer_throws_an_exception
    skip
    buffer = CircularBuffer.new(2)
    buffer.write '1'
    buffer.write '2'
    assert_raises(CircularBuffer::BufferFullException) { buffer.write 'A' }
  end

  def test_overwriting_oldest_item_in_a_full_buffer
    skip
    buffer = CircularBuffer.new(2)
    buffer.write '1'
    buffer.write '2'
    buffer.write! 'A'
    assert_equal '2', buffer.read
    assert_equal 'A', buffer.read
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end

  def test_forced_writes_to_non_full_buffer_should_behave_like_writes
    skip
    buffer = CircularBuffer.new(2)
    buffer.write '1'
    buffer.write! '2'
    assert_equal '1', buffer.read
    assert_equal '2', buffer.read
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end

  def test_alternate_read_and_write_into_buffer_overflow
    skip
    buffer = CircularBuffer.new(5)
    ('1'..'3').each { |i| buffer.write i }
    buffer.read
    buffer.read
    buffer.write '4'
    buffer.read
    ('5'..'8').each { |i| buffer.write i }
    buffer.write! 'A'
    buffer.write! 'B'
    ('6'..'8').each do |i|
      assert_equal i, buffer.read
    end
    assert_equal 'A', buffer.read
    assert_equal 'B', buffer.read
    assert_raises(CircularBuffer::BufferEmptyException) { buffer.read }
  end
end
# frozen_string_literal: true

require "forwardable"

class CircularBuffer
  class BufferEmptyException < StandardError; end
  class BufferFullException < StandardError; end

  extend Forwardable

  def initialize(size)
    @buffer = []
    @size = size
  end

  def_delegators :@buffer, :clear, :empty?, :length, :push, :shift

  def read
    raise BufferEmptyException if empty?

    shift
  end

  def write(char)
    raise BufferFullException if full?

    push(char)
  end

  def write!(char)
    read if full?
    write(char)
  end

  private

  attr_reader :size

  def full?
    length == size
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?