// Traits are like interfaces
trait MySet[A] extends (A => Boolean) {
  def apply(element: A): Boolean = contains(element)

  def contains(element: A): Boolean

  def +(element: A): MySet[A]
  def ++(otherSet: MySet[A]): MySet[A]
  def -(element: A): MySet[A]
  def --(otherSet: MySet[A]): MySet[A]

  def map[B](fn: A => B): MySet[B]
  def flatMap[B](fn: A => MySet[B]): MySet[B]
  def filter(fn: A => Boolean): MySet[A]
  def foreach(fn: A => Unit): Unit
}

class EmptySet[A] extends MySet[A] {
  def contains(element: A): Boolean = false

  def +(element: A): MySet[A] = new NonEmptySet(element, this)
  def ++(otherSet: MySet[A]): MySet[A] = otherSet
  def -(element: A): MySet[A] = this
  def --(otherSet: MySet[A]): MySet[A] = this

  def map[B](fn: A => B): MySet[B] = new EmptySet[B]
  def flatMap[B](fn: A => MySet[B]): MySet[B] = new EmptySet[B]
  def filter(fn: A => Boolean): MySet[A] = this
  def foreach(fn: A => Unit): Unit = ()
}

class NonEmptySet[A](head: A, tail: MySet[A]) extends MySet[A] {
  def contains(element: A): Boolean =
    head == element || tail.contains(element)

  def +(element: A): MySet[A] =
    if (this contains element) this
    else new NonEmptySet[A](element, this)

  def ++(otherSet: MySet[A]): MySet[A] =
    tail ++ otherSet + head

  def -(element: A): MySet[A] =
    if (head == element) tail
    else tail - element + head

  def --(otherSet: MySet[A]): MySet[A] = filter(e => !otherSet.contains(e))

  def map[B](fn: A => B): MySet[B] = (tail map fn) + fn(head)
  def flatMap[B](fn: A => MySet[B]): MySet[B] = (tail flatMap fn) ++ fn(head)
  def filter(fn: A => Boolean): MySet[A] = {
    val filteredTail = tail filter fn
    if (fn(head)) filteredTail + head
    else filteredTail
  }
  def foreach(fn: A => Unit): Unit = {
    fn(head)
    tail foreach fn
  }
}

object MySet {
  def apply[A](values: A*): MySet[A] = {
    @tailrec
    def buildSet(valueSequence: Seq[A], accumulator: MySet[A]): MySet[A] = {
      if (valueSequence.isEmpty) accumulator
      else buildSet(valueSequence.tail, accumulator + valueSequence.head)
    }

    buildSet(values.toSeq, new EmptySet[A])
  }
}