Конечный растущий массив в Scala - PullRequest
Новая
       27

Конечный растущий массив в Scala

2 голосов
/ 22 марта 2011

Я хотел бы иметь возможность увеличивать структуру, подобную массиву, до максимального размера, после чего самый старый (1-й) элемент будет удаляться из структуры каждый раз, когда добавляется новый элемент. Я не знаю, каков наилучший способ сделать это, но одним из способов было бы расширить класс 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>
    }
}

Может кто-нибудь предложить лучший путь и / или помочь мне в этом? ПРИМЕЧАНИЕ. Мне потребуется произвольный доступ к элементам в структуре несколько раз между операциями + =.

Спасибо

1 Ответ

5 голосов
/ 22 марта 2011

Как уже обсуждали другие, вам нужен кольцевой буфер. Однако вы также должны решить, хотите ли вы на самом деле все методы коллекций или нет, и если да, что произойдет, когда вы фильтруете кольцевой буфер максимального размера 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
...