diff options
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/Vector.scala | 752 |
1 files changed, 315 insertions, 437 deletions
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index d9d925705f..1093084b9d 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -23,7 +23,7 @@ object Vector extends IndexedSeqFactory[Vector] { ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] private[immutable] val NIL = new Vector[Nothing](0, 0, 0) override def empty[A]: Vector[A] = NIL - + // Constants governing concat strategy for performance private final val Log2ConcatFaster = 5 private final val TinyAppendFaster = 2 @@ -71,12 +71,7 @@ extends AbstractSeq[A] with CustomParallelizable[A, ParVector[A]] { self => -override def companion: GenericCompanion[Vector] = Vector - - //assert(startIndex >= 0, startIndex+"<0") - //assert(startIndex <= endIndex, startIndex+">"+endIndex) - //assert(focus >= 0, focus+"<0") - //assert(focus <= endIndex, focus+">"+endIndex) + override def companion: GenericCompanion[Vector] = Vector private[immutable] var dirty = false @@ -100,8 +95,6 @@ override def companion: GenericCompanion[Vector] = Vector s } - - // can still be improved override /*SeqLike*/ def reverseIterator: Iterator[A] = new AbstractIterator[A] { private var i = self.length @@ -113,22 +106,18 @@ override def companion: GenericCompanion[Vector] = Vector } else Iterator.empty.next() } - // TODO: reverse - - // TODO: check performance of foreach/map etc. should override or not? // Ideally, clients will inline calls to map all the way down, including the iterator/builder methods. // In principle, escape analysis could even remove the iterator/builder allocations and do it // with local variables exclusively. But we're not quite there yet ... 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) + if (index >= 0 && idx < endIndex) idx else throw new IndexOutOfBoundsException(index.toString) @@ -137,7 +126,7 @@ override def companion: GenericCompanion[Vector] = Vector // If we have a default builder, there are faster ways to perform some operations @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean = (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF) - + // SeqLike api override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = @@ -191,31 +180,36 @@ override def companion: GenericCompanion[Vector] = Vector Vector.empty } - override /*IterableLike*/ def head: A = { + override /*IterableLike*/ + def head: A = { if (isEmpty) throw new UnsupportedOperationException("empty.head") apply(0) } - override /*TraversableLike*/ def tail: Vector[A] = { + override /*TraversableLike*/ + def tail: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.tail") drop(1) } - override /*TraversableLike*/ def last: A = { + override /*TraversableLike*/ + def last: A = { if (isEmpty) throw new UnsupportedOperationException("empty.last") - apply(length-1) + apply(length - 1) } - override /*TraversableLike*/ def init: Vector[A] = { + override /*TraversableLike*/ + def init: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.init") dropRight(1) } - override /*IterableLike*/ def slice(from: Int, until: Int): Vector[A] = + override /*IterableLike*/ + def slice(from: Int, until: Int): Vector[A] = take(until).drop(from) - override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) - + override /*IterableLike*/ + def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { @@ -227,11 +221,11 @@ override def companion: GenericCompanion[Vector] = Vector val again = if (!that.isTraversableAgain) that.toVector else that.seq again.size match { // Often it's better to append small numbers of elements (or prepend if RHS is a vector) - case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + case n if n <= TinyAppendFaster || n < (this.size >>> Log2ConcatFaster) => var v: Vector[B] = this for (x <- again) v = v :+ x v.asInstanceOf[That] - case n if this.size < (n >> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => + case n if this.size < (n >>> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => var v = again.asInstanceOf[Vector[B]] val ri = this.reverseIterator while (ri.hasNext) v = ri.next +: v @@ -243,8 +237,6 @@ override def companion: GenericCompanion[Vector] = Vector else super.++(that.seq) } - - // semi-private api private[immutable] def updateAt[B >: A](index: Int, elem: B): Vector[B] = { @@ -253,11 +245,10 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, idx, focus ^ idx) // if dirty commit changes; go to new pos and prepare for writing - s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef] + s.display0(idx & 31) = elem.asInstanceOf[AnyRef] s } - private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) { gotoPosWritable1(oldIndex, newIndex, xor) } else { @@ -272,7 +263,7 @@ override def companion: GenericCompanion[Vector] = Vector dirty = true } - private[immutable] def appendFront[B>:A](value: B): Vector[B] = { + private[immutable] def appendFront[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = (startIndex - 1) & ~31 val lo = (startIndex - 1) & 31 @@ -286,61 +277,46 @@ override def companion: GenericCompanion[Vector] = Vector 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) - val shiftBlocks = freeSpace >>> 5*(depth-1) // number of top-level blocks + 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) + val shiftBlocks = freeSpace >>> (5 * (depth - 1)) // number of top-level blocks - //println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start") if (shift != 0) { // case A: we can shift right on the top level - debug() - //println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - if (depth > 1) { val newBlockIndex = blockIndex + shift val newFocus = focus + shift + val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex + 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing - s.display0(shift-1) = value.asInstanceOf[AnyRef] - s.debug() + s.display0(shift - 1) = value.asInstanceOf[AnyRef] s } } else if (blockIndex < 0) { // case B: we need to move the whole structure - val move = (1 << 5*(depth+1)) - (1 << 5*(depth)) - //println("moving right by " + move + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - + val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth)) val newBlockIndex = blockIndex + move val newFocus = focus + move - val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) s.dirty = dirty - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(s.depth == depth+1) s } else { val newBlockIndex = blockIndex @@ -351,31 +327,26 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth) s } - } } else { // empty vector, just insert single element at the back val elems = new Array[AnyRef](32) elems(31) = value.asInstanceOf[AnyRef] - val s = new Vector(31,32,0) + val s = new Vector(31, 32, 0) s.depth = 1 s.display0 = elems s } } - private[immutable] def appendBack[B>:A](value: B): Vector[B] = { -// //println("------- append " + value) -// debug() + private[immutable] def appendBack[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = endIndex & ~31 val lo = endIndex & 31 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 @@ -383,41 +354,31 @@ override def companion: GenericCompanion[Vector] = Vector s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1<<5*(depth-1))-1) - val shiftBlocks = startIndex >>> 5*(depth-1) - - //println("----- appendBack " + value + " at " + endIndex + " reached block end") + val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) + val shiftBlocks = startIndex >>> (5 * (depth - 1)) if (shift != 0) { - debug() - //println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)") if (depth > 1) { val newBlockIndex = blockIndex - shift val newFocus = focus - shift + val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex - 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(32 - shift) = value.asInstanceOf[AnyRef] - s.debug() s } } else { @@ -429,18 +390,13 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth+1) might or might not create new level! - if (s.depth == depth+1) { - //println("creating new level " + s.depth + " (had "+0+" free space)") - s.debug() - } s } } } else { val elems = new Array[AnyRef](32) elems(0) = value.asInstanceOf[AnyRef] - val s = new Vector(0,1,0) + val s = new Vector(0, 1, 0) s.depth = 1 s.display0 = elems s @@ -451,39 +407,39 @@ override def companion: GenericCompanion[Vector] = Vector // low-level implementation (needs cleanup, maybe move to util class) 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) + 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 zeroLeft(array: Array[AnyRef], index: Int): Unit = { - var i = 0; while (i < index) { array(i) = null; i+=1 } + var i = 0 + while (i < index) { + array(i) = null + i += 1 + } } private def zeroRight(array: Array[AnyRef], index: Int): Unit = { - var i = index; while (i < array.length) { array(i) = null; i+=1 } + var i = index + while (i < array.length) { + array(i) = null + i += 1 + } } private 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) - java.lang.System.arraycopy(array, 0, a2, 0, right) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, 0, copy, 0, right) + copy } private def copyRight(array: Array[AnyRef], left: Int): Array[AnyRef] = { - val a2 = new Array[AnyRef](array.length) - java.lang.System.arraycopy(array, left, a2, left, a2.length - left) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, left, copy, left, copy.length - left) + copy } private def preClean(depth: Int) = { @@ -515,38 +471,33 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is at index cutIndex and writable at level 0 private def cleanLeftEdge(cutIndex: Int) = { - if (cutIndex < (1 << 5)) { + if (cutIndex < (1 << 5)) { zeroLeft(display0, cutIndex) - } else - if (cutIndex < (1 << 10)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5)) - } else - if (cutIndex < (1 << 15)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10)) - } else - if (cutIndex < (1 << 20)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15)) - } else - if (cutIndex < (1 << 25)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20)) - } else - if (cutIndex < (1 << 30)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20) & 0x1f) - display5 = copyRight(display5, (cutIndex >>> 25)) + } else if (cutIndex < (1 << 10)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, cutIndex >>> 5) + } else if (cutIndex < (1 << 15)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, cutIndex >>> 10) + } else if (cutIndex < (1 << 20)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, cutIndex >>> 15) + } else if (cutIndex < (1 << 25)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, cutIndex >>> 20) + } else if (cutIndex < (1 << 30)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, (cutIndex >>> 20) & 31) + display5 = copyRight(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } @@ -554,49 +505,43 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is writable and at index cutIndex private def cleanRightEdge(cutIndex: Int) = { - // 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)) { + if (cutIndex <= (1 << 5)) { zeroRight(display0, cutIndex) - } else - if (cutIndex <= (1 << 10)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (cutIndex >>> 5)) - } else - if (cutIndex <= (1 << 15)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (cutIndex >>> 10)) - } else - if (cutIndex <= (1 << 20)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (cutIndex >>> 15)) - } else - if (cutIndex <= (1 << 25)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (cutIndex >>> 20)) - } else - if (cutIndex <= (1 << 30)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (((cutIndex-1) >>> 20) & 0x1f) + 1) - display5 = copyLeft(display5, (cutIndex >>> 25)) + } else if (cutIndex <= (1 << 10)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, cutIndex >>> 5) + } else if (cutIndex <= (1 << 15)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, cutIndex >>> 10) + } else if (cutIndex <= (1 << 20)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, cutIndex >>> 15) + } else if (cutIndex <= (1 << 25)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, cutIndex >>> 20) + } else if (cutIndex <= (1 << 30)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, (((cutIndex - 1) >>> 20) & 31) + 1) + display5 = copyLeft(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } } private def requiredDepth(xor: Int) = { - if (xor < (1 << 5)) 1 + if (xor < (1 << 5)) 1 else if (xor < (1 << 10)) 2 else if (xor < (1 << 15)) 3 else if (xor < (1 << 20)) 4 @@ -609,24 +554,11 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = 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 Vector(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 -*/ + val shift = cutIndex & ~((1 << (5 * d)) - 1) // need to init with full display iff going to cutIndex requires swapping block at level >= d - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) + val s = new Vector(cutIndex - shift, endIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) @@ -639,25 +571,18 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = (cutIndex - 1) & ~31 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-shift, cutIndex-shift, blockIndex-shift) + val shift = startIndex & ~((1 << (5 * d)) - 1) + + 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-shift) + s.cleanRightEdge(cutIndex - shift) s } - } - class VectorIterator[+A](_startIndex: Int, endIndex: Int) extends AbstractIterator[A] with Iterator[A] @@ -680,7 +605,7 @@ extends AbstractIterator[A] if (lo == endLo) { if (blockIndex + lo < endIndex) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStart(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex @@ -707,7 +632,7 @@ extends AbstractIterator[A] } /** A class to build instances of `Vector`. This builder is reusable. */ -final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorPointer[A @uncheckedVariance] { +final class VectorBuilder[A]() extends ReusableBuilder[A, Vector[A]] with VectorPointer[A @uncheckedVariance] { // possible alternative: start with display0 = null, blockIndex = -32, lo = 32 // to avoid allocating initial array if the result will be empty anyways @@ -718,9 +643,9 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP private var blockIndex = 0 private var lo = 0 - def += (elem: A): this.type = { + def +=(elem: A): this.type = { if (lo >= display0.length) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStartWritable(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex lo = 0 @@ -730,8 +655,7 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP this } - override def ++=(xs: TraversableOnce[A]): this.type = - super.++=(xs) + override def ++=(xs: TraversableOnce[A]): this.type = super.++=(xs) def result: Vector[A] = { val size = blockIndex + lo @@ -751,10 +675,8 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP } } - - private[immutable] trait VectorPointer[T] { - private[immutable] var depth: Int = _ + private[immutable] var depth: Int = _ private[immutable] var display0: Array[AnyRef] = _ private[immutable] var display1: Array[AnyRef] = _ private[immutable] var display2: Array[AnyRef] = _ @@ -799,98 +721,102 @@ private[immutable] trait VectorPointer[T] { } } - // requires structure is at pos oldIndex = xor ^ index private[immutable] final def getElem(index: Int, xor: Int): T = { - if (xor < (1 << 5)) { // level = 0 - display0(index & 31).asInstanceOf[T] - } else - if (xor < (1 << 10)) { // level = 1 - display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 15)) { // level = 2 - display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 20)) { // level = 3 - display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 25)) { // level = 4 - display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 30)) { // level = 5 - display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]]((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + (display0 + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 10)) { // level = 1 + (display1 + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 15)) { // level = 2 + (display2 + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 20)) { // level = 3 + (display3 + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 25)) { // level = 4 + (display4 + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 30)) { // level = 5 + (display5 + ((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else { // level = 6 throw new IllegalArgumentException() } } - // go to specific position // requires structure is at pos oldIndex = xor ^ index, // ensures structure is at pos index private[immutable] final def gotoPos(index: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 (could maybe removed) - } else - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start pos + } else if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else { // level = 6 throw new IllegalArgumentException() } } - - // USED BY ITERATOR // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] + if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] display3 = display4(0).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -899,73 +825,65 @@ private[immutable] trait VectorPointer[T] { // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStartWritable(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth+=1} + if (xor < (1 << 10)) { // level = 1 + if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth += 1 } display0 = new Array(32) - display1((index >> 5) & 31) = display0 - } else - if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth+=1} + display1((index >>> 5) & 31) = display0 + } else if (xor < (1 << 15)) { // level = 2 + if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth += 1 } display0 = new Array(32) display1 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - } else - if (xor < (1 << 20)) { // level = 3 - if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + } else if (xor < (1 << 20)) { // level = 3 + if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - } else - if (xor < (1 << 25)) { // level = 4 - if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + } else if (xor < (1 << 25)) { // level = 4 + if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - } else - if (xor < (1 << 30)) { // level = 5 - if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + } else if (xor < (1 << 30)) { // level = 5 + if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) display4 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - display5((index >> 25) & 31) = display4 - } else { // level = 6 + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + display5((index >>> 25) & 31) = display4 + } else { // level = 6 throw new IllegalArgumentException() } } - - // STUFF BELOW USED BY APPEND / UPDATE - private[immutable] final def copyOf(a: Array[AnyRef]) = { - val b = new Array[AnyRef](a.length) - java.lang.System.arraycopy(a, 0, b, 0, a.length) - b + private[immutable] final def copyOf(a: Array[AnyRef]): Array[AnyRef] = { + val copy = new Array[AnyRef](a.length) + java.lang.System.arraycopy(a, 0, copy, 0, a.length) + copy } - private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { - //println("copy and null") + private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int): Array[AnyRef] = { val x = array(index) array(index) = null copyOf(x.asInstanceOf[Array[AnyRef]]) } - // make sure there is no aliasing // requires structure is at pos index // ensures structure is clean and at pos index and writable at all levels except 0 @@ -977,40 +895,39 @@ private[immutable] trait VectorPointer[T] { display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display5((index >> 25) & 31) = display4 - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display5((index >>> 25) & 31) = display4 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 4 => display4 = copyOf(display4) display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 3 => display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 2 => display2 = copyOf(display2) display1 = copyOf(display1) - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 1 => display1 = copyOf(display1) - display1((index >> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 case 0 => } - /// USED IN UPDATE AND APPEND BACK // prepare for writing at an existing position @@ -1020,29 +937,29 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def gotoPosWritable0(newIndex: Int, xor: Int): Unit = (depth - 1) match { case 5 => display5 = copyOf(display5) - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 4 => display4 = copyOf(display4) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 3 => display3 = copyOf(display3) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 2 => display2 = copyOf(display2) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 1 => display1 = copyOf(display1) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 0 => display0 = copyOf(display0) } @@ -1051,64 +968,59 @@ private[immutable] trait VectorPointer[T] { // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 + if (xor < (1 << 5)) { // level = 0 display0 = copyOf(display0) - } else - if (xor < (1 << 10)) { // level = 1 + } else if (xor < (1 << 10)) { // level = 1 display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 15)) { // level = 2 + display1((oldIndex >>> 5) & 31) = display0 + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 15)) { // level = 2 display1 = copyOf(display1) display2 = copyOf(display2) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 20)) { // level = 3 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 25)) { // level = 4 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 30)) { // level = 5 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) display5 = copyOf(display5) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display5((oldIndex >> 25) & 31) = display4 - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display5((oldIndex >>> 25) & 31) = display4 + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else { // level = 6 throw new IllegalArgumentException() } } @@ -1118,117 +1030,83 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { val elems = new Array[AnyRef](32) - java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft,oldLeft)) + java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft, oldLeft)) elems } - - // USED IN APPEND // create a new block at the bottom level (and possibly nodes on its path) and prepares for writing // requires structure is clean and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable0(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 5)) { // level = 0 - //println("XXX clean with low xor") - } else - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start + } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { display1 = new Array(32) - display1((oldIndex >> 5) & 31) = display0 - depth +=1 + display1((oldIndex >>> 5) & 31) = display0 + depth += 1 } display0 = new Array(32) - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 if (depth == 2) { display2 = new Array(32) - display2((oldIndex >> 10) & 31) = display1 - depth +=1 + display2((oldIndex >>> 10) & 31) = display1 + depth += 1 } - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 if (depth == 3) { display3 = new Array(32) - display3((oldIndex >> 15) & 31) = display2 - depth +=1 + display3((oldIndex >>> 15) & 31) = display2 + depth += 1 } - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 if (depth == 4) { display4 = new Array(32) - display4((oldIndex >> 20) & 31) = display3 - depth +=1 + display4((oldIndex >>> 20) & 31) = display3 + depth += 1 } - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 if (depth == 5) { display5 = new Array(32) - display5((oldIndex >> 25) & 31) = display4 - depth +=1 + display5((oldIndex >>> 25) & 31) = display4 + depth += 1 } - display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] + display4 = display5((newIndex >>> 25) & 31).asInstanceOf[Array[AnyRef]] if (display4 == null) display4 = new Array(32) - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } - // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } - - - - - // DEBUG STUFF - - private[immutable] def debug(): Unit = { - return -/* - //println("DISPLAY 5: " + display5 + " ---> " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 4: " + display4 + " ---> " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 3: " + display3 + " ---> " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 2: " + display2 + " ---> " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 1: " + display1 + " ---> " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 0: " + display0 + " ---> " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) -*/ - //println("DISPLAY 5: " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 4: " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 3: " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 2: " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 1: " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 0: " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) - } - - } - |