Максимальная длина очереди scala - PullRequest
Новая
       21

Максимальная длина очереди scala

14 голосов
/ 03 августа 2011

Мне любопытно, есть ли в Scala какой-то драгоценный камень, который я могу использовать в своих коллекционных классах. В основном я ищу что-то вроде очереди FIFO, но у нее есть верхний предел размера, так что при достижении предела самый старый (первый) элемент удаляется из очереди. Я реализовал это сам в Java в прошлом, но я бы предпочел использовать что-то стандартное, если это возможно.

Ответы [ 3 ]

20 голосов
/ 03 августа 2011

Часто предпочтительной альтернативой для подклассов является (* к сожалению названный) шаблон " pimp my library ". Вы можете использовать его для добавления метода enqueueFinite к Queue, например: 

import scala.collection.immutable.Queue
class FiniteQueue[A](q: Queue[A]) {
  def enqueueFinite[B >: A](elem: B, maxSize: Int): Queue[B] = {
    var ret = q.enqueue(elem)
    while (ret.size > maxSize) { ret = ret.dequeue._2 }
    ret
  }
}
implicit def queue2finitequeue[A](q: Queue[A]) = new FiniteQueue[A](q)

Всякий раз, когда queue2finitequeue находится в области видимости, вы можете обрабатывать Queue объекты, как если бы они имели метод enqueueFinite: 

val maxSize = 3
val q1 = Queue(1, 2, 3)
val q2 = q1.enqueueFinite(5, maxSize)
val q3 = q2.map(_+1)
val q4 = q3.enqueueFinite(7, maxSize)

Преимущество этого подхода перед подклассами заключается в том, что enqueueFinite доступен для всех Queue с, включая те, которые создаются с помощью таких операций, как enqueue, map, ++ и т. Д.

Обновление : Как говорит Дилан в комментариях, enqueueFinite необходимо также принять параметр для максимального размера очереди и отбросить элементы по мере необходимости. Я обновил код.

4 голосов
/ 03 августа 2011

Вот неизменное решение: 

class FixedSizeFifo[T](val limit: Int)
( private val out: List[T], private val in: List[T] ) 
extends Traversable[T] {

  override def size = in.size + out.size

  def :+( t: T ) = {
    val (nextOut,nextIn) = if (size == limit) {
      if( out.nonEmpty) {
        ( out.tail, t::in ) 
      } else {
        ( in.reverse.tail, List(t) )
      }
    } else ( out, t::in )
      new FixedSizeFifo( limit )( nextOut, nextIn )
  }

  private lazy val deq = {
    if( out.isEmpty ) {
      val revIn = in.reverse
      ( revIn.head, new FixedSizeFifo( limit )( revIn.tail, List() ) )
    } else {
      ( out.head, new FixedSizeFifo( limit )( out.tail, in ) )
    }
  }
  override lazy val head = deq._1
  override lazy val tail = deq._2

  def foreach[U]( f: T => U ) = ( out ::: in.reverse ) foreach f

}

object FixedSizeFifo {
  def apply[T]( limit: Int ) = new FixedSizeFifo[T]( limit )(List(),List())
}

Пример: 

val fifo = FixedSizeFifo[Int](3) :+ 1 :+ 2 :+ 3 :+ 4 :+ 5 :+ 6
println( fifo )                //prints: FixedSizeFifo(4, 5, 6)
println( fifo.head )           //prints: 4
println( fifo.tail :+ 7 :+8 )  //prints: FixedSizeFifo(6, 7, 8)
4 голосов
/ 03 августа 2011

Почему бы вам просто не создать подкласс FIFO-очереди? Примерно так должно работать: (псевдокод следует ...) 

class Limited(limit:Int) extends FIFO {
  override def enqueue() = {
    if (size >= limit) {
      //remove oldest element
    }
    super.enqueue()
  }
}
...