token-align 0.1.0

//! Linear-space matching over unit keys.

use alloc::vec;
use alloc::vec::Vec;

pub(crate) fn matched_pairs(a: &[char], b: &[char], out: &mut Vec<(usize, usize)>) {
    match_range(a, b, 0, 0, out);
}

fn match_range(
    mut a: &[char],
    mut b: &[char],
    mut a_offset: usize,
    mut b_offset: usize,
    out: &mut Vec<(usize, usize)>,
) {
    let prefix = common_prefix(a, b);
    for index in 0..prefix {
        out.push((a_offset + index, b_offset + index));
    }
    a = &a[prefix..];
    b = &b[prefix..];
    a_offset += prefix;
    b_offset += prefix;

    let suffix = common_suffix(a, b);
    let (a_middle, a_tail) = a.split_at(a.len() - suffix);
    let (b_middle, _) = b.split_at(b.len() - suffix);

    if !a_middle.is_empty() && !b_middle.is_empty() {
        if a_middle.len() == 1 {
            if let Some(index) = b_middle.iter().position(|&c| c == a_middle[0]) {
                out.push((a_offset, b_offset + index));
            }
        } else if b_middle.len() == 1 {
            if let Some(index) = a_middle.iter().rposition(|&c| c == b_middle[0]) {
                out.push((a_offset + index, b_offset));
            }
        } else if let Some((a_split, b_split)) = bisect(a_middle, b_middle) {
            if (a_split, b_split) != (0, 0)
                && (a_split, b_split) != (a_middle.len(), b_middle.len())
            {
                match_range(
                    &a_middle[..a_split],
                    &b_middle[..b_split],
                    a_offset,
                    b_offset,
                    out,
                );
                match_range(
                    &a_middle[a_split..],
                    &b_middle[b_split..],
                    a_offset + a_split,
                    b_offset + b_split,
                    out,
                );
            }
        }
    }

    let a_tail_offset = a_offset + a_middle.len();
    let b_tail_offset = b_offset + b_middle.len();
    for index in 0..a_tail.len() {
        out.push((a_tail_offset + index, b_tail_offset + index));
    }
}

fn common_prefix(a: &[char], b: &[char]) -> usize {
    a.iter().zip(b).take_while(|(x, y)| x == y).count()
}

fn common_suffix(a: &[char], b: &[char]) -> usize {
    a.iter()
        .rev()
        .zip(b.iter().rev())
        .take_while(|(x, y)| x == y)
        .count()
}

fn bisect(a: &[char], b: &[char]) -> Option<(usize, usize)> {
    let n = isize::try_from(a.len()).ok()?;
    let m = isize::try_from(b.len()).ok()?;
    let max_d = (n + m + 1) / 2;
    let offset = max_d;
    let size = usize::try_from(2 * max_d + 1).ok()?;
    let mut forward = vec![-1isize; size];
    let mut reverse = vec![-1isize; size];
    forward[usize::try_from(offset + 1).ok()?] = 0;
    reverse[usize::try_from(offset + 1).ok()?] = 0;

    let delta = n - m;
    let odd_delta = delta % 2 != 0;
    let mut forward_start = 0;
    let mut forward_end = 0;
    let mut reverse_start = 0;
    let mut reverse_end = 0;

    for d in 0..max_d {
        let mut k = -d + forward_start;
        while k <= d - forward_end {
            let index = usize::try_from(offset + k).ok()?;
            let mut x = if k == -d || (k != d && forward[index - 1] < forward[index + 1]) {
                forward[index + 1]
            } else {
                forward[index - 1] + 1
            };
            let mut y = x - k;
            while x < n && y < m && a[usize::try_from(x).ok()?] == b[usize::try_from(y).ok()?] {
                x += 1;
                y += 1;
            }
            forward[index] = x;
            if x > n {
                forward_end += 2;
            } else if y > m {
                forward_start += 2;
            } else if odd_delta {
                let reverse_k = delta - k;
                if reverse_k > -d && reverse_k < d {
                    let reverse_index = usize::try_from(offset + reverse_k).ok()?;
                    if reverse[reverse_index] != -1 && x + reverse[reverse_index] >= n {
                        return Some((usize::try_from(x).ok()?, usize::try_from(y).ok()?));
                    }
                }
            }
            k += 2;
        }

        k = -d + reverse_start;
        while k <= d - reverse_end {
            let index = usize::try_from(offset + k).ok()?;
            let mut x = if k == -d || (k != d && reverse[index - 1] < reverse[index + 1]) {
                reverse[index + 1]
            } else {
                reverse[index - 1] + 1
            };
            let mut y = x - k;
            while x < n
                && y < m
                && a[usize::try_from(n - x - 1).ok()?] == b[usize::try_from(m - y - 1).ok()?]
            {
                x += 1;
                y += 1;
            }
            reverse[index] = x;
            if x > n {
                reverse_end += 2;
            } else if y > m {
                reverse_start += 2;
            } else if !odd_delta {
                let forward_k = delta - k;
                if forward_k >= -d && forward_k <= d {
                    let forward_index = usize::try_from(offset + forward_k).ok()?;
                    if forward[forward_index] != -1 && forward[forward_index] + x >= n {
                        let split_x = n - x;
                        let split_y = m - y;
                        return Some((
                            usize::try_from(split_x).ok()?,
                            usize::try_from(split_y).ok()?,
                        ));
                    }
                }
            }
            k += 2;
        }
    }
    None
}