From a04195e63727872f04ad01900a18f6ca9ec5cf2b Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 27 Aug 2009 14:45:35 +0000 Subject: added manifests to most parts of standard libra... added manifests to most parts of standard library which deal with arrays. One test is temporarily disabled, as it shows a deep problem with multi-dimensional arrays (which was present all along). --- .../scala/tools/nsc/ast/parser/TreeBuilder.scala | 2 +- .../scala/tools/nsc/symtab/Definitions.scala | 4 + src/compiler/scala/tools/nsc/symtab/StdNames.scala | 1 + .../scala/tools/nsc/transform/Erasure.scala | 28 ++- .../scala/tools/nsc/transform/UnCurry.scala | 10 +- .../scala/tools/nsc/typechecker/Implicits.scala | 15 +- .../tools/nsc/typechecker/NamesDefaults.scala | 4 +- .../scala/tools/nsc/typechecker/RefChecks.scala | 21 +- .../scala/tools/nsc/typechecker/Typers.scala | 22 +- src/library/scala/Array.scala | 243 +++++++++++++++++---- src/library/scala/collection/JavaConversions.scala | 10 +- src/library/scala/collection/Traversable.scala | 61 +----- .../collection/generic/SequenceTemplate.scala | 3 +- .../collection/generic/TraversableClass.scala | 14 +- .../collection/generic/TraversableFactory.scala | 53 +++-- .../collection/generic/TraversableForwarder.scala | 2 +- .../generic/TraversableProxyTemplate.scala | 2 +- .../collection/generic/TraversableTemplate.scala | 8 +- .../scala/collection/generic/VectorTemplate.scala | 2 + .../scala/collection/immutable/Stream.scala | 6 +- .../scala/collection/mutable/ArrayBuilder.scala | 12 +- .../scala/collection/mutable/StringBuilder.scala | 1 + src/library/scala/reflect/ClassManifest.scala | 45 ++-- src/library/scala/reflect/Manifest.scala | 59 +++-- src/library/scala/reflect/NoManifest.scala | 4 +- src/library/scala/runtime/BoxedArray.scala | 50 ++--- src/library/scala/runtime/BoxedObjectArray.scala | 3 +- src/library/scala/runtime/RichString.scala | 8 +- src/library/scala/runtime/ScalaRunTime.scala | 27 ++- src/library/scala/util/Marshal.scala | 8 +- src/library/scala/util/Random.scala | 2 +- src/library/scala/util/Sorting.scala | 17 +- 32 files changed, 477 insertions(+), 270 deletions(-) (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala index aa057c43b5..66b358383d 100644 --- a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala @@ -512,7 +512,7 @@ abstract class TreeBuilder { if (contextBounds.isEmpty) vparamss else { val mods = Modifiers(if (owner.isTypeName) PARAMACCESSOR | LOCAL | PRIVATE else PARAM) - def makeEvidenceParam(tpt: Tree) = ValDef(mods | IMPLICIT, freshName("man$"), tpt, EmptyTree) + def makeEvidenceParam(tpt: Tree) = ValDef(mods | IMPLICIT, freshName(nme.EVIDENCE_PARAM_PREFIX), tpt, EmptyTree) vparamss ::: List(contextBounds map makeEvidenceParam) } diff --git a/src/compiler/scala/tools/nsc/symtab/Definitions.scala b/src/compiler/scala/tools/nsc/symtab/Definitions.scala index 71f005a98a..87c874465a 100644 --- a/src/compiler/scala/tools/nsc/symtab/Definitions.scala +++ b/src/compiler/scala/tools/nsc/symtab/Definitions.scala @@ -649,6 +649,10 @@ trait Definitions { addModuleMethod(DoubleClass, "NegativeInfinity", java.lang.Double.NEGATIVE_INFINITY) } + /** Is symbol a phantom class for which no runtime representation exists? */ + def isPhantomClass(sym: Symbol) = + sym == AnyClass || sym == AnyValClass || sym == NullClass || sym == NothingClass + /** Is symbol a value class? */ def isValueClass(sym: Symbol): Boolean = (sym eq UnitClass) || (boxedClass contains sym) diff --git a/src/compiler/scala/tools/nsc/symtab/StdNames.scala b/src/compiler/scala/tools/nsc/symtab/StdNames.scala index 5426a76643..894291d4dc 100644 --- a/src/compiler/scala/tools/nsc/symtab/StdNames.scala +++ b/src/compiler/scala/tools/nsc/symtab/StdNames.scala @@ -82,6 +82,7 @@ trait StdNames { val INTERPRETER_VAR_PREFIX = "res" val INTERPRETER_IMPORT_WRAPPER = "$iw" val INTERPRETER_SYNTHVAR_PREFIX = "synthvar$" + val EVIDENCE_PARAM_PREFIX = "evidence$" def LOCAL(clazz: Symbol) = newTermName(LOCALDUMMY_PREFIX_STRING + clazz.name+">") def TUPLE_FIELD(index: Int) = newTermName(TUPLE_FIELD_PREFIX_STRING + index) diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala index c3de8d6bd9..6618480d58 100644 --- a/src/compiler/scala/tools/nsc/transform/Erasure.scala +++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala @@ -21,10 +21,9 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast. // @S: XXX: why is this here? earsure is a typer, if you comment this // out erasure still works, uses its own typed methods. lazy val typerXXX = this.typer - import typerXXX.{typed} // methods to type trees + import typerXXX.{typed, typedPos} // methods to type trees import CODE._ - def typedPos(pos: Position)(tree: Tree) = typed { atPos(pos)(tree) } val phaseName: String = "erasure" @@ -387,7 +386,9 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast. }) } - /** generate ScalaRuntime.boxArray(tree) */ + /** generate ScalaRuntime.boxArray(tree) + * !!! todo: optimize this in case the runtime type is known + */ private def boxArray(tree: Tree): Tree = tree match { case LabelDef(name, params, rhs) => val rhs1 = boxArray(rhs) @@ -451,12 +452,12 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast. ELSE (x()) ) ) - else if (pt.typeSymbol isNonBottomSubClass BoxedArrayClass) once (x => - (IF (x() IS_OBJ BoxedArrayClass.tpe) THEN (x()) ELSE boxArray(x())) - ) - else if (isSeqClass(pt.typeSymbol)) once (x => - (IF (x() IS_OBJ pt) THEN (x()) ELSE (boxArray(x()))) - ) + else if (pt.typeSymbol isNonBottomSubClass BoxedArrayClass) + once (x => + (IF (x() IS_OBJ BoxedArrayClass.tpe) THEN (x()) ELSE boxArray(x()))) + else if (isSeqClass(pt.typeSymbol)) + once (x => + (IF (x() IS_OBJ pt) THEN (x()) ELSE (boxArray(x())))) else asPt(tree) } else asPt(tree) } @@ -560,12 +561,9 @@ abstract class Erasure extends AddInterfaces with typechecker.Analyzer with ast. tree match { case Apply(Select(New(tpt), name), args) if (tpt.tpe.typeSymbol == BoxedArrayClass) => assert(name == nme.CONSTRUCTOR); - val translated: Tree = - if (args.length >= 2) REF(ArrayModule) DOT nme.ofDim - else NEW(BoxedAnyArrayClass) DOT name - - atPos(tree.pos) { - Typed(Apply(translated, args), tpt) + assert(args.length < 2) + typedPos(tree.pos) { + Typed(Apply(NEW(BoxedAnyArrayClass) DOT name, args), tpt) } case Apply(TypeApply(sel @ Select(qual, name), List(targ)), List()) if tree.symbol == Any_asInstanceOf => val qual1 = typedQualifier(qual) diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index 7af0c4f56c..9b2b9e2248 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -392,15 +392,7 @@ abstract class UnCurry extends InfoTransform with TypingTransformers { 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) - } - } + else List(localTyper.getManifestTree(tree.pos, tree.tpe.typeArgs.head, false)) // new style, with manifest atPhase(phase.next) { localTyper.typed { atPos(pos) { diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index 9d3cccab37..7ebaa27872 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -599,7 +599,7 @@ self: Analyzer => * reflect.Manifest for type 'tp'. An EmptyTree is returned if * no manifest is found. todo: make this instantiate take type params as well? */ - def manifestOfType(tp: Type, full: Boolean): Tree = { + private def manifestOfType(tp: Type, full: Boolean): Tree = { /** Creates a tree that calls the factory method called constructor in object reflect.Manifest */ def manifestFactoryCall(constructor: String, args: Tree*): Tree = @@ -627,25 +627,22 @@ self: Analyzer => case ConstantType(value) => manifestOfType(tp0.deconst, full) case TypeRef(pre, sym, args) => - if (isValueClass(sym)) { + if (isValueClass(sym) || isPhantomClass(sym)) { typed { atPos(tree.pos.focus) { Select(gen.mkAttributedRef(FullManifestModule), sym.name.toString) }} - } - else if (sym.isClass) { + } else if (sym.isClass) { val suffix = gen.mkClassOf(tp0) :: (args map findSubManifest) manifestFactoryCall( "classType", (if ((pre eq NoPrefix) || pre.typeSymbol.isStaticOwner) suffix else findSubManifest(pre) :: suffix): _*) - } - else if (sym.isTypeParameterOrSkolem || sym.isExistential) { - EmptyTree // a manifest should have been found by normal searchImplicit - } - else { + } else if (sym.isAbstractType && !sym.isTypeParameterOrSkolem && !sym.isExistential) { manifestFactoryCall( "abstractType", findSubManifest(pre) :: Literal(sym.name.toString) :: findManifest(tp0.bounds.hi) :: (args map findSubManifest): _*) + } else { + EmptyTree // a manifest should have been found by normal searchImplicit } case RefinedType(parents, decls) => // refinement is not generated yet diff --git a/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala index d86c9f3b44..25af71be19 100644 --- a/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala +++ b/src/compiler/scala/tools/nsc/typechecker/NamesDefaults.scala @@ -31,7 +31,7 @@ trait NamesDefaults { self: Analyzer => /** @param pos maps indicies from old to new */ - def reorderArgs[T](args: List[T], pos: Int => Int): List[T] = { + def reorderArgs[T: ClassManifest](args: List[T], pos: Int => Int): List[T] = { val res = new Array[T](args.length) // (hopefully) faster than zipWithIndex (0 /: args) { case (index, arg) => res(pos(index)) = arg; index + 1 } @@ -39,7 +39,7 @@ trait NamesDefaults { self: Analyzer => } /** @param pos maps indicies from new to old (!) */ - def reorderArgsInv[T](args: List[T], pos: Int => Int): List[T] = { + def reorderArgsInv[T: ClassManifest](args: List[T], pos: Int => Int): List[T] = { val argsArray = args.toArray val res = new ListBuffer[T] for (i <- 0 until argsArray.length) diff --git a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala index 42d0dd80fb..3dec50e03d 100644 --- a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala +++ b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala @@ -708,13 +708,7 @@ abstract class RefChecks extends InfoTransform { List(transform(cdef)) } } else { - val vdef = - localTyper.typed { - atPos(tree.pos) { - gen.mkModuleVarDef(sym) - } - } - + val vdef = localTyper.typedPos(tree.pos) { gen.mkModuleVarDef(sym) } val ddef = atPhase(phase.next) { localTyper.typed { @@ -930,6 +924,19 @@ abstract class RefChecks extends InfoTransform { if (tpt.tpe.typeSymbol == ArrayClass && args.length >= 2) => unit.deprecationWarning(tree.pos, "new Array(...) with multiple dimensions has been deprecated; use Array.ofDim(...) instead") + val manif = { + var etpe = tpt.tpe + for (_ <- args) { etpe = etpe.typeArgs.headOption.getOrElse(NoType) } + if (etpe == NoType) { + unit.error(tree.pos, "too many dimensions for array creation") + Literal(Constant(null)) + } else { + localTyper.getManifestTree(tree.pos, etpe, false) + } + } + result = localTyper.typedPos(tree.pos) { + Apply(Apply(Select(gen.mkAttributedRef(ArrayModule), nme.ofDim), args), List(manif)) + } currentApplication = tree case Apply(fn, args) => diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index cbb9129b30..372f8965e4 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -180,7 +180,7 @@ trait Typers { self: Analyzer => def applyImplicitArgs(fun: Tree): Tree = fun.tpe match { case MethodType(params, _) => var positional = true - val argResults = params map (_.tpe) map (inferImplicit(fun, _, true, false, context)) + val argResults = params map (p => inferImplicit(fun, p.tpe, true, false, context)) val args = argResults.zip(params) flatMap { case (arg, param) => if (arg != SearchFailure) { @@ -188,8 +188,10 @@ trait Typers { self: Analyzer => else List(atPos(arg.tree.pos)(new AssignOrNamedArg(Ident(param.name), (arg.tree)))) } else { if (!param.hasFlag(DEFAULTPARAM)) - context.error(fun.pos, "could not find implicit value for parameter "+ - param.name +":"+ param.tpe +".") + context.error( + fun.pos, "could not find implicit value for "+ + (if (param.name startsWith nme.EVIDENCE_PARAM_PREFIX) "evidence parameter of type " + else "parameter "+param.name+": ")+param.tpe) positional = false Nil } @@ -956,7 +958,7 @@ trait Typers { self: Analyzer => if (coercion != EmptyTree) { if (settings.debug.value) log("inferred view from "+tree.tpe+" to "+pt+" = "+coercion+":"+coercion.tpe) return newTyper(context.makeImplicit(context.reportAmbiguousErrors)).typed( - Apply(coercion, List(tree)) setPos tree.pos, mode, pt) + Apply(coercion, List(tree)) setPos tree.pos, mode, pt) } } } @@ -3778,6 +3780,8 @@ trait Typers { self: Analyzer => ret } + def typedPos(pos: Position)(tree: Tree) = typed(atPos(pos)(tree)) + /** Types expression tree with given prototype pt. * * @param tree ... @@ -3851,6 +3855,16 @@ trait Typers { self: Analyzer => EmptyTree, appliedType((if (full) FullManifestClass else PartialManifestClass).typeConstructor, List(tp)), true, false, context) + + def getManifestTree(pos: Position, tp: Type, full: Boolean): Tree = { + val manifestOpt = findManifest(tp, false) + if (manifestOpt.tree.isEmpty) { + error(pos, "cannot find "+(if (full) "" else "class ")+"manifest for element type of "+tp) + Literal(Constant(null)) + } else { + manifestOpt.tree + } + } /* def convertToTypeTree(tree: Tree): Tree = tree match { case TypeTree() => tree diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala index 7f42ada4b1..9877fb59d4 100644 --- a/src/library/scala/Array.scala +++ b/src/library/scala/Array.scala @@ -12,21 +12,26 @@ package scala import scala.collection.generic._ -import scala.collection.mutable.{Vector, ArrayBuffer} +import scala.collection.Traversable +import scala.collection.mutable.{Vector, ArrayBuilder} import compat.Platform.arraycopy +import scala.reflect.ClassManifest /** This object contains utility methods operating on arrays. * * @author Martin Odersky * @version 1.0 */ -object Array extends SequenceFactory[Array] { +object Array { import runtime.BoxedArray; import scala.runtime.ScalaRunTime.boxArray; - implicit def builderFactory[A]: BuilderFactory[A, Array[A], Coll] = new BuilderFactory[A, Array[A], Coll] { def apply(from: Coll) = newBuilder[A] } - def newBuilder[A]: Builder[A, Array[A]] = new ArrayBuffer[A].mapResult(_.toArray) + implicit def builderFactory[A]/* !!!(implicit m: ClassManifest[A])*/: BuilderFactory[A, Array[A], Array[_]] = + new BuilderFactory[A, Array[A], Array[_]] { def apply(from: Array[_]) = newBuilder[A](null) } + + def newBuilder[A](implicit m: ClassManifest[A]): Builder[A, Array[A]] = + new ArrayBuilder[A](m).asInstanceOf[Builder[A, Array[A]]] // the cast is safe, because the erasure of Array[A] is BoxedArray[A] private def slowcopy( src : AnyRef, @@ -64,32 +69,15 @@ object Array extends SequenceFactory[Array] { slowcopy(src, srcPos, dest, destPos, length) } - /** Concatenate all argument sequences into a single array. - * - * @param xs the given argument sequences - * @return the array created from the concatenated arguments - */ - def concat[T](xs: Seq[T]*): Array[T] = { - var len = 0 - for (x <- xs) len += x.length - val result = new Array[T](len) - var start = 0 - for (x <- xs) { - copy(x.toArray, 0, result, start, x.length) - start += x.length - } - result - } - /** Returns array of length 0 */ - override def empty[A]: Array[A] = new Array[A](0) + def empty[A: ClassManifest]: Array[A] = new Array[A](0) /** Create an array with given elements. * * @param xs the elements to put in the array * @return the array containing elements xs. */ - override def apply[A](xs: A*): Array[A] = { + def apply[A: ClassManifest](xs: A*): Array[A] = { val array = new Array[A](xs.length) var i = 0 for (x <- xs.iterator) { array(i) = x; i += 1 } @@ -160,17 +148,186 @@ object Array extends SequenceFactory[Array] { } /** Create array with given dimensions */ - def ofDim[A](n1: Int): Array[A] = + def ofDim[A: ClassManifest](n1: Int): Array[A] = new Array[A](n1) - def ofDim[A](n1: Int, n2: Int): Array[Array[A]] = + def ofDim[A: ClassManifest](n1: Int, n2: Int): Array[Array[A]] = tabulate(n1)(_ => ofDim[A](n2)) - def ofDim[A](n1: Int, n2: Int, n3: Int): Array[Array[Array[A]]] = + def ofDim[A: ClassManifest](n1: Int, n2: Int, n3: Int): Array[Array[Array[A]]] = tabulate(n1)(_ => ofDim[A](n2, n3)) - def ofDim[A](n1: Int, n2: Int, n3: Int, n4: Int): Array[Array[Array[Array[A]]]] = + def ofDim[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int): Array[Array[Array[Array[A]]]] = tabulate(n1)(_ => ofDim[A](n2, n3, n4)) - def ofDim[A](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int): Array[Array[Array[Array[Array[A]]]]] = + def ofDim[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int): Array[Array[Array[Array[Array[A]]]]] = tabulate(n1)(_ => ofDim[A](n2, n3, n4, n5)) + /** Concatenate all argument sequences into a single array. + * + * @param xs the given argument sequences + * @return the array created from the concatenated arguments + */ + def concat[A: ClassManifest](xss: Traversable[A]*): Array[A] = { + val b = newBuilder[A] + b.sizeHint(xss.map(_.size).sum) + for (xs <- xss) b ++= xs + b.result + } + + /** An array that contains the results of some element computation a number of times. + * @param n the number of elements returned + * @param elem the element computation + */ + def fill[A: ClassManifest](n: Int)(elem: => A): Array[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += elem + i += 1 + } + b.result + } + + /** A two-dimensional array that contains the results of some element computation a number of times. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param elem the element computation + */ + def fill[A: ClassManifest](n1: Int, n2: Int)(elem: => A): Array[Array[A]] = + tabulate(n1)(_ => fill(n2)(elem)) + + /** A three-dimensional array that contains the results of some element computation a number of times. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param elem the element computation + */ + def fill[A: ClassManifest](n1: Int, n2: Int, n3: Int)(elem: => A): Array[Array[Array[A]]] = + tabulate(n1)(_ => fill(n2, n3)(elem)) + + /** A four-dimensional array that contains the results of some element computation a number of times. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param n4 the number of elements in the 4th dimension + * @param elem the element computation + */ + def fill[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int)(elem: => A): Array[Array[Array[Array[A]]]] = + tabulate(n1)(_ => fill(n2, n3, n4)(elem)) + + /** A five-dimensional array that contains the results of some element computation a number of times. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param n4 the number of elements in the 4th dimension + * @param n5 the number of elements in the 5th dimension + * @param elem the element computation + */ + def fill[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(elem: => A): Array[Array[Array[Array[Array[A]]]]] = + tabulate(n1)(_ => fill(n2, n3, n4, n5)(elem)) + + /** An array containing values of a given function over a range of integer values starting from 0. + * @param n The number of elements in the traversable + * @param f The function computing element values + * @return A traversable consisting of elements `f(0), ..., f(n -1)` + */ + def tabulate[A: ClassManifest](n: Int)(f: Int => A): Array[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += f(i) + i += 1 + } + b.result + } + + /** A two-dimensional array containing values of a given function over ranges of integer values starting from 0. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param f The function computing element values + */ + def tabulate[A: ClassManifest](n1: Int, n2: Int)(f: (Int, Int) => A): Array[Array[A]] = + tabulate(n1)(i1 => tabulate(n2)(f(i1, _))) + + /** A three-dimensional array containing values of a given function over ranges of integer values starting from 0. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param f The function computing element values + */ + def tabulate[A: ClassManifest](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) => A): Array[Array[Array[A]]] = + tabulate(n1)(i1 => tabulate(n2, n3)(f(i1, _, _))) + + /** A four-dimensional array containing values of a given function over ranges of integer values starting from 0. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param n4 the number of elements in the 4th dimension + * @param f The function computing element values + */ + def tabulate[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int)(f: (Int, Int, Int, Int) => A): Array[Array[Array[Array[A]]]] = + tabulate(n1)(i1 => tabulate(n2, n3, n4)(f(i1, _, _, _))) + + /** A five-dimensional array containing values of a given function over ranges of integer values starting from 0. + * @param n1 the number of elements in the 1st dimension + * @param n2 the number of elements in the 2nd dimension + * @param n3 the number of elements in the 3nd dimension + * @param n4 the number of elements in the 4th dimension + * @param n5 the number of elements in the 5th dimension + * @param f The function computing element values + */ + def tabulate[A: ClassManifest](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(f: (Int, Int, Int, Int, Int) => A): Array[Array[Array[Array[Array[A]]]]] = + tabulate(n1)(i1 => tabulate(n2, n3, n4, n5)(f(i1, _, _, _, _))) + + /** An array containing a sequence of increasing integers in a range. + * + * @param from the start value of the array + * @param end the end value of the array (the first value NOT returned) + * @return the array with values in range `start, start + 1, ..., end - 1` + * up to, but exclusding, `end`. + */ + def range(start: Int, end: Int): Array[Int] = range(start, end, 1) + + /** An array containing equally spaced values in some integer interval. + * @param start the start value of the array + * @param end the end value of the array (the first value NOT returned) + * @param step the increment value of the array (must be positive or negative) + * @return the array with values in `start, start + step, ...` up to, but excluding `end` + */ + def range(start: Int, end: Int, step: Int): Array[Int] = { + if (step == 0) throw new IllegalArgumentException("zero step") + val b = newBuilder[Int] + var i = start + while (if (step < 0) end < i else i < end) { + b += i + i += step + } + b.result + } + + /** An array containing repeated applications of a function to a start value. + * + * @param start the start value of the array + * @param len the number of elements returned by the array + * @param f the function that's repeatedly applied + * @return the array returning `len` values in the sequence `start, f(start), f(f(start)), ...` + */ + def iterate[A: ClassManifest](start: A, len: Int)(f: A => A): Array[A] = { + val b = newBuilder[A] + var acc = start + var i = 0 + while (i < len) { + b += acc + acc = f(acc) + i += 1 + } + b.result + } + + /** This method is called in a pattern match { case Sequence(...) => }. + * + * @param x the selector value + * @return sequence wrapped in an option, if this is a Sequence, otherwise none + */ + def unapplySeq[A](x: Array[A]): Some[Array[A]] = Some(x) + /** Create an array containing several copies of an element. * * @param n the length of the resulting array @@ -178,7 +335,7 @@ object Array extends SequenceFactory[Array] { * @return an array composed of n elements all equal to elem */ @deprecated("use `Array.fill' instead") - def make[A](n: Int, elem: A): Array[A] = { + def make[A: ClassManifest](n: Int, elem: A): Array[A] = { val a = new Array[A](n) var i = 0 while (i < n) { @@ -192,7 +349,7 @@ object Array extends SequenceFactory[Array] { * over given range [0..n) */ @deprecated("use `Array.tabulate' instead") - def fromFunction[A](f: Int => A)(n: Int): Array[A] = { + def fromFunction[A: ClassManifest](f: Int => A)(n: Int): Array[A] = { val a = new Array[A](n) var i = 0 while (i < n) { @@ -206,28 +363,28 @@ object Array extends SequenceFactory[Array] { * over given range [0..n1, 0..n2) */ @deprecated("use `Array.tabulate' instead") - def fromFunction[A](f: (Int, Int) => A)(n1: Int, n2: Int): Array[Array[A]] = + def fromFunction[A: ClassManifest](f: (Int, Int) => A)(n1: Int, n2: Int): Array[Array[A]] = fromFunction(i => fromFunction(f(i, _))(n2))(n1) /** Create an array containing the values of a given function f * over given range [0..n1, 0..n2, 0..n3) */ @deprecated("use `Array.tabulate' instead") - def fromFunction[A](f: (Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int): Array[Array[Array[A]]] = + def fromFunction[A: ClassManifest](f: (Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int): Array[Array[Array[A]]] = fromFunction(i => fromFunction(f(i, _, _))(n2, n3))(n1) /** Create an array containing the values of a given function f * over given range [0..n1, 0..n2, 0..n3, 0..n4) */ @deprecated("use `Array.tabulate' instead") - def fromFunction[A](f: (Int, Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int, n4: Int): Array[Array[Array[Array[A]]]] = + def fromFunction[A: ClassManifest](f: (Int, Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int, n4: Int): Array[Array[Array[Array[A]]]] = fromFunction(i => fromFunction(f(i, _, _, _))(n2, n3, n4))(n1) /** Create an array containing the values of a given function f * over given range [0..n1, 0..n2, 0..n3, 0..n4, 0..n5) */ @deprecated("use `Array.tabulate' instead") - def fromFunction[A](f: (Int, Int, Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int, n4: Int, n5: Int): Array[Array[Array[Array[Array[A]]]]] = + def fromFunction[A: ClassManifest](f: (Int, Int, Int, Int, Int) => A)(n1: Int, n2: Int, n3: Int, n4: Int, n5: Int): Array[Array[Array[Array[Array[A]]]]] = fromFunction(i => fromFunction(f(i, _, _, _, _))(n2, n3, n4, n5))(n1) } @@ -337,9 +494,21 @@ final class Array[A](_length: Int) extends Vector[A] */ override def update(i: Int, x: A) { throw new Error() } + /** Creates a possible nested vector which consists of all the elements + * of this array. If the elements are arrays themselves, the `deep' transformation + * is applied recursively to them. The stringPrefix of the vector is + * "Array", hence the vector prints like an array with all its + * elements shown, and the same recursively for any subarrays. + * + * Example: Array(Array(1, 2), Array(3, 4)).deep.toString + * prints: Array(Array(1, 2), Array(3, 4)) + */ + def deep: Vector[Any] = throw new Error() + /** * @return a deep string representation of this array. */ + @deprecated("use deep.toString instead") def deepToString(): String = throw new Error() /**

@@ -358,6 +527,7 @@ final class Array[A](_length: Int) extends Vector[A] * @param end ending string. * @return a string representation of this array object. */ + @deprecated("use deep.mkString instead") def deepMkString(start: String, sep: String, end: String): String = throw new Error() @@ -368,6 +538,7 @@ final class Array[A](_length: Int) extends Vector[A] * @param sep separator string. * @return a string representation of this array object. */ + @deprecated("use deep.mkString instead") def deepMkString(sep: String): String = throw new Error() /**

@@ -389,8 +560,6 @@ final class Array[A](_length: Int) extends Vector[A] * @param that the second * @return true iff both arrays are deeply equal. */ + @deprecated("use array1.deep.equals(array2.deep) instead") def deepEquals(that: Any): Boolean = throw new Error() - - @deprecated("use `slice' instead") - def subArray(from: Int, end: Int): Array[A] = throw new Error() } diff --git a/src/library/scala/collection/JavaConversions.scala b/src/library/scala/collection/JavaConversions.scala index 7bc774c066..a353af7313 100644 --- a/src/library/scala/collection/JavaConversions.scala +++ b/src/library/scala/collection/JavaConversions.scala @@ -52,7 +52,7 @@ package scala.collection object JavaConversions { import java.{ lang => jl, util => ju } import scala.collection.{ generic, immutable, mutable, Traversable } - import scala.reflect.Manifest + import scala.reflect.ClassManifest // Scala => Java @@ -157,7 +157,7 @@ object JavaConversions { * @param s The Set to be converted. * @return A Java Set view of the argument. */ - implicit def asSet[A](s : mutable.Set[A])(implicit m : Manifest[A]) : ju.Set[A] = s match { + implicit def asSet[A](s : mutable.Set[A])(implicit m : ClassManifest[A]) : ju.Set[A] = s match { case JSetWrapper(wrapped) => wrapped case _ => new MutableSetWrapper(s)(m) } @@ -175,7 +175,7 @@ object JavaConversions { * @param m The Map to be converted. * @return A Java Map view of the argument. */ - implicit def asMap[A, B](m : mutable.Map[A, B])(implicit ma : Manifest[A]) : ju.Map[A, B] = m match { + implicit def asMap[A, B](m : mutable.Map[A, B])(implicit ma : ClassManifest[A]) : ju.Map[A, B] = m match { case JMapWrapper(wrapped) => wrapped case _ => new MutableMapWrapper(m)(ma) } @@ -365,7 +365,7 @@ object JavaConversions { def result = this } - case class MutableSetWrapper[A](underlying : mutable.Set[A])(m : Manifest[A]) extends ju.AbstractSet[A] { + case class MutableSetWrapper[A](underlying : mutable.Set[A])(m : ClassManifest[A]) extends ju.AbstractSet[A] { self => def size = underlying.size override def add(elem: A) = { val sz = underlying.size ; underlying += elem ; sz < underlying.size } @@ -408,7 +408,7 @@ object JavaConversions { override def empty = JSetWrapper(new ju.HashSet[A]) } - case class MutableMapWrapper[A, B](underlying : mutable.Map[A, B])(m : Manifest[A]) extends ju.AbstractMap[A, B] { + case class MutableMapWrapper[A, B](underlying : mutable.Map[A, B])(m : ClassManifest[A]) extends ju.AbstractMap[A, B] { self => override def size = underlying.size diff --git a/src/library/scala/collection/Traversable.scala b/src/library/scala/collection/Traversable.scala index 1a8ca8a621..d527836603 100644 --- a/src/library/scala/collection/Traversable.scala +++ b/src/library/scala/collection/Traversable.scala @@ -74,7 +74,7 @@ trait Traversable[+A] extends TraversableTemplate[A, Traversable[A]] override def copyToBuffer[B >: A](dest: Buffer[B]) override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) override def copyToArray[B >: A](xs: Array[B], start: Int) - override def toArray[B >: A]: Array[B] + override def toArray[B >: A : ClassManifest]: Array[B] override def toList: List[A] override def toIterable: Iterable[A] override def toSequence: Sequence[A] @@ -102,64 +102,5 @@ object Traversable extends TraversableFactory[Traversable] { self => implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Traversable[A]] = immutable.Traversable.newBuilder[A] - - /** A wrapper class which adds `flatten` and `transpose` methods to iterables or iterable element type`. - */ - class TraversableTraversableOps[This <: Traversable[Traversable[A]], A](self: This) { - - /** Returns the concatenation of all elements of the wrapped iterable `self` */ - def flatten[That](implicit bf: BuilderFactory[A, That, This]): That = { - val b = bf(self) - for (xs <- self) - b ++= xs - b.result - } - - /** Returns the transposition of the wrapped iterable `self`: rows become columns and columns become rows. - */ - def transpose[Row, That](implicit bf: BuilderFactory[A, Row, This], bbf: BuilderFactory[Row, That, This]): That = { - val bs: Array[Builder[A, Row]] = self.head.map(_ => bf(self))(Traversable.builderFactory[Builder[A, Row]]).toArray - for (xs <- self) { - var i = 0 - for (x <- xs) { - bs(i) += x - i += 1 - } - } - val bb = bbf(self) - for (b <- bs) bb += b.result - bb.result - } - } - - /** A wrapper class which adds an `unzip` method to iterable whose elements are pairs. - */ - class PairTraversableOps[This <: Traversable[(A1, A2)], A1, A2](self: This) { - - /** Returns a pair of iterables consisting of the first, respectively second, component of all - * elements in the wrapped iterable `self`. - */ - def unzip[That1, That2](implicit bf1: BuilderFactory[A1, That1, This], bf2: BuilderFactory[A2, That2, This]): (That1, That2) = { - val b1 = bf1(self) - val b2 = bf2(self) - for ((x1, x2) <- self) { - b1 += x1 - b2 += x2 - } - (b1.result, b2.result) - } - } - - /** Implicit wrapper conversion of iterables with iterable elements. - * @see TraversableTraversableOps - */ - implicit def traversableTraversableWrapper[This <: Traversable[Traversable[A]], A](self: This) = - new TraversableTraversableOps[This, A](self) // !!! error if type parameters are omitted - - /** Implicit wrapper conversion of iterables with pairs as elements. - * @see PairTraversableOps - */ - implicit def pairTraversableWrapper[This <: Traversable[(A1, A2)], A1, A2](self: This) = - new PairTraversableOps[This, A1, A2](self) } diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index eaa00c18d2..b436c990c6 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -11,6 +11,7 @@ package scala.collection.generic import scala.collection._ +import annotation.unchecked.uncheckedVariance import mutable.{ListBuffer, HashMap} @@ -593,7 +594,7 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] * .sortWith((e1, e2) => (e1 compareTo e2) < 0) = * List("Bob", "John", "Steve", "Tom") */ - def sortWith(lt: (A, A) => Boolean): This = { + def sortWith(lt: (A, A) => Boolean)(implicit m: ClassManifest[A @uncheckedVariance]): This = { val arr = toArray import java.util.{Arrays, Comparator} Arrays.sort(arr, new Comparator[A] { diff --git a/src/library/scala/collection/generic/TraversableClass.scala b/src/library/scala/collection/generic/TraversableClass.scala index 6d6d445d88..4d0e44e0d6 100644 --- a/src/library/scala/collection/generic/TraversableClass.scala +++ b/src/library/scala/collection/generic/TraversableClass.scala @@ -29,29 +29,29 @@ trait TraversableClass[+A, +CC[X] <: Traversable[X]] { /** The generic builder that builds instances of CC at arbitrary element types. */ def genericBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B] - def unzip[A1, A2](implicit toPair: A => (A1, A2)): (CC[A1], CC[A2]) = { + def unzip[A1, A2](implicit asPair: A => /*<: Traversable[B]): CC[B] = { + def flatten[B](implicit asTraversable: A => /*<: Traversable[B]): CC[CC[B] @uncheckedVariance] = { - val bs: Array[Builder[B, CC[B]]] = head.map(_ => genericBuilder[B]).toArray + def transpose[B](implicit asTraversable: A => /*<: genericBuilder[B]).toVector for (xs <- this) { var i = 0 - for (x <- toTraversable(xs)) { + for (x <- asTraversable(xs)) { bs(i) += x i += 1 } diff --git a/src/library/scala/collection/generic/TraversableFactory.scala b/src/library/scala/collection/generic/TraversableFactory.scala index b91556333a..1b20fb40a8 100644 --- a/src/library/scala/collection/generic/TraversableFactory.scala +++ b/src/library/scala/collection/generic/TraversableFactory.scala @@ -34,7 +34,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ b.result } - /** An iterable that contains the results of some element computation a number of times. + /** A traversable that contains the results of some element computation a number of times. * @param n the number of elements returned * @param elem the element computation */ @@ -48,7 +48,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ b.result } - /** A two-dimensional iterable that contains the results of some element computation a number of times. + /** A two-dimensional traversable that contains the results of some element computation a number of times. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param elem the element computation @@ -56,7 +56,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def fill[A](n1: Int, n2: Int)(elem: => A): CC[CC[A]] = tabulate(n1)(_ => fill(n2)(elem)) - /** A three-dimensional iterable that contains the results of some element computation a number of times. + /** A three-dimensional traversable that contains the results of some element computation a number of times. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -65,7 +65,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def fill[A](n1: Int, n2: Int, n3: Int)(elem: => A): CC[CC[CC[A]]] = tabulate(n1)(_ => fill(n2, n3)(elem)) - /** A four-dimensional iterable that contains the results of some element computation a number of times. + /** A four-dimensional traversable that contains the results of some element computation a number of times. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -75,7 +75,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def fill[A](n1: Int, n2: Int, n3: Int, n4: Int)(elem: => A): CC[CC[CC[CC[A]]]] = tabulate(n1)(_ => fill(n2, n3, n4)(elem)) - /** A five-dimensional iterable that contains the results of some element computation a number of times. + /** A five-dimensional traversable that contains the results of some element computation a number of times. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -86,10 +86,10 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def fill[A](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(elem: => A): CC[CC[CC[CC[CC[A]]]]] = tabulate(n1)(_ => fill(n2, n3, n4, n5)(elem)) - /** An iterable containing values of a given function over a range of integer values starting from 0. - * @param n The number of elements in the iterable + /** A traversable containing values of a given function over a range of integer values starting from 0. + * @param n The number of elements in the traversable * @param f The function computing element values - * @return An iterable consisting of elements `f(0), ..., f(n -1)` + * @return A traversable consisting of elements `f(0), ..., f(n -1)` */ def tabulate[A](n: Int)(f: Int => A): CC[A] = { val b = newBuilder[A] @@ -101,7 +101,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ b.result } - /** A two-dimensional iterable containing values of a given function over ranges of integer values starting from 0. + /** A two-dimensional traversable containing values of a given function over ranges of integer values starting from 0. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param f The function computing element values @@ -109,7 +109,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def tabulate[A](n1: Int, n2: Int)(f: (Int, Int) => A): CC[CC[A]] = tabulate(n1)(i1 => tabulate(n2)(f(i1, _))) - /** A three-dimensional iterable containing values of a given function over ranges of integer values starting from 0. + /** A three-dimensional traversable containing values of a given function over ranges of integer values starting from 0. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -118,7 +118,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def tabulate[A](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) => A): CC[CC[CC[A]]] = tabulate(n1)(i1 => tabulate(n2, n3)(f(i1, _, _))) - /** A four-dimensional iterable containing values of a given function over ranges of integer values starting from 0. + /** A four-dimensional traversable containing values of a given function over ranges of integer values starting from 0. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -128,7 +128,7 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def tabulate[A](n1: Int, n2: Int, n3: Int, n4: Int)(f: (Int, Int, Int, Int) => A): CC[CC[CC[CC[A]]]] = tabulate(n1)(i1 => tabulate(n2, n3, n4)(f(i1, _, _, _))) - /** A five-dimensional iterable containing values of a given function over ranges of integer values starting from 0. + /** A five-dimensional traversable containing values of a given function over ranges of integer values starting from 0. * @param n1 the number of elements in the 1st dimension * @param n2 the number of elements in the 2nd dimension * @param n3 the number of elements in the 3nd dimension @@ -139,21 +139,20 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ def tabulate[A](n1: Int, n2: Int, n3: Int, n4: Int, n5: Int)(f: (Int, Int, Int, Int, Int) => A): CC[CC[CC[CC[CC[A]]]]] = tabulate(n1)(i1 => tabulate(n2, n3, n4, n5)(f(i1, _, _, _, _))) - /** An iterable containing a sequence of increasing integers in a range. + /** A traversable containing a sequence of increasing integers in a range. * - * @param from the start value of the iterable - * @param end the end value of the iterable (the first value NOT returned) - * @return the iterable with values in range `start, start + 1, ..., end - 1` + * @param from the start value of the traversable + * @param end the end value of the traversable (the first value NOT returned) + * @return the traversable with values in range `start, start + 1, ..., end - 1` * up to, but exclusding, `end`. */ - def range[A](start: Int, end: Int): CC[Int] = range(start, end, 1) + def range(start: Int, end: Int): CC[Int] = range(start, end, 1) - /** An iterable containing equally spaced values in some integer interval. - - * @param start the start value of the iterable - * @param end the end value of the iterable (the first value NOT returned) - * @param step the increment value of the iterable (must be positive or negative) - * @return the iterable with values in `start, start + step, ...` up to, but excluding `end` + /** A traversable containing equally spaced values in some integer interval. + * @param start the start value of the traversable + * @param end the end value of the traversable (the first value NOT returned) + * @param step the increment value of the traversable (must be positive or negative) + * @return the traversable with values in `start, start + step, ...` up to, but excluding `end` */ def range(start: Int, end: Int, step: Int): CC[Int] = { if (step == 0) throw new IllegalArgumentException("zero step") @@ -166,12 +165,12 @@ abstract class TraversableFactory[CC[X] <: Traversable[X] with TraversableClass[ b.result } - /** An iterable containing repeated applications of a function to a start value. + /** A traversable containing repeated applications of a function to a start value. * - * @param start the start value of the iterable - * @param len the number of elements returned by the iterable + * @param start the start value of the traversable + * @param len the number of elements returned by the traversable * @param f the function that's repeatedly applied - * @return the iterable returning `len` values in the sequence `start, f(start), f(f(start)), ...` + * @return the traversable returning `len` values in the sequence `start, f(start), f(f(start)), ...` */ def iterate[A](start: A, len: Int)(f: A => A): CC[A] = { val b = newBuilder[A] diff --git a/src/library/scala/collection/generic/TraversableForwarder.scala b/src/library/scala/collection/generic/TraversableForwarder.scala index eff1bef8a1..4760413fbd 100644 --- a/src/library/scala/collection/generic/TraversableForwarder.scala +++ b/src/library/scala/collection/generic/TraversableForwarder.scala @@ -59,7 +59,7 @@ trait TraversableForwarder[+A] extends Traversable[A] { override def reduceRightOption[B >: A](op: (A, B) => B): Option[B] = underlying.reduceRightOption(op) override def copyToBuffer[B >: A](dest: Buffer[B]) = underlying.copyToBuffer(dest) override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) = underlying.copyToArray(xs, start, len) - override def toArray[B >: A]: Array[B] = underlying.toArray + override def toArray[B >: A : ClassManifest]: Array[B] = underlying.toArray override def toList: List[A] = underlying.toList override def toSequence: Sequence[A] = underlying.toSequence override def toStream: Stream[A] = underlying.toStream diff --git a/src/library/scala/collection/generic/TraversableProxyTemplate.scala b/src/library/scala/collection/generic/TraversableProxyTemplate.scala index b44f6c230d..ae711b9260 100644 --- a/src/library/scala/collection/generic/TraversableProxyTemplate.scala +++ b/src/library/scala/collection/generic/TraversableProxyTemplate.scala @@ -68,7 +68,7 @@ trait TraversableProxyTemplate[+A, +This <: TraversableTemplate[A, This] with Tr override def copyToBuffer[B >: A](dest: Buffer[B]) = self.copyToBuffer(dest) override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) = self.copyToArray(xs, start, len) override def copyToArray[B >: A](xs: Array[B], start: Int) = self.copyToArray(xs, start) - override def toArray[B >: A]: Array[B] = self.toArray + override def toArray[B >: A: ClassManifest]: Array[B] = self.toArray override def toList: List[A] = self.toList override def toIterable: Iterable[A] = self.toIterable override def toSequence: Sequence[A] = self.toSequence diff --git a/src/library/scala/collection/generic/TraversableTemplate.scala b/src/library/scala/collection/generic/TraversableTemplate.scala index 2e808145cd..c57e6c7d50 100644 --- a/src/library/scala/collection/generic/TraversableTemplate.scala +++ b/src/library/scala/collection/generic/TraversableTemplate.scala @@ -11,6 +11,7 @@ package scala.collection.generic import scala.collection._ +import scala.reflect.ClassManifest // import immutable.{List, Stream, Nil} //!!! import mutable.{Buffer, ArrayBuffer, ListBuffer} @@ -718,7 +719,7 @@ self => /** Converts this traversable to a fresh Array containing all elements. * @note Will not terminate for infinite-sized collections. */ - def toArray[B >: A]: Array[B] = { + def toArray[B >: A : ClassManifest]: Array[B] = { val result = new Array[B](size) copyToArray(result, 0) result @@ -739,6 +740,11 @@ self => */ 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 diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index d122859a4a..0925ca5d27 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -171,6 +171,7 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend } } + // Overridden methods from Sequence override def lengthCompare(len: Int): Int = length - len @@ -259,6 +260,7 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend super.endsWith(that) } + override def equals(that: Any): Boolean = that match { case that: Vector[_] => this.length == that.length && startsWith(that, 0) case _ => super.equals(that) diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index e6f3d3c47c..4810b29e5a 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -370,7 +370,7 @@ self => result } - override def flatten[B](implicit toTraversable: A => Traversable[B]): Stream[B] = { + override def flatten[B](implicit asTraversable: A => /*<: if (isEmpty) Stream.empty else - flatten1(toTraversable(head)) + flatten1(asTraversable(head)) } /** Defines the prefix of this object's toString representation as ``Stream''. @@ -553,7 +553,7 @@ object Stream extends SequenceFactory[Stream] { /** The concatenation of all streams returned by an iterator */ @deprecated("use xs.toStream.flatten instead") - def concat[A](xs: Iterator[Stream[A]]): Stream[A] = xs.toStream.flatten + def concat[A](xs: Iterator[Stream[A]]): Stream[A] = xs.toStream.flatten //(conforms[Stream[A], collection.Traversable[A]]) /** * Create a stream with element values diff --git a/src/library/scala/collection/mutable/ArrayBuilder.scala b/src/library/scala/collection/mutable/ArrayBuilder.scala index 060227a327..67fb4918ea 100755 --- a/src/library/scala/collection/mutable/ArrayBuilder.scala +++ b/src/library/scala/collection/mutable/ArrayBuilder.scala @@ -23,9 +23,15 @@ class ArrayBuilder[A](manifest: ClassManifest[A]) extends Builder[A, BoxedArray[ private var size: Int = 0 private def mkArray(size: Int): BoxedArray[A] = { - val newelems = manifest.newArray(size) - if (this.size > 0) Array.copy(elems.value, 0, newelems.value, 0, this.size) - newelems + if (manifest != null) { + val newelems = manifest.newArray(size) + if (this.size > 0) Array.copy(elems.value, 0, newelems.value, 0, this.size) + newelems + } else { // !!! + val newelems = new scala.runtime.BoxedAnyArray[A](size) + if (this.size > 0) Array.copy(elems, 0, newelems, 0, this.size) + newelems + } } private def resize(size: Int) { diff --git a/src/library/scala/collection/mutable/StringBuilder.scala b/src/library/scala/collection/mutable/StringBuilder.scala index d1aaa1234d..c9e9faca84 100644 --- a/src/library/scala/collection/mutable/StringBuilder.scala +++ b/src/library/scala/collection/mutable/StringBuilder.scala @@ -14,6 +14,7 @@ package scala.collection.mutable import collection.generic._ import scala.runtime.RichString import compat.Platform.arraycopy +import scala.reflect.Manifest /**

* A mutable sequence of characters. This class provides an API compatible diff --git a/src/library/scala/reflect/ClassManifest.scala b/src/library/scala/reflect/ClassManifest.scala index bbc4e0c2cd..b3df97a50f 100644 --- a/src/library/scala/reflect/ClassManifest.scala +++ b/src/library/scala/reflect/ClassManifest.scala @@ -104,30 +104,45 @@ object ClassManifest { val Double = Manifest.Double val Boolean = Manifest.Boolean val Unit = Manifest.Unit + val Any = Manifest.Any + val AnyVal = Manifest.AnyVal + val Nothing = Manifest.Nothing + val Null = Manifest.Null def singleType[T](value: Any): Manifest[T] = Manifest.singleType(value) + /** ClassManifest for the class type `clazz', where `clazz' is + * a top-level or static class. + * @note This no-prefix, no-arguments case is separate because we + * it's called from ScalaRunTime.boxArray itself. If we + * pass varargs as arrays into this, we get an infinitely recursive call + * to boxArray. (Besides, having a separate case is more efficient) + */ + def classType[T](clazz: Predef.Class[_]): ClassManifest[T] = + new ClassTypeManifest[T](None, clazz, Nil) + /** ClassManifest for the class type `clazz[args]', where `clazz' is - * a top-level or static class. */ - def classType[T](clazz: Predef.Class[_], args: OptManifest[_]*): ClassManifest[T] = - classType(None, clazz, args: _*) + * a top-level or static class and `args` are its type arguments */ + def classType[T](clazz: Predef.Class[_], arg1: OptManifest[_], args: OptManifest[_]*): ClassManifest[T] = + new ClassTypeManifest[T](None, clazz, arg1 :: args.toList) /** ClassManifest for the class type `clazz[args]', where `clazz' is - * a top-level or static class. */ + * a class with non-package prefix type `prefix` and type arguments `args`. + */ def classType[T](prefix: OptManifest[_], clazz: Predef.Class[_], args: OptManifest[_]*): ClassManifest[T] = - classType(Some(prefix), clazz, args: _*) + new ClassTypeManifest[T](Some(prefix), clazz, args.toList) - /** ClassManifest for the class type `clazz[args]', where `clazz' is + /** Manifest for the class type `clazz[args]', where `clazz' is * a top-level or static class. */ - def classType[T](prefix: Option[OptManifest[_]], clazz: Predef.Class[_], args: OptManifest[_]*): ClassManifest[T] = - new (ClassManifest[T] @serializable) { - def erasure = clazz - override val typeArguments = args.toList - override def toString = - (if (prefix.isEmpty) "" else prefix.get.toString+"#") + - (if (erasure.isArray) "Array" else erasure.getName) + - argString - } + @serializable + private class ClassTypeManifest[T](prefix: Option[OptManifest[_]], + val erasure: Predef.Class[_], + override val typeArguments: List[OptManifest[_]]) extends ClassManifest[T] { + override def toString = + (if (prefix.isEmpty) "" else prefix.get.toString+"#") + + (if (erasure.isArray) "Array" else erasure.getName) + + argString + } /** ClassManifest for the abstract type `prefix # name'. `upperBound' is not * strictly necessary as it could be obtained by reflection. It was diff --git a/src/library/scala/reflect/Manifest.scala b/src/library/scala/reflect/Manifest.scala index 161e60d6d8..e83061856b 100644 --- a/src/library/scala/reflect/Manifest.scala +++ b/src/library/scala/reflect/Manifest.scala @@ -95,6 +95,26 @@ object Manifest { override def newArray(len: Int): BoxedArray[Unit] = new BoxedUnitArray(new Array[Unit](len)) } + val Any: Manifest[Any] = new ClassTypeManifest[Any](None, classOf[java.lang.Object], List()) { + override def toString = "Any" + // todo: re-implement <:< + } + + val AnyVal: Manifest[AnyVal] = new ClassTypeManifest[AnyVal](None, classOf[java.lang.Object], List()) { + override def toString = "AnyVal" + // todo: re-implement <:< + } + + val Null: Manifest[Null] = new ClassTypeManifest[Null](None, classOf[java.lang.Object], List()) { + override def toString = "Null" + // todo: re-implement <:< + } + + val Nothing: Manifest[Nothing] = new ClassTypeManifest[Nothing](None, classOf[java.lang.Object], List()) { + override def toString = "Nothing" + // todo: re-implement <:< + } + /** Manifest for the singleton type `value.type'. */ def singleType[T](value: Any): Manifest[T] = new (Manifest[T] @serializable) { @@ -106,27 +126,38 @@ object Manifest { override lazy val toString = value.toString + ".type" } + /** Manifest for the class type `clazz[args]', where `clazz' is + * a top-level or static class. + * @note This no-prefix, no-arguments case is separate because we + * it's called from ScalaRunTime.boxArray itself. If we + * pass varargs as arrays into this, we get an infinitely recursive call + * to boxArray. (Besides, having a separate case is more efficient) + */ + def classType[T](clazz: Predef.Class[_]): Manifest[T] = + new ClassTypeManifest[T](None, clazz, Nil) + /** Manifest for the class type `clazz', where `clazz' is - * a top-level or static class. */ - def classType[T](clazz: Predef.Class[T], args: Manifest[_]*): Manifest[T] = - classType(None, clazz, args: _*) + * a top-level or static class and args are its type arguments. */ + def classType[T](clazz: Predef.Class[T], arg1: Manifest[_], args: Manifest[_]*): Manifest[T] = + new ClassTypeManifest[T](None, clazz, arg1 :: args.toList) /** Manifest for the class type `clazz[args]', where `clazz' is - * a top-level or static class. */ + * a class with non-package prefix type `prefix` and type arguments `args`. + */ def classType[T](prefix: Manifest[_], clazz: Predef.Class[_], args: Manifest[_]*): Manifest[T] = - classType(Some(prefix), clazz, args: _*) + new ClassTypeManifest[T](Some(prefix), clazz, args.toList) /** Manifest for the class type `clazz[args]', where `clazz' is * a top-level or static class. */ - def classType[T](prefix: Option[Manifest[_]], clazz: Predef.Class[_], args: Manifest[_]*): Manifest[T] = - new (Manifest[T] @serializable) { - def erasure = clazz - override val typeArguments = args.toList - override def toString = - (if (prefix.isEmpty) "" else prefix.get.toString+"#") + - (if (erasure.isArray) "Array" else erasure.getName) + - argString - } + @serializable + private class ClassTypeManifest[T](prefix: Option[Manifest[_]], + val erasure: Predef.Class[_], + override val typeArguments: List[Manifest[_]]) extends Manifest[T] { + override def toString = + (if (prefix.isEmpty) "" else prefix.get.toString+"#") + + (if (erasure.isArray) "Array" else erasure.getName) + + argString + } /** Manifest for the abstract type `prefix # name'. `upperBound' is not * strictly necessary as it could be obtained by reflection. It was diff --git a/src/library/scala/reflect/NoManifest.scala b/src/library/scala/reflect/NoManifest.scala index 06c13c9b32..015712858f 100644 --- a/src/library/scala/reflect/NoManifest.scala +++ b/src/library/scala/reflect/NoManifest.scala @@ -14,4 +14,6 @@ package scala.reflect /**

One of the branches of an OptManifest */ @serializable -object NoManifest extends OptManifest[Nothing] +object NoManifest extends OptManifest[Nothing] { + override def toString = "" +} diff --git a/src/library/scala/runtime/BoxedArray.scala b/src/library/scala/runtime/BoxedArray.scala index 7c7798d866..c626f685d3 100644 --- a/src/library/scala/runtime/BoxedArray.scala +++ b/src/library/scala/runtime/BoxedArray.scala @@ -45,33 +45,9 @@ abstract class BoxedArray[A] extends Vector[A] with VectorTemplate[A, BoxedArray // !!! todo: remove override def genericBuilder[B]: Builder[B, BoxedArray[B]] = new ArrayBuffer[B].mapResult { - _.toArray.asInstanceOf[BoxedArray[B]] + _.toArray(null).asInstanceOf[BoxedArray[B]] } - /** Creates a possible nested vector which consists of all the elements - * of this array. If the elements are arrays themselves, the `deep' transformation - * is applied recursively to them. The stringPrefix of the vector is - * "Array", hence the vector prints like an array with all its - * elements shown, and the same recursively for any subarrays. - * - * Example: Array(Array(1, 2), Array(3, 4)).deep.toString - * prints: Array(Array(1, 2), Array(3, 4)) - */ - def deep: collection.Vector[Any] = new collection.Vector[Any] { - def length = self.length - def apply(idx: Int): Any = self.apply(idx) match { - case elem: AnyRef if ScalaRunTime.isArray(elem) => ScalaRunTime.boxArray(elem).deep - case elem => elem - } - override def stringPrefix = "Array" - } - - /* - override def genericBuilder[B]: Builder[B, BoxedArray[B]] = new ArrayBuffer[B].mapResult { - _.toArray.asInstanceOf[BoxedArray[B]] - } - */ - /** Convert to Java array. * @param elemTag Either one of the tags ".N" where N is the name of a primitive type * (@see ScalaRunTime), or a full class name. @@ -88,6 +64,12 @@ abstract class BoxedArray[A] extends Vector[A] with VectorTemplate[A, BoxedArray def copyTo(from: Int, dest: AnyRef, to: Int, len: Int): Unit = { Array.copy(value, from, dest, to, len) } + + override def toArray[B >: A](implicit m: ClassManifest[B]): Array[B] = { + if ((elemManifest ne null) && (elemManifest.erasure eq m.erasure)) this.asInstanceOf[Array[B]] + else super.toArray[B] + } + /* override def equals(other: Any) = (value eq other) || @@ -106,6 +88,24 @@ abstract class BoxedArray[A] extends Vector[A] with VectorTemplate[A, BoxedArray override def copyToArray[B](xs: Array[B], start: Int, len: Int): Unit = copyTo(0, xs, start, len) + /** Creates a possible nested vector which consists of all the elements + * of this array. If the elements are arrays themselves, the `deep' transformation + * is applied recursively to them. The stringPrefix of the vector is + * "Array", hence the vector prints like an array with all its + * elements shown, and the same recursively for any subarrays. + * + * Example: Array(Array(1, 2), Array(3, 4)).deep.toString + * prints: Array(Array(1, 2), Array(3, 4)) + */ + def deep: collection.Vector[Any] = new collection.Vector[Any] { + def length = self.length + def apply(idx: Int): Any = self.apply(idx) match { + case elem: AnyRef if ScalaRunTime.isArray(elem) => ScalaRunTime.boxArray(elem).deep + case elem => elem + } + override def stringPrefix = "Array" + } + @deprecated("use deep.toString instead") final def deepToString() = deepMkString(stringPrefix + "(", ", ", ")") diff --git a/src/library/scala/runtime/BoxedObjectArray.scala b/src/library/scala/runtime/BoxedObjectArray.scala index c778a9291b..b2f3380417 100644 --- a/src/library/scala/runtime/BoxedObjectArray.scala +++ b/src/library/scala/runtime/BoxedObjectArray.scala @@ -17,7 +17,8 @@ import Predef._ @serializable final class BoxedObjectArray[A <: AnyRef](val value: Array[AnyRef], val elemManifest: ClassManifest[A]) extends BoxedArray[A] { - def this(value: Array[AnyRef]) = this(value, null) // !!! todo: remove +// @deprecated("creating array w/o manifest") + def this(value: Array[AnyRef]) = this(value, null) // !!! todo: remove def length: Int = value.length diff --git a/src/library/scala/runtime/RichString.scala b/src/library/scala/runtime/RichString.scala index 6d36237359..1be546a902 100644 --- a/src/library/scala/runtime/RichString.scala +++ b/src/library/scala/runtime/RichString.scala @@ -31,7 +31,7 @@ object RichString { import RichString._ -class RichString(val self: String) extends Proxy with Vector[Char] with VectorTemplate[Char, RichString] with PartialFunction[Int, Char] with Ordered[String] { +class RichString(val self: String) extends Proxy with Vector[Char] with VectorTemplate[Char, RichString] with PartialFunction[Int, Char] with Ordered[String] with Boxed { /** Creates a string builder buffer as builder for this class */ override protected[this] def newBuilder = RichString.newBuilder @@ -209,11 +209,13 @@ class RichString(val self: String) extends Proxy with Vector[Char] with VectorTe else throw new NumberFormatException("For input string: \"null\"") + /* !!! causes crash? def toArray: Array[Char] = { val result = new Array[Char](length) self.getChars(0, length, result, 0) result } + */ /**

* Uses the underlying string as a pattern (in a fashion similar to @@ -230,7 +232,7 @@ class RichString(val self: String) extends Proxy with Vector[Char] with VectorTe * @throws java.lang.IllegalArgumentException */ def format(args : Any*) : String = - java.lang.String.format(self, args.toArray[Any].asInstanceOf[Array[AnyRef]]: _*) + java.lang.String.format(self, args.asInstanceOf[Seq[AnyRef]].toArray: _*) /**

* Like format(args*) but takes an initial Locale parameter @@ -247,6 +249,6 @@ class RichString(val self: String) extends Proxy with Vector[Char] with VectorTe * @throws java.lang.IllegalArgumentException */ def format(l: java.util.Locale, args: Any*): String = - java.lang.String.format(l, self, args.toArray[Any].asInstanceOf[Array[AnyRef]]: _*) + java.lang.String.format(l, self, args.asInstanceOf[Seq[AnyRef]].toArray: _*) } diff --git a/src/library/scala/runtime/ScalaRunTime.scala b/src/library/scala/runtime/ScalaRunTime.scala index 86aa61aec2..327097f61b 100644 --- a/src/library/scala/runtime/ScalaRunTime.scala +++ b/src/library/scala/runtime/ScalaRunTime.scala @@ -11,6 +11,8 @@ package scala.runtime +import scala.reflect.ClassManifest + /* The object ScalaRunTime provides ... */ object ScalaRunTime { @@ -18,6 +20,7 @@ object ScalaRunTime { def isArray(x: AnyRef): Boolean = (x != null && x.getClass.isArray) || (x != null && x.isInstanceOf[BoxedArray[_]]) def isValueClass(clazz: Class[_]) = clazz.isPrimitive() + // todo: [for Gilles] replace with boxArray def forceBoxedArray[A <: Any](xs: Seq[A]): Array[A] = { val array = new Array[A](xs.length) var i = 0 @@ -117,19 +120,33 @@ object ScalaRunTime { if (x eq null) null else x.unbox(elemClass) def boxArray(value: AnyRef): BoxedArray[_] = value match { - case x: Array[Byte] => new BoxedByteArray(x) - case x: Array[Short] => new BoxedShortArray(x) - case x: Array[Char] => new BoxedCharArray(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[Double] => new BoxedDoubleArray(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: Array[AnyRef] => new BoxedObjectArray(x) case x: BoxedArray[_] => x 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/src/library/scala/util/Marshal.scala b/src/library/scala/util/Marshal.scala index b590dddc80..63d2004769 100644 --- a/src/library/scala/util/Marshal.scala +++ b/src/library/scala/util/Marshal.scala @@ -19,9 +19,9 @@ package scala.util */ object Marshal { import java.io._ - import scala.reflect.Manifest + import scala.reflect.ClassManifest - def dump[A](o: A)(implicit m: Manifest[A]): Array[Byte] = { + def dump[A](o: A)(implicit m: ClassManifest[A]): Array[Byte] = { val ba = new ByteArrayOutputStream(512) val out = new ObjectOutputStream(ba) out.writeObject(m) @@ -33,9 +33,9 @@ object Marshal { @throws(classOf[IOException]) @throws(classOf[ClassCastException]) @throws(classOf[ClassNotFoundException]) - def load[A](buffer: Array[Byte])(implicit expected: Manifest[A]): A = { + def load[A](buffer: Array[Byte])(implicit expected: ClassManifest[A]): A = { val in = new ObjectInputStream(new ByteArrayInputStream(buffer)) - val found = in.readObject.asInstanceOf[Manifest[_]] + val found = in.readObject.asInstanceOf[ClassManifest[_]] if (found <:< expected) { val o = in.readObject.asInstanceOf[A] in.close() diff --git a/src/library/scala/util/Random.scala b/src/library/scala/util/Random.scala index 50a038b032..334c76a5db 100644 --- a/src/library/scala/util/Random.scala +++ b/src/library/scala/util/Random.scala @@ -107,7 +107,7 @@ object Random extends Random // only make it work that way if it's called like // shuffle[Int,List](List.range(0,100)) // which nicely defeats the "convenience" portion of "convenience method". - val buf: Array[T] = seq.toArray + val buf = seq.toVector def swap(i1: Int, i2: Int) { val tmp = buf(i1) diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index a7b740ce40..a7c83a5f43 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -10,6 +10,7 @@ package scala.util +import scala.reflect.ClassManifest /**

* The Sorting object provides functions that can sort various kinds of @@ -33,7 +34,7 @@ object Sorting { * items. This doesn't quite work the way that I want yet -- K should be * bounded as viewable, but the compiler rejects that. */ - implicit def seq2RichSort[K <: Ordered[K]](s: Seq[K]) = new RichSorting[K](s) + implicit def seq2RichSort[K <: Ordered[K] : ClassManifest](s: Seq[K]) = new RichSorting[K](s) /** Quickly sort an array of Doubles. */ def quickSort(a: Array[Double]) = sort1(a, 0, a.length) @@ -49,7 +50,7 @@ object Sorting { /** Sort an array of K where K is Ordered, preserving the existing order where the values are equal. */ - def stableSort[K <% Ordered[K]](a: Array[K]) { + def stableSort[K <% Ordered[K] : ClassManifest](a: Array[K]) { stableSort(a, 0, a.length-1, new Array[K](a.length), (a:K, b:K) => a < b) } @@ -57,7 +58,7 @@ object Sorting { * f. f should return true iff * its first parameter is strictly less than its second parameter. */ - def stableSort[K](a: Array[K], f: (K,K) => Boolean) { + def stableSort[K : ClassManifest](a: Array[K], f: (K,K) => Boolean) { stableSort(a, 0, a.length-1, new Array[K](a.length), f) } @@ -69,14 +70,14 @@ object Sorting { * @param f the comparison function. * @return the sorted sequence of items. */ - def stableSort[K](a: Seq[K], f: (K,K) => Boolean): Array[K] = { + def stableSort[K : ClassManifest](a: Seq[K], f: (K,K) => Boolean): Array[K] = { val ret = a.toArray stableSort(ret, f) ret } /** Sorts an arbitrary sequence of items that are viewable as ordered. */ - def stableSort[K <% Ordered[K]](a: Seq[K]): Array[K] = + def stableSort[K <% Ordered[K] : ClassManifest](a: Seq[K]): Array[K] = stableSort(a, (a:K, b:K) => a < b) /** Stably sorts a sequence of items given an extraction function that will @@ -86,7 +87,7 @@ object Sorting { * @param f the comparison function. * @return the sorted sequence of items. */ - def stableSort[K, M <% Ordered[M]](a: Seq[K], f: K => M): Array[K] = + def stableSort[K : ClassManifest, M <% Ordered[M]](a: Seq[K], f: K => M): Array[K] = stableSort(a, (a: K, b: K) => f(a) < f(b)) private def sort1[K <% Ordered[K]](x: Array[K], off: Int, len: Int) { @@ -507,7 +508,7 @@ object Sorting { sort2(off, len) } - private def stableSort[K](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) { + private def stableSort[K : ClassManifest](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) { if (lo < hi) { val mid = (lo+hi) / 2 stableSort(a, lo, mid, scratch, f) @@ -584,7 +585,7 @@ object Sorting { * the items are ordered. *

*/ -class RichSorting[K <: Ordered[K]](s: Seq[K]) { +class RichSorting[K <: Ordered[K] : ClassManifest](s: Seq[K]) { /** Returns an array with a sorted copy of the RichSorting's sequence. */ -- cgit v1.2.3