ex_6_0_1.scala

abstract class IntSet {
  def isEmpty: Boolean 
  def contains(x: Int): Boolean
  def include(x: Int): IntSet
  def union(other: IntSet): IntSet
}

class EmptySet extends IntSet {
  def isEmpty = true
  def contains(x: Int): Boolean = false
  def include(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
  def union(other: IntSet) = other
}

class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
  def isEmpty = false
  def contains(x: Int): Boolean = {
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true
  } 
  def include(x: Int): IntSet = {
    if (x < elem) new NonEmptySet(elem, left include x, right)
    else if (x > elem) new NonEmptySet(elem, left, right include x)
    else this
  }
  def union(other: IntSet): IntSet = other.union(left).union(right).include(elem)
}

/* unit tests */
val u = new NonEmptySet(2, new NonEmptySet(1, new EmptySet, new EmptySet), new NonEmptySet(3, new EmptySet, new EmptySet))
val v = new NonEmptySet(5, new NonEmptySet(4, new EmptySet, new EmptySet), new EmptySet)

val w = u.union(v)
assert(w.contains(1) == true)
assert(w.contains(2) == true)
assert(w.contains(3) == true)
assert(w.contains(4) == true)
assert(w.contains(5) == true)
assert(w.contains(6) == false)

val x = v.union(u)
assert(x.contains(1) == true)
assert(x.contains(2) == true)
assert(x.contains(3) == true)
assert(x.contains(4) == true)
assert(x.contains(5) == true)
assert(x.contains(6) == false)