" # Circular Buffer # Description 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: [5][6][7][8][9][3][4] 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: [5][6][7][8][9][A][B] 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. [C][D][7][8][9][A][B] ## Hint For error cases during operations, see Error class hierarchy (class side) to find out how to signal exception with given message. " Class { #name : #CircularBufferTest, #superclass : #ExercismTest, #instVars : [ 'circularBufferCalculator' ], #category : #'Exercise@CircularBuffer' } { #category : #config } CircularBufferTest class >> exercise [ ^ (ExercismExercise for: self) difficulty: 5; topics: #('arrays' 'conditionals' 'data_structures' 'exception_handling' 'lists' 'list-methods'); yourself ] { #category : #config } CircularBufferTest class >> uuid [ "Answer a unique id for this exercise" ^'158d4bc4-1002-4612-bdaf-5aa711a4f9a4' ] { #category : #config } CircularBufferTest class >> version [ "Generated from specification: 7 September 2023" ^'Not specified' ] { #category : #running } CircularBufferTest >> setUp [ super setUp. circularBufferCalculator := CircularBuffer new ] { #category : #tests } CircularBufferTest >> test01_ReadingEmptyBufferShouldFail [ "Tip: Remember to review the class [Comment] tab" circularBufferCalculator capacity: 1. self should: [circularBufferCalculator read] raise: Error. ] { #category : #tests } CircularBufferTest >> test02_CanReadAnItemJustWritten [ | result | circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. result := circularBufferCalculator read. self assert: result equals: 1 ] { #category : #tests } CircularBufferTest >> test03_EachItemMayOnlyBeReadOnce [ | result | circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. result := circularBufferCalculator read. self assert: result equals: 1. self should: [circularBufferCalculator read] raise: Error ] { #category : #tests } CircularBufferTest >> test04_ItemsAreReadInTheOrderTheyAreWritten [ | result | circularBufferCalculator capacity: 2. circularBufferCalculator write: 1. circularBufferCalculator write: 2. result := circularBufferCalculator read. self assert: result equals: 1. result := circularBufferCalculator read. self assert: result equals: 2 ] { #category : #tests } CircularBufferTest >> test05_FullBufferCantBeWrittenTo [ circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. self should: [ circularBufferCalculator write: 2 ] raise: Error ] { #category : #tests } CircularBufferTest >> test06_AReadFreesUpCapacityForAnotherWrite [ | result | circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. result := circularBufferCalculator read. self assert: result equals: 1. circularBufferCalculator write: 2. result := circularBufferCalculator read. self assert: result equals: 2 ] { #category : #tests } CircularBufferTest >> test07_ReadPositionIsMaintainedEvenAcrossMultipleWrites [ | result | circularBufferCalculator capacity: 3. circularBufferCalculator write: 1. circularBufferCalculator write: 2. result := circularBufferCalculator read. self assert: result equals: 1. circularBufferCalculator write: 3. result := circularBufferCalculator read. self assert: result equals: 2. result := circularBufferCalculator read. self assert: result equals: 3 ] { #category : #tests } CircularBufferTest >> test08_ItemsClearedOutOfBufferCantBeRead [ circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. circularBufferCalculator clear. self should: [ circularBufferCalculator read ] raise: Error ] { #category : #tests } CircularBufferTest >> test09_ClearFreesUpCapacityForAnotherWrite [ | result | circularBufferCalculator capacity: 1. circularBufferCalculator write: 1. circularBufferCalculator clear. circularBufferCalculator write: 2. result := circularBufferCalculator read. self assert: result equals: 2 ] { #category : #tests } CircularBufferTest >> test10_ClearDoesNothingOnEmptyBuffer [ | result | circularBufferCalculator capacity: 1. circularBufferCalculator clear. circularBufferCalculator write: 1. result := circularBufferCalculator read. self assert: result equals: 1 ] { #category : #tests } CircularBufferTest >> test11_OverwriteActsLikeWriteOnNonfullBuffer [ | result | circularBufferCalculator capacity: 2. circularBufferCalculator write: 1. circularBufferCalculator overwrite: 2. result := circularBufferCalculator read. self assert: result equals: 1. result := circularBufferCalculator read. self assert: result equals: 2 ] { #category : #tests } CircularBufferTest >> test12_OverwriteReplacesTheOldestItemOnFullBuffer [ | result | circularBufferCalculator capacity: 2. circularBufferCalculator write: 1. circularBufferCalculator write: 2. circularBufferCalculator overwrite: 3. result := circularBufferCalculator read. self assert: result equals: 2. result := circularBufferCalculator read. self assert: result equals: 3 ] { #category : #tests } CircularBufferTest >> test13_OverwriteReplacesTheOldestItemRemainingInBufferFollowingARead [ | result | circularBufferCalculator capacity: 3. circularBufferCalculator write: 1. circularBufferCalculator write: 2. circularBufferCalculator write: 3. result := circularBufferCalculator read. self assert: result equals: 1. circularBufferCalculator write: 4. circularBufferCalculator overwrite: 5. result := circularBufferCalculator read. self assert: result equals: 3. result := circularBufferCalculator read. self assert: result equals: 4. result := circularBufferCalculator read. self assert: result equals: 5 ] { #category : #tests } CircularBufferTest >> test14_InitialClearDoesNotAffectWrappingAround [ | result | circularBufferCalculator capacity: 2. circularBufferCalculator clear. circularBufferCalculator write: 1. circularBufferCalculator write: 2. circularBufferCalculator overwrite: 3. circularBufferCalculator overwrite: 4. result := circularBufferCalculator read. self assert: result equals: 3. result := circularBufferCalculator read. self assert: result equals: 4. self should: [ circularBufferCalculator read ] raise: Error ]