csLeaf.js (1659B)
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 var s, sparent; // our result 19 20 var jleaf = 0; 21 var q; // check j is a leaf 22 23 if (i <= j || w[first + j] <= w[maxfirst + i]) { 24 return -1; 25 } // update max first[j] seen so far 26 27 28 w[maxfirst + i] = w[first + j]; // jprev = previous leaf of ith subtree 29 30 var jprev = w[prevleaf + i]; 31 w[prevleaf + i] = j; // check j is first or subsequent leaf 32 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; // q = least common ancester (jprev,j) 40 41 for (q = jprev; q !== w[ancestor + q]; q = w[ancestor + q]) { 42 ; 43 } 44 45 for (s = jprev; s !== q; s = sparent) { 46 // path compression 47 sparent = w[ancestor + s]; 48 w[ancestor + s] = q; 49 } 50 } 51 52 return { 53 jleaf: jleaf, 54 q: q 55 }; 56 }