1 | /**
|
2 | * This function determines if j is a leaf of the ith row subtree.
|
3 | * Consider A(i,j), node j in ith row subtree and return lca(jprev,j)
|
4 | *
|
5 | * @param {Number} i The ith row subtree
|
6 | * @param {Number} j The node to test
|
7 | * @param {Array} w The workspace array
|
8 | * @param {Number} first The index offset within the workspace for the first array
|
9 | * @param {Number} maxfirst The index offset within the workspace for the maxfirst array
|
10 | * @param {Number} prevleaf The index offset within the workspace for the prevleaf array
|
11 | * @param {Number} ancestor The index offset within the workspace for the ancestor array
|
12 | *
|
13 | * @return {Object}
|
14 | *
|
15 | * Reference: http://faculty.cse.tamu.edu/davis/publications.html
|
16 | */
|
17 | export function csLeaf (i, j, w, first, maxfirst, prevleaf, ancestor) {
|
18 | let s, sparent, jprev
|
19 |
|
20 | // our result
|
21 | let jleaf = 0
|
22 | let q
|
23 |
|
24 | // check j is a leaf
|
25 | if (i <= j || w[first + j] <= w[maxfirst + i]) { return (-1) }
|
26 | // update max first[j] seen so far
|
27 | w[maxfirst + i] = w[first + j]
|
28 | // jprev = previous leaf of ith subtree
|
29 | jprev = w[prevleaf + i]
|
30 | w[prevleaf + i] = j
|
31 |
|
32 | // check j is first or subsequent leaf
|
33 | if (jprev === -1) {
|
34 | // 1st leaf, q = root of ith subtree
|
35 | jleaf = 1
|
36 | q = i
|
37 | } else {
|
38 | // update jleaf
|
39 | jleaf = 2
|
40 | // q = least common ancester (jprev,j)
|
41 | for (q = jprev; q !== w[ancestor + q]; q = w[ancestor + q]);
|
42 | for (s = jprev; s !== q; s = sparent) {
|
43 | // path compression
|
44 | sparent = w[ancestor + s]
|
45 | w[ancestor + s] = q
|
46 | }
|
47 | }
|
48 | return {
|
49 | jleaf: jleaf,
|
50 | q: q
|
51 | }
|
52 | }
|