object Week3 extends Application {
  
  abstract class IntSet {
    def incl(x: int): IntSet
    def contains(x: int): boolean
  }
  
  class Empty extends IntSet {

    def contains(x: int): boolean = false

    def incl(x: int): IntSet = new NonEmpty(x, new Empty, new Empty)

    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

    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

    override def toString() = "(" + left + "|" + elem + "|" + right + ")"
  }

  val s = (new Empty).incl(3).incl(1).incl(4).incl(6).incl(5)
  Console.println(s)
  Console.println(s.contains(1))
  Console.println(s.contains(5))

}