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