Insertion-ordered ListSet

Question

ListSet (collection.immutable.ListSet) ist eine inverse geordnete Menge. Ich brauche eine geordnete Menge. Dies ist ein Beispiel für original ListSet:

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

Und dies ist ein Beispiel dafür, ich brauche:

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

UPDATE:

"bestellt" ist eine für mich "Insertion bestellt". Ich brauche das:

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

Eigentlich ist es überhaupt kein geordneter Satz. Wenn Sie eine Bestellung benötigen, verwenden Sie eine Implementierung von immutable.SortedSet, z. B. immutable.TreeSet.

Answer 3

Es ist nicht bestellt:

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 eine Menge ist, die ihre Mitglieder in der gleichen Reihenfolge iteriert sie eingefügt wurden. (Ich vermeide den Begriff hier „bestellt“, da ich, dass für den Fall einer Ordnungsrelation auf den Werten reservieren bevorzugen, nicht die bestimmte Reihenfolge, in der einige Aktionen durchgeführt wurden.)

Answer 5

var eti = a.toList.reverse.iterator 

Answer 6

Wenn Wenn Sie Ihre Elemente in der Reihenfolge abrufen möchten, in der sie eingefügt wurden, benötigen Sie eine First-In-First-Out-Sammlung. Verwenden Sie einfach Queue.

import collection.mutable.Queue 

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

for(i <- queue) 
    println(i) 

druckt

1 
2 
3 
5 
4