/*

* Scala (https://www.scala-lang.org)

*

* Copyright EPFL and Lightbend, Inc. dba Akka

*

* Licensed under Apache License 2.0

* (http://www.apache.org/licenses/LICENSE-2.0).

*

* See the NOTICE file distributed with this work for

* additional information regarding copyright ownership.

*/

package scala.collection

package immutable

import java.lang.Math.{abs, max => mmax, min => mmin}

import java.util.Arrays.{copyOf, copyOfRange}

import java.util.{Arrays, Spliterator}

import scala.annotation.switch

import scala.annotation.unchecked.uncheckedVariance

import scala.collection.Stepper.EfficientSplit

import scala.collection.generic.{CommonErrors, DefaultSerializable}

import scala.collection.immutable.VectorInline._

import scala.collection.immutable.VectorStatics._

import scala.collection.mutable.ReusableBuilder

/** $factoryInfo

* @define Coll `Vector`

* @define coll vector

*/

@SerialVersionUID(3L)

object Vector extends StrictOptimizedSeqFactory[Vector] {

def empty[A]: Vector[A] = Vector0

def from[E](it: collection.IterableOnce[E]): Vector[E] =

it match {

case v: Vector[E] => v

case _ =>

val knownSize = it.knownSize

if (knownSize == 0) empty[E]

else if (knownSize > 0 && knownSize <= WIDTH) {

val a1: Arr1 = it match {

case as: ArraySeq.ofRef[_] if as.elemTag.runtimeClass == classOf[AnyRef] =>

as.unsafeArray.asInstanceOf[Arr1]

case it: Iterable[E] =>

val a1 = new Arr1(knownSize)

@annotation.unused val copied = it.copyToArray(a1.asInstanceOf[Array[Any]])

//assert(copied == knownSize)

a1

case _ =>

val a1 = new Arr1(knownSize)

@annotation.unused val copied = it.iterator.copyToArray(a1.asInstanceOf[Array[Any]])

//assert(copied == knownSize)

a1.asInstanceOf[Arr1]

}

new Vector1[E](a1)

} else {

(newBuilder ++= it).result()

}

}

def newBuilder[A]: ReusableBuilder[A, Vector[A]] = new VectorBuilder[A]

/** Create a Vector with the same element at each index.

*

* Unlike `fill`, which takes a by-name argument for the value and can thereby

* compute different values for each index, this method guarantees that all

* elements are identical. This allows sparse allocation in O(log n) time and space.

*/

private[collection] def fillSparse[A](n: Int)(elem: A): Vector[A] = {

//TODO Make public; this method is private for now because it is not forward binary compatible

if(n <= 0) Vector0

else {

val b = new VectorBuilder[A]

b.initSparse(n, elem)

b.result()

}

}

private val defaultApplyPreferredMaxLength: Int =

// explicit StringOps to avoid initialization cycle with Predef (scala/bug#13009)

try new StringOps(System.getProperty("scala.collection.immutable.Vector.defaultApplyPreferredMaxLength",

"250")).toInt

catch {

case _: SecurityException => 250

}

private val emptyIterator = new NewVectorIterator(Vector0, 0, 0)

}

/** Vector is a general-purpose, immutable data structure. It provides random access and updates

* in O(log n) time, as well as very fast append/prepend/tail/init (amortized O(1), worst case O(log n)).

* Because vectors strike a good balance between fast random selections and fast random functional updates,

* they are currently the default implementation of immutable indexed sequences.

*

* Vectors are implemented by radix-balanced finger trees of width 32. There is a separate subclass

* for each level (0 to 6, with 0 being the empty vector and 6 a tree with a maximum width of 64 at the

* top level).

*

* Tree balancing:

* - Only the first dimension of an array may have a size < WIDTH

* - In a `data` (central) array the first dimension may be up to WIDTH-2 long, in `prefix1` and `suffix1` up

* to WIDTH, and in other `prefix` and `suffix` arrays up to WIDTH-1

* - `prefix1` and `suffix1` are never empty

* - Balancing does not cross the main data array (i.e. prepending never touches the suffix and appending never touches

* the prefix). The level is increased/decreased when the affected side plus main data is already full/empty

* - All arrays are left-aligned and truncated

*

* In addition to the data slices (`prefix1`, `prefix2`, ..., `dataN`, ..., `suffix2`, `suffix1`) we store a running

* count of elements after each prefix for more efficient indexing without having to dereference all prefix arrays.

*/

sealed abstract class Vector[+A] private[immutable] (private[immutable] final val prefix1: Arr1)

extends AbstractSeq[A]

with IndexedSeq[A]

with IndexedSeqOps[A, Vector, Vector[A]]

with StrictOptimizedSeqOps[A, Vector, Vector[A]]

with IterableFactoryDefaults[A, Vector]

with DefaultSerializable {

override def iterableFactory: SeqFactory[Vector] = Vector

override final def length: Int =

if(this.isInstanceOf[BigVector[_]]) this.asInstanceOf[BigVector[_]].length0

else prefix1.length

override final def iterator: Iterator[A] =

if(this.isInstanceOf[Vector0.type]) Vector.emptyIterator

else new NewVectorIterator(this, length, vectorSliceCount)

override final protected[collection] def filterImpl(pred: A => Boolean, isFlipped: Boolean): Vector[A] = {

var i = 0

val len = prefix1.length

while (i != len) {

if (pred(prefix1(i).asInstanceOf[A]) == isFlipped) {

// each 1 bit indicates that index passes the filter.

// all indices < i are also assumed to pass the filter

var bitmap = 0

var j = i + 1

while (j < len) {

if (pred(prefix1(j).asInstanceOf[A]) != isFlipped) {

bitmap |= (1 << j)

}

j += 1

}

val newLen = i + java.lang.Integer.bitCount(bitmap)

if(this.isInstanceOf[BigVector[_]]) {

val b = new VectorBuilder[A]

var k = 0

while(k < i) {

b.addOne(prefix1(k).asInstanceOf[A])

k += 1

}

k = i + 1

while (i != newLen) {

if (((1 << k) & bitmap) != 0) {

b.addOne(prefix1(k).asInstanceOf[A])

i += 1

}

k += 1

}

this.asInstanceOf[BigVector[A]].foreachRest { v => if(pred(v) != isFlipped) b.addOne(v) }

return b.result()

} else {

if (newLen == 0) return Vector0

val newData = new Array[AnyRef](newLen)

System.arraycopy(prefix1, 0, newData, 0, i)

var k = i + 1

while (i != newLen) {

if (((1 << k) & bitmap) != 0) {

newData(i) = prefix1(k)

i += 1

}

k += 1

}

return new Vector1[A](newData)

}

}

i += 1

}

if(this.isInstanceOf[BigVector[_]]) {

val b = new VectorBuilder[A]

b.initFrom(prefix1)

this.asInstanceOf[BigVector[A]].foreachRest { v => if(pred(v) != isFlipped) b.addOne(v) }

b.result()

} else this

}

// Dummy overrides to refine result types for binary compatibility:

override def updated[B >: A](index: Int, elem: B): Vector[B] = super.updated(index, elem)

override def appended[B >: A](elem: B): Vector[B] = super.appended(elem)

override def prepended[B >: A](elem: B): Vector[B] = super.prepended(elem)

override def prependedAll[B >: A](prefix: collection.IterableOnce[B]): Vector[B] = {

val k = prefix.knownSize

if (k == 0) this

else if (k < 0) super.prependedAll(prefix)

else prependedAll0(prefix, k)

}

override final def appendedAll[B >: A](suffix: collection.IterableOnce[B]): Vector[B] = {

val k = suffix.knownSize

if (k == 0) this

else if (k < 0) super.appendedAll(suffix)

else appendedAll0(suffix, k)

}

protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] = {

// k >= 0, k = prefix.knownSize

val tinyAppendLimit = 4 + vectorSliceCount

if (k < tinyAppendLimit /*|| k < (this.size >>> Log2ConcatFaster)*/) {

var v: Vector[B] = this

val it = IndexedSeq.from(prefix).reverseIterator

while (it.hasNext) v = it.next() +: v

v

} else if (this.size < (k >>> Log2ConcatFaster) && prefix.isInstanceOf[Vector[_]]) {

var v = prefix.asInstanceOf[Vector[B]]

val it = this.iterator

while (it.hasNext) v = v :+ it.next()

v

} else if (k < this.size - AlignToFaster) {

new VectorBuilder[B].alignTo(k, this).addAll(prefix).addAll(this).result()

} else super.prependedAll(prefix)

}

protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

// k >= 0, k = suffix.knownSize

val tinyAppendLimit = 4 + vectorSliceCount

if (k < tinyAppendLimit) {

var v: Vector[B] = this

suffix match {

case it: Iterable[_] => it.asInstanceOf[Iterable[B]].foreach(x => v = v.appended(x))

case _ => suffix.iterator.foreach(x => v = v.appended(x))

}

v

} else if (this.size < (k >>> Log2ConcatFaster) && suffix.isInstanceOf[Vector[_]]) {

var v = suffix.asInstanceOf[Vector[B]]

val ri = this.reverseIterator

while (ri.hasNext) v = v.prepended(ri.next())

v

} else if (this.size < k - AlignToFaster && suffix.isInstanceOf[Vector[_]]) {

val v = suffix.asInstanceOf[Vector[B]]

new VectorBuilder[B].alignTo(this.size, v).addAll(this).addAll(v).result()

} else new VectorBuilder[B].initFrom(this).addAll(suffix).result()

}

override def className = "Vector"

@inline override final def take(n: Int): Vector[A] = slice(0, n)

@inline override final def drop(n: Int): Vector[A] = slice(n, length)

@inline override final def takeRight(n: Int): Vector[A] = slice(length - mmax(n, 0), length)

@inline override final def dropRight(n: Int): Vector[A] = slice(0, length - mmax(n, 0))

override def tail: Vector[A] = slice(1, length)

override def init: Vector[A] = slice(0, length-1)

/** Like slice but parameters must be 0 <= lo < hi < length */

protected[this] def slice0(lo: Int, hi: Int): Vector[A]

/** Number of slices */

protected[immutable] def vectorSliceCount: Int

/** Slice at index */

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef]

/** Length of all slices up to and including index */

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int

override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Int = iterator.copyToArray(xs, start, len)

override def toVector: Vector[A] = this

override protected def applyPreferredMaxLength: Int = Vector.defaultApplyPreferredMaxLength

override def stepper[S <: Stepper[_]](implicit shape: StepperShape[A, S]): S with EfficientSplit = {

val s = shape.shape match {

case StepperShape.IntShape => new IntVectorStepper(iterator.asInstanceOf[NewVectorIterator[Int]])

case StepperShape.LongShape => new LongVectorStepper(iterator.asInstanceOf[NewVectorIterator[Long]])

case StepperShape.DoubleShape => new DoubleVectorStepper(iterator.asInstanceOf[NewVectorIterator[Double]])

case _ => shape.parUnbox(new AnyVectorStepper[A](iterator.asInstanceOf[NewVectorIterator[A]]))

}

s.asInstanceOf[S with EfficientSplit]

}

protected[this] def ioob(index: Int): IndexOutOfBoundsException =

CommonErrors.indexOutOfBounds(index = index, max = length - 1)

override final def head: A =

if (prefix1.length == 0) throw new NoSuchElementException("empty.head")

else prefix1(0).asInstanceOf[A]

override final def last: A = {

if(this.isInstanceOf[BigVector[_]]) {

val suffix = this.asInstanceOf[BigVector[_]].suffix1

if(suffix.length == 0) throw new NoSuchElementException("empty.tail")

else suffix(suffix.length-1)

} else prefix1(prefix1.length-1)

}.asInstanceOf[A]

override final def foreach[U](f: A => U): Unit = {

val c = vectorSliceCount

var i = 0

while (i < c) {

foreachRec(vectorSliceDim(c, i) - 1, vectorSlice(i), f)

i += 1

}

}

// The following definitions are needed for binary compatibility with ParVector

private[collection] def startIndex: Int = 0

private[collection] def endIndex: Int = length

private[collection] def initIterator[B >: A](s: VectorIterator[B]): Unit =

s.it = iterator.asInstanceOf[NewVectorIterator[B]]

}

/** This class only exists because we cannot override `slice` in `Vector` in a binary-compatible way */

private sealed abstract class VectorImpl[+A](_prefix1: Arr1) extends Vector[A](_prefix1) {

override final def slice(from: Int, until: Int): Vector[A] = {

val lo = mmax(from, 0)

val hi = mmin(until, length)

if (hi <= lo) Vector0

else if (hi - lo == length) this

else slice0(lo, hi)

}

}

/** Vector with suffix and length fields; all Vector subclasses except Vector1 extend this */

private sealed abstract class BigVector[+A](_prefix1: Arr1, private[immutable] val suffix1: Arr1, private[immutable] val length0: Int) extends VectorImpl[A](_prefix1) {

protected[immutable] final def foreachRest[U](f: A => U): Unit = {

val c = vectorSliceCount

var i = 1

while(i < c) {

foreachRec(vectorSliceDim(c, i)-1, vectorSlice(i), f)

i += 1

}

}

}

/** Empty vector */

private object Vector0 extends BigVector[Nothing](empty1, empty1, 0) {

def apply(index: Int): Nothing = throw ioob(index)

override def updated[B >: Nothing](index: Int, elem: B): Vector[B] = throw ioob(index)

override def appended[B >: Nothing](elem: B): Vector[B] = new Vector1(wrap1(elem))

override def prepended[B >: Nothing](elem: B): Vector[B] = new Vector1(wrap1(elem))

override def map[B](f: Nothing => B): Vector[B] = this

override def tail: Vector[Nothing] = throw new UnsupportedOperationException("empty.tail")

override def init: Vector[Nothing] = throw new UnsupportedOperationException("empty.init")

protected[this] def slice0(lo: Int, hi: Int): Vector[Nothing] = this

protected[immutable] def vectorSliceCount: Int = 0

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = null

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = 0

override def equals(o: Any): Boolean = {

if(this eq o.asInstanceOf[AnyRef]) true

else o match {

case that: Vector[_] => false

case o => super.equals(o)

}

}

override protected[this]def prependedAll0[B >: Nothing](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

Vector.from(prefix)

override protected[this]def appendedAll0[B >: Nothing](suffix: collection.IterableOnce[B], k: Int): Vector[B] =

Vector.from(suffix)

override protected[this] def ioob(index: Int): IndexOutOfBoundsException =

new IndexOutOfBoundsException(s"$index is out of bounds (empty vector)")

}

/** Flat ArraySeq-like structure */

private final class Vector1[+A](_data1: Arr1) extends VectorImpl[A](_data1) {

@inline def apply(index: Int): A = {

if(index >= 0 && index < prefix1.length)

prefix1(index).asInstanceOf[A]

else throw ioob(index)

}

override def updated[B >: A](index: Int, elem: B): Vector[B] = {

if(index >= 0 && index < prefix1.length)

new Vector1(copyUpdate(prefix1, index, elem))

else throw ioob(index)

}

override def appended[B >: A](elem: B): Vector[B] = {

val len1 = prefix1.length

if(len1 < WIDTH) new Vector1(copyAppend1(prefix1, elem))

else new Vector2(prefix1, WIDTH, empty2, wrap1(elem), WIDTH+1)

}

override def prepended[B >: A](elem: B): Vector[B] = {

val len1 = prefix1.length

if(len1 < WIDTH) new Vector1(copyPrepend1(elem, prefix1))

else new Vector2(wrap1(elem), 1, empty2, prefix1, len1+1)

}

override def map[B](f: A => B): Vector[B] = new Vector1(mapElems1(prefix1, f))

protected[this] def slice0(lo: Int, hi: Int): Vector[A] =

new Vector1(copyOfRange(prefix1, lo, hi))

override def tail: Vector[A] =

if(prefix1.length == 1) Vector0

else new Vector1(copyTail(prefix1))

override def init: Vector[A] =

if(prefix1.length == 1) Vector0

else new Vector1(copyInit(prefix1))

protected[immutable] def vectorSliceCount: Int = 1

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = prefix1

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = prefix1.length

override protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

prepend1IfSpace(prefix1, prefix) match {

case null => super.prependedAll0(prefix, k)

case data1b => new Vector1(data1b)

}

override protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

val data1b = append1IfSpace(prefix1, suffix)

if(data1b ne null) new Vector1(data1b)

else super.appendedAll0(suffix, k)

}

}

/** 2-dimensional radix-balanced finger tree */

private final class Vector2[+A](_prefix1: Arr1, private[immutable] val len1: Int,

private[immutable] val data2: Arr2,

_suffix1: Arr1,

_length0: Int) extends BigVector[A](_prefix1, _suffix1, _length0) {

@inline private[this] def copy(prefix1: Arr1 = prefix1, len1: Int = len1,

data2: Arr2 = data2,

suffix1: Arr1 = suffix1,

length0: Int = length0) =

new Vector2(prefix1, len1, data2, suffix1, length0)

@inline def apply(index: Int): A = {

if(index >= 0 && index < length0) {

val io = index - len1

if(io >= 0) {

val i2 = io >>> BITS

val i1 = io & MASK

if(i2 < data2.length) data2(i2)(i1)

else suffix1(io & MASK)

} else prefix1(index)

}.asInstanceOf[A] else throw ioob(index)

}

override def updated[B >: A](index: Int, elem: B): Vector[B] = {

if(index >= 0 && index < length0) {

if(index >= len1) {

val io = index - len1

val i2 = io >>> BITS

val i1 = io & MASK

if(i2 < data2.length) copy(data2 = copyUpdate(data2, i2, i1, elem))

else copy(suffix1 = copyUpdate(suffix1, i1, elem))

} else {

copy(prefix1 = copyUpdate(prefix1, index, elem))

}

} else throw ioob(index)

}

override def appended[B >: A](elem: B): Vector[B] = {

if (suffix1.length < WIDTH ) copy(suffix1 = copyAppend1(suffix1, elem), length0 = length0+1)

else if(data2.length < WIDTH-2) copy(data2 = copyAppend(data2, suffix1), suffix1 = wrap1(elem), length0 = length0+1)

else new Vector3(prefix1, len1, data2, WIDTH*(WIDTH-2) + len1, empty3, wrap2(suffix1), wrap1(elem), length0+1)

}

override def prepended[B >: A](elem: B): Vector[B] = {

if (len1 < WIDTH ) copy(copyPrepend1(elem, prefix1), len1+1, length0 = length0+1)

else if(data2.length < WIDTH-2) copy(wrap1(elem), 1, copyPrepend(prefix1, data2), length0 = length0+1)

else new Vector3(wrap1(elem), 1, wrap2(prefix1), len1+1, empty3, data2, suffix1, length0+1)

}

override def map[B](f: A => B): Vector[B] =

copy(prefix1 = mapElems1(prefix1, f), data2 = mapElems(2, data2, f), suffix1 = mapElems1(suffix1, f))

protected[this] def slice0(lo: Int, hi: Int): Vector[A] = {

val b = new VectorSliceBuilder(lo, hi)

b.consider(1, prefix1)

b.consider(2, data2)

b.consider(1, suffix1)

b.result()

}

override def tail: Vector[A] =

if(len1 > 1) copy(copyTail(prefix1), len1-1, length0 = length0-1)

else slice0(1, length0)

override def init: Vector[A] =

if(suffix1.length > 1) copy(suffix1 = copyInit(suffix1), length0 = length0-1)

else slice0(0, length0-1)

protected[immutable] def vectorSliceCount: Int = 3

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = (idx: @switch) match {

case 0 => prefix1

case 1 => data2

case 2 => suffix1

}

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = (idx: @switch) match {

case 0 => len1

case 1 => length0 - suffix1.length

case 2 => length0

}

override protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

prepend1IfSpace(prefix1, prefix) match {

case null => super.prependedAll0(prefix, k)

case prefix1b =>

val diff = prefix1b.length - prefix1.length

copy(prefix1 = prefix1b,

len1 = len1 + diff,

length0 = length0 + diff,

)

}

override protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

val suffix1b = append1IfSpace(suffix1, suffix)

if(suffix1b ne null) copy(suffix1 = suffix1b, length0 = length0-suffix1.length+suffix1b.length)

else super.appendedAll0(suffix, k)

}

}

/** 3-dimensional radix-balanced finger tree */

private final class Vector3[+A](_prefix1: Arr1, private[immutable] val len1: Int,

private[immutable] val prefix2: Arr2, private[immutable] val len12: Int,

private[immutable] val data3: Arr3,

private[immutable] val suffix2: Arr2, _suffix1: Arr1,

_length0: Int) extends BigVector[A](_prefix1, _suffix1, _length0) {

@inline private[this] def copy(prefix1: Arr1 = prefix1, len1: Int = len1,

prefix2: Arr2 = prefix2, len12: Int = len12,

data3: Arr3 = data3,

suffix2: Arr2 = suffix2, suffix1: Arr1 = suffix1,

length0: Int = length0) =

new Vector3(prefix1, len1, prefix2, len12, data3, suffix2, suffix1, length0)

@inline def apply(index: Int): A = {

if(index >= 0 && index < length0) {

val io = index - len12

if(io >= 0) {

val i3 = io >>> BITS2

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if(i3 < data3.length) data3(i3)(i2)(i1)

else if(i2 < suffix2.length) suffix2(i2)(i1)

else suffix1(i1)

} else if(index >= len1) {

val io = index - len1

prefix2(io >>> BITS)(io & MASK)

} else prefix1(index)

}.asInstanceOf[A] else throw ioob(index)

}

override def updated[B >: A](index: Int, elem: B): Vector[B] = {

if(index >= 0 && index < length0) {

if(index >= len12) {

val io = index - len12

val i3 = io >>> BITS2

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if (i3 < data3.length ) copy(data3 = copyUpdate(data3, i3, i2, i1, elem))

else if(i2 < suffix2.length) copy(suffix2 = copyUpdate(suffix2, i2, i1, elem))

else copy(suffix1 = copyUpdate(suffix1, i1, elem))

} else if(index >= len1) {

val io = index - len1

copy(prefix2 = copyUpdate(prefix2, io >>> BITS, io & MASK, elem))

} else {

copy(prefix1 = copyUpdate(prefix1, index, elem))

}

} else throw ioob(index)

}

override def appended[B >: A](elem: B): Vector[B] = {

if (suffix1.length < WIDTH ) copy(suffix1 = copyAppend1(suffix1, elem), length0 = length0+1)

else if(suffix2.length < WIDTH-1) copy(suffix2 = copyAppend(suffix2, suffix1), suffix1 = wrap1(elem), length0 = length0+1)

else if(data3.length < WIDTH-2) copy(data3 = copyAppend(data3, copyAppend(suffix2, suffix1)), suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else new Vector4(prefix1, len1, prefix2, len12, data3, (WIDTH-2)*WIDTH2 + len12, empty4, wrap3(copyAppend(suffix2, suffix1)), empty2, wrap1(elem), length0+1)

}

override def prepended[B >: A](elem: B): Vector[B] = {

if (len1 < WIDTH ) copy(prefix1 = copyPrepend1(elem, prefix1), len1 = len1+1, len12 = len12+1, length0 = length0+1)

else if(len12 < WIDTH2 ) copy(prefix1 = wrap1(elem), len1 = 1, prefix2 = copyPrepend(prefix1, prefix2), len12 = len12+1, length0 = length0+1)

else if(data3.length < WIDTH-2) copy(prefix1 = wrap1(elem), len1 = 1, prefix2 = empty2, len12 = 1, data3 = copyPrepend(copyPrepend(prefix1, prefix2), data3), length0 = length0+1)

else new Vector4(wrap1(elem), 1, empty2, 1, wrap3(copyPrepend(prefix1, prefix2)), len12+1, empty4, data3, suffix2, suffix1, length0+1)

}

override def map[B](f: A => B): Vector[B] =

copy(prefix1 = mapElems1(prefix1, f), prefix2 = mapElems(2, prefix2, f),

data3 = mapElems(3, data3, f),

suffix2 = mapElems(2, suffix2, f), suffix1 = mapElems1(suffix1, f))

protected[this] def slice0(lo: Int, hi: Int): Vector[A] = {

val b = new VectorSliceBuilder(lo, hi)

b.consider(1, prefix1)

b.consider(2, prefix2)

b.consider(3, data3)

b.consider(2, suffix2)

b.consider(1, suffix1)

b.result()

}

override def tail: Vector[A] =

if(len1 > 1) copy(prefix1 = copyTail(prefix1), len1 = len1-1, len12 = len12-1, length0 = length0-1)

else slice0(1, length0)

override def init: Vector[A] =

if(suffix1.length > 1) copy(suffix1 = copyInit(suffix1), length0 = length0-1)

else slice0(0, length0-1)

protected[immutable] def vectorSliceCount: Int = 5

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = (idx: @switch) match {

case 0 => prefix1

case 1 => prefix2

case 2 => data3

case 3 => suffix2

case 4 => suffix1

}

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = (idx: @switch) match {

case 0 => len1

case 1 => len12

case 2 => len12 + data3.length*WIDTH2

case 3 => length0 - suffix1.length

case 4 => length0

}

override protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

prepend1IfSpace(prefix1, prefix) match {

case null => super.prependedAll0(prefix, k)

case prefix1b =>

val diff = prefix1b.length - prefix1.length

copy(prefix1 = prefix1b,

len1 = len1 + diff,

len12 = len12 + diff,

length0 = length0 + diff,

)

}

override protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

val suffix1b = append1IfSpace(suffix1, suffix)

if(suffix1b ne null) copy(suffix1 = suffix1b, length0 = length0-suffix1.length+suffix1b.length)

else super.appendedAll0(suffix, k)

}

}

/** 4-dimensional radix-balanced finger tree */

private final class Vector4[+A](_prefix1: Arr1, private[immutable] val len1: Int,

private[immutable] val prefix2: Arr2, private[immutable] val len12: Int,

private[immutable] val prefix3: Arr3, private[immutable] val len123: Int,

private[immutable] val data4: Arr4,

private[immutable] val suffix3: Arr3, private[immutable] val suffix2: Arr2, _suffix1: Arr1,

_length0: Int) extends BigVector[A](_prefix1, _suffix1, _length0) {

@inline private[this] def copy(prefix1: Arr1 = prefix1, len1: Int = len1,

prefix2: Arr2 = prefix2, len12: Int = len12,

prefix3: Arr3 = prefix3, len123: Int = len123,

data4: Arr4 = data4,

suffix3: Arr3 = suffix3, suffix2: Arr2 = suffix2, suffix1: Arr1 = suffix1,

length0: Int = length0) =

new Vector4(prefix1, len1, prefix2, len12, prefix3, len123, data4, suffix3, suffix2, suffix1, length0)

@inline def apply(index: Int): A = {

if(index >= 0 && index < length0) {

val io = index - len123

if(io >= 0) {

val i4 = io >>> BITS3

val i3 = (io >>> BITS2) & MASK

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if(i4 < data4.length) data4(i4)(i3)(i2)(i1)

else if(i3 < suffix3.length) suffix3(i3)(i2)(i1)

else if(i2 < suffix2.length) suffix2(i2)(i1)

else suffix1(i1)

} else if(index >= len12) {

val io = index - len12

prefix3(io >>> BITS2)((io >>> BITS) & MASK)(io & MASK)

} else if(index >= len1) {

val io = index - len1

prefix2(io >>> BITS)(io & MASK)

} else prefix1(index)

}.asInstanceOf[A] else throw ioob(index)

}

override def updated[B >: A](index: Int, elem: B): Vector[B] = {

if(index >= 0 && index < length0) {

if(index >= len123) {

val io = index - len123

val i4 = io >>> BITS3

val i3 = (io >>> BITS2) & MASK

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if (i4 < data4.length ) copy(data4 = copyUpdate(data4, i4, i3, i2, i1, elem))

else if(i3 < suffix3.length) copy(suffix3 = copyUpdate(suffix3, i3, i2, i1, elem))

else if(i2 < suffix2.length) copy(suffix2 = copyUpdate(suffix2, i2, i1, elem))

else copy(suffix1 = copyUpdate(suffix1, i1, elem))

} else if(index >= len12) {

val io = index - len12

copy(prefix3 = copyUpdate(prefix3, io >>> BITS2, (io >>> BITS) & MASK, io & MASK, elem))

} else if(index >= len1) {

val io = index - len1

copy(prefix2 = copyUpdate(prefix2, io >>> BITS, io & MASK, elem))

} else {

copy(prefix1 = copyUpdate(prefix1, index, elem))

}

} else throw ioob(index)

}

override def appended[B >: A](elem: B): Vector[B] = {

if (suffix1.length < WIDTH ) copy(suffix1 = copyAppend1(suffix1, elem), length0 = length0+1)

else if(suffix2.length < WIDTH-1) copy(suffix2 = copyAppend(suffix2, suffix1), suffix1 = wrap1(elem), length0 = length0+1)

else if(suffix3.length < WIDTH-1) copy(suffix3 = copyAppend(suffix3, copyAppend(suffix2, suffix1)), suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else if(data4.length < WIDTH-2) copy(data4 = copyAppend(data4, copyAppend(suffix3, copyAppend(suffix2, suffix1))), suffix3 = empty3, suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else new Vector5(prefix1, len1, prefix2, len12, prefix3, len123, data4, (WIDTH-2)*WIDTH3 + len123, empty5, wrap4(copyAppend(suffix3, copyAppend(suffix2, suffix1))), empty3, empty2, wrap1(elem), length0+1)

}

override def prepended[B >: A](elem: B): Vector[B] = {

if (len1 < WIDTH ) copy(copyPrepend1(elem, prefix1), len1+1, len12 = len12+1, len123 = len123+1, length0 = length0+1)

else if(len12 < WIDTH2 ) copy(wrap1(elem), 1, copyPrepend(prefix1, prefix2), len12+1, len123 = len123+1, length0 = length0+1)

else if(len123 < WIDTH3 ) copy(wrap1(elem), 1, empty2, 1, copyPrepend(copyPrepend(prefix1, prefix2), prefix3), len123+1, length0 = length0+1)

else if(data4.length < WIDTH-2) copy(wrap1(elem), 1, empty2, 1, empty3, 1, copyPrepend(copyPrepend(copyPrepend(prefix1, prefix2), prefix3), data4), length0 = length0+1)

else new Vector5(wrap1(elem), 1, empty2, 1, empty3, 1, wrap4(copyPrepend(copyPrepend(prefix1, prefix2), prefix3)), len123+1, empty5, data4, suffix3, suffix2, suffix1, length0+1)

}

override def map[B](f: A => B): Vector[B] =

copy(prefix1 = mapElems1(prefix1, f), prefix2 = mapElems(2, prefix2, f), prefix3 = mapElems(3, prefix3, f),

data4 = mapElems(4, data4, f),

suffix3 = mapElems(3, suffix3, f), suffix2 = mapElems(2, suffix2, f), suffix1 = mapElems1(suffix1, f))

protected[this] def slice0(lo: Int, hi: Int): Vector[A] = {

val b = new VectorSliceBuilder(lo, hi)

b.consider(1, prefix1)

b.consider(2, prefix2)

b.consider(3, prefix3)

b.consider(4, data4)

b.consider(3, suffix3)

b.consider(2, suffix2)

b.consider(1, suffix1)

b.result()

}

override def tail: Vector[A] =

if(len1 > 1) copy(copyTail(prefix1), len1-1, len12 = len12-1, len123 = len123-1, length0 = length0-1)

else slice0(1, length0)

override def init: Vector[A] =

if(suffix1.length > 1) copy(suffix1 = copyInit(suffix1), length0 = length0-1)

else slice0(0, length0-1)

protected[immutable] def vectorSliceCount: Int = 7

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = (idx: @switch) match {

case 0 => prefix1

case 1 => prefix2

case 2 => prefix3

case 3 => data4

case 4 => suffix3

case 5 => suffix2

case 6 => suffix1

}

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = (idx: @switch) match {

case 0 => len1

case 1 => len12

case 2 => len123

case 3 => len123 + data4.length*WIDTH3

case 4 => len123 + data4.length*WIDTH3 + suffix3.length*WIDTH2

case 5 => length0 - suffix1.length

case 6 => length0

}

override protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

prepend1IfSpace(prefix1, prefix) match {

case null => super.prependedAll0(prefix, k)

case prefix1b =>

val diff = prefix1b.length - prefix1.length

copy(prefix1 = prefix1b,

len1 = len1 + diff,

len12 = len12 + diff,

len123 = len123 + diff,

length0 = length0 + diff,

)

}

override protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

val suffix1b = append1IfSpace(suffix1, suffix)

if(suffix1b ne null) copy(suffix1 = suffix1b, length0 = length0-suffix1.length+suffix1b.length)

else super.appendedAll0(suffix, k)

}

}

/** 5-dimensional radix-balanced finger tree */

private final class Vector5[+A](_prefix1: Arr1, private[immutable] val len1: Int,

private[immutable] val prefix2: Arr2, private[immutable] val len12: Int,

private[immutable] val prefix3: Arr3, private[immutable] val len123: Int,

private[immutable] val prefix4: Arr4, private[immutable] val len1234: Int,

private[immutable] val data5: Arr5,

private[immutable] val suffix4: Arr4, private[immutable] val suffix3: Arr3, private[immutable] val suffix2: Arr2, _suffix1: Arr1,

_length0: Int) extends BigVector[A](_prefix1, _suffix1, _length0) {

@inline private[this] def copy(prefix1: Arr1 = prefix1, len1: Int = len1,

prefix2: Arr2 = prefix2, len12: Int = len12,

prefix3: Arr3 = prefix3, len123: Int = len123,

prefix4: Arr4 = prefix4, len1234: Int = len1234,

data5: Arr5 = data5,

suffix4: Arr4 = suffix4, suffix3: Arr3 = suffix3, suffix2: Arr2 = suffix2, suffix1: Arr1 = suffix1,

length0: Int = length0) =

new Vector5(prefix1, len1, prefix2, len12, prefix3, len123, prefix4, len1234, data5, suffix4, suffix3, suffix2, suffix1, length0)

@inline def apply(index: Int): A = {

if(index >= 0 && index < length0) {

val io = index - len1234

if(io >= 0) {

val i5 = io >>> BITS4

val i4 = (io >>> BITS3) & MASK

val i3 = (io >>> BITS2) & MASK

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if(i5 < data5.length) data5(i5)(i4)(i3)(i2)(i1)

else if(i4 < suffix4.length) suffix4(i4)(i3)(i2)(i1)

else if(i3 < suffix3.length) suffix3(i3)(i2)(i1)

else if(i2 < suffix2.length) suffix2(i2)(i1)

else suffix1(i1)

} else if(index >= len123) {

val io = index - len123

prefix4(io >>> BITS3)((io >>> BITS2) & MASK)((io >>> BITS) & MASK)(io & MASK)

} else if(index >= len12) {

val io = index - len12

prefix3(io >>> BITS2)((io >>> BITS) & MASK)(io & MASK)

} else if(index >= len1) {

val io = index - len1

prefix2(io >>> BITS)(io & MASK)

} else prefix1(index)

}.asInstanceOf[A] else throw ioob(index)

}

override def updated[B >: A](index: Int, elem: B): Vector[B] = {

if(index >= 0 && index < length0) {

if(index >= len1234) {

val io = index - len1234

val i5 = io >>> BITS4

val i4 = (io >>> BITS3) & MASK

val i3 = (io >>> BITS2) & MASK

val i2 = (io >>> BITS) & MASK

val i1 = io & MASK

if (i5 < data5.length ) copy(data5 = copyUpdate(data5, i5, i4, i3, i2, i1, elem))

else if(i4 < suffix4.length) copy(suffix4 = copyUpdate(suffix4, i4, i3, i2, i1, elem))

else if(i3 < suffix3.length) copy(suffix3 = copyUpdate(suffix3, i3, i2, i1, elem))

else if(i2 < suffix2.length) copy(suffix2 = copyUpdate(suffix2, i2, i1, elem))

else copy(suffix1 = copyUpdate(suffix1, i1, elem))

} else if(index >= len123) {

val io = index - len123

copy(prefix4 = copyUpdate(prefix4, io >>> BITS3, (io >>> BITS2) & MASK, (io >>> BITS) & MASK, io & MASK, elem))

} else if(index >= len12) {

val io = index - len12

copy(prefix3 = copyUpdate(prefix3, io >>> BITS2, (io >>> BITS) & MASK, io & MASK, elem))

} else if(index >= len1) {

val io = index - len1

copy(prefix2 = copyUpdate(prefix2, io >>> BITS, io & MASK, elem))

} else {

copy(prefix1 = copyUpdate(prefix1, index, elem))

}

} else throw ioob(index)

}

override def appended[B >: A](elem: B): Vector[B] = {

if (suffix1.length < WIDTH ) copy(suffix1 = copyAppend1(suffix1, elem), length0 = length0+1)

else if(suffix2.length < WIDTH-1) copy(suffix2 = copyAppend(suffix2, suffix1), suffix1 = wrap1(elem), length0 = length0+1)

else if(suffix3.length < WIDTH-1) copy(suffix3 = copyAppend(suffix3, copyAppend(suffix2, suffix1)), suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else if(suffix4.length < WIDTH-1) copy(suffix4 = copyAppend(suffix4, copyAppend(suffix3, copyAppend(suffix2, suffix1))), suffix3 = empty3, suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else if(data5.length < WIDTH-2) copy(data5 = copyAppend(data5, copyAppend(suffix4, copyAppend(suffix3, copyAppend(suffix2, suffix1)))), suffix4 = empty4, suffix3 = empty3, suffix2 = empty2, suffix1 = wrap1(elem), length0 = length0+1)

else new Vector6(prefix1, len1, prefix2, len12, prefix3, len123, prefix4, len1234, data5, (WIDTH-2)*WIDTH4 + len1234, empty6, wrap5(copyAppend(suffix4, copyAppend(suffix3, copyAppend(suffix2, suffix1)))), empty4, empty3, empty2, wrap1(elem), length0+1)

}

override def prepended[B >: A](elem: B): Vector[B] = {

if (len1 < WIDTH ) copy(copyPrepend1(elem, prefix1), len1+1, len12 = len12+1, len123 = len123+1, len1234 = len1234+1, length0 = length0+1)

else if(len12 < WIDTH2 ) copy(wrap1(elem), 1, copyPrepend(prefix1, prefix2), len12+1, len123 = len123+1, len1234 = len1234+1, length0 = length0+1)

else if(len123 < WIDTH3 ) copy(wrap1(elem), 1, empty2, 1, copyPrepend(copyPrepend(prefix1, prefix2), prefix3), len123+1, len1234 = len1234+1, length0 = length0+1)

else if(len1234 < WIDTH4 ) copy(wrap1(elem), 1, empty2, 1, empty3, 1, copyPrepend(copyPrepend(copyPrepend(prefix1, prefix2), prefix3), prefix4), len1234+1, length0 = length0+1)

else if(data5.length < WIDTH-2) copy(wrap1(elem), 1, empty2, 1, empty3, 1, empty4, 1, copyPrepend(copyPrepend(copyPrepend(copyPrepend(prefix1, prefix2), prefix3), prefix4), data5), length0 = length0+1)

else new Vector6(wrap1(elem), 1, empty2, 1, empty3, 1, empty4, 1, wrap5(copyPrepend(copyPrepend(copyPrepend(prefix1, prefix2), prefix3), prefix4)), len1234+1, empty6, data5, suffix4, suffix3, suffix2, suffix1, length0+1)

}

override def map[B](f: A => B): Vector[B] =

copy(prefix1 = mapElems1(prefix1, f), prefix2 = mapElems(2, prefix2, f), prefix3 = mapElems(3, prefix3, f), prefix4 = mapElems(4, prefix4, f),

data5 = mapElems(5, data5, f),

suffix4 = mapElems(4, suffix4, f), suffix3 = mapElems(3, suffix3, f), suffix2 = mapElems(2, suffix2, f), suffix1 = mapElems1(suffix1, f))

protected[this] def slice0(lo: Int, hi: Int): Vector[A] = {

val b = new VectorSliceBuilder(lo, hi)

b.consider(1, prefix1)

b.consider(2, prefix2)

b.consider(3, prefix3)

b.consider(4, prefix4)

b.consider(5, data5)

b.consider(4, suffix4)

b.consider(3, suffix3)

b.consider(2, suffix2)

b.consider(1, suffix1)

b.result()

}

override def tail: Vector[A] =

if(len1 > 1) copy(copyTail(prefix1), len1-1, len12 = len12-1, len123 = len123-1, len1234 = len1234-1, length0 = length0-1)

else slice0(1, length0)

override def init: Vector[A] =

if(suffix1.length > 1) copy(suffix1 = copyInit(suffix1), length0 = length0-1)

else slice0(0, length0-1)

protected[immutable] def vectorSliceCount: Int = 9

protected[immutable] def vectorSlice(idx: Int): Array[_ <: AnyRef] = (idx: @switch) match {

case 0 => prefix1

case 1 => prefix2

case 2 => prefix3

case 3 => prefix4

case 4 => data5

case 5 => suffix4

case 6 => suffix3

case 7 => suffix2

case 8 => suffix1

}

protected[immutable] def vectorSlicePrefixLength(idx: Int): Int = (idx: @switch) match {

case 0 => len1

case 1 => len12

case 2 => len123

case 3 => len1234

case 4 => len1234 + data5.length*WIDTH4

case 5 => len1234 + data5.length*WIDTH4 + suffix4.length*WIDTH3

case 6 => len1234 + data5.length*WIDTH4 + suffix4.length*WIDTH3 + suffix3.length*WIDTH2

case 7 => length0 - suffix1.length

case 8 => length0

}

override protected[this] def prependedAll0[B >: A](prefix: collection.IterableOnce[B], k: Int): Vector[B] =

prepend1IfSpace(prefix1, prefix) match {

case null => super.prependedAll0(prefix, k)

case prefix1b =>

val diff = prefix1b.length - prefix1.length

copy(prefix1 = prefix1b,

len1 = len1 + diff,

len12 = len12 + diff,

len123 = len123 + diff,

len1234 = len1234 + diff,

length0 = length0 + diff,

)

}

override protected[this] def appendedAll0[B >: A](suffix: collection.IterableOnce[B], k: Int): Vector[B] = {

val suffix1b = append1IfSpace(suffix1, suffix)

if(suffix1b ne null) copy(suffix1 = suffix1b, length0 = length0-suffix1.length+suffix1b.length)

else super.appendedAll0(suffix, k)

}

}

/** 6-dimensional radix-balanced finger tree */

private final class Vector6[+A](_prefix1: Arr1, private[immutable] val len1: Int,

private[immutable] val prefix2: Arr2, private[immutable] val len12: Int,

private[immutable] val prefix3: Arr3, private[immutable] val len123: Int,

private[immutable] val prefix4: Arr4, private[immutable] val len1234: Int,

private[immutable] val prefix5: Arr5, private[immutable] val len12345: Int,

private[immutable] val data6: Arr6,

private[immutable] val suffix5: Arr5, private[immutable] val suffix4: Arr4, private[immutable] val suffix3: Arr3, private[immutable] val suffix2: Arr2, _suffix1: Arr1,

_length0: Int) extends BigVector[A](_prefix1, _suffix1, _length0) {

@inline private[this] def copy(prefix1: Arr1 = prefix1, len1: Int = len1,

prefix2: Arr2 = prefix2, len12: Int = len12,

prefix3: Arr3 = prefix3, len123: Int = len123,

prefix4: Arr4 = prefix4, len1234: Int = len1234,

prefix5: Arr5 = prefix5, len12345: Int = len12345,

data6: Arr6 = data6,

suffix5: Arr5 = suffix5, suffix4: Arr4 = suffix4, suffix3: Arr3 = suffix3, suffix2: Arr2 = suffix2, suffix1: Arr1 = suffix1,

length0: Int = length0) =

new Vector6(prefix1, len1, prefix2, len12, prefix3, len123, prefix4, len1234, prefix5, len12345, data6, suffix5, suffix4, suffix3, suffix2, suffix1, length0)

@inline def apply(index: Int): A = {

if(index >= 0 && index < length0) {

val io = index - len12345

if(io >= 0) {

val i6 = io >>> BITS5

val i5 = (io >>> BITS4) & MASK