diff options
author | Sean McDirmid <sean.mcdirmid@gmail.com> | 2007-08-29 10:38:23 +0000 |
---|---|---|
committer | Sean McDirmid <sean.mcdirmid@gmail.com> | 2007-08-29 10:38:23 +0000 |
commit | 9d12fe104d1c20199df227696e47fdfb7efae416 (patch) | |
tree | 6058ef0fdd81ddae030f5e2157cf5ad969617463 /src | |
parent | 79cda8f630e80919769c00a2c65a31acb92994f6 (diff) | |
download | scala-9d12fe104d1c20199df227696e47fdfb7efae416.tar.gz scala-9d12fe104d1c20199df227696e47fdfb7efae416.tar.bz2 scala-9d12fe104d1c20199df227696e47fdfb7efae416.zip |
* Added Array.Projection to facilitate efficien...
* Added Array.Projection to facilitate efficient forcing of array
projections
* Fixed boundary problems in RandomAccessSeq.slice
* Added RandomAccessSeq.patch to facilitate efficient patching of arrays
and other random access sequences.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/Array.scala | 62 | ||||
-rw-r--r-- | src/library/scala/Predef.scala | 3 | ||||
-rw-r--r-- | src/library/scala/RandomAccessSeq.scala | 93 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedAnyArray.scala | 14 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedArray.scala | 27 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedBooleanArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedByteArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedCharArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedDoubleArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedFloatArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedIntArray.scala | 11 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedLongArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedObjectArray.scala | 9 | ||||
-rw-r--r-- | src/library/scala/runtime/BoxedShortArray.scala | 9 |
14 files changed, 146 insertions, 136 deletions
diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala index fc673b7507..edaf6f6613 100644 --- a/src/library/scala/Array.scala +++ b/src/library/scala/Array.scala @@ -179,6 +179,32 @@ object Array { * @return array wrapped in an option */ def unapplySeq[A](x: Array[A]): Option[Seq[A]] = Some(x) + + trait Projection[A] extends RandomAccessSeq.MutableProjection[A] { + protected def newArray[B >: A](length : Int, elements : Iterator[A]) : Array[B] + override def toArray[B >: A] = newArray(length, elements) + override def force : Array[A] = toArray + override def drop( from: Int) = slice(from, length) + override def take(until: Int) = slice(0, until) + override def slice(from0 : Int, until0 : Int) : Projection[A] = new RandomAccessSeq.MutableSlice[A] with Projection[A] { + override def from = from0 + override def until = until0 + override def underlying = Projection.this + override protected def newArray[B >: A](length : Int, elements : Iterator[A]) = underlying.newArray(length, elements) + override def slice(from0 : Int, until0 : Int) = + Projection.this.slice(from + from0, from + until0) + } + override def reverse : Projection[A] = new Projection[A] { + override protected def newArray[B >: A](length : Int, elements : Iterator[A]) = Projection.this.newArray(length, elements) + def update(idx : Int, what : A) : Unit = Projection.this.update(length - idx - 1, what) + def length = Projection.this.length + def apply(idx : Int) = Projection.this.apply(length - idx - 1) + override def stringPrefix = Projection.this.stringPrefix + "R" + } + } + trait Array0[A] extends RandomAccessSeq.Mutable[A] { + override def projection : Projection[A] = throw new Error + } } /** This class represents polymorphic arrays. <code>Array[T]</code> is Scala's representation @@ -187,7 +213,7 @@ object Array { * @author Martin Odersky * @version 1.0 */ -final class Array[A](_length: Int) extends RandomAccessSeq.Mutable[A] { +final class Array[A](_length: Int) extends Array.Array0[A] { /** Multidimensional array creation */ def this(dim1: Int, dim2: Int) = { @@ -279,18 +305,9 @@ final class Array[A](_length: Int) extends RandomAccessSeq.Mutable[A] { */ override def elements: Iterator[A] = throw new Error() - /** @deprecated use slice instead */ + /** @deprecated use <code>slice(from,end).force</code> instead */ def subArray(from: Int, end: Int): Array[A] = throw new Error() - /** A sub-array of <code>len</code> elements - * starting at index <code>from</code> - * - * @param from The index of the first element of the slice - * @param end The index of the element following the slice - * @throws IndexOutOfBoundsException if <code>from < 0</code> - * or <code>length < end<code> - */ - //override def slice(from: Int, end: Int): Array[A] = throw new Error() /** Returns an array consisting of all elements of this array that satisfy the @@ -301,24 +318,6 @@ final class Array[A](_length: Int) extends RandomAccessSeq.Mutable[A] { */ override def filter(p: A => Boolean): Array[A] = throw new Error() - /** Returns an array consisting only over the first <code>n</code> - * elements of this array, or else the whole array, if it has less - * than <code>n</code> elements. - * - * @param n the number of elements to take - * @return the new array - */ - //override def take(n: Int): Array[A] = throw new Error() - - /** Returns this array without its <code>n</code> first elements - * If this array has less than <code>n</code> elements, the empty - * array is returned. - * - * @param n the number of elements to drop - * @return the new array - */ - //override def drop(n: Int): Array[A] =throw new Error() - /** Returns the longest prefix of this array whose elements satisfy * the predicate <code>p</code>. * @@ -337,10 +336,6 @@ final class Array[A](_length: Int) extends RandomAccessSeq.Mutable[A] { */ override def dropWhile(p: A => Boolean): Array[A] = throw new Error() - /** A array consisting of all elements of this array in reverse order. - */ - //override def reverse: Array[A] = throw new Error() - /** Returns an array consisting of all elements of this array followed * by all elements of the argument iterable. */ @@ -439,4 +434,5 @@ final class Array[A](_length: Int) extends RandomAccessSeq.Mutable[A] { * @return <code>true</code> iff both arrays are deeply equal. */ def deepEquals(that: Any): Boolean = throw new Error() + } diff --git a/src/library/scala/Predef.scala b/src/library/scala/Predef.scala index 340f7a8f68..5d450b11e7 100644 --- a/src/library/scala/Predef.scala +++ b/src/library/scala/Predef.scala @@ -311,6 +311,9 @@ object Predef { implicit def double2Double(x: Double) = new java.lang.Double(x) implicit def boolean2Boolean(x: Boolean) = java.lang.Boolean.valueOf(x) + /** any array projection can be automatically converted into an array */ + implicit def forceArrayProjection[A](x : Array.Projection[A]) : Array[A] = x.force + def currentThread = java.lang.Thread.currentThread() } diff --git a/src/library/scala/RandomAccessSeq.scala b/src/library/scala/RandomAccessSeq.scala index edcec42d07..36f9057084 100644 --- a/src/library/scala/RandomAccessSeq.scala +++ b/src/library/scala/RandomAccessSeq.scala @@ -20,6 +20,35 @@ object RandomAccessSeq { } } } + private[scala] trait Slice[+A] extends Projection[A] { + protected def from : Int + protected def until : Int + protected def underlying : RandomAccessSeq[A] + def length = { + val length0 = underlying.length + if (from >= until || from >= length0) 0 + else (if (until >= length0) length0 else until) - (if (from < 0) 0 else from) + } + def apply(idx : Int) = if (idx < 0 || idx >= length) throw new Predef.IndexOutOfBoundsException + else underlying.apply((if (from < 0) 0 else from) + idx) + override def slice(from0 : Int, until0 : Int) = { + val from = if (this.from < 0) 0 else this.from + underlying.slice(from + from0, from + until0) + } + } + private[scala] trait Patch[+A] extends Projection[A] { + protected def original : RandomAccessSeq[A] + protected def patch : RandomAccessSeq[A] + protected def from : Int + protected def replaced : Int + def length = original.length + patch.length - replaced + def apply(idx : Int) = + if (idx < from) original.apply(idx) + else if (idx < from + patch.length) patch.apply(idx - from) + else original.apply(idx - patch.length + replaced) + override def stringPrefix = "patch" + } + /** A random access sequence that supports update (e.g., an array) */ trait Mutable[A] extends RandomAccessSeq[A] { /** <p> @@ -51,22 +80,12 @@ object RandomAccessSeq { def apply(idx : Int) = Mutable.this.apply(idx) override def stringPrefix = Mutable.this.stringPrefix + "RO" } - override def drop( from: Int): Mutable[A] = slice(from, length) - override def take(until: Int): Mutable[A] = slice(0, until) - override def slice(from : Int, until : Int) : Mutable[A] = { - if (from == 0 && until >= length) return projection - else if (from >= until) new MutableProjection[A] { - def length = 0 - def apply(idx : Int) = throw new Predef.IndexOutOfBoundsException - def update(idx : Int, what : A) = throw new Predef.IndexOutOfBoundsException - } else new MutableProjection[A] { - def length = until - from - def apply(idx : Int) = if (idx < 0 || idx >= length) throw new Predef.IndexOutOfBoundsException - else Mutable.this.apply(from + idx) - def update(idx : Int, what : A) = - if (idx < 0 || idx >= length) throw new Predef.IndexOutOfBoundsException - else Mutable.this.update(from + idx, what) - } + override def drop( from: Int): MutableProjection[A] = slice(from, length) + override def take(until: Int): MutableProjection[A] = slice(0, until) + override def slice(from0 : Int, until0 : Int) : MutableProjection[A] = new MutableSlice[A] { + def from = from0 + def until = until0 + def underlying = Mutable.this } override def reverse : Mutable[A] = new MutableProjection[A] { def update(idx : Int, what : A) : Unit = Mutable.this.update(length - idx - 1, what) @@ -77,10 +96,21 @@ object RandomAccessSeq { } } trait MutableProjection[A] extends Projection[A] with Mutable[A] { - // XXX: must copy. override def force : Mutable[A] = toArray override def projection : MutableProjection[A] = this } + private[scala] trait MutableSlice[A] extends MutableProjection[A] with Slice[A] { + protected def underlying : Mutable[A] + override def slice(from0 : Int, until0 : Int) = { + val from = (if (this.from < 0) 0 else this.from) + underlying.slice(from + from0, from + until0) + } + override def update(idx : Int, what : A) : Unit = { + val from = (if (this.from < 0) 0 else this.from) + if (idx < 0 || idx >= length) throw new Predef.IndexOutOfBoundsException + else underlying.update(from + idx, what) + } + } } /** Sequences that support O(1) element access and O(1) length computation. @@ -109,19 +139,10 @@ trait RandomAccessSeq[+A] extends Seq[A] { } override def drop( from: Int): RandomAccessSeq[A] = slice(from, length) override def take(until: Int): RandomAccessSeq[A] = slice(0, until) - override def slice(from : Int, until : Int) : RandomAccessSeq[A] = { - if (from == 0 && until >= length) return projection - else if (from >= until) new RandomAccessSeq.Projection[A] { - def length = 0 - def apply(idx : Int) = throw new Predef.IndexOutOfBoundsException - } else new RandomAccessSeq.Projection[A] { - def length = until - from - def apply(idx : Int) = if (idx < 0 || idx >= length) throw new Predef.IndexOutOfBoundsException - else RandomAccessSeq.this.apply(from + idx) - override def slice(from0 : Int, until0 : Int) = // minimize the object chain. - if (from + until0 > until) RandomAccessSeq.this.slice(from + from0, until) - else RandomAccessSeq.this.slice(from + from0, from + until0) - } + override def slice(from0 : Int, until0 : Int) : RandomAccessSeq[A] = new RandomAccessSeq.Slice[A] { + def from = from0 + def until = until0 + def underlying = RandomAccessSeq.this } override def reverse : Seq[A] = new RandomAccessSeq.Projection[A] { def length = RandomAccessSeq.this.length @@ -129,6 +150,18 @@ trait RandomAccessSeq[+A] extends Seq[A] { override def stringPrefix = RandomAccessSeq.this.stringPrefix + "R" override def reverse : RandomAccessSeq.Projection[A] = RandomAccessSeq.this.projection } + + /** insert segment <code>patch</code> into this sequence at <code>from</code> + * replacing <code>replaced</code> elements. The result is a projection. + */ + def patch[B >: A](from0 : Int, patch0 : RandomAccessSeq[B], replaced0 : Int) : RandomAccessSeq.Projection[B] = new RandomAccessSeq.Patch[B] { + override def original = RandomAccessSeq.this + override def from = from0 + override def patch = patch0 + override def replaced = replaced0 + override def stringPrefix = RandomAccessSeq.this.stringPrefix + "P" + } + override def ++[B >: A](that : Iterable[B]) : RandomAccessSeq[B] = that match { case that : RandomAccessSeq[b] => val ret = new Array[B](length + that.length) diff --git a/src/library/scala/runtime/BoxedAnyArray.scala b/src/library/scala/runtime/BoxedAnyArray.scala index 59ea4cd81a..a03ed39053 100644 --- a/src/library/scala/runtime/BoxedAnyArray.scala +++ b/src/library/scala/runtime/BoxedAnyArray.scala @@ -254,13 +254,13 @@ final class BoxedAnyArray(val length: Int) extends BoxedArray { } result } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new BoxedAnyArray(len) - Array.copy(this, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new BoxedAnyArray(length) + var i = 0 + while (elements.hasNext) { + result(i) = elements.next + i += 1 + } result } -*/ - } diff --git a/src/library/scala/runtime/BoxedArray.scala b/src/library/scala/runtime/BoxedArray.scala index b92f737fea..26be18946d 100644 --- a/src/library/scala/runtime/BoxedArray.scala +++ b/src/library/scala/runtime/BoxedArray.scala @@ -22,7 +22,7 @@ import compat.StringBuilder * @author Martin Odersky, Stephane Micheloud * @version 1.0 */ -abstract class BoxedArray extends RandomAccessSeq.Mutable[Any] { +abstract class BoxedArray extends Array.Array0[Any] { /** The length of the array */ def length: Int @@ -126,11 +126,6 @@ abstract class BoxedArray extends RandomAccessSeq.Mutable[Any] { /** Returns an array that contains all indices of this array */ def indices: Array[Int] = Array.range(0, length) - // use implementation in RandomAccessSeq - //override def slice(start: Int, end: Int): BoxedArray = throw new Error("internal: slice") - //override def take(n: Int) = slice(0, n) - //override def drop(n: Int) = slice(n, length) - override def takeWhile(p: Any => Boolean) = { val c = length + 1 take((findIndexOf(!p(_)) + c) % c) @@ -140,11 +135,6 @@ abstract class BoxedArray extends RandomAccessSeq.Mutable[Any] { drop((findIndexOf(!p(_)) + c) % c) } -/* - /** A array consisting of all elements of this array in reverse order. - */ - def reverse: Array[A] = super.reverse.toArray -*/ final def deepToString() = deepMkString(stringPrefix + "(", ",", ")") final def deepMkString(start: String, sep: String, end: String): String = { @@ -194,6 +184,19 @@ abstract class BoxedArray extends RandomAccessSeq.Mutable[Any] { false } } - override final def stringPrefix: String = "Array" + + protected def newArray(length : Int, elements : Iterator[Any]) : BoxedArray + override def projection : scala.Array.Projection[Any] = new scala.Array.Projection[Any] { + def update(idx : Int, what : Any) : Unit = BoxedArray.this.update(idx, what) + def length = BoxedArray.this.length + def apply(idx : Int) = BoxedArray.this.apply(idx) + override def stringPrefix = "ArrayP" + protected def newArray[B >: Any](length : Int, elements : Iterator[Any]) = + BoxedArray.this.newArray(length, elements).asInstanceOf[Array[B]] + } + override def slice(from : Int, until : Int) = projection.slice(from,until) + override def take(until : Int) = projection.take(until) + override def drop(from : Int) = projection.drop(from) + override def reverse = projection.reverse } diff --git a/src/library/scala/runtime/BoxedBooleanArray.scala b/src/library/scala/runtime/BoxedBooleanArray.scala index ede3396a29..6e55ec3692 100644 --- a/src/library/scala/runtime/BoxedBooleanArray.scala +++ b/src/library/scala/runtime/BoxedBooleanArray.scala @@ -57,12 +57,9 @@ final class BoxedBooleanArray(val value: Array[Boolean]) extends BoxedArray { } new BoxedBooleanArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Boolean](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Boolean](length) + elements.map(_.asInstanceOf[Boolean]).copyToArray(result, 0) new BoxedBooleanArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedByteArray.scala b/src/library/scala/runtime/BoxedByteArray.scala index c509cb1f22..91b7fca7ce 100644 --- a/src/library/scala/runtime/BoxedByteArray.scala +++ b/src/library/scala/runtime/BoxedByteArray.scala @@ -57,12 +57,9 @@ final class BoxedByteArray(val value: Array[Byte]) extends BoxedArray { } new BoxedByteArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Byte](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Byte](length) + elements.map(_.asInstanceOf[Byte]).copyToArray(result, 0) new BoxedByteArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedCharArray.scala b/src/library/scala/runtime/BoxedCharArray.scala index e70efedfd0..ef5674f713 100644 --- a/src/library/scala/runtime/BoxedCharArray.scala +++ b/src/library/scala/runtime/BoxedCharArray.scala @@ -58,12 +58,9 @@ final class BoxedCharArray(val value: Array[Char]) extends BoxedArray { } new BoxedCharArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Char](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Char](length) + elements.map(_.asInstanceOf[Char]).copyToArray(result, 0) new BoxedCharArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedDoubleArray.scala b/src/library/scala/runtime/BoxedDoubleArray.scala index bbf0189285..5877eaae09 100644 --- a/src/library/scala/runtime/BoxedDoubleArray.scala +++ b/src/library/scala/runtime/BoxedDoubleArray.scala @@ -57,12 +57,9 @@ final class BoxedDoubleArray(val value: Array[Double]) extends BoxedArray { } new BoxedDoubleArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Double](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Double](length) + elements.map(_.asInstanceOf[Double]).copyToArray(result, 0) new BoxedDoubleArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedFloatArray.scala b/src/library/scala/runtime/BoxedFloatArray.scala index d78facc705..3cf6b36938 100644 --- a/src/library/scala/runtime/BoxedFloatArray.scala +++ b/src/library/scala/runtime/BoxedFloatArray.scala @@ -57,12 +57,9 @@ final class BoxedFloatArray(val value: Array[Float]) extends BoxedArray { } new BoxedFloatArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Float](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Float](length) + elements.map(_.asInstanceOf[Float]).copyToArray(result, 0) new BoxedFloatArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedIntArray.scala b/src/library/scala/runtime/BoxedIntArray.scala index a837a0ee6f..ed79f0c4da 100644 --- a/src/library/scala/runtime/BoxedIntArray.scala +++ b/src/library/scala/runtime/BoxedIntArray.scala @@ -57,12 +57,11 @@ final class BoxedIntArray(val value: Array[Int]) extends BoxedArray { } new BoxedIntArray(result) } -/* use implementation in RandomAccessSeq - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Int](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Int](length) + elements.map(_.asInstanceOf[Int]).copyToArray(result, 0) new BoxedIntArray(result) } -*/ + + } diff --git a/src/library/scala/runtime/BoxedLongArray.scala b/src/library/scala/runtime/BoxedLongArray.scala index b8ea3ee5fb..8dbf87edf1 100644 --- a/src/library/scala/runtime/BoxedLongArray.scala +++ b/src/library/scala/runtime/BoxedLongArray.scala @@ -57,12 +57,9 @@ final class BoxedLongArray(val value: Array[Long]) extends BoxedArray { } new BoxedLongArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Long](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Long](length) + elements.map(_.asInstanceOf[Long]).copyToArray(result, 0) new BoxedLongArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedObjectArray.scala b/src/library/scala/runtime/BoxedObjectArray.scala index ded515b87f..4826518173 100644 --- a/src/library/scala/runtime/BoxedObjectArray.scala +++ b/src/library/scala/runtime/BoxedObjectArray.scala @@ -62,12 +62,9 @@ final class BoxedObjectArray(val value: Array[AnyRef]) extends BoxedArray { } new BoxedObjectArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = create(len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[AnyRef](length) + elements.map(_.asInstanceOf[AnyRef]).copyToArray(result, 0) new BoxedObjectArray(result) } -*/ } diff --git a/src/library/scala/runtime/BoxedShortArray.scala b/src/library/scala/runtime/BoxedShortArray.scala index c34faf76d9..7f3e2c09e1 100644 --- a/src/library/scala/runtime/BoxedShortArray.scala +++ b/src/library/scala/runtime/BoxedShortArray.scala @@ -57,12 +57,9 @@ final class BoxedShortArray(val value: Array[Short]) extends BoxedArray { } new BoxedShortArray(result) } -/* - final override def slice(start: Int, end: Int): BoxedArray = { - val (s, len) = slice0(start, end) - val result = new Array[Short](len) - Array.copy(value, s, result, 0, len) + override protected def newArray(length : Int, elements : Iterator[Any]) = { + val result = new Array[Short](length) + elements.map(_.asInstanceOf[Short]).copyToArray(result, 0) new BoxedShortArray(result) } -*/ } |