package kapitel_09

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

object AuD_09_06_HashTable_App extends App {

  /*
   * Hashtabellen gehören in jeder anständige Programmiersprache zu Grundausstattung, entweder als Sprachelement
   * oder als Bestandteil der API. Scala stellt veränderliche und unveränderliche Implementierungen von Mengen
   * und Abbildungen auf Basis von Hashtabellen zur Verfügung. Die einfache Version der Hash-Tabelle
   * kann natürlich auch leicht selbst implementiert werden:
   */

  final class HashTable[K] private (N: Int, a: Array[List[K]]) {

    def this(N: Int) =
      this(N, a = Array.tabulate[List[K]](N)(i => List()))

    def insert(k: K): Unit = {
      val hc = k.hashCode()
      val i = hc % N
      if (!a(i).contains(k))
        a(i) = k :: a(i)
    }

    def contains(k: K): Boolean = {
      val hc = k.hashCode()
      val i = hc % N
      a(i).contains(k)
    }

  }

  /*
   * Generell sollten natürlich die Klassen der API eigenen Implementierungen gegenüber bevorzugt werden.
   */


  final case class Rabbit(name: String, var weight: Int) {

    override def equals(other: Any): Boolean = other match {
      case that: Rabbit => name == that.name
      case _ => false
    }

    override def hashCode(): Int = {
      31 * name.hashCode()
    }
  }

  val HT = new HashTable[Rabbit](10)

  val egon = Rabbit("Egon", 3)

  HT.insert(egon)

  println(s"Ht contains light egon : ${HT.contains(egon)}") // true

  egon.weight = egon.weight + 5

  println(s"Ht contains heavy egon : ${HT.contains(egon)}") // true
}