object IntSet {

  abstract class IntSet { // extends java.lang.Object
    def incl(x: Int): IntSet
    def contains(x: Int): Boolean
    def union(other: IntSet): IntSet
  }

  // singleton object
  object Empty extends IntSet {
    def contains(x: Int): Boolean = false
    def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
    def union(other: IntSet): IntSet = other
    override def toString = "."
  }

  class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    def contains(x: Int): Boolean =
      if (x < elem) left contains x
      else if (x > elem) right contains x
      else true
    // creat a new tree, but does not destroy the previous one
    // persistent data structure
    def incl(x: Int): IntSet =
      if (x < elem) new NonEmpty(elem, left incl x, right)
      else if (x > elem) new NonEmpty(elem, left, right incl x)
      else this
    def union(other: IntSet): IntSet =
      ((left union right) union other) incl elem
    override def toString = "{" + left + elem + right + "}"
  }

  def run = {
    println("IntSet")
    val t1 = new NonEmpty(3, Empty, Empty)
    println(t1)
    println(t1 contains 4)
    val t2 = t1 incl 4
    println(t1)
    println(t2 toString)
    println(t2 contains 4)
  }

}