Scala中的有限可生长数组

Question

我希望能够将类似数组的结构增长到最大尺寸,之后每次添加新元素时,最旧的(第一个)元素将从结构中删除.我不知道最好的方法是什么,但一种方法是扩展ArrayBuffer类,并覆盖+ =运算符,这样如果达到最大大小,每次新的时候都会删除第一个元素一个是添加.我还没想出如何正确扩展集合.到目前为止我所拥有的是:

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

有人可以建议一条更好的道路和/或帮助我吗？注意:我需要在+ =操作之间多次任意访问结构中的元素.

谢谢

Answer 1

正如其他人所讨论的,你需要一个环形缓冲区.但是,您还必须决定是否确实需要所有集合方法,如果是,那么当您过滤最大大小为N的环形缓冲区时会发生什么 - 它是否保持其最大大小,或者是什么？

如果您能够接受只能够查看您的环形缓冲区作为集合层次结构的一部分(但不希望有效利用集合来产生新的环形缓冲区),那么你可以:

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

现在您可以直接使用它,并且可以在需要时跳转到IndexedSeq:

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)

如果你想把东西放回环形缓冲区,你可以

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

然后你可以做的事情

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