This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
sealed trait CompleteBinaryTree[A] { | |
def lookup(size: Int, index: Int): A = (this, index) match { | |
case (Leaf(x), 0) => x | |
case (Leaf(_), _) => throw new Exception("Index is not in list.") | |
case (Node(x, _, _), 0) => x | |
case (Node(x, l, _), i) if i <= size / 2 => l.lookup(size / 2, i - 1) | |
case (Node(x, _, r), i) if i > size / 2 => r.lookup(size / 2, i - 1 - size / 2) | |
} | |
def update(size: Int, index: Int, y: A): CompleteBinaryTree[A] = (this, index) match { | |
case (Leaf(_), 0) => Leaf(y) |