Created
May 2, 2019 07:35
-
-
Save baseerhk/3dcb978120e3628a388e3418d8b4d3c2 to your computer and use it in GitHub Desktop.
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) | |
} | |
} | |
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 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment