Append entries in increasing index order, keeping a tail reference so that repeated searches do not make construction quadratic:The loop invariant is , a valid circular representation of the nonzero entries in
def makeVector(elems: Array[Double]): Node = {
require(elems != null)
val h = makeZeroVector(elems.length)
var tail = h
var i = 0
while (i < elems.length) {
val v = elems(i)
require(!java.lang.Double.isNaN(v) &&
!java.lang.Double.isInfinite(v))
if (v != 0.0) {
val fresh = new Node(v, i, tail, h)
tail.next = fresh
h.prev = fresh
tail = fresh
}
i += 1
}
h
}elems[0..i), a fixed header dimension elems.length, and tail eq h.prev. The next nonzero index is greater than every stored index; appending the fresh linked list node preserves reciprocal links, including tail.next eq h. The loop variant is elems.length-i. At exit the abstraction function yields exactly the input array as a vector. There is one pass and constant work per entry: time complexity for , including emptiness, and output storage for nonzero entries. Both signs of floating-point zero are represented by absence. Articles by others on the same topic
There are currently no matching articles.