PFDS Exercise 2.2

pfds_member_delayed_equality_check.scala

class UnbalancedTreeSet[T] private (tree: BinaryTree[T]) (implicit val ordering: Ordering[T]) extends Set[T] {
  // ...
  def member(x: T) = UnbalancedTreeSet.member(x, tree, None)
  // ...
}

object UnbalancedTreeSet {
  // ...
  private def member[T](x: T, t: BinaryTree[T], c: Option[T])(implicit ordering: Ordering[T]): Boolean = (t, c) match {
    case (BinaryTreeLeaf, None) => false
    case (BinaryTreeLeaf, Some(d)) => ordering.equiv(x, d)
    case (BinaryTreeNode(a, y, b), _) =>
      if (ordering.lt(x, y)) member(x, a, c)
      else member(x, b, Some(y))
  }
  // ...
}