Maksymalna długość kolejki scala

Question

Ciekaw jestem, czy Scala ma jakiś klejnot ukryty w klasach kolekcji, z których mogę korzystać. Zasadniczo szukam czegoś podobnego do kolejki FIFO, ale ma ona górny limit rozmiaru, tak że po osiągnięciu limitu najstarszy (pierwszy) element jest usuwany z kolejki. W przeszłości już to zaimplementowałem w Javie, ale wolę używać czegoś standardowego, jeśli to możliwe.

Answer 1

Często preferowane alternatywą dla podklasy jest (niestety nazwie) „pimp my library” wzór. Można go używać, aby dodać metodę enqueueFinite do Queue, tak:

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) 

Ilekroć queue2finitequeue jest w zakresie, można traktować Queue obiekty tak, jakby mieć metodę 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) 

zaletę tego podejścia w stosunku do podklasy polega na tym, że enqueueFinite jest dostępne dla wszystkich Queue s, włączając te, które są konstruowane za pomocą operacji takich jak enqueue, map, ++ itd.

Aktualizacja: jak Dylan mówi w komentarzach, enqueueFinite musi także brać parametr dla maksymalnego rozmiaru kolejki i upuść elementy, jak jest to konieczne. Zaktualizowałem kod.

Answer 2

Po prostu podklasuj kolejkę FIFO? Coś jak to powinno działać: (pseudokod następująco ...)

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

Answer 3

Oto niezmienne rozwiązanie:

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

Przykład:

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)