diff options
| -rw-r--r-- | src/library/scala/collection/immutable/ListSet.scala | 66 | ||||
| -rw-r--r-- | test/files/jvm/serialization.check | 4 | ||||
| -rw-r--r-- | test/files/run/bug3822.scala | 13 |
3 files changed, 70 insertions, 13 deletions
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala index 4268e742b0..136a57c680 100644 --- a/src/library/scala/collection/immutable/ListSet.scala +++ b/src/library/scala/collection/immutable/ListSet.scala @@ -12,6 +12,8 @@ package scala.collection package immutable import generic._ +import annotation.tailrec +import mutable.{ ListBuffer, Builder } /** $factoryInfo * @define Coll immutable.ListSet @@ -22,8 +24,27 @@ object ListSet extends ImmutableSetFactory[ListSet] { /** setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A] override def empty[A] = new ListSet[A] -} + override def newBuilder[A]: Builder[A, ListSet[A]] = new ListSetBuilder[A] + /** A custom builder because forgetfully adding elements one at + * a time to a list backed set puts the "squared" in N^2. There is a + * temporary space cost, but it's improbable a list backed set could + * become large enough for this to matter given its pricy element lookup. + */ + class ListSetBuilder[Elem] extends Builder[Elem, ListSet[Elem]] { + protected val elems = new mutable.ListBuffer[Elem] + protected val seen = new mutable.HashSet[Elem] + 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_+ _) + } +} /** This class implements immutable sets using a list-based data * structure. Instances of `ListSet` represent @@ -64,22 +85,39 @@ class ListSet[A] extends Set[A] */ def + (elem: A): ListSet[A] = new Node(elem) - /** <code>-</code> can be used to remove a single element from - * a set. + /** `-` can be used to remove a single element. */ def - (elem: A): ListSet[A] = this + /** If we are bulk adding elements and desire a runtime measured in + * sub-interstellar time units, we better find a way to avoid traversing + * the collection on each element. That's what the custom builder does, + * so we take the easy way out and add ourselves and the argument to + * a new builder. + */ + override def ++(xs: TraversableOnce[A]): ListSet[A] = + if (xs.isEmpty) this + else newBuilder ++= this ++= xs result + + 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") + /** Creates a new iterator over all elements contained in this set. * * @throws Predef.NoSuchElementException * @return the new iterator */ def iterator: Iterator[A] = new Iterator[A] { - var that: ListSet[A] = self; - def hasNext = !that.isEmpty; + var that: ListSet[A] = self + def hasNext = that.nonEmpty def next: A = - if (!hasNext) throw new NoSuchElementException("next on empty iterator") - else { val res = that.elem; that = that.next; res } + if (hasNext) { + val res = that.elem + that = that.next + res + } + else Iterator.empty.next } /** @@ -92,16 +130,22 @@ class ListSet[A] extends Set[A] */ protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set"); + override def stringPrefix = "ListSet" + /** Represents an entry in the `ListSet`. */ @serializable protected class Node(override protected val elem: A) extends ListSet[A] { + override private[ListSet] def unchecked_outer = self /** Returns the number of elements in this set. * * @return number of set elements. */ - override def size = self.size + 1 + 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) /** Checks if this set is empty. * @@ -114,7 +158,9 @@ class ListSet[A] extends Set[A] * @param elem the element to check for membership. * @return true, iff <code>elem</code> is contained in this set. */ - override def contains(e: A) = (e == elem) || self.contains(e) + 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)) /** This method creates a new set with an additional element. */ @@ -128,7 +174,5 @@ class ListSet[A] extends Set[A] } override protected def next: ListSet[A] = self - - override def stringPrefix = "Set" } } diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check index 3f095cb51e..9397d3f7e9 100644 --- a/test/files/jvm/serialization.check +++ b/test/files/jvm/serialization.check @@ -93,8 +93,8 @@ x = Map(buffers -> 20, layers -> 2, title -> 3) y = Map(buffers -> 20, layers -> 2, title -> 3) x equals y: true, y equals x: true -x = Set(5, 3) -y = Set(5, 3) +x = ListSet(5, 3) +y = ListSet(5, 3) x equals y: true, y equals x: true x = Queue(a, b, c) diff --git a/test/files/run/bug3822.scala b/test/files/run/bug3822.scala new file mode 100644 index 0000000000..7401ecbde2 --- /dev/null +++ b/test/files/run/bug3822.scala @@ -0,0 +1,13 @@ +import scala.collection.{ mutable, immutable, generic } +import immutable.ListSet + +object Test { + def main(args: Array[String]): Unit = { + val xs = ListSet(-100000 to 100001: _*) + + assert(xs.size == 200002) + assert(xs.sum == 100001) + } +} + + |