插入排序的 ListSet [英] Insertion-ordered ListSet

问题描述

ListSet (collection.immutable.ListSet) 是一个逆序集合.我需要订购的套装.这是原始 ListSet 的示例:

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

更新:

Ordered"对我来说是Insertion Ordered".我需要这个:

"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

推荐答案

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
  }

}

这篇关于插入排序的 ListSet的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！