// Modified for gitoxide from the upstream imara-diff crate.
// Upstream source: git cat-file -p 32d1e45d3df061e6ccba6db7fdce92db29e345d8:src/histogram/lcs.rs

use crate::histogram::{Histogram, MAX_CHAIN_LEN};
use crate::intern::Token;

/// Finds the longest common subsequence (LCS) using a histogram-based approach.
///
/// Returns `None` if the sequences are highly repetitive and should fall back to Myers.
pub(super) fn find_lcs(before: &[Token], after: &[Token], histogram: &mut Histogram) -> Option<Lcs> {
    let mut search = LcsSearch {
        lcs: Lcs::default(),
        min_occurrences: MAX_CHAIN_LEN + 1,
        found_cs: false,
    };
    search.run(before, after, histogram);
    if search.success() { Some(search.lcs) } else { None }
}

/// Represents a longest common subsequence found by the histogram algorithm.
#[derive(Default, Debug)]
pub struct Lcs {
    /// Starting position in the "before" sequence.
    pub before_start: u32,
    /// Starting position in the "after" sequence.
    pub after_start: u32,
    /// Length of the common subsequence.
    pub len: u32,
}

/// State for searching for the longest common subsequence.
pub struct LcsSearch {
    /// The best LCS found so far.
    lcs: Lcs,
    /// The minimum occurrence count of tokens in the best LCS.
    min_occurrences: u32,
    /// Whether any common subsequence was found.
    found_cs: bool,
}

impl LcsSearch {
    fn run(&mut self, before: &[Token], after: &[Token], histogram: &mut Histogram) {
        let mut pos = 0;
        while let Some(&token) = after.get(pos as usize) {
            if histogram.num_token_occurrences(token) != 0 {
                self.found_cs = true;
                if histogram.num_token_occurrences(token) <= self.min_occurrences {
                    pos = self.update_lcs(pos, token, histogram, before, after);
                    continue;
                }
            }

            pos += 1;
        }

        histogram.clear();
    }

    fn success(&mut self) -> bool {
        !self.found_cs || self.min_occurrences <= MAX_CHAIN_LEN
    }

    fn update_lcs(
        &mut self,
        after_pos: u32,
        token: Token,
        histogram: &Histogram,
        before: &[Token],
        after: &[Token],
    ) -> u32 {
        let mut next_token_idx2 = after_pos + 1;
        let mut occurrences_iter = histogram.token_occurrences(token).iter().copied();
        let mut token_idx1 = occurrences_iter.next().unwrap();

        'occurrences_iter: loop {
            let mut occurrences = histogram.num_token_occurrences(token);
            let mut start1 = token_idx1;
            let mut start2 = after_pos;
            loop {
                if start1 == 0 || start2 == 0 {
                    break;
                }
                let token1 = before.get(start1 as usize - 1);
                let token2 = after.get(start2 as usize - 1);
                if matches!((token1, token2), (Some(token1), Some(token2)) if token1 == token2) {
                    start1 -= 1;
                    start2 -= 1;
                    let new_occurrences = histogram.num_token_occurrences(before[start1 as usize]);
                    occurrences = occurrences.min(new_occurrences);
                } else {
                    break;
                }
            }

            let mut end1 = token_idx1 + 1;
            let mut end2 = after_pos + 1;
            loop {
                let token1 = before.get(end1 as usize);
                let token2 = after.get(end2 as usize);
                if matches!((token1, token2), (Some(token1), Some(token2)) if token1 == token2) {
                    let new_occurrences = histogram.num_token_occurrences(before[end1 as usize]);
                    occurrences = occurrences.min(new_occurrences);
                    end1 += 1;
                    end2 += 1;
                } else {
                    break;
                }
            }

            if next_token_idx2 < end2 {
                next_token_idx2 = end2;
            }

            let len = end2 - start2;
            debug_assert_eq!(len, end1 - start1);
            if self.lcs.len < len || self.min_occurrences > occurrences {
                self.min_occurrences = occurrences;
                self.lcs = Lcs {
                    before_start: start1,
                    after_start: start2,
                    len,
                };
            }

            loop {
                if let Some(next_token_idx) = occurrences_iter.next() {
                    if next_token_idx > end2 {
                        token_idx1 = next_token_idx;
                        break;
                    }
                } else {
                    break 'occurrences_iter;
                }
            }
        }

        next_token_idx2
    }
}