package kapitel_08

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

import scala.collection.mutable.ListBuffer
import scala.util.Sorting

object AuD_08_06_KnapsackDomi_App extends App {

  case class Item(name: String, gewicht: Int, wert: Int)

  def GetDominants(L: Array[List[Item]]): List[List[Item]] = {

    //sortiere L absteigend nach dem Wert
    Sorting.quickSort[List[Item]](L)(
      (a:List[Item], b:List[Item]) => b.map(_.wert).sum - a.map(_.wert).sum)

    //sortiere L stabil aufsteigend nach dem Gewicht
    Sorting.stableSort[List[Item]](L)(
      (a:List[Item], b:List[Item]) => a.map(_.gewicht).sum - b.map(_.gewicht).sum)

    var combi = L(0)
    val D = new ListBuffer[List[Item]]
    D += combi
    for (l <- L.drop(1)) {
      if (l.map(_.wert).sum > combi.map(_.wert).sum) {
        combi = l
        D += combi
      }
    }
    D.toList
  }

  def allSubLists[A](lst: List[A]): List[List[A]] = lst match {
    case Nil =>
      List(Nil)
    case head :: tail =>
      for (s <- allSubLists(tail);
           b <- List(List(head), Nil)
           ) yield s ++ b
  }

  val items = List[Item](Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100))

  /*
   * Bei einer Tragkraft von 20 kg dominieren Computer, Vase und Uhr.
   */
  GetDominants(allSubLists(items).toArray).foreach( l => {
    print(s"[${l.map(_.name).mkString(",")}] ")
    println(s" wert: ${l.map(_.wert).sum} gewicht: ${l.map(_.gewicht).sum}")
  })


  def KnapsackDomi(M: List[Item], T: Int): List[Item] = {

    def GetDominants(L: Array[List[Item]]): List[List[Item]] = {
      Sorting.quickSort[List[Item]](L)(
        (a:List[Item], b:List[Item]) => b.map(_.wert).sum - a.map(_.wert).sum)
      Sorting.stableSort[List[Item]](L)(
        (a:List[Item], b:List[Item]) => a.map(_.gewicht).sum - b.map(_.gewicht).sum)
      var combi = L(0)
      val D = new ListBuffer[List[Item]]
      D += combi
      for (l <- L.drop(1)) {
        if (l.map(_.wert).sum > combi.map(_.wert).sum) {
          combi = l
          D += combi
        }
      }
      D.toList
    }

    var D: List[List[Item]] = List(Nil)
    for (mi <- M) {
      val L = new ListBuffer[List[Item]]
      for (combi <- D) {
        L += combi
        if (combi.map(_.gewicht).sum + mi.gewicht <= T) {
          L += mi :: combi
        }
      }
      D = GetDominants(L.toArray)
    }
    println(D)
    D.last
  }

  val items1 = List[Item](Item("A", 7, 42), Item("B", 3, 12), Item("C", 4, 40), Item("D", 5, 25))
  val items2 = List[Item](Item("Goldkorn", 1, 10), Item("Silberbarren", 200, 500))
  val items3 = List[Item](Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100))

  val selection1 = KnapsackDomi(items1, 10)
  val selection2 = KnapsackDomi(items2, 200)
  val selection3 = KnapsackDomi(items3, 20)

  println("1: " + selection1.mkString(", "))
  println("2: " + selection2.mkString(", "))
  println("3: " + selection3.mkString(", "))

}