package scala.collection
package immutable
import generic._
import annotation.{tailrec, bridge}
import mutable.{ ListBuffer, Builder }
object ListSet extends ImmutableSetFactory[ListSet] {
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A]
override def empty[A] = EmptyListSet.asInstanceOf[ListSet[A]]
override def newBuilder[A]: Builder[A, ListSet[A]] = new ListSetBuilder[A]
private object EmptyListSet extends ListSet[Any] { }
class ListSetBuilder[Elem](initial: ListSet[Elem]) extends Builder[Elem, ListSet[Elem]] {
def this() = this(empty[Elem])
protected val elems = new mutable.ListBuffer[Elem] ++= initial reverse
protected val seen = new mutable.HashSet[Elem] ++= initial
def +=(x: Elem): this.type = {
if (!seen(x)) {
elems += x
seen += x
}
this
}
def clear() = { elems.clear() ; seen.clear() }
def result() = elems.foldLeft(empty[Elem])(_ unchecked_+ _)
}
}
class ListSet[A] extends Set[A]
with GenericSetTemplate[A, ListSet]
with SetLike[A, ListSet[A]]
with Serializable{ self =>
override def companion: GenericCompanion[ListSet] = ListSet
override def size: Int = 0
override def isEmpty: Boolean = true;
def contains(elem: A): Boolean = false
def + (elem: A): ListSet[A] = new Node(elem)
def - (elem: A): ListSet[A] = this
override def ++(xs: GenTraversableOnce[A]): ListSet[A] =
if (xs.isEmpty) this
else new ListSet.ListSetBuilder(this) ++= xs.seq result
@bridge def ++(xs: TraversableOnce[A]): ListSet[A] = ++(xs: GenTraversableOnce[A]): ListSet[A]
private[ListSet] def unchecked_+(e: A): ListSet[A] = new Node(e)
private[ListSet] def unchecked_outer: ListSet[A] =
throw new NoSuchElementException("Empty ListSet has no outer pointer")
def iterator: Iterator[A] = new Iterator[A] {
var that: ListSet[A] = self
def hasNext = that.nonEmpty
def next: A =
if (hasNext) {
val res = that.elem
that = that.next
res
}
else Iterator.empty.next
}
protected def elem: A = throw new NoSuchElementException("Set has no elements");
protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set");
override def stringPrefix = "ListSet"
protected class Node(override protected val elem: A) extends ListSet[A] with Serializable {
override private[ListSet] def unchecked_outer = self
override def size = sizeInternal(this, 0)
@tailrec private def sizeInternal(n: ListSet[A], acc: Int): Int =
if (n.isEmpty) acc
else sizeInternal(n.unchecked_outer, acc + 1)
override def isEmpty: Boolean = false
override def contains(e: A) = containsInternal(this, e)
@tailrec private def containsInternal(n: ListSet[A], e: A): Boolean =
!n.isEmpty && (n.elem == e || containsInternal(n.unchecked_outer, e))
override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)
override def -(e: A): ListSet[A] = if (e == elem) self else {
val tail = self - e; new tail.Node(elem)
}
override protected def next: ListSet[A] = self
}
}