Function longest_increasing_subsequence

atomic-core/src/diff/patience.rs:227–273

Find the Longest Increasing Subsequence of matches by new_idx. Given matches sorted by old_idx, find the longest subsequence where new_idx values are strictly increasing. This ensures the matches maintain relative order in both sequences. Uses the O(N log N) algorithm with binary search.

(matches: &[UniqueMatch])

///
/// Uses the O(N log N) algorithm with binary search.
fn longest_increasing_subsequence(matches: &[UniqueMatch]) -> Vec<UniqueMatch> {
    if matches.is_empty() {
        return Vec::new();
    }

    let n = matches.len();

    // tails[i] = index in matches of the smallest ending element of all
    // increasing subsequences of length i+1
    let mut tails: Vec<usize> = Vec::with_capacity(n);

    // predecessors[i] = index of the predecessor of matches[i] in the LIS
    let mut predecessors: Vec<Option<usize>> = vec![None; n];

    for i in 0..n {
        let new_idx = matches[i].new_idx;

        // Binary search for the position to insert/replace
        let pos = tails
            .binary_search_by(|&j| matches[j].new_idx.cmp(&new_idx))
            .unwrap_or_else(|x| x);

        // Update predecessor
        if pos > 0 {
            predecessors[i] = Some(tails[pos - 1]);
        }

        // Update tails
        if pos == tails.len() {
            tails.push(i);
        } else {
            tails[pos] = i;
        }
    }

    // Reconstruct the LIS by following predecessors
    let mut lis = Vec::with_capacity(tails.len());
    let mut current = tails.last().copied();

    while let Some(idx) = current {
        lis.push(matches[idx]);
        current = predecessors[idx];
    }

    lis.reverse();
    lis
}

/// Build the diff result using LIS anchors.
///