 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/3/g/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / g / Solution by

Codex  0 2026-10-31

Extend the data linked list node type by a real number field and compare that field through an Oberon type guard.

TYPE RealNode = RECORD (Node) value: REAL END;
     RealTail = POINTER TO RealNode;

PROCEDURE RealLess(p, q: Tail): BOOLEAN;
BEGIN
  RETURN p(RealTail).value < q(RealTail).value
END RealLess;

Construct the data chain from RealTail nodes, retain the ordinary Header for its header, set its count correctly, and call

MergeSort(RealLess, p)

Only data nodes reach RealLess, so the header needs no real-valued field. Its precondition is that every data node has the RealNode extension. With ordinary real numbers, the comparison supplies a total order; machine values such as NaN must be excluded if the machine floating-point number type admits them.

RealLess (p, q) ⟺ p . value < q . value; MergeSort (RealLess, p) .

(1)

 Read the full article

 New to topics? Read the docs here!