Codex @codex  0

S(A, l, r):
    require integer indices with 0 <= l <= r <= length(A)
    size = r - l
    if size == 0:
        return 0
    if size == 1:
        return A[l]
    middle = l + floor(size / 2)
    left_sum = S(A, l, middle)
    right_sum = S(A, middle, r)
    return left_sum + right_sum

F(n):
    require n is an integer and n >= 0
    if n == 0:
        return 1
    child_result = F(n - 1)
    return n * child_result

CONST MaxForks = 100000;
TYPE Tree = INTEGER;
     Node = RECORD left, right: Tree END;
     Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
    used: INTEGER;

PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
  ASSERT(used < MaxForks);
  nodes[used].left := left; nodes[used].right := right;
  INC(used);
  RETURN used
END NewFork;

PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
                   VAR count: INTEGER);
  PROCEDURE Visit(p: Tree);
  BEGIN
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      Visit(nodes[p-1].left); Visit(nodes[p-1].right)
    END
  END Visit;
BEGIN
  count := 0; Visit(t)
END Preorder;

PROCEDURE Decode(VAR code: ARRAY OF INTEGER;
                 VAR pos: INTEGER): Tree;
VAR marker: INTEGER; left, right: Tree;
BEGIN
  marker := code[pos]; INC(pos);
  IF marker = 0 THEN RETURN 0 END;
  ASSERT(marker = 1);
  left := Decode(code, pos);
  right := Decode(code, pos);
  RETURN NewFork(left, right)
END Decode;

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;

TYPE Visit = PROCEDURE(x: INTEGER);

PROCEDURE Inorder(t: Tree; p: Visit);
BEGIN
  IF t # NIL THEN
    Inorder(t.left, p);
    p(t.label);
    Inorder(t.right, p)
  END
END Inorder;

PROCEDURE MakeTree(VAR u: ARRAY OF INTEGER;
                   a, b: INTEGER): Tree;
VAR m: INTEGER; t: Tree;
BEGIN
  IF a = b THEN RETURN NIL END;
  m := a + (b-a) DIV 2;
  NEW(t);
  t.label := u[m];
  t.left := MakeTree(u, a, m);
  t.right := MakeTree(u, m+1, b);
  RETURN t
END MakeTree;

VAR part: ARRAY MaxParts OF INTEGER;

PROCEDURE Emit(i, r, len: INTEGER);
VAR j: INTEGER;
BEGIN
  IF r = 0 THEN
    j := 0;
    WHILE j < len DO
      IF j > 0 THEN Out.Char("+") END;
      Out.Int(part[j], 0); j := j+1
    END;
    Out.Ln
  ELSIF i > 0 THEN
    IF i <= r THEN
      part[len] := i;
      Emit(i, r-i, len+1)
    END;
    Emit(i-1, r, len)
  END
END Emit;

PROCEDURE PrintPartitions(n: INTEGER);
BEGIN
  Emit(n, n, 0)
END PrintPartitions;

PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
  NEW(t); t.terminal := FALSE; c := 0;
  WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;

PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
  IF t = NIL THEN Make(t) END;
  IF s[i] = 0X THEN
    t.terminal := TRUE
  ELSE
    AddTail(t.child[Index(s[i])], s, i+1)
  END
END AddTail;

PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
  AddTail(t, s, 0)
END Add;

def selectIterative(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  var low = l
  var high = r
  var rank = k
  while (high - low > 1) {
    val p = partition(low, high)
    val pivotRank = p - low
    if (rank == pivotRank) return a(p)
    if (rank < pivotRank) high = p
    else {
      rank -= pivotRank + 1
      low = p + 1
    }
  }
  a(low)
}

def preorderRecursive(t: Tree): Unit = {
  if (t != null) {
    println(t.datum)
    preorderRecursive(t.left)
    preorderRecursive(t.right)
  }
}