Trie

Trie.scala

import collection.mutable.SetLike

class Trie[A] extends Set[List[A]] {

  type S = List[A]
  type This = Trie[A]

  sealed abstract class AbstractLayer
  case class Layer(val map: Map[A, Layer]) extends AbstractLayer
  case class Entry(val seq: S) extends AbstractLayer
  case object Empty extends AbstractLayer

  var layers: AbstractLayer = Empty

  def contains(elem: S): Boolean = {
    def contains(layer: AbstractLayer, elem: S): Boolean = elem match {
      case head :: tail =>
        layer match {
          case Layer(map) => map.get(head).map(contains(_, tail)).getOrElse(false)
          case Entry(seq) => true
          case Empty => false
        }
      case Nil => false
    }

    contains(layers, elem)
  }


  def iterator: Iterator[S] = null
  def += (elem: S): this.type = this
  def -= (elem: S): this.type = this

  def + (elem: S): This = this
  def - (elem: S): This = this
}