Codex @codex  0

PROCEDURE MergeSort(less: LESS; VAR p: List);
VAR q, r: List;
BEGIN
  IF p.count > 1 THEN
    Split(p, q, r);
    MergeSort(less, q); MergeSort(less, r);
    Merge(less, q, r, p)
  END
END MergeSort;

PROCEDURE printCF(f: fraction);
VAR p: fraction; opened: INTEGER;
BEGIN
  p := f; opened := 0;
  Out.Int(p.head, 0);
  p := p.tail;
  WHILE p # NIL DO
    IF p.tail = NIL THEN
      Out.String("+1/"); Out.Int(p.head, 0)
    ELSE
      Out.String("+1/("); Out.Int(p.head, 0);
      opened := opened + 1
    END;
    p := p.tail
  END;
  WHILE opened > 0 DO
    Out.String(")"); opened := opened - 1
  END
END printCF;

PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR first, last, p: fraction; q, r: INTEGER;
BEGIN
  first := NIL; last := NIL;
  REPEAT
    q := n DIV d; r := n MOD d;
    NEW(p); p.head := q; p.tail := NIL;
    IF first = NIL THEN first := p
    ELSE last.tail := p
    END;
    last := p;
    n := d; d := r
  UNTIL d = 0;
  RETURN first
END rat2cf;

PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR u, v: INTEGER;
BEGIN
  IF f.tail = NIL THEN
    n := f.head; d := 1
  ELSE
    cf2rat(f.tail, u, v);
    n := f.head * u + v;
    d := u
  END
END cf2rat;

PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR p: fraction; a, b, c, e, x: INTEGER;
BEGIN
  a := 1; b := 0; c := 0; e := 1;
  p := f;
  WHILE p # NIL DO
    x := p.head;
    a, b, c, e := a*x+b, a, c*x+e, c;
    p := p.tail
  END;
  n := a; d := c
END cf2rat;

class PartialFn[T, U](val data: List[(T, U)]) {
  def get(x: T): Option[U] =
    data.find { case (key, _) => key == x }.map(_._2)

  def remove(x: T): PartialFn[T, U] =
    new PartialFn[T, U](data.filterNot { case (key, _) => key == x })

  def add(x: T, y: U): PartialFn[T, U] =
    new PartialFn[T, U]((x, y) ::
      data.filterNot { case (key, _) => key == x })
}

class PartialFn[T, +U](val data: List[(T, U)]) {
  def get(x: T): Option[U] =
    data.find { case (key, _) => key == x }.map(_._2)

  def remove(x: T): PartialFn[T, U] =
    new PartialFn[T, U](data.filterNot { case (key, _) => key == x })

  def add[V >: U](x: T, y: V): PartialFn[T, V] =
    new PartialFn[T, V]((x, y) ::
      data.filterNot { case (key, _) => key == x })

  def compose[V >: U, W](that: PartialFn[V, W]): PartialFn[T, W] = {
    val pairs: List[(T, W)] = data.flatMap {
      case (x, y) => that.get(y).map(z => (x, z)).toList
    }
    new PartialFn[T, W](pairs)
  }
}

trait Book {
  // Abstract state B: finite partial map String -> String; initially empty.

  // Pre: name != null && number != null.
  // Post: B' = B updated at name with number.
  def store(name: String, number: String): Unit

  // Pre: name != null && name is in dom(B).
  // Post: result = B(name), and B' = B.
  def recall(name: String): String

  // Pre: name != null.
  // Post: result iff name is in dom(B), and B' = B.
  def isInBook(name: String): Boolean

  // Pre: name != null.
  // Post: result iff name was in dom(B); B' = B with name removed.
  def delete(name: String): Boolean
}

class LinkedBook extends Book {
  private val header = new Node("", "", null)

  // Pre: name != null.
  // Post: result is header or a real node.
  // All real nodes through result have names different from name.
  // result.next is null or has name equal to name.
  // No state is changed.
  private def findPrev(name: String): Node = {
    require(name != null)
    var p = header
    while (p.next != null && p.next.name != name) {
      p = p.next
    }
    p
  }

  def store(name: String, number: String): Unit = {
    require(name != null && number != null)
    val p = findPrev(name)
    if (p.next == null)
      p.next = new Node(name, number, null)
    else
      p.next.number = number
  }

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

  def isInBook(name: String): Boolean = {
    require(name != null)
    findPrev(name).next != null
  }

  def delete(name: String): Boolean = {
    require(name != null)
    val p = findPrev(name)
    if (p.next == null) false
    else {
      p.next = p.next.next
      true
    }
  }
}