Finite Growable Array in Scala

Question

I would like to be able to grow an Array-like structure up to a maximum size, after which the oldest (1st) element would be dropped off the structure every time a new element is added. I don't know what the best way to do this is, but one way would be to extend the ArrayBuffer class, and override the += operator so that if the maximum size has been reached, the first element is dropped every time a new one is added. I haven't figured out how to properly extend collections yet. What I have so far is:

class FiniteGrowableArray[A](maxLength:Int) extends scala.collection.mutable.ArrayBuffer {
    override def +=(elem:A): <insert some return type here> = {
        // append element
        if(length > maxLength) remove(0)
        <returned collection>
    }
}

Can someone suggest a better path and/or help me along this one? NOTE: I will need to arbitrarily access elements within the structure multiple times in between the += operations.

Thanks

Answer 1

As others have discussed, you want a ring buffer. However, you also have to decide if you actually want all of the collections methods or not, and if so, what happens when you filter a ring buffer of maximum size N--does it keep its maximum size, or what?

If you're okay with merely being able to view your ring buffer as part of the collections hierarchy (but don't want to use collections efficiently to generate new ring buffers) then you can just:

class RingBuffer[T: ClassManifest](maxsize: Int) {
  private[this] val buffer = new Array[T](maxsize+1)
  private[this] var i0,i1 = 0
  private[this] def i0up = { i0 += 1; if (i0>=buffer.length) i0 -= buffer.length }
  private[this] def i0dn = { i0 -= 1; if (i0<0) i0 += buffer.length }
  private[this] def i1up = { i1 += 1; if (i1>=buffer.length) i1 -= buffer.length }
  private[this] def i1dn = { i1 -= 1; if (i1<0) i1 += buffer.length }   
  private[this] def me = this

  def apply(i: Int) = {
    val j = i+i0
    if (j >= buffer.length) buffer(j-buffer.length) else buffer(j)
  }
  def size = if (i1<i0) buffer.length+i1-i0 else i1-i0
  def :+(t: T) = {
    buffer(i1) = t
    i1up; if (i1==i0) i0up
    this
  }
  def +:(t: T) = {
    i0dn; if (i0==i1) i1dn
    buffer(i0) = t
    this
  }
  def popt = {
    if (i1==i0) throw new java.util.NoSuchElementException
    i1dn; buffer(i1)
  }
  def poph = {
    if (i1==i0) throw new java.util.NoSuchElementException
    val ans = buffer(i0); i0up; ans
  }
  def seqView = new IndexedSeq[T] {
    def apply(i: Int) = me(i)
    def length = me.size
  }
}

Now you can use this easily directly, and you can jump out to IndexedSeq when needed:

val r = new RingBuffer[Int](4)
r :+ 7 :+ 9 :+ 2
r.seqView.mkString(" ")    // Prints 7 9 2
r.popt                     // Returns 2
r.poph                     // Returns 7
r :+ 6 :+ 5 :+ 4 :+ 3
r.seqView.mkString(" ")    // Prints 6 5 4 3 -- 7 fell off the end
0 +: 1 +: 2 +: r
r.seqView.mkString(" ")    // Prints 0 1 2 6 -- added to front; 3,4,5 fell off
r.seqView.filter(_>1)      // Vector(2,6)

and if you want to put things back into a ring buffer, you can

class RingBufferImplicit[T: ClassManifest](ts: Traversable[T]) {
  def ring(maxsize: Int) = {
    val rb = new RingBuffer[T](maxsize)
    ts.foreach(rb :+ _)
    rb
  }
}
implicit def traversable2ringbuffer[T: ClassManifest](ts: Traversable[T]) = {
  new RingBufferImplicit(ts)
}

and then you can do things like

val rr = List(1,2,3,4,5).ring(4)
rr.seqView.mkString(" ")            // Prints 2,3,4,5