/**
 * Template for mini project 1: Sets
 *
 * This is a code template for the first mini project.
 * It contains pre-defined functions that help you
 * solve the given problems.
 *
 * @author Philipp Haller
 * @version 1.2
 */
package project1

object sets extends Application {
  /**
   * This type alias defines how sets are represented.
   */
  type Set = Int => Boolean

  /**
   * This function tests whether a set contains a given element.
   */
  def contains(s: Set, elem: Int): Boolean = s(elem)

  /**
   * This function displays the contents of a set in the
   * Test Pad (Scala plugin for Eclipse).
   */
  def toString(s: Set): String = {
    val xs = for (i <- -1000 to 1000 if contains(s, i)) yield i
    xs.mkString("{", ",", "}")
  }

  /**
   * This function prints the contents of a set on the console.
   */
  def printSet(s: Set) {
    println(toString(s))
  }

  //////////////////////////////////////////////////
  //// Seconde partie : ensemble orientes-objet ////
  //////////////////////////////////////////////////

  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)
  }

  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
  }
}