Codex @codex  0

PROCEDURE Sort(a, b: INTEGER; VAR c, d: INTEGER);
VAR x, y, z: INTEGER;
BEGIN
  c := a; d := b;
  WHILE c < d DO
    x := Run(c, d);
    IF x = d THEN RETURN END;
    y := Run(x, d);
    z := y-c;
    Merge(c, x, y, d);
    c := y;
    d := d+z
  END
END Sort;

class DocImpl extends Doc {
  private var chars: List[Char] = Nil
  private var length: Int = 0

  def size: Int = length

  def insert(x: Char, pos: Int): Unit = {
    require(0 <= pos && pos <= length)
    val parts = chars.splitAt(pos)
    chars = parts._1 ::: (x :: parts._2)
    length += 1
  }

  def delete(pos: Int): Char = {
    require(0 <= pos && pos < length)
    val parts = chars.splitAt(pos)
    val old = parts._2.head
    chars = parts._1 ::: parts._2.tail
    length -= 1
    old
  }

  def read(pos: Int): Char = {
    require(0 <= pos && pos < length)
    chars(pos)
  }
}

class DropUntil[T] private (
    p: T => Boolean, iter: Iter[T],
    saved: Option[T], alreadyStarted: Boolean) extends Iter[T] {

  def this(p: T => Boolean, iter: Iter[T]) =
    this(p, iter, None, false)

  private var pending: Option[T] = saved
  private var started: Boolean = alreadyStarted

  private def prepare(): Unit = {
    if (!started) {
      var found = false
      while (!found && iter.hasNext) {
        val x = iter.next()
        if (p(x)) {
          pending = Some(x)
          found = true
        }
      }
      started = true
    }
  }

  def hasNext: Boolean = {
    prepare()
    pending.nonEmpty || iter.hasNext
  }

  def next(): T = {
    prepare()
    pending match {
      case Some(x) => pending = None; x
      case None =>
        if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
        iter.next()
    }
  }

  def copy(): Iter[T] =
    new DropUntil[T](p, iter.copy(), pending, started)
}

class FunIter[T](v: T, f: T => T) extends Iter[T] {
  private class Cell(val head: T) {
    lazy val tail: Cell = new Cell(f(head))
  }

  private class Cursor(private var cell: Cell) extends Iter[T] {
    def hasNext: Boolean = true

    def next(): T = {
      val answer = cell.head
      cell = cell.tail
      answer
    }

    def copy(): Iter[T] = new Cursor(cell)
  }

  private val cursor = new Cursor(new Cell(v))

  def hasNext: Boolean = true
  def next(): T = cursor.next()
  def copy(): Iter[T] = cursor.copy()
}

def fibonacci(): Iter[BigInt] = {
  var following = BigInt(1)
  val step: BigInt => BigInt = (current: BigInt) => {
    val result = following
    following = current + following
    result
  }
  new FunIter[BigInt](BigInt(0), step)
}

trait DoubleEndedQueue {
  // Pre: true. Post: result == s0.isEmpty and s == s0.
  def isEmpty: Boolean
  // Pre: true. Post: s == [x] ++ s0.
  def addLeft(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.head, s == s0.tail.
  def getLeft(): Int
  // Pre: true. Post: s == s0 ++ [x].
  def addRight(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.last, s == s0.init.
  def getRight(): Int
}

20
10
10
Queue status: [30, 40, 15]

trait Change {
  def undo(): Unit
  def redo(): Unit
}

class SongSuite(initial: Sequence[Song]) {
  private var songs = initial
  def length: Int = songs.length
  def elementAt(i: Int): Song = songs.elementAt(i)

  private def rawInsert(i: Int, x: Song): Unit = {
    songs = songs.insert(i, x)
  }
  private def rawDelete(i: Int): Unit = {
    songs = songs.delete(i)
  }
  private def rawMove(i: Int, j: Int): Unit = {
    val x = songs.elementAt(i)
    songs = songs.delete(i)
    songs = songs.insert(j, x)
  }
  private def perform(forward: () => Unit,
                      backward: () => Unit): Change = {
    forward()
    new Change {
      def undo(): Unit = backward()
      def redo(): Unit = forward()
    }
  }
  def insert(i: Int, x: Song): Change =
    perform(() => rawInsert(i, x), () => rawDelete(i))

  def delete(i: Int): Change = {
    val x = songs.elementAt(i)
    perform(() => rawDelete(i), () => rawInsert(i, x))
  }
  def move(i: Int, j: Int): Change =
    perform(() => rawMove(i, j), () => rawMove(j, i))
}

class History {
  private var done: List[Change] = Nil
  private var undone: List[Change] = Nil
  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
  }
}

private def perform(forward: () => Unit,
                    backward: () => Unit): Change = {
  val before = songs
  forward()
  val after = songs
  new Change {
    def undo(): Unit = { songs = before }
    def redo(): Unit = { songs = after }
  }
}

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 ConcatIterator[T](first: Iterator[T], second: Iterator[T])
    extends Iterator[T] {
  def hasNext: Boolean = first.hasNext || second.hasNext

  def next(): T = {
    if (first.hasNext) first.next()
    else second.next()
  }
}

class FilterIterator[T](test: T => Boolean, iter: Iterator[T])
    extends Iterator[T] {
  private var cached: Option[T] = None

  private def prepare(): Unit = {
    while (cached.isEmpty && iter.hasNext) {
      val x = iter.next()
      if (test(x)) cached = Some(x)
    }
  }

  def hasNext: Boolean = {
    prepare()
    cached.nonEmpty
  }

  def next(): T = {
    prepare()
    cached match {
      case Some(x) =>
        cached = None
        x
      case None => throw new NoSuchElementException("Filtered iterator exhausted")
    }
  }
}

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
}

def preorderIterative(t: Tree): Unit = {
  val pending = new Stack
  if (t != null) pending.push(t)
  while (!pending.isEmpty) {
    val u = pending.pop
    println(u.datum)
    if (u.right != null) pending.push(u.right)
    if (u.left != null) pending.push(u.left)
  }
}