diff options
author | Martin Odersky <odersky@gmail.com> | 2009-09-10 15:39:11 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2009-09-10 15:39:11 +0000 |
commit | e72f0c7f2ff54f2afff3b612e7e9f9572ce3c82f (patch) | |
tree | d6f07e52e994609c8fc81624a987cc92a66b49b4 | |
parent | 5f5b82e792094d3d51985167f96742f4ea210a31 (diff) | |
download | scala-e72f0c7f2ff54f2afff3b612e7e9f9572ce3c82f.tar.gz scala-e72f0c7f2ff54f2afff3b612e7e9f9572ce3c82f.tar.bz2 scala-e72f0c7f2ff54f2afff3b612e7e9f9572ce3c82f.zip |
Massive redesign so that: scala> "hi" == "hi".r...
Massive redesign so that: scala> "hi" == "hi".reverse.reverse gives: res0: Boolean = true
Preparing to do similar things to arrays.
78 files changed, 3228 insertions, 2386 deletions
@@ -258,6 +258,7 @@ LOCAL REFERENCE BUILD (LOCKER) srcdir="${src.dir}/library" jvmargs="${scalacfork.jvmargs}"> <include name="scala/Predef.scala"/> + <include name="scala/LowPriorityImplicits.scala"/> <compilationpath> <pathelement location="${build-locker.dir}/classes/library"/> </compilationpath> @@ -271,6 +272,7 @@ LOCAL REFERENCE BUILD (LOCKER) jvmargs="${scalacfork.jvmargs}"> <include name="**/*.scala"/> <exclude name="scala/Predef.scala"/> + <exclude name="scala/LowPriorityImplicits.scala"/> <compilationpath> <pathelement location="${build-locker.dir}/classes/library"/> </compilationpath> @@ -439,6 +441,7 @@ QUICK BUILD (QUICK) srcdir="${src.dir}/library" jvmargs="${scalacfork.jvmargs}"> <include name="scala/Predef.scala"/> + <include name="scala/LowPriorityImplicits.scala"/> <compilationpath> <pathelement location="${build-quick.dir}/classes/library"/> </compilationpath> @@ -452,6 +455,7 @@ QUICK BUILD (QUICK) jvmargs="${scalacfork.jvmargs}"> <include name="**/*.scala"/> <exclude name="scala/Predef.scala"/> + <exclude name="scala/LowPriorityImplicits.scala"/> <compilationpath> <pathelement location="${build-quick.dir}/classes/library"/> </compilationpath> @@ -896,6 +900,7 @@ BOOTSTRAPPING BUILD (STRAP) target="jvm-1.5" addparams="${scalac.args.all}"> <include name="scala/Predef.scala"/> + <include name="scala/LowPriorityImplicits.scala"/> </scalac> <scalac srcdir="${src.dir}/library" @@ -905,6 +910,7 @@ BOOTSTRAPPING BUILD (STRAP) addparams="${scalac.args.all}"> <include name="**/*.scala"/> <exclude name="scala/Predef.scala"/> + <exclude name="scala/LowPriorityImplicits.scala"/> </scalac> <scalac srcdir="${src.dir}/actors" diff --git a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala index 6d1914f88b..c4f0be7cf5 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala @@ -121,7 +121,7 @@ trait TreeDSL { /** Methods for sequences **/ def DROP(count: Int): Tree = if (count == 0) target - else (target DOT nme.drop)(LIT(count)) DOT nme.toSeq + else (target DOT nme.drop)(LIT(count)) DOT nme.toSequence /** Casting & type tests -- working our way toward understanding exactly * what differs between the different forms of IS and AS. diff --git a/src/compiler/scala/tools/nsc/ast/parser/SymbolicXMLBuilder.scala b/src/compiler/scala/tools/nsc/ast/parser/SymbolicXMLBuilder.scala index db70eb34df..2285af5d3d 100644 --- a/src/compiler/scala/tools/nsc/ast/parser/SymbolicXMLBuilder.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/SymbolicXMLBuilder.scala @@ -59,6 +59,7 @@ abstract class SymbolicXMLBuilder(p: Parsers#Parser, preserveWS: Boolean) private def LL[A](x: A*): List[List[A]] = List(List(x:_*)) private def const(x: Any) = x match { case s: runtime.RichString => Literal(Constant(s.toString)) // not our finest hour + case s: collection.immutable.StringLike[_] => Literal(Constant(s.toString)) // not our finest hour case _ => Literal(Constant(x)) } private def wild = Ident(nme.WILDCARD) diff --git a/src/compiler/scala/tools/nsc/symtab/StdNames.scala b/src/compiler/scala/tools/nsc/symtab/StdNames.scala index 894291d4dc..ca6b70c453 100644 --- a/src/compiler/scala/tools/nsc/symtab/StdNames.scala +++ b/src/compiler/scala/tools/nsc/symtab/StdNames.scala @@ -328,7 +328,7 @@ trait StdNames { val tail = newTermName("tail") val toArray = newTermName("toArray") val toList = newTermName("toList") - val toSeq = newTermName("toSeq") + val toSequence = newTermName("toSequence") val toString_ = newTermName("toString") val clone_ = newTermName("clone") val this_ = newTermName("this") diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index d1c06cd87a..5d1f30d9b6 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -373,67 +373,57 @@ abstract class UnCurry extends InfoTransform with TypingTransformers { } def transformArgs(pos: Position, args: List[Tree], formals: List[Type], isJava: Boolean) = { - if (formals.isEmpty) { - assert(args.isEmpty); List() - } else { - val args1 = - formals.last match { - case TypeRef(pre, sym, List(elempt)) if (sym == RepeatedParamClass) => - def mkArrayValue(ts: List[Tree]) = - atPos(pos)(ArrayValue(TypeTree(elempt), ts) setType formals.last); - - // when calling into java varargs, make sure it's an array - see bug #1360 - def forceToArray(arg: Tree) = { - val Typed(tree, _) = arg - if (!isJava || tree.tpe.typeSymbol == ArrayClass) tree - else { - val traversableTpe = tree.tpe.baseType(TraversableClass) - val toArray = tree.tpe member nme.toArray - if (traversableTpe != NoType && toArray != NoSymbol) { - val arguments = - if (toArray.tpe.paramTypes.isEmpty) List() // !!! old style toArray - else { // new style, with manifest - val manifestOpt = localTyper.findManifest(tree.tpe.typeArgs.head, false) - if (manifestOpt.tree.isEmpty) { - unit.error(tree.pos, "cannot find class manifest for element type of "+tree.tpe) - List(Literal(Constant(null))) - } else { - List(manifestOpt.tree) - } - } - atPhase(phase.next) { - localTyper.typed { - atPos(pos) { - Apply(gen.mkAttributedSelect(tree, toArray), arguments) - } - } - } - } else tree - } - } - if (args.isEmpty) - List(mkArrayValue(args)) - else { - val suffix: Tree = - if (treeInfo isWildcardStarArg args.last) forceToArray(args.last) - else mkArrayValue(args drop (formals.length - 1)) - - args.take(formals.length - 1) ::: List(suffix) + val args1 = formals.lastOption match { + case Some(TypeRef(pre, sym, List(elempt))) if (sym == RepeatedParamClass) => + def callMethod(tree: Tree, nme: Name): Tree = { + val sym = tree.tpe member nme + assert(sym != NoSymbol) + val arguments = + if (sym.tpe.paramTypes.isEmpty) List() // !!! no manifest required + else List(localTyper.getManifestTree(tree.pos, tree.tpe.typeArgs.head, false)) // call with manifest + atPhase(phase.next) { + localTyper.typedPos(pos) { + Apply(gen.mkAttributedSelect(tree, sym), arguments) } - case _ => args + } } - List.map2(formals, args1) { (formal, arg) => - if (formal.typeSymbol != ByNameParamClass) { - arg - } else if (isByNameRef(arg)) { - byNameArgs.addEntry(arg) - arg setType functionType(List(), arg.tpe) - } else { - val fun = localTyper.typed( - Function(List(), arg) setPos arg.pos).asInstanceOf[Function]; - new ChangeOwnerTraverser(currentOwner, fun.symbol).traverse(arg); - transformFunction(fun) + + def mkArrayValue(ts: List[Tree]) = { + val arr = ArrayValue(TypeTree(elempt), ts) setType formals.last + if (isJava || inPattern) arr + else callMethod(arr, nme.toSequence) // println("need to callMethod("+arr+", nme.toSequence)"); arr } + } + + // when calling into java varargs, make sure it's an array - see bug #1360 + def forceToArray(arg: Tree) = { + val Typed(tree, _) = arg + if (isJava && tree.tpe.typeSymbol != ArrayClass && + (tree.tpe.typeSymbol isSubClass TraversableClass)) callMethod(tree, nme.toArray) + else tree } + + if (args.isEmpty) + List(mkArrayValue(args)) + else { + val suffix: Tree = + if (treeInfo isWildcardStarArg args.last) forceToArray(args.last) + else mkArrayValue(args drop (formals.length - 1)) + args.take(formals.length - 1) ::: List(suffix) + } + case _ => + args + } + List.map2(formals, args1) { (formal, arg) => + if (formal.typeSymbol != ByNameParamClass) { + arg + } else if (isByNameRef(arg)) { + byNameArgs.addEntry(arg) + arg setType functionType(List(), arg.tpe) + } else { + val fun = localTyper.typed( + Function(List(), arg) setPos arg.pos).asInstanceOf[Function]; + new ChangeOwnerTraverser(currentOwner, fun.symbol).traverse(arg); + transformFunction(fun) } } } diff --git a/src/library/scala/Console.scala b/src/library/scala/Console.scala index 933986a2ba..63eea8237c 100644 --- a/src/library/scala/Console.scala +++ b/src/library/scala/Console.scala @@ -220,7 +220,7 @@ object Console { * target="contentFrame">Console.printf</a>. */ @deprecated("For console output, use <code>Console.printf</code>. For <code>String</code>\n"+ - "formatting, <code>RichString</code>'s <code>format</code> method.") + "formatting, <code>StringOps</code>'s <code>format</code> method.") def format(text: String, args: Any*) { if (text eq null) out.printf("null") else out.print(text format (args : _*)) diff --git a/src/library/scala/Equals.scala b/src/library/scala/Equals.scala new file mode 100644 index 0000000000..aa02cb0982 --- /dev/null +++ b/src/library/scala/Equals.scala @@ -0,0 +1,26 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Equals.scala 18478 2009-08-13 21:30:20Z stepancheg $ + +package scala + +/** An interface containing operations for equality + * The only method not already present in AnyRef is canEqual + */ +trait Equals { + /** A method that should be called from every well-designed equals method + * that is open to be overridden in a subclass. See Programming in Scala, Chapter 28 + * for discussion and design. + */ + def canEqual(that: Any): Boolean + + /** The equality method defined in AnyRef + */ + def equals(that: Any): Boolean +} diff --git a/src/library/scala/LowPriorityImplicits.scala b/src/library/scala/LowPriorityImplicits.scala new file mode 100644 index 0000000000..934c0f27e1 --- /dev/null +++ b/src/library/scala/LowPriorityImplicits.scala @@ -0,0 +1,50 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Predef.scala 18558 2009-08-24 14:03:30Z moors $ + + +package scala + +import collection.mutable._ +import collection.immutable.WrappedString + +/** The `LowPriorityImplicits` class provides implicit values that are + * valid in all Scala compilation units without explicit qualification, but that + * are partially overridden by higher-priority conmversions in Predef + */ +class LowPriorityImplicits { + + implicit def genericArrayWrapper[T](xs: Array[T]): WrappedArray[T] = (xs: AnyRef) match { // !!! drop the AnyRef and get unreachable code errors! + case x: Array[AnyRef] => arrayWrapper[AnyRef](x).asInstanceOf[WrappedArray[T]] + case x: Array[Int] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Double] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Long] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Float] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Char] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Byte] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Short] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Boolean] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + case x: Array[Unit] => arrayWrapper(x).asInstanceOf[WrappedArray[T]] + } + + implicit def arrayWrapper[T <: AnyRef](xs: Array[T]): WrappedRefArray[T] = new WrappedRefArray[T](xs.asInstanceOf[Array[AnyRef]]) + implicit def arrayWrapper(xs: Array[Int]): WrappedIntArray = new WrappedIntArray(xs) + implicit def arrayWrapper(xs: Array[Double]): WrappedDoubleArray = new WrappedDoubleArray(xs) + implicit def arrayWrapper(xs: Array[Long]): WrappedLongArray = new WrappedLongArray(xs) + implicit def arrayWrapper(xs: Array[Float]): WrappedFloatArray = new WrappedFloatArray(xs) + implicit def arrayWrapper(xs: Array[Char]): WrappedCharArray = new WrappedCharArray(xs) + implicit def arrayWrapper(xs: Array[Byte]): WrappedByteArray = new WrappedByteArray(xs) + implicit def arrayWrapper(xs: Array[Short]): WrappedShortArray = new WrappedShortArray(xs) + implicit def arrayWrapper(xs: Array[Boolean]): WrappedBooleanArray = new WrappedBooleanArray(xs) + implicit def arrayWrapper(xs: Array[Unit]): WrappedUnitArray = new WrappedUnitArray(xs) + + implicit def wrapString(s: String): WrappedString = new WrappedString(s) + implicit def unwrapString(ws: WrappedString): String = ws.self + +} diff --git a/src/library/scala/Predef.scala b/src/library/scala/Predef.scala index 108729fae0..f359a3ccd1 100644 --- a/src/library/scala/Predef.scala +++ b/src/library/scala/Predef.scala @@ -11,11 +11,15 @@ package scala +import collection.immutable.StringOps +import collection.mutable.StringBuilder +import collection.generic.BuilderFactory + /** The <code>Predef</code> object provides definitions that are * accessible in all Scala compilation units without explicit * qualification. */ -object Predef { +object Predef extends LowPriorityImplicits { // classOf dummy ------------------------------------------------------ @@ -63,7 +67,7 @@ object Predef { private val P = scala.`package` // to force scala package object to be seen. private val L = scala.collection.immutable.List // to force Nil, :: to be seen. - private val S = scala.collection.mutable.StringBuilder // to force StringBuilder to be seen. + private val S = StringBuilder // to force StringBuilder to be seen. val $scope = scala.xml.TopScope @@ -177,7 +181,7 @@ object Predef { def println() = Console.println() def println(x: Any) = Console.println(x) def printf(text: String, xs: Any*) = Console.printf(text, xs: _*) - def format(text: String, xs: Any*) = stringWrapper(text).format(xs: _*) + def format(text: String, xs: Any*) = augmentString(text).format(xs: _*) def readLine(): String = Console.readLine() def readLine(text: String, args: Any*) = Console.readLine(text, args) @@ -206,7 +210,10 @@ object Predef { implicit def booleanWrapper(x: Boolean) = new runtime.RichBoolean(x) - implicit def stringWrapper(x: String) = new runtime.RichString(x) + implicit def augmentString(x: String): StringOps = new StringOps(x) + implicit def unaugmentString(x: StringOps): String = x.repr + implicit def stringBuilderFactory: BuilderFactory[Char, String, String] = + new BuilderFactory[Char, String, String] { def apply(from: String) = new StringBuilder } implicit def any2stringadd(x: Any) = new runtime.StringAdd(x) @@ -252,8 +259,7 @@ object Predef { /** any array projection can be automatically converted into an array */ //implicit def forceArrayProjection[A](x: Array.Projection[A]): Array[A] = x.force !!! re-enable? - /** any random access character seq (including rich string can be converted into a string */ - implicit def richString2String(x: runtime.RichString): String = if (x eq null) null else x.toString + //implicit def lazyStreamToConsable[A](xs: => Stream[A]) = new runtime.StreamCons(xs) implicit def seqToCharSequence(xs: collection.Vector[Char]): CharSequence = new CharSequence { diff --git a/src/library/scala/Product.scala b/src/library/scala/Product.scala index a7c7a216b4..a67fb94167 100644 --- a/src/library/scala/Product.scala +++ b/src/library/scala/Product.scala @@ -18,7 +18,7 @@ package scala * @version 1.0 * @since 2.3 */ -trait Product extends AnyRef { +trait Product extends Equals { /** for a product <code>A(x_1,...,x_k)</code>, returns <code>x_(n+1)</code> * for <code>0 <= n < k</code> @@ -56,5 +56,5 @@ trait Product extends AnyRef { * in the face of subtyping. For more, see * http://www.artima.com/lejava/articles/equality.html */ - def canEqual(other: Any) = true + override def canEqual(other: Any): Boolean = true } diff --git a/src/library/scala/Proxy.scala b/src/library/scala/Proxy.scala index 31aec941e0..4c890c828d 100644 --- a/src/library/scala/Proxy.scala +++ b/src/library/scala/Proxy.scala @@ -25,9 +25,6 @@ import Predef._ trait Proxy { def self: Any override def hashCode: Int = self.hashCode - override def equals(that: Any): Boolean = that match { - case that: Proxy => self equals that.self - case that => false - } + override def equals(that: Any): Boolean = that equals self override def toString: String = self.toString } diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala new file mode 100755 index 0000000000..47a2e77240 --- /dev/null +++ b/src/library/scala/collection/IterableLike.scala @@ -0,0 +1,402 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IterableLike.scala 18602 2009-08-29 00:54:16Z extempore $ + +package scala.collection +import generic._ +import annotation.unchecked.uncheckedVariance + +// import immutable.Stream // !!! + +/** <p> + * A template trait for iterable collections. + * </p> + * <p> + * Collection classes mixing in this trait provide a method + * <code>iterator</code> which returns an iterator over all the + * elements contained in the collection. They also provide a method + * <code>newBuilder</code> which creates a builder for collections of the + * same kind. + * </p> + * <p> + * This trait implements <code>Iterable</code>'s <code>foreach</code> + * method by stepping through all elements. Subclasses of <code>Iterable</code> + * should re-implement <code>foreach</code> with something more efficient, + * if possible. + * </p> + * <p> + * This trait adds methods <code>iterator</code>, <code>sameElements</code>, + * <code>takeRight</code>, <code>dropRight</code> to the methods inherited + * from trait <a href="../Iterable.html" target="ContentFrame"> + * <code>Iterable</code></a>. + * </p> + * + * @note This trait replaces every method that uses breaks in the original by an iterator version. + * + * @author Martin Odersky + * @version 2.8 + */ +trait IterableLike[+A, +Repr] extends Equals with TraversableLike[A, Repr] { +self => + + override protected[this] def thisCollection: Iterable[A] = this.asInstanceOf[Iterable[A]] + override protected[this] def toCollection(repr: Repr): Iterable[A] = repr.asInstanceOf[Iterable[A]] + + /** Creates a new iterator over all elements contained in this + * iterable object. + * + * @return the new iterator + */ + def iterator: Iterator[A] + + @deprecated("use `iterator' instead") + def elements = iterator + + /** Apply a function <code>f</code> to all elements of this + * iterable object. + * + * @param f A function that is applied for its side-effect to every element. + * The result (of arbitrary type U) of function `f` is discarded. + * + * @note This method underlies the implementation of most other bulk operations. + * Implementing `foreach` with `iterator` is often suboptimal. + * So `foreach` should be overridden in concrete collection classes if a more + * efficient implementation is available. + */ + def foreach[U](f: A => U): Unit = iterator.foreach(f) + + + /** Return true iff the given predicate `p` yields true for all elements + * of this iterable. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + override def forall(p: A => Boolean): Boolean = iterator.forall(p) + + /** Return true iff there is an element in this iterable for which the + * given predicate `p` yields true. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + override def exists(p: A => Boolean): Boolean = iterator.exists(p) + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @note may not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered. + * @param p the predicate + * @return an option containing the first element in the iterable object + * satisfying <code>p</code>, or <code>None</code> if none exists. + */ + override def find(p: A => Boolean): Option[A] = iterator.find(p) + + /** Does this iterable contain no elements? + */ + override def isEmpty: Boolean = !this.iterator.hasNext + + /** Combines the elements of this iterable together using the binary + * function <code>f</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. + * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> + * if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + */ + override def foldRight[B](z: B)(op: (A, B) => B): B = + this.iterator.foldRight(z)(op) + + /** Combines the elements of this iterable object together using the binary + * operator <code>op</code>, from right to left + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this iterable is ordered, or + * the operator is associative and commutative. + * @param op The operator to apply + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> + * if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + override def reduceRight[B >: A](op: (A, B) => B): B = + this.iterator.reduceRight(op) + + /** The iterable itself */ + override def toIterable: Iterable[A] = thisCollection + + /** The first element of this iterable. + * + * @note Might return different results for different runs, unless this iterable is ordered + * @throws Predef.NoSuchElementException if the iterable is empty. + */ + override def head: A = + if (isEmpty) + throw new NoSuchElementException + else + this.iterator.next + + /** Return an iterable consisting only of the first <code>n</code> + * elements of this iterable, or else the whole iterable, if it has less + * than <code>n</code> elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + override def take(n: Int): Repr = { + val b = newBuilder + var i = 0 + val it = iterator + while (i < n && it.hasNext) { + b += it.next + i += 1 + } + b.result + } + + /** A sub-iterable starting at index `from` + * and extending up to (but not including) index `until`. + * + * @note c.slice(from, to) is equivalent to (but possibly more efficient than) + * c.drop(from).take(to - from) + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @note Might return different results for different runs, unless this iterable is ordered + */ + override def slice(from: Int, until: Int): Repr = { + val b = newBuilder + var i = from + val it = iterator drop from + while (i < until && it.hasNext) { + b += it.next + i += 1 + } + b.result + } + + /** Returns the longest prefix of this iterable whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this iterable is ordered + */ + override def takeWhile(p: A => Boolean): Repr = { + val b = newBuilder + val it = iterator + while (it.hasNext) { + val x = it.next + if (!p(x)) return b.result + b += x + } + b.result + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeRight(n: Int): Repr = { + val b = newBuilder + val lead = this.iterator drop n + var go = false + for (x <- this) { + if (lead.hasNext) lead.next + else go = true + if (go) b += x + } + b.result + } + + /** Returns the iterable wihtout its rightmost <code>n</code> elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropRight(n: Int): Repr = { + val b = newBuilder + val lead = iterator drop n + val it = iterator + while (lead.hasNext) { + b += it.next + lead.next + } + b.result + } + + /** Fills the given array <code>xs</code> with at most `len` elements of + * this iterable starting at position `start`. + * Copying will stop once either the end of the current iterable is reached or + * `len` elements have been copied or the end of the array is reached. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + */ + override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { + var i = start + val end = (start + len) min xs.length + val it = iterator + while (i < end && it.hasNext) { + xs(i) = it.next + i += 1 + } + } + + /** Returns an iterable formed from this iterable and another iterable + * by combining corresponding elements in pairs. + * If one of the two iterables is longer than the other, its remaining elements are ignored. + * @param that The iterable providing the second half of each result pair + */ + def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, Repr]): That = { + val b = bf(repr) + val these = this.iterator + val those = that.iterator + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + b.result + } + + /** Returns an iterable formed from this iterable and the specified iterable + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterable <code>that</code> may have a different length + * as the self iterable. + * @param thisElem element <code>thisElem</code> is used to fill up the + * resulting iterable if the self iterable is shorter than + * <code>that</code> + * @param thatElem element <code>thatElem</code> is used to fill up the + * resulting iterable if <code>that</code> is shorter than + * the self iterable + * @return <code>Sequence((a<sub>0</sub>,b<sub>0</sub>), ..., + * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), + * ..., {elem,b<sub>m</sub>})</code> + * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip + * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is + * invoked where <code>m > n</code>. + * + */ + def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, Repr]): That = { + val b = bf(repr) + val these = this.iterator + val those = that.iterator + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + while (these.hasNext) + b += ((these.next, thatElem)) + while (those.hasNext) + b += ((thisElem, those.next)) + b.result + } + + /** Zips this iterable with its indices (startiong from 0). + */ + def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, Repr]): That = { + val b = bf(repr) + var i = 0 + for (x <- this) { + b += ((x, i)) + i +=1 + } + b.result + } + + /** Sort the iterable according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>, + * which should be true iff <code>e1</code> is smaller than + * <code>e2</code>. + * The sort is stable. That is elements that are equal wrt `lt` appear in the + * same order in the sorted sequence as in the original. + * + * @param lt the comparison function + * @return an iterable sorted according to the comparison function + * <code><(e1: a, e2: a) => Boolean</code>. + * @ex <pre> + * List("Steve", "Tom", "John", "Bob") + * .sortWith((e1, e2) => (e1 compareTo e2) < 0) = + * List("Bob", "John", "Steve", "Tom")</pre> + */ + def sortWith(lt: (A, A) => Boolean)(implicit m: ClassManifest[A @uncheckedVariance]): Repr = { + // !!! can we supply a default argument to m: ClassManifest ? + val arr = toArray + java.util.Arrays.sort(arr, Ordering fromLessThan lt) + + val b = newBuilder + for (x <- arr) b += x + b.result + } + + /** Checks if the other iterable object contains the same elements as this one. + * + * @note will not terminate for infinite-sized iterables. + * @param that the other iterable + * @return true, iff both iterables contain the same elements in the same order. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def sameElements[B >: A](that: Iterable[B]): Boolean = { + val these = this.iterator + val those = that.iterator + while (these.hasNext && those.hasNext) + if (these.next != those.next) + return false + + !these.hasNext && !those.hasNext + } + + /** Returns a stream with all elements in this iterable object. + */ + override def toStream: Stream[A] = iterator.toStream + + /** Method called from equality methods, so that user-defined subclasses can + * refuse to be equal to other collections of the same kind. + */ + override def canEqual(that: Any) = true + + /** Creates a view of this iterable @see IterableView + */ + override def view = new IterableView[A, Repr] { + protected lazy val underlying = self.repr + override def iterator = self.iterator + } + + /** A sub-iterable view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current iterable, whereas `slice` produces a new iterable. + * + * @note Might return different results for different runs, unless this iterable is ordered + * @note view(from, to) is equivalent to view.slice(from, to) + */ + override def view(from: Int, until: Int) = view.slice(from, until) + + @deprecated("use `head' instead") def first: A = head + + /** <code>None</code> if iterable is empty. */ + @deprecated("use `headOption' instead") def firstOption: Option[A] = headOption + + @deprecated("use `toSequence' instead") def toSeq: Sequence[A] = toSequence + + /** + * returns a projection that can be used to call non-strict <code>filter</code>, + * <code>map</code>, and <code>flatMap</code> methods that build projections + * of the collection. + */ + @deprecated("use `view' instead") + def projection = view +} diff --git a/src/library/scala/collection/LinearSequenceLike.scala b/src/library/scala/collection/LinearSequenceLike.scala new file mode 100644 index 0000000000..80aed33584 --- /dev/null +++ b/src/library/scala/collection/LinearSequenceLike.scala @@ -0,0 +1,404 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: LinearSequenceTemplate.scala 18646 2009-09-04 16:56:11Z odersky $ + + +package scala.collection +import generic._ + +import mutable.ListBuffer +// import immutable.{List, Nil, ::} +import generic._ +import scala.util.control.Breaks._ + +/** Class <code>Linear[A]</code> represents linear sequences of elements. + * For such sequences `isEmpty`, `head` and `tail` are guaranteed to be + * efficient constant time (or near so) operations. + * It does not add any methods to <code>Sequence</code> but overrides + * several methods with optimized implementations. + * + * @author Martin Odersky + * @author Matthias Zenger + * @version 1.0, 16/07/2003 + */ +trait LinearSequenceLike[+A, +Repr <: LinearSequenceLike[A, Repr]] extends SequenceLike[A, Repr] { self: Repr => + + override protected[this] def thisCollection: LinearSequence[A] = this.asInstanceOf[LinearSequence[A]] + override protected[this] def toCollection(repr: Repr): LinearSequence[A] = repr.asInstanceOf[LinearSequence[A]] + + /** Abstract method to be implemented in a subclass */ + def isEmpty: Boolean + + /** Abstract method to be implemented in a subclass */ + def head: A + + /** Abstract method to be implemented in a subclass */ + def tail: Repr + + /** Returns the number of elements in the linear sequence. + */ + def length: Int = { + var these = self + var len = 0 + while (!these.isEmpty) { + len += 1 + these = these.tail + } + len + } + + /** Returns the <code>n</code>-th element of this linear sequence. The first element + * (head of the linear sequence) is at position 0. + * + * @param n index of the element to return + * @return the element at position <code>n</code> in this linear sequence. + * @throws Predef.NoSuchElementException if the linear sequence is too short. + */ + def apply(n: Int): A = drop(n).head + + /** Returns the elements in the sequence as an iterator + */ + override def iterator: Iterator[A] = new Iterator[A] { + var these = self + def hasNext: Boolean = !these.isEmpty + def next: A = + if (hasNext) { + val result = these.head; these = these.tail; result + } else Iterator.empty.next + override def toList: List[A] = these.toList + } + + /** Apply the given function <code>f</code> to each element of this linear sequence + * (while respecting the order of the elements). + * + * @param f the treatment to apply to each element. + */ + override def foreach[B](f: A => B) { + var these = this + while (!these.isEmpty) { + f(these.head) + these = these.tail + } + } + + /** Tests if the predicate <code>p</code> is satisfied by all elements + * in this list. + * + * @param p the test predicate. + * @return <code>true</code> iff all elements of this list satisfy the + * predicate <code>p</code>. + */ + override def forall(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (!p(these.head)) return false + these = these.tail + } + true + } + + /** Tests the existence in this list of an element that satisfies the + * predicate <code>p</code>. + * + * @param p the test predicate. + * @return <code>true</code> iff there exists an element in this list that + * satisfies the predicate <code>p</code>. + */ + override def exists(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (p(these.head)) return true + these = these.tail + } + false + } + + /** Count the number of elements in the iterable which satisfy a predicate. + * + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate <code>p</code>. + */ + override def count(p: A => Boolean): Int = { + var these = this + var cnt = 0 + while (!these.isEmpty) { + if (p(these.head)) cnt += 1 + these = these.tail + } + cnt + } + + /** Find and return the first element of the list satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the list satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + override def find(p: A => Boolean): Option[A] = { + var these = this + while (!these.isEmpty) { + if (p(these.head)) return Some(these.head) + these = these.tail + } + None + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from left to right, and starting with + * the value <code>z</code>. + * + * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), + * a<sub>n</sub>)</code> if the list is + * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. + */ + override def foldLeft[B](z: B)(f: (B, A) => B): B = { + var acc = z + var these = this + while (!these.isEmpty) { + acc = f(acc, these.head) + these = these.tail + } + acc + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> + * if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + */ + override def foldRight[B](z: B)(f: (A, B) => B): B = + if (this.isEmpty) z + else f(head, tail.foldRight(z)(f)) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from left to right + * @param op The operator to apply + * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> + if the list has elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + * @throws Predef.UnsupportedOperationException if the list is empty. + */ + override def reduceLeft[B >: A](f: (B, A) => B): B = + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + else tail.foldLeft[B](head)(f) + + /** Combines the elements of this iterable object together using the binary + * operator <code>op</code>, from right to left + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> + * if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + override def reduceRight[B >: A](op: (A, B) => B): B = + if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight") + else if (tail.isEmpty) head + else op(head, tail.reduceRight(op)) + + /** The last element of this linear sequence. + * + * @throws Predef.NoSuchElementException if the linear sequence is empty. + */ + override def last: A = { + if (isEmpty) throw new NoSuchElementException + var these = this + var nx = these.tail + while (!nx.isEmpty) { + these = nx + nx = nx.tail + } + these.head + } + + override def take(n: Int): Repr = { + val b = newBuilder + var i = 0 + var these = repr + while (!these.isEmpty && i < n) { + i += 1 + b += these.head + these = these.tail + } + b.result + } + + override def drop(n: Int): Repr = { + var these: Repr = repr + var count = n + while (!these.isEmpty && count > 0) { + these = these.tail + count -= 1 + } + these + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * @param n the number of elements to take + */ + override def dropRight(n: Int): Repr = { + val b = newBuilder + var these = this + var lead = this drop n + while (!lead.isEmpty) { + b += these.head + these = these.tail + lead = lead.tail + } + b.result + } + + /** A sub-traversable starting at index `from` + * and extending up to (but not including) index `until`. + * + * @note c.slice(from, to) is equivalent to (but possibly more efficient than) + * c.drop(from).take(to - from) + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @note Might return different results for different runs, unless this traversable is ordered + */ + override def slice(from: Int, until: Int): Repr = { + val b = newBuilder + var i = from + var these = this drop from + while (i < until && !these.isEmpty) { + b += these.head + these = these.tail + i += 1 + } + b.result + } + + /** Returns the longest prefix of this traversable whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this traversable is ordered + */ + override def takeWhile(p: A => Boolean): Repr = { + val b = newBuilder + var these = this + while (!these.isEmpty && p(these.head)) { + b += these.head + these = these.tail + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the linear sequence whose + * elements all satisfy the given predicate, and the rest of the linear sequence. + * + * @param p the test predicate + */ + override def span(p: A => Boolean): (Repr, Repr) = { + var these: Repr = repr + val b = newBuilder + while (!these.isEmpty && p(these.head)) { + b += these.head + these = these.tail + } + (b.result, these) + } + + /** Returns true iff the other linear sequence contains the same elements as this one. + * + * @note will not terminate for two infinite-sized linear sequences. + * @param that the other linear sequence + */ + override def sameElements[B >: A](that: Iterable[B]): Boolean = that match { + case that1: LinearSequence[_] => + var these = this + var those = that + while (!these.isEmpty && !those.isEmpty && these.head == those.head) { + these = these.tail + those = those.tail + } + these.isEmpty && those.isEmpty + case _ => super.sameElements(that) + } + + // Overridden methods from Sequence + + /** Result of comparing <code>length</code> with operand <code>len</code>. + * returns <code>x</code> where + * <code>x < 0</code> iff <code>this.length < len</code> + * <code>x == 0</code> iff <code>this.length == len</code> + * <code>x > 0</code> iff <code>this.length > len</code>. + */ + override def lengthCompare(len: Int): Int = { + var i = 0 + var these = self + while (!these.isEmpty && i <= len) { + i += 1 + these = these.tail + } + i - len + } + + /** Is this partial function defined for the index <code>x</code>? + */ + override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) > 0 + + /** Returns length of longest segment starting from a start index `from` + * such that every element of the segment satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + override def segmentLength(p: A => Boolean, from: Int): Int = { + var i = 0 + var these = this drop from + while (!these.isEmpty && p(these.head)) { + i += 1 + these = these.tail + } + i + } + + /** Returns index of the first element starting from a start index + * satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized linear sequences. + * @param p the predicate + * @param from the start index + */ + override def indexWhere(p: A => Boolean, from: Int): Int = { + var i = from + var these = this drop from + while (!these.isEmpty && !p(these.head)) { + i += 1 + these = these.tail + } + if (these.isEmpty) -1 else i + } + + /** Returns index of the last element satisying a predicate, or -1, if none exists. + * + * @param p the predicate + * @return the index of the last element satisfying <code>p</code>, + * or -1 if such an element does not exist + */ + override def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = 0 + var these = this + var last = -1 + while (!these.isEmpty && i <= end) { + if (p(these.head)) last = i + these = these.tail + i += 1 + } + last + } +} diff --git a/src/library/scala/collection/SequenceLike.scala b/src/library/scala/collection/SequenceLike.scala new file mode 100755 index 0000000000..bd62590c4c --- /dev/null +++ b/src/library/scala/collection/SequenceLike.scala @@ -0,0 +1,492 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: SequenceTemplate.scala 18646 2009-09-04 16:56:11Z odersky $ + + +package scala.collection +import generic._ +import mutable.{ListBuffer, HashMap} + +// import immutable.{List, Nil, ::} +import generic._ + +/** Class <code>Sequence[A]</code> represents sequences of elements + * of type <code>A</code>. + * It adds the following methods to class Iterable: + * `length`, `lengthCompare`, `apply`, `isDefinedAt`, `segmentLength`, `prefixLength`, + * `indexWhere`, `indexOf`, `lastIndexWhere`, `lastIndexOf`, `reverse`, `reverseIterator`, + * `startsWith`, `endsWith`, `indexOfSeq`, , `zip`, `zipAll`, `zipWithIndex`. + * + * + * @author Martin Odersky + * @author Matthias Zenger + * @version 1.0, 16/07/2003 + */ +trait SequenceLike[+A, +Repr] extends IterableLike[A, Repr] { self => + + override protected[this] def thisCollection: Sequence[A] = this.asInstanceOf[Sequence[A]] + override protected[this] def toCollection(repr: Repr): Sequence[A] = repr.asInstanceOf[Sequence[A]] + + import Traversable.breaks._ + + /** Returns the length of the sequence. + */ + def length: Int + + /** Returns the elements at position `idx` + */ + def apply(idx: Int): A + + /** Result of comparing <code>length</code> with operand <code>len</code>. + * returns <code>x</code> where + * <code>x < 0</code> iff <code>this.length < len</code> + * <code>x == 0</code> iff <code>this.length == len</code> + * <code>x > 0</code> iff <code>this.length > len</code>. + * + * The method as implemented here does not call length directly; its running time + * is O(length min len) instead of O(length). The method should be overwritten + * if computing length is cheap. + */ + def lengthCompare(len: Int): Int = { + var i = 0 + breakable { + for (_ <- this) { + i += 1 + if (i > len) break + } + } + i - len + } + + /** Should always be <code>length</code> */ + override def size = length + + /** Is this partial function defined for the index <code>x</code>? + */ + def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) + + /** Returns length of longest segment starting from a start index `from` + * such that every element of the segment satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + def segmentLength(p: A => Boolean, from: Int): Int = { + var result = 0 + var i = 0 + breakable { + for (x <- this) { + if (i >= from && !p(x)) { result = i - from; break } + else i += 1 + } + } + result + } + + /** Returns length of longest prefix of this seqence + * such that every element of the prefix satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def prefixLength(p: A => Boolean) = segmentLength(p, 0) + + /** Returns index of the first element satisfying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) + + /** Returns index of the first element starting from a start index + * satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + def indexWhere(p: A => Boolean, from: Int): Int = { + var result = -1 + var i = from + breakable { + for (x <- this) { + if (i >= from && p(x)) { result = i; break } + else i += 1 + } + } + result + } + + /** Returns index of the first element satisying a predicate, or -1. */ + @deprecated("Use `indexWhere' instead") + def findIndexOf(p: A => Boolean): Int = indexWhere(p) + + /** Returns the index of the first occurence of the specified + * object in this iterable object. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) + + /** Returns the index of the first occurence of the specified + * object in this iterable object, starting from a start index, or + * -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + */ + def indexOf[B >: A](elem: B, from: Int): Int = indexWhere(elem ==, from) + + /** Returns the index of the last occurence of the specified element + * in this sequence, or -1 if the sequence does not contain this element. + * + * @param elem element to search for. + * @return the index in this sequence of the last occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def lastIndexOf[B >: A](elem: B): Int = lastIndexWhere(elem ==) + + /** Returns the index of the last + * occurence of the specified element in this sequence + * before or at a given end index, + * or -1 if the sequence does not contain this element. + * + * @param elem element to search for. + * @param end the end index + */ + def lastIndexOf[B >: A](elem: B, end: Int): Int = lastIndexWhere(elem ==, end) + + /** Returns index of the last element satisying a predicate, or -1, if none exists. + * + * @param p the predicate + * @return the index of the last element satisfying <code>p</code>, + * or -1 if such an element does not exist + */ + def lastIndexWhere(p: A => Boolean): Int = lastIndexWhere(p, length - 1) + + /** Returns index of the last element not exceeding a given end index + * and satisying a predicate, or -1 if none exists. + * + * @param end the end index + * @param p the predicate + */ + def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = length - 1 + val it = reverseIterator + while (it.hasNext && { val elem = it.next; (i > end || !p(elem)) }) i -= 1 + i + } + + /** A sequence of type <code>C</code> consisting of all elements of + * this sequence in reverse order. + * @note the operation is implemented by building a new sequence + * from <code>this(length - 1), ..., this(0)</code> + * If random access is inefficient for the given sequence implementation, + * this operation should be overridden. + */ + def reverse: Repr = { + var xs: List[A] = List() + for (x <- this) + xs = x :: xs + val b = newBuilder + for (x <- xs) + b += x + b.result + } + + /** The elements of this sequence in reversed order + */ + def reverseIterator: Iterator[A] = toCollection(reverse).iterator + + @deprecated("use `reverseIterator' instead") + def reversedElements = reverseIterator + + /** + * Checks whether the argument sequence is contained at the + * specified index within the receiver object. + * + * If the both the receiver object, <code>this</code> and + * the argument, <code>that</code> are infinite sequences + * this method may not terminate. + * + * @return true if <code>that</code> is contained in + * <code>this</code>, at the specified index, otherwise false + * + * @see String.startsWith + */ + def startsWith[B](that: Sequence[B], offset: Int): Boolean = { + val i = this.iterator drop offset + val j = that.iterator + while (j.hasNext && i.hasNext) + if (i.next != j.next) + return false + + !j.hasNext + } + + /** + * Check whether the receiver object starts with the argument sequence. + * + * @return true if <code>that</code> is a prefix of <code>this</code>, + * otherwise false + */ + def startsWith[B](that: Sequence[B]): Boolean = startsWith(that, 0) + + /** @return true if this sequence end with that sequence + * @see String.endsWith + */ + def endsWith[B](that: Sequence[B]): Boolean = { + val i = this.iterator.drop(length - that.length) + val j = that.iterator + while (i.hasNext && j.hasNext) + if (i.next != j.next) + return false + + !j.hasNext + } + + /** @return -1 if <code>that</code> not contained in this, otherwise the + * first index where <code>that</code> is contained. + */ + def indexOfSeq[B >: A](that: Sequence[B]): Int = indexOfSeq(that, 0) + + def indexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = + if (this.hasDefiniteSize && that.hasDefiniteSize) + KMP.indexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) + else { + var i = fromIndex + var s: Sequence[A] = thisCollection drop i + while (!s.isEmpty) { + if (s startsWith that) + return i + + i += 1 + s = s.tail + } + -1 + } + + /** @return -1 if <code>that</code> not contained in this, otherwise the + * last index where <code>that</code> is contained. + * @note may not terminate for infinite-sized collections. + */ + def lastIndexOfSeq[B >: A](that: Sequence[B]): Int = lastIndexOfSeq(that, that.length) + + // since there's no way to find the last index in an infinite sequence, + // we just document it may not terminate and assume it will. + def lastIndexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = + KMP.lastIndexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) + + /** Tests if the given value <code>elem</code> is a member of this + * sequence. + * + * @param elem element whose membership has to be tested. + * @return <code>true</code> iff there is an element of this sequence + * which is equal (w.r.t. <code>==</code>) to <code>elem</code>. + */ + def contains(elem: Any): Boolean = exists (_ == elem) + + /** <p> + * Computes the multiset union of this sequence and the given sequence + * <code>that</code>. For example: + * </p><pre> + * <b>val</b> xs = List(1, 1, 2) + * <b>val</b> ys = List(1, 2, 2, 3) + * println(xs union ys) // prints "List(1, 1, 2, 1, 2, 2, 3)" + * println(ys union xs) // prints "List(1, 2, 2, 3, 1, 1, 2)" + * </pre> + * + * @param that the sequence of elements to add to the sequence. + * @return a sequence containing the elements of this + * sequence and those of the given sequence <code>that</code>. + */ + def union[B >: A, That](that: Sequence[B])(implicit bf: BuilderFactory[B, That, Repr]): That = + this ++ that + + /** <p> + * Computes the multiset difference between this sequence and the + * given sequence <code>that</code>. If an element appears more + * than once in both sequences, the difference contains <i>m</i> copies + * of that element, where <i>m</i> is the difference between the + * number of times the element appears in this sequence and the number + * of times it appears in <code>that</code>. For example: + * </p><pre> + * <b>val</b> xs = List(1, 1, 2) + * <b>val</b> ys = List(1, 2, 2, 3) + * println(xs diff ys) // prints "List(1)" + * println(xs -- ys) // prints "List()" + * </pre> + * + * @param that the sequence of elements to remove from this sequence. + * @return the sequence of elements contained only in this sequence plus + * <i>m</i> copies of each element present in both sequences, + * where <i>m</i> is defined as above. + */ + def diff[B >: A, That](that: Sequence[B]): Repr = { + val occ = occCounts(that) + val b = newBuilder + for (x <- this) + if (occ(x) == 0) b += x + else occ(x) -= 1 + b.result + } + + /** <p> + * Computes the multiset intersection between this sequence and the + * given sequence <code>that</code>; the intersection contains <i>m</i> + * copies of an element contained in both sequences, where <i>m</i> is + * the smaller of the number of times the element appears in this + * sequence or in <code>that</code>. For example: + * </p><pre> + * <b>val</b> xs = List(1, 1, 2) + * <b>val</b> ys = List(3, 2, 2, 1) + * println(xs intersect ys) // prints "List(1, 2)" + * println(ys intersect xs) // prints "List(2, 1)" + * </pre> + * + * @param that the sequence to intersect. + * @return the sequence of elements contained both in this sequence and + * in the given sequence <code>that</code>. + */ + def intersect[B >: A, That](that: Sequence[B]): Repr = { + val occ = occCounts(that) + val b = newBuilder + for (x <- this) + if (occ(x) > 0) { + b += x + occ(x) -= 1 + } + b.result + } + + 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 + } + + /** Builds a new sequence from this sequence in which any duplicates (wrt to ==) removed. + * Among duplicate elements, only the first one is retained in the result sequence + */ + def removeDuplicates: Repr = { + val b = newBuilder + var seen = Set[A]() + for (x <- this) { + if (!(seen contains x)) { + b += x + seen = (seen + x) + } + } + b.result + } + + /** A new sequence, consisting of all elements of current sequence + * except that `replaced` elements starting from `from` are replaced + * by `patch`. + */ + def patch[B >: A, That](from: Int, patch: Sequence[B], replaced: Int)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + val (prefix, rest) = this.splitAt(from) + b ++= toCollection(prefix) + b ++= patch + b ++= toCollection(rest).view drop replaced + b.result + } + + /** Returns a new sequence of given length containing the elements of this sequence followed by zero + * or more occurrences of given elements. + */ + def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + b.sizeHint(length max len) + var diff = len - length + b ++= thisCollection + while (diff > 0) { + b += elem + diff -=1 + } + b.result + } + + /** + * Overridden for efficiency. + * + * @return the sequence itself + */ + override def toSequence: Sequence[A] = thisCollection + + /** The range of all indices of this sequence. + */ + def indices: Range = 0 until length + + override def view = new SequenceView[A, Repr] { + protected lazy val underlying = self.repr + override def iterator = self.iterator + override def length = self.length + override def apply(idx: Int) = self.apply(idx) + } + + override def view(from: Int, until: Int) = view.slice(from, until) + + override def hashCode() = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode) + + override def equals(that: Any): Boolean = that match { + case that: Sequence[_] => /*(that canEqual this)!!! &&*/ (this sameElements that) + case _ => false + } + + /** Need to override string, so that it's not the Function1's string that gets mixed in. + */ + override def toString = super[IterableLike].toString + + /** Returns index of the last element satisying a predicate, or -1. */ + @deprecated("use `lastIndexWhere' instead") + def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) + + /** A sub-sequence starting at index <code>from</code> + * and extending up to the length of the current sequence + * + * @param from The index of the first element of the slice + * @throws IndexOutOfBoundsException if <code>from < 0</code> + */ + @deprecated("use `drop' instead") + def slice(from: Int): Sequence[A] = toCollection(slice(from, length)) + + @deprecated("Should be replaced by <code>(s1, s2) forall { case (x, y) => f(x, y) }</code>") + def equalsWith[B](that: Sequence[B])(f: (A,B) => Boolean): Boolean = { + val i = this.iterator + val j = that.iterator + while (i.hasNext && j.hasNext) + if (!f(i.next, j.next)) + return false + + !i.hasNext && !j.hasNext + } + + /** Is <code>that</code> a slice in this? */ + @deprecated("Should be replaced by <code>indexOfSeq(that) != -1</code>") + def containsSlice[B](that: Sequence[B]): Boolean = indexOfSeq(that) != -1 + + /** + * returns a projection that can be used to call non-strict <code>filter</code>, + * <code>map</code>, and <code>flatMap</code> methods that build projections + * of the collection. + */ + @deprecated("use `view' instead") + override def projection = view +} + diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala new file mode 100755 index 0000000000..bf76fa09b3 --- /dev/null +++ b/src/library/scala/collection/TraversableLike.scala @@ -0,0 +1,829 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: TraversableLike.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection +import generic._ +import scala.reflect.ClassManifest + +// import immutable.{List, Stream, Nil} //!!! +import mutable.{Buffer, ArrayBuffer, ListBuffer} +import annotation.experimental + +/** <p> + * A template trait for traversable collections. + * This is a base trait of all kinds of Scala collections. It implements + * the behavior common to all collections, in terms of a method + * <code>foreach</code> with signature: + * </p><pre> + * <b>def</b> foreach[U](f: Elem => U): Unit</pre> + * <p> + * Collection classes mixing in this trait provide a concrete + * <code>foreach</code> method which traverses all the + * elements contained in the collection, applying a given function to each. + * They also need to provide a method <code>newBuilder</code> + * which creates a builder for collections of the same kind. + * </p> + * <p> + * A traversable class might or might not have two properties: strictness + * and orderedness. Neither is represented as a type. + * </p> + * <p> + * The instances of a strict collection class have all their elements + * computed before they can be used as values. By contrast, instances of + * a non-strict collection class may defer computation of some of their + * elements until after the instance is available as a value. + * A typical example of a non-strict collection class is a + * <a href="../immutable/Stream.html" target="ContentFrame"> + * <code>scala.collection.immutable.Stream</code></a>. + * A more general class of examples are <code>TraversableViews</code>. + * </p> + * <p> + * If a collection is an instance of an ordered collection class, traversing + * its elements with <code>foreach</code> will always visit elements in the + * same order, even for different runs of the program. If the class is not + * ordered, <code>foreach</code> can visit elements in different orders for + * different runs (but it will keep the same order in the same run).<br/> + * A typical example of a collection class which is not ordered is a + * <code>HashMap</code> of objects. The traversal order for hash maps will + * depend on the hash codes of its elements, and these hash codes might + * differ from one run to the next. By contrast, a <code>LinkedHashMap</code> + * is odered because it's <code>foreach</code> method visits elements in the + * order they were inserted into the <code>HashMap</code>. + * </p> + * + * @author Martin Odersky + * @version 2.8 + */ +trait TraversableLike[+A, +Repr] { +self => + + import Traversable.breaks._ + + def repr: Repr = this.asInstanceOf[Repr] + + protected[this] def thisCollection: Traversable[A] = this.asInstanceOf[Traversable[A]] + protected[this] def toCollection(repr: Repr): Traversable[A] = repr.asInstanceOf[Traversable[A]] + + /** Create a new builder for this collection type. + */ + protected[this] def newBuilder: Builder[A, Repr] + + /** Apply a function <code>f</code> to all elements of this + * traversable object. + * + * @param f A function that is applied for its side-effect to every element. + * The result (of arbitrary type U) of function `f` is discarded. + * + * @note This method underlies the implementation of most other bulk operations. + * It's important to implement this method in an efficient way. + */ + def foreach[U](f: A => U): Unit + + /** Does this collection contain no elements? + */ + def isEmpty: Boolean = { + var result = true + breakable { + for (x <- this) { + result = false + break + } + } + result + } + + /** Does this collection contain some elements? + */ + def nonEmpty: Boolean = !isEmpty + + /** The number of elements in this collection + */ + def size: Int = { + var result = 0 + for (x <- this) result += 1 + result + } + + /** Returns true if this collection is known to have finite size. + * This is the case if the collection type is strict, or if the + * collection type is non-strict (e.g. it's a Stream), but all + * collection elements have been computed. + * Many methods in this trait will not work on collections of + * infinite sizes. + */ + def hasDefiniteSize = true + + /** Creates a new traversable of type `That` which contains all elements of this traversable + * followed by all elements of another traversable. + * + * @param that The traversable to append + */ + def ++[B >: A, That](that: Traversable[B])(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + b ++= thisCollection + b ++= that + b.result + } + + /** Creates a new traversable of type `That` which contains all elements of this traversable + * followed by all elements of an iterator. + * + * @param that The iterator to append + */ + def ++[B >: A, That](that: Iterator[B])(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + b ++= thisCollection + b ++= that + b.result + } + + /** Returns the traversable that results from applying the given function + * <code>f</code> to each element of this traversable and collecting the results + * in a traversable of type `That`. + * + * @param f function to apply to each element. + */ + def map[B, That](f: A => B)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + for (x <- this) b += f(x) + b.result + } + + /** Applies the given function <code>f</code> to each element of + * this traversable, then concatenates the results in a traversable of type That. + * + * @param f the function to apply on each element. + */ + def flatMap[B, That](f: A => Traversable[B])(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + for (x <- this) b ++= f(x) + b.result + } + + /** Returns all the elements of this traversable that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * @param p the predicate used to filter the traversable. + * @return the elements of this traversable satisfying <code>p</code>. + */ + def filter(p: A => Boolean): Repr = { + val b = newBuilder + for (x <- this) + if (p(x)) b += x + b.result + } + + /** Returns a traversable with all elements of this traversable which do not satisfy the predicate + * <code>p</code>. + * + * @param p the predicate used to test elements + * @return the traversable without all elements that satisfy <code>p</code> + */ + def filterNot(p: A => Boolean): Repr = filter(!p(_)) + + /** Returns a new traversable based on the partial function <code>pf</code>, + * containing pf(x) for all the elements which are defined on pf. + * The order of the elements is preserved. + * @param pf the partial function which filters and maps the traversable. + * @return the new traversable. + */ + @experimental + def filterMap[B, That](pf: PartialFunction[Any, B])(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + for (x <- this) if (pf.isDefinedAt(x)) b += pf(x) + b.result + } + + /** Returns a traversable with all elements of this traversable which do not satisfy the predicate + * <code>p</code>. + * + * @param p the predicate used to test elements + * @return the traversable without all elements that satisfy <code>p</code> + */ + @deprecated("use `filterNot' instead") + def remove(p: A => Boolean): Repr = filterNot(p) + + /** Partitions this traversable in two traversables according to a predicate. + * + * @param p the predicate on which to partition + * @return a pair of traversables: the traversable that satisfies the predicate + * <code>p</code> and the traversable that does not. + * The relative order of the elements in the resulting traversables + * is the same as in the original traversable. + */ + def partition(p: A => Boolean): (Repr, Repr) = { + val l, r = newBuilder + for (x <- this) (if (p(x)) l else r) += x + (l.result, r.result) + } + + /** Partition this traversable into a map of traversables + * according to some discriminator function. + * @invariant (xs partition f)(k) = xs filter (x => f(x) == k) + * + * @note This method is not re-implemented by views. This means + * when applied to a view it will always force the view and + * return a new collection. + */ + def groupBy[K](f: A => K): Map[K, Repr] = { + var m = Map[K, Builder[A, Repr]]() + for (elem <- this) { + val key = f(elem) + val bldr = m get key match { + case None => val b = newBuilder; m = m updated (key, b); b + case Some(b) => b + } + bldr += elem + } + m mapValues (_.result) + } + + /** Return true iff the given predicate `p` yields true for all elements + * of this traversable. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def forall(p: A => Boolean): Boolean = { + var result = true + breakable { + for (x <- this) + if (!p(x)) { result = false; break } + } + result + } + + /** Return true iff there is an element in this traversable for which the + * given predicate `p` yields true. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def exists(p: A => Boolean): Boolean = { + var result = false + breakable { + for (x <- this) + if (p(x)) { result = true; break } + } + result + } + + /** Count the number of elements in the traversable which satisfy a predicate. + * + * @note Will not terminate for infinite-sized collections. + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate <code>p</code>. + */ + def count(p: A => Boolean): Int = { + var cnt = 0 + for (x <- this) { + if (p(x)) cnt += 1 + } + cnt + } + + /** Find and return the first element of the traversable object satisfying a + * predicate, if any. + * + * @note may not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered. + * @param p the predicate + * @return an option containing the first element in the traversable object + * satisfying <code>p</code>, or <code>None</code> if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var result: Option[A] = None + breakable { + for (x <- this) + if (p(x)) { result = Some(x); break } + } + result + } + + /** Combines the elements of this traversable object together using the binary + * function <code>f</code>, from left to right, and starting with + * the value <code>z</code>. + * + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), + * a<sub>n</sub>)</code> if the traversable is + * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var result = z + for (x <- this) + result = op(result, x) + result + } + + /** Similar to <code>foldLeft</code> but can be used as + * an operator with the order of traversable and zero arguments reversed. + * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + */ + def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) + + /** Combines the elements of this traversable together using the binary + * function <code>f</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> + * if the traversable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = { + var elems: List[A] = Nil + for (x <- this) elems = x :: elems + elems.foldLeft(z)((x, y) => op(y, x)) + } + + /** An alias for <code>foldRight</code>. + * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + */ + def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) + + /** Combines the elements of this traversable object together using the binary + * operator <code>op</code>, from left to right + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @param op The operator to apply + * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> + if the traversable object has elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + * @throws Predef.UnsupportedOperationException if the traversable object is empty. + */ + def reduceLeft[B >: A](op: (B, A) => B): B = { + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + var result: B = head + var first = true + for (x <- this) + if (first) first = false + else result = op(result, x) + result + } + + /** Combines the elements of this traversable object together using the binary + * operator <code>op</code>, from left to right + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @param op The operator to apply + * @return If the traversable is non-empty, the result of the operations as an Option, otherwise None. + */ + def reduceLeftOption[B >: A](op: (B, A) => B): Option[B] = { + if (isEmpty) None else Some(reduceLeft(op)) + } + + /** Combines the elements of this traversable object together using the binary + * operator <code>op</code>, from right to left + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @param op The operator to apply + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> + * if the traversable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceRight[B >: A](op: (A, B) => B): B = { + if (isEmpty) throw new UnsupportedOperationException("empty.reduceRight") + var elems: List[A] = Nil + for (x <- this) elems = x :: elems + elems.reduceLeft[B]((x, y) => op(y, x)) + } + + /** Combines the elements of this traversable object together using the binary + * operator <code>op</code>, from right to left. + * @note Will not terminate for infinite-sized collections. + * @note Might return different results for different runs, unless this traversable is ordered, or + * the operator is associative and commutative. + * @param op The operator to apply + * @return If the traversable is non-empty, the result of the operations as an Option, otherwise None. + */ + def reduceRightOption[B >: A](op: (A, B) => B): Option[B] = { + if (isEmpty) None else Some(reduceRight(op)) + } + + /** Returns the sum of all elements with respect to the numeric operations in `num` */ + def sum[B >: A](implicit num: Numeric[B]): B = { + var acc = num.zero + for (x <- self) acc = num.plus(acc, x) + acc + } + + /** Returns the product of all elements with respect to the numeric operations in `num` */ + def product[B >: A](implicit num: Numeric[B]): B = { + var acc = num.one + for (x <- self) acc = num.times(acc, x) + acc + } + + /** Returns the minimal element with respect to the given ordering `cmp` */ + def min[B >: A](implicit cmp: Ordering[B]): A = { + require(!self.isEmpty, "<empty>.min") + var acc = self.head + for (x <- self) + if (cmp.lt(x, acc)) acc = x + acc + } + + /** Returns the maximal element with respect to the given ordering `cmp` */ + def max[B >: A](implicit cmp: Ordering[B]): A = { + require(!self.isEmpty, "<empty>.max") + var acc = self.head + for (x <- self) + if (cmp.gt(x, acc)) acc = x + acc + } + + /** The first element of this traversable. + * + * @note Might return different results for different runs, unless this traversable is ordered + * @throws Predef.NoSuchElementException if the traversable is empty. + */ + def head: A = { + var result: () => A = () => throw new NoSuchElementException + breakable { + for (x <- this) { + result = () => x + break + } + } + result() + } + + /** Returns as an option the first element of this traversable + * or <code>None</code> if traversable is empty. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def headOption: Option[A] = if (isEmpty) None else Some(head) + + /** a traversable consisting of all elements of this traversable + * except the first one. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def tail: Repr = { + require(!self.isEmpty, "<empty>.tail") + drop(1) + } + + /** The last element of this traversable. + * + * @throws Predef.NoSuchElementException if the traversable is empty. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def last: A = { + var lst = head + for (x <- this) + lst = x + lst + } + + /** Returns as an option the last element of this traversable or + * <code>None</code> if traversable is empty. + * + * @return the last element as an option. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def lastOption: Option[A] = if (isEmpty) None else Some(last) + + /** a traversable consisting of all elements of this traversable except the last one. + * @throws Predef.UnsupportedOperationException if the stream is empty. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def init: Repr = { + if (isEmpty) throw new UnsupportedOperationException("empty.init") + var lst = head + var follow = false + val b = newBuilder + for (x <- this) { + if (follow) b += lst + else follow = true + lst = x + } + b.result + } + + /** Return a traversable consisting only of the first <code>n</code> + * elements of this traversable, or else the whole traversable, if it has less + * than <code>n</code> elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this traversable is ordered + */ + def take(n: Int): Repr = { + val b = newBuilder + var i = 0 + breakable { + for (x <- this) { + if (i >= n) break + b += x + i += 1 + } + } + b.result + } + + /** Returns this traversable without its <code>n</code> first elements + * If this traversable has less than <code>n</code> elements, the empty + * traversable is returned. + * + * @param n the number of elements to drop + * @return the new traversable + * @note Might return different results for different runs, unless this traversable is ordered + */ + def drop(n: Int): Repr = { + val b = newBuilder + var i = 0 + for (x <- this) { + if (i >= n) b += x + i += 1 + } + b.result + } + + /** A sub-traversable starting at index `from` + * and extending up to (but not including) index `until`. + * + * @note c.slice(from, to) is equivalent to (but possibly more efficient than) + * c.drop(from).take(to - from) + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @note Might return different results for different runs, unless this traversable is ordered + */ + def slice(from: Int, until: Int): Repr = { + val b = newBuilder + var i = 0 + breakable { + for (x <- this) { + if (i >= from) b += x + i += 1 + if (i == until) break + } + } + b.result + } + + /** Returns the longest prefix of this traversable whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def takeWhile(p: A => Boolean): Repr = { + val b = newBuilder + breakable { + for (x <- this) { + if (!p(x)) break + b += x + } + } + b.result + } + + /** Returns the longest suffix of this traversable whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def dropWhile(p: A => Boolean): Repr = { + val b = newBuilder + var go = false + for (x <- this) { + if (!p(x)) go = true + if (go) b += x + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the traversable whose + * elements all satisfy the given predicate, and the rest of the traversable. + * + * @param p the test predicate + * @return a pair consisting of the longest prefix of the traversable whose + * elements all satisfy <code>p</code>, and the rest of the traversable. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def span(p: A => Boolean): (Repr, Repr) = { + val l, r = newBuilder + var toLeft = true + for (x <- this) { + toLeft = toLeft && p(x) + (if (toLeft) l else r) += x + } + (l.result, r.result) + } + + /** Split the traversable at a given point and return the two parts thus + * created. + * + * @param n the position at which to split + * @return a pair of traversables composed of the first <code>n</code> + * elements, and the other elements. + * @note Might return different results for different runs, unless this traversable is ordered + */ + def splitAt(n: Int): (Repr, Repr) = { + val l, r = newBuilder + var i = 0 + for (x <- this) { + (if (i < n) l else r) += x + i += 1 + } + (l.result, r.result) + } + + /** Copy all elements of this traversable to a given buffer + * @note Will not terminate for infinite-sized collections. + * @param dest The buffer to which elements are copied + */ + def copyToBuffer[B >: A](dest: Buffer[B]) { + for (x <- this) dest += x + } + + /** Fills the given array <code>xs</code> with at most `len` elements of + * this traversable starting at position `start`. + * Copying will stop once either the end of the current traversable is reached or + * `len` elements have been copied or the end of the array is reached. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + */ + def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { + var i = start + val end = (start + len) min xs.length + breakable { + for (x <- this) { + if (i >= end) break + xs(i) = x + i += 1 + } + } + } + + /** Fills the given array <code>xs</code> with the elements of + * this traversable starting at position <code>start</code> + * until either the end of the current traversable or the end of array `xs` is reached. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int) { + copyToArray(xs, start, xs.length - start) + } + + /** Converts this traversable to a fresh Array containing all elements. + * @note Will not terminate for infinite-sized collections. + */ + def toArray[B >: A : ClassManifest]: Array[B] = { + val result = new Array[B](size) + copyToArray(result, 0) + result + } + + /** Returns a list with all elements of this traversable object. + * @note Will not terminate for infinite-sized collections. + */ + def toList: List[A] = (new ListBuffer[A] ++= thisCollection).toList + + /** Returns a traversable with all elements in this traversable object. + * @note Will not terminate for infinite-sized collections. + */ + def toIterable: Iterable[A] = toStream + + /** Returns a sequence with all elements in this traversable object. + * @note Will not terminate for infinite-sized collections. + */ + def toSequence: Sequence[A] = toList + + /** Returns a vector with all elements in this traversable object. + * @note Will not terminate for infinite-sized collections. + */ + def toVector[B >: A]: mutable.Vector[B] = (new ArrayBuffer[B] ++= thisCollection) + + /** Returns a stream with all elements in this traversable object. + */ + def toStream: Stream[A] = toList.toStream + + /** Returns a set with all unique elements in this traversable object. + */ + @experimental + def toSet[B >: A]: immutable.Set[B] = immutable.Set() ++ thisCollection + + /** Returns a string representation of this traversable object. The resulting string + * begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. + * + * @ex <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this traversable object. + */ + def mkString(start: String, sep: String, end: String): String = + addString(new StringBuilder(), start, sep, end).toString + + /** Returns a string representation of this traversable object. The string + * representations of elements (w.r.t. the method <code>toString()</code>) + * are separated by the string <code>sep</code>. + * + * @param sep separator string. + * @return a string representation of this traversable object. + */ + def mkString(sep: String): String = + addString(new StringBuilder(), sep).toString + + /** Returns a string representation of this traversable object. The string + * representations of elements (w.r.t. the method <code>toString()</code>) + * follow each other without any separator string. + */ + def mkString: String = + addString(new StringBuilder()).toString + + /** Write all elements of this traversable into given string builder. + * The written text begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. + */ + def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + b append start + var first = true + for (x <- this) { + if (first) first = false + else b append sep + b append x + } + b append end + } + + /** Write all elements of this string into given string builder. + * The string representations of elements (w.r.t. the method <code>toString()</code>) + * are separated by the string <code>sep</code>. + */ + def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "") + + /** Write all elements of this string into given string builder without using + * any separator between consecutive elements. + */ + def addString(b: StringBuilder): StringBuilder = addString(b, "") + + override def toString = mkString(stringPrefix + "(", ", ", ")") + + /** Defines the prefix of this object's <code>toString</code> representation. + */ + def stringPrefix : String = { + var string = repr.asInstanceOf[AnyRef].getClass.getName + val idx1 = string.lastIndexOf('.' : Int) + if (idx1 != -1) string = string.substring(idx1 + 1) + val idx2 = string.indexOf('$') + if (idx2 != -1) string = string.substring(0, idx2) + string + } + + /** Creates a view of this traversable @see TraversableView + */ + def view = new TraversableView[A, Repr] { + protected lazy val underlying = self.repr + override def foreach[B](f: A => B) = self foreach f + } + + /** A sub-traversable starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current traversable, whereas `slice` produces a new traversable. + * + * @note Might return different results for different runs, unless this traversable is ordered + * @note view(from, to) is equivalent to view.slice(from, to) + */ + def view(from: Int, until: Int): TraversableView[A, Repr] = view.slice(from, until) +} diff --git a/src/library/scala/collection/VectorLike.scala b/src/library/scala/collection/VectorLike.scala new file mode 100755 index 0000000000..dc1c5aed4a --- /dev/null +++ b/src/library/scala/collection/VectorLike.scala @@ -0,0 +1,274 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2006-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: VectorTemplate.scala 18646 2009-09-04 16:56:11Z odersky $ + +package scala.collection +import generic._ +import mutable.ArrayBuffer + +/** Sequences that support O(1) element access and O(1) length computation. + * This class does not add any methods to Sequence but overrides several + * methods with optimized implementations. + * + * @author Sean McDirmid + * @author Martin Odersky + * @version 2.8 + */ +trait VectorLike[+A, +Repr] extends SequenceLike[A, Repr] { self => + + override protected[this] def thisCollection: Vector[A] = this.asInstanceOf[Vector[A]] + override protected[this] def toCollection(repr: Repr): Vector[A] = repr.asInstanceOf[Vector[A]] + + // Overridden methods from IterableTemplate + + /** The iterator returned by the iterator method + */ + @serializable @SerialVersionUID(1756321872811029277L) + protected class Elements(start: Int, end: Int) extends BufferedIterator[A] { + private var i = start + + def hasNext: Boolean = i < end + + def next: A = + if (i < end) { + val x = self(i) + i += 1 + x + } else Iterator.empty.next + + def head = + if (i < end) self(i) else Iterator.empty.next + + /** drop is overridden to enable fast searching in the middle of random access sequences */ + override def drop(n: Int): Iterator[A] = + if (n > 0) new Elements(start + n, end) else this + + /** take is overridden to be symmetric to drop */ + override def take(n: Int): Iterator[A] = + if (n <= 0) Iterator.empty.buffered + else if (start + n < end) new Elements(start, start + n) + else this + } + + override def iterator: Iterator[A] = new Elements(0, length) + + override def isEmpty: Boolean = { length == 0 } + + override def foreach[U](f: A => U): Unit = { + var i = 0 + val len = length + while (i < len) { f(this(i)); i += 1 } + } + + override def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length + override def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length + + override def find(p: A => Boolean): Option[A] = { + val i = prefixLength(!p(_)) + if (i < length) Some(this(i)) else None + } + + private def foldl[B](start: Int, z: B, op: (B, A) => B): B = { + var i = start + val len = length + var result = z + while (i < len) { + result = op(result, this(i)) + i += 1 + } + result + } + + private def foldr[B](start: Int, len: Int, z: B, op: (A, B) => B): B = + if (start == len) z + else op(this(start), foldr(start + 1, len, z, op)) + + override def foldLeft[B](z: B)(op: (B, A) => B): B = + foldl(0, z, op) + override def foldRight[B](z: B)(op: (A, B) => B): B = + foldr(0, length, z, op) + override def reduceLeft[B >: A](op: (B, A) => B): B = + if (length > 0) foldl(1, this(0), op) else super.reduceLeft(op) + override def reduceRight[B >: A](op: (A, B) => B): B = + if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op) + + override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, Repr]): That = that match { + case that: Vector[_] => + val b = bf(repr) + var i = 0 + val len = this.length min that.length + b.sizeHint(len) + while (i < len) { + b += ((this(i), that(i).asInstanceOf[B])) + i += 1 + } + b.result + case _ => + super.zip[A1, B, That](that)(bf) + } + + override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, Repr]): That = { + val b = bf(repr) + val len = length + b.sizeHint(len) + var i = 0 + while (i < len) { + b += ((this(i), i)) + i += 1 + } + b.result + } + + override def slice(from: Int, until: Int): Repr = { + var i = from max 0 + val end = until min length + val b = newBuilder + b.sizeHint(end - i) + while (i < end) { + b += this(i) + i += 1 + } + b.result + } + + override def head: A = if (isEmpty) super.head else this(0) + override def tail: Repr = if (isEmpty) super.tail else slice(1, length) + override def last: A = if (length > 0) this(length - 1) else super.last + override def init: Repr = if (length > 0) slice(0, length - 1) else super.init + override def take(n: Int): Repr = slice(0, n) + override def drop(n: Int): Repr = slice(n, length) + override def takeRight(n: Int): Repr = slice(length - n, length) + override def dropRight(n: Int): Repr = slice(0, length - n) + override def splitAt(n: Int): (Repr, Repr) = (take(n), drop(n)) + override def takeWhile(p: A => Boolean): Repr = take(prefixLength(p)) + override def dropWhile(p: A => Boolean): Repr = drop(prefixLength(p)) + override def span(p: A => Boolean): (Repr, Repr) = splitAt(prefixLength(p)) + + override def sameElements[B >: A](that: Iterable[B]): Boolean = that match { + case that: Vector[_] => + val len = length + len == that.length && { + var i = 0 + while (i < len && this(i) == that(i)) i += 1 + i == len + } + case _ => + super.sameElements(that) + } + + override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { + var i = 0 + var j = start + val end = length min len min (xs.length - start) + while (i < end) { + xs(j) = this(i) + i += 1 + j += 1 + } + } + + + // Overridden methods from Sequence + + override def lengthCompare(len: Int): Int = length - len + + override def segmentLength(p: A => Boolean, from: Int): Int = { + val start = from + val len = length + var i = start + while (i < len && p(this(i))) i += 1 + i - start + } + + private def negLength(n: Int) = if (n == length) -1 else n + + override def indexWhere(p: A => Boolean, from: Int): Int = { + val start = from max 0 + negLength(start + segmentLength(!p(_), start)) + } + + override def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = end + while (i >= 0 && !p(this(i))) i -= 1 + i + } + + override def reverse: Repr = { + val b = newBuilder + b.sizeHint(length) + var i = length + while (0 < i) { + i -= 1 + b += this(i) + } + b.result + } + + override def reverseIterator: Iterator[A] = new Iterator[A] { + private var i = self.length + def hasNext: Boolean = 0 < i + def next: A = + if (0 < i) { + i -= 1 + self(i) + } else Iterator.empty.next + } + + override def startsWith[B](that: Sequence[B], offset: Int): Boolean = that match { + case that: Vector[_] => + var i = offset + var j = 0 + val thisLen = length + val thatLen = that.length + while (i < thisLen && j < thatLen && this(i) == that(j)) { + i += 1 + j += 1 + } + j == thatLen + case _ => + var i = offset + val thisLen = length + val thatElems = that.iterator + while (i < thisLen && thatElems.hasNext) { + if (this(i) != thatElems.next()) + return false + + i += 1 + } + !thatElems.hasNext + } + + override def endsWith[B](that: Sequence[B]): Boolean = that match { + case that: Vector[_] => + var i = length - 1 + var j = that.length - 1 + + (j <= i) && { + while (j >= 0) { + if (this(i) != that(j)) + return false + i -= 1 + j -= 1 + } + true + } + case _ => + super.endsWith(that) + } + + override def view = new VectorView[A, Repr] { + protected lazy val underlying = self.repr + override def iterator = self.iterator + override def length = self.length + override def apply(idx: Int) = self.apply(idx) + } + + override def view(from: Int, until: Int) = view.slice(from, until) +} + diff --git a/src/library/scala/collection/generic/Addable.scala b/src/library/scala/collection/generic/Addable.scala index d1348ee2ff..5cde44cef1 100644 --- a/src/library/scala/collection/generic/Addable.scala +++ b/src/library/scala/collection/generic/Addable.scala @@ -20,7 +20,7 @@ import scala.collection._ */ trait Addable[A, +This <: Addable[A, This]] { self => - protected def thisCollection: This + protected def repr: This /** Creates a new collection with an additional element, unless the element is already present. * @param elem the element to be added @@ -43,14 +43,14 @@ trait Addable[A, +This <: Addable[A, This]] { self => * * @param elems the traversable object. */ - def ++ (elems: Traversable[A]): This = (thisCollection /: elems) (_ + _) + def ++ (elems: Traversable[A]): This = (repr /: elems) (_ + _) /** Adds a number of elements provided by an iterator * and returns a new collection with the added elements. * * @param iter the iterator */ - def ++ (iter: Iterator[A]): This = (thisCollection /: iter) (_ + _) + def ++ (iter: Iterator[A]): This = (repr /: iter) (_ + _) } diff --git a/src/library/scala/collection/generic/BufferTemplate.scala b/src/library/scala/collection/generic/BufferTemplate.scala index c7522b465a..ee494507bc 100644 --- a/src/library/scala/collection/generic/BufferTemplate.scala +++ b/src/library/scala/collection/generic/BufferTemplate.scala @@ -118,11 +118,11 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] /** Prepends a number of elements provided by an iterable object * via its <code>iterator</code> method. The identity of the - * buffer is returned.(thisCollection /: elems) (_ plus _) + * buffer is returned.(repr /: elems) (_ plus _) * * @param iter the iterable object. */ - def ++:(iter: Traversable[A]): This = { for (x <- iter) x +: this; thisCollection } + def ++:(iter: Traversable[A]): This = { for (x <- iter) x +: this; repr } /** Prepends a number of elements provided by an iterator * The identity of the buffer is returned. @@ -130,7 +130,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] * @param iter the iterator * @return the updated buffer. */ - def ++:(iter: Iterator[A]): This = { for (x <- iter) x +: this; thisCollection } + def ++:(iter: Iterator[A]): This = { for (x <- iter) x +: this; repr } /** Appends elements to this buffer. * @@ -241,7 +241,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] */ @deprecated("Use += instead if you intend to add by side effect to an existing collection.\n"+ "Use `clone() ++=' if you intend to create a new collection.") - override def + (elem: A): This = { +=(elem); thisCollection } + override def + (elem: A): This = { +=(elem); repr } /** Adds two or more elements to this collection and returns * the collection itself. @@ -254,7 +254,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() ++=' if you intend to create a new collection.") override def + (elem1: A, elem2: A, elems: A*): This = { this += elem1 += elem2 ++= elems - thisCollection + repr } /** Adds a number of elements provided by a traversable object and returns @@ -266,7 +266,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() ++=` if you intend to create a new collection.") override def ++(iter: Traversable[A]): This = { for (elem <- iter) +=(elem) - thisCollection + repr } /** Adds a number of elements provided by an iterator and returns @@ -278,7 +278,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() ++=` if you intend to create a new collection.") override def ++ (iter: Iterator[A]): This = { for (elem <- iter) +=(elem) - thisCollection + repr } /** Removes a single element from this collection and returns @@ -288,7 +288,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] */ @deprecated("Use -= instead if you intend to remove by side effect from an existing collection.\n"+ "Use `clone() -=` if you intend to create a new collection.") - override def -(elem: A): This = { -=(elem); thisCollection } + override def -(elem: A): This = { -=(elem); repr } /** Removes two or more elements from this collection and returns * the collection itself. @@ -301,7 +301,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() -=` if you intend to create a new collection.") override def -(elem1: A, elem2: A, elems: A*): This = { this -= elem1 -= elem2 --= elems - thisCollection + repr } /** Removes a number of elements provided by a Traversable object and returns @@ -313,7 +313,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() --=` if you intend to create a new collection.") override def --(iter: Traversable[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } /** Removes a number of elements provided by an iterator and returns @@ -325,7 +325,7 @@ trait BufferTemplate[A, +This <: BufferTemplate[A, This] with Buffer[A]] "Use `clone() --=` if you intend to create a new collection.") override def --(iter: Iterator[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } } diff --git a/src/library/scala/collection/generic/DoubleLinkedListTemplate.scala b/src/library/scala/collection/generic/DoubleLinkedListTemplate.scala index 6bad44054d..082cce4eae 100644 --- a/src/library/scala/collection/generic/DoubleLinkedListTemplate.scala +++ b/src/library/scala/collection/generic/DoubleLinkedListTemplate.scala @@ -27,14 +27,14 @@ trait DoubleLinkedListTemplate[A, This >: Null <: LinearSequence[A] with DoubleL override def append(that: This): Unit = if (next eq null) { next = that - if (that ne null) that.prev = thisCollection + if (that ne null) that.prev = repr } else next.append(that) override def insert(that: This): Unit = if (that ne null) { that.append(next) next = that - that.prev = thisCollection + that.prev = repr } def remove() { diff --git a/src/library/scala/collection/generic/ImmutableMapTemplate.scala b/src/library/scala/collection/generic/ImmutableMapTemplate.scala index c754de541f..70a55438d9 100644 --- a/src/library/scala/collection/generic/ImmutableMapTemplate.scala +++ b/src/library/scala/collection/generic/ImmutableMapTemplate.scala @@ -71,7 +71,7 @@ self => * @param elems the traversable object. */ override def ++[B1 >: B](elems: Traversable[(A, B1)]): immutable.Map[A, B1] = - ((thisCollection: immutable.Map[A, B1]) /: elems) (_ + _) + ((repr: immutable.Map[A, B1]) /: elems) (_ + _) /** Adds a number of elements provided by an iterator * and returns a new collection with the added elements. @@ -79,7 +79,7 @@ self => * @param iter the iterator */ override def ++[B1 >: B] (iter: Iterator[(A, B1)]): immutable.Map[A, B1] = - ((thisCollection: immutable.Map[A, B1]) /: iter) (_ + _) + ((repr: immutable.Map[A, B1]) /: iter) (_ + _) /** This function transforms all the values of mappings contained * in this map with function <code>f</code>. @@ -88,7 +88,7 @@ self => * @return the updated map */ def transform[C, That](f: (A, B) => C)(implicit bf: BuilderFactory[(A, C), That, This]): That = { - val b = bf(thisCollection) + val b = bf(repr) for ((key, value) <- this) b += ((key, f(key, value))) b.result } @@ -104,7 +104,7 @@ self => * with a negated predicate instead. */ override def filterNot(p: ((A, B)) => Boolean): This = { - var res: This = thisCollection + var res: This = repr for (kv <- this) if (p(kv)) res = (res - kv._1).asInstanceOf[This] // !!! concrete overrides abstract problem res diff --git a/src/library/scala/collection/generic/IterableTemplate.scala b/src/library/scala/collection/generic/IterableTemplate.scala index 35210e036d..493a16e03d 100644 --- a/src/library/scala/collection/generic/IterableTemplate.scala +++ b/src/library/scala/collection/generic/IterableTemplate.scala @@ -41,252 +41,6 @@ import scala.util.control.Breaks._ * @author Martin Odersky * @version 2.8 */ -trait IterableTemplate[+A, +This <: IterableTemplate[A, This] with Iterable[A]] extends TraversableTemplate[A, This] { self => - - /** Creates a new iterator over all elements contained in this - * iterable object. - * - * @return the new iterator - */ - def iterator: Iterator[A] - - @deprecated("use `iterator' instead") - def elements = iterator - - /** Apply a function <code>f</code> to all elements of this - * traversable object. - * - * @param f A function that is applied for its side-effect to every element. - * The result (of arbitrary type U) of function `f` is discarded. - * - * @note This method underlies the implementation of most other bulk operations. - * Implementing `foreach` with `iterator` is often suboptimal. - * So `foreach` should be overridden in concrete collection classes if a more - * efficient implementation is available. - */ - def foreach[U](f: A => U): Unit = this.iterator.foreach(f) - - /** Does this iterable contain no elements? - */ - override def isEmpty: Boolean = !this.iterator.hasNext - - /** Combines the elements of this iterable together using the binary - * function <code>f</code>, from right to left, and starting with - * the value <code>z</code>. - * - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this iterable is ordered, or - * the operator is associative and commutative. - * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> - * if the iterable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. - */ - override def foldRight[B](z: B)(op: (A, B) => B): B = - this.iterator.foldRight(z)(op) - - /** Combines the elements of this iterable object together using the binary - * operator <code>op</code>, from right to left - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this iterable is ordered, or - * the operator is associative and commutative. - * @param op The operator to apply - * - * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> - * if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., - * a<sub>n</sub></code>. - * - * @throws Predef.UnsupportedOperationException if the iterator is empty. - */ - override def reduceRight[B >: A](op: (A, B) => B): B = - this.iterator.reduceRight(op) - - /** The iterable itself */ - override def toIterable: Iterable[A] = thisCollection - - /** The first element of this iterable. - * - * @note Might return different results for different runs, unless this iterable is ordered - * @throws Predef.NoSuchElementException if the iterable is empty. - */ - override def head: A = - if (isEmpty) - throw new NoSuchElementException - else - this.iterator.next - - /** Returns the rightmost <code>n</code> elements from this iterable. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def takeRight(n: Int): This = { - val b = newBuilder - val lead = this.iterator drop n - var go = false - for (x <- this) { - if (lead.hasNext) lead.next - else go = true - if (go) b += x - } - b.result - } - - /** Returns the iterable wihtout its rightmost <code>n</code> elements. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this iterable is ordered - */ - def dropRight(n: Int): This = { - val b = newBuilder - val lead = iterator drop n - breakable { - for (x <- this) { - if (!lead.hasNext) break - lead.next - b += x - } - } - b.result - } - - - /** Returns an iterable formed from this iterable and another iterable - * by combining corresponding elements in pairs. - * If one of the two iterables is longer than the other, its remaining elements are ignored. - * @param that The iterable providing the second half of each result pair - */ - def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { - val b = bf(thisCollection) - val these = this.iterator - val those = that.iterator - while (these.hasNext && those.hasNext) - b += ((these.next, those.next)) - b.result - } - - /** Returns a iterable formed from this iterable and the specified iterable - * <code>that</code> by associating each element of the former with - * the element at the same position in the latter. - * - * @param that iterable <code>that</code> may have a different length - * as the self iterable. - * @param thisElem element <code>thisElem</code> is used to fill up the - * resulting iterable if the self iterable is shorter than - * <code>that</code> - * @param thatElem element <code>thatElem</code> is used to fill up the - * resulting iterable if <code>that</code> is shorter than - * the self iterable - * @return <code>Sequence((a<sub>0</sub>,b<sub>0</sub>), ..., - * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), - * ..., {elem,b<sub>m</sub>})</code> - * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip - * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is - * invoked where <code>m > n</code>. - * - */ - def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = { - val b = bf(thisCollection) - val these = this.iterator - val those = that.iterator - while (these.hasNext && those.hasNext) - b += ((these.next, those.next)) - while (these.hasNext) - b += ((these.next, thatElem)) - while (those.hasNext) - b += ((thisElem, those.next)) - b.result - } - - /** Zips this iterable with its indices (startiong from 0). - */ - def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = { - val b = bf(thisCollection) - var i = 0 - for (x <- this) { - b += ((x, i)) - i +=1 - } - b.result - } - - /** Sort the iterable according to the comparison function - * <code><(e1: a, e2: a) => Boolean</code>, - * which should be true iff <code>e1</code> is smaller than - * <code>e2</code>. - * The sort is stable. That is elements that are equal wrt `lt` appear in the - * same order in the sorted sequence as in the original. - * - * @param lt the comparison function - * @return an iterable sorted according to the comparison function - * <code><(e1: a, e2: a) => Boolean</code>. - * @ex <pre> - * List("Steve", "Tom", "John", "Bob") - * .sortWith((e1, e2) => (e1 compareTo e2) < 0) = - * List("Bob", "John", "Steve", "Tom")</pre> - */ - def sortWith(lt: (A, A) => Boolean)(implicit m: ClassManifest[A @uncheckedVariance]): This = { - // !!! can we supply a default argument to m: ClassManifest ? - val arr = toArray - java.util.Arrays.sort(arr, Ordering fromLessThan lt) - - val b = newBuilder - for (x <- arr) b += x - b.result - } - - /** Checks if the other iterable object contains the same elements as this one. - * - * @note will not terminate for infinite-sized iterables. - * @param that the other iterable - * @return true, iff both iterables contain the same elements in the same order. - * @note Might return different results for different runs, unless this iterable is ordered - */ - def sameElements[B >: A](that: Iterable[B]): Boolean = { - val these = this.iterator - val those = that.iterator - while (these.hasNext && those.hasNext) - if (these.next != those.next) - return false - - !these.hasNext && !those.hasNext - } - - /** Returns a stream with all elements in this traversable object. - */ - override def toStream: Stream[A] = iterator.toStream - - /** Creates a view of this iterable @see IterableView - */ - override def view = new IterableView[A, This] { - protected lazy val underlying = self.thisCollection - override def iterator = self.iterator - } - - /** A sub-iterable view starting at index `from` - * and extending up to (but not including) index `until`. - * - * @param from The index of the first element of the slice - * @param until The index of the element following the slice - * @note The difference between `view` and `slice` is that `view` produces - * a view of the current iterable, whereas `slice` produces a new iterable. - * - * @note Might return different results for different runs, unless this iterable is ordered - * @note view(from, to) is equivalent to view.slice(from, to) - */ - override def view(from: Int, until: Int) = view.slice(from, until) - - protected def anyEq(that: Any) = this eq that.asInstanceOf[AnyRef] - - @deprecated("use `head' instead") def first: A = head - - /** <code>None</code> if traversable is empty. */ - @deprecated("use `headOption' instead") def firstOption: Option[A] = headOption - - @deprecated("use `toSequence' instead") def toSeq: Sequence[A] = toSequence - - /** - * returns a projection that can be used to call non-strict <code>filter</code>, - * <code>map</code>, and <code>flatMap</code> methods that build projections - * of the collection. - */ - @deprecated("use `view' instead") def projection = view -} +trait IterableTemplate[+A, +This <: IterableTemplate[A, This] with Iterable[A]] +extends TraversableTemplate[A, This] + with IterableLike[A, This] diff --git a/src/library/scala/collection/generic/IterableView.scala b/src/library/scala/collection/generic/IterableView.scala index 30d3f772ef..387cc78abb 100644 --- a/src/library/scala/collection/generic/IterableView.scala +++ b/src/library/scala/collection/generic/IterableView.scala @@ -19,7 +19,7 @@ import TraversableView.NoBuilder * @author Martin Odersky * @version 2.8 */ -trait IterableView[+A, +Coll <: Iterable[_]] extends IterableViewTemplate[A, Coll, IterableView[A, Coll]] +trait IterableView[+A, +Coll] extends IterableViewTemplate[A, Coll, IterableView[A, Coll]] object IterableView { type Coll = TraversableView[_, C] forSome {type C <: Traversable[_]} diff --git a/src/library/scala/collection/generic/IterableViewTemplate.scala b/src/library/scala/collection/generic/IterableViewTemplate.scala index 327e719be2..2de03c1702 100644 --- a/src/library/scala/collection/generic/IterableViewTemplate.scala +++ b/src/library/scala/collection/generic/IterableViewTemplate.scala @@ -20,7 +20,7 @@ import TraversableView.NoBuilder * @version 2.8 */ trait IterableViewTemplate[+A, - +Coll <: Iterable[_], + +Coll, +This <: IterableView[A, Coll] with IterableViewTemplate[A, Coll, This]] extends Iterable[A] with IterableTemplate[A, This] with TraversableView[A, Coll] with TraversableViewTemplate[A, Coll, This] { self => @@ -71,7 +71,7 @@ extends Iterable[A] with IterableTemplate[A, This] with TraversableView[A, Coll] override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { newZipped(that).asInstanceOf[That] -// was: val b = bf(thisCollection) +// was: val b = bf(repr) // if (b.isInstanceOf[NoBuilder[_]]) newZipped(that).asInstanceOf[That] // else super.zip[A1, B, That](that)(bf) } diff --git a/src/library/scala/collection/generic/LinearSequenceTemplate.scala b/src/library/scala/collection/generic/LinearSequenceTemplate.scala index 1e667f1e10..3eb4ee598b 100644 --- a/src/library/scala/collection/generic/LinearSequenceTemplate.scala +++ b/src/library/scala/collection/generic/LinearSequenceTemplate.scala @@ -27,349 +27,6 @@ import scala.util.control.Breaks._ * @author Matthias Zenger * @version 1.0, 16/07/2003 */ -trait LinearSequenceTemplate[+A, +This <: LinearSequenceTemplate[A, This] with LinearSequence[A]] extends SequenceTemplate[A, This] { self => - - /** Abstract method to be implemented in a subclass */ - def isEmpty: Boolean - - /** Abstract method to be implemented in a subclass */ - def head: A - - /** Abstract method to be implemented in a subclass */ - def tail: This - - /** Returns the number of elements in the linear sequence. - */ - def length: Int = { - var these = self - var len = 0 - while (!these.isEmpty) { - len += 1 - these = these.tail - } - len - } - - /** Returns the <code>n</code>-th element of this linear sequence. The first element - * (head of the linear sequence) is at position 0. - * - * @param n index of the element to return - * @return the element at position <code>n</code> in this linear sequence. - * @throws Predef.NoSuchElementException if the linear sequence is too short. - */ - def apply(n: Int): A = drop(n).head - - /** Returns the elements in the sequence as an iterator - */ - override def iterator: Iterator[A] = new Iterator[A] { - var these = self - def hasNext: Boolean = !these.isEmpty - def next: A = - if (hasNext) { - val result = these.head; these = these.tail; result - } else Iterator.empty.next - override def toList: List[A] = these.toList - } - - /** Apply the given function <code>f</code> to each element of this linear sequence - * (while respecting the order of the elements). - * - * @param f the treatment to apply to each element. - */ - override def foreach[B](f: A => B) { - var these = this - while (!these.isEmpty) { - f(these.head) - these = these.tail - } - } - - /** Tests if the predicate <code>p</code> is satisfied by all elements - * in this list. - * - * @param p the test predicate. - * @return <code>true</code> iff all elements of this list satisfy the - * predicate <code>p</code>. - */ - override def forall(p: A => Boolean): Boolean = { - var these = this - while (!these.isEmpty) { - if (!p(these.head)) return false - these = these.tail - } - true - } - - /** Tests the existence in this list of an element that satisfies the - * predicate <code>p</code>. - * - * @param p the test predicate. - * @return <code>true</code> iff there exists an element in this list that - * satisfies the predicate <code>p</code>. - */ - override def exists(p: A => Boolean): Boolean = { - var these = this - while (!these.isEmpty) { - if (p(these.head)) return true - these = these.tail - } - false - } - - /** Count the number of elements in the iterable which satisfy a predicate. - * - * @param p the predicate for which to count - * @return the number of elements satisfying the predicate <code>p</code>. - */ - override def count(p: A => Boolean): Int = { - var these = this - var cnt = 0 - while (!these.isEmpty) { - if (p(these.head)) cnt += 1 - these = these.tail - } - cnt - } - - /** Find and return the first element of the list satisfying a - * predicate, if any. - * - * @param p the predicate - * @return the first element in the list satisfying <code>p</code>, - * or <code>None</code> if none exists. - */ - override def find(p: A => Boolean): Option[A] = { - var these = this - while (!these.isEmpty) { - if (p(these.head)) return Some(these.head) - these = these.tail - } - None - } - - /** Combines the elements of this list together using the binary - * function <code>f</code>, from left to right, and starting with - * the value <code>z</code>. - * - * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), - * a<sub>n</sub>)</code> if the list is - * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. - */ - override def foldLeft[B](z: B)(f: (B, A) => B): B = { - var acc = z - var these = this - while (!these.isEmpty) { - acc = f(acc, these.head) - these = these.tail - } - acc - } - - /** Combines the elements of this list together using the binary - * function <code>f</code>, from right to left, and starting with - * the value <code>z</code>. - * - * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> - * if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. - */ - override def foldRight[B](z: B)(f: (A, B) => B): B = - if (this.isEmpty) z - else f(head, tail.foldRight(z)(f)) - - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from left to right. - * - * @param op The operator to apply - * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> - if the list has elements - * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. - * @throws Predef.UnsupportedOperationException if the list is empty. - */ - override def reduceLeft[B >: A](f: (B, A) => B): B = - if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") - else tail.foldLeft[B](head)(f) - - /** Combines the elements of this iterable object together using the binary - * operator <code>op</code>, from right to left. - * - * @note Will not terminate for infinite-sized collections. - * @param op The operator to apply - * - * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> - * if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., - * a<sub>n</sub></code>. - * - * @throws Predef.UnsupportedOperationException if the iterator is empty. - */ - override def reduceRight[B >: A](op: (A, B) => B): B = - if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight") - else if (tail.isEmpty) head - else op(head, tail.reduceRight(op)) - - /** The last element of this linear sequence. - * - * @throws Predef.NoSuchElementException if the linear sequence is empty. - */ - override def last: A = { - if (isEmpty) throw new NoSuchElementException - var these = this - var nx = these.tail - while (!nx.isEmpty) { - these = nx - nx = nx.tail - } - these.head - } - - override def take(n: Int): This = { - val b = newBuilder - var i = 0 - var these = this - while (!these.isEmpty && i < n) { - i += 1 - b += these.head - these = these.tail - } - b.result - } - - override def drop(n: Int): This = { - var these: This = thisCollection - var count = n - while (!these.isEmpty && count > 0) { - these = these.tail - count -= 1 - } - these - } - - /** Returns the rightmost <code>n</code> elements from this iterable. - * @param n the number of elements to take - */ - override def dropRight(n: Int): This = { - val b = newBuilder - var these = this - var lead = this drop n - while (!lead.isEmpty) { - b += these.head - these = these.tail - lead = lead.tail - } - b.result - } - - /** Returns a pair consisting of the longest prefix of the linear sequence whose - * elements all satisfy the given predicate, and the rest of the linear sequence. - * - * @param p the test predicate - */ - override def span(p: A => Boolean): (This, This) = { - var these: This = thisCollection - val b = newBuilder - while (!these.isEmpty && p(these.head)) { - b += these.head - these = these.tail - } - (b.result, these) - } - - /** Returns true iff the other linear sequence contains the same elements as this one. - * - * @note will not terminate for two infinite-sized linear sequences. - * @param that the other linear sequence - */ - override def sameElements[B >: A](that: Iterable[B]): Boolean = that match { - case that1: LinearSequence[_] => - // !!! todo: do the LinearSequence methods need to assume null might be - // used to indicate termination or not? The fact that null is checked for - // here would seem to indicate "yes", but the comment in LinkedListTemplate is - // !!! todo: integrate with LinearSequence, need to drop null then. - // which contradicts the need for null checking here in two different ways: - // 1) LinkedList does not currently inherit from LinearSequenceTemplate - // 2) According to that comment, if it does it will stop using null - // (but what is the alternative?) - def isEmpty(xs: LinearSequence[_]) = xs == null || xs.isEmpty - var these = thisCollection - var those = that1 - - while (!isEmpty(these) && !isEmpty(those) && these.head == those.head) { - these = these.tail - those = those.tail - } - isEmpty(these) && isEmpty(those) - case _ => super.sameElements(that) - } - - // Overridden methods from Sequence - - /** Result of comparing <code>length</code> with operand <code>len</code>. - * returns <code>x</code> where - * <code>x < 0</code> iff <code>this.length < len</code> - * <code>x == 0</code> iff <code>this.length == len</code> - * <code>x > 0</code> iff <code>this.length > len</code>. - */ - override def lengthCompare(len: Int): Int = { - var i = 0 - var these = self - while (!these.isEmpty && i <= len) { - i += 1 - these = these.tail - } - i - len - } - - /** Is this partial function defined for the index <code>x</code>? - */ - override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) > 0 - - /** Returns length of longest segment starting from a start index `from` - * such that every element of the segment satisfies predicate `p`. - * @note may not terminate for infinite-sized collections. - * @param p the predicate - * @param from the start index - */ - override def segmentLength(p: A => Boolean, from: Int): Int = { - var i = 0 - var these = this drop from - while (!these.isEmpty && p(these.head)) { - i += 1 - these = these.tail - } - i - } - - /** Returns index of the first element starting from a start index - * satisying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized linear sequences. - * @param p the predicate - * @param from the start index - */ - override def indexWhere(p: A => Boolean, from: Int): Int = { - var i = from - var these = this drop from - while (!these.isEmpty && !p(these.head)) { - i += 1 - these = these.tail - } - if (these.isEmpty) -1 else i - } - - /** Returns index of the last element satisying a predicate, or -1, if none exists. - * - * @param p the predicate - * @return the index of the last element satisfying <code>p</code>, - * or -1 if such an element does not exist - */ - override def lastIndexWhere(p: A => Boolean, end: Int): Int = { - var i = 0 - var these = this - var last = -1 - while (!these.isEmpty && i <= end) { - if (p(these.head)) last = i - these = these.tail - i += 1 - } - last - } +trait LinearSequenceTemplate[+A, +This <: LinearSequenceTemplate[A, This] with LinearSequence[A]] extends LinearSequenceLike[A, This] { + self: This => } diff --git a/src/library/scala/collection/generic/MapTemplate.scala b/src/library/scala/collection/generic/MapTemplate.scala index 9d441028d7..2bd15ee315 100644 --- a/src/library/scala/collection/generic/MapTemplate.scala +++ b/src/library/scala/collection/generic/MapTemplate.scala @@ -238,7 +238,7 @@ self => * @param elems the traversable object. */ def ++[B1 >: B](elems: Traversable[(A, B1)]): Map[A, B1] = - ((thisCollection: Map[A, B1]) /: elems) (_ + _) + ((repr: Map[A, B1]) /: elems) (_ + _) /** Adds a number of elements provided by an iterator * and returns a new collection with the added elements. @@ -246,7 +246,7 @@ self => * @param iter the iterator */ def ++[B1 >: B] (iter: Iterator[(A, B1)]): Map[A, B1] = - ((thisCollection: Map[A, B1]) /: iter) (_ + _) + ((repr: Map[A, B1]) /: iter) (_ + _) /** Creates a string representation for this map. * @@ -256,6 +256,7 @@ self => this.iterator.map { case (k, v) => k+" -> "+v }.addString(b, start, sep, end) /** Defines the prefix of this object's <code>toString</code> representation. + * !!! todo: remove stringPrefix overrides where possible */ override def stringPrefix: String = "Map" @@ -264,7 +265,6 @@ self => override def toString = super[IterableTemplate].toString override def hashCode() = this map (_.hashCode) sum - override def canEqualCollection(that: Any) = that.isInstanceOf[Map[_, _]] /** Compares two maps structurally; i.e. checks if all mappings * contained in this map are also contained in the other map, @@ -274,10 +274,23 @@ self => * @return <code>true</code> iff both maps contain exactly the * same mappings. */ - override def equals(that: Any): Boolean = - anyEq(that) || (cond(that) { - case x: Map[A, _] if x.canEqualCollection(this) && size == x.size => - try this forall { case (k, v) => x.get(k.asInstanceOf[A]) == Some(v) } - catch { case ex: ClassCastException => false } - }) + override def equals(that: Any): Boolean = that match { + case that: Map[b, _] => + (this eq that) || + /*(that canEqual this) && !!!*/ + (this.size == that.size) && { + try { + this forall { + case (k, v) => that.get(k.asInstanceOf[b]) match { + case Some(`v`) => true + case _ => false + } + } + } catch { + case ex: ClassCastException => + println("calss cast "); false + }} + case _ => + false + } } diff --git a/src/library/scala/collection/generic/MutableMapTemplate.scala b/src/library/scala/collection/generic/MutableMapTemplate.scala index baf5c8b163..1a575a16e7 100644 --- a/src/library/scala/collection/generic/MutableMapTemplate.scala +++ b/src/library/scala/collection/generic/MutableMapTemplate.scala @@ -173,7 +173,7 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta @deprecated("This operation will create a new map in the future. To add elements as a side\n"+ "effect to an existing map and return that map itself, use -=. If you do want\n"+ "to create a fresh map, you can use `clone() -=` to avoid a @deprecated warning.") - override def -(key: A): This = { -=(key); thisCollection } + override def -(key: A): This = { -=(key); repr } /** If given key is defined in this map, remove it and return associated value as an Option. * If key is not present return None. @@ -221,10 +221,10 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta } override def clone(): This = - empty ++= thisCollection + empty ++= repr /** The result when this map is used as a builder */ - def result: This = thisCollection + def result: This = repr /** Removes two or more elements from this collection and returns * the collection itself. @@ -237,7 +237,7 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta "Use `clone() -=' if you intend to create a new collection.") override def -(elem1: A, elem2: A, elems: A*): This = { this -= elem1 -= elem2 --= elems - thisCollection + repr } /** Removes a number of elements provided by a Traversable object and returns @@ -249,7 +249,7 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta "Use `clone() --=' if you intend to create a new collection.") override def --(iter: Traversable[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } @@ -262,6 +262,6 @@ trait MutableMapTemplate[A, B, +This <: MutableMapTemplate[A, B, This] with muta "Use `clone() --=' if you intend to create a new collection.") override def --(iter: Iterator[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } } diff --git a/src/library/scala/collection/generic/MutableSetTemplate.scala b/src/library/scala/collection/generic/MutableSetTemplate.scala index c44d06fbd7..7a1aa9c974 100644 --- a/src/library/scala/collection/generic/MutableSetTemplate.scala +++ b/src/library/scala/collection/generic/MutableSetTemplate.scala @@ -103,9 +103,9 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se */ def clear() { foreach(-=) } - override def clone(): mutable.Set[A] = empty ++= thisCollection + override def clone(): mutable.Set[A] = empty ++= repr - def result: This = thisCollection + def result: This = repr /** Adds a single element to this collection and returns * the collection itself. @@ -114,7 +114,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se */ @deprecated("Use += instead if you intend to add by side effect to an existing collection.\n"+ "Use `clone() +=' if you intend to create a new collection.") - override def + (elem: A): This = { +=(elem); thisCollection } + override def + (elem: A): This = { +=(elem); repr } /** Adds two or more elements to this collection and returns * the collection itself. @@ -127,7 +127,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() +=' if you intend to create a new collection.") override def + (elem1: A, elem2: A, elems: A*): This = { this += elem1 += elem2 ++= elems - thisCollection + repr } /** Adds a number of elements provided by a traversable object and returns @@ -139,7 +139,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() ++=' if you intend to create a new collection.") override def ++(iter: Traversable[A]): This = { for (elem <- iter) +=(elem) - thisCollection + repr } @@ -152,7 +152,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() ++=' if you intend to create a new collection.") override def ++ (iter: Iterator[A]): This = { for (elem <- iter) +=(elem) - thisCollection + repr } /** Removes a single element from this collection and returns @@ -162,7 +162,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se */ @deprecated("Use -= instead if you intend to remove by side effect from an existing collection.\n"+ "Use `clone() -=' if you intend to create a new collection.") - override def -(elem: A): This = { -=(elem); thisCollection } + override def -(elem: A): This = { -=(elem); repr } /** Removes two or more elements from this collection and returns * the collection itself. @@ -175,7 +175,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() -=' if you intend to create a new collection.") override def -(elem1: A, elem2: A, elems: A*): This = { this -= elem1 -= elem2 --= elems - thisCollection + repr } /** Removes a number of elements provided by a Traversable object and returns @@ -187,7 +187,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() --=' if you intend to create a new collection.") override def --(iter: Traversable[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } /** Removes a number of elements provided by an iterator and returns @@ -199,7 +199,7 @@ trait MutableSetTemplate[A, +This <: MutableSetTemplate[A, This] with mutable.Se "Use `clone() --=' if you intend to create a new collection.") override def --(iter: Iterator[A]): This = { for (elem <- iter) -=(elem) - thisCollection + repr } /** Send a message to this scriptable object. diff --git a/src/library/scala/collection/generic/MutableVectorTemplate.scala b/src/library/scala/collection/generic/MutableVectorTemplate.scala index 4cb3856464..c276d3531d 100644 --- a/src/library/scala/collection/generic/MutableVectorTemplate.scala +++ b/src/library/scala/collection/generic/MutableVectorTemplate.scala @@ -22,7 +22,7 @@ trait MutableVectorTemplate[A, +This <: MutableVectorTemplate[A, This] with muta /** Creates a view of this iterable @see Iterable.View */ override def view = new MutableVectorView[A, This] { - protected lazy val underlying = self.thisCollection + protected lazy val underlying = self.repr override def iterator = self.iterator override def length = self.length override def apply(idx: Int) = self.apply(idx) diff --git a/src/library/scala/collection/generic/MutableVectorView.scala b/src/library/scala/collection/generic/MutableVectorView.scala index 604d18ea98..38c7319880 100644 --- a/src/library/scala/collection/generic/MutableVectorView.scala +++ b/src/library/scala/collection/generic/MutableVectorView.scala @@ -19,7 +19,7 @@ import TraversableView.NoBuilder * @author Martin Odersky * @version 2.8 */ -trait MutableVectorView[A, +Coll <: mutable.Vector[_]] extends MutableVectorViewTemplate[A, Coll, MutableVectorView[A, Coll]] +trait MutableVectorView[A, +Coll] extends MutableVectorViewTemplate[A, Coll, MutableVectorView[A, Coll]] object MutableVectorView { type Coll = TraversableView[_, C] forSome {type C <: Traversable[_]} diff --git a/src/library/scala/collection/generic/MutableVectorViewTemplate.scala b/src/library/scala/collection/generic/MutableVectorViewTemplate.scala index 61531ed96b..e4d37c830a 100644 --- a/src/library/scala/collection/generic/MutableVectorViewTemplate.scala +++ b/src/library/scala/collection/generic/MutableVectorViewTemplate.scala @@ -20,7 +20,7 @@ import TraversableView.NoBuilder * @version 2.8 */ trait MutableVectorViewTemplate[A, - +Coll <: mutable.Vector[_], + +Coll, +This <: MutableVectorView[A, Coll] with MutableVectorViewTemplate[A, Coll, This]] extends mutable.Vector[A] with MutableVectorTemplate[A, This] with VectorView[A, Coll] with VectorViewTemplate[A, Coll, This] { self => diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index 9b919375fe..df51449528 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -16,7 +16,6 @@ import mutable.{ListBuffer, HashMap} // import immutable.{List, Nil, ::} import generic._ -import PartialFunction._ /** Class <code>Sequence[A]</code> represents sequences of elements * of type <code>A</code>. @@ -30,462 +29,6 @@ import PartialFunction._ * @author Matthias Zenger * @version 1.0, 16/07/2003 */ -trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] extends IterableTemplate[A, This] { self => - - import Traversable.breaks._ - - /** Returns the length of the sequence. - */ - def length: Int - - /** Returns the elements at position `idx` - */ - def apply(idx: Int): A - - /** Result of comparing <code>length</code> with operand <code>len</code>. - * returns <code>x</code> where - * <code>x < 0</code> iff <code>this.length < len</code> - * <code>x == 0</code> iff <code>this.length == len</code> - * <code>x > 0</code> iff <code>this.length > len</code>. - * - * The method as implemented here does not call length directly; its running time - * is O(length min len) instead of O(length). The method should be overwritten - * if computing length is cheap. - */ - def lengthCompare(len: Int): Int = { - var i = 0 - breakable { - for (_ <- this) { - i += 1 - if (i > len) break - } - } - i - len - } - - /** Should always be <code>length</code> */ - override def size = length - - /** Is this partial function defined for the index <code>x</code>? - */ - def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) - - /** Returns length of longest segment starting from a start index `from` - * such that every element of the segment satisfies predicate `p`. - * @note may not terminate for infinite-sized collections. - * @param p the predicate - * @param from the start index - */ - def segmentLength(p: A => Boolean, from: Int): Int = { - var result = 0 - var i = 0 - breakable { - for (x <- this) { - if (i >= from && !p(x)) { result = i - from; break } - else i += 1 - } - } - result - } - - /** Returns length of longest prefix of this seqence - * such that every element of the prefix satisfies predicate `p`. - * @note may not terminate for infinite-sized collections. - * @param p the predicate - */ - def prefixLength(p: A => Boolean) = segmentLength(p, 0) - - /** Returns index of the first element satisfying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param p the predicate - */ - def indexWhere(p: A => Boolean): Int = indexWhere(p, 0) - - /** Returns index of the first element starting from a start index - * satisying a predicate, or -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param p the predicate - * @param from the start index - */ - def indexWhere(p: A => Boolean, from: Int): Int = { - var result = -1 - var i = from - breakable { - for (x <- this) { - if (i >= from && p(x)) { result = i; break } - else i += 1 - } - } - result - } - - /** Returns index of the first element satisying a predicate, or -1. */ - @deprecated("Use `indexWhere' instead") - def findIndexOf(p: A => Boolean): Int = indexWhere(p) - - /** Returns the index of the first occurence of the specified - * object in this iterable object. - * - * @note may not terminate for infinite-sized collections. - * @param elem element to search for. - * @return the index in this sequence of the first occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ - def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) - - /** Returns the index of the first occurence of the specified - * object in this iterable object, starting from a start index, or - * -1, if none exists. - * - * @note may not terminate for infinite-sized collections. - * @param elem element to search for. - */ - def indexOf[B >: A](elem: B, from: Int): Int = indexWhere(elem ==, from) - - /** Returns the index of the last occurence of the specified element - * in this sequence, or -1 if the sequence does not contain this element. - * - * @param elem element to search for. - * @return the index in this sequence of the last occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ - def lastIndexOf[B >: A](elem: B): Int = lastIndexWhere(elem ==) - - /** Returns the index of the last - * occurence of the specified element in this sequence - * before or at a given end index, - * or -1 if the sequence does not contain this element. - * - * @param elem element to search for. - * @param end the end index - */ - def lastIndexOf[B >: A](elem: B, end: Int): Int = lastIndexWhere(elem ==, end) - - /** Returns index of the last element satisying a predicate, or -1, if none exists. - * - * @param p the predicate - * @return the index of the last element satisfying <code>p</code>, - * or -1 if such an element does not exist - */ - def lastIndexWhere(p: A => Boolean): Int = lastIndexWhere(p, length - 1) - - /** Returns index of the last element not exceeding a given end index - * and satisying a predicate, or -1 if none exists. - * - * @param end the end index - * @param p the predicate - */ - def lastIndexWhere(p: A => Boolean, end: Int): Int = { - var i = length - 1 - val it = reverseIterator - while (it.hasNext && { val elem = it.next; (i > end || !p(elem)) }) i -= 1 - i - } - - /** A sequence of type <code>C</code> consisting of all elements of - * this sequence in reverse order. - * @note the operation is implemented by building a new sequence - * from <code>this(length - 1), ..., this(0)</code> - * If random access is inefficient for the given sequence implementation, - * this operation should be overridden. - */ - def reverse: This = { - var xs: List[A] = List() - for (x <- this) - xs = x :: xs - val b = newBuilder - for (x <- xs) - b += x - b.result - } - - /** The elements of this sequence in reversed order - */ - def reverseIterator: Iterator[A] = reverse.iterator - - @deprecated("use `reverseIterator' instead") - def reversedElements = reverseIterator - - /** - * Checks whether the argument sequence is contained at the - * specified index within the receiver object. - * - * If the both the receiver object, <code>this</code> and - * the argument, <code>that</code> are infinite sequences - * this method may not terminate. - * - * @return true if <code>that</code> is contained in - * <code>this</code>, at the specified index, otherwise false - * - * @see String.startsWith - */ - def startsWith[B](that: Sequence[B], offset: Int): Boolean = { - val i = this.iterator drop offset - val j = that.iterator - while (j.hasNext && i.hasNext) - if (i.next != j.next) - return false - - !j.hasNext - } - - /** - * Check whether the receiver object starts with the argument sequence. - * - * @return true if <code>that</code> is a prefix of <code>this</code>, - * otherwise false - */ - def startsWith[B](that: Sequence[B]): Boolean = startsWith(that, 0) - - /** @return true if this sequence end with that sequence - * @see String.endsWith - */ - def endsWith[B](that: Sequence[B]): Boolean = { - val i = this.iterator.drop(length - that.length) - val j = that.iterator - while (i.hasNext && j.hasNext) - if (i.next != j.next) - return false - - !j.hasNext - } - - /** @return -1 if <code>that</code> not contained in this, otherwise the - * first index where <code>that</code> is contained. - */ - def indexOfSeq[B >: A](that: Sequence[B]): Int = indexOfSeq(that, 0) - - def indexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = - if (thisCollection.hasDefiniteSize && that.hasDefiniteSize) - KMP.indexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) - else { - var i = fromIndex - var s: Sequence[A] = thisCollection drop i - while (!s.isEmpty) { - if (s startsWith that) - return i - - i += 1 - s = s.tail - } - -1 - } - - /** @return -1 if <code>that</code> not contained in this, otherwise the - * last index where <code>that</code> is contained. - * @note may not terminate for infinite-sized collections. - */ - def lastIndexOfSeq[B >: A](that: Sequence[B]): Int = lastIndexOfSeq(that, that.length) - - // since there's no way to find the last index in an infinite sequence, - // we just document it may not terminate and assume it will. - def lastIndexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = - KMP.lastIndexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) - - /** Tests if the given value <code>elem</code> is a member of this - * sequence. - * - * @param elem element whose membership has to be tested. - * @return <code>true</code> iff there is an element of this sequence - * which is equal (w.r.t. <code>==</code>) to <code>elem</code>. - */ - def contains(elem: Any): Boolean = exists (_ == elem) - - /** <p> - * Computes the multiset union of this sequence and the given sequence - * <code>that</code>. For example: - * </p><pre> - * <b>val</b> xs = List(1, 1, 2) - * <b>val</b> ys = List(1, 2, 2, 3) - * println(xs union ys) // prints "List(1, 1, 2, 1, 2, 2, 3)" - * println(ys union xs) // prints "List(1, 2, 2, 3, 1, 1, 2)" - * </pre> - * - * @param that the sequence of elements to add to the sequence. - * @return a sequence containing the elements of this - * sequence and those of the given sequence <code>that</code>. - */ - def union[B >: A, That](that: Sequence[B])(implicit bf: BuilderFactory[B, That, This]): That = - thisCollection ++ that - - /** <p> - * Computes the multiset difference between this sequence and the - * given sequence <code>that</code>. If an element appears more - * than once in both sequences, the difference contains <i>m</i> copies - * of that element, where <i>m</i> is the difference between the - * number of times the element appears in this sequence and the number - * of times it appears in <code>that</code>. For example: - * </p><pre> - * <b>val</b> xs = List(1, 1, 2) - * <b>val</b> ys = List(1, 2, 2, 3) - * println(xs diff ys) // prints "List(1)" - * println(xs -- ys) // prints "List()" - * </pre> - * - * @param that the sequence of elements to remove from this sequence. - * @return the sequence of elements contained only in this sequence plus - * <i>m</i> copies of each element present in both sequences, - * where <i>m</i> is defined as above. - */ - def diff[B >: A, That](that: Sequence[B]): This = { - val occ = occCounts(that) - val b = newBuilder - for (x <- this) - if (occ(x) == 0) b += x - else occ(x) -= 1 - b.result - } - - /** <p> - * Computes the multiset intersection between this sequence and the - * given sequence <code>that</code>; the intersection contains <i>m</i> - * copies of an element contained in both sequences, where <i>m</i> is - * the smaller of the number of times the element appears in this - * sequence or in <code>that</code>. For example: - * </p><pre> - * <b>val</b> xs = List(1, 1, 2) - * <b>val</b> ys = List(3, 2, 2, 1) - * println(xs intersect ys) // prints "List(1, 2)" - * println(ys intersect xs) // prints "List(2, 1)" - * </pre> - * - * @param that the sequence to intersect. - * @return the sequence of elements contained both in this sequence and - * in the given sequence <code>that</code>. - */ - def intersect[B >: A, That](that: Sequence[B]): This = { - val occ = occCounts(that) - val b = newBuilder - for (x <- this) - if (occ(x) > 0) { - b += x - occ(x) -= 1 - } - b.result - } - - 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 - } - - /** Builds a new sequence from this sequence in which any duplicates (wrt to ==) removed. - * Among duplicate elements, only the first one is retained in the result sequence - */ - def removeDuplicates: This = { - val b = newBuilder - var seen = Set[A]() - for (x <- this) { - if (!(seen contains x)) { - b += x - seen = (seen + x) - } - } - b.result - } - - /** A new sequence, consisting of all elements of current sequence - * except that `replaced` elements starting from `from` are replaced - * by `patch`. - */ - def patch[B >: A, That](from: Int, patch: Sequence[B], replaced: Int)(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - val (prefix, rest) = this.splitAt(from) - b ++= prefix - b ++= patch - b ++= rest/*.view*/ drop replaced // !!! todo: make this a view - b.result - } - - /** Returns a new sequence of given length containing the elements of this sequence followed by zero - * or more occurrences of given elements. - */ - def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - b.sizeHint(length max len) - var diff = len - length - b ++= thisCollection - while (diff > 0) { - b += elem - diff -=1 - } - b.result - } - - /** - * Overridden for efficiency. - * - * @return the sequence itself - */ - override def toSequence: Sequence[A] = thisCollection - - /** The range of all indices of this sequence. - */ - def indices: Range = 0 until length - - override def view = new SequenceView[A, This] { - protected lazy val underlying = self.thisCollection - override def iterator = self.iterator - override def length = self.length - override def apply(idx: Int) = self.apply(idx) - } - - override def view(from: Int, until: Int) = view.slice(from, until) - - /** Need to override string, so that it's not the Function1's string that gets mixed in. - */ - override def toString = super[IterableTemplate].toString - - override def hashCode() = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode) - override def canEqualCollection(that: Any) = that.isInstanceOf[Sequence[_]] - override def equals(that: Any): Boolean = - anyEq(that) || (cond(that) { - case x: Sequence[_] if (x canEqualCollection this) => this sameElements x - }) - - /** Returns index of the last element satisying a predicate, or -1. */ - @deprecated("use `lastIndexWhere' instead") - def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) - - /** A sub-sequence starting at index <code>from</code> - * and extending up to the length of the current sequence - * - * @param from The index of the first element of the slice - * @throws IndexOutOfBoundsException if <code>from < 0</code> - */ - @deprecated("use `drop' instead") - def slice(from: Int): Sequence[A] = slice(from, length) - - @deprecated("Should be replaced by <code>(s1, s2) forall { case (x, y) => f(x, y) }</code>") - def equalsWith[B](that: Sequence[B])(f: (A,B) => Boolean): Boolean = { - val i = this.iterator - val j = that.iterator - while (i.hasNext && j.hasNext) - if (!f(i.next, j.next)) - return false - - !i.hasNext && !j.hasNext - } - - /** Is <code>that</code> a slice in this? */ - @deprecated("Should be replaced by <code>indexOfSeq(that) != -1</code>") - def containsSlice[B](that: Sequence[B]): Boolean = indexOfSeq(that) != -1 - - /** - * returns a projection that can be used to call non-strict <code>filter</code>, - * <code>map</code>, and <code>flatMap</code> methods that build projections - * of the collection. - */ - @deprecated("use `view' instead") - override def projection = view -} - +trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] +extends IterableTemplate[A, This] + with SequenceLike[A, This] diff --git a/src/library/scala/collection/generic/SequenceView.scala b/src/library/scala/collection/generic/SequenceView.scala index f3a93914a8..b665ffdc1f 100644 --- a/src/library/scala/collection/generic/SequenceView.scala +++ b/src/library/scala/collection/generic/SequenceView.scala @@ -19,7 +19,7 @@ import TraversableView.NoBuilder * @author Martin Odersky * @version 2.8 */ -trait SequenceView[+A, +Coll <: Sequence[_]] extends SequenceViewTemplate[A, Coll, SequenceView[A, Coll]] +trait SequenceView[+A, +Coll] extends SequenceViewTemplate[A, Coll, SequenceView[A, Coll]] object SequenceView { type Coll = TraversableView[_, C] forSome {type C <: Traversable[_]} diff --git a/src/library/scala/collection/generic/SequenceViewTemplate.scala b/src/library/scala/collection/generic/SequenceViewTemplate.scala index f721072825..547e929aab 100644 --- a/src/library/scala/collection/generic/SequenceViewTemplate.scala +++ b/src/library/scala/collection/generic/SequenceViewTemplate.scala @@ -21,7 +21,7 @@ import TraversableView.NoBuilder * @version 2.8 */ trait SequenceViewTemplate[+A, - +Coll <: Sequence[_], + +Coll, +This <: SequenceView[A, Coll] with SequenceViewTemplate[A, Coll, This]] extends Sequence[A] with SequenceTemplate[A, This] with IterableView[A, Coll] with IterableViewTemplate[A, Coll, This] { self => @@ -142,7 +142,7 @@ trait SequenceViewTemplate[+A, override def patch[B >: A, That](from: Int, patch: Sequence[B], replaced: Int)(implicit bf: BuilderFactory[B, That, This]): That = { newPatched(from, patch, replaced).asInstanceOf[That] -// was: val b = bf(thisCollection) +// was: val b = bf(repr) // if (b.isInstanceOf[NoBuilder[_]]) newPatched(from, patch, replaced).asInstanceOf[That] // else super.patch[B, That](from, patch, replaced)(bf) } diff --git a/src/library/scala/collection/generic/SetTemplate.scala b/src/library/scala/collection/generic/SetTemplate.scala index 9a11283641..f0e735133b 100644 --- a/src/library/scala/collection/generic/SetTemplate.scala +++ b/src/library/scala/collection/generic/SetTemplate.scala @@ -162,9 +162,7 @@ self => */ override def toString = super[IterableTemplate].toString - // override def hashCode() = (this map (_.hashCode)).foldLeft(0)(_ + _) override def hashCode() = this map (_.hashCode) sum - override def canEqualCollection(that: Any) = that.isInstanceOf[Set[_]] /** Compares this set with another object and returns true, iff the * other object is also a set which contains the same elements as @@ -175,10 +173,14 @@ self => * @return <code>true</code> iff this set and the other set * contain the same elements. */ - override def equals(that: Any): Boolean = anyEq(that) || (cond(that) { - case x: Set[A] if (x canEqualCollection this) && size == x.size => - // can we find a safer way to do this? - try this subsetOf x.asInstanceOf[Set[A]] - catch { case ex: ClassCastException => false } - }) + override def equals(that: Any): Boolean = that match { + case that: Set[A] => + (this eq that) || + /*(that canEqual this) &&!!!*/ + (this.size == that.size) && + (try this subsetOf that.asInstanceOf[Set[A]] + catch { case ex: ClassCastException => false }) + case _ => + false + } } diff --git a/src/library/scala/collection/generic/Sorted.scala b/src/library/scala/collection/generic/Sorted.scala index 43d46dcc26..108255612b 100644 --- a/src/library/scala/collection/generic/Sorted.scala +++ b/src/library/scala/collection/generic/Sorted.scala @@ -19,7 +19,7 @@ trait Sorted[K, +This <: Sorted[K, This]]{ def ordering : Ordering[K]; /** The current collection */ - protected def thisCollection: This + protected def repr: This /** return as a projection the set of keys in this collection */ def keySet: SortedSet[K] @@ -74,10 +74,10 @@ trait Sorted[K, +This <: Sorted[K, This]]{ def to(to: K): This = { // tough! val i = keySet.from(to).iterator; - if (!i.hasNext) return thisCollection + if (!i.hasNext) return repr val next = i.next; if (next == to) { - if (!i.hasNext) return thisCollection + if (!i.hasNext) return repr else return until(i.next) } else return until(next) } diff --git a/src/library/scala/collection/generic/SortedSetTemplate.scala b/src/library/scala/collection/generic/SortedSetTemplate.scala index 2a793daca6..ba058b4276 100644 --- a/src/library/scala/collection/generic/SortedSetTemplate.scala +++ b/src/library/scala/collection/generic/SortedSetTemplate.scala @@ -21,7 +21,7 @@ import scala.collection._ trait SortedSetTemplate[A, +This <: SortedSet[A] with SortedSetTemplate[A, This]] extends Sorted[A, This] with SetTemplate[A, This] { self => - override def keySet = thisCollection + override def keySet = repr override def firstKey: A = head override def lastKey: A = last diff --git a/src/library/scala/collection/generic/Subtractable.scala b/src/library/scala/collection/generic/Subtractable.scala index 1ac70c7391..bdaeb72fe2 100644 --- a/src/library/scala/collection/generic/Subtractable.scala +++ b/src/library/scala/collection/generic/Subtractable.scala @@ -19,7 +19,7 @@ import scala.collection._ */ trait Subtractable[A, +This <: Subtractable[A, This]] { self => - protected def thisCollection: This + protected def repr: This /** Returns a new collection that contains all elements of the current collection * except a given element. @@ -43,7 +43,7 @@ trait Subtractable[A, +This <: Subtractable[A, This]] { self => * * @param elems the traversable object containing the elements that do not form part of the new collection. */ - def --(elems: Traversable[A]): This = (thisCollection /: elems) (_ - _) + def --(elems: Traversable[A]): This = (repr /: elems) (_ - _) /** Returns a new collection that contains all elements of the current collection * except the elements provided by an iterator @@ -51,5 +51,5 @@ trait Subtractable[A, +This <: Subtractable[A, This]] { self => * @param elems the iterator containing the elements that do not form part of the new collection * @note same as -- */ - def --(iter: Iterator[A]): This = (thisCollection /: iter) (_ - _) + def --(iter: Iterator[A]): This = (repr /: iter) (_ - _) } diff --git a/src/library/scala/collection/generic/TraversableProxyTemplate.scala b/src/library/scala/collection/generic/TraversableProxyTemplate.scala index 4c6fa5403a..183a74f1c1 100644 --- a/src/library/scala/collection/generic/TraversableProxyTemplate.scala +++ b/src/library/scala/collection/generic/TraversableProxyTemplate.scala @@ -89,7 +89,7 @@ private class TraversableProxyTemplateConfirmation[+A, +This <: TraversableTempl extends TraversableProxyTemplate[A, Traversable[A]] with interfaces.TraversableMethods[A, Traversable[A]] { - def self: This = thisCollection.asInstanceOf[This] + def self: This = repr.asInstanceOf[This] protected[this] def newBuilder = collection.Traversable.newBuilder[A] // : Builder[A, This] } diff --git a/src/library/scala/collection/generic/TraversableTemplate.scala b/src/library/scala/collection/generic/TraversableTemplate.scala index 3f99a17132..4e23e5d6ab 100644 --- a/src/library/scala/collection/generic/TraversableTemplate.scala +++ b/src/library/scala/collection/generic/TraversableTemplate.scala @@ -62,793 +62,6 @@ import annotation.experimental * @author Martin Odersky * @version 2.8 */ -trait TraversableTemplate[+A, +This <: TraversableTemplate[A, This] with Traversable[A]] { -self => +trait TraversableTemplate[+A, +This <: TraversableTemplate[A, This] with Traversable[A]] +extends TraversableLike[A, This] - import Traversable.breaks._ - - /** <p> - * The proper way to do this would be to make <code>self</code> of type - * <code>This</code>. But unfortunately this makes <b><code>this</code></b> - * to be of type <code>Traversable[A]</code>. Since <code>Traversable</code> - * is a subtype of <code>TraversableTemplate</code>, all methods of - * <b><code>this</code></b> are taken from <code>Traversable</code>. In - * particular the <code>newBuilder</code> method is taken from - * <code>Traversable</code>, which means it yields a <code>Traversable[A]</code> - * instead of a <code>This</code>. - * </p> - * <p> - * The right way out of this is to change Scala's member selection rules, - * so that always the most specific type will be selected, no matter - * whether a member is abstract or concrete. I tried to fake this by - * having a method <code>thisTemplate</code> which returns this at the - * <code>Template</code> type. But unfortunately that does not work, - * because we need to call <code>newBuilder</code> on this at the - * <code>Template</code> type (so that we get back a <code>This</code>) - * and <code>newBuilder</code> has to be a <b><code>protected[this]</code></b> - * because of variance.<br/> - * The less appealing alternative is implemented now: Forget the self type - * and introduce a <code>thisCollection</code> which is this seen as an - * instance of <code>This</code>. We should go back to this once we have - * ameliorated Scala's member selection rules. - * </p> - */ - protected def thisCollection: This = this.asInstanceOf[This] - - /** Create a new builder for this collection type. - */ - protected[this] def newBuilder: Builder[A, This] - - /** Apply a function <code>f</code> to all elements of this - * traversable object. - * - * @param f A function that is applied for its side-effect to every element. - * The result (of arbitrary type U) of function `f` is discarded. - * - * @note This method underlies the implementation of most other bulk operations. - * It's important to implement this method in an efficient way. - */ - def foreach[U](f: A => U): Unit - - /** Does this collection contain no elements? - */ - def isEmpty: Boolean = { - var result = true - breakable { - for (x <- this) { - result = false - break - } - } - result - } - - /** Does this collection contain some elements? - */ - def nonEmpty: Boolean = !isEmpty - - /** The number of elements in this collection - */ - def size: Int = { - var result = 0 - for (x <- this) result += 1 - result - } - - /** Returns true if this collection is known to have finite size. - * This is the case if the collection type is strict, or if the - * collection type is non-strict (e.g. it's a Stream), but all - * collection elements have been computed. - * Many methods in this trait will not work on collections of - * infinite sizes. - */ - def hasDefiniteSize = true - - /** Creates a new traversable of type `That` which contains all elements of this traversable - * followed by all elements of another traversable. - * - * @param that The traversable to append - */ - def ++[B >: A, That](that: Traversable[B])(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - b ++= thisCollection - b ++= that - b.result - } - - /** Creates a new traversable of type `That` which contains all elements of this traversable - * followed by all elements of an iterator. - * - * @param that The iterator to append - */ - def ++[B >: A, That](that: Iterator[B])(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - b ++= thisCollection - b ++= that - b.result - } - - /** Returns the traversable that results from applying the given function - * <code>f</code> to each element of this traversable and collecting the results - * in an traversable of type `That`. - * - * @param f function to apply to each element. - */ - def map[B, That](f: A => B)(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - for (x <- this) b += f(x) - b.result - } - - /** Applies the given function <code>f</code> to each element of - * this traversable, then concatenates the results in an traversable of type That. - * - * @param f the function to apply on each element. - */ - def flatMap[B, That](f: A => Traversable[B])(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - for (x <- this) b ++= f(x) - b.result - } - - /** Returns all the elements of this traversable that satisfy the - * predicate <code>p</code>. The order of the elements is preserved. - * @param p the predicate used to filter the traversable. - * @return the elements of this traversable satisfying <code>p</code>. - */ - def filter(p: A => Boolean): This = { - val b = newBuilder - for (x <- this) - if (p(x)) b += x - b.result - } - - /** Returns a traversable with all elements of this traversable which do not satisfy the predicate - * <code>p</code>. - * - * @param p the predicate used to test elements - * @return the traversable without all elements that satisfy <code>p</code> - */ - def filterNot(p: A => Boolean): This = filter(!p(_)) - - /** Returns a new traversable based on the partial function <code>pf</code>, - * containing pf(x) for all the elements which are defined on pf. - * The order of the elements is preserved. - * @param pf the partial function which filters and maps the traversable. - * @return the new traversable. - */ - @experimental - def filterMap[B, That](pf: PartialFunction[Any, B])(implicit bf: BuilderFactory[B, That, This]): That = { - val b = bf(thisCollection) - for (x <- this) if (pf.isDefinedAt(x)) b += pf(x) - b.result - } - - /** Returns a traversable with all elements of this traversable which do not satisfy the predicate - * <code>p</code>. - * - * @param p the predicate used to test elements - * @return the traversable without all elements that satisfy <code>p</code> - */ - @deprecated("use `filterNot' instead") - def remove(p: A => Boolean): This = filterNot(p) - - /** Partitions this traversable in two traversables according to a predicate. - * - * @param p the predicate on which to partition - * @return a pair of traversables: the traversable that satisfies the predicate - * <code>p</code> and the traversable that does not. - * The relative order of the elements in the resulting traversables - * is the same as in the original traversable. - */ - def partition(p: A => Boolean): (This, This) = { - val l, r = newBuilder - for (x <- this) (if (p(x)) l else r) += x - (l.result, r.result) - } - - /** Partition this traversable into a map of traversables - * according to some discriminator function. - * @invariant (xs partition f)(k) = xs filter (x => f(x) == k) - * - * @note This method is not re-implemented by views. This means - * when applied to a view it will always force the view and - * return a new collection. - */ - def groupBy[K](f: A => K): Map[K, This] = { - var m = Map[K, Builder[A, This]]() - for (elem <- this) { - val key = f(elem) - val bldr = m get key match { - case None => val b = newBuilder; m = m updated (key, b); b - case Some(b) => b - } - bldr += elem - } - m mapValues (_.result) - } - - /** Return true iff the given predicate `p` yields true for all elements - * of this traversable. - * - * @note May not terminate for infinite-sized collections. - * @param p the predicate - */ - def forall(p: A => Boolean): Boolean = { - var result = true - breakable { - for (x <- this) - if (!p(x)) { result = false; break } - } - result - } - - /** Return true iff there is an element in this traversable for which the - * given predicate `p` yields true. - * - * @note May not terminate for infinite-sized collections. - * @param p the predicate - */ - def exists(p: A => Boolean): Boolean = { - var result = false - breakable { - for (x <- this) - if (p(x)) { result = true; break } - } - result - } - - /** Count the number of elements in the traversable which satisfy a predicate. - * - * @note Will not terminate for infinite-sized collections. - * @param p the predicate for which to count - * @return the number of elements satisfying the predicate <code>p</code>. - */ - def count(p: A => Boolean): Int = { - var cnt = 0 - for (x <- this) { - if (p(x)) cnt += 1 - } - cnt - } - - /** Find and return the first element of the traversable object satisfying a - * predicate, if any. - * - * @note may not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered. - * @param p the predicate - * @return an option containing the first element in the traversable object - * satisfying <code>p</code>, or <code>None</code> if none exists. - */ - def find(p: A => Boolean): Option[A] = { - var result: Option[A] = None - breakable { - for (x <- this) - if (p(x)) { result = Some(x); break } - } - result - } - - /** Combines the elements of this traversable object together using the binary - * function <code>f</code>, from left to right, and starting with - * the value <code>z</code>. - * - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), - * a<sub>n</sub>)</code> if the traversable is - * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. - */ - def foldLeft[B](z: B)(op: (B, A) => B): B = { - var result = z - for (x <- this) - result = op(result, x) - result - } - - /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of traversable and zero arguments reversed. - * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - */ - def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) - - /** Combines the elements of this traversable together using the binary - * function <code>f</code>, from right to left, and starting with - * the value <code>z</code>. - * - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> - * if the traversable is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. - */ - def foldRight[B](z: B)(op: (A, B) => B): B = { - var elems: List[A] = Nil - for (x <- this) elems = x :: elems - elems.foldLeft(z)((x, y) => op(y, x)) - } - - /** An alias for <code>foldRight</code>. - * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - */ - def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) - - /** Combines the elements of this traversable object together using the binary - * operator <code>op</code>, from left to right - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @param op The operator to apply - * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> - if the traversable object has elements - * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. - * @throws Predef.UnsupportedOperationException if the traversable object is empty. - */ - def reduceLeft[B >: A](op: (B, A) => B): B = { - if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") - var result: B = head - var first = true - for (x <- this) - if (first) first = false - else result = op(result, x) - result - } - - /** Combines the elements of this traversable object together using the binary - * operator <code>op</code>, from left to right - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @param op The operator to apply - * @return If the traversable is non-empty, the result of the operations as an Option, otherwise None. - */ - def reduceLeftOption[B >: A](op: (B, A) => B): Option[B] = { - if (isEmpty) None else Some(reduceLeft(op)) - } - - /** Combines the elements of this traversable object together using the binary - * operator <code>op</code>, from right to left - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @param op The operator to apply - * - * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> - * if the traversable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., - * a<sub>n</sub></code>. - * - * @throws Predef.UnsupportedOperationException if the iterator is empty. - */ - def reduceRight[B >: A](op: (A, B) => B): B = { - if (isEmpty) throw new UnsupportedOperationException("empty.reduceRight") - var elems: List[A] = Nil - for (x <- this) elems = x :: elems - elems.reduceLeft[B]((x, y) => op(y, x)) - } - - /** Combines the elements of this traversable object together using the binary - * operator <code>op</code>, from right to left. - * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this traversable is ordered, or - * the operator is associative and commutative. - * @param op The operator to apply - * @return If the traversable is non-empty, the result of the operations as an Option, otherwise None. - */ - def reduceRightOption[B >: A](op: (A, B) => B): Option[B] = { - if (isEmpty) None else Some(reduceRight(op)) - } - - /** Returns the sum of all elements with respect to the numeric operations in `num` */ - def sum[B >: A](implicit num: Numeric[B]): B = { - var acc = num.zero - for (x <- self) acc = num.plus(acc, x) - acc - } - - /** Returns the product of all elements with respect to the numeric operations in `num` */ - def product[B >: A](implicit num: Numeric[B]): B = { - var acc = num.one - for (x <- self) acc = num.times(acc, x) - acc - } - - /** Returns the minimal element with respect to the given ordering `cmp` */ - def min[B >: A](implicit cmp: Ordering[B]): A = { - require(!self.isEmpty, "<empty>.min") - var acc = self.head - for (x <- self) - if (cmp.lt(x, acc)) acc = x - acc - } - - /** Returns the maximal element with respect to the given ordering `cmp` */ - def max[B >: A](implicit cmp: Ordering[B]): A = { - require(!self.isEmpty, "<empty>.max") - var acc = self.head - for (x <- self) - if (cmp.gt(x, acc)) acc = x - acc - } - - /** The first element of this traversable. - * - * @note Might return different results for different runs, unless this traversable is ordered - * @throws Predef.NoSuchElementException if the traversable is empty. - */ - def head: A = { - var result: () => A = () => throw new NoSuchElementException - breakable { - for (x <- this) { - result = () => x - break - } - } - result() - } - - /** Returns as an option the first element of this traversable - * or <code>None</code> if traversable is empty. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def headOption: Option[A] = if (isEmpty) None else Some(head) - - /** An traversable consisting of all elements of this traversable - * except the first one. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def tail: This = { - require(!self.isEmpty, "<empty>.tail") - drop(1) - } - - /** The last element of this traversable. - * - * @throws Predef.NoSuchElementException if the traversable is empty. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def last: A = { - var lst = head - for (x <- this) - lst = x - lst - } - - /** Returns as an option the last element of this traversable or - * <code>None</code> if traversable is empty. - * - * @return the last element as an option. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def lastOption: Option[A] = if (isEmpty) None else Some(last) - - /** An traversable consisting of all elements of this traversable except the last one. - * @throws Predef.UnsupportedOperationException if the stream is empty. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def init: This = { - if (isEmpty) throw new UnsupportedOperationException("empty.init") - var lst = head - var follow = false - val b = newBuilder - for (x <- this) { - if (follow) b += lst - else follow = true - lst = x - } - b.result - } - - /** Return an traversable consisting only of the first <code>n</code> - * elements of this traversable, or else the whole traversable, if it has less - * than <code>n</code> elements. - * - * @param n the number of elements to take - * @note Might return different results for different runs, unless this traversable is ordered - */ - def take(n: Int): This = { - val b = newBuilder - var i = 0 - breakable { - for (x <- this) { - if (i >= n) break - b += x - i += 1 - } - } - b.result - } - - /** Returns this traversable without its <code>n</code> first elements - * If this traversable has less than <code>n</code> elements, the empty - * traversable is returned. - * - * @param n the number of elements to drop - * @return the new traversable - * @note Might return different results for different runs, unless this traversable is ordered - */ - def drop(n: Int): This = { - val b = newBuilder - var i = 0 - for (x <- this) { - if (i >= n) b += x - i += 1 - } - b.result - } - - /** A sub-traversable starting at index `from` - * and extending up to (but not including) index `until`. - * - * @note c.slice(from, to) is equivalent to (but possibly more efficient than) - * c.drop(from).take(to - from) - * - * @param from The index of the first element of the returned subsequence - * @param until The index of the element following the returned subsequence - * @note Might return different results for different runs, unless this traversable is ordered - */ - def slice(from: Int, until: Int): This = { - val b = newBuilder - var i = 0 - breakable { - for (x <- this) { - if (i >= from) b += x - i += 1 - if (i == until) break - } - } - b.result - } - - /** Returns the longest prefix of this traversable whose elements satisfy - * the predicate <code>p</code>. - * - * @param p the test predicate. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def takeWhile(p: A => Boolean): This = { - val b = newBuilder - breakable { - for (x <- this) { - if (!p(x)) break - b += x - } - } - b.result - } - - /** Returns the longest suffix of this traversable whose first element - * does not satisfy the predicate <code>p</code>. - * - * @param p the test predicate. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def dropWhile(p: A => Boolean): This = { - val b = newBuilder - var go = false - for (x <- this) { - if (!p(x)) go = true - if (go) b += x - } - b.result - } - - /** Returns a pair consisting of the longest prefix of the traversable whose - * elements all satisfy the given predicate, and the rest of the traversable. - * - * @param p the test predicate - * @return a pair consisting of the longest prefix of the traversable whose - * elements all satisfy <code>p</code>, and the rest of the traversable. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def span(p: A => Boolean): (This, This) = { - val l, r = newBuilder - var toLeft = true - for (x <- this) { - toLeft = toLeft && p(x) - (if (toLeft) l else r) += x - } - (l.result, r.result) - } - - /** Split the traversable at a given point and return the two parts thus - * created. - * - * @param n the position at which to split - * @return a pair of traversables composed of the first <code>n</code> - * elements, and the other elements. - * @note Might return different results for different runs, unless this traversable is ordered - */ - def splitAt(n: Int): (This, This) = { - val l, r = newBuilder - var i = 0 - for (x <- this) { - (if (i < n) l else r) += x - i += 1 - } - (l.result, r.result) - } - - /** Copy all elements of this traversable to a given buffer - * @note Will not terminate for infinite-sized collections. - * @param dest The buffer to which elements are copied - */ - def copyToBuffer[B >: A](dest: Buffer[B]) { - for (x <- this) dest += x - } - - /** Fills the given array <code>xs</code> with at most `len` elements of - * this traversable starting at position `start`. - * Copying will stop once either the end of the current traversable is reached or - * `len` elements have been copied or the end of the array is reached. - * - * @note Will not terminate for infinite-sized collections. - * @param xs the array to fill. - * @param start starting index. - * @param len number of elements to copy - */ - def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { - var i = start - val end = (start + len) min xs.length - breakable { - for (x <- this) { - if (i >= end) break - xs(i) = x - i += 1 - } - } - } - - /** Fills the given array <code>xs</code> with the elements of - * this traversable starting at position <code>start</code> - * until either the end of the current traversable or the end of array `xs` is reached. - * - * @note Will not terminate for infinite-sized collections. - * @param xs the array to fill. - * @param start starting index. - * @pre the array must be large enough to hold all elements. - */ - def copyToArray[B >: A](xs: Array[B], start: Int) { - copyToArray(xs, start, xs.length - start) - } - - /** Converts this traversable to a fresh Array containing all elements. - * @note Will not terminate for infinite-sized collections. - */ - def toArray[B >: A : ClassManifest]: Array[B] = { - val result = new Array[B](size) - copyToArray(result, 0) - result - } - - /** Returns a list with all elements of this traversable object. - * @note Will not terminate for infinite-sized collections. - */ - def toList: List[A] = (new ListBuffer[A] ++= thisCollection).toList - - /** Returns an traversable with all elements in this traversable object. - * @note Will not terminate for infinite-sized collections. - */ - def toIterable: Iterable[A] = toStream - - /** Returns a sequence with all elements in this traversable object. - * @note Will not terminate for infinite-sized collections. - */ - def toSequence: Sequence[A] = toList - - /** Returns a vector with all elements in this traversable object. - * @note Will not terminate for infinite-sized collections. - */ - def toVector[B >: A]: mutable.Vector[B] = (new ArrayBuffer[B] ++= thisCollection) - - /** Returns a stream with all elements in this traversable object. - */ - def toStream: Stream[A] = toList.toStream - - /** Returns a set with all unique elements in this traversable object. - */ - @experimental - def toSet[B >: A]: immutable.Set[B] = immutable.Set() ++ thisCollection - - /** Returns a string representation of this traversable object. The resulting string - * begins with the string <code>start</code> and is finished by the string - * <code>end</code>. Inside, the string representations of elements (w.r.t. - * the method <code>toString()</code>) are separated by the string - * <code>sep</code>. - * - * @ex <code>List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> - * @param start starting string. - * @param sep separator string. - * @param end ending string. - * @return a string representation of this traversable object. - */ - def mkString(start: String, sep: String, end: String): String = - addString(new StringBuilder(), start, sep, end).toString - - /** Returns a string representation of this traversable object. The string - * representations of elements (w.r.t. the method <code>toString()</code>) - * are separated by the string <code>sep</code>. - * - * @param sep separator string. - * @return a string representation of this traversable object. - */ - def mkString(sep: String): String = - addString(new StringBuilder(), sep).toString - - /** Returns a string representation of this traversable object. The string - * representations of elements (w.r.t. the method <code>toString()</code>) - * follow each other without any separator string. - */ - def mkString: String = - addString(new StringBuilder()).toString - - /** Write all elements of this traversable into given string builder. - * The written text begins with the string <code>start</code> and is finished by the string - * <code>end</code>. Inside, the string representations of elements (w.r.t. - * the method <code>toString()</code>) are separated by the string - * <code>sep</code>. - */ - def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { - b append start - var first = true - for (x <- this) { - if (first) first = false - else b append sep - b append x - } - b append end - } - - /** Write all elements of this string into given string builder. - * The string representations of elements (w.r.t. the method <code>toString()</code>) - * are separated by the string <code>sep</code>. - */ - def addString(b: StringBuilder, sep: String): StringBuilder = addString(b, "", sep, "") - - /** Write all elements of this string into given string builder without using - * any separator between consecutive elements. - */ - def addString(b: StringBuilder): StringBuilder = addString(b, "") - - override def toString = mkString(stringPrefix + "(", ", ", ")") - - def canEqualCollection(other: Any) = true - - /** Defines the prefix of this object's <code>toString</code> representation. - */ - def stringPrefix : String = { - var string = thisCollection.getClass.getName - val idx1 = string.lastIndexOf('.' : Int) - if (idx1 != -1) string = string.substring(idx1 + 1) - val idx2 = string.indexOf('$') - if (idx2 != -1) string = string.substring(0, idx2) - string - } - - /** Creates a view of this traversable @see TraversableView - */ - def view = new TraversableView[A, This] { - protected lazy val underlying = self.thisCollection - override def foreach[B](f: A => B) = self foreach f - } - - /** A sub-traversable starting at index `from` - * and extending up to (but not including) index `until`. - * - * @param from The index of the first element of the slice - * @param until The index of the element following the slice - * @note The difference between `view` and `slice` is that `view` produces - * a view of the current traversable, whereas `slice` produces a new traversable. - * - * @note Might return different results for different runs, unless this traversable is ordered - * @note view(from, to) is equivalent to view.slice(from, to) - */ - def view(from: Int, until: Int): TraversableView[A, This] = view.slice(from, until) -} diff --git a/src/library/scala/collection/generic/TraversableView.scala b/src/library/scala/collection/generic/TraversableView.scala index 66bfee31cc..b5367f347a 100644 --- a/src/library/scala/collection/generic/TraversableView.scala +++ b/src/library/scala/collection/generic/TraversableView.scala @@ -23,7 +23,7 @@ import TraversableView.NoBuilder * @author Martin Odersky * @version 2.8 */ -trait TraversableView[+A, +Coll <: Traversable[_]] extends TraversableViewTemplate[A, Coll, TraversableView[A, Coll]] +trait TraversableView[+A, +Coll] extends TraversableViewTemplate[A, Coll, TraversableView[A, Coll]] object TraversableView { class NoBuilder[A] extends Builder[A, Nothing] { diff --git a/src/library/scala/collection/generic/TraversableViewTemplate.scala b/src/library/scala/collection/generic/TraversableViewTemplate.scala index 6b8cdbd2ec..347ad60221 100644 --- a/src/library/scala/collection/generic/TraversableViewTemplate.scala +++ b/src/library/scala/collection/generic/TraversableViewTemplate.scala @@ -31,7 +31,7 @@ import TraversableView.NoBuilder * @version 2.8 */ trait TraversableViewTemplate[+A, - +Coll <: Traversable[_], + +Coll, +This <: TraversableView[A, Coll] with TraversableViewTemplate[A, Coll, This]] extends Traversable[A] with TraversableTemplate[A, This] { self => @@ -144,7 +144,7 @@ self => override def ++[B >: A, That](that: Traversable[B])(implicit bf: BuilderFactory[B, That, This]): That = { newAppended(that).asInstanceOf[That] -// was: val b = bf(thisCollection) +// was: val b = bf(repr) // if (b.isInstanceOf[NoBuilder[_]]) newAppended(that).asInstanceOf[That] // else super.++[B, That](that)(bf) } @@ -153,14 +153,14 @@ self => override def map[B, That](f: A => B)(implicit bf: BuilderFactory[B, That, This]): That = { newMapped(f).asInstanceOf[That] -// was: val b = bf(thisCollection) +// was: val b = bf(repr) // if (b.isInstanceOf[NoBuilder[_]]) newMapped(f).asInstanceOf[That] // else super.map[B, That](f)(bf) } override def flatMap[B, That](f: A => Traversable[B])(implicit bf: BuilderFactory[B, That, This]): That = { newFlatMapped(f).asInstanceOf[That] -// was: val b = bf(thisCollection) +// was: val b = bf(repr) // if (b.isInstanceOf[NoBuilder[_]]) newFlatMapped(f).asInstanceOf[That] // else super.flatMap[B, That](f)(bf) } diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index 19e6cfb19c..e80a439c76 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -8,10 +8,8 @@ // $Id$ -package scala.collection.generic - -import scala.collection.{BufferedIterator, Sequence, Vector} -import scala.collection.mutable.ArrayBuffer +package scala.collection +package generic /** Sequences that support O(1) element access and O(1) length computation. * This class does not add any methods to Sequence but overrides several @@ -21,258 +19,4 @@ import scala.collection.mutable.ArrayBuffer * @author Martin Odersky * @version 2.8 */ -trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extends SequenceTemplate[A, This] { self => - - // Overridden methods from IterableTemplate - - /** The iterator returned by the iterator method - */ - @serializable @SerialVersionUID(1756321872811029277L) - protected class Elements(start: Int, end: Int) extends BufferedIterator[A] { - private var i = start - - def hasNext: Boolean = i < end - - def next: A = - if (i < end) { - val x = self(i) - i += 1 - x - } else Iterator.empty.next - - def head = - if (i < end) self(i) else Iterator.empty.next - - /** drop is overridden to enable fast searching in the middle of random access sequences */ - override def drop(n: Int): Iterator[A] = - if (n > 0) new Elements(start + n, end) else this - - /** take is overridden to be symmetric to drop */ - override def take(n: Int): Iterator[A] = - if (n <= 0) Iterator.empty.buffered - else if (start + n < end) new Elements(start, start + n) - else this - } - - override def iterator: Iterator[A] = new Elements(0, length) - - override def isEmpty: Boolean = { length == 0 } - - override def foreach[U](f: A => U): Unit = { - var i = 0 - val len = length - while (i < len) { f(this(i)); i += 1 } - } - - override def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length - override def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length - - override def find(p: A => Boolean): Option[A] = { - val i = prefixLength(!p(_)) - if (i < length) Some(this(i)) else None - } - - private def foldl[B](start: Int, z: B, op: (B, A) => B): B = { - var i = start - val len = length - var result = z - while (i < len) { - result = op(result, this(i)) - i += 1 - } - result - } - - private def foldr[B](start: Int, len: Int, z: B, op: (A, B) => B): B = - if (start == len) z - else op(this(start), foldr(start + 1, len, z, op)) - - override def foldLeft[B](z: B)(op: (B, A) => B): B = - foldl(0, z, op) - override def foldRight[B](z: B)(op: (A, B) => B): B = - foldr(0, length, z, op) - override def reduceLeft[B >: A](op: (B, A) => B): B = - if (length > 0) foldl(1, this(0), op) else super.reduceLeft(op) - override def reduceRight[B >: A](op: (A, B) => B): B = - if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op) - - override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = that match { - case that: Vector[_] => - val b = bf(thisCollection) - var i = 0 - val len = this.length min that.length - b.sizeHint(len) - while (i < len) { - b += ((this(i), that(i).asInstanceOf[B])) - i += 1 - } - b.result - case _ => - super.zip[A1, B, That](that)(bf) - } - - override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = { - val b = bf(thisCollection) - val len = length - b.sizeHint(len) - var i = 0 - while (i < len) { - b += ((this(i), i)) - i += 1 - } - b.result - } - - override def slice(from: Int, until: Int): This = { - var i = from max 0 - val end = until min length - val b = newBuilder - b.sizeHint(end - i) - while (i < end) { - b += this(i) - i += 1 - } - b.result - } - - override def head: A = if (isEmpty) super.head else this(0) - override def tail: This = if (isEmpty) super.tail else slice(1, length) - override def last: A = if (length > 0) this(length - 1) else super.last - override def init: This = if (length > 0) slice(0, length - 1) else super.init - override def take(n: Int): This = slice(0, n) - override def drop(n: Int): This = slice(n, length) - override def takeRight(n: Int): This = slice(length - n, length) - override def dropRight(n: Int): This = slice(0, length - n) - override def splitAt(n: Int): (This, This) = (take(n), drop(n)) - override def takeWhile(p: A => Boolean): This = take(prefixLength(p)) - override def dropWhile(p: A => Boolean): This = drop(prefixLength(p)) - override def span(p: A => Boolean): (This, This) = splitAt(prefixLength(p)) - - override def sameElements[B >: A](that: Iterable[B]): Boolean = that match { - case that: Vector[_] => - val len = length - len == that.length && { - var i = 0 - while (i < len && this(i) == that(i)) i += 1 - i == len - } - case _ => - super.sameElements(that) - } - - override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { - var i = 0 - var j = start - val end = length min len min (xs.length - start) - while (i < end) { - xs(j) = this(i) - i += 1 - j += 1 - } - } - - - // Overridden methods from Sequence - - override def lengthCompare(len: Int): Int = length - len - - override def segmentLength(p: A => Boolean, from: Int): Int = { - val start = from - val len = length - var i = start - while (i < len && p(this(i))) i += 1 - i - start - } - - private def negLength(n: Int) = if (n == length) -1 else n - - override def indexWhere(p: A => Boolean, from: Int): Int = { - val start = from max 0 - negLength(start + segmentLength(!p(_), start)) - } - - override def lastIndexWhere(p: A => Boolean, end: Int): Int = { - var i = end - while (i >= 0 && !p(this(i))) i -= 1 - i - } - - override def reverse: This = { - val b = newBuilder - b.sizeHint(length) - var i = length - while (0 < i) { - i -= 1 - b += this(i) - } - b.result - } - - override def reverseIterator: Iterator[A] = new Iterator[A] { - private var i = self.length - def hasNext: Boolean = 0 < i - def next: A = - if (0 < i) { - i -= 1 - self(i) - } else Iterator.empty.next - } - - override def startsWith[B](that: Sequence[B], offset: Int): Boolean = that match { - case that: Vector[_] => - var i = offset - var j = 0 - val thisLen = length - val thatLen = that.length - while (i < thisLen && j < thatLen && this(i) == that(j)) { - i += 1 - j += 1 - } - j == thatLen - case _ => - var i = offset - val thisLen = length - val thatElems = that.iterator - while (i < thisLen && thatElems.hasNext) { - if (this(i) != thatElems.next()) - return false - - i += 1 - } - !thatElems.hasNext - } - - override def endsWith[B](that: Sequence[B]): Boolean = that match { - case that: Vector[_] => - var i = length - 1 - var j = that.length - 1 - - (j <= i) && { - while (j >= 0) { - if (this(i) != that(j)) - return false - i -= 1 - j -= 1 - } - true - } - case _ => - super.endsWith(that) - } - - // only optimization - override def equals(that: Any): Boolean = that match { - case that: Vector[_] => this.length == that.length && startsWith(that, 0) - case _ => super.equals(that) - } - - override def view = new VectorView[A, This] { - protected lazy val underlying = self.thisCollection - override def iterator = self.iterator - override def length = self.length - override def apply(idx: Int) = self.apply(idx) - } - - override def view(from: Int, until: Int) = view.slice(from, until) -} - +trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extends SequenceTemplate[A, This] with VectorLike[A, This] diff --git a/src/library/scala/collection/generic/VectorView.scala b/src/library/scala/collection/generic/VectorView.scala index 7125af05e6..7eae0c121c 100644 --- a/src/library/scala/collection/generic/VectorView.scala +++ b/src/library/scala/collection/generic/VectorView.scala @@ -20,7 +20,7 @@ import TraversableView.NoBuilder * @author Martin Odersky * @version 2.8 */ -trait VectorView[+A, +Coll <: Vector[_]] extends VectorViewTemplate[A, Coll, VectorView[A, Coll]] +trait VectorView[+A, +Coll] extends VectorViewTemplate[A, Coll, VectorView[A, Coll]] object VectorView { type Coll = TraversableView[_, C] forSome {type C <: Traversable[_]} diff --git a/src/library/scala/collection/generic/VectorViewTemplate.scala b/src/library/scala/collection/generic/VectorViewTemplate.scala index 30fb629739..6e8681ef80 100644 --- a/src/library/scala/collection/generic/VectorViewTemplate.scala +++ b/src/library/scala/collection/generic/VectorViewTemplate.scala @@ -21,7 +21,7 @@ import TraversableView.NoBuilder * @version 2.8 */ trait VectorViewTemplate[+A, - +Coll <: Vector[_], + +Coll, +This <: VectorView[A, Coll] with VectorViewTemplate[A, Coll, This]] extends Vector[A] with VectorTemplate[A, This] with SequenceView[A, Coll] with SequenceViewTemplate[A, Coll, This] { self => diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 502fe6273a..26c8a309a5 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -446,6 +446,7 @@ case object Nil extends List[Nothing] { throw new NoSuchElementException("head of empty list") override def tail: List[Nothing] = throw new NoSuchElementException("tail of empty list") + // Removal of equals method here might lead to an infinite recusion similar to IntMap.equals. override def equals(that: Any) = that match { case that1: Sequence[_] => that1.isEmpty case _ => false diff --git a/src/library/scala/collection/immutable/MapProxy.scala b/src/library/scala/collection/immutable/MapProxy.scala index 1ad7219fc7..933ba3acfc 100644 --- a/src/library/scala/collection/immutable/MapProxy.scala +++ b/src/library/scala/collection/immutable/MapProxy.scala @@ -28,7 +28,7 @@ import scala.collection.generic.MapProxyTemplate trait MapProxy[A, +B] extends Map[A, B] with MapProxyTemplate[A, B, Map[A, B]] { - override def thisCollection = this + override def repr = this private def newProxy[B1 >: B](newSelf: Map[A, B1]): MapProxy[A, B1] = new MapProxy[A, B1] { val self = newSelf } diff --git a/src/library/scala/collection/immutable/SetProxy.scala b/src/library/scala/collection/immutable/SetProxy.scala index d33a4b68cc..30b11f62b4 100644 --- a/src/library/scala/collection/immutable/SetProxy.scala +++ b/src/library/scala/collection/immutable/SetProxy.scala @@ -22,7 +22,7 @@ import scala.collection.generic.SetProxyTemplate trait SetProxy[A] extends Set[A] with SetProxyTemplate[A, Set[A]] { - override def thisCollection = this + override def repr = this private def newProxy[B >: A](newSelf: Set[B]): SetProxy[B] = new SetProxy[B] { val self = newSelf } diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala index cc641e70f8..b363c54a29 100644 --- a/src/library/scala/collection/immutable/SortedMap.scala +++ b/src/library/scala/collection/immutable/SortedMap.scala @@ -54,7 +54,7 @@ trait SortedMap[A, +B] extends Map[A, B] * @param elems the traversable object. */ override def ++[B1 >: B](elems: collection.Traversable[(A, B1)]): SortedMap[A, B1] = - ((thisCollection: SortedMap[A, B1]) /: elems) (_ + _) + ((repr: SortedMap[A, B1]) /: elems) (_ + _) /** Adds a number of elements provided by an iterator * and returns a new collection with the added elements. @@ -62,7 +62,7 @@ trait SortedMap[A, +B] extends Map[A, B] * @param iter the iterator */ override def ++[B1 >: B] (iter: Iterator[(A, B1)]): SortedMap[A, B1] = - ((thisCollection: SortedMap[A, B1]) /: iter) (_ + _) + ((repr: SortedMap[A, B1]) /: iter) (_ + _) } object SortedMap extends ImmutableSortedMapFactory[SortedMap] { diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index 04e9251bec..4684a22162 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -111,12 +111,6 @@ class Stack[+A] extends Sequence[A] { def next: A = { val r = top; cur = cur.pop; r } } - /** Returns the hash code for this stack. - * - * @return the hash code of the stack. - */ - override def hashCode(): Int = "Stack".hashCode - /** * Redefines the prefix of the string representation. */ @@ -128,7 +122,6 @@ class Stack[+A] extends Sequence[A] { override def length: Int = Stack.this.length + 1 override def top: B = elem override def pop: Stack[B] = Stack.this - override def hashCode(): Int = elem.hashCode() * 37 + Stack.this.hashCode() } } diff --git a/src/library/scala/collection/immutable/StringLike.scala b/src/library/scala/collection/immutable/StringLike.scala new file mode 100644 index 0000000000..5813c86607 --- /dev/null +++ b/src/library/scala/collection/immutable/StringLike.scala @@ -0,0 +1,250 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: RichString.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection +package immutable + +import scala.util.matching.Regex +import generic._ + +object StringLike { + + // just statics for companion class. + private final val LF: Char = 0x0A + private final val FF: Char = 0x0C + private final val CR: Char = 0x0D + private final val SU: Char = 0x1A +} + +import StringLike._ + +trait StringLike[+Repr] extends VectorLike[Char, Repr] with Ordered[String] { +self => + + /** Creates a string builder buffer as builder for this class */ + protected[this] def newBuilder: Builder[Char, Repr] + + /** Return element at index `n` + * @throws IndexOutofBoundsException if the index is not valid + */ + def apply(n: Int): Char = toString charAt n + + def length: Int = toString.length + + override def mkString = toString + + /** return n times the current string + */ + def * (n: Int): String = { + val buf = new StringBuilder + for (i <- 0 until n) buf append toString + buf.toString + } + + override def compare(other: String) = toString compareTo other + + private def isLineBreak(c: Char) = c == LF || c == FF + + /** <p> + * Strip trailing line end character from this string if it has one. + * A line end character is one of + * </p> + * <ul style="list-style-type: none;"> + * <li>LF - line feed (0x0A hex)</li> + * <li>FF - form feed (0x0C hex)</li> + * </ul> + * <p> + * If a line feed character LF is preceded by a carriage return CR + * (0x0D hex), the CR character is also stripped (Windows convention). + * </p> + */ + def stripLineEnd: String = { + val len = toString.length + if (len == 0) toString + else { + val last = apply(len - 1) + if (isLineBreak(last)) + toString.substring(0, if (last == LF && len >= 2 && apply(len - 2) == CR) len - 2 else len - 1) + else + toString + } + } + + /** <p> + * Return all lines in this string in an iterator, including trailing + * line end characters. + * </p> + * <p> + * The number of strings returned is one greater than the number of line + * end characters in this string. For an empty string, a single empty + * line is returned. A line end character is one of + * </p> + * <ul style="list-style-type: none;"> + * <li>LF - line feed (0x0A hex)</li> + * <li>FF - form feed (0x0C hex)</li> + * </ul> + */ + def linesWithSeparators: Iterator[String] = new Iterator[String] { + val str = self.toString + private val len = str.length + private var index = 0 + def hasNext: Boolean = index < len + def next(): String = { + if (index >= len) throw new NoSuchElementException("next on empty iterator") + val start = index + while (index < len && !isLineBreak(apply(index))) index += 1 + index += 1 + str.substring(start, index min len) + } + } + + /** Return all lines in this string in an iterator, excluding trailing line + * end characters, i.e. apply <code>.stripLineEnd</code> to all lines + * returned by <code>linesWithSeparators</code>. + */ + def lines: Iterator[String] = + linesWithSeparators map (line => new WrappedString(line).stripLineEnd) + + /** Return all lines in this string in an iterator, excluding trailing line + * end characters, i.e. apply <code>.stripLineEnd</code> to all lines + * returned by <code>linesWithSeparators</code>. + */ + def linesIterator: Iterator[String] = + linesWithSeparators map (line => new WrappedString(line).stripLineEnd) + + /** Returns this string with first character converted to upper case */ + def capitalize: String = + if (toString == null) null + else if (toString.length == 0) "" + else { + val chars = toString.toCharArray + chars(0) = chars(0).toUpperCase + new String(chars) + } + + /** Returns this string with the given <code>prefix</code> stripped. */ + def stripPrefix(prefix: String) = + if (toString.startsWith(prefix)) toString.substring(prefix.length) + else toString + + /** Returns this string with the given <code>suffix</code> stripped. */ + def stripSuffix(suffix: String) = + if (toString.endsWith(suffix)) toString.substring(0, toString.length() - suffix.length) + else toString + + /** <p> + * For every line in this string: + * </p> + * <blockquote> + * Strip a leading prefix consisting of blanks or control characters + * followed by <code>marginChar</code> from the line. + * </blockquote> + */ + def stripMargin(marginChar: Char): String = { + val buf = new StringBuilder + for (line <- linesWithSeparators) { + val len = line.length + var index = 0 + while (index < len && line.charAt(index) <= ' ') index += 1 + buf append + (if (index < len && line.charAt(index) == marginChar) line.substring(index + 1) else line) + } + buf.toString + } + + /** <p> + * For every line in this string: + * </p> + * <blockquote> + * Strip a leading prefix consisting of blanks or control characters + * followed by <code>|</code> from the line. + * </blockquote> + */ + def stripMargin: String = stripMargin('|') + + private def escape(ch: Char): String = "\\Q" + ch + "\\E" + + @throws(classOf[java.util.regex.PatternSyntaxException]) + def split(separator: Char): Array[String] = toString.split(escape(separator)) + + @throws(classOf[java.util.regex.PatternSyntaxException]) + def split(separators: Array[Char]): Array[String] = { + val re = separators.foldLeft("[")(_+escape(_)) + "]" + toString.split(re) + } + + /** You can follow a string with `.r', turning + * it into a Regex. E.g. + * + * """A\w*""".r is the regular expression for identifiers starting with `A'. + */ + def r: Regex = new Regex(toString) + + def toBoolean: Boolean = parseBoolean(toString) + def toByte: Byte = java.lang.Byte.parseByte(toString) + def toShort: Short = java.lang.Short.parseShort(toString) + def toInt: Int = java.lang.Integer.parseInt(toString) + def toLong: Long = java.lang.Long.parseLong(toString) + def toFloat: Float = java.lang.Float.parseFloat(toString) + def toDouble: Double = java.lang.Double.parseDouble(toString) + + private def parseBoolean(s: String): Boolean = + if (s != null) s.toLowerCase match { + case "true" => true + case "false" => false + case _ => throw new NumberFormatException("For input string: \""+s+"\"") + } + else + throw new NumberFormatException("For input string: \"null\"") + + /* !!! causes crash? + def toArray: Array[Char] = { + val result = new Array[Char](length) + toString.getChars(0, length, result, 0) + result + } + */ + + /** <p> + * Uses the underlying string as a pattern (in a fashion similar to + * printf in C), and uses the supplied arguments to fill in the + * holes. + * </p> + * <p> + * The interpretation of the formatting patterns is described in + * <a href="" target="contentFrame" class="java/util/Formatter"> + * <code>java.util.Formatter</code></a>. + * </p> + * + * @param args the arguments used to instantiating the pattern. + * @throws java.lang.IllegalArgumentException + */ + def format(args : Any*) : String = + java.lang.String.format(toString, args.asInstanceOf[Seq[AnyRef]].toArray: _*) + + /** <p> + * Like format(args*) but takes an initial Locale parameter + * which influences formatting as in java.lang.String's format. + * </p> + * <p> + * The interpretation of the formatting patterns is described in + * <a href="" target="contentFrame" class="java/util/Formatter"> + * <code>java.util.Formatter</code></a>. + * </p> + * + * @param locale an instance of java.util.Locale + * @param args the arguments used to instantiating the pattern. + * @throws java.lang.IllegalArgumentException + */ + def format(l: java.util.Locale, args: Any*): String = + java.lang.String.format(l, toString, args.asInstanceOf[Seq[AnyRef]].toArray: _*) +} + diff --git a/src/library/scala/collection/immutable/StringOps.scala b/src/library/scala/collection/immutable/StringOps.scala new file mode 100644 index 0000000000..57045d5a8b --- /dev/null +++ b/src/library/scala/collection/immutable/StringOps.scala @@ -0,0 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: RichString.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection +package immutable + +class StringOps(override val repr: String) extends StringLike[String] { + + override protected[this] def thisCollection: WrappedString = new WrappedString(repr) + override protected[this] def toCollection(repr: String): WrappedString = new WrappedString(repr) + + /** Creates a string builder buffer as builder for this class */ + override protected[this] def newBuilder = new StringBuilder + + override def toString = repr +} diff --git a/src/library/scala/collection/immutable/StringVector.scala b/src/library/scala/collection/immutable/StringVector.scala index 7073ccd117..2cda4cc8be 100644 --- a/src/library/scala/collection/immutable/StringVector.scala +++ b/src/library/scala/collection/immutable/StringVector.scala @@ -20,6 +20,10 @@ import scala.annotation.experimental * I looked for the fastest way to do these operations so there * is some unattractiveness. * + * Martin: We should disable this because it is superseded in functionality by + * StringLike/StringOps. We need to clarify whether performance is good enough with the new scheme. + * If not, maybe we need to bring back this object in some form. + * * @author Paul Phillips * @version 2.8 */ @@ -213,4 +217,4 @@ object StringVector } (sb1.toString, sb2.toString) } -}
\ No newline at end of file +} diff --git a/src/library/scala/collection/immutable/WrappedString.scala b/src/library/scala/collection/immutable/WrappedString.scala new file mode 100755 index 0000000000..d06a837a7f --- /dev/null +++ b/src/library/scala/collection/immutable/WrappedString.scala @@ -0,0 +1,29 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: RichString.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection +package immutable + +import scala.util.matching.Regex +import generic._ + +class WrappedString(override val self: String) extends Vector[Char] with StringLike[WrappedString] with Proxy { + + override protected[this] def thisCollection: WrappedString = this + override protected[this] def toCollection(repr: WrappedString): WrappedString = repr + + /** Creates a string builder buffer as builder for this class */ + override protected[this] def newBuilder = WrappedString.newBuilder +} + +object WrappedString { + def newBuilder: Builder[Char, WrappedString] = new StringBuilder() mapResult (new WrappedString(_)) +} diff --git a/src/library/scala/collection/interfaces/SetMethods.scala b/src/library/scala/collection/interfaces/SetMethods.scala index 534a4e240e..0f895d16be 100644 --- a/src/library/scala/collection/interfaces/SetMethods.scala +++ b/src/library/scala/collection/interfaces/SetMethods.scala @@ -15,7 +15,7 @@ import scala.reflect.ClassManifest import annotation.unchecked.uncheckedVariance trait AddableMethods[A, +This <: Addable[A, This]] { - protected def thisCollection: This + protected def repr: This def +(elem: A): This def + (elem1: A, elem2: A, elems: A*): This def ++ (elems: Traversable[A]): This @@ -23,7 +23,7 @@ trait AddableMethods[A, +This <: Addable[A, This]] { } trait SubtractableMethods[A, +This <: Subtractable[A, This]] { - protected def thisCollection: This + protected def repr: This def -(elem: A): This def -(elem1: A, elem2: A, elems: A*): This def --(elems: Traversable[A]): This diff --git a/src/library/scala/collection/mutable/GenericArray.scala b/src/library/scala/collection/mutable/GenericArray.scala new file mode 100755 index 0000000000..a1a86b2491 --- /dev/null +++ b/src/library/scala/collection/mutable/GenericArray.scala @@ -0,0 +1,77 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ResizableArray.scala 18387 2009-07-24 15:28:37Z odersky $ + + +package scala.collection.mutable + +import scala.collection.generic._ + +/** This class is used internally to implement data structures that + * are based on resizable arrays. + * + * @author Matthias Zenger, Burak Emir + * @author Martin Odersky + * @version 2.8 + */ +class GenericArray[A](override val length: Int) +extends Vector[A] + with TraversableClass[A, GenericArray] + with VectorTemplate[A, GenericArray[A]] { + + override def companion: Companion[GenericArray] = GenericArray + + var array: Array[AnyRef] = new Array[AnyRef](length) + + def apply(idx: Int): A = { + if (idx >= length) throw new IndexOutOfBoundsException(idx.toString) + array(idx).asInstanceOf[A] + } + + def update(idx: Int, elem: A) { + if (idx >= length) throw new IndexOutOfBoundsException(idx.toString) + array(idx) = elem.asInstanceOf[AnyRef] + } + + /** Fills the given array <code>xs</code> with the elements of + * this sequence starting at position <code>start</code>. + * + * @param xs the array to fill. + * @param start starting index. + */ + override def copyToArray[B >: A](xs: Array[B], start: Int) { + Array.copy(array, 0, xs, start, length) + } + + /** Copy all elements to a buffer + * @param The buffer to which elements are copied + override def copyToBuffer[B >: A](dest: Buffer[B]) { + dest ++= (array: Sequence[AnyRef]).asInstanceOf[Sequence[B]] + } + */ + + override def foreach[U](f: A => U) { + var i = 0 + while (i < length) { + f(array(i).asInstanceOf[A]) + i += 1 + } + } +} + +object GenericArray extends SequenceFactory[GenericArray] { + implicit def builderFactory[A]: BuilderFactory[A, GenericArray[A], Coll] = new VirtualBuilderFactory[A] + def newBuilder[A]: Builder[A, GenericArray[A]] = + new ArrayBuffer[A] mapResult { buf => + val result = new GenericArray[A](buf.length) + for (i <- 0 until buf.length) result.array(i) = buf(i).asInstanceOf[AnyRef] + // !!! todo: replace with buf.copyToArray(result.array, 0) + result + } +} diff --git a/src/library/scala/collection/mutable/MapProxy.scala b/src/library/scala/collection/mutable/MapProxy.scala index 051f92f62a..4092348f1a 100644 --- a/src/library/scala/collection/mutable/MapProxy.scala +++ b/src/library/scala/collection/mutable/MapProxy.scala @@ -28,7 +28,7 @@ import scala.collection.generic.MapProxyTemplate trait MapProxy[A, B] extends Map[A, B] with MapProxyTemplate[A, B, Map[A, B]] { - override def thisCollection = this + override def repr = this override def empty: MapProxy[A, B] = new MapProxy[A, B] { val self = MapProxy.this.self.empty } override def +(kv: (A, B)) = { self.update(kv._1, kv._2) ; this } diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala index 0e2d8cf7f6..cb471a0ee1 100644 --- a/src/library/scala/collection/mutable/PriorityQueue.scala +++ b/src/library/scala/collection/mutable/PriorityQueue.scala @@ -18,6 +18,12 @@ import scala.collection.generic.{ Addable, Cloneable, Growable } * To prioritize elements of type T there must be an implicit * Ordering[T] available at creation. * + * Martin: This class is utterly broken. It uses a resizable array + * as a heap, yet pretends to be a sequence via this same resizable array. + * Needless to say, order of elements is different in the two. + * So this class needs to be redesigned so that it uses the array only + * in its implementation, but implements a sequence interface separately. + * * @author Matthias Zenger * @version 1.0, 03/05/2004 */ @@ -34,7 +40,7 @@ class PriorityQueue[A](implicit ord: Ordering[A]) size0 += 1 // we do not use array(0) override def length: Int = super.length - 1 // adjust length accordingly override def isEmpty: Boolean = size0 < 2 - override protected def thisCollection = this + override def repr = this // hey foreach, our 0th element doesn't exist override def foreach[U](f: A => U) { @@ -156,14 +162,9 @@ class PriorityQueue[A](implicit ord: Ordering[A]) } } - /** Checks if two queues are structurally identical. - * - * @return true, iff both queues contain the same sequence of elements. + /** This is utterly broken: Two priority queues of different length can still be equal! + * The method should be removed once PriotyQueue inserts correctly into the sequence class hierarchy. */ - override def canEqualCollection(that: Any) = that.isInstanceOf[PriorityQueue[_]] - // !!! At this writing this is the only sequence which imposes stricter - // equality requirements, if there is some logic behind this we should - // document it. override def equals(obj: Any): Boolean = obj match { case that: PriorityQueue[_] => (this.iterator zip that.iterator) forall { case (x, y) => x == y } case _ => false diff --git a/src/library/scala/collection/mutable/ResizableArray.scala b/src/library/scala/collection/mutable/ResizableArray.scala index 5a6a5a187b..e0fbbf8e79 100644 --- a/src/library/scala/collection/mutable/ResizableArray.scala +++ b/src/library/scala/collection/mutable/ResizableArray.scala @@ -113,6 +113,6 @@ trait ResizableArray[A] extends Vector[A] } object ResizableArray extends SequenceFactory[ResizableArray] { - implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] + implicit def builderFactory[A]: BuilderFactory[A, ResizableArray[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, ResizableArray[A]] = new ArrayBuffer[A] } diff --git a/src/library/scala/collection/mutable/SetProxy.scala b/src/library/scala/collection/mutable/SetProxy.scala index 0ff57ee366..d14cbeeb4c 100644 --- a/src/library/scala/collection/mutable/SetProxy.scala +++ b/src/library/scala/collection/mutable/SetProxy.scala @@ -22,7 +22,7 @@ import scala.collection.generic.SetProxyTemplate */ trait SetProxy[A] extends Set[A] with SetProxyTemplate[A, Set[A]] { - override def thisCollection = this + override def repr = this override def empty = new SetProxy[A] { val self = SetProxy.this.self.empty } override def + (elem: A) = { self += elem ; this } override def - (elem: A) = { self -= elem ; this } diff --git a/src/library/scala/collection/mutable/StringBuilder.scala b/src/library/scala/collection/mutable/StringBuilder.scala index c9e9faca84..6f7ecc8c70 100644 --- a/src/library/scala/collection/mutable/StringBuilder.scala +++ b/src/library/scala/collection/mutable/StringBuilder.scala @@ -12,7 +12,6 @@ package scala.collection.mutable import collection.generic._ -import scala.runtime.RichString import compat.Platform.arraycopy import scala.reflect.Manifest diff --git a/src/library/scala/collection/mutable/VectorLike.scala b/src/library/scala/collection/mutable/VectorLike.scala new file mode 100755 index 0000000000..e686e21dd2 --- /dev/null +++ b/src/library/scala/collection/mutable/VectorLike.scala @@ -0,0 +1,47 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: MutableVectorTemplate.scala 18387 2009-07-24 15:28:37Z odersky $ + + +package scala.collection +package mutable +import generic._ + +/** A subtrait of collection.Vector which represents sequences + * that can be mutated. + */ +trait VectorLike[A, +Repr] extends scala.collection.VectorLike[A, Repr] { self => + + override protected[this] def thisCollection: Vector[A] = this.asInstanceOf[Vector[A]] + override protected[this] def toCollection(repr: Repr): Vector[A] = repr.asInstanceOf[Vector[A]] + + def update(idx: Int, elem: A) + + /** Creates a view of this iterable @see Iterable.View + */ + override def view = new MutableVectorView[A, Repr] { + protected lazy val underlying = self.repr + override def iterator = self.iterator + override def length = self.length + override def apply(idx: Int) = self.apply(idx) + override def update(idx: Int, elem: A) = self.update(idx, elem) + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current sequence, whereas `slice` produces a new sequence. + * + * @note view(from, to) is equivalent to view.slice(from, to) + */ + override def view(from: Int, until: Int) = view.slice(from, until) +} diff --git a/src/library/scala/collection/mutable/ArrayVector.scala b/src/library/scala/collection/mutable/WrappedArray.scala index 7c29d97336..45fe5ff39e 100755 --- a/src/library/scala/collection/mutable/ArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedArray.scala @@ -6,7 +6,7 @@ ** |/ ** \* */ -// $Id: ArrayVector.scala 18589 2009-08-27 14:45:35Z odersky $ +// $Id: WrappedArray.scala 18589 2009-08-27 14:45:35Z odersky $ package scala.collection.mutable @@ -21,7 +21,10 @@ import collection.generic._ * @author Martin Odersky, Stephane Micheloud * @version 1.0 */ -abstract class ArrayVector[A] extends Vector[A] with VectorTemplate[A, ArrayVector[A]] { self => +abstract class WrappedArray[A] extends Vector[A] with VectorLike[A, WrappedArray[A]] with Proxy { self => + + override protected[this] def thisCollection: WrappedArray[A] = this + override protected[this] def toCollection(repr: WrappedArray[A]): WrappedArray[A] = repr /** The manifest of the element type */ def elemManifest: ClassManifest[A] @@ -36,10 +39,13 @@ abstract class ArrayVector[A] extends Vector[A] with VectorTemplate[A, ArrayVect def update(index: Int, elem: A): Unit /** The underlying array */ - def value: AnyRef + def array: AnyRef + + /** The original of a proxy represented by a wrapped array */ + override def self = repr /** Creates new builder for this collection ==> move to subclasses */ - override protected[this] def newBuilder: Builder[A, ArrayVector[A]] = - new ArrayVectorBuilder[A](elemManifest) + override protected[this] def newBuilder: Builder[A, WrappedArray[A]] = + new WrappedArrayBuilder[A](elemManifest) } diff --git a/src/library/scala/collection/mutable/ArrayVectorBuilder.scala b/src/library/scala/collection/mutable/WrappedArrayBuilder.scala index 761fc1c25e..bf363cc097 100755 --- a/src/library/scala/collection/mutable/ArrayVectorBuilder.scala +++ b/src/library/scala/collection/mutable/WrappedArrayBuilder.scala @@ -15,15 +15,15 @@ import scala.collection.generic._ import scala.reflect.ClassManifest /** A builder class for arrays */ -class ArrayVectorBuilder[A](manifest: ClassManifest[A]) extends Builder[A, ArrayVector[A]] { +class WrappedArrayBuilder[A](manifest: ClassManifest[A]) extends Builder[A, WrappedArray[A]] { - private var elems: ArrayVector[A] = _ + private var elems: WrappedArray[A] = _ private var capacity: Int = 0 private var size: Int = 0 - private def mkArray(size: Int): ArrayVector[A] = { - val newelems = manifest.newArrayVector(size) - if (this.size > 0) Array.copy(elems.value, 0, newelems.value, 0, this.size) + private def mkArray(size: Int): WrappedArray[A] = { + val newelems = manifest.newWrappedArray(size) + if (this.size > 0) Array.copy(elems.array, 0, newelems.array, 0, this.size) newelems } diff --git a/src/library/scala/collection/mutable/BooleanArrayVector.scala b/src/library/scala/collection/mutable/WrappedBooleanArray.scala index 0d701464ee..9274a805ab 100755 --- a/src/library/scala/collection/mutable/BooleanArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedBooleanArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: BooleanArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedBooleanArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class BooleanArrayVector(val value: Array[Boolean]) extends ArrayVector[Boolean] { +final class WrappedBooleanArray(val array: Array[Boolean]) extends WrappedArray[Boolean] { def elemManifest = ClassManifest.Boolean - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Boolean = value(index) + def apply(index: Int): Boolean = array(index) def update(index: Int, elem: Boolean) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/ByteArrayVector.scala b/src/library/scala/collection/mutable/WrappedByteArray.scala index 47fe905ec3..5cacc7858e 100755 --- a/src/library/scala/collection/mutable/ByteArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedByteArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: ByteArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedByteArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class ByteArrayVector(val value: Array[Byte]) extends ArrayVector[Byte] { +final class WrappedByteArray(val array: Array[Byte]) extends WrappedArray[Byte] { def elemManifest = ClassManifest.Byte - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Byte = value(index) + def apply(index: Int): Byte = array(index) def update(index: Int, elem: Byte) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/CharArrayVector.scala b/src/library/scala/collection/mutable/WrappedCharArray.scala index cd9a0592de..4d3ffaa3f0 100755 --- a/src/library/scala/collection/mutable/CharArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedCharArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: CharArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedCharArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class CharArrayVector(val value: Array[Char]) extends ArrayVector[Char] { +final class WrappedCharArray(val array: Array[Char]) extends WrappedArray[Char] { def elemManifest = ClassManifest.Char - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Char = value(index) + def apply(index: Int): Char = array(index) def update(index: Int, elem: Char) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/DoubleArrayVector.scala b/src/library/scala/collection/mutable/WrappedDoubleArray.scala index dd775fb279..c5e6704bcd 100755 --- a/src/library/scala/collection/mutable/DoubleArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedDoubleArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: DoubleArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedDoubleArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class DoubleArrayVector(val value: Array[Double]) extends ArrayVector[Double] { +final class WrappedDoubleArray(val array: Array[Double]) extends WrappedArray[Double] { def elemManifest = ClassManifest.Double - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Double = value(index) + def apply(index: Int): Double = array(index) def update(index: Int, elem: Double) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/FloatArrayVector.scala b/src/library/scala/collection/mutable/WrappedFloatArray.scala index 67ff0e09e0..d9eb77cdb5 100755 --- a/src/library/scala/collection/mutable/FloatArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedFloatArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: FloatArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedFloatArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class FloatArrayVector(val value: Array[Float]) extends ArrayVector[Float] { +final class WrappedFloatArray(val array: Array[Float]) extends WrappedArray[Float] { def elemManifest = ClassManifest.Float - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Float = value(index) + def apply(index: Int): Float = array(index) def update(index: Int, elem: Float) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/IntArrayVector.scala b/src/library/scala/collection/mutable/WrappedIntArray.scala index ea3e9bf5af..bc734a21bf 100755 --- a/src/library/scala/collection/mutable/IntArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedIntArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: IntArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedIntArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class IntArrayVector(val value: Array[Int]) extends ArrayVector[Int] { +final class WrappedIntArray(val array: Array[Int]) extends WrappedArray[Int] { def elemManifest = ClassManifest.Int - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Int = value(index) + def apply(index: Int): Int = array(index) def update(index: Int, elem: Int) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/LongArrayVector.scala b/src/library/scala/collection/mutable/WrappedLongArray.scala index a1a2a5795d..22eeef8363 100755 --- a/src/library/scala/collection/mutable/LongArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedLongArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: LongArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedLongArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class LongArrayVector(val value: Array[Long]) extends ArrayVector[Long] { +final class WrappedLongArray(val array: Array[Long]) extends WrappedArray[Long] { def elemManifest = ClassManifest.Long - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Long = value(index) + def apply(index: Int): Long = array(index) def update(index: Int, elem: Long) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/ObjectArrayVector.scala b/src/library/scala/collection/mutable/WrappedRefArray.scala index 48cfb204d3..aeaf4545b2 100755 --- a/src/library/scala/collection/mutable/ObjectArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedRefArray.scala @@ -6,7 +6,7 @@ ** |/ ** \* */ -// $Id: ObjectArrayVector.scala 18589 2009-08-27 14:45:35Z odersky $ +// $Id: WrappedObjectArray.scala 18589 2009-08-27 14:45:35Z odersky $ package scala.collection.mutable @@ -15,19 +15,18 @@ import scala.reflect.ClassManifest import Predef._ @serializable -final class ObjectArrayVector[A <: AnyRef](val value: Array[AnyRef], val elemManifest: ClassManifest[A]) extends ArrayVector[A] { +final class WrappedRefArray[A](val array: Array[AnyRef]) extends WrappedArray[A] { -// @deprecated("creating array w/o manifest") - def this(value: Array[AnyRef]) = this(value, null) // !!! todo: remove + lazy val elemManifest = ClassManifest.classType[A](array.getClass.getComponentType) - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): A = value(index).asInstanceOf[A] + def apply(index: Int): A = array(index).asInstanceOf[A] def update(index: Int, elem: A) { - value(index) = elem + array(index) = elem.asInstanceOf[AnyRef] } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/ShortArrayVector.scala b/src/library/scala/collection/mutable/WrappedShortArray.scala index 62e4c9a2f9..e119248c16 100755 --- a/src/library/scala/collection/mutable/ShortArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedShortArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: ShortArrayVector.scala 18572 2009-08-25 14:14:11Z odersky $ +// $Id: WrappedShortArray.scala 18572 2009-08-25 14:14:11Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class ShortArrayVector(val value: Array[Short]) extends ArrayVector[Short] { +final class WrappedShortArray(val array: Array[Short]) extends WrappedArray[Short] { def elemManifest = ClassManifest.Short - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Short = value(index) + def apply(index: Int): Short = array(index) def update(index: Int, elem: Short) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/collection/mutable/UnitArrayVector.scala b/src/library/scala/collection/mutable/WrappedUnitArray.scala index a89da3cd0d..52a3f06077 100755 --- a/src/library/scala/collection/mutable/UnitArrayVector.scala +++ b/src/library/scala/collection/mutable/WrappedUnitArray.scala @@ -6,23 +6,23 @@ ** |/ ** \* */ -// $Id: DoubleArrayVector.scala 17680 2009-05-08 16:33:15Z odersky $ +// $Id: WrappedDoubleArray.scala 17680 2009-05-08 16:33:15Z odersky $ package scala.collection.mutable import scala.reflect.ClassManifest @serializable -final class UnitArrayVector(val value: Array[Unit]) extends ArrayVector[Unit] { +final class WrappedUnitArray(val array: Array[Unit]) extends WrappedArray[Unit] { def elemManifest = ClassManifest.Unit - def length: Int = value.length + def length: Int = array.length - def apply(index: Int): Unit = value(index) + def apply(index: Int): Unit = array(index) def update(index: Int, elem: Unit) { - value(index) = elem + array(index) = elem } - def unbox(elemClass: Class[_]): AnyRef = value + def unbox(elemClass: Class[_]): AnyRef = array } diff --git a/src/library/scala/reflect/ClassManifest.scala b/src/library/scala/reflect/ClassManifest.scala index 66e4758542..f83ed8cb28 100644 --- a/src/library/scala/reflect/ClassManifest.scala +++ b/src/library/scala/reflect/ClassManifest.scala @@ -13,7 +13,7 @@ package scala.reflect import scala.runtime._ import scala.collection.immutable.Nil -import scala.collection.mutable.{ArrayVector, ObjectArrayVector} +import scala.collection.mutable.{WrappedArray, WrappedRefArray} /** <p> * A <code>ClassManifest[T]</code> is an opaque descriptor for type <code>T</code>. @@ -78,10 +78,10 @@ trait ClassManifest[T] extends OptManifest[T] { .asInstanceOf[BoxedArray[T]] } - def newArrayVector(len: Int): ArrayVector[T] = + def newWrappedArray(len: Int): WrappedArray[T] = // it's safe to assume T <: AnyRef here because the method is overridden for all value type manifests - new ObjectArrayVector(java.lang.reflect.Array.newInstance(erasure, len).asInstanceOf[Array[AnyRef]]) - .asInstanceOf[ArrayVector[T]] + new WrappedRefArray(java.lang.reflect.Array.newInstance(erasure, len).asInstanceOf[Array[AnyRef]]) + .asInstanceOf[WrappedArray[T]] def typeArguments: List[OptManifest[_]] = List() diff --git a/src/library/scala/reflect/Manifest.scala b/src/library/scala/reflect/Manifest.scala index 354058ab4c..8bcf60d323 100644 --- a/src/library/scala/reflect/Manifest.scala +++ b/src/library/scala/reflect/Manifest.scala @@ -46,63 +46,63 @@ object Manifest { def erasure = java.lang.Byte.TYPE override def toString = "Byte" override def newArray(len: Int): BoxedArray[Byte] = new BoxedByteArray(new Array[Byte](len)) - override def newArrayVector(len: Int): ArrayVector[Byte] = new ByteArrayVector(new Array[Byte](len)) + override def newWrappedArray(len: Int): WrappedArray[Byte] = new WrappedByteArray(new Array[Byte](len)) } val Short = new (Manifest[Short] @serializable) { def erasure = java.lang.Short.TYPE override def toString = "Short" override def newArray(len: Int): BoxedArray[Short] = new BoxedShortArray(new Array[Short](len)) - override def newArrayVector(len: Int): ArrayVector[Short] = new ShortArrayVector(new Array[Short](len)) + override def newWrappedArray(len: Int): WrappedArray[Short] = new WrappedShortArray(new Array[Short](len)) } val Char = new (Manifest[Char] @serializable) { def erasure = java.lang.Character.TYPE override def toString = "Char" override def newArray(len: Int): BoxedArray[Char] = new BoxedCharArray(new Array[Char](len)) - override def newArrayVector(len: Int): ArrayVector[Char] = new CharArrayVector(new Array[Char](len)) + override def newWrappedArray(len: Int): WrappedArray[Char] = new WrappedCharArray(new Array[Char](len)) } val Int = new (Manifest[Int] @serializable) { def erasure = java.lang.Integer.TYPE override def toString = "Int" override def newArray(len: Int): BoxedArray[Int] = new BoxedIntArray(new Array[Int](len)) - override def newArrayVector(len: Int): ArrayVector[Int] = new IntArrayVector(new Array[Int](len)) + override def newWrappedArray(len: Int): WrappedArray[Int] = new WrappedIntArray(new Array[Int](len)) } val Long = new (Manifest[Long] @serializable) { def erasure = java.lang.Long.TYPE override def toString = "Long" override def newArray(len: Int): BoxedArray[Long] = new BoxedLongArray(new Array[Long](len)) - override def newArrayVector(len: Int): ArrayVector[Long] = new LongArrayVector(new Array[Long](len)) + override def newWrappedArray(len: Int): WrappedArray[Long] = new WrappedLongArray(new Array[Long](len)) } val Float = new (Manifest[Float] @serializable) { def erasure = java.lang.Float.TYPE override def toString = "Float" override def newArray(len: Int): BoxedArray[Float] = new BoxedFloatArray(new Array[Float](len)) - override def newArrayVector(len: Int): ArrayVector[Float] = new FloatArrayVector(new Array[Float](len)) + override def newWrappedArray(len: Int): WrappedArray[Float] = new WrappedFloatArray(new Array[Float](len)) } val Double = new (Manifest[Double] @serializable) { def erasure = java.lang.Double.TYPE override def toString = "Double" override def newArray(len: Int): BoxedArray[Double] = new BoxedDoubleArray(new Array[Double](len)) - override def newArrayVector(len: Int): ArrayVector[Double] = new DoubleArrayVector(new Array[Double](len)) + override def newWrappedArray(len: Int): WrappedArray[Double] = new WrappedDoubleArray(new Array[Double](len)) } val Boolean = new (Manifest[Boolean] @serializable) { def erasure = java.lang.Boolean.TYPE override def toString = "Boolean" override def newArray(len: Int): BoxedArray[Boolean] = new BoxedBooleanArray(new Array[Boolean](len)) - override def newArrayVector(len: Int): ArrayVector[Boolean] = new BooleanArrayVector(new Array[Boolean](len)) + override def newWrappedArray(len: Int): WrappedArray[Boolean] = new WrappedBooleanArray(new Array[Boolean](len)) } val Unit = new (Manifest[Unit] @serializable) { def erasure = java.lang.Void.TYPE override def toString = "Unit" override def newArray(len: Int): BoxedArray[Unit] = new BoxedUnitArray(new Array[Unit](len)) - override def newArrayVector(len: Int): ArrayVector[Unit] = new UnitArrayVector(new Array[Unit](len)) + override def newWrappedArray(len: Int): WrappedArray[Unit] = new WrappedUnitArray(new Array[Unit](len)) } val Any: Manifest[Any] = new ClassTypeManifest[Any](None, classOf[java.lang.Object], List()) { diff --git a/src/library/scala/runtime/ScalaRunTime.scala b/src/library/scala/runtime/ScalaRunTime.scala index fdabfd0d34..042528697c 100644 --- a/src/library/scala/runtime/ScalaRunTime.scala +++ b/src/library/scala/runtime/ScalaRunTime.scala @@ -40,15 +40,15 @@ object ScalaRunTime { /** Convert arrays to sequences, leave sequences as they are */ def toSequence[T](xs: AnyRef): Sequence[T] = xs match { case ts: Sequence[T] => ts.asInstanceOf[Sequence[T]] - case x: Array[AnyRef] => new ObjectArrayVector(x, ClassManifest.classType(x.getClass.getComponentType)) - case x: Array[Int] => new IntArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Double] => new DoubleArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Long] => new LongArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Float] => new FloatArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Char] => new CharArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Byte] => new ByteArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Short] => new ShortArrayVector(x).asInstanceOf[Array[T]] - case x: Array[Boolean] => new BooleanArrayVector(x).asInstanceOf[Array[T]] + case x: Array[AnyRef] => new WrappedRefArray(x).asInstanceOf[Array[T]] + case x: Array[Int] => new WrappedIntArray(x).asInstanceOf[Array[T]] + case x: Array[Double] => new WrappedDoubleArray(x).asInstanceOf[Array[T]] + case x: Array[Long] => new WrappedLongArray(x).asInstanceOf[Array[T]] + case x: Array[Float] => new WrappedFloatArray(x).asInstanceOf[Array[T]] + case x: Array[Char] => new WrappedCharArray(x).asInstanceOf[Array[T]] + case x: Array[Byte] => new WrappedByteArray(x).asInstanceOf[Array[T]] + case x: Array[Short] => new WrappedShortArray(x).asInstanceOf[Array[T]] + case x: Array[Boolean] => new WrappedBooleanArray(x).asInstanceOf[Array[T]] case null => null } @@ -165,20 +165,6 @@ object ScalaRunTime { case null => null } - def box(value: AnyRef): AnyRef = value match { - case x: String => new RichString(x) - case x: Array[AnyRef] => new BoxedObjectArray(x, ClassManifest.classType(x.getClass.getComponentType)) - case x: Array[Int] => new BoxedIntArray(x) - case x: Array[Double] => new BoxedDoubleArray(x) - case x: Array[Long] => new BoxedLongArray(x) - case x: Array[Float] => new BoxedFloatArray(x) - case x: Array[Char] => new BoxedCharArray(x) - case x: Array[Byte] => new BoxedByteArray(x) - case x: Array[Short] => new BoxedShortArray(x) - case x: Array[Boolean] => new BoxedBooleanArray(x) - case x => x - } - /** Given any Scala value, convert it to a String. * * The primary motivation for this method is to provide a means for diff --git a/test/files/run/implicits.scala b/test/files/run/implicits.scala index 3fd3561fe7..e554575284 100644 --- a/test/files/run/implicits.scala +++ b/test/files/run/implicits.scala @@ -23,3 +23,26 @@ object Test extends Application { Console.println(s) Console.println(2: String) } + +object TestPriority { + + class C(x: Int) { def foo: Int = x + 1 } + + class D(x: Int) { def foo: Int = x + 2 } + + class IMPL { + implicit def Int2C(x: Int): C = new C(x) + } + + object impl extends IMPL { + implicit def Int2D(x: Int): D = new D(x) + } + + import impl._ + + val x: C = 2 + val y: D = 2 + assert(x.foo == 3, x.foo) + assert(y.foo == 4, y.foo) + assert((2).foo == 4, (2).foo) +} diff --git a/test/files/run/t2212.scala b/test/files/run/t2212.scala.disabled index 5f4447fa2b..5f4447fa2b 100644 --- a/test/files/run/t2212.scala +++ b/test/files/run/t2212.scala.disabled |