Error for next > prev can occur in valid sequence

[trepidacious]

If we have a sequence p and q where the first identifier of p is less than that of q, but with no gap between them, then the second identifier of p is greater than the second identifier of q, the Error on line 218 will be triggered.

For example
p = [[0, 3], [100, 3]]
q = [[1, 2], [99, 2]]

This is valid since p < q, and both positions look to me like they could be produced while running.

Say we are inserting as site 2 - in this case we see that [0, 3] < [1,2], but cannot insert an ident between them because we have site id 2 giving [0, 2] < [0, 3] (and couldn't insert as [1, 2] either since it is equal to q's first ident). So we move on to the next digit, and the error triggers.

In fact we can use any position of the form [[0, 3], [x, 2]] for x > 100 and <= MAX - we just need the ident to be greater than p's second ident - it's not necessary any more to be < the ident from q, since we already incorporate an earlier ident < the one than q.

I think this can be done very simply by just modifying the first recursion on line 212:

      } else {
        return [prevHead].concat(
          genPosition(siteID, prevPos.slice(1), nextPos.slice(1)));
      }

nextPos.slide(1) needs to be just the empty list instead, thus removing the restriction on the upper limit of subsequent idents. This means that the Error doesn't trigger any more, since we are comparing the maximum identifier to the one from p, rather than the actual identifier from q, and also means that we will produce a valid position between p and q. The error will still trigger if p is actually > q, when we get to an index where p's ident > q's ident BEFORE an index where p's ident < q's ident. Behaviour when p and q have equal idents is unaltered.

[jclem]

How would that error be triggered? The return value of compareIdents([[0, 3], [100, 3]], [[1, 2], [99, 2]]) is -1, since 0 < 1. Nevermind! I see the problem.

[jclem]

This is correct—thank you! I'll accept a PR.

[jclem]

Note that the same issue exists at https://github.com/usecanvas/logoot_ex/blob/51d0f950f2f5d7c0de9c82b65a416f8a4865d1ea/lib/logoot/sequence.ex#L211

[eugene-eeo]

Just a comment that you can speed up insertion if a binary search is used (i think this is also suggested in the paper):

function bsearch(seq, id) {
    let lo = 0
    let hi = seq.length - 1
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2)
        switch (compareAtomIdents(seq[mid][0], id)) {
            case +1: hi = mid - 1; break;
            case -1: lo = mid + 1; break;
            case 0: return mid;
        }
    }
    return lo
}