pub fn doubling(a: &Vec<usize>) -> Vec<usize> {
    let n = a.len();
    let mut rank = crate::array_compression::compress(&a).keys;
    let mut k = 1usize;
    let mut key = vec![0; n];
    let mut sa = vec![0; n];
    loop {
        for i in 0..n {
            key[i] = rank[i] << 30;
            if i + k < n {
                key[i] |= 1 + rank[i + k];
            }
            sa[i] = i;
        }
        sa.sort_by_key(|&x| key[x]);
        rank[sa[0]] = 0;
        for i in 0..n - 1 {
            rank[sa[i + 1]] = rank[sa[i]];
            if key[sa[i + 1]] > key[sa[i]] {
                rank[sa[i + 1]] += 1;
            }
        }
        k <<= 1;
        if k >= n {
            break;
        }
    }
    sa
}

pub fn doubling_counting_sort(a: &Vec<usize>) -> Vec<usize> {
    let n = a.len();
    let counting_sort_key = |a: &Vec<usize>| -> Vec<usize> {
        let mut cnt = vec![0; n + 2];
        for &x in a.iter() {
            cnt[x + 1] += 1;
        }
        let mut key = vec![0; n];
        for i in 0..n {
            cnt[i + 1] += cnt[i];
        }
        for i in 0..n {
            key[cnt[a[i]]] = i;
            cnt[a[i]] += 1;
        }
        key
    };
    let mut rank = crate::array_compression::compress(&a).keys;
    let mut k = 1usize;
    let mut key = vec![0; n];
    let mut first = vec![0; n];
    let mut second = vec![0; n];
    let mut sa = vec![0; n];
    loop {
        for i in 0..n {
            second[i] = if i + k < n { 1 + rank[i + k] } else { 0 };
        }
        let rank_second = counting_sort_key(&second);
        for i in 0..n {
            first[i] = rank[rank_second[i]];
        }
        let rank_first = counting_sort_key(&first);
        for i in 0..n {
            sa[i] = rank_second[rank_first[i]];
        }
        for i in 0..n {
            key[i] = first[rank_first[i]] << 30 | second[sa[i]];
        }
        rank[sa[0]] = 0;
        for i in 0..n - 1 {
            rank[sa[i + 1]] = rank[sa[i]];
            if key[i + 1] > key[i] {
                rank[sa[i + 1]] += 1;
            }
        }

        k <<= 1;
        if k >= n {
            break;
        }
    }
    sa
}

pub fn sais_recurse(a: &Vec<usize>) -> Vec<usize> {
    assert!(a.len() > 0);
    let mn = *a.iter().min().unwrap();
    let mut a = a.iter().map(|x| x - mn + 1).collect::<Vec<usize>>();
    a.push(0);
    let n = a.len();
    let m = a.iter().max().unwrap() + 1;
    let mut is_s = vec![true; n];
    let mut is_lms = vec![false; n];
    let mut lms = Vec::with_capacity(n);
    for i in (1..n).rev() {
        is_s[i - 1] = if a[i - 1] == a[i] {
            is_s[i]
        } else {
            a[i - 1] < a[i]
        };
        is_lms[i] = !is_s[i - 1] && is_s[i];
        if is_lms[i] {
            lms.push(i);
        }
    }
    lms.reverse();
    let mut bucket = vec![0usize; m];
    for &x in a.iter() {
        bucket[x] += 1;
    }

    let induce = |lms: &Vec<usize>| -> Vec<usize> {
        let mut sa = vec![n; n];
        let mut sa_idx = bucket.clone();

        for i in 0..m - 1 {
            sa_idx[i + 1] += sa_idx[i];
        }
        for &i in lms.iter().rev() {
            sa_idx[a[i]] -= 1;
            sa[sa_idx[a[i]]] = i;
        }

        sa_idx = bucket.clone();
        let mut s = 0usize;
        for i in 0..m {
            sa_idx[i] += s;
            std::mem::swap(&mut s, &mut sa_idx[i]);
        }
        for i in 0..n {
            if sa[i] == n || sa[i] == 0 {
                continue;
            }
            let i = sa[i] - 1;
            if !is_s[i] {
                sa[sa_idx[a[i]]] = i;
                sa_idx[a[i]] += 1;
            }
        }

        sa_idx = bucket.clone();
        for i in 0..m - 1 {
            sa_idx[i + 1] += sa_idx[i];
        }
        for i in (0..n).rev() {
            if sa[i] == n || sa[i] == 0 {
                continue;
            }
            let i = sa[i] - 1;
            if is_s[i] {
                sa_idx[a[i]] -= 1;
                sa[sa_idx[a[i]]] = i;
            }
        }
        sa
    };

    let sa = induce(&lms);
    let mut lms_idx = Vec::with_capacity(n);
    let mut rank = vec![n; n];
    for &i in sa.iter() {
        if is_lms[i] {
            lms_idx.push(i);
        };
    }
    let l = lms_idx.len();
    let mut r = 0usize;
    rank[n - 1] = r;
    for i in 0..l - 1 {
        let j = lms_idx[i];
        let k = lms_idx[i + 1];
        for d in 0..n {
            let j_is_lms = is_lms[j + d];
            let k_is_lms = is_lms[k + d];
            if a[j + d] != a[k + d] || j_is_lms ^ k_is_lms {
                r += 1;
                break;
            }
            if d > 0 && j_is_lms | k_is_lms {
                break;
            }
        }
        rank[k] = r;
    }
    rank = rank.into_iter().filter(|&x| x != n).collect();
    let mut lms_order: Vec<usize> = Vec::new();
    if r == l - 1 {
        lms_order.resize(l, n);
        for i in 0..l {
            lms_order[rank[i]] = i;
        }
    } else {
        lms_order = sais_recurse(&rank);
    }
    lms = lms_order.iter().map(|&i| lms[i]).collect();
    let sa = induce(&lms);
    sa[1..].to_vec()
}

#[cfg(test)]
mod tests {

    #[test]
    fn suffix_array() {
        let s = vec![
            1, 1, 0, 0, 3, 3, 0, 0, 3, 3, 0, 0, 2, 2, 0, 0,
        ];
        let answer = vec![
            15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4,
        ];
        assert_eq!(super::sais_recurse(&s), answer,);
        assert_eq!(super::doubling_counting_sort(&s), answer,);
        assert_eq!(super::doubling(&s), answer,);
    }
}