Last active
March 10, 2019 03:20
-
-
Save JamesMenetrey/12b886227efbd1b7f3bf0d95f3b438cf to your computer and use it in GitHub Desktop.
Academic implementation of a binary tree in Scala.
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
| // Written by Jämes Ménétrey for the lecture Advanced Programming Paradigms. | |
| // Linear walk through inspired from https://gist.github.com/dholbrook/2967371. | |
| import scala.annotation.tailrec | |
| import scala.language.implicitConversions | |
| object BinaryTreeImpl { | |
| /** | |
| * The contract that defines a binary tree. | |
| */ | |
| abstract class BinaryTree[A](implicit ordering: Ordering[A]) { | |
| def +(x: A): BinaryTree[A] = add(x) | |
| def +(x: BinaryTree[A]): BinaryTree[A] = union(x) | |
| def -(x: A): BinaryTree[A] = excl(x) | |
| def add(x: A): BinaryTree[A] | |
| def contains(x: A): Boolean | |
| def excl(elems: A): BinaryTree[A] | |
| def foreach(f: A => Unit): Unit = iteratorInorder().foreach(f) | |
| def foldInorder[B](z: B)(op: (B, A) => B): B = iteratorInorder().foldLeft(z)(op) | |
| def foldPreorder[B](z: B)(op: (B, A) => B): B = iteratorPreorder().foldLeft(z)(op) | |
| def foldPostorder[B](z: B)(op: (B, A) => B): B = iteratorPostorder().foldLeft(z)(op) | |
| def intersect(other: BinaryTree[A]): BinaryTree[A] | |
| def isEmpty: Boolean | |
| def iteratorInorder(): Iterator[A] = new Iterators.InorderBinaryTreeIterator[A](this) | |
| def iteratorPreorder(): Iterator[A] = new Iterators.PreorderBinaryTreeIterator[A](this) | |
| def iteratorPostorder(): Iterator[A] = new Iterators.PostorderBinaryTreeIterator[A](this) | |
| def union(other: BinaryTree[A]): BinaryTree[A] | |
| } | |
| /** | |
| * The companion object to create binary trees. | |
| */ | |
| object BinaryTree { | |
| /** | |
| * Creates a new binary tree from 0 to n elements. | |
| */ | |
| def apply[A](elements: A*)(implicit ordering: Ordering[A]): BinaryTree[A] = | |
| elements.foldLeft(new EmptyBinaryTree[A](): BinaryTree[A]) { (acc, e) => acc add e } | |
| /** | |
| * Defines an implicit conversion from ordering element to binary trees, so methods can directly be called from. | |
| */ | |
| implicit def AToBinaryTree[A](x: A)(implicit ordering: Ordering[A]): BinaryTree[A] = BinaryTree(x) | |
| } | |
| /** | |
| * A definition of a non empty binary tree. | |
| */ | |
| class NonEmptyBinaryTree[A](val elem: A, val left: BinaryTree[A], val right: BinaryTree[A])(implicit val ordering: Ordering[A]) extends BinaryTree[A] { | |
| /** | |
| * Adds an element in the binary tree. | |
| * | |
| * Complexity: O(log n) | |
| */ | |
| override def add(x: A): BinaryTree[A] = { | |
| if (ordering.lt(x, elem)) new NonEmptyBinaryTree[A](elem, left add x, right) | |
| else if (ordering.gt(x, elem)) new NonEmptyBinaryTree[A](elem, left, right add x) | |
| else this | |
| } | |
| /** | |
| * Determines whether the binary tree contains a given element. | |
| * | |
| * Complexity: O(log n) | |
| */ | |
| override def contains(x: A): Boolean = { | |
| if (ordering.lt(x, elem)) left contains x | |
| else if (ordering.gt(x, elem)) right contains x | |
| else true | |
| } | |
| /** | |
| * Removes an element from the binary tree. | |
| * | |
| * Complexity: O(log n) | |
| */ | |
| override def excl(x: A): BinaryTree[A] = { | |
| /** | |
| * Finds the deepest right element of the tree from a given node. | |
| */ | |
| @tailrec | |
| def findDeepestRightElement(node: NonEmptyBinaryTree[A]): A = node.right match { | |
| case _: EmptyBinaryTree[A] => node.elem | |
| case right: NonEmptyBinaryTree[A] => findDeepestRightElement(right) | |
| } | |
| if(ordering.lt(x, elem)) new NonEmptyBinaryTree[A](elem, left excl x, right) | |
| else if(ordering.gt(x, elem)) new NonEmptyBinaryTree[A](elem, left, right excl x) | |
| else { | |
| left match { | |
| case _: EmptyBinaryTree[A] => right | |
| case l: NonEmptyBinaryTree[A] => | |
| val replacementElement = findDeepestRightElement(l) | |
| new NonEmptyBinaryTree[A](replacementElement, left excl replacementElement, right) | |
| } | |
| } | |
| } | |
| override def isEmpty: Boolean = false | |
| /** | |
| * Intersects two binary trees using the merge algorithm. | |
| * | |
| * Complexity: O(n + m) | |
| */ | |
| override def intersect(other: BinaryTree[A]): BinaryTree[A] = { | |
| val thisIterator = iteratorInorder() | |
| val otherIterator = other.iteratorInorder() | |
| @tailrec | |
| def iter(x: A, y: A, acc: BinaryTree[A]): BinaryTree[A] = acc match { | |
| case a if ordering.lt(x, y) => iter(thisIterator.next(), y, a) | |
| case a if ordering.gt(x, y) => iter(x, otherIterator.next(), a) | |
| case a if ordering.equiv(x, y) && !thisIterator.hasNext || !otherIterator.hasNext => a add x | |
| case a if ordering.equiv(x, y) => iter(thisIterator.next(), otherIterator.next(), a add x) | |
| case a => a | |
| } | |
| iter(thisIterator.next(), otherIterator.next(), new EmptyBinaryTree[A]()) | |
| } | |
| /** | |
| * Formats all the nodes of the binary tree. | |
| * | |
| * Complexity: O(n) | |
| */ | |
| override def toString: String = s"($left|$elem|$right)" | |
| /** | |
| * Unifies two binary trees. | |
| * | |
| * Complexity: O(m * log n) | |
| */ | |
| def union(other: BinaryTree[A]): BinaryTree[A] = foldInorder(other) { (acc, e) => acc add e } | |
| } | |
| /** | |
| * A definition of an empty binary tree. | |
| */ | |
| class EmptyBinaryTree[A]()(implicit ordering: Ordering[A]) extends BinaryTree[A] { | |
| override def add(x: A): BinaryTree[A] = new NonEmptyBinaryTree[A](x, new EmptyBinaryTree[A], new EmptyBinaryTree[A]) | |
| override def contains(x: A): Boolean = false | |
| override def excl(elems: A): BinaryTree[A] = this | |
| override def intersect(other: BinaryTree[A]) = new EmptyBinaryTree[A]() | |
| override def isEmpty: Boolean = true | |
| override def toString: String = "-" | |
| def union(other: BinaryTree[A]): BinaryTree[A] = other | |
| } | |
| /** | |
| * Definition of the iterators of the binary trees. | |
| */ | |
| object Iterators { | |
| /** | |
| * A type that indicates that the node of the tree must be evaluated when linearized through the method extractor. | |
| * This enables to walk through the tree using a tail recursion with different orders. | |
| */ | |
| private class WaitingForEval[A](elem: A)(implicit ordering: Ordering[A]) extends NonEmptyBinaryTree[A](elem, null, null) | |
| class InorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A]) | |
| extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](set.left, new WaitingForEval(set.elem), set.right)) | |
| class PreorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A]) | |
| extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](new WaitingForEval(set.elem), set.left, set.right)) | |
| class PostorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A]) | |
| extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](set.left, set.right, new WaitingForEval(set.elem))) | |
| /** | |
| * The iterator of a binary tree. The tree is linearised to prevent extensive use of the stack. | |
| */ | |
| abstract class BinaryTreeIterator[A](tree: BinaryTree[A], order: NonEmptyBinaryTree[A] => List[BinaryTree[A]]) extends Iterator[A] { | |
| // Scala doc recommends to use a var instead of a val stack. Let's face the reality, an iterator is stateful. | |
| var list: List[BinaryTree[A]] = removeEmptyTree(List(tree)) | |
| override def hasNext: Boolean = list.nonEmpty | |
| override def next(): A = extractor(list) | |
| /** | |
| * Loops across the nodes of the binary tree using a tail recursion. | |
| */ | |
| @tailrec | |
| private def extractor(l: List[BinaryTree[A]]): A = l match { | |
| case (h: WaitingForEval[A]) :: r => list = removeEmptyTree(r); h.elem | |
| case (h: NonEmptyBinaryTree[A]) :: r => list = removeEmptyTree(order(h)) ++ r; extractor(list) | |
| case _ => throw new UnsupportedOperationException("Cannot call next method with no element left in the iterator.") | |
| } | |
| private def removeEmptyTree(l: List[BinaryTree[A]]): List[BinaryTree[A]] = l.dropWhile(_.isEmpty) | |
| } | |
| } | |
| } | |
| import BinaryTreeImpl._ | |
| val s1 = BinaryTree[Int]() | |
| .add(2) | |
| .add(1) | |
| .add(3) | |
| .add(0) | |
| s1.foldPreorder("") { (acc, e) => s"$acc[$e]" } | |
| s1.foldPostorder("") { (acc, e) => s"$acc[$e]" } | |
| s1.contains(3) | |
| s1.contains(4) | |
| s1.foreach(e => print(s"[$e]")) | |
| BinaryTree(5, 4, 3, 2, 1).foldInorder(0)(_ + _) | |
| // | |
| // 1.c | |
| // | |
| s1.foreach(e => print(s"${e + 1}, ")) | |
| // | |
| // 2.a | |
| // | |
| BinaryTree(1, 2, 3) union BinaryTree(4, 5, 6) | |
| // | |
| // 2.b | |
| // | |
| BinaryTree(1, 2, 3) intersect BinaryTree(3, 4, 1) | |
| // | |
| // 3.a | |
| // | |
| BinaryTree(5,3,4,2,1,8,7,9,6) excl 3 | |
| // | |
| // 3.b | |
| // | |
| val s2 = BinaryTree[Int]() + 3 + 5 + 1 + 2 | |
| s2 - 3 | |
| // the implicit conversion is in the implicit scope because it is defined in the companion class AND there is | |
| // a +(BinaryTree[A]) method. Indeed, scala compiler import the implicit scope of the argument's type. | |
| 3 + BinaryTree(2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment