diff options
67 files changed, 981 insertions, 575 deletions
diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala index 6336a774c6..820195be3c 100644 --- a/src/library/scala/Array.scala +++ b/src/library/scala/Array.scala @@ -25,7 +25,6 @@ object Array extends SequenceFactory[Array] { import runtime.BoxedArray; import scala.runtime.ScalaRunTime.boxArray; - type Coll = Array[_] implicit def builderFactory[A]: BuilderFactory[A, Array[A], Coll] = new BuilderFactory[A, Array[A], Coll] { def apply(from: Coll) = newBuilder[A] } def newBuilder[A]: Builder[A, Array[A]] = new ArrayBuffer[A].mapResult(_.toArray) @@ -246,9 +245,11 @@ object Array extends SequenceFactory[Array] { * @author Martin Odersky * @version 1.0 */ -final class Array[A](_length: Int) extends Vector[A] with VectorTemplate[A, Array[A]] { +final class Array[A](_length: Int) extends Vector[A] + with TraversableClass[A, Array] + with VectorTemplate[A, Array[A]] { - override protected[this] def newBuilder: Builder[A, Array[A]] = throw new Error() + override def companion: Companion[Array] = throw new Error() /** Multidimensional array creation * @deprecated use Array.ofDim instead diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala index 2fb469e680..b7a77c63ce 100644 --- a/src/library/scala/collection/BitSet.scala +++ b/src/library/scala/collection/BitSet.scala @@ -15,17 +15,13 @@ import generic._ /** common base class for mutable and immutable bit sets */ -trait BitSet extends Set[Int] with BitSetTemplate[BitSet] { - override def empty = BitSet.empty +trait BitSet extends Set[Int] + with BitSetTemplate[BitSet] { + override def empty: BitSet = BitSet.empty } /** A factory object for bitsets */ -object BitSet { - - /** The empty bitset */ +object BitSet extends BitSetFactory[BitSet] { val empty: BitSet = immutable.BitSet.empty - - /** A bitset containing given elements */ - def apply(elems: Int*) = immutable.BitSet.apply(elems: _*) } diff --git a/src/library/scala/collection/Iterable.scala b/src/library/scala/collection/Iterable.scala index 42b6c5afe7..af52831428 100644 --- a/src/library/scala/collection/Iterable.scala +++ b/src/library/scala/collection/Iterable.scala @@ -31,9 +31,10 @@ import generic._ * @author Martin Odersky * @version 2.8 */ -trait Iterable[+A] extends Traversable[A] with IterableTemplate[A, Iterable[A]] { - override protected[this] def newBuilder = Iterable.newBuilder - override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B] +trait Iterable[+A] extends Traversable[A] + with TraversableClass[A, Iterable] + with IterableTemplate[A, Iterable[A]] { + override def companion: Companion[Iterable] = Iterable /* The following methods are inherited from trait IterableTemplate * @@ -44,13 +45,13 @@ trait Iterable[+A] extends Traversable[A] with IterableTemplate[A, Iterable[A]] override def view override def view(from: Int, until: Int) */ + } /** Factory methods and utilities for instances of type Traversable */ object Iterable extends TraversableFactory[Iterable] { - type Coll = Iterable[_] - implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Iterable[A]] = immutable.Iterable.newBuilder[A] def fromOld[A](it: scala.Iterable[A]): Iterable[A] = new Iterable[A] { diff --git a/src/library/scala/collection/LinearSequence.scala b/src/library/scala/collection/LinearSequence.scala index aed1b88a9a..676102fe35 100644 --- a/src/library/scala/collection/LinearSequence.scala +++ b/src/library/scala/collection/LinearSequence.scala @@ -26,13 +26,13 @@ import util.control.Breaks._ * @author Matthias Zenger * @version 1.0, 16/07/2003 */ -trait LinearSequence[+A] extends Sequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] { - override protected[this] def newBuilder = LinearSequence.newBuilder - override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B] +trait LinearSequence[+A] extends Sequence[A] + with TraversableClass[A, LinearSequence] + with LinearSequenceTemplate[A, LinearSequence[A]] { + override def companion: Companion[LinearSequence] = LinearSequence } object LinearSequence extends SequenceFactory[LinearSequence] { - type Coll = LinearSequence[_] - implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, LinearSequence[A]] = immutable.LinearSequence.newBuilder[A] } diff --git a/src/library/scala/collection/Map.scala b/src/library/scala/collection/Map.scala index 3544c195dd..174ed8e863 100644 --- a/src/library/scala/collection/Map.scala +++ b/src/library/scala/collection/Map.scala @@ -37,16 +37,11 @@ import generic._ */ trait Map[A, +B] extends Iterable[(A, B)] with MapTemplate[A, B, Map[A, B]] { def empty: Map[A, B] = Map.empty - - override protected[this] def newBuilder : Builder[(A, B), Map[A, B]] = - throw new UnsupportedOperationException("Map.newBuilder") - - def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B] + override protected[this] def newBuilder: Builder[(A, B), Map[A, B]] = immutable.Map.newBuilder[A, B] } /* Factory object for `Map` class */ object Map extends ImmutableMapFactory[immutable.Map] { - type Coll = Map[_, _] def empty[A, B]: immutable.Map[A, B] = immutable.Map.empty - implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B] } diff --git a/src/library/scala/collection/Sequence.scala b/src/library/scala/collection/Sequence.scala index 5391a89997..c5853355d4 100644 --- a/src/library/scala/collection/Sequence.scala +++ b/src/library/scala/collection/Sequence.scala @@ -28,15 +28,16 @@ import util.control.Breaks._ * @author Matthias Zenger * @version 1.0, 16/07/2003 */ -trait Sequence[+A] extends PartialFunction[Int, A] with Iterable[A] with SequenceTemplate[A, Sequence[A]] { - override protected[this] def newBuilder = Sequence.newBuilder - override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B] +trait Sequence[+A] extends PartialFunction[Int, A] + with Iterable[A] + with TraversableClass[A, Sequence] + with SequenceTemplate[A, Sequence[A]] { + override def companion: Companion[Sequence] = Sequence } object Sequence extends SequenceFactory[Sequence] { - type Coll = Sequence[_] - implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Sequence[A]] = immutable.Sequence.newBuilder[A] /** @deprecated use View instead diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala index 16cfbf3a1b..8a215a0bf2 100644 --- a/src/library/scala/collection/Set.scala +++ b/src/library/scala/collection/Set.scala @@ -21,16 +21,17 @@ import generic._ * @author Martin Odersky * @version 2.8 */ -trait Set[A] extends (A => Boolean) with Iterable[A] with SetTemplate[A, Set[A]] { - def empty = Set.empty - override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B] +trait Set[A] extends (A => Boolean) + with Iterable[A] + with SetClass[A, Set] + with SetTemplate[A, Set[A]] { + override def companion: Companion[Set] = Set } /* Factory object for `Set` class */ object Set extends SetFactory[Set] { - def empty[A]: Set[A] = immutable.Set.empty[A] - type Coll = Set[_] - implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + override def empty[A]: Set[A] = immutable.Set.empty[A] + implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A] } /* !!! what to do about this? diff --git a/src/library/scala/collection/SortedMap.scala b/src/library/scala/collection/SortedMap.scala index b2f44ebbac..1c1029da58 100644 --- a/src/library/scala/collection/SortedMap.scala +++ b/src/library/scala/collection/SortedMap.scala @@ -19,8 +19,16 @@ import generic._ */ trait SortedMap[A, +B] extends Map[A, B] with SortedMapTemplate[A, B, SortedMap[A, B]] { /** Needs to be overridden in subclasses. */ - override def empty: SortedMap[A, B] = throw new UnsupportedOperationException("SortedMap.empty") + override def empty = SortedMap.empty[A, B] + override protected[this] def newBuilder : Builder[(A, B), SortedMap[A, B]] = - throw new UnsupportedOperationException("SortedMap.newBuilder") + immutable.SortedMap.newBuilder[A, B] +} +object SortedMap extends ImmutableSortedMapFactory[immutable.SortedMap] { + implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), SortedMap[A, B], Coll] = new SortedMapBuilderFactory[A, B] + def empty[A, B](implicit ord: Ordering[A]): immutable.SortedMap[A, B] = immutable.SortedMap.empty[A, B](ord) } + + + diff --git a/src/library/scala/collection/Traversable.scala b/src/library/scala/collection/Traversable.scala index 39a7a188f0..4d2ace813c 100644 --- a/src/library/scala/collection/Traversable.scala +++ b/src/library/scala/collection/Traversable.scala @@ -25,9 +25,9 @@ import generic._ * @author Martin Odersky * @version 2.8 */ -trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] { - protected[this] def newBuilder = Traversable.newBuilder - def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B] +trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] + with TraversableClass[A, Traversable] { + def companion: Companion[Traversable] = Traversable /* The following methods are inherited from TraversableTemplate * @@ -93,10 +93,9 @@ trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] { /** Factory methods and utilities for instances of type Traversable */ object Traversable extends TraversableFactory[Traversable] { self => - type Coll = Traversable[_] - implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = - new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A] +// new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } def newBuilder[A]: Builder[A, Traversable[A]] = immutable.Traversable.newBuilder[A] diff --git a/src/library/scala/collection/Vector.scala b/src/library/scala/collection/Vector.scala index 7ac579283c..723fd8c610 100644 --- a/src/library/scala/collection/Vector.scala +++ b/src/library/scala/collection/Vector.scala @@ -21,13 +21,13 @@ import mutable.ArrayBuffer * @author Martin Odersky * @version 2.8 */ -trait Vector[+A] extends Sequence[A] with VectorTemplate[A, Vector[A]] { - override protected[this] def newBuilder = Vector.newBuilder - override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B] +trait Vector[+A] extends Sequence[A] + with TraversableClass[A, Vector] + with VectorTemplate[A, Vector[A]] { + override def companion: Companion[Vector] = Vector } object Vector extends SequenceFactory[Vector] { - type Coll = Vector[_] - implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Vector[A]] = mutable.Vector.newBuilder[A] } diff --git a/src/library/scala/collection/generic/BitSetFactory.scala b/src/library/scala/collection/generic/BitSetFactory.scala new file mode 100644 index 0000000000..479a857ee7 --- /dev/null +++ b/src/library/scala/collection/generic/BitSetFactory.scala @@ -0,0 +1,19 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ +// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $ +package scala.collection.generic + +trait BitSetFactory[Coll <: BitSet with BitSetTemplate[Coll]] { + def newBuilder: Builder[Int, Coll] = new AddingBuilder[Int, Coll](empty) + def empty: Coll + def apply(elems: Int*): Coll = (empty /: elems) (_ + _) + def bitsetBuilderFactory = new BuilderFactory[Int, Coll, Coll] { + def apply(from: Coll) = newBuilder + } +} + diff --git a/src/library/scala/collection/generic/BitSetTemplate.scala b/src/library/scala/collection/generic/BitSetTemplate.scala index 83c51d9aed..f5c5a64d4e 100644 --- a/src/library/scala/collection/generic/BitSetTemplate.scala +++ b/src/library/scala/collection/generic/BitSetTemplate.scala @@ -7,6 +7,8 @@ import generic._ */ trait BitSetTemplate[+This <: BitSetTemplate[This] with Set[Int]] extends SetTemplate[Int, This] { self => + def empty: This + /** The number of words (each with 64 bits) making up the set */ protected def nwords: Int diff --git a/src/library/scala/collection/generic/Companion.scala b/src/library/scala/collection/generic/Companion.scala new file mode 100644 index 0000000000..21bd6ece3e --- /dev/null +++ b/src/library/scala/collection/generic/Companion.scala @@ -0,0 +1,26 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ +// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $ +package scala.collection.generic + +abstract class Companion[+CC[X] <: Traversable[X]] { + type Coll = CC[_] + + def newBuilder[A]: Builder[A, CC[A]] + + /** The empty iterable of type CC */ + def empty[A]: CC[A] = newBuilder[A].result + + /** Creates an iterable of type CC with specified elements */ + def apply[A](args: A*): CC[A] = { + val b = newBuilder[A] + b ++= args + b.result + } +} + diff --git a/src/library/scala/collection/generic/ImmutableMapFactory.scala b/src/library/scala/collection/generic/ImmutableMapFactory.scala index 51758fe8c2..07eb37a4ad 100644 --- a/src/library/scala/collection/generic/ImmutableMapFactory.scala +++ b/src/library/scala/collection/generic/ImmutableMapFactory.scala @@ -2,15 +2,8 @@ package scala.collection.generic /** A template for companion objects of immutable.Map and subclasses thereof. */ -abstract class ImmutableMapFactory[CC[A, +B] <: immutable.Map[A, B] with MapTemplate[A, B, CC[A, B]]] { +abstract class ImmutableMapFactory[CC[A, +B] <: immutable.Map[A, B] with ImmutableMapTemplate[A, B, CC[A, B]]] + extends MapFactory[CC] { - def newBuilder[A, B]: Builder[(A, B), CC[A, B]] = new ImmutableMapBuilder[A, B, CC[A, B]](empty[A, B]) - - def empty[A, B]: CC[A, B] - - def apply[A, B](elems: (A, B)*): CC[A, B] = { - val b = newBuilder[A, B] - b ++= Iterable.fromOld(elems) - b.result - } + def newBuilder[A, B] = new ImmutableMapBuilder[A, B, CC[A, B]](empty[A, B]) } diff --git a/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala b/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala new file mode 100644 index 0000000000..d6751e24e9 --- /dev/null +++ b/src/library/scala/collection/generic/ImmutableSortedMapFactory.scala @@ -0,0 +1,10 @@ +package scala.collection.generic + +/** A template for companion objects of mutable.Map and subclasses thereof. + */ +abstract class ImmutableSortedMapFactory[CC[A, B] <: immutable.SortedMap[A, B] with SortedMapTemplate[A, B, CC[A, B]]] + extends SortedMapFactory[CC] { + + def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, B), CC[A, B]] = + new ImmutableMapBuilder[A, B, CC[A, B]](empty(ord)) +} diff --git a/src/library/scala/collection/generic/MapFactory.scala b/src/library/scala/collection/generic/MapFactory.scala new file mode 100644 index 0000000000..067f22dbf1 --- /dev/null +++ b/src/library/scala/collection/generic/MapFactory.scala @@ -0,0 +1,18 @@ +package scala.collection.generic + +/** A template for companion objects of mutable.Map and subclasses thereof. + */ +abstract class MapFactory[CC[A, B] <: Map[A, B] with MapTemplate[A, B, CC[A, B]]] { + + type Coll = CC[_, _] + + def newBuilder[A, B]: Builder[(A, B), CC[A, B]] + + def empty[A, B]: CC[A, B] + + def apply[A, B](elems: (A, B)*): CC[A, B] = (newBuilder[A, B] ++= elems).result + + class MapBuilderFactory[A, B] extends BuilderFactory[(A, B), CC[A, B], Coll] { + def apply(from: Coll) = newBuilder[A, B] + } +} diff --git a/src/library/scala/collection/generic/MapTemplate.scala b/src/library/scala/collection/generic/MapTemplate.scala index 3f2c9d2fb0..1076347977 100644 --- a/src/library/scala/collection/generic/MapTemplate.scala +++ b/src/library/scala/collection/generic/MapTemplate.scala @@ -33,8 +33,6 @@ trait MapTemplate[A, +B, +This <: MapTemplate[A, B, This] with Map[A, B]] with Subtractable[A, This] { self => -// import immutable.{Set, FlexSet} - def empty: This /** Is this an empty map? diff --git a/src/library/scala/collection/generic/MutableMapBuilder.scala b/src/library/scala/collection/generic/MutableMapBuilder.scala index 419eaef0a4..1e55a3b069 100644 --- a/src/library/scala/collection/generic/MutableMapBuilder.scala +++ b/src/library/scala/collection/generic/MutableMapBuilder.scala @@ -19,8 +19,8 @@ package scala.collection.generic */ class MutableMapBuilder[A, B, Coll <: mutable.Map[A, B] with MapTemplate[A, B, Coll]](empty: Coll) extends Builder[(A, B), Coll] { - protected var elems: Coll = empty + protected val elems: Coll = empty def +=(x: (A, B)): this.type = { elems += x; this } - def clear() { elems = empty } + def clear() { elems.clear() } def result: Coll = elems } diff --git a/src/library/scala/collection/generic/MutableMapFactory.scala b/src/library/scala/collection/generic/MutableMapFactory.scala index 9b3ccf7221..09fc16cd02 100644 --- a/src/library/scala/collection/generic/MutableMapFactory.scala +++ b/src/library/scala/collection/generic/MutableMapFactory.scala @@ -2,15 +2,8 @@ package scala.collection.generic /** A template for companion objects of mutable.Map and subclasses thereof. */ -abstract class MutableMapFactory[CC[A, B] <: mutable.Map[A, B] with MutableMapTemplate[A, B, CC[A, B]]] { +abstract class MutableMapFactory[CC[A, B] <: mutable.Map[A, B] with MutableMapTemplate[A, B, CC[A, B]]] + extends MapFactory[CC] { - def newBuilder[A, B]: Builder[(A, B), CC[A, B]] = new MutableMapBuilder(empty[A, B]) - - def empty[A, B]: CC[A, B] - - def apply[A, B](elems: (A, B)*): CC[A, B] = { - val b = newBuilder[A, B] - b ++= Iterable.fromOld(elems) - b.result - } + def newBuilder[A, B] = new MutableMapBuilder[A, B, CC[A, B]](empty[A, B]) } diff --git a/src/library/scala/collection/generic/SequenceFactory.scala b/src/library/scala/collection/generic/SequenceFactory.scala index b3ae8c7dd2..3a2979dd70 100644 --- a/src/library/scala/collection/generic/SequenceFactory.scala +++ b/src/library/scala/collection/generic/SequenceFactory.scala @@ -2,7 +2,7 @@ package scala.collection.generic /** A template for companion objects of Sequence and subclasses thereof. */ -abstract class SequenceFactory[CC[A] <: Sequence[A]] extends TraversableFactory[CC] { +abstract class SequenceFactory[CC[X] <: Sequence[X] with TraversableClass[X, CC]] extends TraversableFactory[CC] { /** This method is called in a pattern match { case Sequence(...) => }. * diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index b1643a1a62..c8f321075f 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -12,6 +12,7 @@ package scala.collection.generic import mutable.{ListBuffer, HashMap} + // import immutable.{List, Nil, ::} import generic._ import util.control.Breaks._ @@ -402,8 +403,12 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] b.result } - private def occCounts[B](seq: Sequence[B]): HashMap[B, Int] = { - val occ = new HashMap[B, Int] { override def default(k: B) = 0 } + private def occCounts[B](seq: Sequence[B]): mutable.Map[B, Int] = { + val occ = + if (seq.isEmpty || seq.head.isInstanceOf[Unhashable]) + new mutable.ListMap[B, Int] { override def default(k: B) = 0 } + else + new mutable.HashMap[B, Int] { override def default(k: B) = 0 } for (y <- seq) occ(y) += 1 occ } diff --git a/src/library/scala/collection/generic/SetClass.scala b/src/library/scala/collection/generic/SetClass.scala new file mode 100644 index 0000000000..0b38b7c91e --- /dev/null +++ b/src/library/scala/collection/generic/SetClass.scala @@ -0,0 +1,14 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ +// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $ +package scala.collection.generic + +trait SetClass[A, +CC[X] <: Set[X]] extends TraversableClass[A, CC] { + def empty: CC[A] = companion.empty[A] +} + diff --git a/src/library/scala/collection/generic/SetFactory.scala b/src/library/scala/collection/generic/SetFactory.scala index ea7bb69192..72774e659b 100644 --- a/src/library/scala/collection/generic/SetFactory.scala +++ b/src/library/scala/collection/generic/SetFactory.scala @@ -2,15 +2,12 @@ package scala.collection.generic /** A template for companion objects of Map and subclasses thereof. */ -abstract class SetFactory[CC[A] <: Set[A] with SetTemplate[A, CC[A]]] { +abstract class SetFactory[CC[X] <: Set[X] with SetTemplate[X, CC[X]]] + extends Companion[CC] { def newBuilder[A]: Builder[A, CC[A]] = new AddingBuilder[A, CC[A]](empty[A]) - def empty[A]: CC[A] - - def apply[A](elems: A*): CC[A] = { - var s = empty[A] - for (elem <- elems) s = s + elem - s + def setBuilderFactory[A] = new BuilderFactory[A, CC[A], CC[_]] { + def apply(from: CC[_]) = newBuilder[A] } } diff --git a/src/library/scala/collection/generic/SetTemplate.scala b/src/library/scala/collection/generic/SetTemplate.scala index 5d5abca295..ed706ab1bc 100644 --- a/src/library/scala/collection/generic/SetTemplate.scala +++ b/src/library/scala/collection/generic/SetTemplate.scala @@ -30,7 +30,6 @@ trait SetTemplate[A, +This <: SetTemplate[A, This] with Set[A]] extends Iterable self => def empty: This - override protected[this] def newBuilder: Builder[A, This] = new AddingBuilder[A, This](empty) /** Checks if this set contains element <code>elem</code>. diff --git a/src/library/scala/collection/generic/SortedMapFactory.scala b/src/library/scala/collection/generic/SortedMapFactory.scala new file mode 100644 index 0000000000..938ce145f9 --- /dev/null +++ b/src/library/scala/collection/generic/SortedMapFactory.scala @@ -0,0 +1,18 @@ +package scala.collection.generic + +/** A template for companion objects of mutable.Map and subclasses thereof. + */ +abstract class SortedMapFactory[CC[A, B] <: SortedMap[A, B] with SortedMapTemplate[A, B, CC[A, B]]] { + + type Coll = CC[_, _] + + def newBuilder[A, B](implicit ord: Ordering[A]): Builder[(A, B), CC[A, B]] + + def empty[A, B](implicit ord: Ordering[A]): CC[A, B] + + def apply[A, B](elems: (A, B)*)(implicit ord: Ordering[A]): CC[A, B] = (newBuilder[A, B](ord) ++= elems).result + + class SortedMapBuilderFactory[A, B](implicit ord: Ordering[A]) extends BuilderFactory[(A, B), CC[A, B], Coll] { + def apply(from: Coll) = newBuilder[A, B](ord) + } +} diff --git a/src/library/scala/collection/generic/SortedMapTemplate.scala b/src/library/scala/collection/generic/SortedMapTemplate.scala index eefd257136..90c81e8484 100644 --- a/src/library/scala/collection/generic/SortedMapTemplate.scala +++ b/src/library/scala/collection/generic/SortedMapTemplate.scala @@ -23,6 +23,8 @@ self => def firstKey : A = head._1 def lastKey : A = last._1 + implicit def ordering: Ordering[A] + // XXX: implement default version def rangeImpl(from : Option[A], until : Option[A]) : This diff --git a/src/library/scala/collection/generic/TraversableClass.scala b/src/library/scala/collection/generic/TraversableClass.scala new file mode 100644 index 0000000000..9ed2ff4eb3 --- /dev/null +++ b/src/library/scala/collection/generic/TraversableClass.scala @@ -0,0 +1,23 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ +// $Id: Traversable.scala 15188 2008-05-24 15:01:02Z stepancheg $ +package scala.collection.generic + +trait TraversableClass[+A, +CC[X] <: Traversable[X]] { + + /** The factory companion object that builds instances of class CC */ + + def companion: Companion[CC] + /** The builder that builds instances of CC[A] */ + + protected[this] def newBuilder: Builder[A, CC[A]] = companion.newBuilder[A] + + /** The generic builder that builds instances of CC at arbitrary element types. */ + def traversableBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B] +} + diff --git a/src/library/scala/collection/generic/TraversableFactory.scala b/src/library/scala/collection/generic/TraversableFactory.scala index e1d4f4bc24..d8afe73d02 100644 --- a/src/library/scala/collection/generic/TraversableFactory.scala +++ b/src/library/scala/collection/generic/TraversableFactory.scala @@ -2,20 +2,11 @@ /** A template for companion objects of Traversable and subclasses thereof. */ -abstract class TraversableFactory[CC[A] <: Traversable[A]] { +abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[X, CC]] + extends Companion[CC] { - /** The builder for this kind of collection. - */ - def newBuilder[A]: Builder[A, CC[A]] - - /** The empty iterable of type CC */ - def empty[A]: CC[A] = newBuilder[A].result - - /** Creates an iterable of type CC with specified elements */ - def apply[A](args: A*): CC[A] = { - val b = newBuilder[A] - b ++= Iterable.fromOld(args) - b.result + class VirtualBuilderFactory[A] extends BuilderFactory[A, CC[A], CC[_]] { + def apply(from: Coll) = from.traversableBuilder[A] } /** Concatenate all the argument collections into a single collection. diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index f3bfffff81..01c0d78b53 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -11,14 +11,16 @@ package scala.collection.immutable -import BitSet._ import generic._ import BitSetTemplate.{LogWL, updateArray} /** a base class for immutable bit sets */ -abstract class BitSet extends Set[Int] with collection.BitSet with BitSetTemplate[BitSet] { +abstract class BitSet extends Set[Int] + with collection.BitSet + with BitSetTemplate[BitSet] { override def empty = BitSet.empty + def fromArray(elems: Array[Long]): BitSet = BitSet.fromArray(elems) /** Update word at index `idx`; enlarge set if `idx` outside range of set @@ -48,13 +50,12 @@ abstract class BitSet extends Set[Int] with collection.BitSet with BitSetTemplat } /** A factory object for bitsets */ -object BitSet { +object BitSet extends BitSetFactory[BitSet] { /** The empty bitset */ val empty: BitSet = new BitSet1(0L) - /** A bitset containing given elements */ - def apply(elems: Int*) = (empty /: elems) (_ + _) + implicit def builderFactory: BuilderFactory[Int, BitSet, BitSet] = bitsetBuilderFactory /** A bitset containing all the bits in an array */ def fromArray(elems: Array[Long]): BitSet = { diff --git a/src/library/scala/collection/immutable/FlexMap.scala b/src/library/scala/collection/immutable/FlexMap.scala deleted file mode 100644 index 8370acd07c..0000000000 --- a/src/library/scala/collection/immutable/FlexMap.scala +++ /dev/null @@ -1,144 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -// $Id: Map.scala 16893 2009-01-13 13:09:22Z cunei $ - - -package scala.collection.immutable - -import generic._ - -/** A default implementation of immutable maps. - * This is implemented by specialized implementations - * `EmptyMap`, Map1, ..., Map4, for maps of size up to 4, and - * a proxy for an immutable HashMap for larger maps. - */ -trait FlexMap[A, +B] extends Map[A, B] { self => - override def empty: Map[A, B] = FlexMap.empty - def + [B1 >: B] (kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) -} - -/* Factory object for `FlexMap class */ -object FlexMap extends ImmutableMapFactory[Map] { - def empty[A, B]: FlexMap[A, B] = new EmptyMap[A, B] - - @serializable - class EmptyMap[A, +B] extends FlexMap[A, B] { - override def size: Int = 0 - def get(key: A): Option[B] = None - def elements: Iterator[(A, B)] = Iterator.empty - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = new Map1(key, value) - def - (key: A): Map[A, B] = this - } - - @serializable - class Map1[A, +B](key1: A, value1: B) extends FlexMap[A, B] { - override def size = 1 - def get(key: A): Option[B] = - if (key == key1) Some(value1) else None - def elements = Iterator((key1, value1)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = - if (key == key1) new Map1(key1, value) - else new Map2(key1, value1, key, value) - def - (key: A): Map[A, B] = - if (key == key1) empty else this - override def foreach[U](f: ((A, B)) => U): Unit = { - f((key1, value1)) - } - } - - @serializable - class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends FlexMap[A, B] { - override def size = 2 - def get(key: A): Option[B] = - if (key == key1) Some(value1) - else if (key == key2) Some(value2) - else None - def elements = Iterator((key1, value1), (key2, value2)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = - if (key == key1) new Map2(key1, value, key2, value2) - else if (key == key2) new Map2(key1, value1, key2, value) - else new Map3(key1, value1, key2, value2, key, value) - def - (key: A): Map[A, B] = - if (key == key1) new Map1(key2, value2) - else if (key == key2) new Map1(key1, value1) - else this - override def foreach[U](f: ((A, B)) => U): Unit = { - f((key1, value1)); f((key2, value2)) - } - } - - @serializable - class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends FlexMap[A, B] { - override def size = 3 - def get(key: A): Option[B] = - if (key == key1) Some(value1) - else if (key == key2) Some(value2) - else if (key == key3) Some(value3) - else None - def elements = Iterator((key1, value1), (key2, value2), (key3, value3)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = - if (key == key1) new Map3(key1, value, key2, value2, key3, value3) - else if (key == key2) new Map3(key1, value1, key2, value, key3, value3) - else if (key == key3) new Map3(key1, value1, key2, value2, key3, value) - else new Map4(key1, value1, key2, value2, key3, value3, key, value) - def - (key: A): Map[A, B] = - if (key == key1) new Map2(key2, value2, key3, value3) - else if (key == key2) new Map2(key1, value1, key3, value3) - else if (key == key3) new Map2(key1, value1, key2, value2) - else this - override def foreach[U](f: ((A, B)) => U): Unit = { - f((key1, value1)); f((key2, value2)); f((key3, value3)) - } - } - - @serializable - class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends FlexMap[A, B] { - override def size = 4 - def get(key: A): Option[B] = - if (key == key1) Some(value1) - else if (key == key2) Some(value2) - else if (key == key3) Some(value3) - else if (key == key4) Some(value4) - else None - def elements = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = - if (key == key1) new Map4(key1, value, key2, value2, key3, value3, key4, value4) - else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4) - else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4) - else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value) - else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value)) - def - (key: A): Map[A, B] = - if (key == key1) new Map3(key2, value2, key3, value3, key4, value4) - else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4) - else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4) - else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3) - else this - override def foreach[U](f: ((A, B)) => U): Unit = { - f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4)) - } - } -} - - - - - - - - - - - - - - - - - - diff --git a/src/library/scala/collection/immutable/FlexSet.scala b/src/library/scala/collection/immutable/FlexSet.scala deleted file mode 100644 index 37082a4407..0000000000 --- a/src/library/scala/collection/immutable/FlexSet.scala +++ /dev/null @@ -1,120 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $ - -package scala.collection.immutable - -import generic._ - -/** A default implementation of immutable sets. - * This is implemented by specialized implementations - * `EmptySet`, Set1, ..., Set4, for sets of size up to 4, and - * a proxy for an immutable HashSet for larger sets. - */ -trait FlexSet[A] extends Set[A] { self => - override def empty = FlexSet.empty -} - -/* Factory object for `FlexSet` class */ -object FlexSet extends SetFactory[Set] { - def empty[A]: FlexSet[A] = new EmptySet[A] - - /** An optimized representation for immutable empty sets */ - @serializable - class EmptySet[A] extends FlexSet[A] { - override def size: Int = 0 - def contains(elem: A): Boolean = false - def + (elem: A): Set[A] = new Set1(elem) - def - (elem: A): Set[A] = this - def elements: Iterator[A] = Iterator.empty - override def foreach[U](f: A => U): Unit = {} - } - - /** An optimized representation for immutable sets of size 1 */ - @serializable - class Set1[A](elem1: A) extends FlexSet[A] { - override def size: Int = 1 - def contains(elem: A): Boolean = - elem == elem1 - def + (elem: A): Set[A] = - if (contains(elem)) this - else new Set2(elem1, elem) - def - (elem: A): Set[A] = - if (elem == elem1) new EmptySet[A] - else this - def elements: Iterator[A] = - Iterator(elem1) - override def foreach[U](f: A => U): Unit = { - f(elem1) - } - } - - /** An optimized representation for immutable sets of size 2 */ - @serializable - class Set2[A](elem1: A, elem2: A) extends FlexSet[A] { - override def size: Int = 2 - def contains(elem: A): Boolean = - elem == elem1 || elem == elem2 - def + (elem: A): Set[A] = - if (contains(elem)) this - else new Set3(elem1, elem2, elem) - def - (elem: A): Set[A] = - if (elem == elem1) new Set1(elem2) - else if (elem == elem2) new Set1(elem1) - else this - def elements: Iterator[A] = - Iterator(elem1, elem2) - override def foreach[U](f: A => U): Unit = { - f(elem1); f(elem2) - } - } - - /** An optimized representation for immutable sets of size 3 */ - @serializable - class Set3[A](elem1: A, elem2: A, elem3: A) extends FlexSet[A] { - override def size: Int = 3 - def contains(elem: A): Boolean = - elem == elem1 || elem == elem2 || elem == elem3 - def + (elem: A): Set[A] = - if (contains(elem)) this - else new Set4(elem1, elem2, elem3, elem) - def - (elem: A): Set[A] = - if (elem == elem1) new Set2(elem2, elem3) - else if (elem == elem2) new Set2(elem1, elem3) - else if (elem == elem3) new Set2(elem1, elem2) - else this - def elements: Iterator[A] = - Iterator(elem1, elem2, elem3) - override def foreach[U](f: A => U): Unit = { - f(elem1); f(elem2); f(elem3) - } - } - - /** An optimized representation for immutable sets of size 4 */ - @serializable - class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends FlexSet[A] { - override def size: Int = 4 - def contains(elem: A): Boolean = - elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4 - def + (elem: A): Set[A] = - if (contains(elem)) this - else new HashSet[A] + (elem1, elem2, elem3, elem4, elem) - def - (elem: A): Set[A] = - if (elem == elem1) new Set3(elem2, elem3, elem4) - else if (elem == elem2) new Set3(elem1, elem3, elem4) - else if (elem == elem3) new Set3(elem1, elem2, elem4) - else if (elem == elem4) new Set3(elem1, elem2, elem3) - else this - def elements: Iterator[A] = - Iterator(elem1, elem2, elem3, elem4) - override def foreach[U](f: A => U): Unit = { - f(elem1); f(elem2); f(elem3); f(elem4) - } - } -} diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 7979d096aa..351cbf60d8 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -37,7 +37,6 @@ class HashMap[A, +B] extends Map[A,B] with ImmutableMapTemplate[A, B, HashMap[A, protected var deltaSize: Int = _ override def empty = HashMap.empty[A, B] - override def mapBuilder[A, B]: Builder[(A, B), HashMap[A, B]] = HashMap.newBuilder[A, B] def get(key: A): Option[B] = synchronized { var m: HashMap[A, _ >: B] = this @@ -176,8 +175,7 @@ class HashMap[A, +B] extends Map[A,B] with ImmutableMapTemplate[A, B, HashMap[A, * @version 2.8 */ object HashMap extends ImmutableMapFactory[HashMap] { - type Coll = HashMap[_, _] - implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new BuilderFactory[(A, B), HashMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B]: HashMap[A, B] = new HashMap } diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 3abffa6ec4..86efa9c6c6 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -25,10 +25,11 @@ import generic._ * @version 2.8 */ @serializable -class HashSet[A] extends Set[A] with SetTemplate[A, HashSet[A]] with mutable.FlatHashTable[A] { - - override def empty = HashSet.empty - override def traversableBuilder[B]: Builder[B, HashSet[B]] = HashSet.newBuilder[B] +class HashSet[A] extends Set[A] + with SetClass[A, HashSet] + with SetTemplate[A, HashSet[A]] + with mutable.FlatHashTable[A] { + override def companion: Companion[HashSet] = HashSet protected var later: HashSet[A] = null protected var changedElem: A = _ @@ -131,8 +132,7 @@ class HashSet[A] extends Set[A] with SetTemplate[A, HashSet[A]] with mutable.Fla * @version 2.8 */ object HashSet extends SetFactory[HashSet] { - type Coll = HashSet[_] - implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = new BuilderFactory[A, HashSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } - def empty[A]: HashSet[A] = new HashSet + implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A] + override def empty[A]: HashSet[A] = new HashSet } diff --git a/src/library/scala/collection/immutable/Iterable.scala b/src/library/scala/collection/immutable/Iterable.scala index 60f77bdc6f..bcc3951965 100644 --- a/src/library/scala/collection/immutable/Iterable.scala +++ b/src/library/scala/collection/immutable/Iterable.scala @@ -9,15 +9,16 @@ import generic._ * @autor Martin Odersky * @version 2.8 */ -trait Iterable[+A] extends Traversable[A] with collection.Iterable[A] with IterableTemplate[A, Iterable[A]] { self => - override protected[this] def newBuilder = Iterable.newBuilder - override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B] +trait Iterable[+A] extends Traversable[A] + with collection.Iterable[A] + with TraversableClass[A, Iterable] + with IterableTemplate[A, Iterable[A]] { + override def companion: Companion[Iterable] = Iterable } /* A factory object for the trait `Iterable` */ object Iterable extends TraversableFactory[Iterable] { - type Coll = Iterable[_] - implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Iterable[A]] = new mutable.ListBuffer } diff --git a/src/library/scala/collection/immutable/LinearSequence.scala b/src/library/scala/collection/immutable/LinearSequence.scala index 36e9a50428..6a9665e705 100644 --- a/src/library/scala/collection/immutable/LinearSequence.scala +++ b/src/library/scala/collection/immutable/LinearSequence.scala @@ -5,13 +5,14 @@ import generic._ /** A subtrait of collection.Sequence which represents sequences * that cannot be mutated. */ -trait LinearSequence[+A] extends Sequence[A] with collection.LinearSequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] { - override protected[this] def newBuilder = LinearSequence.newBuilder - override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B] +trait LinearSequence[+A] extends Sequence[A] + with collection.LinearSequence[A] + with TraversableClass[A, LinearSequence] + with LinearSequenceTemplate[A, LinearSequence[A]] { + override def companion: Companion[LinearSequence] = LinearSequence } object LinearSequence extends SequenceFactory[LinearSequence] { - type Coll = LinearSequence[_] - implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, LinearSequence[A]] = new mutable.ListBuffer } diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index e715fad0fa..acfbdc531f 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -12,7 +12,7 @@ package scala.collection.immutable import mutable.ListBuffer -import generic.{SequenceFactory, Builder, BuilderFactory, LinearSequenceTemplate} +import generic._ /** A class representing an ordered collection of elements of type * <code>a</code>. This class comes with two implementing case @@ -23,7 +23,11 @@ import generic.{SequenceFactory, Builder, BuilderFactory, LinearSequenceTemplate * @author Martin Odersky and others * @version 2.8 */ -sealed abstract class List[+A] extends LinearSequence[A] with Product with LinearSequenceTemplate[A, List[A]] { +sealed abstract class List[+A] extends LinearSequence[A] + with Product + with TraversableClass[A, List] + with LinearSequenceTemplate[A, List[A]] { + override def companion: Companion[List] = List import collection.{Iterable, Traversable, Sequence, Vector} @@ -46,10 +50,6 @@ sealed abstract class List[+A] extends LinearSequence[A] with Product with Linea */ def tail: List[A] - /** Creates a list buffer as builder for this class */ - override protected[this] def newBuilder = List.newBuilder - override def traversableBuilder[B]: Builder[B, List[B]] = List.newBuilder[B] - // New methods in List /** <p> @@ -488,8 +488,7 @@ object List extends SequenceFactory[List] { import collection.{Iterable, Sequence, Vector} - type Coll = List[_] - implicit def builderFactory[A]: BuilderFactory[A, List[A], Coll] = new BuilderFactory[A, List[A], Coll] { def apply(from: Coll) = new ListBuffer[A] } + implicit def builderFactory[A]: BuilderFactory[A, List[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, List[A]] = new ListBuffer[A] override def empty[A]: List[A] = Nil diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index b812cef8df..98aca89049 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -16,9 +16,7 @@ import generic._ /** The canonical factory of <a href="ListMap.html">ListMap</a>'s */ object ListMap extends ImmutableMapFactory[ListMap] { - - type Coll = ListMap[_,_] - implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new BuilderFactory[(A, B), ListMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B]: ListMap[A, B] = new ListMap } @@ -35,7 +33,6 @@ object ListMap extends ImmutableMapFactory[ListMap] { class ListMap[A, +B] extends Map[A, B] with ImmutableMapTemplate[A, B, ListMap[A, B]] { override def empty = ListMap.empty - override def mapBuilder[A, B]: Builder[(A, B), ListMap[A, B]] = ListMap.newBuilder[A, B] /** Returns the number of mappings in this map. * diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala index 6257e8c9cc..210413171b 100644 --- a/src/library/scala/collection/immutable/ListSet.scala +++ b/src/library/scala/collection/immutable/ListSet.scala @@ -15,9 +15,8 @@ import generic._ /** The canonical factory of <a href="ListSet.html">ListSet</a>'s */ object ListSet extends SetFactory[ListSet] { - type Coll = ListSet[_] - implicit def builderFactory[A]: BuilderFactory[A, ListSet[A], Coll] = new BuilderFactory[A, ListSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } - def empty[A] = new ListSet[A] + implicit def builderFactory[A]: BuilderFactory[A, ListSet[A], Coll] = setBuilderFactory[A] + override def empty[A] = new ListSet[A] } @@ -30,19 +29,18 @@ object ListSet extends SetFactory[ListSet] { * @version 1.0, 09/07/2003 */ @serializable -class ListSet[A] extends Set[A] with SetTemplate[A, ListSet[A]] { self => +class ListSet[A] extends Set[A] + with SetClass[A, ListSet] + with SetTemplate[A, ListSet[A]] { self => + override def companion: Companion[ListSet] = ListSet /** Returns the number of elements in this set. * * @return number of set elements. */ override def size: Int = 0 - override def isEmpty: Boolean = true; - override def empty = ListSet.empty - override def traversableBuilder[B]: Builder[B, ListSet[B]] = ListSet.newBuilder[B] - /** Checks if this set contains element <code>elem</code>. * * @param elem the element to check for membership. diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala index 8a1325735f..103d8f3d5a 100644 --- a/src/library/scala/collection/immutable/Map.scala +++ b/src/library/scala/collection/immutable/Map.scala @@ -18,7 +18,6 @@ trait Map[A, +B] extends Iterable[(A, B)] with ImmutableMapTemplate[A, B, Map[A, B]] { self => override def empty: Map[A, B] = Map.empty - override def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B] /** Add a key/value pair to this map. * @param key the key @@ -33,7 +32,6 @@ trait Map[A, +B] extends Iterable[(A, B)] override def hashCode() = (Map.hashSeed /: this) (_ * 41 + _.hashCode) - /** The same map with a given default function !!! todo: move to general maps? */ def withDefault[B1 >: B](d: A => B1): Map[A, B1] = new Map.WithDefault[A, B1](this, d) @@ -43,10 +41,9 @@ trait Map[A, +B] extends Iterable[(A, B)] object Map extends ImmutableMapFactory[Map] { private val hashSeed = "Map".hashCode - type Coll = Map[_, _] - implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B] - def empty[A, B]: Map[A, B] = FlexMap.empty + def empty[A, B]: Map[A, B] = new EmptyMap[A, B] class WithDefault[A, +B](underlying: Map[A, B], d: A => B) extends Map[A, B] { override def size = underlying.size @@ -58,5 +55,107 @@ object Map extends ImmutableMapFactory[Map] { def - (key: A): WithDefault[A, B] = new WithDefault(underlying - key, d) override def default(key: A): B = d(key) } + + @serializable + class EmptyMap[A, +B] extends Map[A, B] { + override def size: Int = 0 + def get(key: A): Option[B] = None + def elements: Iterator[(A, B)] = Iterator.empty + override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = new Map1(key, value) + def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) + def - (key: A): Map[A, B] = this + } + + @serializable + class Map1[A, +B](key1: A, value1: B) extends Map[A, B] { + override def size = 1 + def get(key: A): Option[B] = + if (key == key1) Some(value1) else None + def elements = Iterator((key1, value1)) + override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + if (key == key1) new Map1(key1, value) + else new Map2(key1, value1, key, value) + def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) + def - (key: A): Map[A, B] = + if (key == key1) empty else this + override def foreach[U](f: ((A, B)) => U): Unit = { + f((key1, value1)) + } + } + + @serializable + class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends Map[A, B] { + override def size = 2 + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else None + def elements = Iterator((key1, value1), (key2, value2)) + override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + if (key == key1) new Map2(key1, value, key2, value2) + else if (key == key2) new Map2(key1, value1, key2, value) + else new Map3(key1, value1, key2, value2, key, value) + def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) + def - (key: A): Map[A, B] = + if (key == key1) new Map1(key2, value2) + else if (key == key2) new Map1(key1, value1) + else this + override def foreach[U](f: ((A, B)) => U): Unit = { + f((key1, value1)); f((key2, value2)) + } + } + + @serializable + class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends Map[A, B] { + override def size = 3 + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else None + def elements = Iterator((key1, value1), (key2, value2), (key3, value3)) + override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + if (key == key1) new Map3(key1, value, key2, value2, key3, value3) + else if (key == key2) new Map3(key1, value1, key2, value, key3, value3) + else if (key == key3) new Map3(key1, value1, key2, value2, key3, value) + else new Map4(key1, value1, key2, value2, key3, value3, key, value) + def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) + def - (key: A): Map[A, B] = + if (key == key1) new Map2(key2, value2, key3, value3) + else if (key == key2) new Map2(key1, value1, key3, value3) + else if (key == key3) new Map2(key1, value1, key2, value2) + else this + override def foreach[U](f: ((A, B)) => U): Unit = { + f((key1, value1)); f((key2, value2)); f((key3, value3)) + } + } + + @serializable + class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends Map[A, B] { + override def size = 4 + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else if (key == key4) Some(value4) + else None + def elements = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4)) + override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + if (key == key1) new Map4(key1, value, key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4) + else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4) + else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value) + else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value)) + def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) + def - (key: A): Map[A, B] = + if (key == key1) new Map3(key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4) + else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4) + else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3) + else this + override def foreach[U](f: ((A, B)) => U): Unit = { + f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4)) + } + } } diff --git a/src/library/scala/collection/immutable/Sequence.scala b/src/library/scala/collection/immutable/Sequence.scala index 565937335f..715cabb705 100644 --- a/src/library/scala/collection/immutable/Sequence.scala +++ b/src/library/scala/collection/immutable/Sequence.scala @@ -12,15 +12,17 @@ import generic._ /** A subtrait of collection.Sequence which represents sequences * that cannot be mutated. */ -trait Sequence[+A] extends Iterable[A] with collection.Sequence[A] with SequenceTemplate[A, Sequence[A]] { - override protected[this] def newBuilder = Sequence.newBuilder - override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B] +trait Sequence[+A] extends Iterable[A] + with collection.Sequence[A] + with TraversableClass[A, Sequence] + with SequenceTemplate[A, Sequence[A]] { + override def companion: Companion[Sequence] = Sequence + override def hashCode = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode) } object Sequence extends SequenceFactory[Sequence] { private val hashSeed = "Sequence".hashCode - type Coll = Sequence[_] - implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Sequence[A]] = new mutable.ListBuffer } diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index 315f658542..78aaa54f1c 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -13,21 +13,125 @@ package scala.collection.immutable import generic._ -/** A generic trait for immutable sets +/** A generic trait for immutable sets. Concrete set implementations + * have to provide functionality for the abstract methods in Set: + * + * def contains(elem: A): Boolean + * def elements: Iterator[A] + * def + (elem: A): This + * def - (elem: A): This + * + * where `This` is the type of the set + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 */ -trait Set[A] extends Iterable[A] with collection.Set[A] with SetTemplate[A, Set[A]] { self => - - override def empty = Set.empty - +trait Set[A] extends Iterable[A] + with collection.Set[A] + with SetClass[A, Set] + with SetTemplate[A, Set[A]] { + override def companion: Companion[Set] = Set override def hashCode = (Set.hashSeed /: this)(_ * 41 + _.hashCode) - - override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B] } object Set extends SetFactory[Set] { + implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A] + override def empty[A]: Set[A] = new EmptySet[A] + private val hashSeed = "Set".hashCode - type Coll = Set[_] - implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } - def empty[A]: Set[A] = FlexSet.empty + + /** An optimized representation for immutable empty sets */ + @serializable + class EmptySet[A] extends Set[A] { + override def size: Int = 0 + def contains(elem: A): Boolean = false + def + (elem: A): Set[A] = new Set1(elem) + def - (elem: A): Set[A] = this + def elements: Iterator[A] = Iterator.empty + override def foreach[U](f: A => U): Unit = {} + } + + /** An optimized representation for immutable sets of size 1 */ + @serializable + class Set1[A](elem1: A) extends Set[A] { + override def size: Int = 1 + def contains(elem: A): Boolean = + elem == elem1 + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set2(elem1, elem) + def - (elem: A): Set[A] = + if (elem == elem1) new EmptySet[A] + else this + def elements: Iterator[A] = + Iterator(elem1) + override def foreach[U](f: A => U): Unit = { + f(elem1) + } + } + + /** An optimized representation for immutable sets of size 2 */ + @serializable + class Set2[A](elem1: A, elem2: A) extends Set[A] { + override def size: Int = 2 + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set3(elem1, elem2, elem) + def - (elem: A): Set[A] = + if (elem == elem1) new Set1(elem2) + else if (elem == elem2) new Set1(elem1) + else this + def elements: Iterator[A] = + Iterator(elem1, elem2) + override def foreach[U](f: A => U): Unit = { + f(elem1); f(elem2) + } + } + + /** An optimized representation for immutable sets of size 3 */ + @serializable + class Set3[A](elem1: A, elem2: A, elem3: A) extends Set[A] { + override def size: Int = 3 + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set4(elem1, elem2, elem3, elem) + def - (elem: A): Set[A] = + if (elem == elem1) new Set2(elem2, elem3) + else if (elem == elem2) new Set2(elem1, elem3) + else if (elem == elem3) new Set2(elem1, elem2) + else this + def elements: Iterator[A] = + Iterator(elem1, elem2, elem3) + override def foreach[U](f: A => U): Unit = { + f(elem1); f(elem2); f(elem3) + } + } + + /** An optimized representation for immutable sets of size 4 */ + @serializable + class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends Set[A] { + override def size: Int = 4 + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4 + def + (elem: A): Set[A] = + if (contains(elem)) this + else new HashSet[A] + (elem1, elem2, elem3, elem4, elem) + def - (elem: A): Set[A] = + if (elem == elem1) new Set3(elem2, elem3, elem4) + else if (elem == elem2) new Set3(elem1, elem3, elem4) + else if (elem == elem3) new Set3(elem1, elem2, elem4) + else if (elem == elem4) new Set3(elem1, elem2, elem3) + else this + def elements: Iterator[A] = + Iterator(elem1, elem2, elem3, elem4) + override def foreach[U](f: A => U): Unit = { + f(elem1); f(elem2); f(elem3); f(elem4) + } + } } diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala index 43a7562f84..2ce558fa00 100644 --- a/src/library/scala/collection/immutable/SortedMap.scala +++ b/src/library/scala/collection/immutable/SortedMap.scala @@ -25,12 +25,8 @@ trait SortedMap[A, +B] extends Map[A, B] with ImmutableMapTemplate[A, B, SortedMap[A, B]] with SortedMapTemplate[A, B, SortedMap[A, B]] { - /** Needs to be overridden in subclasses. */ - override def empty: SortedMap[A, B] = throw new AbstractMethodError("SortedMap.empty") - - /** Needs to be overridden in subclasses. */ override protected[this] def newBuilder : Builder[(A, B), SortedMap[A, B]] = - throw new AbstractMethodError("SortedMap.newBuilder") + immutable.SortedMap.newBuilder[A, B] override def updated [B1 >: B](key: A, value: B1): SortedMap[A, B1] = this + ((key, value)) @@ -109,3 +105,7 @@ trait SortedMap[A, +B] extends Map[A, B] override def plusAll [B1 >: B](iter: Iterator[(A, B1)]): SortedMap[A, B1] = this.++(iter) } +object SortedMap extends ImmutableSortedMapFactory[SortedMap] { + implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), SortedMap[A, B], Coll] = new SortedMapBuilderFactory[A, B] + def empty[A, B](implicit ord: Ordering[A]): SortedMap[A, B] = TreeMap.empty[A, B] +} diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 5e678edddf..7ac6b78bf4 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -12,7 +12,7 @@ package scala.collection.immutable import mutable.ListBuffer -import generic.{SequenceFactory, Builder, BuilderFactory, LazyBuilder, LinearSequenceTemplate} +import generic._ /** * <p>The class <code>Stream</code> implements lazy lists where elements @@ -35,8 +35,12 @@ import generic.{SequenceFactory, Builder, BuilderFactory, LazyBuilder, LinearSeq * @author Martin Odersky, Matthias Zenger * @version 1.1 08/08/03 */ -abstract class Stream[+A] extends LinearSequence[A] with LinearSequenceTemplate[A, Stream[A]] { +abstract class Stream[+A] extends LinearSequence[A] + with TraversableClass[A, Stream] + with LinearSequenceTemplate[A, Stream[A]] { self => + override def companion: Companion[Stream] = Stream + import collection.{Traversable, Iterable, Sequence, Vector} /** is this stream empty? */ @@ -57,14 +61,6 @@ self => // Implementation of abstract method in Traversable - /** The builder for stream objects. - * @note: This builder is lazy only in the sense that it does not go downs the spine - * of traversables taht are added as a whole. If more layzness can be achieved, - * this builder should be bypassed. - */ - override protected[this] def newBuilder = Stream.newBuilder - override def traversableBuilder[B]: Builder[B, Stream[B]] = Stream.newBuilder[B] - // New methods in Stream /** The stream resulting from the concatenation of this stream with the argument stream. @@ -367,8 +363,8 @@ self => */ object Stream extends SequenceFactory[Stream] { - type Coll = Stream[_] - class StreamBuilderFactory[A] extends BuilderFactory[A, Stream[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + class StreamBuilderFactory[A] extends VirtualBuilderFactory[A] + implicit def builderFactory[A]: BuilderFactory[A, Stream[A], Coll] = new StreamBuilderFactory[A] /** Creates a new builder for a stream */ @@ -377,6 +373,9 @@ object Stream extends SequenceFactory[Stream] { import collection.{Iterable, Sequence, Vector} /** A builder for streams + * @note: This builder is lazy only in the sense that it does not go downs the spine + * of traversables taht are added as a whole. If more layzness can be achieved, + * this builder should be bypassed. */ class StreamBuilder[A] extends LazyBuilder[A, Stream[A]] { def result: Stream[A] = (for (xs <- parts.elements; x <- xs.toIterable.elements) yield x).toStream diff --git a/src/library/scala/collection/immutable/Traversable.scala b/src/library/scala/collection/immutable/Traversable.scala index 302115a6d6..ffb389212b 100644 --- a/src/library/scala/collection/immutable/Traversable.scala +++ b/src/library/scala/collection/immutable/Traversable.scala @@ -9,15 +9,16 @@ import generic._ * @autor Martin Odersky * @version 2.8 */ -trait Traversable[+A] extends collection.Traversable[A] with TraversableTemplate[A, Traversable[A]] with Immutable { self => - override protected[this] def newBuilder = Traversable.newBuilder - override def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B] +trait Traversable[+A] extends collection.Traversable[A] + with TraversableClass[A, Traversable] + with TraversableTemplate[A, Traversable[A]] + with Immutable { + override def companion: Companion[Traversable] = Traversable } /* A factory object for the trait `Traversable` */ object Traversable extends TraversableFactory[Traversable] { - type Coll = Traversable[_] - implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Traversable[A]] = new mutable.ListBuffer } diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index fd596465a0..2298a64ba7 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -8,25 +8,15 @@ // $Id$ -// todo: make balanced once Tree.scala is updated to be covariant. - package scala.collection.immutable import generic._ /** The canonical factory of <a href="TreeMap.html">TreeMap</a>'s. */ -object TreeMap { - - type Coll = TreeMap[_, _] - implicit def builderFactory[A <% Ordered[A], B]: BuilderFactory[(A, B), TreeMap[A, B], Coll] = new BuilderFactory[(A, B), TreeMap[A, B], Coll] { def apply(from: Coll) = newBuilder[A, B] } - def newBuilder[A <% Ordered[A], B]: Builder[(A, B), TreeMap[A, B]] = new ImmutableMapBuilder(empty[A, B]) - - /** The empty map of this type */ - def empty[A <% Ordered[A], B] = new TreeMap[A, B] - - /** The canonical factory for this type - */ - def apply[A <% Ordered[A], B](elems: (A, B)*) = empty[A, B] ++ elems +object TreeMap extends ImmutableSortedMapFactory[TreeMap] { + def empty[A, B](implicit ord: Ordering[A]) = new TreeMap[A, B]()(ord) + implicit def builderFactory[A, B](implicit ord: Ordering[A]): BuilderFactory[(A, B), TreeMap[A, B], Coll] = new SortedMapBuilderFactory[A, B] + private def make[A, B](s: Int, t: RedBlack[A]#Tree[B])(implicit ord: Ordering[A]) = new TreeMap[A, B](s, t)(ord) } /** This class implements immutable maps using a tree. @@ -36,18 +26,18 @@ object TreeMap { * @version 1.1, 03/05/2004 */ @serializable -class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B]) +class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit val ordering: Ordering[A]) extends RedBlack[A] with SortedMap[A, B] with SortedMapTemplate[A, B, TreeMap[A, B]] with ImmutableMapTemplate[A, B, TreeMap[A, B]] { + def isSmaller(x: A, y: A) = ordering.lt(x, y) + override protected[this] def newBuilder : Builder[(A, B), TreeMap[A, B]] = TreeMap.newBuilder[A, B] - def isSmaller(x: A, y: A) = x < y - - def this() = this(0, null) + def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering) protected val tree: RedBlack[A]#Tree[B] = if (size == 0) Empty else t @@ -58,13 +48,11 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B override def firstKey = t.first override def lastKey = t.last - override def compare(k0: A, k1: A): Int = k0.compare(k1) - - private def newMap[B](s: Int, t: RedBlack[A]#Tree[B]) = new TreeMap[A, B](s, t) + override def compare(k0: A, k1: A): Int = ordering.compare(k0, k1) /** A factory to create empty maps of the same type of keys. */ - override def empty = TreeMap.empty + override def empty: TreeMap[A, B] = TreeMap.empty[A, B](ordering) /** A new TreeMap with the entry added is returned, * if key is <em>not</em> in the TreeMap, otherwise @@ -76,7 +64,7 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B */ override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = { val newsize = if (tree.lookup(key).isEmpty) size + 1 else size - newMap(newsize, tree.update(key, value)) + TreeMap.make(newsize, tree.update(key, value)) } /** Add a key/value pair to this map. @@ -94,19 +82,19 @@ class TreeMap[A <% Ordered[A], +B](override val size: Int, t: RedBlack[A]#Tree[B * @param elems the remaining elements to add. */ override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): TreeMap[A, B1] = - this + elem1 + elem2 ++ collection.Iterable.fromOld(elems) + this + elem1 + elem2 ++ elems /** A new TreeMap with the entry added is returned, * assuming that key is <em>not</em> in the TreeMap. */ def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = { assert(tree.lookup(key).isEmpty) - newMap(size + 1, tree.update(key, value)) + TreeMap.make(size + 1, tree.update(key, value)) } def - (key:A): TreeMap[A, B] = if (tree.lookup(key).isEmpty) this - else newMap(size - 1, tree.delete(key)) + else TreeMap.make(size - 1, tree.delete(key)) /** Check if this map maps <code>key</code> to a value and return the * value if it exists. diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 2fe3f36e67..58ff1ceafd 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -13,17 +13,18 @@ import mutable.ArrayBuffer /** A subtrait of collection.Vector which represents sequences * that cannot be mutated. */ -trait Vector[+A] extends Sequence[A] with collection.Vector[A] with VectorTemplate[A, Vector[A]] { self => - override protected[this] def newBuilder = Vector.newBuilder - override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B] +trait Vector[+A] extends Sequence[A] + with collection.Vector[A] + with TraversableClass[A, Vector] + with VectorTemplate[A, Vector[A]] { + override def companion: Companion[Vector] = Vector } object Vector extends SequenceFactory[Vector] { - type Coll = Vector[_] - class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] { // todo: insert better vector implementation here + class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] { // todo: insert better vector implementation here def length = buf.length def apply(idx: Int) = buf.apply(idx) } - implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Vector[A]] = new ArrayBuffer[A] mapResult (buf => new Impl(buf)) } diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala index 2e37d55ed2..8586ae3fee 100644 --- a/src/library/scala/collection/mutable/ArrayBuffer.scala +++ b/src/library/scala/collection/mutable/ArrayBuffer.scala @@ -25,11 +25,14 @@ import generic._ @serializable class ArrayBuffer[A](override protected val initialSize: Int) extends Buffer[A] + with TraversableClass[A, ArrayBuffer] with BufferTemplate[A, ArrayBuffer[A]] with VectorTemplate[A, ArrayBuffer[A]] with Builder[A, ArrayBuffer[A]] with ResizableArray[A] { + override def companion: Companion[ArrayBuffer] = ArrayBuffer + import collection.Traversable def this() = this(16) @@ -42,9 +45,6 @@ class ArrayBuffer[A](override protected val initialSize: Int) array = newarray } - override protected[this] def newBuilder = ArrayBuffer.newBuilder - override def traversableBuilder[B]: Builder[B, ArrayBuffer[B]] = ArrayBuffer.newBuilder[B] - /** Appends a single element to this buffer and returns * the identity of the buffer. It takes constant time. * @@ -159,8 +159,7 @@ class ArrayBuffer[A](override protected val initialSize: Int) /* Factory object for `ArrayBuffer` class */ object ArrayBuffer extends SequenceFactory[ArrayBuffer] { - type Coll = ArrayBuffer[_] - implicit def builderFactory[A]: BuilderFactory[A, ArrayBuffer[A], Coll] = new BuilderFactory[A, ArrayBuffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, ArrayBuffer[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, ArrayBuffer[A]] = new ArrayBuffer[A] } diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala index 9518597b2f..996130766c 100644 --- a/src/library/scala/collection/mutable/BitSet.scala +++ b/src/library/scala/collection/mutable/BitSet.scala @@ -4,7 +4,10 @@ import generic._ import BitSetTemplate.{LogWL, updateArray} /** A class for mutable bitsets */ -class BitSet (protected var elems: Array[Long]) extends Set[Int] with collection.BitSet with BitSetTemplate[BitSet] with MutableSetTemplate[Int, BitSet] { +class BitSet (protected var elems: Array[Long]) extends Set[Int] + with collection.BitSet + with BitSetTemplate[BitSet] + with MutableSetTemplate[Int, BitSet] { override def empty = BitSet.empty @@ -67,9 +70,7 @@ class BitSet (protected var elems: Array[Long]) extends Set[Int] with collection } /** A factory object for mutable bitsets */ -object BitSet { +object BitSet extends BitSetFactory[BitSet] { def empty: BitSet = new BitSet - def apply(bits: Int*): BitSet = { - var s = empty; for (b <- bits) s += b; s - } + implicit def builderFactory: BuilderFactory[Int, BitSet, BitSet] = bitsetBuilderFactory } diff --git a/src/library/scala/collection/mutable/Buffer.scala b/src/library/scala/collection/mutable/Buffer.scala index f2e0997294..2099f134fc 100644 --- a/src/library/scala/collection/mutable/Buffer.scala +++ b/src/library/scala/collection/mutable/Buffer.scala @@ -23,15 +23,15 @@ import generic._ * @version 2.8 */ @cloneable -trait Buffer[A] extends Sequence[A] with BufferTemplate[A, Buffer[A]] { - override protected[this] def newBuilder = Buffer.newBuilder - override def traversableBuilder[B]: Builder[B, Buffer[B]] = Buffer.newBuilder[B] +trait Buffer[A] extends Sequence[A] + with TraversableClass[A, Buffer] + with BufferTemplate[A, Buffer[A]] { + override def companion: Companion[Buffer] = Buffer } /* Factory object for `Buffer` trait */ object Buffer extends SequenceFactory[Buffer] { - type Coll = Buffer[_] - implicit def builderFactory[A]: BuilderFactory[A, Buffer[A], Coll] = new BuilderFactory[A, Buffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Buffer[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Buffer[A]] = new ArrayBuffer } diff --git a/src/library/scala/collection/mutable/DoubleLinkedList.scala b/src/library/scala/collection/mutable/DoubleLinkedList.scala index 1c67e3a413..aeaaf71808 100644 --- a/src/library/scala/collection/mutable/DoubleLinkedList.scala +++ b/src/library/scala/collection/mutable/DoubleLinkedList.scala @@ -1,10 +1,12 @@ +/* TODO: reintegrate + /* __ *\ ** ________ ___ / / ___ Scala API ** ** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** -\* */ +* */ // $Id$ @@ -27,10 +29,10 @@ class DoubleLinkedList[A]/*(_elem: A, _next: DoubleLinkedList[A])*/ extends Line } object DoubleLinkedList extends SequenceFactory[DoubleLinkedList] { - type Coll = DoubleLinkedList[_] implicit def builderFactory[A]: BuilderFactory[A, DoubleLinkedList[A], Coll] = new BuilderFactory[A, DoubleLinkedList[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } def newBuilder[A]: Builder[A, DoubleLinkedList[A]] = null // !!! } +*/ diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index a2cce3358b..d80e514ac8 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -18,7 +18,6 @@ import generic._ class HashMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, HashMap[A, B]] with HashTable[A] with DefaultMapModel[A, B] { override def empty: HashMap[A, B] = HashMap.empty[A, B] - override def mapBuilder[A, B]: Builder[(A, B), HashMap[A, B]] = HashMap.newBuilder[A, B] override def remove(key: A): Option[B] = removeEntry(key) match { case Some(e) => Some(e.value) @@ -39,7 +38,6 @@ class HashMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, HashMap[A, B * @version 2.8 */ object HashMap extends MutableMapFactory[HashMap] { - type Coll = HashMap[_, _] - implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new BuilderFactory[(A, B), HashMap[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), HashMap[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B]: HashMap[A, B] = new HashMap[A, B] } diff --git a/src/library/scala/collection/mutable/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala index b72f3dc6fd..5c93ff96eb 100644 --- a/src/library/scala/collection/mutable/HashSet.scala +++ b/src/library/scala/collection/mutable/HashSet.scala @@ -20,10 +20,11 @@ import generic._ * @version 2.0, 31/12/2006 */ @serializable -class HashSet[A] extends Set[A] with MutableSetTemplate[A, HashSet[A]] with FlatHashTable[A] { - - override def empty = HashSet.empty - override def traversableBuilder[B]: Builder[B, HashSet[B]] = HashSet.newBuilder[B] +class HashSet[A] extends Set[A] + with SetClass[A, HashSet] + with MutableSetTemplate[A, HashSet[A]] + with FlatHashTable[A] { + override def companion: Companion[HashSet] = HashSet override def size = super.size @@ -52,8 +53,7 @@ class HashSet[A] extends Set[A] with MutableSetTemplate[A, HashSet[A]] with Flat /** Factory object for `HashSet` class */ object HashSet extends SetFactory[HashSet] { - type Coll = HashSet[_] - implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = new BuilderFactory[A, HashSet[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } - def empty[A]: HashSet[A] = new HashSet[A] + implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A] + override def empty[A]: HashSet[A] = new HashSet[A] } diff --git a/src/library/scala/collection/mutable/Iterable.scala b/src/library/scala/collection/mutable/Iterable.scala index f7896dc3cc..18ca5588d6 100644 --- a/src/library/scala/collection/mutable/Iterable.scala +++ b/src/library/scala/collection/mutable/Iterable.scala @@ -15,15 +15,16 @@ import generic._ * @autor Martin Odersky * @version 2.8 */ -trait Iterable[A] extends Traversable[A] with collection.Iterable[A] with IterableTemplate[A, Iterable[A]] { self => - override protected[this] def newBuilder = Iterable.newBuilder - override def traversableBuilder[B]: Builder[B, Iterable[B]] = Iterable.newBuilder[B] +trait Iterable[A] extends Traversable[A] + with collection.Iterable[A] + with TraversableClass[A, Iterable] + with IterableTemplate[A, Iterable[A]] { + override def companion: Companion[Iterable] = Iterable } /* A factory object for the trait `Iterable` */ object Iterable extends TraversableFactory[Iterable] { - type Coll = Iterable[_] - implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new BuilderFactory[A, Iterable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Iterable[A]] = new ArrayBuffer } diff --git a/src/library/scala/collection/mutable/LinearSequence.scala b/src/library/scala/collection/mutable/LinearSequence.scala index 60858bcb77..3d71be1f81 100644 --- a/src/library/scala/collection/mutable/LinearSequence.scala +++ b/src/library/scala/collection/mutable/LinearSequence.scala @@ -5,13 +5,14 @@ import generic._ /** A subtrait of collection.Sequence which represents sequences * that cannot be mutated. */ -trait LinearSequence[A] extends Sequence[A] with collection.LinearSequence[A] with LinearSequenceTemplate[A, LinearSequence[A]] { - override protected[this] def newBuilder = LinearSequence.newBuilder - override def traversableBuilder[B]: Builder[B, LinearSequence[B]] = LinearSequence.newBuilder[B] +trait LinearSequence[A] extends Sequence[A] + with collection.LinearSequence[A] + with TraversableClass[A, LinearSequence] + with LinearSequenceTemplate[A, LinearSequence[A]] { + override def companion: Companion[LinearSequence] = LinearSequence } object LinearSequence extends SequenceFactory[LinearSequence] { - type Coll = LinearSequence[_] - implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new BuilderFactory[A, LinearSequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, LinearSequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, LinearSequence[A]] = new MutableList[A] } diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala index e02e574c43..476bd39b7e 100644 --- a/src/library/scala/collection/mutable/LinkedHashMap.scala +++ b/src/library/scala/collection/mutable/LinkedHashMap.scala @@ -12,6 +12,7 @@ package scala.collection.mutable import Predef._ +import generic._ /** This class implements mutable maps using a hashtable. * @@ -19,20 +20,19 @@ import Predef._ * @author Martin Odersky * @version 2.0, 31/12/2006 */ -object LinkedHashMap { - - /** The empty map of this type */ +object LinkedHashMap extends MutableMapFactory[LinkedHashMap] { + implicit def builderFactory[A, B]: BuilderFactory[(A, B), LinkedHashMap[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B] = new LinkedHashMap[A, B] - - /** The canonical factory for this type - */ - def apply[A, B](elems: (A, B)*) = empty[A, B] ++ elems } @serializable -class LinkedHashMap[A, B] extends Map[A,B] with HashTable[A] with DefaultMapModel[A,B] { +class LinkedHashMap[A, B] extends Map[A, B] + with MutableMapTemplate[A, B, LinkedHashMap[A, B]] + with HashTable[A] + with DefaultMapModel[A,B] { override def empty = LinkedHashMap.empty + override def size = super[HashTable].size private var ordered = List[Entry]() @@ -66,7 +66,5 @@ class LinkedHashMap[A, B] extends Map[A,B] with HashTable[A] with DefaultMapMode super.clear() } - override def clone(): Map[A, B] = new LinkedHashMap[A, B] ++ this - override def elements = ordered.reverse.elements map {e => (e.key, e.value)} } diff --git a/src/library/scala/collection/mutable/LinkedList.scala b/src/library/scala/collection/mutable/LinkedList.scala index 47be78a8ed..90c88439b4 100644 --- a/src/library/scala/collection/mutable/LinkedList.scala +++ b/src/library/scala/collection/mutable/LinkedList.scala @@ -21,16 +21,16 @@ import generic._ * @version 2.8 */ @serializable -class LinkedList[A](_elem: A, _next: LinkedList[A]) extends LinearSequence[A] with LinkedListTemplate[A, LinkedList[A]] { +class LinkedList[A](_elem: A, _next: LinkedList[A]) extends LinearSequence[A] + with TraversableClass[A, LinkedList] + with LinkedListTemplate[A, LinkedList[A]] { elem = _elem next = _next - override protected[this] def newBuilder = LinkedList.newBuilder - override def traversableBuilder[B]: Builder[B, LinkedList[B]] = LinkedList.newBuilder[B] + override def companion: Companion[LinkedList] = LinkedList } object LinkedList extends SequenceFactory[LinkedList] { - type Coll = LinkedList[_] - implicit def builderFactory[A]: BuilderFactory[A, LinkedList[A], Coll] = new BuilderFactory[A, LinkedList[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, LinkedList[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, LinkedList[A]] = (new MutableList) mapResult ((l: MutableList[A]) => l.toLinkedList) } diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala index 22396f1322..a83f620699 100644 --- a/src/library/scala/collection/mutable/ListBuffer.scala +++ b/src/library/scala/collection/mutable/ListBuffer.scala @@ -24,10 +24,13 @@ import generic._ @serializable final class ListBuffer[A] extends Buffer[A] + with TraversableClass[A, ListBuffer] with BufferTemplate[A, ListBuffer[A]] with Builder[A, List[A]] with SequenceForwarder[A] { + override def companion: Companion[ListBuffer] = ListBuffer + import collection.Traversable private var start: List[A] = Nil @@ -37,9 +40,6 @@ final class ListBuffer[A] protected def underlying: immutable.Sequence[A] = start - override protected[this] def newBuilder = ListBuffer.newBuilder[A] - override def traversableBuilder[B]: Builder[B, ListBuffer[B]] = ListBuffer.newBuilder[B] - /** The current length of the buffer */ override def length = len @@ -320,8 +320,7 @@ final class ListBuffer[A] /* Factory object for `ListBuffer` class */ object ListBuffer extends SequenceFactory[ListBuffer] { - type Coll = ListBuffer[_] - implicit def builderFactory[A]: BuilderFactory[A, ListBuffer[A], Coll] = new BuilderFactory[A, ListBuffer[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, ListBuffer[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, ListBuffer[A]] = new AddingBuilder(new ListBuffer[A]) } diff --git a/src/library/scala/collection/mutable/ListMap.scala b/src/library/scala/collection/mutable/ListMap.scala new file mode 100644 index 0000000000..8b8e5d87a6 --- /dev/null +++ b/src/library/scala/collection/mutable/ListMap.scala @@ -0,0 +1,47 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashMap.scala 17715 2009-05-12 18:33:22Z odersky $ + + +package scala.collection.mutable + +import generic._ + +@serializable +class ListMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, ListMap[A, B]] { + + + override def empty = ListMap.empty[A, B] + + private var elems: List[(A, B)] = List() + private var siz: Int = 0 + + def get(key: A): Option[B] = elems find (_._1 == key) map (_._2) + def elements: Iterator[(A, B)] = elems.elements + def += (kv: (A, B)) = { elems = remove(kv._1, elems); elems = kv :: elems; siz += 1; this } + def -= (key: A) = { elems = remove(key, elems); this } + + private def remove(key: A, elems: List[(A, B)]): List[(A, B)] = + if (elems.isEmpty) elems + else if (elems.head._1 == key) { siz -= 1; elems.tail } + else elems.head :: remove(key, elems.tail) + + override def clear() = elems = List() + override def size: Int = siz +} + +/** This class implements mutable maps using a list. + * + * @author Martin Odersky + * @version 2.8 + */ +object ListMap extends MutableMapFactory[ListMap] { + implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new MapBuilderFactory[A, B] + def empty[A, B]: ListMap[A, B] = new ListMap[A, B] +} diff --git a/src/library/scala/collection/mutable/Map.scala b/src/library/scala/collection/mutable/Map.scala index 17c3e81472..94e376cd67 100644 --- a/src/library/scala/collection/mutable/Map.scala +++ b/src/library/scala/collection/mutable/Map.scala @@ -20,7 +20,6 @@ trait Map[A, B] with Unhashable { override def empty: Map[A, B] = Map.empty - override def mapBuilder[A, B]: Builder[(A, B), Map[A, B]] = Map.newBuilder[A, B] /** Return a read-only projection of this map. !!! or just use an (immutable) MapProxy? def readOnly : collection.Map[A, B] = new collection.Map[A, B] { @@ -38,8 +37,7 @@ trait Map[A, B] * Currently this returns a HashMap. */ object Map extends MutableMapFactory[Map] { - type Coll = Map[_, _] - implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new BuilderFactory[(A, B), Map[A, B], Coll] { def apply(from: Coll) = from.mapBuilder[A, B] } + implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B]: Map[A, B] = new HashMap[A, B] } diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala index b7d0c14806..6f8d58ad47 100644 --- a/src/library/scala/collection/mutable/ResizableArray.scala +++ b/src/library/scala/collection/mutable/ResizableArray.scala @@ -20,13 +20,11 @@ import generic._ * @author Martin Odersky * @version 2.8 */ -trait ResizableArray[A] extends Vector[A] with VectorTemplate[A, ResizableArray[A]] { self => +trait ResizableArray[A] extends Vector[A] + with TraversableClass[A, ResizableArray] + with VectorTemplate[A, ResizableArray[A]] { - import scala.Array // !!! - import collection.Iterable // !!! - - override protected[this] def newBuilder = ResizableArray.newBuilder - override def traversableBuilder[B]: Builder[B, ResizableArray[B]] = ResizableArray.newBuilder[B] + override def companion: Companion[ResizableArray] = ResizableArray protected def initialSize: Int = 16 protected var array: Array[AnyRef] = new Array[AnyRef](initialSize max 1) @@ -115,7 +113,6 @@ trait ResizableArray[A] extends Vector[A] with VectorTemplate[A, ResizableArray[ } object ResizableArray extends SequenceFactory[ResizableArray] { - type Coll = Vector[_] - implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, ResizableArray[A]] = new ArrayBuffer[A] } diff --git a/src/library/scala/collection/mutable/Sequence.scala b/src/library/scala/collection/mutable/Sequence.scala index efc4092853..4f460f74c7 100644 --- a/src/library/scala/collection/mutable/Sequence.scala +++ b/src/library/scala/collection/mutable/Sequence.scala @@ -13,15 +13,17 @@ import generic._ * that can be mutated. * The class adds an `update` method to collection.Sequence. */ -trait Sequence[A] extends Iterable[A] with collection.Sequence[A] with SequenceTemplate[A, Sequence[A]] with Unhashable { - override protected[this] def newBuilder = Sequence.newBuilder - override def traversableBuilder[B]: Builder[B, Sequence[B]] = Sequence.newBuilder[B] +trait Sequence[A] extends Iterable[A] + with collection.Sequence[A] + with TraversableClass[A, Sequence] + with SequenceTemplate[A, Sequence[A]] + with Unhashable { + override def companion: Companion[Sequence] = Sequence def update(idx: Int, elem: A) } object Sequence extends SequenceFactory[Sequence] { - type Coll = Sequence[_] - implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new BuilderFactory[A, Sequence[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Sequence[A]] = new ArrayBuffer } diff --git a/src/library/scala/collection/mutable/Set.scala b/src/library/scala/collection/mutable/Set.scala index 79a31cc5ef..8118f8a58f 100644 --- a/src/library/scala/collection/mutable/Set.scala +++ b/src/library/scala/collection/mutable/Set.scala @@ -13,7 +13,7 @@ package scala.collection.mutable import generic._ -/** This class represents mutable sets. Concrete set implementations +/** A generic trait for mutable sets. Concrete set implementations * have to provide functionality for the abstract methods in Set: * * def contains(elem: A): Boolean @@ -27,20 +27,17 @@ import generic._ */ trait Set[A] extends Iterable[A] with collection.Set[A] + with SetClass[A, Set] with MutableSetTemplate[A, Set[A]] with Unhashable { - - override def empty = Set.empty - - override def traversableBuilder[B]: Builder[B, Set[B]] = Set.newBuilder[B] + override def companion: Companion[Set] = Set } /** The canonical factory methods for <a href="Set.html">mutable sets</a>. * Currently this returns a HashSet. */ object Set extends SetFactory[Set] { - type Coll = Set[_] - implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = new BuilderFactory[A, Set[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } - def empty[A]: Set[A] = HashSet.empty[A] + implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A] + override def empty[A]: Set[A] = HashSet.empty[A] } diff --git a/src/library/scala/collection/mutable/SynchronizedMap.scala b/src/library/scala/collection/mutable/SynchronizedMap.scala index 1afc02ed57..838b987e9b 100644 --- a/src/library/scala/collection/mutable/SynchronizedMap.scala +++ b/src/library/scala/collection/mutable/SynchronizedMap.scala @@ -23,7 +23,6 @@ trait SynchronizedMap[A, B] extends Map[A, B] { import collection.Traversable - override def mapBuilder[A, B]: Builder[(A, B), SynchronizedMap[A, B]] = SynchronizedMap.newBuilder[A, B] abstract override def size: Int = synchronized { super.size diff --git a/src/library/scala/collection/mutable/Traversable.scala b/src/library/scala/collection/mutable/Traversable.scala index 72b7271b85..46a99c7b42 100644 --- a/src/library/scala/collection/mutable/Traversable.scala +++ b/src/library/scala/collection/mutable/Traversable.scala @@ -15,15 +15,16 @@ import generic._ * @autor Martin Odersky * @version 2.8 */ -trait Traversable[A] extends collection.Traversable[A] with TraversableTemplate[A, Traversable[A]] with Mutable { self => - override protected[this] def newBuilder = Traversable.newBuilder - override def traversableBuilder[B]: Builder[B, Traversable[B]] = Traversable.newBuilder[B] +trait Traversable[A] extends collection.Traversable[A] + with TraversableClass[A, Traversable] + with TraversableTemplate[A, Traversable[A]] + with Mutable { + override def companion: Companion[Traversable] = Traversable } /* A factory object for the trait `Traversable` */ object Traversable extends TraversableFactory[Traversable] { - type Coll = Traversable[_] - implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new BuilderFactory[A, Traversable[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Traversable[A]] = new ArrayBuffer } diff --git a/src/library/scala/collection/mutable/Vector.scala b/src/library/scala/collection/mutable/Vector.scala index dae5c4864f..db082bb09d 100644 --- a/src/library/scala/collection/mutable/Vector.scala +++ b/src/library/scala/collection/mutable/Vector.scala @@ -12,13 +12,14 @@ import generic._ /** A subtrait of collection.Vector which represents sequences * that can be mutated. */ -trait Vector[A] extends Sequence[A] with collection.Vector[A] with MutableVectorTemplate[A, Vector[A]] { - override protected[this] def newBuilder = Vector.newBuilder - override def traversableBuilder[B]: Builder[B, Vector[B]] = Vector.newBuilder[B] +trait Vector[A] extends Sequence[A] + with collection.Vector[A] + with TraversableClass[A, Vector] + with MutableVectorTemplate[A, Vector[A]] { + override def companion: Companion[Vector] = Vector } object Vector extends SequenceFactory[Vector] { - type Coll = Vector[_] - implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new BuilderFactory[A, Vector[A], Coll] { def apply(from: Coll) = from.traversableBuilder[A] } + implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Vector[A]] = new ArrayBuffer } diff --git a/test/files/run/colltest1.check b/test/files/run/colltest1.check new file mode 100644 index 0000000000..079c57910a --- /dev/null +++ b/test/files/run/colltest1.check @@ -0,0 +1,99 @@ +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with Stream() +10: Stream(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: Stream(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +Stream(1, ?) +new test starting with Array() +10: Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: Array(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with ArrayBuffer() +10: ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with ListBuffer() +10: ListBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ListBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +ListBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with ArrayBuffer() +10: ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with ArrayBuffer() +10: ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with ArrayBuffer() +10: ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with List() +10: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: List(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +new test starting with ArrayBuffer() +10: ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +9: ArrayBuffer(2, 3, 4, 5, 6, 7, 8, 9, 10) +1 +ArrayBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) +true +false +true +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, V -> V, G -> G, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, V -> V, G -> G, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(A -> A, B -> B, C -> C, D -> D, E -> E, F -> F, G -> G, H -> H, I -> I, J -> J, K -> K, L -> L, M -> M, N -> N, O -> O, P -> P, Q -> Q, R -> R, S -> S, T -> T, U -> U, V -> V, W -> W, X -> X, Y -> Y, Z -> Z) +Map(A -> A, B -> B, C -> C, D -> D, E -> E, F -> F, G -> G, H -> H, I -> I, J -> J, K -> K, L -> L, M -> M, N -> N, O -> O, P -> P, Q -> Q, R -> R, S -> S, T -> T, U -> U, V -> V, W -> W, X -> X, Y -> Y, Z -> Z) +Map(O -> O, W -> W, H -> H, P -> P, V -> V, G -> G, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, V -> V, G -> G, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) +Map(O -> O, W -> W, H -> H, P -> P, G -> G, V -> V, I -> I, A -> A, F -> F, U -> U, N -> N, X -> X, Z -> Z, S -> S, D -> D, K -> K, R -> R, C -> C, B -> B, L -> L, Q -> Q, M -> M, J -> J, Y -> Y, T -> T, E -> E) diff --git a/test/files/run/colltest1.scala b/test/files/run/colltest1.scala new file mode 100755 index 0000000000..f28221e205 --- /dev/null +++ b/test/files/run/colltest1.scala @@ -0,0 +1,231 @@ +import collection._ + +object Test extends Application { + + def orderedTraversableTest(empty: Traversable[Int]) + { + println("new test starting with "+empty) + assert(empty.isEmpty) + val ten = empty ++ List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) + println(ten.size+": "+ten) + println(ten.tail.size+": "+ten.tail) + assert(ten == empty ++ (1 to 10)) + assert(ten.size == 10) + assert(ten forall (_ <= 10)) + assert(ten exists (_ == 5)) + assert((ten count (_ % 2 == 0)) == 5) + assert((ten find (_ % 2 == 0)) == Some(2)) + assert((0 /: ten)(_ + _) == 55) + assert((ten :\ 0)(_ + _) == 55) + println(ten.head) + val x = ten reduceLeft (_ + _) + assert(x == 55, x) + assert((ten reduceRight (_ + _)) == 55) + val firstFive = empty ++ (1 to 5) + val secondFive = empty ++ (6 to 10) + assert(firstFive ++ secondFive == ten, firstFive ++ secondFive) + val odds = ten filter (_ % 2 != 0) + val evens = ten remove (_ % 2 != 0) + assert(odds.size == evens.size) + val (o, e) = ten.partition(_ % 2 == 0) + assert(o.size == e.size) + val gs = ten groupBy (x => x / 4) + val vs1 = (for (k <- gs.keys; v <- gs(k).toIterable.elements) yield v).toList + val vs2 = Traversable.traversableTraversableWrapper[List[Traversable[Int]], Int](gs.values.toList).flatten +// val vs2 = gs.values.toList flatMap (xs => xs) + assert(ten.head == 1) + assert(ten.tail.head == 2) + assert(ten.tail.size == 9) + assert(ten.tail.foldLeft(10)(_ + _) == 64) + assert(ten.last == 10) + assert(List(ten.head) ++ ten.tail == ten) + assert(ten.init ++ List(ten.last) == ten, ten.init) + assert(vs1 == vs2, vs1+"!="+vs2) + assert(vs1 == ten) + assert((ten take 5) == firstFive) + assert((ten drop 5) == secondFive) + assert(ten slice (3, 3) isEmpty) + assert((ten slice (3, 6)) == List(4, 5, 6), ten slice (3, 6)) + assert((ten takeWhile (_ <= 5)) == firstFive) + assert((ten dropWhile (_ <= 5)) == secondFive) + assert((ten span (_ <= 5)) == (firstFive, secondFive)) + assert((ten splitAt 5) == (firstFive, secondFive), ten splitAt 5) + val buf = new mutable.ArrayBuffer[Int] + firstFive copyToBuffer buf + secondFive copyToBuffer buf + assert(buf.result == ten, buf.result) + assert(ten.toArray.size == 10) + assert(ten.toArray == ten) + assert(ten.toIterable == ten) + assert(ten.toList == ten) + assert(ten.toSequence == ten) + assert(ten.toStream == ten) + assert(ten.toString endsWith "(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)") + assert(ten.mkString("[", "; ", "]") endsWith "[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]") + } + + def orderedIterableTest(empty: Iterable[Int]) { + orderedTraversableTest(empty) + val six = empty ++ List(1, 2, 3, 4, 5, 6) + assert(six.elements.toStream == six) + assert(six.takeRight(4) == List(3, 4, 5, 6), six.takeRight(4)) + assert(six.dropRight(3) == List(1, 2, 3)) + assert(six sameElements (1 to 6)) + } + + def sequenceTest(empty: Sequence[Int]) { + orderedIterableTest(empty) + val ten = empty ++ (1 to 10) + println(ten) + val tenPlus = ten map (_ + 1) + assert((ten zip tenPlus) forall { case (x, y) => x + 1 == y }) + val dble = ten flatMap (x => List(x, x)) + assert(dble.removeDuplicates == ten) + assert(ten.length == 10) + assert(ten(0) == 1 && ten(9) == 10) + assert((ten lengthCompare 10) == 0 && (ten lengthCompare 1) > 0 && (ten lengthCompare 11) < 0) + assert((ten isDefinedAt 0) && (ten isDefinedAt 9)) + assert(!(ten isDefinedAt -1)); + assert(!(ten isDefinedAt 10)) + val tenten = ten zip ten + assert((tenten map (_._1)) == ten) + assert((tenten map (_._2)) == ten) + assert(ten.zipWithIndex forall { case (x, y) => x == y + 1 }) + assert(ten.segmentLength(_ <= 8, 4) == 4, ten.segmentLength(_ <= 8, 4)) + assert(ten.prefixLength(_ <= 8) == 8) + assert(ten.indexWhere(_ >= 8, 4) == 7, ten.indexWhere(_ >= 8, 4)) + assert(ten.indexWhere(_ >= 8) == 7) + assert(ten.indexOf(5) == 4) + assert(ten.indexOf(5, 4) == 4) + assert(ten.indexOf(5, 5) == -1) + assert(ten.lastIndexOf(5) == 4, ten.lastIndexOf(5)) + assert(ten.lastIndexOf(5, 4) == 4) + assert(ten.lastIndexOf(5, 3) == -1) + assert(ten.lastIndexWhere(_ <= 8) == 7) + assert(ten.lastIndexWhere(_ <= 8, 6) == 6) + assert(ten.lastIndexWhere(_ <= 8, 8) == 7) + assert(ten.reverse startsWith List(10, 9, 8), ten.reverse.take(10).toList) + assert(ten.reverse.length == 10) + assert(ten.reverse.reverse == ten) + assert(ten.reversedElements.toList.reverse == ten, ten.reversedElements.toList) + assert(ten.startsWith(List(1))) + assert(ten.startsWith(List(3, 4), 2)) + assert(ten.endsWith(List(9, 10))) + assert(ten.endsWith(List())) + assert(ten.indexOfSeq(List(3, 4, 5)) == 2, ten.indexOfSeq(List(3, 4, 5))) + assert(ten contains 1) + assert(ten contains 10) + assert(!(ten contains 0)) + assert((empty ++ (1 to 7) union empty ++ (3 to 10)) == List(1, 2, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 8, 9, 10)) + assert((ten diff ten).isEmpty) + assert((ten diff List()) == ten) + assert((ten diff (ten filter (_ % 2 == 0))) == (ten remove (_ % 2 == 0))) + assert((ten intersect ten) == ten) + assert((ten intersect List(5)) == List(5)) + assert((ten ++ ten).removeDuplicates == ten) + assert(ten.patch(3, List(4, 5, 6, 7), 4) == ten) + assert(ten.patch(0, List(1, 2, 3), 9) == List(1, 2, 3, 10)) + assert(empty.padTo(10, 7) == Array.fill(10)(7)) + assert((ten zip ten.indices) == ten.zipWithIndex) + } + + def setTest(empty: => Set[String]) { + var s = empty + "A" + "B" + "C" + s += ("D", "E", "F") + s ++= List("G", "H", "I") + s ++= ('J' to 'Z') map (_.toString) + assert(s forall (s contains)) + assert(s contains "X") + assert(!(s contains "0")) + s = s + "0" + assert(s contains "0") + s = s - "X" + assert(!(s contains "X")) + assert(empty.isEmpty) + assert(!s.isEmpty) + assert((s intersect s) == s) + assert((empty intersect s) == empty) + assert(!s.isEmpty) + val s1 = s intersect empty + assert(s1 == empty, s1) + def abc = empty + ("a", "b", "c") + def bc = empty + ("b", "c") + assert(bc subsetOf abc) + } + + def rangeTest(r: Range) { + val ten = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) + assert(r == ten) + assert(r.toList == ten) + assert((r filter (_ % 2 == 0)) == (ten filter (_ % 2 == 0))) + println((r map (_ + 1)) == (ten map (_ + 1))) + println((r map (_ * 2)) == (ten map (_ + 1))) + println((r flatMap (i => 0 until i)) == (ten flatMap (i => 0 until i))) + } + + def mapTest(empty: => Map[String, String]) = { + var m = empty + ("A" -> "A") + ("B" -> "B") + ("C" -> "C") + m += (("D" -> "D"), ("E" -> "E"), ("F" -> "F")) + m ++= List(("G" -> "G"), ("H" -> "H"), ("I" -> "I")) + m ++= ('J' to 'Z') map (x => (x.toString -> x.toString)) + println(m) + assert(!m.isEmpty) + assert(m.keys forall (k => (m get k) == Some(k))) + assert(m.keys forall (k => (m apply k) == k)) + assert(m.keys forall (m contains)) + assert(m.getOrElse("7", "@") == "@") + assert(m.keys.length == 26) + assert(m.size == 26) + assert(m.keySet == Set() ++ m.keys) + assert(m.keys.toList == m.values.toList) + val m1 = empty ++ m + val mm = m -- m.keySet.toList + assert(mm.isEmpty, mm) + def m3 = empty ++ m1 + assert(m1 == m3) + println(m3) + val m4 = m3.remove { case (k, v) => k != "A" } + assert(m4.size == 1, m4) + } + + def mutableMapTest(empty: => mutable.Map[String, String]) = { + mapTest(empty) + val m1 = empty ++ (('A' to 'Z') map (_.toString) map (x => (x, x))) + val m2 = m1 retain ((k, v) => k == "N") + assert(m2.size == 1, m2) + } + + sequenceTest(Nil) + sequenceTest(List()) + sequenceTest(Stream.empty) + sequenceTest(Array()) + sequenceTest(mutable.ArrayBuffer()) + sequenceTest(mutable.ListBuffer()) + orderedTraversableTest(Traversable()) + orderedTraversableTest(mutable.Traversable()) + orderedTraversableTest(immutable.Traversable()) + orderedIterableTest(Iterable()) + orderedIterableTest(mutable.Iterable()) + orderedIterableTest(immutable.Iterable()) + sequenceTest(Sequence()) + sequenceTest(mutable.Sequence()) + sequenceTest(immutable.Sequence()) + sequenceTest(LinearSequence()) +// sequenceTest(mutable.LinearSequence()) + sequenceTest(immutable.LinearSequence()) + sequenceTest(mutable.Vector()) + rangeTest(1 to 10) + + setTest(Set()) + setTest(mutable.Set()) + setTest(immutable.Set()) + setTest(mutable.HashSet()) + setTest(immutable.HashSet()) + + mapTest(Map()) + mutableMapTest(mutable.Map()) + mapTest(immutable.Map()) + mapTest(immutable.TreeMap()) + mutableMapTest(mutable.HashMap()) + mapTest(immutable.HashMap()) +} |