Insertion-ordered ListSet

Question

ListSet (collection.immutable.ListSet) is a inverse ordered set. I need ordered set. This is a example of original ListSet:

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

And this is a example of I need:

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

UPDATE:

"Ordered" is a "Insertion Ordered" for me. I need this:

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

If you want to retrieve your elements in the order they were inserted, you need a first-in-first-out collection, so simply use a Queue.

import collection.mutable.Queue

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

for(i <- queue)
  println(i)

prints

 1
 2
 3
 5
 4

Answer 2

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 3

collection.mutable.LinkedHashSet is a set that iterates its members in the same sequence they were inserted. (I avoid the term "ordered" here, since I prefer to reserve that to cases of an ordering relation on the values, not the particular sequence in which some actions were carried out.)

Answer 4

var eti = a.toList.reverse.iterator

Answer 5

Actually, it's not an ordered set at all. If you need order, use an implementation of immutable.SortedSet, such as immutable.TreeSet.

Answer 6

It is not ordered:

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