use std::{
    cmp::{Ordering, PartialOrd},
    collections::HashSet,
};

type Graph = Vec<Vec<usize>>;

fn add_edge(graph: &mut Graph, source: usize, target: usize) {
    let len = graph.len();

    if source >= len {
        panic!("source = {source} >= len = {len}");
    }

    if target >= len {
        panic!("target = {target} >= len = {len}");
    }

    if !graph.get(source).unwrap().contains(&target) {
        graph.get_mut(source).unwrap().push(target);
    }

    if !graph.get(target).unwrap().contains(&source) {
        graph.get_mut(target).unwrap().push(source);
    }
}

fn sm1<T: PartialOrd>(a: Vec<T>, count: &mut usize) -> (usize, Graph) {
    let n = a.len();

    if n == 0 {
        panic!("invalid empty input");
    }

    let mut result: Graph = std::iter::repeat_with(Default::default).take(n).collect();

    let mut indices: Vec<usize> = (0..n).collect();

    let mut upper_bound = n;

    while upper_bound > 1 {
        for i in 0..(upper_bound.div_euclid(2)) {
            *count += 1;

            let x = *indices.get(2 * i).unwrap();
            let y = *indices.get(2 * i + 1).unwrap();

            add_edge(&mut result, x, y);

            match a.get(x).unwrap().partial_cmp(a.get(y).unwrap()) {
                Some(Ordering::Less) | Some(Ordering::Equal) => {
                    *indices.get_mut(i).unwrap() = x;
                }
                Some(_) => {
                    *indices.get_mut(i).unwrap() = y;
                }
                None => {
                    if a.get(x).unwrap().partial_cmp(a.get(x).unwrap()).is_some() {
                        *indices.get_mut(i).unwrap() = x;
                    } else {
                        *indices.get_mut(i).unwrap() = y;
                    }
                }
            }
        }

        let offset = upper_bound.rem_euclid(2);

        if offset == 1 {
            *indices.get_mut(upper_bound.div_euclid(2)).unwrap() =
                *indices.get(upper_bound - 1).unwrap();
        }

        upper_bound = upper_bound.div_euclid(2) + offset;
    }

    (*indices.first().unwrap(), result)
}

fn sm<T: PartialOrd>(a: Vec<T>, count: &mut usize) -> Vec<usize> {
    let n = a.len();

    let mut result: Vec<usize> = Vec::with_capacity(n);

    let mut added: Vec<bool> = std::iter::repeat(false).take(n).collect();

    let mut g_to_a_s: Vec<Vec<usize>> = Vec::with_capacity(n);

    g_to_a_s.push((0..n).collect());

    let mut lis: Vec<Graph> = vec![];

    for i in 0..n {
        let g: Vec<&T> = g_to_a_s
            .last()
            .unwrap()
            .iter()
            .copied()
            .map(|x| a.get(x).unwrap())
            .collect();

        let g_len = g.len();

        assert_eq!(Some(g_len), g_to_a_s.last().map(|v| v.len()));

        let (hi, li) = sm1(g, count);
        assert!(hi < g_len);

        let hi = *g_to_a_s.last().unwrap().get(hi).unwrap();

        result.push(hi);

        if i + 1 == n {
            // early break to prevent unnecessary efforts
            break;
        }

        *added.get_mut(hi).unwrap() = true;

        lis.push(li);

        assert_eq!(lis.len(), i + 1);
        assert_eq!(g_to_a_s.len(), i + 1);

        let mut new_g_to_a: Vec<usize> = Vec::new();
        let mut new_g_to_a_set: HashSet<usize> = Default::default();

        for j in 0..=i {
            let mut ell_j: Vec<usize> = Vec::new();

            let i_j = g_to_a_s.get(j).unwrap();

            let index = i_j.iter().position(|x| *x == hi);

            if let Some(x_j) = index {
                for y in lis.get(j).unwrap().get(x_j).unwrap().iter().copied() {
                    ell_j.push(*i_j.get(y).unwrap());
                }
            }

            for x in ell_j {
                if !new_g_to_a_set.contains(&x) && !added.get(x).unwrap() {
                    new_g_to_a.push(x);
                    new_g_to_a_set.insert(x);
                }
            }
        }

        g_to_a_s.push(new_g_to_a);
    }

    result
}

fn main() {
    // sample: 1 3 4 0 2 3 5 1
    let inputs: Vec<f32> = std::env::args()
        .skip(1)
        .map(|arg| arg.parse().unwrap())
        .collect();

    // let enumeration: Vec<f32> = (0..inputs.len()).map(|n| n as f32).collect();

    // println!("        {enumeration:?}");

    if inputs.is_empty() {
        println!("Please input some numbers to sort.");
        return;
    }

    println!("inputs: {inputs:?}");

    let mut count = 0;

    let sort = sm(inputs.clone(), &mut count);

    let sort_result: Vec<f32> = sort
        .iter()
        .copied()
        .map(|n| *inputs.get(n).unwrap())
        .collect();

    println!("sort indices = {sort:?}\nsort result: {sort_result:?}\ncount = {count}");
}