Copying a circular buffer to a larger buffer while preserving contents and modulus indices

Question

I am keeping an efficient circular buffer buf as an array and two total read and write counts bufRead and bufWrite such that bufRead % buf.length and bufWrite % buf.length are correct indices into buffer for current operations.

Now I might need to "grow" the array at some point because the buffer size expands. So I want to replace buf with a new, larger array, but preserve all the previous contents of the buffer while preserving the above modulus properties. So if at bufRead % buf.length in the old buffer we find element X, then I want this element X to be found again at the same index bufRead % buf.length after buf has been updated.

Example:

trait Algorithm {
  var buf: Array[Double]
  var bufRead : Long  // this won't be needed in `resize`
  var bufWrite: Long  // this won't be needed in `resize`

  def resize(newLength: Int): Unit = {
    val newBuf = new Array[Double](newLength)
    ???
    buf = newBuf
  }
}

A test procedure:

def test(in: Algorithm): Unit = {
  import in._
  import math.{min, random}
  val avail  = buf.length // (bufWrite - bufRead).toInt
  val data0  = Array.fill(avail)(random)
  val off0   = (bufRead % buf.length).toInt
  val chunk0 = min(avail, buf.length - off0)  
  val off1   = (off0 + chunk0) % buf.length
  val chunk1 = avail - chunk0

  System.arraycopy(data0, 0     , buf, off0, chunk0)
  System.arraycopy(data0, chunk0, buf, off1, chunk1)

  resize(avail * 2)  // arbitrary growth

  val data1  = new Array[Double](avail)
  val off2   = (bufRead % buf.length).toInt
  val chunk2 = min(avail, buf.length - off2)
  val off3   = (off2 + chunk2) % buf.length
  val chunk3 = avail - chunk2
  System.arraycopy(buf, off2, data1, 0     , chunk2)
  System.arraycopy(buf, off3, data1, chunk2, chunk3)

  assert(data0 sameElements data1)
}

Answer 1

There are two possible approaches:

• re-ordering the contents so they fit into the new modulus

  for (i <- bufRead until bufWrite) {
      newBuf(i % newBuf.length) = buf(i % buf.length)
  }
  

• resetting read and write pointers to fit to the new array

  var j = 0
  for (i <- bufRead until bufWrite) {
      newBuf(j) = buf(i % buf.length)
      j += 1
  }
  bufWrite -= bufRead
  bufRead = 0
  

I'm not sure whether you want to keep track of the number of all elements the buffer has ever stored, if yes then the second approach doesn't work of course. The first approach, re-ordering, shouldn't be too much of a hazzle as you need to copy the contents from the old into the new array anyway.