* 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.

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 &lt; 0</code>
-   *          or <code>length &lt; 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)
   }
-*/
 }