package com.codecommit.collection

import Math.max
import Vector._

/**
 * <p>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 <i>completely</i> 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.</p>
 * 
 * <p>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.</p>
 *
 * <p>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
 * <i>invariantly</i>.  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).</p>
 * 
 * @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]