插入排序的 ListSet

本文介绍了插入排序的 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 } }