diff options
-rw-r--r-- | src/library/scala/collection/immutable/Vector.scala | 57 | ||||
-rw-r--r-- | test/files/run/vector1.check | 6 | ||||
-rw-r--r-- | test/files/run/vector1.scala | 199 |
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") + } + +} + |