MySet2

abstract class MySet {
  def insert(v:Int): MySet
  def union(s:MySet): MySet
  def filter(f:Int=>Boolean): MySet
  def remove(v:Int): MySet
  def contains(v:Int): Boolean
  def foreach(f:Int=>Unit): Unit
  def map(f:Int=>Int): MySet
}

object EmptySet extends MySet {
  override def toString = ""
  override def insert(v:Int) = MySet(v)
  override def union(s:MySet) = s
  override def filter(f:Int=>Boolean) = MySet.empty
  override def remove(v:Int) = MySet.empty
  override def contains(v:Int) = false
  override def foreach(f:Int=>Unit) = Unit
  override def map(f:Int=>Int) = MySet.empty
}

class NonEmptySet(data:Int, left:MySet, right:MySet) extends MySet {
  override def toString = left.toString + data.toString + right.toString
  override def insert(v:Int) = {
    if(v < data) new NonEmptySet(data, left.insert(v), right)
    else new NonEmptySet(data, left, right.insert(v))
  }

  override def union(s:MySet) =  this.remove(data) union s.insert(data)

  override def filter(f:Int=>Boolean) = {
    if(f(data)) new NonEmptySet(data, left.filter(f), right.filter(f))
    else left.filter(f) union right.filter(f)
  }
  override def remove(v:Int) = filter(_ != v)
  override def contains(v:Int) = {
    if(v == data) true
    else if(left.contains(v) || right.contains(v)) true
      else false
  }
  override def foreach(f:Int=>Unit) = {
    left.foreach(f)
    f(data)
    right.foreach(f)
  }
  override def map(f:Int=>Int) = {
    new NonEmptySet(f(data), MySet.empty, MySet.empty).union(left.map(f).union(right.map(f)))
  }
}

object MySet {
  def empty:MySet = EmptySet
  def apply(v:Int) = new NonEmptySet(v, empty, empty)
  def apply(l:List[Int]) = {
    l.foldLeft(empty)((s,e)=>s.insert(e))
  }
}

object Main extends App {
  val s1 = MySet((1 to 10000).toList)
  val s2 = MySet((10001 to 20000).toList)

  val s3 = s1.union(s2)

  println(s3.contains(2000))
}

//http://www.scala-lang.org/api/current/#scala.collection.immutable.List