PFDS Exercise 2.3

pfds_insert_use_exceptions.scala

class ElementAlreadyExistsException extends RuntimeException

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T]) extends Set[T] {
  // ...
  def insert(x: T) = try {
    newSet(UnbalancedTreeSet.insert(x, tree))
  } catch {
    case _:ElementAlreadyExistsException => this
  }
  // ...
}
 
object UnbalancedTreeSet {
  // ...
  private def insert[T](x: T, t: BinaryTree[T])(implicit ordering: Ordering[T]): BinaryTree[T] = t match {
    case BinaryTreeLeaf => BinaryTreeNode(BinaryTreeLeaf, x, BinaryTreeLeaf)
    case BinaryTreeNode(a, y, b) =>
      if (ordering.lt(x, y)) BinaryTreeNode(insert(x, a), y, b)
      else if (ordering.lt(y, x)) BinaryTreeNode(a, y, insert(x, b))
      else throw new ElementAlreadyExistsException
  }
  // ...
}