ListSet pedido por inserción

Question

ListSet (collection.immutable.ListSet) es un conjunto ordenado inverso. Necesito un conjunto ordenado. Este es un ejemplo de ListSet el original:

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

Y este es un ejemplo de lo que necesito:

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

ACTUALIZACIÓN:

"ordenada" es un "inserciones ordenadas" para mí. Necesito esto:

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 realidad, no es un conjunto ordenado en absoluto. Si necesita un pedido, use una implementación de immutable.SortedSet, como immutable.TreeSet.

Answer 3

No se ordena:

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 es un conjunto que itera sus miembros en la misma secuencia que se insertaron. (Evito el término "ordenó" aquí, ya que prefiero reservar que para los casos de una relación de orden en los valores, no la secuencia particular en la que algunas acciones se llevaron a cabo.)

Answer 5

var eti = a.toList.reverse.iterator 

Answer 6

Si desea recuperar sus elementos en el orden en que se insertaron, necesita una colección de primero en entrar, primero en salir, así que simplemente use un Queue.

import collection.mutable.Queue 

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

for(i <- queue) 
    println(i) 

impresiones

1 
2 
3 
5 
4