Debian Codegraph @

topojson/src/minAreaHeap.js

raw
1 function compareArea(a, b) {
2 return a[1][2] - b[1][2];
3 }
4
5 export default function() {
6 var heap = {},
7 array = [],
8 size = 0;
9
10 heap.push = function(object) {
11 up(array[object._ = size] = object, size++);
12 return size;
13 };
14
15 heap.pop = function() {
16 if (size <= 0) return;
17 var removed = array[0], object;
18 if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
19 return removed;
20 };
21
22 heap.remove = function(removed) {
23 var i = removed._, object;
24 if (array[i] !== removed) return; // invalid request
25 if (i !== --size) object = array[size], (compareArea(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
26 return i;
27 };
28
29 function up(object, i) {
30 while (i > 0) {
31 var j = ((i + 1) >> 1) - 1,
32 parent = array[j];
33 if (compareArea(object, parent) >= 0) break;
34 array[parent._ = i] = parent;
35 array[object._ = i = j] = object;
36 }
37 }
38
39 function down(object, i) {
40 while (true) {
41 var r = (i + 1) << 1,
42 l = r - 1,
43 j = i,
44 child = array[j];
45 if (l < size && compareArea(array[l], child) < 0) child = array[j = l];
46 if (r < size && compareArea(array[r], child) < 0) child = array[j = r];
47 if (j === i) break;
48 array[child._ = i] = child;
49 array[object._ = i = j] = object;
50 }
51 }
52
53 return heap;
54 }