higher_kinded_types_graph_search_bfs_dfs

higher_kinded_types_graph_search_bfs_dfs.scala

import scala.annotation.tailrec
import scala.collection.immutable.{Queue, Stack}

sealed trait Tree[T] {
  def value: T
}
case class Node[T](value: T, children: List[Tree[T]]) extends Tree[T]
case class Leaf[T](value: T) extends Tree[T]


// Tree search is a higher kinded type,
// and depth first and breadth first search are first order type constructors
trait TreeSearch[H[T] <: List[T]] {
  def initFrontier[T]: H[T]
  def addToFrontier[T](t: T, f: H[T]): H[T]
  def removeFromFrontier[T](f: H[T]): (T, H[T])

  def visitNodes[T](treeRoot: Tree[T], element: T, visitFn: T => Unit): Unit = {
    @tailrec
    def loop(currFrontier: H[Tree[T]]): Unit = {
      if (currFrontier.nonEmpty) {
        val (currNode, newFrontier) = removeFromFrontier(currFrontier)
        if (currNode.value == element) visitFn(element)
        currNode match {
          case Node(_, children) =>
            val childFrontier = children.foldLeft(newFrontier)((acc, child) => addToFrontier(child, acc))
            loop(childFrontier)
          case Leaf(_) => // We are already done
        }
      }
    }

    loop(initFrontier())
  }
}

class DepthFirstSearch[T] extends TreeSearch[Queue[T]] {
  override def initFrontier[T]: Queue[T] = Queue()
  override def addToFrontier[T](t: T, q: Queue[T]): Queue[T] = q.enqueue(t)
  override def removeFromFrontier[T](q: Queue[T]): (T, Queue[T]) = q.dequeue
}

class BreadFirstSearch[T] extends TreeSearch[Stack[T]] {
  override def initFrontier[T]: Stack[T] = Stack()
  override def addToFrontier[T](t: T, f: Stack[T]): Stack[T] = f.push(t)
  override def removeFromFrontier[T](f: Stack[T]): (T, Stack[T]) = f.pop2
}