From d6db8f82138dee3c91aec21bf6f2713c17b8124c Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 4 Sep 2009 16:56:11 +0000 Subject: some changes and additions to move to new arrays. --- .../scala/tools/nsc/transform/Erasure.scala | 22 ++-- .../scala/tools/nsc/transform/UnCurry.scala | 10 +- .../collection/generic/IterableTemplate.scala | 2 +- src/library/scala/collection/generic/KMP.scala | 78 +++++++++++++++ .../generic/LinearSequenceTemplate.scala | 2 +- .../collection/generic/SequenceTemplate.scala | 82 ++------------- .../collection/generic/TraversableTemplate.scala | 111 +++++++++++---------- .../scala/collection/generic/VectorTemplate.scala | 2 +- .../scala/collection/immutable/PagedSeq.scala | 2 +- .../scala/collection/immutable/StringVector.scala | 4 +- .../scala/collection/mutable/ArrayVector.scala | 45 +++++++++ .../collection/mutable/ArrayVectorBuilder.scala | 64 ++++++++++++ .../collection/mutable/BooleanArrayVector.scala | 28 ++++++ .../scala/collection/mutable/ByteArrayVector.scala | 28 ++++++ .../scala/collection/mutable/CharArrayVector.scala | 28 ++++++ .../collection/mutable/DoubleArrayVector.scala | 28 ++++++ .../collection/mutable/FloatArrayVector.scala | 28 ++++++ .../scala/collection/mutable/IntArrayVector.scala | 28 ++++++ .../scala/collection/mutable/LongArrayVector.scala | 28 ++++++ .../collection/mutable/ObjectArrayVector.scala | 42 ++++++++ .../collection/mutable/ShortArrayVector.scala | 28 ++++++ .../scala/collection/mutable/UnitArrayVector.scala | 28 ++++++ src/library/scala/reflect/ClassManifest.scala | 6 ++ src/library/scala/reflect/Manifest.scala | 10 ++ src/library/scala/runtime/ScalaRunTime.scala | 34 ++++++- 25 files changed, 621 insertions(+), 147 deletions(-) create mode 100755 src/library/scala/collection/generic/KMP.scala create mode 100755 src/library/scala/collection/mutable/ArrayVector.scala create mode 100755 src/library/scala/collection/mutable/ArrayVectorBuilder.scala create mode 100755 src/library/scala/collection/mutable/BooleanArrayVector.scala create mode 100755 src/library/scala/collection/mutable/ByteArrayVector.scala create mode 100755 src/library/scala/collection/mutable/CharArrayVector.scala create mode 100755 src/library/scala/collection/mutable/DoubleArrayVector.scala create mode 100755 src/library/scala/collection/mutable/FloatArrayVector.scala create mode 100755 src/library/scala/collection/mutable/IntArrayVector.scala create mode 100755 src/library/scala/collection/mutable/LongArrayVector.scala create mode 100755 src/library/scala/collection/mutable/ObjectArrayVector.scala create mode 100755 src/library/scala/collection/mutable/ShortArrayVector.scala create mode 100755 src/library/scala/collection/mutable/UnitArrayVector.scala (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/transform/Erasure.scala b/src/compiler/scala/tools/nsc/transform/Erasure.scala index 9bffa01b71..b3a6d5260d 100644 --- a/src/compiler/scala/tools/nsc/transform/Erasure.scala +++ b/src/compiler/scala/tools/nsc/transform/Erasure.scala @@ -21,9 +21,10 @@ 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, typedPos} // methods to type trees + import typerXXX.{typed} // methods to type trees import CODE._ + def typedPos(pos: Position)(tree: Tree) = typed { atPos(pos)(tree) } val phaseName: String = "erasure" @@ -452,12 +453,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) } @@ -561,9 +562,12 @@ 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); - assert(args.length < 2) + val translated: Tree = + if (args.length >= 2) REF(ArrayModule) DOT nme.ofDim + else NEW(BoxedAnyArrayClass) DOT name + typedPos(tree.pos) { - Typed(Apply(NEW(BoxedAnyArrayClass) DOT name, args), tpt) + Typed(Apply(translated, 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 9b2b9e2248..7af0c4f56c 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -392,7 +392,15 @@ abstract class UnCurry extends InfoTransform with TypingTransformers { if (traversableTpe != NoType && toArray != NoSymbol) { val arguments = if (toArray.tpe.paramTypes.isEmpty) List() // !!! old style toArray - else List(localTyper.getManifestTree(tree.pos, tree.tpe.typeArgs.head, false)) // new style, with manifest + 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) { diff --git a/src/library/scala/collection/generic/IterableTemplate.scala b/src/library/scala/collection/generic/IterableTemplate.scala index e6d2652ebd..acdbc695d2 100644 --- a/src/library/scala/collection/generic/IterableTemplate.scala +++ b/src/library/scala/collection/generic/IterableTemplate.scala @@ -12,7 +12,7 @@ package scala.collection.generic import scala.collection._ import annotation.unchecked.uncheckedVariance -import util.control.Breaks._ +import scala.util.control.Breaks._ // import immutable.Stream // !!! /**

diff --git a/src/library/scala/collection/generic/KMP.scala b/src/library/scala/collection/generic/KMP.scala new file mode 100755 index 0000000000..8da2cec274 --- /dev/null +++ b/src/library/scala/collection/generic/KMP.scala @@ -0,0 +1,78 @@ +package scala.collection.generic + +/** KMP implementation, based on the undoubtedly reliable wikipedia entry + * @author paulp + */ +object KMP { + + private def KMP[B](S: Seq[B], W: Seq[B]): Option[Int] = { + // trivial cases + if (W.isEmpty) return Some(0) + else if (W drop 1 isEmpty) return (S indexOf W(0)) match { + case -1 => None + case x => Some(x) + } + + val T: Array[Int] = { + val arr = new Array[Int](W.length) + var pos = 2 + var cnd = 0 + arr(0) = -1 + arr(1) = 0 + while (pos < W.length) { + if (W(pos - 1) == W(cnd)) { + arr(pos) = cnd + 1 + pos += 1 + cnd += 1 + } + else if (cnd > 0) { + cnd = arr(cnd) + } + else { + arr(pos) = 0 + pos += 1 + } + } + arr + } + + var m, i = 0 + def mi = m + i + + while (mi < S.length) { + if (W(i) == S(mi)) { + i += 1 + if (i == W.length) + return Some(m) + } + else { + m = mi - T(i) + if (i > 0) + i = T(i) + } + } + None + } + + def indexOf[B]( + source: Seq[B], sourceOffset: Int, sourceCount: Int, + target: Seq[B], targetOffset: Int, targetCount: Int, + fromIndex: Int): Int = + KMP(source.slice(sourceOffset, sourceCount) drop fromIndex, target.slice(targetOffset, targetCount)) match { + case None => -1 + case Some(x) => x + fromIndex + } + + def lastIndexOf[B]( + source: Seq[B], sourceOffset: Int, sourceCount: Int, + target: Seq[B], targetOffset: Int, targetCount: Int, + fromIndex: Int): Int = { + val src = (source.slice(sourceOffset, sourceCount) take fromIndex).reverse + val tgt = target.slice(targetOffset, targetCount).reverse + + KMP(src, tgt) match { + case None => -1 + case Some(x) => (src.length - tgt.length - x) + sourceOffset + } + } +} diff --git a/src/library/scala/collection/generic/LinearSequenceTemplate.scala b/src/library/scala/collection/generic/LinearSequenceTemplate.scala index c35bc57bac..b0f68022b5 100644 --- a/src/library/scala/collection/generic/LinearSequenceTemplate.scala +++ b/src/library/scala/collection/generic/LinearSequenceTemplate.scala @@ -15,7 +15,7 @@ import scala.collection._ import mutable.ListBuffer // import immutable.{List, Nil, ::} import generic._ -import util.control.Breaks._ +import scala.util.control.Breaks._ /** Class Linear[A] represents linear sequences of elements. * For such sequences `isEmpty`, `head` and `tail` are guaranteed to be diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index f4ec24044f..7c88e0b404 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -34,8 +34,6 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] import Traversable.breaks._ /** Returns the length of the sequence. - * - * @return the sequence length. */ def length: Int @@ -262,7 +260,7 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] def indexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = if (thisCollection.hasDefiniteSize && that.hasDefiniteSize) - indexOf_KMP(thisCollection, 0, length, that, 0, that.length, fromIndex) + KMP.indexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) else { var i = fromIndex var s: Sequence[A] = thisCollection drop i @@ -285,7 +283,7 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] // 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 = - lastIndexOf_KMP(thisCollection, 0, length, that, 0, that.length, fromIndex) + KMP.lastIndexOf(thisCollection, 0, length, that, 0, that.length, fromIndex) /** Tests if the given value elem is a member of this * sequence. @@ -403,7 +401,7 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] val (prefix, rest) = this.splitAt(from) b ++= prefix b ++= patch - b ++= rest drop replaced + b ++= rest/*.view*/ drop replaced // !!! todo: make this a view b.result } @@ -412,6 +410,7 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] */ 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) { @@ -428,6 +427,8 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] */ 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] { @@ -439,77 +440,6 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] override def view(from: Int, until: Int) = view.slice(from, until) - // KMP implementation by paulp, based on the undoubtedly reliable wikipedia entry - private def KMP[B](S: Seq[B], W: Seq[B]): Option[Int] = { - // trivial cases - if (W.isEmpty) return Some(0) - else if (W drop 1 isEmpty) return (S indexOf W(0)) match { - case -1 => None - case x => Some(x) - } - - val T: Array[Int] = { - val arr = new Array[Int](W.length) - var pos = 2 - var cnd = 0 - arr(0) = -1 - arr(1) = 0 - while (pos < W.length) { - if (W(pos - 1) == W(cnd)) { - arr(pos) = cnd + 1 - pos += 1 - cnd += 1 - } - else if (cnd > 0) { - cnd = arr(cnd) - } - else { - arr(pos) = 0 - pos += 1 - } - } - arr - } - - var m, i = 0 - def mi = m + i - - while (mi < S.length) { - if (W(i) == S(mi)) { - i += 1 - if (i == W.length) - return Some(m) - } - else { - m = mi - T(i) - if (i > 0) - i = T(i) - } - } - None - } - private def indexOf_KMP[B]( - source: Seq[B], sourceOffset: Int, sourceCount: Int, - target: Seq[B], targetOffset: Int, targetCount: Int, - fromIndex: Int): Int = - KMP(source.slice(sourceOffset, sourceCount) drop fromIndex, target.slice(targetOffset, targetCount)) match { - case None => -1 - case Some(x) => x + fromIndex - } - - private def lastIndexOf_KMP[B]( - source: Seq[B], sourceOffset: Int, sourceCount: Int, - target: Seq[B], targetOffset: Int, targetCount: Int, - fromIndex: Int): Int = { - val src = (source.slice(sourceOffset, sourceCount) take fromIndex).reverse - val tgt = target.slice(targetOffset, targetCount).reverse - - KMP(src, tgt) match { - case None => -1 - case Some(x) => (src.length - tgt.length - x) + sourceOffset - } - } - override def equals(that: Any): Boolean = that match { case that: Sequence[_] => this sameElements that case _ => false diff --git a/src/library/scala/collection/generic/TraversableTemplate.scala b/src/library/scala/collection/generic/TraversableTemplate.scala index c57e6c7d50..10cb92916e 100644 --- a/src/library/scala/collection/generic/TraversableTemplate.scala +++ b/src/library/scala/collection/generic/TraversableTemplate.scala @@ -135,38 +135,6 @@ self => result } - /** 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, "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, "max()") - var acc = self.head - for (x <- self) - if (cmp.gt(x, acc)) acc = x - acc - } - /** 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 @@ -235,6 +203,14 @@ self => b.result } + /** Returns a traversable with all elements of this traversable which do not satisfy the predicate + * p. + * + * @param p the predicate used to test elements + * @return the traversable without all elements that satisfy p + */ + def filterNot(p: A => Boolean): This = filter(!p(_)) + /** Returns a new traversable based on the partial function pf, * containing pf(x) for all the elements which are defined on pf. * The order of the elements is preserved. @@ -248,14 +224,6 @@ self => b.result } - /** Returns a traversable with all elements of this traversable which do not satisfy the predicate - * p. - * - * @param p the predicate used to test elements - * @return the traversable without all elements that satisfy p - */ - def filterNot(p: A => Boolean): This = filter(!p(_)) - /** Returns a traversable with all elements of this traversable which do not satisfy the predicate * p. * @@ -389,15 +357,15 @@ self => */ def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) - /** Combines the elements of this iterable together using the binary + /** Combines the elements of this traversable together using the binary * function f, from right to left, and starting with * the value z. * * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this iterable is ordered, or + * @note Might return different results for different runs, unless this traversable is ordered, or * the operator is associative and commutative. * @return f(a0, f(a1, f(..., f(an, z)...))) - * if the iterable is [a0, a1, ..., an]. + * if the traversable is [a0, a1, ..., an]. */ def foldRight[B](z: B)(op: (A, B) => B): B = { var elems: List[A] = Nil @@ -408,7 +376,7 @@ self => /** An alias for foldRight. * That is, xs :\ z is the same as xs foldRight z * @note Will not terminate for infinite-sized collections. - * @note Might return different results for different runs, unless this iterable is ordered, or + * @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) @@ -446,15 +414,15 @@ self => if (isEmpty) None else Some(reduceLeft(op)) } - /** Combines the elements of this iterable object together using the binary + /** Combines the elements of this traversable object together using the binary * operator op, 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 + * @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 a0 op (... op (an-1 op an)...) - * if the iterable object has elements a0, a1, ..., + * if the traversable object has elements a0, a1, ..., * an. * * @throws Predef.UnsupportedOperationException if the iterator is empty. @@ -466,18 +434,50 @@ self => elems.reduceLeft[B]((x, y) => op(y, x)) } - /** Combines the elements of this iterable object together using the binary + /** Combines the elements of this traversable object together using the binary * operator op, 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 + * @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 iterable is non-empty, the result of the operations as an Option, otherwise None. + * @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, ".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, ".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 @@ -504,7 +504,10 @@ self => * except the first one. * @note Might return different results for different runs, unless this traversable is ordered */ - def tail: This = drop(1) + def tail: This = { + require(!self.isEmpty, ".tail") + drop(1) + } /** The last element of this traversable. * @@ -730,7 +733,7 @@ self => */ def toList: List[A] = (new ListBuffer[A] ++= thisCollection).toList - /** Returns an iterable with all elements in this traversable object. + /** Returns an traversable with all elements in this traversable object. * @note Will not terminate for infinite-sized collections. */ def toIterable: Iterable[A] = toStream @@ -840,9 +843,9 @@ self => * @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. + * a view of the current traversable, whereas `slice` produces a new traversable. * - * @note Might return different results for different runs, unless this iterable is ordered + * @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/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index 76f1f061b8..c56076de37 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -136,7 +136,7 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend } override def head: A = if (isEmpty) super.head else this(0) - override def tail: This = slice(1, length) + 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) diff --git a/src/library/scala/collection/immutable/PagedSeq.scala b/src/library/scala/collection/immutable/PagedSeq.scala index 51bcfebf52..b8888c3aef 100644 --- a/src/library/scala/collection/immutable/PagedSeq.scala +++ b/src/library/scala/collection/immutable/PagedSeq.scala @@ -12,7 +12,7 @@ package scala.collection.immutable import java.io._ -import util.matching.Regex +import scala.util.matching.Regex /** The PagedSeq object defines a lazy implementations of * a random access sequence. diff --git a/src/library/scala/collection/immutable/StringVector.scala b/src/library/scala/collection/immutable/StringVector.scala index 3a3f2c0944..7073ccd117 100644 --- a/src/library/scala/collection/immutable/StringVector.scala +++ b/src/library/scala/collection/immutable/StringVector.scala @@ -10,8 +10,8 @@ package scala.collection.immutable -import util.matching.Regex -import annotation.experimental +import scala.util.matching.Regex +import scala.annotation.experimental /** An incomplete implementation of all the methods on Vector, * written as static methods which take a String as a faux "this" diff --git a/src/library/scala/collection/mutable/ArrayVector.scala b/src/library/scala/collection/mutable/ArrayVector.scala new file mode 100755 index 0000000000..7c29d97336 --- /dev/null +++ b/src/library/scala/collection/mutable/ArrayVector.scala @@ -0,0 +1,45 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ArrayVector.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection.mutable + +import Predef._ +import scala.reflect.ClassManifest +import collection.generic._ + +/** + *

A class representing Array[T]

+ * + * @author Martin Odersky, Stephane Micheloud + * @version 1.0 + */ +abstract class ArrayVector[A] extends Vector[A] with VectorTemplate[A, ArrayVector[A]] { self => + + /** The manifest of the element type */ + def elemManifest: ClassManifest[A] + + /** The length of the array */ + def length: Int + + /** The element at given index */ + def apply(index: Int): A + + /** Update element at given index */ + def update(index: Int, elem: A): Unit + + /** The underlying array */ + def value: AnyRef + + /** Creates new builder for this collection ==> move to subclasses + */ + override protected[this] def newBuilder: Builder[A, ArrayVector[A]] = + new ArrayVectorBuilder[A](elemManifest) +} diff --git a/src/library/scala/collection/mutable/ArrayVectorBuilder.scala b/src/library/scala/collection/mutable/ArrayVectorBuilder.scala new file mode 100755 index 0000000000..761fc1c25e --- /dev/null +++ b/src/library/scala/collection/mutable/ArrayVectorBuilder.scala @@ -0,0 +1,64 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ArrayBuffer.scala 18387 2009-07-24 15:28:37Z odersky $ + + +package scala.collection.mutable + +import scala.collection.generic._ +import scala.reflect.ClassManifest + +/** A builder class for arrays */ +class ArrayVectorBuilder[A](manifest: ClassManifest[A]) extends Builder[A, ArrayVector[A]] { + + private var elems: ArrayVector[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) + newelems + } + + private def resize(size: Int) { + elems = mkArray(size) + capacity = size + } + + override def sizeHint(size: Int) { + if (capacity < size) resize(size) + } + + private def ensureSize(size: Int) { + if (capacity < size) { + var newsize = if (capacity == 0) 16 else capacity * 2 + while (newsize < size) newsize *= 2 + resize(newsize) + } + } + + def +=(elem: A): this.type = { + ensureSize(size + 1) + elems(size) = elem + size += 1 + this + } + + def clear() { + size = 0 + } + + def result() = { + if (capacity != 0 && capacity == size) elems + else mkArray(size) + } + + // todo: add ++= +} diff --git a/src/library/scala/collection/mutable/BooleanArrayVector.scala b/src/library/scala/collection/mutable/BooleanArrayVector.scala new file mode 100755 index 0000000000..0d701464ee --- /dev/null +++ b/src/library/scala/collection/mutable/BooleanArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: BooleanArrayVector.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] { + + def elemManifest = ClassManifest.Boolean + + def length: Int = value.length + + def apply(index: Int): Boolean = value(index) + + def update(index: Int, elem: Boolean) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/ByteArrayVector.scala b/src/library/scala/collection/mutable/ByteArrayVector.scala new file mode 100755 index 0000000000..47fe905ec3 --- /dev/null +++ b/src/library/scala/collection/mutable/ByteArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ByteArrayVector.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] { + + def elemManifest = ClassManifest.Byte + + def length: Int = value.length + + def apply(index: Int): Byte = value(index) + + def update(index: Int, elem: Byte) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/CharArrayVector.scala b/src/library/scala/collection/mutable/CharArrayVector.scala new file mode 100755 index 0000000000..cd9a0592de --- /dev/null +++ b/src/library/scala/collection/mutable/CharArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: CharArrayVector.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] { + + def elemManifest = ClassManifest.Char + + def length: Int = value.length + + def apply(index: Int): Char = value(index) + + def update(index: Int, elem: Char) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/DoubleArrayVector.scala b/src/library/scala/collection/mutable/DoubleArrayVector.scala new file mode 100755 index 0000000000..dd775fb279 --- /dev/null +++ b/src/library/scala/collection/mutable/DoubleArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: DoubleArrayVector.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] { + + def elemManifest = ClassManifest.Double + + def length: Int = value.length + + def apply(index: Int): Double = value(index) + + def update(index: Int, elem: Double) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/FloatArrayVector.scala b/src/library/scala/collection/mutable/FloatArrayVector.scala new file mode 100755 index 0000000000..67ff0e09e0 --- /dev/null +++ b/src/library/scala/collection/mutable/FloatArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: FloatArrayVector.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] { + + def elemManifest = ClassManifest.Float + + def length: Int = value.length + + def apply(index: Int): Float = value(index) + + def update(index: Int, elem: Float) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/IntArrayVector.scala b/src/library/scala/collection/mutable/IntArrayVector.scala new file mode 100755 index 0000000000..ea3e9bf5af --- /dev/null +++ b/src/library/scala/collection/mutable/IntArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: IntArrayVector.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] { + + def elemManifest = ClassManifest.Int + + def length: Int = value.length + + def apply(index: Int): Int = value(index) + + def update(index: Int, elem: Int) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/LongArrayVector.scala b/src/library/scala/collection/mutable/LongArrayVector.scala new file mode 100755 index 0000000000..a1a2a5795d --- /dev/null +++ b/src/library/scala/collection/mutable/LongArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: LongArrayVector.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] { + + def elemManifest = ClassManifest.Long + + def length: Int = value.length + + def apply(index: Int): Long = value(index) + + def update(index: Int, elem: Long) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/ObjectArrayVector.scala b/src/library/scala/collection/mutable/ObjectArrayVector.scala new file mode 100755 index 0000000000..aee89a3cb4 --- /dev/null +++ b/src/library/scala/collection/mutable/ObjectArrayVector.scala @@ -0,0 +1,42 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ObjectArrayVector.scala 18589 2009-08-27 14:45:35Z odersky $ + + +package scala.collection.mutable +import scala.reflect.ClassManifest + +import Predef._ + +@serializable +final class ObjectArrayVector[A <: AnyRef](val value: Array[AnyRef], val elemManifest: ClassManifest[A]) extends ArrayVector[A] { + +// @deprecated("creating array w/o manifest") + def this(value: Array[AnyRef]) = this(value, null) // !!! todo: remove + + def length: Int = value.length + + def apply(index: Int): A = value(index).asInstanceOf[A] + + def update(index: Int, elem: A) { + value(index) = elem + } + + def unbox(elemClass: Class[_]): AnyRef = value + +/* + override def equals(other: Any): Boolean = + (value eq other.asInstanceOf[AnyRef]) || + other.isInstanceOf[ObjectArrayVector[_]] && (value eq other.asInstanceOf[ObjectArrayVector[_]].value) + + override def hashCode(): Int = (value.asInstanceOf[AnyRef]).hashCode() +*/ + +} + diff --git a/src/library/scala/collection/mutable/ShortArrayVector.scala b/src/library/scala/collection/mutable/ShortArrayVector.scala new file mode 100755 index 0000000000..62e4c9a2f9 --- /dev/null +++ b/src/library/scala/collection/mutable/ShortArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ShortArrayVector.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] { + + def elemManifest = ClassManifest.Short + + def length: Int = value.length + + def apply(index: Int): Short = value(index) + + def update(index: Int, elem: Short) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/collection/mutable/UnitArrayVector.scala b/src/library/scala/collection/mutable/UnitArrayVector.scala new file mode 100755 index 0000000000..a89da3cd0d --- /dev/null +++ b/src/library/scala/collection/mutable/UnitArrayVector.scala @@ -0,0 +1,28 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2002-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: DoubleArrayVector.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] { + + def elemManifest = ClassManifest.Unit + + def length: Int = value.length + + def apply(index: Int): Unit = value(index) + + def update(index: Int, elem: Unit) { + value(index) = elem + } + def unbox(elemClass: Class[_]): AnyRef = value +} diff --git a/src/library/scala/reflect/ClassManifest.scala b/src/library/scala/reflect/ClassManifest.scala index b3df97a50f..66e4758542 100644 --- a/src/library/scala/reflect/ClassManifest.scala +++ b/src/library/scala/reflect/ClassManifest.scala @@ -13,6 +13,7 @@ package scala.reflect import scala.runtime._ import scala.collection.immutable.Nil +import scala.collection.mutable.{ArrayVector, ObjectArrayVector} /**

* A ClassManifest[T] is an opaque descriptor for type T. @@ -77,6 +78,11 @@ trait ClassManifest[T] extends OptManifest[T] { .asInstanceOf[BoxedArray[T]] } + def newArrayVector(len: Int): ArrayVector[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]] + def typeArguments: List[OptManifest[_]] = List() protected def argString = if (typeArguments.isEmpty) "" else typeArguments.mkString("[", ", ", "]") diff --git a/src/library/scala/reflect/Manifest.scala b/src/library/scala/reflect/Manifest.scala index e83061856b..354058ab4c 100644 --- a/src/library/scala/reflect/Manifest.scala +++ b/src/library/scala/reflect/Manifest.scala @@ -12,6 +12,7 @@ package scala.reflect import scala.runtime._ +import scala.collection.mutable._ /**

* A Manifest[T] is an opaque descriptor for type T. @@ -45,54 +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)) } 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)) } 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)) } 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)) } 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)) } 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)) } 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)) } 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)) } 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)) } 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 327097f61b..fdabfd0d34 100644 --- a/src/library/scala/runtime/ScalaRunTime.scala +++ b/src/library/scala/runtime/ScalaRunTime.scala @@ -12,12 +12,14 @@ package scala.runtime import scala.reflect.ClassManifest +import scala.collection.Sequence +import scala.collection.mutable._ /* The object ScalaRunTime provides ... */ object ScalaRunTime { - def isArray(x: AnyRef): Boolean = (x != null && x.getClass.isArray) || (x != null && x.isInstanceOf[BoxedArray[_]]) + def isArray(x: AnyRef): Boolean = x != null && (x.getClass.isArray || x.isInstanceOf[BoxedArray[_]]) def isValueClass(clazz: Class[_]) = clazz.isPrimitive() // todo: [for Gilles] replace with boxArray @@ -28,6 +30,28 @@ object ScalaRunTime { array } + def toArray[T](xs: scala.collection.Sequence[T]) = { + val arr = new Array[AnyRef](xs.length) + var i = 0 + for (x <- xs) arr(i) = x.asInstanceOf[AnyRef] + arr + } + + /** 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 null => null + } + def checkInitialized[T <: AnyRef](x: T): T = if (x == null) throw new UninitializedError else x @@ -119,6 +143,14 @@ object ScalaRunTime { def arrayValue[A](x: BoxedArray[A], elemClass: Class[_]): AnyRef = if (x eq null) null else x.unbox(elemClass) + /** Temporary method to go to new array representation + * !!! can be reomved once bootstrap is complete !!! + */ + def unboxedArray[A](x: AnyRef): AnyRef = x match { + case ba: BoxedArray[_] => ba.value + case _ => x + } + def boxArray(value: AnyRef): BoxedArray[_] = value match { case x: Array[AnyRef] => new BoxedObjectArray(x, ClassManifest.classType(x.getClass.getComponentType)) case x: Array[Int] => new BoxedIntArray(x) -- cgit v1.2.3