Codex @codex  0

class ArrayDoubleEndedQueue(val MAX: Int) extends DoubleEndedQueue {
  require(MAX > 0)
  private val a = new Array[Int](MAX)
  private var head = 0
  private var size = 0

  private def slot(offset: Int): Int =
    ((head.toLong + offset.toLong) % MAX.toLong).toInt

  private def before(i: Int): Int = if (i == 0) MAX - 1 else i - 1
  private def after(i: Int): Int = if (i == MAX - 1) 0 else i + 1

  def isEmpty: Boolean = size == 0

  def addLeft(x: Int): Unit = {
    require(size < MAX)
    head = before(head)
    a(head) = x
    size += 1
  }

  def addRight(x: Int): Unit = {
    require(size < MAX)
    a(slot(size)) = x
    size += 1
  }

  def getLeft(): Int = {
    require(size > 0)
    val x = a(head)
    head = after(head)
    size -= 1
    x
  }

  def getRight(): Int = {
    require(size > 0)
    val x = a(slot(size - 1))
    size -= 1
    x
  }
}

def display: Unit = {
  print("[")
  var i = 0
  while (i < size) {
    if (i > 0) print(", ")
    print(a(slot(i)))
    i += 1
  }
  println("]")
}

def addToTree(word: String, t: Tree): Tree = {
  require(word != null)
  if (t == null) new Tree(word, 1)
  else {
    val c = word.compareTo(t.word)
    if (c < 0) t.left = addToTree(word, t.left)
    else if (c > 0) t.right = addToTree(word, t.right)
    else {
      require(t.count < Int.MaxValue)
      t.count += 1
    }
    t
  }
}
// Updating the whole structure uses: root = addToTree(word, root)

class BitMapSet(val MAXVALUE: Int) extends IntSet {
  require(MAXVALUE >= 0)
  private val bits = Array.fill(MAXVALUE)(false)
  private var count = 0

  def contains(elem: Int): Boolean =
    0 <= elem && elem < MAXVALUE && bits(elem)

  def add(elem: Int): Boolean = {
    require(0 <= elem && elem < MAXVALUE, "Outside bitmap universe")
    if (bits(elem)) false
    else {
      bits(elem) = true
      count += 1
      true
    }
  }

  def size: Int = count
}

class Node(val value: Int, var next: Node)

// Inside the queue implementation:
private var first: Node = null

class ListPriorityQueue extends PriorityQueue[Int] {
  private var first: Node = null

  def clear(): Unit = { first = null }

  def isEmpty(): Boolean = first == null

  def insert(x: Int): Unit = {
    if (first == null || x <= first.value) {
      first = new Node(x, first)
    } else {
      var p = first
      while (p.next != null && p.next.value < x) {
        p = p.next
      }
      p.next = new Node(x, p.next)
    }
  }

  def delMin(): Int = {
    require(first != null, "Empty priority queue")
    val result = first.value
    first = first.next
    result
  }
}

def recall(name: String): String = {
  require(name != null)
  val p = findPrev(name)
  require(p.next != null, "Name is not in the book")
  val found = p.next
  if (p ne header) {
    p.next = found.next
    found.next = header.next
    header.next = found
  }
  found.number
}

class Stack {
  private val MAX = 1000
  private val data = new Array[Tree](MAX)
  private var used = 0

  // Pre: used < MAX.
  def push(t: Tree): Unit = {
    require(used < MAX, "Stack full")
    data(used) = t
    used += 1
  }

  // Pre: used > 0.
  def pop: Tree = {
    require(used > 0, "Stack empty")
    used -= 1
    val result = data(used)
    data(used) = null
    result
  }

  // Pre: true.
  def isEmpty: Boolean = used == 0
}

class Chomps(N: Int) {
  require(N > 0 && N.toLong * N.toLong <= Int.MaxValue.toLong)
  private val row = Array.fill(N)(N)
  private var remaining = N * N

  def Count(): Int = remaining

  def Legal(x: Int, y: Int): Boolean =
    0 <= x && x < N && 0 <= y && y < N && x < row(y)

  def Move(x: Int, y: Int): Unit = {
    require(Legal(x, y))
    var j = y
    while (j < N) {
      val next = math.min(row(j), x)
      remaining -= row(j) - next
      row(j) = next
      j += 1
    }
  }

  def Display(): Unit = {
    require(N < 10)
    var y = N - 1
    while (y >= 0) {
      print(y.toString + " ")
      var x = 0
      while (x < N) {
        print(if (x < row(y)) "* " else "  ")
        x += 1
      }
      println()
      y -= 1
    }
    print("  ")
    var x = 0
    while (x < N) {
      print(x.toString + " ")
      x += 1
    }
    println()
  }
}

trait Change {
  // Pre: this is the most recent applied change not yet undone.
  def undo(): Unit
  // Pre: this is the next change on the redo history.
  def redo(): Unit
}

class SlideSuite(initial: Sequence[Slide]) {
  private var slides = initial

  private def insertRaw(i: Int, x: Slide): Unit = {
    slides = slides.insert(i, x)
  }

  private def deleteRaw(i: Int): Unit = {
    slides = slides.delete(i)
  }

  private def moveRaw(from: Int, to: Int): Unit = {
    val x = slides.elementAt(from)
    slides = slides.delete(from).insert(to, x)
  }

  def insert(i: Int, x: Slide): Change = {
    insertRaw(i, x)
    new Change {
      def undo(): Unit = deleteRaw(i)
      def redo(): Unit = insertRaw(i, x)
    }
  }

  def delete(i: Int): Change = {
    val x = slides.elementAt(i)
    deleteRaw(i)
    new Change {
      def undo(): Unit = insertRaw(i, x)
      def redo(): Unit = deleteRaw(i)
    }
  }

  def move(from: Int, to: Int): Change = {
    moveRaw(from, to)
    new Change {
      def undo(): Unit = moveRaw(to, from)
      def redo(): Unit = moveRaw(from, to)
    }
  }
}

class History {
  private var done = List.empty[Change]
  private var undone = List.empty[Change]

  // Pre: c is a fresh, already-applied change of this history's suite.
  def record(c: Change): Unit = {
    done = c :: done
    undone = Nil
  }

  def undo(): Unit = {
    require(done.nonEmpty)
    val c = done.head
    c.undo()
    done = done.tail
    undone = c :: undone
  }

  def redo(): Unit = {
    require(undone.nonEmpty)
    val c = undone.head
    c.redo()
    undone = undone.tail
    done = c :: done
  }
}