token-align 0.1.0

use alloc::string::String;
use alloc::vec;
use alloc::vec::Vec;

use super::{get_alignments, get_charmap, Exact, Fold, Normalizer, Stream};

#[test]
fn fold_strips_each_marker_rule() {
    let mut out = String::new();
    Fold.normalize("##A▁ĠĊ</w>", &mut out);
    assert_eq!(out, "a");
}

#[test]
fn exact_copies_input() {
    let mut out = String::new();
    Exact.normalize("##A", &mut out);
    assert_eq!(out, "##A");
}

#[test]
fn empty_inputs_have_empty_outputs() {
    let empty: [&str; 0] = [];
    assert_eq!(get_alignments(&empty, &empty), (vec![], vec![]));
    assert_eq!(get_charmap("", ""), (vec![], vec![]));
}

#[cfg(target_pointer_width = "64")]
#[test]
fn owner_indices_above_u32_max_remain_distinct() {
    let mut stream = Stream {
        chars: Vec::new(),
        owners: Vec::new(),
        units: Vec::new(),
    };
    let boundary = u32::MAX as usize;
    stream.extend("a", boundary);
    stream.extend("b", boundary + 1);
    assert_eq!(stream.owners, vec![boundary, boundary + 1]);
}

#[test]
fn fallback_matches_dynamic_programming_cardinality() {
    let mut state = 0xA5A5_1234_9876_FEDCu64;
    for _ in 0..5_000 {
        let a = random_keys(&mut state);
        let b = random_keys(&mut state);
        let mut pairs = Vec::new();
        super::diff::matched_pairs(&a, &b, &mut pairs);
        assert_eq!(pairs.len(), lcs_len(&a, &b), "{a:?} against {b:?}");
        assert!(pairs
            .windows(2)
            .all(|pair| pair[0].0 < pair[1].0 && pair[0].1 < pair[1].1));
        assert!(pairs.iter().all(|&(i, j)| a[i] == b[j]));
    }
}

#[test]
fn fallback_keeps_maximal_equal_boundaries() {
    let a: Vec<char> = "prefix-aba-suffix".chars().collect();
    let b: Vec<char> = "prefix-a-suffix".chars().collect();
    let mut pairs = Vec::new();
    super::diff::matched_pairs(&a, &b, &mut pairs);
    for index in 0.."prefix-".chars().count() {
        assert!(pairs.contains(&(index, index)));
    }
    let suffix_len = "-suffix".chars().count();
    for offset in 0..suffix_len {
        assert!(pairs.contains(&(a.len() - suffix_len + offset, b.len() - suffix_len + offset)));
    }
}

fn random_keys(state: &mut u64) -> Vec<char> {
    *state = state
        .wrapping_mul(6_364_136_223_846_793_005)
        .wrapping_add(1_442_695_040_888_963_407);
    let len = (*state as usize) % 16;
    (0..len)
        .map(|_| {
            *state = state
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            char::from(b'a' + ((*state >> 32) % 4) as u8)
        })
        .collect()
}

fn lcs_len(a: &[char], b: &[char]) -> usize {
    let mut row = vec![0usize; b.len() + 1];
    for &left in a {
        let mut diagonal = 0;
        for (index, &right) in b.iter().enumerate() {
            let above = row[index + 1];
            row[index + 1] = if left == right {
                diagonal + 1
            } else {
                row[index].max(above)
            };
            diagonal = above;
        }
    }
    row[b.len()]
}