fixed problem with Vector.dropRight, added addi...

fixed problem with Vector.dropRight, added additional test case

3 files changed, 232 insertions, 30 deletions

diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index d0c3acd43b..e0a73fe427 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -30,9 +30,10 @@ object Vector extends SeqFactory[Vector] {
 }
 
 
+// TODO: most members are still public -> restrict access (caveat: private prevents inlining)
 
 @serializable
-final class Vector[+A](startIndex: Int, endIndex: Int, focus: Int) extends Seq[A] // TODO: protect members
+final class Vector[+A](startIndex: Int, endIndex: Int, focus: Int) extends Seq[A]
                  with GenericTraversableTemplate[A, Vector]
                  with SeqLike[A, Vector[A]]
                  with VectorPointer[A @uncheckedVariance] {
@@ -65,7 +66,6 @@ override def companion: GenericCompanion[Vector] = Vector
   // with local variables exclusively. But we're not quite there yet ...
 
   @inline def foreach0[U](f: A => U): Unit = iterator.foreach0(f)
-
   @inline def map0[B, That](f: A => B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = {
     val b = bf(repr)
     foreach0(x => b += f(x))
@@ -154,12 +154,6 @@ override def companion: GenericCompanion[Vector] = Vector
 
 
 
-  def gotoPosWritableFull(oldIndex: Int, newIndex: Int, xor: Int) = {
-    if (dirty) stabilize(oldIndex) // will copy level 1 to level d-1
-    gotoPosWritable0(newIndex, xor) // will copy level 0
-    dirty = true
-  }
-
   private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) {
     gotoPosWritable1(oldIndex, newIndex, xor)
   } else {
@@ -179,7 +173,14 @@ override def companion: GenericCompanion[Vector] = Vector
       var blockIndex = (startIndex - 1) & ~31
       var lo = (startIndex - 1) & 31
 
-      if (blockIndex + 32 == startIndex) {
+      if (startIndex != blockIndex + 32) {
+        val s = new Vector(startIndex - 1, endIndex, blockIndex)
+        s.initFrom(this)
+        s.dirty = dirty
+        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
+        s.display0(lo) = value.asInstanceOf[AnyRef]
+        s
+      } else {
 
         val freeSpace = ((1<<5*(depth)) - endIndex) // free space at the right given the current tree-structure depth
         val shift = freeSpace & ~((1<<5*(depth-1))-1) // number of elements by which we'll shift right (only move at top level)
@@ -250,14 +251,6 @@ override def companion: GenericCompanion[Vector] = Vector
           s
         }
 
-      } else {
-        //println("will make writable block (from "+focus+") at: " + blockIndex)
-        val s = new Vector(startIndex - 1, endIndex, blockIndex)
-        s.initFrom(this)
-        s.dirty = dirty
-        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
-        s.display0(lo) = value.asInstanceOf[AnyRef]
-        s
       }
     } else {
       // empty vector, just insert single element at the back
@@ -277,7 +270,15 @@ override def companion: GenericCompanion[Vector] = Vector
       var blockIndex = endIndex & ~31
       var lo = endIndex & 31
 
-      if (endIndex == blockIndex) {
+      if (endIndex != blockIndex) {
+        //println("will make writable block (from "+focus+") at: " + blockIndex)
+        val s = new Vector(startIndex, endIndex + 1, blockIndex)
+        s.initFrom(this)
+        s.dirty = dirty
+        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
+        s.display0(lo) = value.asInstanceOf[AnyRef]
+        s
+      } else {
         val shift = startIndex & ~((1<<5*(depth-1))-1)
         val shiftBlocks = startIndex >>> 5*(depth-1)
 
@@ -331,14 +332,6 @@ override def companion: GenericCompanion[Vector] = Vector
           }
           s
         }
-      } else {
-        //println("will make writable block (from "+focus+") at: " + blockIndex)
-        val s = new Vector(startIndex, endIndex + 1, blockIndex)
-        s.initFrom(this)
-        s.dirty = dirty
-        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
-        s.display0(lo) = value.asInstanceOf[AnyRef]
-        s
       }
     } else {
       val elems = new Array[AnyRef](32)
@@ -351,7 +344,7 @@ override def companion: GenericCompanion[Vector] = Vector
   }
 
 
-  // low-level implementation (needs cleanup)
+  // low-level implementation (needs cleanup, maybe move to util class)
 
   private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match {
     case 0 =>
@@ -377,6 +370,8 @@ override def companion: GenericCompanion[Vector] = Vector
   }
 
   def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = {
+//    if (array eq null)
+//      println("OUCH!!! " + right + "/" + depth + "/"+startIndex + "/" + endIndex + "/" + focus)
     val a2 = new Array[AnyRef](array.length)
     Platform.arraycopy(array, 0, a2, 0, right)
     a2
@@ -456,7 +451,7 @@ override def companion: GenericCompanion[Vector] = Vector
   // requires structure is writable and at index cutIndex
   private def cleanRightEdge(cutIndex: Int) = {
 
-    // FIXME: we're actually sitting one block left if cutIndex lies on a block boundary
+    // we're actually sitting one block left if cutIndex lies on a block boundary
     // this means that we'll end up erasing the whole block!!
 
     if (cutIndex <= (1 << 5)) {
@@ -544,17 +539,19 @@ override def companion: GenericCompanion[Vector] = Vector
 
     val xor = startIndex ^ (cutIndex - 1)
     val d = requiredDepth(xor)
+    val shift = (startIndex & ~((1 << (5*d))-1))
+
 /*
     println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")")
     if (cutIndex == blockIndex + 32)
       println("OUCH!!!")
 */
-    val s = new Vector(startIndex, cutIndex, blockIndex)
+    val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift)
     s.initFrom(this)
     s.dirty = dirty
     s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
     s.preClean(d)
-    s.cleanRightEdge(cutIndex)
+    s.cleanRightEdge(cutIndex-shift)
     s
   }
 
diff --git a/test/files/run/vector1.check b/test/files/run/vector1.check
new file mode 100644
index 0000000000..10447a0964
--- /dev/null
+++ b/test/files/run/vector1.check
@@ -0,0 +1,6 @@
+===== test1 =====
+===== test2 =====
+===== test3 =====
+===== test4 =====
+===== test5 =====
+done
diff --git a/test/files/run/vector1.scala b/test/files/run/vector1.scala
new file mode 100644
index 0000000000..320bef220c
--- /dev/null
+++ b/test/files/run/vector1.scala
@@ -0,0 +1,199 @@
+// testing the impl from the scala library
+//package test5
+
+import scala.collection._
+import scala.collection.immutable._
+
+import scala.collection.generic._
+import scala.collection.mutable.Builder
+
+
+object Test {
+
+    def vector(label: String, n: Int): Vector[String] = {
+      val a = new VectorBuilder[String]
+      for (i <- 0 until n)
+        a += (label + i)
+
+      val res = a.result
+      assertVector(res, label, 0, n)
+    }
+
+    def vectorForward(label: String, n: Int): Vector[String] = {
+      var a: Vector[String] = Vector.empty
+      for (i <- 0 until n)
+        a = a.appendBack(label + i)
+
+      assertVector(a, label, 0, n)
+    }
+
+    def vectorBackward(label: String, n: Int): Vector[String] = {
+      var a: Vector[String] = Vector.empty
+      for (i <- 0 until n)
+        a = a.appendFront(label + (n-1-i))
+
+      assertVector(a, label, 0, n)
+    }
+
+    def assertVector[V](a: Vector[V], label: String, start: Int, end: Int) = {
+      assertVectorIndexed(a, label, start, end)
+      assertVectorIterated(a, label, start, end)
+    }
+
+    def assertVectorIndexed[V](a: Vector[V], label: String, start: Int, end: Int) = {
+      val res = a
+      assert(res.length == (end-start), res.length+"!="+(end-start)+" ("+res+")")
+      for (i <- start until end) {
+        assert(res(i) == (label + i), ""+res(i)+"!="+(label + i))
+      }
+      res
+    }
+
+    def assertVectorIterated[V](a: Vector[V], label: String, start: Int, end: Int) = {
+      val res = a
+      assert(res.length == (end-start), res.length+"!="+(end-start)+" ("+res+")")
+      var i = start
+      var it = res.iterator
+      while(it.hasNext) {
+        val x = it.next()
+        assert(x == (label + i), x.toString+"!="+(label + i))
+        i += 1
+      }
+      assert(i == end)
+      res
+    }
+
+
+
+  def test1() = {
+    println("===== test1 =====")
+
+    val N = 150000
+    val a = vector("a", N)
+    val b = vectorForward("b", N)
+    val c = vectorBackward("b", N)
+
+    ()
+//    //println(a)
+  }
+
+  def test2() = {
+    println("===== test2 =====")
+
+    var a: Vector[String] = Vector.empty
+
+    val rand = new java.util.Random
+
+    val N = 150000
+    var min = N/2//rand.nextInt(N)
+    var max = min
+
+    val chunkLimit = 11
+
+    def nextChunkSize = 3 //rand.nextInt(chunkLimit)
+
+    def seqBack() = for (i <- 0 until Math.min(nextChunkSize, N-max)) { a = a.appendBack("a"+max); max += 1 }
+    def seqFront() = for (i <- 0 until Math.min(nextChunkSize, min)) { min -= 1; a = a.appendFront("a"+min) }
+
+    try {
+
+    while (min > 0 || max < N) {
+      seqFront()
+      seqBack()
+    }
+  } catch {
+    case ex =>
+      //println("----------------")
+      a.debug
+      throw ex
+  }
+
+    assertVector(a, "a", 0, N)
+  }
+
+
+
+  def test3() = {
+    println("===== test3 =====")
+
+    val N = 150000
+    val a = vector("a", N)
+
+    val pos = scala.util.Random.shuffle(scala.collection.mutable.WrappedArray.make[Int](Array.tabulate[Int](N)(i => i)))
+
+    var b = a
+
+    {
+      var i = 0
+      while (i < N) {
+        b = b.updated(pos(i), "b"+(pos(i)))
+        i += 1
+      }
+
+      assertVector(b, "b", 0, N)
+    }
+
+//    //println(a)
+  }
+
+  def test4() = {
+    println("===== test4 =====")
+
+    val N = 150000
+    val a = vectorForward("a", N)
+
+    {
+      var i = 0
+      var it = a
+      while (i < N) {
+        assert(it.length == (N-i), it.length+" items at iteration "+i)
+        val x = it(0)
+        val y = it(N-i-1)
+        assert(x == "a"+i, x+"!=a"+i)
+        assert(y == "a"+(N-1), y+"!=a"+(N-1))
+        it = it.drop(1)
+        i += 1
+      }
+      assert(it.length == 0)
+    }
+
+//    //println(a)
+  }
+
+  def test5() = {
+    println("===== test5 =====")
+
+    val N = 150000
+    val a = vectorBackward("a", N)
+
+    {
+      var i = 0
+      var it = a
+      while (i < N) {
+        assert(it.length == (N-i), it.length+" items at iteration "+i)
+        val x = it(0)
+        val y = it(N-i-1)
+//        println("x " + x + "/" + i)
+//        println("y " + y)
+        assert(x == "a0", x+"!=a0")
+        assert(y == "a"+(N-i-1), y+"!=a"+(N-i-1))
+        it = it.dropRight(1)
+        i += 1
+      }
+      assert(it.length == 0)
+    }
+  }
+
+  def main(args: Array[String]) = {
+
+    test1()
+    test2()
+    test3()
+    test4()
+    test5()
+
+    println("done")
+  }
+
+}
+