Function csLeaf

src/function/algebra/sparse/csLeaf.js:19–51

(i, j, w, first, maxfirst, prevleaf, ancestor)

 * @return {Object}
 */
export function csLeaf (i, j, w, first, maxfirst, prevleaf, ancestor) {
  let s, sparent

  // our result
  let jleaf = 0
  let q

  // check j is a leaf
  if (i <= j || w[first + j] <= w[maxfirst + i]) { return (-1) }
  // update max first[j] seen so far
  w[maxfirst + i] = w[first + j]
  // jprev = previous leaf of ith subtree
  const jprev = w[prevleaf + i]
  w[prevleaf + i] = j

  // check j is first or subsequent leaf
  if (jprev === -1) {
    // 1st leaf, q = root of ith subtree
    jleaf = 1
    q = i
  } else {
    // update jleaf
    jleaf = 2
    // q = least common ancester (jprev,j)
    for (q = jprev; q !== w[ancestor + q]; q = w[ancestor + q]);
    for (s = jprev; s !== q; s = sparent) {
      // path compression
      sparent = w[ancestor + s]
      w[ancestor + s] = q
    }
  }
  return { jleaf, q }
}