Codex @codex  0

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
  }
}

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

  private def changeTo(after: Sequence[Slide]): Change = {
    val before = slides
    slides = after
    new Change {
      def undo(): Unit = { slides = before }
      def redo(): Unit = { slides = after }
    }
  }

  def insert(i: Int, x: Slide): Change =
    changeTo(slides.insert(i, x))

  def delete(i: Int): Change =
    changeTo(slides.delete(i))

  def move(from: Int, to: Int): Change = {
    val x = slides.elementAt(from)
    changeTo(slides.delete(from).insert(to, x))
  }
}

newtype List a = List (Int -> Maybe a)

take' :: Int -> List a -> List a
take' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i >= k = Nothing
      | otherwise      = f i

drop' :: Int -> List a -> List a
drop' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i > maxBound - k = Nothing
      | otherwise                = f (i+k)

length' :: List a -> Int
length' (List f) = countFrom 0
  where
    countFrom i = case f i of
                    Nothing -> i
                    Just _  -> countFrom (i+1)

merge' :: Ord a => List a -> List a -> List a
merge' left right
  | null' left  = right
  | null' right = left
  | head' left <= head' right =
      cons' (head' left) (merge' (tail' left) right)
  | otherwise =
      cons' (head' right) (merge' left (tail' right))

mergeSort' :: Ord a => List a -> List a
mergeSort' input =
  let n = length' input
      middle = n `div` 2
  in if n <= 1 then input
     else merge' (mergeSort' (take' middle input))
                 (mergeSort' (drop' middle input))

trait DoubleEndedQueue {
  def isEmpty: Boolean
  def addLeft(x: Int): Unit
  def getLeft(): Int
  def addRight(x: Int): Unit
  def getRight(): Int
}

class DoublyLinkedDoubleEndedQueue extends DoubleEndedQueue {
  private var first: Node = null
  private var last: Node = null

  def isEmpty: Boolean = first == null

  def addLeft(x: Int): Unit = {
    val node = new Node(x, null, first)
    if (first == null) last = node
    else first.prev = node
    first = node
  }

  def addRight(x: Int): Unit = {
    val node = new Node(x, last, null)
    if (last == null) first = node
    else last.next = node
    last = node
  }

  def getLeft(): Int = {
    require(!isEmpty)
    val old = first
    first = old.next
    if (first == null) last = null
    else first.prev = null
    old.next = null
    old.datum
  }

  def getRight(): Int = {
    require(!isEmpty)
    val old = last
    last = old.prev
    if (last == null) first = null
    else last.next = null
    old.prev = null
    old.datum
  }
}

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

def printDestructively(input: Tree): Unit = {
  var root = input
  while (root != null) {
    while (root.left != null) {
      val child = root.left
      root.left = child.right
      child.right = root
      root = child
    }
    println(root.datum)
    root = root.right
  }
}

final class Ones extends Iterator[Int] {
  def hasNext: Boolean = true
  def next(): Int = 1
}

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 if (second.hasNext) second.next()
    else throw new java.util.NoSuchElementException("empty concatenation")
  }
}