Scala 中的有限可增长数组

Question

我希望能够将类似数组的结构增长到最大大小，之后每次添加新元素时，最旧的（第一个）元素将从结构中删除。我不知道最好的方法是什么，但一种方法是扩展 ArrayBuffer 类，并重写 += 运算符，这样如果达到最大大小，则每次新的元素都会删除第一个元素已添加 1 个。我还没有弄清楚如何正确扩展集合。到目前为止我所拥有的是：

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