// Abstract classes

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
}



//======================================================================
// Traits
//
// are like abstract classes, but used as "mixins",
//  or in other words: as interfaces containing code (and maybe also data)
// more later
//======================================================================

/*
class EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
}
*/


class NonEmptySet(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 NonEmptySet(elem, left incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this
}

// better version, singleton pattern is builtin into Scala
// [object creation time: first time a method is accessed, i.e. lazy]
object EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, EmptySet, EmptySet)
}