added methods updated +: :+ to SeqLike

3 files changed, 240 insertions, 184 deletions

diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala
index 50ea0c3a5a..25be79b0d5 100644
--- a/src/library/scala/collection/SeqLike.scala
+++ b/src/library/scala/collection/SeqLike.scala
@@ -6,7 +6,7 @@
 **                          |/                                          **
 \*                                                                      */
 
-// $Id$
+// $Id: SeqLike.scala 18895 2009-10-02 17:57:16Z odersky $
 
 
 package scala.collection
@@ -133,7 +133,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
    *  is O(length min len) instead of O(length). The method should be overwritten
    *  if computing length is cheap.
    */
-  def lengthCompare(len: Int): Int = {
+  def lengthCompare(len: Int): Int = { //TR: should use iterator?
     var i = 0
     breakable {
       for (_ <- this) {
@@ -157,7 +157,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
    *  @param  p the predicate
    *  @param  from  the start index
    */
-  def segmentLength(p: A => Boolean, from: Int): Int = {
+  def segmentLength(p: A => Boolean, from: Int): Int = { //TR: should use iterator?
     var result = 0
     var i = 0
     breakable {
@@ -190,7 +190,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
    *  @param  p the predicate
    *  @param  from  the start index
    */
-  def indexWhere(p: A => Boolean, from: Int): Int = {
+  def indexWhere(p: A => Boolean, from: Int): Int = { //TR: should use iterator?
     var result = -1
     var i = from
     breakable {
@@ -460,7 +460,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
    */
   def removeDuplicates: Repr = {
     val b = newBuilder
-    var seen = Set[A]()
+    var seen = Set[A]() //TR: should use mutable.HashSet?
     for (x <- this) {
       if (!(seen contains x)) {
         b += x
@@ -483,6 +483,38 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
     b.result
   }
 
+  /** Returns a copy of this sequence with the element at position `index` replaced by `elem`.
+   */
+  def updated[B >: A, That](index: Int, elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = {
+    val b = bf(repr)
+    val (prefix, rest) = this.splitAt(index)
+    b ++= toCollection(prefix)
+    b += elem
+    b ++= toCollection(rest).view.tail
+    b.result
+  }
+
+  /** Returns a new sequence consisting of `elem` followed by the elements of this sequence.
+   */
+  def +:[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = {
+    val b = bf(repr)
+    b += elem
+    b ++= thisCollection
+    b.result
+  }
+
+  /** Returns a new sequence consisting of the elements of this sequence followed by `elem`.
+   */
+  def :+[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = {
+    val b = bf(repr)
+    b ++= thisCollection
+    b += elem
+    b.result
+  }
+
+
+
+
   /** Returns a new sequence of given length containing the elements of this sequence followed by zero
    *  or more occurrences of given elements.
    */
diff --git a/src/library/scala/collection/SeqViewLike.scala b/src/library/scala/collection/SeqViewLike.scala
index 38cfa7ba05..27389c8a5c 100644
--- a/src/library/scala/collection/SeqViewLike.scala
+++ b/src/library/scala/collection/SeqViewLike.scala
@@ -161,6 +161,8 @@ trait SeqViewLike[+A,
 //    else super.patch[B, That](from, patch, replaced)(bf)
   }
 
+  //TR TODO: updated, +: ed :+ ed
+
   override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, This]): That =
     patch(length, fill(len - length)(elem), 0)
 
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 30d766ee01..4b0cecf582 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -8,15 +8,14 @@
 
 // $Id: Vector.scala 19072 2009-10-13 12:19:59Z rompf $
 
-
-// Questions: how to name update, appendFront, appendBack?
-//            how to make them available? trait Vector? VectorLike? have another companion object VectorImpl?
-//            mix in LinearSeq as well? <-- not yet
+// TODO: check overhead of builder factories for methods updated, +: and :+
 
 package scala.collection
 package immutable
 
 import scala.annotation.unchecked.uncheckedVariance
+import compat.Platform.arraycopy // FIXME: Platform.arraycopy is slower than System.arraycopy.
+                                 // Need to check why it isn't inlined.
 
 import scala.collection.generic._
 import scala.collection.mutable.Builder
@@ -39,7 +38,7 @@ trait Vector[+A] extends Seq[A]
 object Vector extends SeqFactory[Vector] {
   implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] =
     new VirtualBuilderFactory[A]
-  override def empty[A]: Vector[A] = NewVector.empty[A]
+  override def empty[A] = NewVector.empty[A]
   def newBuilder[A]: Builder[A, Vector[A]] = NewVector.newBuilder[A]
 }
 
@@ -47,20 +46,22 @@ object Vector extends SeqFactory[Vector] {
 
 // implementation classes below
 
-
 trait NewVector[+A]  extends Vector[A]
                    with GenericTraversableTemplate[A, NewVector]
-                   with VectorLike[A, NewVector[A]] {
+                   with VectorLike[A, NewVector[A]]
+                   with SeqLike[A, NewVector[A]] { // use impl from SeqLike, not VectorLike
   override def companion: GenericCompanion[NewVector] = NewVector
 }
 
 
 object NewVector extends SeqFactory[NewVector] {
+  private[immutable] val bf = new VirtualBuilderFactory[Nothing]
   implicit def builderFactory[A]: BuilderFactory[A, NewVector[A], Coll] =
-    new VirtualBuilderFactory[A]
+    bf.asInstanceOf[BuilderFactory[A, NewVector[A], Coll]]
   def newBuilder[A]: Builder[A, NewVector[A]] = new NewVectorBuilder[A]
+  override def empty[A]: NewVector[A] = new NewVectorImpl[A](0, 0, 0)
 
-  // TODO: override object empty { }
+  // TODO: special-case empty vectors and empty builders
 }
 
 
@@ -68,7 +69,7 @@ object NewVector extends SeqFactory[NewVector] {
 
 
 @serializable @SerialVersionUID(7129304555082767876L)
-class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewVector[A]
+private class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewVector[A]
                               with NewVectorPointer[A @uncheckedVariance] {
 
   //assert(startIndex >= 0, startIndex+"<0")
@@ -89,6 +90,12 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV
   // TODO: reverse
   // TODO: reverseIterator
 
+  def apply(index: Int): A = {
+    val idx = checkRangeConvert(index)
+//    //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")")
+    getElem(idx, idx ^ focus)
+  }
+
   private def checkRangeConvert(index: Int) = {
     val idx = index + startIndex
     if (0 <= index && idx < endIndex)
@@ -97,19 +104,22 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV
       throw new IndexOutOfBoundsException(index.toString)
   }
 
-  def apply(index: Int): A = {
-    val idx = checkRangeConvert(index)
-//    //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")")
-    getElem(idx, idx ^ focus)
+
+  // SeqLike api
+
+  override def updated[B >: A, That](index: Int, elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = {
+    // just ignore bf
+    updateAt(index, elem).asInstanceOf[That]
   }
 
-  def update[B>:A](index: Int, value: B): NewVector[B] = {
-    val idx = checkRangeConvert(index)
-    val s = new NewVectorImpl[B](startIndex, endIndex, idx)
-    s.initFrom(this)
-    s.gotoPosClean(focus, idx, focus ^ idx)
-    s.display0(idx & 0x1f) = value.asInstanceOf[AnyRef]
-    s
+  override def +:[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = {
+    // just ignore bf
+    appendFront(elem).asInstanceOf[That]
+  }
+
+  override def :+[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = {
+    // just ignore bf
+    appendBack(elem).asInstanceOf[That]
   }
 
   override def take(n: Int): NewVector[A] = {
@@ -145,168 +155,17 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV
   }
 
 
+  // semi-private api
 
-  private def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = {
-    val elems = new Array[AnyRef](32)
-    System.arraycopy(array, oldLeft, elems, newLeft, 32 - Math.max(newLeft,oldLeft))
-    elems
-  }
-
-  private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match {
-    case 0 =>
-      display0 = copyRange(display0, oldLeft, newLeft)
-    case 1 =>
-      display1 = copyRange(display1, oldLeft, newLeft)
-    case 2 =>
-      display2 = copyRange(display2, oldLeft, newLeft)
-    case 3 =>
-      display3 = copyRange(display3, oldLeft, newLeft)
-    case 4 =>
-      display4 = copyRange(display4, oldLeft, newLeft)
-    case 5 =>
-      display5 = copyRange(display5, oldLeft, newLeft)
-  }
-
-  private def cleanLeftEdge(cutIndex: Int) = (depth - 1) match {
-    case 5 =>
-      for (i <- 0 until ((cutIndex >>> 25) & 0x1f)) display5(i) = null
-      for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null
-      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
-      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
-      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-    case 4 =>
-      display5 = null
-      for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null
-      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
-      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
-      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-    case 3 =>
-      display5 = null
-      display4 = null
-      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
-      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
-      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-    case 2 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
-      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-    case 1 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      display2 = null
-      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-    case 0 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      display2 = null
-      display1 = null
-      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
-  }
-
-  private def cleanRightEdge(cutIndex: Int) = (depth - 1) match {
-    case 5 =>
-      for (i <- ((cutIndex >>> 25) & 0x1f) until 32) display5(i) = null
-      for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null
-      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
-      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
-      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-    case 4 =>
-      display5 = null
-      for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null
-      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
-      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
-      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-    case 3 =>
-      display5 = null
-      display4 = null
-      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
-      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
-      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-    case 2 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
-      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-    case 1 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      display2 = null
-      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-    case 0 =>
-      display5 = null
-      display4 = null
-      display3 = null
-      display2 = null
-      display1 = null
-      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
-  }
-
-  private def requiredDepth(xor: Int) = {
-    if (xor < (1 <<  5)) 1
-    else if (xor < (1 << 10)) 2
-    else if (xor < (1 << 15)) 3
-    else if (xor < (1 << 20)) 4
-    else if (xor < (1 << 25)) 5
-    else if (xor < (1 << 30)) 6
-    else throw new IllegalArgumentException()
-  }
-
-  private def dropFront0(cutIndex: Int): NewVector[A] = {
-    var blockIndex = cutIndex & ~31
-    var lo = cutIndex & 31
-
-    val xor = cutIndex ^ (endIndex - 1)
-    val d = requiredDepth(xor)
-    val shift = (cutIndex & ~((1 << (5*d))-1))
-
-    //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")")
-
-    val s = new NewVectorImpl(cutIndex-shift, endIndex-shift, blockIndex-shift)
-    s.initFrom(this)
-    if (s.depth > 1)
-      s.gotoPos(blockIndex, focus ^ blockIndex)
-    s.depth = d
-    s.stabilize(blockIndex-shift)
-    s.cleanLeftEdge(cutIndex-shift)
-    s
-  }
-
-  private def dropBack0(cutIndex: Int): NewVector[A] = {
-    var blockIndex = (cutIndex - 1) & ~31
-    var lo = ((cutIndex - 1) & 31) + 1
-
-    val xor = startIndex ^ (cutIndex - 1)
-    val d = requiredDepth(xor)
-
-    //println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")")
-
-    val s = new NewVectorImpl(startIndex, cutIndex, blockIndex)
+  def updateAt[B >: A](index: Int, elem: B): NewVector[B] = {
+    val idx = checkRangeConvert(index)
+    val s = new NewVectorImpl[B](startIndex, endIndex, idx)
     s.initFrom(this)
-    if (s.depth > 1)
-      s.gotoPos(blockIndex, focus ^ blockIndex)
-    s.depth = d
-    s.stabilize(blockIndex)
-    s.cleanRightEdge(cutIndex)
+    s.gotoPosClean(focus, idx, focus ^ idx)
+    s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef]
     s
   }
 
-
   def appendFront[B>:A](value: B): NewVector[B] = {
     if (endIndex != startIndex) {
       var blockIndex = (startIndex - 1) & ~31
@@ -474,6 +333,169 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV
     }
   }
 
+
+  // low-level implementation (needs cleanup)
+
+  private def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = {
+    val elems = new Array[AnyRef](32)
+    arraycopy(array, oldLeft, elems, newLeft, 32 - Math.max(newLeft,oldLeft))
+    elems
+  }
+
+  private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match {
+    case 0 =>
+      display0 = copyRange(display0, oldLeft, newLeft)
+    case 1 =>
+      display1 = copyRange(display1, oldLeft, newLeft)
+    case 2 =>
+      display2 = copyRange(display2, oldLeft, newLeft)
+    case 3 =>
+      display3 = copyRange(display3, oldLeft, newLeft)
+    case 4 =>
+      display4 = copyRange(display4, oldLeft, newLeft)
+    case 5 =>
+      display5 = copyRange(display5, oldLeft, newLeft)
+  }
+
+  private def cleanLeftEdge(cutIndex: Int) = (depth - 1) match {
+    case 5 =>
+      for (i <- 0 until ((cutIndex >>> 25) & 0x1f)) display5(i) = null
+      for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null
+      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
+      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
+      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+    case 4 =>
+      display5 = null
+      for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null
+      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
+      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
+      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+    case 3 =>
+      display5 = null
+      display4 = null
+      for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null
+      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
+      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+    case 2 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null
+      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+    case 1 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      display2 = null
+      for (i <- 0 until ((cutIndex >>>  5) & 0x1f)) display1(i) = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+    case 0 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      display2 = null
+      display1 = null
+      for (i <- 0 until ((cutIndex >>>  0) & 0x1f)) display0(i) = null
+  }
+
+  private def cleanRightEdge(cutIndex: Int) = (depth - 1) match {
+    case 5 =>
+      for (i <- ((cutIndex >>> 25) & 0x1f) until 32) display5(i) = null
+      for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null
+      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
+      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
+      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+    case 4 =>
+      display5 = null
+      for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null
+      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
+      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
+      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+    case 3 =>
+      display5 = null
+      display4 = null
+      for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null
+      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
+      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+    case 2 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null
+      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+    case 1 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      display2 = null
+      for (i <- ((cutIndex >>>  5) & 0x1f) until 32) display1(i) = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+    case 0 =>
+      display5 = null
+      display4 = null
+      display3 = null
+      display2 = null
+      display1 = null
+      for (i <- ((cutIndex >>>  0) & 0x1f) until 32) display0(i) = null
+  }
+
+  private def requiredDepth(xor: Int) = {
+    if (xor < (1 <<  5)) 1
+    else if (xor < (1 << 10)) 2
+    else if (xor < (1 << 15)) 3
+    else if (xor < (1 << 20)) 4
+    else if (xor < (1 << 25)) 5
+    else if (xor < (1 << 30)) 6
+    else throw new IllegalArgumentException()
+  }
+
+  private def dropFront0(cutIndex: Int): NewVector[A] = {
+    var blockIndex = cutIndex & ~31
+    var lo = cutIndex & 31
+
+    val xor = cutIndex ^ (endIndex - 1)
+    val d = requiredDepth(xor)
+    val shift = (cutIndex & ~((1 << (5*d))-1))
+
+    //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")")
+
+    val s = new NewVectorImpl(cutIndex-shift, endIndex-shift, blockIndex-shift)
+    s.initFrom(this)
+    if (s.depth > 1)
+      s.gotoPos(blockIndex, focus ^ blockIndex)
+    s.depth = d
+    s.stabilize(blockIndex-shift)
+    s.cleanLeftEdge(cutIndex-shift)
+    s
+  }
+
+  private def dropBack0(cutIndex: Int): NewVector[A] = {
+    var blockIndex = (cutIndex - 1) & ~31
+    var lo = ((cutIndex - 1) & 31) + 1
+
+    val xor = startIndex ^ (cutIndex - 1)
+    val d = requiredDepth(xor)
+
+    //println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")")
+
+    val s = new NewVectorImpl(startIndex, cutIndex, blockIndex)
+    s.initFrom(this)
+    if (s.depth > 1)
+      s.gotoPos(blockIndex, focus ^ blockIndex)
+    s.depth = d
+    s.stabilize(blockIndex)
+    s.cleanRightEdge(cutIndex)
+    s
+  }
+
 }
 
 
@@ -743,7 +765,7 @@ trait NewVectorPointer[T] {
     final def copyOf(a: Array[AnyRef]) = {
 //      //println("copy")
       val b = new Array[AnyRef](a.length)
-      System.arraycopy(a, 0, b, 0, a.length)
+      arraycopy(a, 0, b, 0, a.length)
       b
     }