Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 4 / b / i

Within the sparse-vector implementation, use:

class Node(var value: Double, val index: Int,
           var prev: Node, var next: Node)

The header's index is the fixed vector dimension, so it need not change after construction. For a data node it is the coordinate index. The representation invariant requires a finite simple cycle through the header, reciprocal predecessor/successor links, strictly increasing indices in the forward data-node traversal, indices in $[0,dimension)$, and a nonzero value at every data node. The header's value is ignored. The abstraction function assigns stored values to their indices and zero to all missing coordinates.

The numerical code below takes entries to be finite Double values. Excluding NaN and infinities makes the relationship to a real sparse vector explicit; arithmetic results still follow ordinary floating-point arithmetic.