Fix LIS bug

[pygy]

The lis function has a bug when the first item is new.

Currently, lis([-1, 1]) returns [0, 1] instead of [1]. Actually, an initial -1 always results in an extra 0.

This may not matter for ivi, but your repo is as far as I'm concerned the canonical LIS implementation in JS, and having at least this PR here lets me document the problem for me and probably others.

I went for !(i === 1 && a[0] === -1) rather than i !== 1 || a[0] !== -1 for clarity, not sure if one is faster than the other.

See here for a live demo with a few tests (edit: tweaked for clarity).

[pygy]

As an alternative, if you don't need this fixed for ivi, a source comment about the quirk could be nice.

I can change this PR accordingly if you want.

Edit: It may be less costly (fewer total branches) to do the check at the end of the function, and to shift the first value. This is assuming that shift bumps the array pointer rather than doing an O(N) copy operation.

Edit 2: Well, this runs deeper than I thought... Even with the fixed version, lis([-1, -1, 1]) returns an extra 0. Working on a complete fix.

Edit 3: got it.

The "buggy" version has the shift solution commented out, if you uncomment it also solves the whole problem.

What fix do you prefer, if any?

Edit 4: Provided Array.prototype.shift is O(N) in Safari, something along the "fixed" version in the demo is probably the way to go. There's no point in caching the a[0] !== -1 test, as it will only be evaluated once because of shortcut semantics.

[localvoid]

Hi, good catch. I am definitely had no idea that this algorithm has such behavior. Reconciliation algorithm isn't affected by this bug, but I agree that it is important to fix it.

What you think about this solution?

  // skip -1 values at the start
  for (; a[i] === -1; ++i) {}
  result[0] = i++;

One caveat is that it won't work with input array that contains only -1 values.

Also, since we don't need LIS indices in the reconciliation algo, instead of returning indices, we can mutate input array and assign -2 value to all positions that are part of LIS. Reconciliation algo should be slightly simpler with such change.

function lis(a) {
  const p = a.slice();
  const result = a.slice();
  let n = 0;
  let i = 0;
  let k;
  let u;
  let v;
  let j;

  // input array should always have at least one non-negative value
  for (; a[i] === -1; ++i) {}

  result[0] = i++;
  for (; i < a.length; ++i) {
    k = a[i];
    if (k > -1) {
      j = result[n];
      if (a[j] < k) {
        p[i] = j;
        result[++n] = i;
      } else {
        u = 0;
        v = n;

        while (u < v) {
          j = (u + v) >> 1;
          if (a[result[j]] < k) {
            u = j + 1;
          } else {
            v = j;
          }
        }

        if (k < a[result[u]]) {
          if (u > 0) {
            p[i] = result[u - 1];
          }
          result[u] = i;
        }
      }
    }
  }

  // mutate input array and assign `-2` to all positions that are part of LIS
  v = result[n];
  while (n-- >= 0) {
    a[v] = -2;
    v = p[v];
  }
}

[pygy]

I'd say, go with whatever fix makes the most sense for ivi, and document the quirks, if any?

I don't think the -2 trick would work for what I do (I'm using the LIS indices to look for stable nodes while rendering/inserting new ones top-down), but the other fix you suggested would, since I don't run the LIS code if there are no out of order nodes.

I'll have to double check though, maybe the -2 mutations could also be made to work.

Edit: You can get it to behave nicely with arrays full of new nodes, not sure if it's worth it though...

[localvoid]

Updated reconciliation algorithm with a LIS algorithm that mutates input array with -2 values. Thanks for noticing this bug in the LIS algo, the new reconciliation algo is now way much better :)