package kapitel_10

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 10, Verbindungen finden
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_10_05_SpanningTree_App extends App {

  import scala.collection.mutable

  /**
   * Disjoint set implementation.
   * Maintains a partition of a set.
   *
   * @param as the elements of the set. Initially each element belongs to
   *           a different partition. The set as thus is separated into
   *           partitions whith a single element.
   * @tparam A the type of the elements.
   */
  class DS[A](as: Seq[A]) {

    private var k = new mutable.HashMap[A, A]() // a -> next element in a"s partition or a if a is the representative
    private var s = new mutable.HashMap[A, Int]() // a -> size of partion with representative a

    as.foreach( a => {
      k += (a -> a)
      s += (a -> 1)
    })

    /**
     * Find the set to which a belongs in terms of the representative of this set.
     * @param a a element of a set
     * @return  the representative of the set to which a belongs
     */
    def find(a: A):A = {
      var a_ = a
      while (a_ != k(a_)) {
        a_ = k(a_)
      }
      a_
    }

    /**
     * Unite the two sets that x and y belong to.
     * This have to be different set.
     * @param x a set
     * @param y another set
     */
    def unite(x: A, y: A): Unit = {
      val a = find(x)
      val b = find(y)
      if (s(a) >= s(b)) {
        s(a) = s(a) + s(b)
        k(b) = a
      } else {
        s(b) = s(b) + s(a)
        k(a) = b
      }
    }
  }


  trait Graph[A] {
    val V: List[A]
    val E: List[(A, A)]
    val w: Map[(A, A), Int]
  }

  def kruskalDS[A](g:Graph[A]): List[(A, A)] = {

    var a: List[(A, A)] = Nil
    val ds: DS[A] = new DS(g.V)

    val eSorted: List[(A, A)] = g.E.sortBy {
      case (u, v) => g.w((u, v))
    }

    for( (u,v) <- eSorted) {
      if (ds.find(u) != ds.find(v)) {
        a = (u, v) :: a
        ds.unite(u, v)
      }
    }

    a.reverse
  }

  val graph = new Graph[String] {
    override val V = List("a", "b", "c", "d", "e", "f")
    override val E = List(
      ("a", "b"), ("a", "f"), ("a", "e"),
      ("b", "c"), ("b", "f"),
      ("c", "d"), ("c", "f"),
      ("d", "e"), ("d", "f"),
      ("e","f")
    )
    override val w = Map(
      ("a", "b")->3, ("a", "f")->5, ("a", "e")->6,
      ("b", "c")->1, ("b", "f")->4,
      ("c", "d")->6, ("c", "f")->4,
      ("d", "e")->8, ("d", "f")->5,
      ("e", "f")->2
    )
  }

  println(kruskalDS(graph).mkString(", "))

}