Codex @codex  0

trait Queue[A] {
  // State q: finite sequence of A; initially [].
  // Pre: length(q) < Int.MaxValue. Post: q = q0 ++ [x].
  def enqueue(x: A): Unit

  // Pre: q is nonempty. Post: return head(q0); q = tail(q0).
  def dequeue(): A

  // Post: q = [].
  def clear(): Unit

  // Post: q unchanged; return q.isEmpty.
  def isEmpty: Boolean

  // Post: q unchanged; return length(q).
  def length: Int
}

private var first: QueueNode = null
private var last: QueueNode = null
private var size = 0

class ListQueue extends Queue[Int] {
  private var first: QueueNode = null
  private var last: QueueNode = null
  private var size = 0

  def enqueue(x: Int): Unit = {
    require(size < Int.MaxValue, "queue size limit")
    val fresh = new QueueNode(x, null)
    if (last == null) first = fresh
    else last.next = fresh
    last = fresh
    size += 1
  }

  def dequeue(): Int = {
    require(first != null, "empty queue")
    val answer = first.value
    first = first.next
    size -= 1
    if (first == null) last = null
    answer
  }

  def clear(): Unit = {
    first = null
    last = null
    size = 0
  }

  def isEmpty: Boolean = size == 0
  def length: Int = size
}

class DocImp extends Doc {
  private val data = scala.collection.mutable.ArrayBuffer.empty[Char]

  def insert(pos: Int, ch: Char): Unit = {
    require(0 <= pos && pos <= data.length)
    require(data.length < Int.MaxValue)
    data.insert(pos, ch)
  }

  def delete(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data.remove(pos)
  }

  def apply(pos: Int): Char = {
    require(0 <= pos && pos < data.length)
    data(pos)
  }

  def length: Int = data.length
}

def map[T, U](f: T => U, it: Iter[T]): Iter[U] = new Iter[U] {
  def hasNext: Boolean = it.hasNext
  def next(): U = {
    require(it.hasNext, "empty iterator")
    f(it.next())
  }
}

def map[T, U](f: T => U, cur: Cursor[T]): Cursor[U] =
  asCursor(map(f, asIter(cur)))

def asIter[T](cur: Cursor[T]): Iter[T] = new Iter[T] {
  def hasNext: Boolean = cur.hasCurrent
  def next(): T = {
    require(cur.hasCurrent, "empty iterator")
    val answer = cur.current
    cur.next()
    answer
  }
}

def asCursor[T](it: Iter[T]): Cursor[T] = new Cursor[T] {
  private var cached: Option[T] = None

  def hasCurrent: Boolean = cached.nonEmpty || it.hasNext

  def current: T = {
    if (cached.isEmpty) {
      require(it.hasNext, "empty cursor")
      cached = Some(it.next())
    }
    cached.get
  }

  def next(): Unit = {
    if (cached.nonEmpty) cached = None
    else {
      require(it.hasNext, "empty cursor")
      it.next()
      ()
    }
  }
}

def unitIter[T](t: T): Iter[T] = new Iter[T] {
  private var available = true
  def hasNext: Boolean = available
  def next(): T = {
    require(available, "empty iterator")
    available = false
    t
  }
}

def unitCursor[T](t: T): Cursor[T] = new Cursor[T] {
  private var available = true
  def hasCurrent: Boolean = available
  def current: T = {
    require(available, "empty cursor")
    t
  }
  def next(): Unit = {
    require(available, "empty cursor")
    available = false
  }
}

def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
  def hasNext: Boolean = t.hasNext || u.hasNext
  def next(): T = {
    if (t.hasNext) t.next()
    else {
      require(u.hasNext, "empty iterator")
      u.next()
    }
  }
}

def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
  def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
  def current: T = {
    if (t.hasCurrent) t.current
    else {
      require(u.hasCurrent, "empty cursor")
      u.current
    }
  }
  def next(): Unit = {
    if (t.hasCurrent) t.next()
    else {
      require(u.hasCurrent, "empty cursor")
      u.next()
    }
  }
}

def reverseBook(): Unit = {
  var prev: Node = null
  var cur = list
  while (cur != null) {
    val following = cur.next
    cur.next = prev
    prev = cur
    cur = following
  }
  list = prev
}