CODEWITHSUNDEEP
algorithmdata-structurescircular-buffercircular-list
KodeWarrior
KodeWarrior

Reputation: 3598

Shrinking a circular buffer

I'm trying to implement the shrinking operation for a circular buffer. The buffer has a start pointer( m_start ) and stores the number of elements( m_numelements). When the buffer is full I just purge the old value.

Say we have a array of size 16. m_start = 9 m_numelements = 11.

I want to shrink this array into an array of size 8( Can discard elements ).

The constraint here is that m_start( 9 ) of the old array should map to the m_start % new capacity ( 9 % 8 = 1 ) of the new array.

I tried writing the code but ended up with a lot of if-else ladder. Any efficient implementation for this ?

Upvotes: 1

Views: 493

Answers (2)

Craig Gidney
Craig Gidney

Reputation: 18306

Shrinking is equivalent to dequeueing the entire contents into a temporary buffer, and then enqueueing the contents of that buffer into a new circular buffer with the specified capacity. This isn't quite what you want, but it will inform what the code must look like.

So: write code to dequeue the entire contents of a circular buffer and enqueue them into a new circular buffer by using methods you already have, then inline the code contained in the methods you used, then refactor that code to place the contents into the existing circular buffer (after resizing) instead of a new one and optimize away any unnecessary copies or cases.

Upvotes: 0

MBo
MBo

Reputation: 80287

Let's storage array has zero-based indexing, and it's size is power of two (2,4,8...), m_start is start index.

When array is growing:

 double array length
 if m_start > 0 then
    copy (m_start elements) from (0th index) to (old size index)

example:

  3 0 1 2|. . . .
  . 0 1 2|3 . . .

When array is shrinking:

  if m_start > 0 then
     copy (m_start elements) from (newsize index) to (0th index) 
  half array length

example:

  . 0 1 2|3 . . . 
  3 0 1 2|. . . .

You can modify this scheme for one-based array indexing.

Upvotes: 1

Related Questions