ral.scala

object RandomAccessList {
  type RandomAccessList[A] = List[(CompleteBinaryTree[A], Int)]

  def fromList[A](xs: List[A]): RandomAccessList[A] = {
    def sublists[A](xs: List[A]): List[(List[A], Int)] = {
      def inner(xs: List[A], size: Int, acc: List[(List[A], Int)]): List[(List[A], Int)] = size match {
        case 0 => acc
        case s => {
          val s_ = Math.pow(2, Math.floor(Math.log(s + 1) / Math.log(2))).toInt - 1
          inner(xs.take(s - s_), s - s_, (xs.drop(s - s_), s_)::acc)
        }
      }
      inner(xs, xs.length, List())
    }
    sublists(xs) map {pair => (CompleteBinaryTree(pair._1), pair._2)}
  }

  def lookup[A](ral: RandomAccessList[A], index: Int): A = ral match {
    case Nil                                => throw new Exception("Index is not in list.")
    case (tree, size)::_ if index < size    => tree.lookup(size, index)
    case (_, size)::tail if index >= size   => lookup(tail, index - size)
  }

  def update[A](ral: RandomAccessList[A], index: Int, y: A): RandomAccessList[A] = ral match {
    case Nil                                 => throw new Exception("Index is not in list.")
    case (tree, size)::tail if index < size  => (tree.update(size, index, y), size)::tail
    case (tree, size)::tail if index >= size => (tree, size)::update(tail, index - size, y)
  }

  def cons[A](ral: RandomAccessList[A], e: A): RandomAccessList[A] = ral match {
    case (tree1, size1)::(tree2, size2)::tail if size1 == size2 => (Node(e, tree1, tree2), size1 + size2 + 1)::tail
    case (tree1, size1)::(tree2, size2)::tail if size1 != size2 => (Leaf(e), 1)::(tree1, size1)::(tree2, size2)::tail
    case ts                                                     => (Leaf(e), 1)::ts
  }

  def head[A](ral: RandomAccessList[A]): A = ral match {
    case Nil                      => throw new Exception("Head of empty list.")
    case (Leaf(x), _)::tail       => x
    case (Node(x, _, _), _)::tail => x
  }

  def tail[A](ral: RandomAccessList[A]): RandomAccessList[A] = ral match {
    case Nil                         => throw new Exception("Tail of empty list.")
    case (Leaf(_), _)::tail          => tail
    case (Node(_, l, r), size)::tail => (l, size / 2)::(r, size / 2)::tail
  }
}