use crate::bitset::BitSet;
use crate::graph::*;
use itertools::Itertools;
use std::fmt::Debug;

use crate::kernelization::apply_rules_exhaustively;

pub type Solution = Vec<Node>;
pub type OptSolution = Option<Solution>;

pub fn branch_and_bound_on_graphs<G>(
    graph: &G,
    _min_size: Option<Node>,
    max_size: Option<Node>,
) -> OptSolution
where
    G: AdjacencyListIn
        + AdjacencyListUndir
        + AdjacencyTest
        + AdjacencyTestUndir
        + GraphEdgeEditing
        + Debug
        + Clone,
{
    let upper_limit_excl = max_size.unwrap_or_else(|| graph.number_of_nodes()) + 1;
    bb_impl(graph.clone(), upper_limit_excl, false)
}

fn bb_impl<G>(mut graph: G, mut upper_limit_excl: Node, skip_reduction: bool) -> OptSolution
where
    G: AdjacencyListIn
        + AdjacencyListUndir
        + AdjacencyTest
        + AdjacencyTestUndir
        + GraphEdgeEditing
        + Debug
        + Clone,
{
    if upper_limit_excl == 0 {
        return None;
    }

    let mut solution = Solution::new();
    if !skip_reduction {
        let expensive = graph.len() % 10 == 0;
        apply_rules_exhaustively(&mut graph, &mut solution, expensive);

        if solution.len() as Node >= upper_limit_excl {
            return None;
        }

        upper_limit_excl -= solution.len() as Node;

        let sccs = graph.strongly_connected_components_no_singletons();
        if sccs.is_empty() {
            return Some(solution);
        }

        // After reduction each SSC has a DFVS size of at least 2
        // (see Chakradhar, "AN EXACT ALGORITHM FOR SELECTING PARTIAL SCAN FLIP-FLOPS" Claim 1)
        // TODO: this needs to be rechecked with new rules, but I currently do not see it changing
        // as this would somehow make rules 1-4 less effective
        if 2 * sccs.len() >= upper_limit_excl as usize {
            return None;
        }

        if sccs.len() > 1 || sccs[0].len() < graph.len() {
            upper_limit_excl -= 2 * sccs.len() as Node;

            for scc in sccs {
                let (subgraph, mapper) =
                    graph.vertex_induced(&BitSet::new_all_unset_but(graph.len(), scc.into_iter()));
                let sub_sol = bb_impl(subgraph, upper_limit_excl + 2, true)?;
                assert!(sub_sol.len() >= 2);

                upper_limit_excl -= sub_sol.len() as Node - 2;

                for u in mapper.get_old_ids(sub_sol.into_iter()) {
                    solution.push(u);
                }
            }

            return Some(solution);
        }
    }

    let node = graph
        .vertices()
        .max_by_key(|&u| graph.in_degree(u) as usize * graph.out_degree(u) as usize)?; // TODO: Improve heuristic!

    // first branch: deletion
    let solution_del: OptSolution = (|| {
        let mut del_graph = graph.clone();
        del_graph.remove_edges_at_node(node);
        let mut solution = bb_impl(del_graph, upper_limit_excl - 1, false)?;
        solution.push(node);
        Some(solution)
    })();

    if let Some(sol) = solution_del.as_ref() {
        upper_limit_excl = sol.len() as Node;
    }

    // second branch: contraction
    let solution_contr: OptSolution = (|| {
        if graph.has_edge(node, node) {
            return None;
        }

        let in_neighbors = graph.in_neighbors(node).collect_vec();
        graph.contract_node(node);

        let loops = in_neighbors
            .into_iter()
            .filter(|&u| graph.has_edge(u, u))
            .collect_vec();

        if loops.len() >= upper_limit_excl as usize {
            return None;
        }

        for &l in &loops {
            graph.remove_edges_at_node(l);
        }

        if let Some(mut sol) = bb_impl(
            graph,
            upper_limit_excl - loops.len() as Node,
            !loops.is_empty(),
        ) {
            for l in loops {
                sol.push(l);
            }
            Some(sol)
        } else {
            None
        }
    })();

    if solution_contr.is_some() {
        solution_contr
    } else {
        solution_del
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::bitset::BitSet;
    use crate::exact::branch_and_bound_matrix::branch_and_bound_matrix;
    use crate::graph::adj_array::AdjArrayIn;
    use crate::random_models::gnp::generate_gnp;
    use rand::SeedableRng;
    use rand_pcg::Pcg64Mcg;

    #[test]
    fn bb_generated_tests() {
        // The results were generated by the branch_and_bound implementation in MR19.
        let solution_sizes = vec![
            4, 4, 5, 5, 4, 4, 6, 7, 5, 6, 5, 6, 6, 8, 6, 6, 8, 6, 5, 6, 7, 7, 7, 5, 7, 8, 9, 9, 7,
            7, 9, 9, 8, 10, 8, 8,
        ];

        let mut gen = Pcg64Mcg::seed_from_u64(123);

        for n in 10..=21 {
            for avg_deg in [5] {
                for i in 0..3 {
                    let p = avg_deg as f64 / n as f64;
                    let mut graph: AdjArrayIn = generate_gnp(&mut gen, n, p);

                    for i in graph.vertices_range() {
                        graph.try_remove_edge(i, i);
                    }

                    let solution = branch_and_bound_on_graphs(&graph, None, None).unwrap();
                    let solution_mask =
                        BitSet::new_all_set_but(graph.len(), solution.iter().copied());

                    assert_eq!(solution.len(), solution_sizes[((n - 10) * 3 + i) as usize]);
                    assert!(graph.vertex_induced(&solution_mask).0.is_acyclic());
                }
            }
        }
    }

    #[test]
    fn cross_validation() {
        let mut gen = Pcg64Mcg::seed_from_u64(234);

        for n in 2..30 {
            for avg_deg in [2, 5, 10] {
                if avg_deg + 1 >= n {
                    continue;
                }

                for _ in 0..3 {
                    let p = avg_deg as f64 / n as f64;
                    let graph: AdjArrayIn = generate_gnp(&mut gen, n, p);

                    let sol1 = branch_and_bound_matrix(&graph, None).unwrap();
                    let sol2 = branch_and_bound_on_graphs(&graph, None, None).unwrap();

                    assert_eq!(sol1.len(), sol2.len());

                    let solution_mask = BitSet::new_all_set_but(graph.len(), sol2.iter().copied());
                    assert!(graph.vertex_induced(&solution_mask).0.is_acyclic());
                }
            }
        }
    }
}
