Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 3 / g / Solution 2026-10-31
View more
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.
(1)
Read the full article