package com.codecommit.collection
import Math.max
import Vector._
/**
* An immutable implementation of the {@link Seq} interface with an array
* backend. Effectively, this class is an immutable vector. The only wrinkle
* in this design is the ability to store elements in *completely* arbitrary
* indexes (to enable use as a random-access array). Thus, the length of this
* data structure is effectively infinite. The {@link #length} field is defined
* to return the maximum index of the elements in the vector.

*
* The underlying data structure for the persistent vector is a trie with an
* extremely high branching factor (in this case: 32). Each trie node contains
* an array representing each branch. This implementation allows almost-constant
* time access coupled with minimal data-copying on insert. The ratio between
* these two is controlled by the branching factor. A higher branching factor
* will lead to a better worst-case access time (asymtotically more constant)
* while a lower branching factor will result in asymtotically less data
* copying on insert.

*
* As is natural for an immutable data structure, this vector is parameterized
* covariantly. This poses a few minor difficulties in implementation, due to
* the fact that arrays, as mutable containers, are parameterized
* *invariantly*. To get around this, some up-casting is utilized durring
* insertion. This is considered to be sound due to the fact that the type
* system will ensure that the casting is always upwards, rather than down (which
* is where the mutability concerns come into play).

*
* @author Daniel Spiewak
*/
class Vector[+T] private (private val data: Option[T], val length: Int, private val branches: Seq[Vector[T]]) extends RandomAccessSeq[T] {
def this() = this(None, 0, new Array[Vector[T]](BRANCHING_FACTOR))
def apply(i: Int) = locate(computePath(i, branches.length))
private def locate(path: List[Int]): T = path match {
case hd :: tail => {
val node = branches(hd)
if (node == null) null.asInstanceOf[T] else node.locate(tail)
}
case Nil => data.get
}
def +[A >: T](e: A) = update(length, e)
def update[A >: T](i: Int, e: A) = store(computePath(i, branches.length), e)
private def store[A >: T](path: List[Int], e: A): Vector[A] = path match {
case hd :: tail => {
val node = branches(hd)
val vector = if (node == null) EmptyVector else node
val newBranches = new Array[Vector[A]](branches.length)
Array.copy(branches, 0, newBranches, 0, branches.length)
newBranches(hd) = vector.store(tail, e)
new Vector(data, max(length, flattenPath(path, branches.length) + 1), newBranches)
}
case Nil => new Vector(Some(e), max(length, flattenPath(path, branches.length) + 1), branches)
}
override def map[A](f: (T)=>A): Vector[A] = {
val newBranches = branches map { vec =>
if (vec == null) null else vec map f
}
new Vector(data map f, length, newBranches)
}
override def equals(other: Any) = other match {
case vec:Vector[T] => {
var back = length == vec.length
for (i <- 0 until length) {
back &&= this(i) == vec(i)
}
back
}
case _ => false
}
}
object Vector {
val BRANCHING_FACTOR = 32
def apply[T](elems: T*) = {
var vector = new Vector[T]
var i = 0
for (e <- elems) {
vector = vector(i) = e
i += 1
}
vector
}
private[collection] def computePath(total: Int, base: Int): List[Int] = {
if (total < 0) {
throw new IndexOutOfBoundsException(total.toString)
} else if (total < base) List(total) else {
var num = total
var digits = 0
while (num >= base) {
num /= base
digits += 1
}
val rem = total % (Math.pow(base, digits)).toInt
val subPath = computePath(rem, base)
num :: (0 until (digits - subPath.length)).foldRight(subPath) { (i, path) => 0 :: path }
}
}
@inline
private[collection] def flattenPath(path: List[Int], base: Int) = path.foldLeft(0) { _ * base + _ }
}
object EmptyVector extends Vector[Nothing]