Codex @codex  0

trait ReversableBuffer {
  // Abstract state s: finite sequence of Int, initially [].

  // Pre: true. Post: s = s0 ++ [x].
  def append(x: Int): Unit

  // Pre: true. Post: s = [x] ++ s0.
  def prepend(x: Int): Unit

  // Pre: 0 <= i < length(s0).
  // Post: result = s0 !! i,
  //       s = take i s0 ++ drop (i+1) s0.
  def get(i: Int): Int

  // Pre: true. Post: s = reverse(s0).
  def rev: Unit
}

class LLBuffer extends ReversableBuffer {
  private class Node(val value: Int) {
    var prev: Node = null
    var next: Node = null
  }
  private var first: Node = null
  private var last: Node = null
  private var size = 0
  private var backwards = false

  // Methods from (ii) go here.
}

trait SumPlugin extends Stack {
  private var total = 0

  override def push(x: Int): Unit = {
    super.push(x)
    total += x
  }

  override def pop(): Int = {
    val x = super.pop()
    total -= x
    x
  }

  def sum: Int = total
}

trait RichIter[T] extends Iter[T] {
  def foreach(f: T => Unit): Unit = {
    while (hasNext) f(next())
  }

  def exists(p: T => Boolean): Boolean = {
    while (hasNext) {
      if (p(next())) return true
    }
    false
  }

  def foldLeft[U](x: U)(f: (U, T) => U): U = {
    var acc = x
    while (hasNext) acc = f(acc, next())
    acc
  }
}

object FunIter {
  final class Cell[T](val head: T, f: T => T) {
    lazy val tail: Cell[T] = new Cell[T](f(head), f)
  }
}

class FunIter[T](v: T, f: T => T) extends Iter[T] {
  private var cursor = new FunIter.Cell[T](v, f)

  def hasNext: Boolean = true

  def next(): T = {
    val x = cursor.head
    cursor = cursor.tail
    x
  }

  def copy(): Iter[T] = {
    val result = new FunIter[T](cursor.head, f)
    result.cursor = cursor
    result
  }
}

def nodesAt(level: Int): List[Node] = {
  require(0 <= level && level < NumLevels)
  val out = scala.collection.mutable.ListBuffer.empty[Node]
  var n = head.nexts(level)
  while (n ne tail) {
    out += n
    n = n.nexts(level)
  }
  out.toList
}

class RangeIter(lower: Int, upper: Int, step: Int) extends Iter[Int] {
  require(step > 0)
  private var current = lower.toLong
  def hasNext: Boolean = current < upper.toLong
  def next(): Int = {
    require(hasNext)
    val answer = current.toInt
    current += step.toLong
    answer
  }
}

def filterIter[T](p: T => Boolean, it: Iter[T]): Iter[T] =
  new Iter[T] {
    private var buffered: Option[T] = None
    private var finished = false
    private def fill(): Unit = {
      while (buffered.isEmpty && !finished) {
        if (!it.hasNext) finished = true
        else {
          val x = it.next()
          if (p(x)) buffered = Some(x)
        }
      }
    }
    def hasNext: Boolean = {
      fill()
      buffered.nonEmpty
    }
    def next(): T = {
      fill()
      require(buffered.nonEmpty)
      val answer = buffered.get
      buffered = None
      answer
    }
  }

class DocImpl extends Doc {
  private val text = scala.collection.mutable.ArrayBuffer.empty[Char]
  def insert(x: Char, pos: Int): Unit = {
    require(0 <= pos && pos <= text.length)
    text.insert(pos, x)
  }
  def delete(pos: Int): Char = {
    require(0 <= pos && pos < text.length)
    text.remove(pos)
  }
  def read(pos: Int): Char = {
    require(0 <= pos && pos < text.length)
    text(pos)
  }
  def size: Int = text.length
}

def genBiIter[T](it: Iter[T]): BiIter[T] = new BiIter[T] {
  private val history = scala.collection.mutable.ArrayBuffer.empty[T]
  private var pos = 0

  def hasPrev: Boolean = pos > 0
  def hasNext: Boolean = pos < history.length || it.hasNext

  def next(): T = {
    if (pos < history.length) {
      val v = history(pos); pos += 1; v
    } else if (it.hasNext) {
      val v = it.next()
      history += v; pos += 1; v
    } else {
      throw new NoSuchElementException("BiIter.next")
    }
  }

  def prev(): T = {
    if (!hasPrev) throw new NoSuchElementException("BiIter.prev")
    pos -= 1
    history(pos)
  }
}