package kapitel_12

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

import scala.language.implicitConversions

object AuD_12_03_BinarySearchLeftRight_App extends App {

  /**
   * Binaere Suche in einem Array nach dem linken Rand des Vorkommens eines Wertes
   * @param a  sortiertes Array mit n Elementen
   * @param x  gesuchter Wert
   * @tparam A Vergleichbarer Typ der Arrayelemente
   * @return   Kleinste Position von x (x ist enthalten)
   *           oder (x ist nicht enthalten) kleinste Position des ersten groesseren Wertes
   *           (es gibt einen groesseren Wert im Array), oder kleinste Indexposition
   *           ausserhalb des Arrays
   */
  def BinarySearchLeft[A](a: Array[A], x: A)(implicit ordering: Ordering[A] ): Int = {
    implicit def toOrdered(a:A): Ordered[A] = Ordered.orderingToOrdered(a)
    var l = 0
    var r = a.length-1
    while (l <= r) {
      // Pruefung der Schleifeninvariante:
      assert( !(0 until l).toList.exists( i => a(i) >= x ))
      assert( !(r+1 until a.length).toList.exists( i => a(i) < x ))

      val m = (l + r)/2
      if (x <= a(m))
        r = m-1
      else
        l = m+1
    }
    l
  }

  /**
   * Binaere Suche in einem Array nach dem rechten Rand des Vorkommens eines Wertes
   * @param a  sortiertes Array mit n Elementen
   * @param x  gesuchter Wert
   * @tparam A Vergleichbarer Typ der Arrayelemente
   * @return   Groesste Position von x (x ist enthalten)
   *           oder (x ist nicht enthalten) groesste Position des letzten kleineren Wertes
   *           (es gibt einen kleineren Wert im Array), oder -1
   */
  def BinarySearchRight[A](a: Array[A], x: A)(implicit ordering: Ordering[A] ): Int = {
    implicit def toOrdered(a:A): Ordered[A] = Ordered.orderingToOrdered(a)
    var l = 0
    var r = a.length-1
    while (l <= r) {
      val m = (l + r)/2
      if (x < a(m))
        r = m-1
      else
        l = m+1
    }
    r
  }

  val a: Array[Int] = Array(0, 3, 3, 5, 5, 5, 5, 8, 8, 12)

  for (x <- -2 to 14) {
    println(s"$x L =>\t${BinarySearchLeft(a, x)}\tR => ${BinarySearchRight(a, x)}")
  }
}