CODEWITHSUNDEEP
algorithmscalacircular-buffer
0__
0__

Reputation: 67330

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

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)
}

Upvotes: 0

Views: 296

Answers (2)

Bergi
Bergi

Reputation: 665286

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.

Upvotes: 1

0__
0__

Reputation: 67330

I believe the following is correct:

class Impl(size0: Int) extends Algorithm {
  var buf = new Array[Double](size0)
  var bufRead  = 0L
  var bufWrite = 0L   // unused here

  override def resize(newLength: Int): Unit = {
    import math.{min, max}
    val newBuf    = new Array[Double](newLength)
    val oldLength = buf.length
    val off0      = (bufRead % oldLength).toInt
    val off1      = (bufRead % newLength).toInt
    val chunk0    = min(oldLength - off0, newLength - off1)
    System.arraycopy(buf, off0, newBuf, off1, chunk0)
    val off2      = (off0 + chunk0) % oldLength
    val off3      = (off1 + chunk0) % newLength
    val chunk1    = min(oldLength - max(chunk0, off2), newLength - off3)
    System.arraycopy(buf, off2, newBuf, off3, chunk1)
    val off4      = (off2 + chunk1) % oldLength
    val off5      = (off3 + chunk1) % newLength
    val chunk2    = oldLength - (chunk0 + chunk1)
    System.arraycopy(buf, off4, newBuf, off5, chunk2)
    buf = newBuf
  }
}

Test:

for (r <- 0 until 200) {
  val a = new Impl(100)
  a.bufRead = r   // test all possible offsets
  test(a)
}

Upvotes: 0

Related Questions