topoline = function (series) {
const E_insert = 0;
const E_left = 1;
const E_right = 2;
const E_merge = 3;
const n = series.length;
const tree = new Int32Array(n).fill(-1);
const features = [];
let k = 0;
const order = d3.sort(
d3.range(0, tree.length),
(i) => series[i],
(i) => i
);
let event;
for (const i of order) {
const left = tree[i - 1] ?? tree[i];
const right = tree[i + 1] ?? tree[i];
if (left === -1 && right === -1) {
tree[i] = i;
event = E_insert;
} else if (left === -1) {
tree[i] = right;
event = E_right;
} else if (right === -1) {
tree[i] = left;
event = E_left;
} else {
let [a, b] = d3.sort(
[tree[left], tree[right]],
(i) => series[i],
(i) => i
);
if (i === order[order.length - 1]) b = a;
features.push({
low: b,
high: i,
persistence: series[i] - series[b],
error: error(b, i)
});
for (let j = i - 1; tree[j] === b; j--) tree[j] = a;
for (let j = i + 1; tree[j] === b; j++) tree[j] = a;
tree[i] = a;
event = E_merge;
}
k++;
}
if (event === E_left || event === E_right) {
const low = order[0];
const high = order.pop();
features.push({
low,
high,
persistence: series[high] - series[low],
error: error(low, high)
});
}
return d3.sort(features, (d) => -d.persistence);
function error(b, i) {
return d3.sum(d3.range(...d3.extent([i, b])), (k) =>
Math.abs(
(series[b] - series[i]) * ((k - i) / (b - i)) - (series[k] - series[i])
)
);
}
}