diff options
author | Tiark Rompf <tiark.rompf@epfl.ch> | 2009-11-02 06:57:36 +0000 |
---|---|---|
committer | Tiark Rompf <tiark.rompf@epfl.ch> | 2009-11-02 06:57:36 +0000 |
commit | 4f373f6da905e1db55ded5795b8d273ffd0bf1bc (patch) | |
tree | 5ce7f0d8e55f8ea576409403b2e06e12c88d2e30 | |
parent | 852f027607699ac4a11f7bae752c2455ff0f7151 (diff) | |
download | scala-4f373f6da905e1db55ded5795b8d273ffd0bf1bc.tar.gz scala-4f373f6da905e1db55ded5795b8d273ffd0bf1bc.tar.bz2 scala-4f373f6da905e1db55ded5795b8d273ffd0bf1bc.zip |
Vector improvements, now doing a lot less copyi...
Vector improvements, now doing a lot less copying for single element
appends/updates
-rw-r--r-- | src/library/scala/collection/immutable/Vector.scala | 847 |
1 files changed, 455 insertions, 392 deletions
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 5cc95df8c9..d0c3acd43b 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -12,27 +12,27 @@ package scala.collection package immutable import scala.annotation.unchecked.uncheckedVariance -import compat.Platform.arraycopy +import compat.Platform import scala.collection.generic._ import scala.collection.mutable.Builder object Vector extends SeqFactory[Vector] { - private[immutable] val BF = new GenericCanBuildFrom[Nothing] { + /*private[immutable]*/ val BF = new GenericCanBuildFrom[Nothing] { override def apply() = newBuilder[Nothing] } @inline implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Vector[A]] = BF.asInstanceOf[CanBuildFrom[Coll, A, Vector[A]]] def newBuilder[A]: Builder[A, Vector[A]] = new VectorBuilder[A] - private[immutable] val NIL = new Vector[Nothing](0, 0, 0) + /*private[immutable]*/ val NIL = new Vector[Nothing](0, 0, 0) @inline override def empty[A]: Vector[A] = NIL } @serializable -final class Vector[+A](startIndex: Int, endIndex: Int, focus: Int) extends Seq[A] +final class Vector[+A](startIndex: Int, endIndex: Int, focus: Int) extends Seq[A] // TODO: protect members with GenericTraversableTemplate[A, Vector] with SeqLike[A, Vector[A]] with VectorPointer[A @uncheckedVariance] { @@ -44,14 +44,14 @@ override def companion: GenericCompanion[Vector] = Vector //assert(focus >= 0, focus+"<0") //assert(focus <= endIndex, focus+">"+endIndex) - var dirty = false + /*private*/ var dirty = false def length = endIndex - startIndex override def lengthCompare(len: Int): Int = length - len - override def iterator: VectorIterator[A] = { + @inline override def iterator: VectorIterator[A] = { val s = new VectorIterator[A](startIndex, endIndex) s.initFrom(this) if (dirty) s.stabilize(focus) @@ -59,12 +59,25 @@ override def companion: GenericCompanion[Vector] = Vector s } + // 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 ... + + @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)) + b.result + } + // 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+")") + //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") getElem(idx, idx ^ focus) } @@ -133,12 +146,34 @@ override def companion: GenericCompanion[Vector] = Vector val idx = checkRangeConvert(index) val s = new Vector[B](startIndex, endIndex, idx) s.initFrom(this) - s.gotoPosClean(focus, idx, focus ^ idx) // if dirty commit changes; go to new pos and prepare for writing + 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.dirty = true s } + + + 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 { + gotoPosWritable0(newIndex, xor) + dirty = true + } + + private def gotoFreshPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) { + gotoFreshPosWritable1(oldIndex, newIndex, xor) + } else { + gotoFreshPosWritable0(oldIndex, newIndex, xor) + dirty = true + } + def appendFront[B>:A](value: B): Vector[B] = { if (endIndex != startIndex) { var blockIndex = (startIndex - 1) & ~31 @@ -146,9 +181,9 @@ override def companion: GenericCompanion[Vector] = Vector if (blockIndex + 32 == startIndex) { - val freeSpace = ((1<<5*(depth)) - endIndex) - val shift = freeSpace & ~((1<<5*(depth-1))-1) - val shiftBlocks = freeSpace >>> 5*(depth-1) + 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) { @@ -161,9 +196,10 @@ override def companion: GenericCompanion[Vector] = Vector 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.gotoFreshPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing + s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] //assert(depth == s.depth) s @@ -176,8 +212,9 @@ override def companion: GenericCompanion[Vector] = Vector 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.gotoPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing + s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing s.display0(shift-1) = value.asInstanceOf[AnyRef] s.debug s @@ -193,8 +230,9 @@ override def companion: GenericCompanion[Vector] = Vector val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) + s.dirty = dirty s.debug - s.gotoFreshPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch + 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) @@ -205,17 +243,19 @@ override def companion: GenericCompanion[Vector] = Vector val s = new Vector(startIndex - 1, endIndex, newBlockIndex) s.initFrom(this) - s.gotoFreshPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) + s.dirty = dirty + s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] //assert(s.depth == depth) s } } else { -// //println("will make writable block (from "+focus+") at: " + blockIndex) + //println("will make writable block (from "+focus+") at: " + blockIndex) val s = new Vector(startIndex - 1, endIndex, blockIndex) s.initFrom(this) - s.gotoPosClean(focus, blockIndex, focus ^ blockIndex) + s.dirty = dirty + s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] s } @@ -251,9 +291,10 @@ override def companion: GenericCompanion[Vector] = Vector 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.gotoFreshPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) + s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] s.debug //assert(depth == s.depth) @@ -267,8 +308,9 @@ override def companion: GenericCompanion[Vector] = Vector 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.gotoPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) + s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(32 - shift) = value.asInstanceOf[AnyRef] s.debug s @@ -279,7 +321,8 @@ override def companion: GenericCompanion[Vector] = Vector val s = new Vector(startIndex, endIndex + 1, newBlockIndex) s.initFrom(this) - s.gotoFreshPosClean(newFocus, newBlockIndex, newFocus ^ newBlockIndex) + 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) { @@ -289,10 +332,11 @@ override def companion: GenericCompanion[Vector] = Vector s } } else { -// //println("will make writable block (from "+focus+") at: " + blockIndex) + //println("will make writable block (from "+focus+") at: " + blockIndex) val s = new Vector(startIndex, endIndex + 1, blockIndex) s.initFrom(this) - s.gotoPosClean(focus, blockIndex, focus ^ blockIndex) + s.dirty = dirty + s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] s } @@ -309,12 +353,6 @@ override def companion: GenericCompanion[Vector] = Vector // 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) @@ -330,94 +368,132 @@ override def companion: GenericCompanion[Vector] = Vector 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 + def zeroLeft(array: Array[AnyRef], index: Int): Unit = { + var i = 0; while (i < index) { array(i) = null; i+=1 } } - 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 + def zeroRight(array: Array[AnyRef], index: Int): Unit = { + var i = index; while (i < array.length) { array(i) = null; i+=1 } + } + + def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = { + val a2 = new Array[AnyRef](array.length) + Platform.arraycopy(array, 0, a2, 0, right) + a2 + } + def copyRight(array: Array[AnyRef], left: Int): Array[AnyRef] = { + val a2 = new Array[AnyRef](array.length) + Platform.arraycopy(array, left, a2, left, a2.length - left) + a2 + } + + private def preClean(depth: Int) = { + this.depth = depth + (depth - 1) match { + case 0 => + display1 = null + display2 = null + display3 = null + display4 = null + display5 = null + case 1 => + display2 = null + display3 = null + display4 = null + display5 = null + case 2 => + display3 = null + display4 = null + display5 = null + case 3 => + display4 = null + display5 = null + case 4 => + display5 = null + case 5 => + } + } + + // requires structure is at index cutIndex and writable at level 0 + private def cleanLeftEdge(cutIndex: Int) = { + 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 { + throw new IllegalArgumentException() + } + } + + // 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 + // this means that we'll end up erasing the whole block!! + + 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 { + throw new IllegalArgumentException() + } } private def requiredDepth(xor: Int) = { @@ -440,6 +516,7 @@ override def companion: GenericCompanion[Vector] = Vector //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) @@ -448,6 +525,17 @@ override def companion: GenericCompanion[Vector] = Vector s.stabilize(blockIndex-shift) s.cleanLeftEdge(cutIndex-shift) s +*/ + + // 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) + s.initFrom(this) + s.dirty = dirty + s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) + s.preClean(d) + s.cleanLeftEdge(cutIndex - shift) + s } private def dropBack0(cutIndex: Int): Vector[A] = { @@ -456,15 +544,16 @@ override def companion: GenericCompanion[Vector] = Vector val xor = startIndex ^ (cutIndex - 1) val d = requiredDepth(xor) - - //println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") - +/* + println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") + if (cutIndex == blockIndex + 32) + println("OUCH!!!") +*/ val s = new Vector(startIndex, cutIndex, blockIndex) s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex) + s.dirty = dirty + s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) + s.preClean(d) s.cleanRightEdge(cutIndex) s } @@ -508,21 +597,27 @@ final class VectorIterator[+A](_startIndex: Int, _endIndex: Int) extends Iterato // TODO: take // TODO: drop + + // TODO: remove! + @inline def foreach0[U](f: A => U) { while (hasNext) f(next()) } } final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A @uncheckedVariance] { + // TODO: possible alternative: start with display0 = null, blockIndex = -32, lo = 32 + // to avoid allocation initial array if the result will be empty anyways + display0 = new Array[AnyRef](32) depth = 1 - var blockIndex = 0 - var lo = 0 + private var blockIndex = 0 + private var lo = 0 def += (elem: A): this.type = { if (lo == 32) { val newBlockIndex = blockIndex+32 - gotoNextBlockStartClean(newBlockIndex, blockIndex ^ newBlockIndex) + gotoNextBlockStartWritable(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex lo = 0 } @@ -532,6 +627,8 @@ final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A } def result: Vector[A] = { + if (blockIndex + lo == 0) + return Vector.empty val s = new Vector[A](0, blockIndex + lo, 0) // TODO: should focus front or back? s.initFrom(this) if (depth > 1) s.gotoPos(0, blockIndex + lo) @@ -548,19 +645,22 @@ final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A -trait VectorPointer[T] { - var depth: Int = _ - var display0: Array[AnyRef] = _ - var display1: Array[AnyRef] = _ - var display2: Array[AnyRef] = _ - var display3: Array[AnyRef] = _ - var display4: Array[AnyRef] = _ - var display5: Array[AnyRef] = _ +private[immutable] trait VectorPointer[T] { + var depth: Int = _ + var display0: Array[AnyRef] = _ + var display1: Array[AnyRef] = _ + var display2: Array[AnyRef] = _ + var display3: Array[AnyRef] = _ + var display4: Array[AnyRef] = _ + var display5: Array[AnyRef] = _ // used - final def initFrom[U](that: VectorPointer[U]) = { - depth = that.depth + final def initFrom[U](that: VectorPointer[U]): Unit = initFrom(that, that.depth) + + final def initFrom[U](that: VectorPointer[U], depth: Int) = { + this.depth = depth (depth - 1) match { + case -1 => case 0 => display0 = that.display0 case 1 => @@ -591,8 +691,9 @@ trait VectorPointer[T] { } } - // used - final def getElem(index: Int, xor: Int): T = { + + // requires structure is at pos oldIndex = xor ^ index + final def getElem(index: Int, xor: Int): T = { if (xor < (1 << 5)) { // level = 0 display0(index & 31).asInstanceOf[T] } else @@ -615,41 +716,48 @@ trait VectorPointer[T] { } } - // unused currently - final def gotoZeroInit(elems: Array[AnyRef]) = (depth - 1) match { // goto pos zero - case 5 => - display5 = elems.asInstanceOf[Array[AnyRef]] - display4 = display5(0).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]] - case 4 => - display4 = elems.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]] - case 3 => - display3 = elems.asInstanceOf[Array[AnyRef]] - display2 = display3(0).asInstanceOf[Array[AnyRef]] - display1 = display2(0).asInstanceOf[Array[AnyRef]] - display0 = display1(0).asInstanceOf[Array[AnyRef]] - case 2 => - display2 = elems.asInstanceOf[Array[AnyRef]] - display1 = display2(0).asInstanceOf[Array[AnyRef]] - display0 = display1(0).asInstanceOf[Array[AnyRef]] - case 1 => - display1 = elems.asInstanceOf[Array[AnyRef]] - display0 = display1(0).asInstanceOf[Array[AnyRef]] - case 0 => - display0 = elems.asInstanceOf[Array[AnyRef]] + + // go to specific position + // requires structure is at pos oldIndex = xor ^ index, + // ensures structure is at pos index + 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 + throw new IllegalArgumentException() + } } + + // USED BY ITERATOR // xor: oldIndex ^ index - final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos + 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 @@ -682,7 +790,7 @@ trait VectorPointer[T] { // USED BY BUILDER // xor: oldIndex ^ index - final def gotoNextBlockStartClean(index: Int, xor: Int): Unit = { // goto block start pos + 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} display0 = new Array(32) @@ -734,28 +842,191 @@ trait VectorPointer[T] { - // STUFF BELOW USED BY APPEND + // STUFF BELOW USED BY APPEND / UPDATE - final def copyOf(a: Array[AnyRef]) = { -// //println("copy") + final def copyOf(a: Array[AnyRef]) = { + //println("copy") val b = new Array[AnyRef](a.length) - arraycopy(a, 0, b, 0, a.length) + Platform.arraycopy(a, 0, b, 0, a.length) b } - final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { -// //println("copy and null") + final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { + //println("copy and null") val x = array(index) -//TODO -// array(index) = null + 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 + + final def stabilize(index: Int) = (depth - 1) match { + case 5 => + display5 = copyOf(display5) + display4 = copyOf(display4) + 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 + 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 + 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 + case 2 => + display2 = copyOf(display2) + display1 = copyOf(display1) + display2((index >> 10) & 31) = display1 + display1((index >> 5) & 31) = display0 + case 1 => + display1 = copyOf(display1) + display1((index >> 5) & 31) = display0 + case 0 => + } + + + + + + + /// USED IN UPDATE AND APPEND BACK + + // prepare for writing at an existing position + + // requires structure is clean and at pos oldIndex = xor ^ newIndex, + // ensures structure is dirty and at pos newIndex and writable at level 0 + 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]] + 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]] + 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]] + case 2 => + display2 = copyOf(display2) + display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + case 1 => + display1 = copyOf(display1) + display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + case 0 => + display0 = copyOf(display0) + } + + + // requires structure is dirty and at pos oldIndex, + // ensures structure is dirty and at pos newIndex and writable at level 0 + final def gotoPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { + if (xor < (1 << 5)) { // level = 0 + display0 = copyOf(display0) + } 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 = 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 = 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 = 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 = 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 + throw new IllegalArgumentException() + } + } + + + // USED IN DROP + + final def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { + val elems = new Array[AnyRef](32) + Platform.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) + // create a new block at the bottom level (and possibly nodes on its path) and prepares for writing - final def gotoFreshPosClean(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos + // requires structure is clean and at pos oldIndex, + // ensures structure is dirty and at pos newIndex and writable at level 0 + 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 @@ -830,164 +1101,20 @@ trait VectorPointer[T] { } else { // level = 6 throw new IllegalArgumentException() } - stabilize(newIndex) } - // xor: oldIndex ^ index - final def XgotoFreshPosClean(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - if (depth == 1) { display1 = new Array(32); depth +=1 } - else { display1 = copyOf(display1) } - display1((oldIndex >> 5) & 31) = display0 - display0 = new Array(32) - } else - if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { display2 = new Array(32); depth+=1} - else { display2 = copyOf(display2) } - display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display0 = new Array(32) - display1 = new Array(32) - } else - if (xor < (1 << 20)) { // level = 3 - if (depth == 3) { display3 = new Array(32); depth+=1} - else { display3 = copyOf(display3) } - display1 = copyOf(display1) - display2 = copyOf(display2) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display0 = new Array(32) - display1 = new Array(32) - display2 = new Array(32) - } else - if (xor < (1 << 25)) { // level = 4 - if (depth == 4) { display4 = new Array(32); depth+=1} - else { display4 = copyOf(display4) } - display1 = copyOf(display1) - display2 = copyOf(display2) - display3 = copyOf(display3) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display0 = new Array(32) - display1 = new Array(32) - display2 = new Array(32) - display3 = new Array(32) - } else - if (xor < (1 << 30)) { // level = 5 - if (depth == 5) { display5 = new Array(32); depth+=1 } - else { display5 = copyOf(display5) } - 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 - display5((oldIndex >> 25) & 31) = display4 - display0 = new Array(32) - display1 = new Array(32) - display2 = new Array(32) - display3 = new Array(32) - display4 = new Array(32) - } 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 + final def gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { + stabilize(oldIndex) + gotoFreshPosWritable0(oldIndex, newIndex, xor) } - /// USED IN UPDATE AND APPEND BACK - - // prepare for writing at an existing position - - // xor: oldIndex ^ index - // precondition: the pointers (and only those) on path oldIndex to display0 are null - // postconditions: - // the pointers (and only those) on path newIndex to display0 are null - // path oldIndex will be updated with previous displayX - // displayX will be fresh, writable copies of path newIndex - final def gotoPosClean(oldIndex: Int, newIndex: Int, xor: Int): Unit = { - if (depth > 1) { - gotoPos(newIndex, xor) - stabilize(newIndex) - } - } - - // old path is maybe dirty (then we need to reconcile) <-- as a start, we could assume it always is (?) - // new path is being made dirty (we do need to change) - - final def XgotoPosClean(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto pos index - if (xor < (1 << 5)) { // level = 0 -// //println("inside same chunk") - display0 = copyOf(display0) - } else - if (xor < (1 << 10)) { // level = 1 -// //println("transfer to chunk at level 1 ("+oldIndex+"->"+newIndex+")") - display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 15)) { // level = 2 -// //println("transfer to chunk at level 1") - 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 = 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 = 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 = 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 - throw new IllegalArgumentException() - } - } + // DEBUG STUFF def debug(): Unit = { return @@ -1008,69 +1135,5 @@ trait VectorPointer[T] { } - // make sure there is no aliasing - - // TODO: optimize - final def stabilize(index: Int) = { -// debug() - display0 = copyOf(display0) - if (depth > 1) { - display1 = copyOf(display1) - display1((index >> 5) & 31) = display0 - } - if (depth > 2) { - display2 = copyOf(display2) - display2((index >> 10) & 31) = display1 - } - if (depth > 3) { - display3 = copyOf(display3) - display3((index >> 15) & 31) = display2 - } - if (depth > 4) { - display4 = copyOf(display4) - display4((index >> 20) & 31) = display3 - } - if (depth > 5) { - display5 = copyOf(display5) - display5((index >> 25) & 31) = display4 - } - } - - - - - // go to specified position - - // xor: oldIndex ^ index - final def gotoPos(index: Int, xor: Int): Unit = { // goto pos index - 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() - } - } - } |