package kapitel_04

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_04_03_RandomAccessList_App extends App {

  object RaList {

    case class Cell(var content: Int, var next: Cell)

    var head: Cell = _

    def lookUp(index: Int): Int = {
      var i = 0
      var pos = head
      while (i < index && pos != null) {
        i = i + 1
        pos = pos.next
      }
      if (pos != null)
        pos.content
      else
        throw new NoSuchElementException
    }

    def InsertAtPos(x: Int, index: Int): Unit = {
      val newCellPtr = Cell(x, null)
      var prev: Cell = null
      var pos: Cell = head
      var i = 0
      while (i < index && pos != null) {
        prev = pos
        pos = pos.next
        i = i+1
      }
      if (pos == null && i < index) {
        throw new IllegalArgumentException(s"no position $index in list")
      }
      newCellPtr.next = pos
      if (prev == null)
        head = newCellPtr
      else
        prev.next = newCellPtr
    }

  }

  for (x <- 0 to 10) {
    RaList.InsertAtPos(10-x, 0)
  }

  for (i <- 0 to 10) {
    println(s"$i : ${RaList.lookUp(i)}")
  }

  RaList.InsertAtPos(55, 5)

  for (i <- 0 to 11) {
    println(s"$i : ${RaList.lookUp(i)}")
  }

  RaList.InsertAtPos(111, 11)

  for (i <- 0 to 12) {
    println(s"$i : ${RaList.lookUp(i)}")
  }
}