Trie.scala

Trie.scala

case class TrieNode[T](edgeList: Map[T, TrieNode[T]] = Map.empty[T, TrieNode[T]], isLeaf: Boolean = false,
                       isEntry: Boolean = false)

object TrieNode {
  def emptyTrieNode[T]: TrieNode[T] = {
    TrieNode[T]()
  }

  def newTrieNode[T](data: T): TrieNode[T] = {
    TrieNode[T](edgeList = Map[T, TrieNode[T]]((data, emptyTrieNode[T])))
  }

  def constructTrieNodeMap[T](l: List[T], t: TrieNode[T] = TrieNode.emptyTrieNode[T]): TrieNode[T] = {
    l match {
      case ::(head, Nil) =>
        t.edgeList.find(e => e._1 == head) match {
          case Some(value) =>
            t.copy(edgeList = t.edgeList.updated(value._1, value._2.copy(isEntry = true)))
            value._2.copy(isEntry = true)
          case None =>
            t.copy(edgeList = t.edgeList.updated(head, TrieNode.emptyTrieNode[T].copy(isLeaf = true, isEntry = true)))
        }
      case ::(head, next) =>
        t.edgeList.find(e => e._1 == head) match {
          case Some(value) =>
            t.copy(edgeList = t.edgeList.updated(head, constructTrieNodeMap[T](next, value._2)))
          case None =>
            t.copy(edgeList = t.edgeList.updated(head, constructTrieNodeMap[T](next)))
        }
      case Nil =>
        TrieNode.emptyTrieNode[T]
    }
  }

  def constructTrieNodeFromList[T](l: List[List[T]], t: TrieNode[T] = TrieNode.emptyTrieNode[T]): TrieNode[T] = {
    l.foldLeft(t) {
      (a, b) => {
        constructTrieNodeMap(b, a)
      }
    }
  }
}
//Resilient, Elastic, MessageDriven, Responsive