ListSet ordonné par insertion

Question

ListSet (collection.immutable.ListSet) est un ensemble ordonné inverse. J'ai besoin d'un ensemble commandé. Ceci est un exemple de ListSet d'origine:

var a = ListSet(1,2,3) 
var ite = a.iterator 
ite.next // returns 3 
ite.next // returns 2 
ite.next // returns 1 

Et ceci est un exemple de I besoin:

var a = ListSet(1,2,3) 
var ite = a.iterator 
ite.next // returns 1 
ite.next // returns 2 
ite.next // returns 3 

MISE À JOUR:

"Ordonné" est un pour moi "Insertion Ordonné". J'ai besoin de ceci:

var a = ListSet(1,2,3) 
a += 5 
a += 4 
var ite = a.iterator 
ite.next // returns 1 
ite.next // returns 2 
ite.next // returns 3 
ite.next // returns 5 
ite.next // returns 4 

Answer 1

import collection.SetLike 
import collection.generic.{CanBuildFrom, ImmutableSetFactory, GenericCompanion, GenericSetTemplate} 

@serializable @SerialVersionUID(2L) 
class OrderedListSet[A] extends Set[A] 
        with GenericSetTemplate[A, OrderedListSet] 
        with SetLike[A, OrderedListSet[A]] { 

    override def companion: GenericCompanion[OrderedListSet] = OrderedListSet 

    override def size: Int = 0 

    override def empty = OrderedListSet.empty[A] 

    def iterator: Iterator[A] = Iterator.empty 

    override def foreach[U](f: A => U): Unit = { } 

    def contains(e: A): Boolean = get0(e) 

    override def + (e: A): OrderedListSet[A] = updated0(e) 

    override def + (elem1: A, elem2: A, elems: A*): OrderedListSet[A] = this + elem1 + elem2 ++ elems 

    def - (e: A): OrderedListSet[A] = removed0(e) 

    protected def get0(key: A): Boolean = false 

    protected def updated0(key: A): OrderedListSet[A] = 
    new OrderedListSet.OrderedListSet1(key) 

    protected def removed0(key: A): OrderedListSet[A] = this 

    protected val indexes:List[Int] = List[Int]() 

    protected val nextIndex:Int = 1 

    def pairIterator:Iterator[(A,Int)] = Iterator.empty 

    protected def writeReplace(): AnyRef = new OrderedListSet.SerializationProxy(this) 

    protected def pairForeach[U](f: ((A,Int)) => U): Unit = { } 
} 


object OrderedListSet extends ImmutableSetFactory[OrderedListSet] { 
    /** $setCanBuildFromInfo */ 
    implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, OrderedListSet[A]] = setCanBuildFrom[A] 
    override def empty[A]: OrderedListSet[A] = EmptyOrderedListSet.asInstanceOf[OrderedListSet[A]] 

    private object EmptyOrderedListSet extends OrderedListSet[Any] { 
    } 

    class OrderedListSet1[A](private[OrderedListSet] var key: A) extends OrderedListSet[A] { 

    override def size = 1 

    override val indexes = List[Int](1) 

    override val nextIndex = indexes.head + 1 

    override def get0(key: A): Boolean = (key == this.key) 

    override def updated0(key: A): OrderedListSet[A] = 
     if (this.key == key) { 
     this 
     } else { 
     val m = new EEOrderedListSet[A](List[A](this.key), indexes, nextIndex) 
     m.updated0(key) 
     } 

    override def removed0(key: A): OrderedListSet[A] = if (key == this.key) OrderedListSet.empty[A] else this 

    override def iterator = Iterator(key) 

    override def pairIterator: Iterator[(A, Int)] = Iterator((key, indexes.head)) 

    override def foreach[U](f: A => U): Unit = f(key) 

    override def pairForeach[U](f: ((A,Int)) => U): Unit = f (key, indexes.head) 
    } 


    class EEOrderedListSet[A](private var elems: List[A], 
           override protected[OrderedListSet] val indexes: List[Int], 
           override protected[OrderedListSet] val nextIndex:Int) 
      extends OrderedListSet[A] { 

    override def size = elems.size 

    override def get0(key: A): Boolean = elems.contains(key) 

    override def updated0(key: A): OrderedListSet[A] = { 
     if (elems contains key) { 
     this 
     } else { 
     new EEOrderedListSet(elems.:+(key), indexes.:+(nextIndex), nextIndex+1) 
     } 
    } 

    override def removed0(key: A): OrderedListSet[A] = { 
     val r = elems findIndexOf (_ == key) 
     if (r != -1) { 
     val e = elems filterNot (_ == key) 
     val (i1, i2) = indexes splitAt r 
     val i = i1 ++ i2.tail 
     new EEOrderedListSet(e, i, nextIndex) 
     } else { 
     this 
     } 
    } 

    override def iterator = elems.iterator 

    override def pairIterator: Iterator[(A, Int)] = (elems zip indexes).iterator 

    override def foreach[U](f: A => U): Unit = elems.foreach(f) 

    override def pairForeach[U](f: ((A,Int)) => U): Unit = (elems zip indexes).foreach(f) 
    } 

    @serializable @SerialVersionUID(2L) private class SerializationProxy[A,B](@transient private var orig: OrderedListSet[A]) { 
    private def writeObject(out: java.io.ObjectOutputStream) { 
     val s = orig.size 
     out.writeInt(s) 
     for (e <- orig) { 
     out.writeObject(e) 
     } 
    } 

    private def readObject(in: java.io.ObjectInputStream) { 
     orig = empty 
     val s = in.readInt() 
     for (i <- 0 until s) { 
     val e = in.readObject().asInstanceOf[A] 
     orig = orig + e 
     } 
    } 

    private def readResolve(): AnyRef = orig 
    } 

} 

Answer 2

En fait, ce n'est pas un ensemble ordonné du tout. Si vous avez besoin d'une commande, utilisez une implémentation de immutable.SortedSet, telle que immutable.TreeSet.

Answer 3

Il n'est pas commandé:

val a = ListSet(3,1,2) 
val ite = a.iterator 
ite.next // returns 2 
ite.next // returns 1 
ite.next // returns 3 

Answer 4

collection.mutable.LinkedHashSet est un ensemble qui itère ses membres dans la même séquence, ils ont été insérés. (J'évite le terme « ordonné » ici, puisque je préfère réserver que pour les cas d'une relation d'ordre sur les valeurs, et non pas la séquence particulière dans laquelle certaines actions ont été menées.)

Answer 5

var eti = a.toList.reverse.iterator 

Answer 6

Si vous voulez récupérer vos éléments dans l'ordre où ils ont été insérés, vous avez besoin d'une collection premier entré, premier sorti, alors utilisez simplement un Queue.

import collection.mutable.Queue 

val queue = Queue(1,2,3) 
queue += 5 
queue += 4 

for(i <- queue) 
    println(i) 

impressions

1 
2 
3 
5 
4