use super::*;
use fxhash::FxHashSet;
use itertools::Itertools;
use std::iter::FromIterator;

/// rule 1 - self-loop
///
/// returns true if rule got applied at least once, false if not at all
pub fn apply_rule_1<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    let mut applied = false;
    for u in graph.vertices_range() {
        if graph.has_edge(u, u) {
            fvs.push(u);
            graph.remove_edges_at_node(u);
            applied = true;
        }
    }
    applied
}

/// rule 3 sink/source nodes
///
/// returns true if rule got applied at least once, false if not at all
pub fn apply_rule_3<G: ReducibleGraph>(graph: &mut G) -> bool {
    repeat_while(|| {
        let mut applied = false;
        for u in graph.vertices_range() {
            if (graph.in_degree(u) == 0) != (graph.out_degree(u) == 0) {
                graph.remove_edges_at_node(u);
                applied = true;
            }
        }

        applied
    })
}

/// rule 4 chaining nodes with deleting self loop
///
/// returns true if rule got applied at least once, false if not at all
pub fn apply_rule_4<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    repeat_while(|| {
        let mut applied = false;
        for u in graph.vertices_range() {
            if graph.in_degree(u) == 1 || graph.out_degree(u) == 1 {
                debug_assert!(!graph.has_edge(u, u));
                let loops = graph.contract_node(u);
                fvs.extend(&loops);
                graph.remove_edges_of_nodes(&loops);
                applied = true;
            }
        }
        applied
    })
}

/// rule 4 chaining nodes with deleting self loop
///
/// returns true if rule got applied at least once, false if not at all
pub fn apply_rule_high_degree<G: ReducibleGraph>(
    graph: &mut G,
    mut upper_bound_incl: Node,
    fvs: &mut Vec<Node>,
) -> Option<bool> {
    if upper_bound_incl == 0 {
        if graph.is_acyclic() {
            return Some(false);
        } else {
            return None;
        }
    }

    let mut global_applied = false;
    loop {
        let mut applied = false;
        for u in graph.vertices_range() {
            if graph.undir_degree(u) > upper_bound_incl {
                fvs.push(u);
                graph.remove_edges_at_node(u);
                upper_bound_incl -= 1;

                if upper_bound_incl == 0 {
                    if graph.is_acyclic() {
                        return Some(true);
                    } else {
                        return None;
                    }
                }

                applied = true;
            }
        }
        if !applied {
            return Some(global_applied);
        }

        global_applied = true;
    }
}

/// This rule identifies all SCCs and deletes edge between them. It should not be included
/// into the [`SuperReducer`] since its SCC-Split is more efficient.
pub fn apply_rule_scc<G: ReducibleGraph>(graph: &mut G) -> bool {
    let partition = graph.partition_into_strongly_connected_components();
    if partition.number_of_classes() == 0 {
        return false;
    }

    if partition.number_of_classes() == 1 && partition.number_of_unassigned() == 0 {
        return false;
    }

    let mut applied = false;
    for u in graph.vertices_range() {
        if graph.total_degree(u) == 0 {
            continue;
        }

        if let Some(part_u) = partition.class_of_node(u) {
            let inter_scc = graph
                .out_neighbors(u)
                .filter(|&v| partition.class_of_node(v) != Some(part_u))
                .collect_vec();

            applied |= !inter_scc.is_empty();

            for v in inter_scc {
                graph.remove_edge(u, v);
            }
        } else {
            graph.remove_edges_at_node(u);
            applied = true;
        }
    }

    applied
}

/// Safe Di-Cliques Reduction, requires self loops to be deleted
///
/// returns true if rule got applied at least once, false if not at all
pub fn apply_rule_di_cliques<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    let mut applied = false;
    for u in graph.vertices_range() {
        let k = graph.undir_degree(u);

        if k == 0 || graph.undir_neighbors(u).any(|v| graph.undir_degree(v) < k) {
            continue;
        }

        let neighbors = FxHashSet::from_iter(graph.undir_neighbors(u));

        if neighbors.iter().any(|&v| {
            graph
                .undir_neighbors(v)
                .filter(|x| *x == u || neighbors.contains(x))
                .take(k as usize)
                .count()
                != k as usize
        }) {
            continue;
        }

        // if u is only in 1 clique we check here if we can safely delete all nodes but u from that
        // clique. Either u has only out- or in-going edges or there is no circle back to u
        // outside of the clique. This last point is checked via breadth first search
        if graph.in_degree(u) == k
            || graph.out_degree(u) == k
            || !graph.is_node_on_cycle_after_deleting(u, neighbors.iter().copied())
        {
            for &node in &neighbors {
                graph.remove_edges_at_node(node);
            }
            fvs.extend(neighbors.iter());
            graph.remove_edges_at_node(u);
            applied = true;
        }
    }
    applied
}

pub fn apply_rule_complete_node<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    let mut num_nodes = graph
        .vertices()
        .filter(|&u| graph.total_degree(u) > 0)
        .count() as Node;

    apply_rule_1(graph, fvs)
        | repeat_while(|| {
            if num_nodes <= 1 {
                return false;
            }

            let mut applied = false;
            for node in graph.vertices_range() {
                if num_nodes > 1 && graph.undir_degree(node) == num_nodes - 1 {
                    fvs.push(node);
                    graph.remove_edges_at_node(node);
                    applied = true;
                    num_nodes -= 1;

                    if num_nodes == 1 {
                        return true;
                    }
                }
            }
            applied
        })
}

/// PIE reduction rule
///
/// Looks for directed edges that are not strongly connected after removing undirected edges
pub fn apply_rule_pie<G: ReducibleGraph>(graph: &mut G) -> bool {
    let mut applied = false;
    let graph_minus_pie = graph_without_pie(graph);
    let graph_sccs = graph_minus_pie.partition_into_strongly_connected_components();
    if graph_sccs.number_of_classes() == 1 && graph_sccs.number_of_unassigned() == 0 {
        return applied;
    }
    // check for every edge of our graph without undirected edges if the nodes have
    // stayed in the same scc, if not we can delete the directed edge
    for (u, v) in graph_minus_pie.edges_iter() {
        if graph_sccs.class_of_node(u) == None
            || graph_sccs.class_of_node(u) != graph_sccs.class_of_node(v)
        {
            graph.remove_edge(u, v);
            applied = true;
        }
    }
    applied
}

/// DOME reduction rule
///
/// Looks for directed edges that get dominated by other edges (un/directed edges)
pub fn apply_rule_dome<G: ReducibleGraph>(graph: &mut G) -> bool {
    let mut applied = false;
    for u in graph.vertices_range() {
        loop {
            if graph.in_degree(u) == 0 || graph.out_degree(u) == 0 {
                break;
            }

            let in_only_neigh_u = graph.in_only_neighbors(u).collect::<FxHashSet<_>>();
            let out_neigh_u = graph.out_neighbors(u).collect::<FxHashSet<_>>();

            let v = graph.out_only_neighbors(u).find(|&neighbor|
                // test if in_only_neigh_u is subset of in_only_neighbors(neighbor)
                graph
                    .in_neighbors(neighbor)
                    .filter(|v| in_only_neigh_u.contains(v))
                    .take(in_only_neigh_u.len())
                    .count()
                    == in_only_neigh_u.len()
                    // test if out_only_neighbors(neighbor) is subset of out_neigh_u
                    || graph
                    .out_only_neighbors(neighbor)
                    .all(|v| out_neigh_u.contains(&v)));

            if let Some(v) = v {
                applied = true;
                graph.remove_edge(u, v);
            } else {
                break;
            }
        }
    }
    applied
}

/// We are looking for an "undirected" cycle of four nodes (not induced; i.e. there
/// may be additional edges).
///      u
///    /   \
///  v       w
///    \   /
///      x
///
/// In such a structure, we have to delete at least {u, x} or {v, w}. Thus, the remaining
/// pair needs to have (amongst others) an undir-degree of exactly 2. To prune the search
/// space we require that the undir-degree of u *is* 2 --- {v,w} may have larger undir-degree.
///
/// To make the deletion of nodes (and adding to the DFVS) compatible with a globally optimal
/// solution,  we require that the remaining pair not to have cycles outside the subgraph. Thus,
/// we can delete all four nodes and add two to the DFVS.
pub fn apply_rule_c4<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    let mut applied = 0;

    loop {
        let c4 = (|| {
            'foru: for u in graph.vertices_range() {
                if graph.undir_degree(u) != 2 {
                    continue;
                }

                let (v, dv, w, dw) = {
                    // v has smaller/eq degree
                    let mut neighs = graph.undir_neighbors(u);
                    let v = neighs.next().unwrap();
                    let w = neighs.next().unwrap();
                    debug_assert!(neighs.next().is_none());
                    debug_assert_ne!(u, v);
                    debug_assert_ne!(u, w);
                    debug_assert_ne!(v, w);

                    let dv = graph.undir_degree(v);
                    let dw = graph.undir_degree(v);
                    if dv < dw {
                        (v, dv, w, dw)
                    } else {
                        (w, dw, v, dv)
                    }
                };

                if dv < 2 {
                    continue;
                }

                // if 2 <= max(dw, dv) = dw, we have to delete the {v, w} pair since at least w
                // will keep a cycle outside of the C4 if we were to delete {u, x}.
                let has_to_delete_vw = dw > 2;
                let mut u_acyclic_without_vw = None;

                for x in graph.undir_neighbors(v) {
                    if x == u
                        || x == v
                        || x == w
                        || (has_to_delete_vw && graph.undir_degree(x) > 2)
                        || !graph.has_edge(w, x)
                        || !graph.has_edge(x, w)
                    {
                        continue;
                    }

                    if u_acyclic_without_vw.is_none() {
                        u_acyclic_without_vw =
                            Some(!graph.is_node_on_cycle_after_deleting(u, [v, w]));

                        if has_to_delete_vw && !u_acyclic_without_vw.unwrap() {
                            continue 'foru;
                        }
                    }

                    if u_acyclic_without_vw.unwrap()
                        && !graph.is_node_on_cycle_after_deleting(x, [v, w])
                    {
                        return Some(((v, w), (u, x)));
                    }

                    if !has_to_delete_vw
                        && !graph.is_node_on_cycle_after_deleting(v, [u, x])
                        && !graph.is_node_on_cycle_after_deleting(w, [u, x])
                    {
                        return Some(((u, x), (v, w)));
                    }
                }
            }
            None
        })();

        if let Some(((del1, del2), (keep1, keep2))) = c4 {
            graph.remove_edges_at_node(del1);
            graph.remove_edges_at_node(del2);
            graph.remove_edges_at_node(keep1);
            graph.remove_edges_at_node(keep2);
            fvs.push(del1);
            fvs.push(del2);

            applied += 1;
        } else {
            return applied > 0;
        }
    }
}

/// Removes unconfined vertices as proposed by Kneis et al. in "A fine-grained analysis of a simple
/// independent set algorithm."  We implement the algorithm based on Akiba and Iwata "Branch-and-reduce
/// exponential/FPT algorithms in practice: A case study of vertex cover". Some adoption were necessary
/// to make it compatible with the DFVS problem (we basically restrict ourselves to the undirected subgraph)
pub fn apply_rule_unconfined<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    let mut applied = false;

    // capacities are estimated from profiling a couple of runs
    let mut set_s = Vec::with_capacity(8);
    let mut neighbors_of_s = Vec::with_capacity(32);

    loop {
        let mut local_applied = false;
        for v in graph.vertices_range() {
            if !graph.has_undir_edges(v) || graph.has_dir_edges(v) {
                continue;
            }

            set_s.clear();
            neighbors_of_s.clear();

            let add_to_s = |v: Node, set_s: &mut Vec<Node>, neighbors_of_s: &mut Vec<Node>| {
                neighbors_of_s.extend(graph.undir_neighbors(v).filter(|w| !set_s.contains(w)));
                if let Some(i) = neighbors_of_s.iter().position(|&x| x == v) {
                    neighbors_of_s.swap_remove(i);
                }
                set_s.push(v)
            };

            add_to_s(v, &mut set_s, &mut neighbors_of_s);

            let is_unconfined = loop {
                let u = neighbors_of_s
                    .iter()
                    .filter_map(|&u| {
                        if graph
                            .undir_neighbors(u)
                            .filter(|v| set_s.contains(v))
                            .take(2)
                            .count()
                            == 1
                        {
                            let mut set = graph
                                .undir_neighbors(u as Node)
                                .filter(|v| !neighbors_of_s.contains(v) && !set_s.contains(v));

                            // try to extract the first entry and count the remainder
                            let w = set.next();
                            Some((w.is_some() as usize + set.count(), w))
                        } else {
                            None
                        }
                    })
                    .min_by_key(|&(n, _)| n);

                if let Some((n, w)) = u {
                    if n == 0 {
                        break neighbors_of_s.iter().all(|&v| !graph.has_dir_edges(v));
                    }

                    if n == 1 {
                        let w = w.unwrap();
                        if graph.has_dir_edges(w) {
                            break false;
                        }
                        add_to_s(w, &mut set_s, &mut neighbors_of_s);
                        continue;
                    }
                }

                break false;
            };

            if is_unconfined {
                graph.remove_edges_at_node(v);
                fvs.push(v);
                local_applied = true;
            }
        }

        if !local_applied {
            return applied;
        }

        applied = true;
    }
}

/// If the contraction of a node does not add an additional edge, we know that we have to
/// delete its neighbors if we need to break a cycle. Hence we can contract that node.
pub fn apply_rule_domn<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    repeat_while(|| {
        let mut applied = false;

        for u in graph.vertices_range() {
            if graph.in_degree(u) > 0
                && graph.out_degree(u) > 0
                && graph.in_neighbors(u).all(|i|
                    graph.out_degree(i) >= graph.out_degree(u)) // fail early
                && graph.in_neighbors(u).all(|i| {
                    graph
                        .out_neighbors(u)
                        .all(|j| i == j || graph.has_edge(i, j))
                })
            {
                applied = true;
                let loops = graph.undir_neighbors(u).collect_vec();

                graph.remove_edges_at_node(u);
                graph.remove_edges_of_nodes(&loops);

                fvs.extend(&loops);
            }
        }

        applied
    })
}

/// The dominance rule proposed for VC searches to node u and v such that
/// N\[u\] subseteq N\[v\]. Then we node v can be put into the VC safely. We generalize it to
/// DFVS by requiring that u and v have undirected edges and that possible in-/out-only neighbors
/// of u have to be present at v as well (in that direction).
pub fn apply_rule_dominance<G: ReducibleGraph>(graph: &mut G, fvs: &mut Vec<Node>) -> bool {
    repeat_while(|| {
        let m = graph.number_of_edges();

        let mut vertices = graph
            .vertices_range()
            .filter(|&u| graph.undir_degree(u) > 0)
            .collect_vec();
        vertices.sort_unstable_by_key(|&u| graph.number_of_nodes() - graph.undir_degree(u));

        for &u in &vertices {
            let mut neighbors = graph
                .undir_neighbors(u)
                .filter(|&v| graph.undir_degree(v) >= graph.total_degree(u) - graph.undir_degree(u))
                .collect_vec();
            neighbors.sort_unstable_by_key(|&u| graph.number_of_nodes() - graph.undir_degree(u));

            for v in neighbors {
                if graph
                    .undir_neighbors(u)
                    .all(|w| w == v || graph.has_undir_edge(v, w))
                    && graph.out_only_neighbors(u).all(|w| graph.has_edge(v, w))
                    && graph.in_only_neighbors(u).all(|w| graph.has_edge(w, v))
                {
                    graph.remove_edges_at_node(v);
                    fvs.push(v)
                }
            }
        }

        m != graph.number_of_edges()
    })
}

pub(super) fn graph_without_pie<G: ReducibleGraph>(graph: &G) -> G {
    let mut graph_minus_pie = G::new(graph.len());
    for node in graph.vertices_range() {
        for out_neighbor in graph.out_only_neighbors(node) {
            graph_minus_pie.add_edge(node, out_neighbor);
        }
    }
    graph_minus_pie
}

#[cfg(test)]
mod tests {
    use super::super::tests::*;
    use super::*;

    #[test]
    fn rule_1() {
        let mut test_pre_process = create_test_pre_processor();
        test_pre_process.apply_rule_1();

        assert_eq!(test_pre_process.graph.number_of_edges(), 4);
        assert_eq!(test_pre_process.in_fvs.len(), 2);
    }

    #[test]
    fn rule_3() {
        let mut test_pre_process = create_test_pre_processor();
        test_pre_process.apply_rule_3();
        assert_eq!(test_pre_process.graph.number_of_edges(), 8);
        assert_eq!(test_pre_process.graph.out_degree(5), 0);
    }

    #[test]
    fn rule_4_neighbor_is_neighbor() {
        let mut test_pre_process = {
            let graph = AdjArrayUndir::from(&[
                (0, 1),
                (0, 2),
                (1, 0),
                (2, 0),
                (2, 1),
                (2, 3),
                (2, 5),
                (3, 2),
                (3, 1),
                (3, 4),
                (4, 1),
                (4, 3),
                (4, 5),
                (5, 2),
                (5, 3),
            ]);

            let test_pre_process = PreprocessorReduction::from(graph);
            test_pre_process
        };
        test_pre_process.apply_rule_4();
        assert_eq!(test_pre_process.in_fvs.len(), 3);
        assert_eq!(test_pre_process.graph.number_of_edges(), 0);
    }

    #[test]
    fn rule_4_neighbor_not_neighbor() {
        let graph = AdjArrayUndir::from(&[
            (0, 2),
            (0, 5),
            (1, 0),
            (2, 0),
            (2, 1),
            (2, 3),
            (2, 5),
            (3, 2),
            (3, 1),
            (3, 4),
            (4, 0),
            (4, 1),
            (4, 5),
            (5, 2),
            (5, 3),
        ]);

        let mut test_pre_process = PreprocessorReduction::from(graph);

        test_pre_process.apply_rule_4();
        assert_eq!(test_pre_process.in_fvs.len(), 0);
        assert_eq!(test_pre_process.graph.number_of_edges(), 10);
    }

    #[test]
    fn pie_reduction() {
        let graph = AdjArrayUndir::from(&[
            (0, 1),
            (0, 3),
            (0, 5),
            (1, 2),
            (1, 3),
            (1, 4),
            (2, 0),
            (2, 4),
            (2, 5),
            (3, 0),
            (3, 4),
            (4, 1),
            (4, 5),
            (4, 2),
            (5, 3),
            (5, 0),
        ]);

        let mut test_pre_process = PreprocessorReduction::from(graph);

        assert_eq!(test_pre_process.graph.edges_vec().len(), 16);
        test_pre_process.apply_rule_pie();
        assert_eq!(test_pre_process.graph.edges_vec().len(), 14);
    }

    #[test]
    fn pie_reduction_nones() {
        let graph = AdjArrayUndir::from(&[
            (0, 1),
            (0, 2),
            (0, 3),
            (1, 0),
            (1, 2),
            (2, 1),
            (2, 3),
            (3, 0),
        ]);

        let mut test_pre_process = PreprocessorReduction::from(graph);

        assert_eq!(test_pre_process.graph.edges_vec().len(), 8);
        test_pre_process.apply_rule_pie();
        assert_eq!(test_pre_process.graph.edges_vec().len(), 6);
    }

    #[test]
    fn dome_reduction() {
        let graph = AdjArrayUndir::from(&[
            (0, 1),
            (0, 2),
            (1, 0),
            (1, 2),
            (2, 1),
            (2, 3),
            (2, 4),
            (3, 0),
            (3, 5),
            (4, 3),
            (4, 5),
            (5, 0),
            (5, 4),
        ]);

        let mut test_pre_process = PreprocessorReduction::from(graph);

        assert_eq!(test_pre_process.graph.edges_vec().len(), 13);
        test_pre_process.apply_rule_dome();
        assert_eq!(test_pre_process.graph.edges_vec().len(), 9);
    }

    fn create_test_pre_processor() -> PreprocessorReduction<AdjArrayUndir> {
        let graph = AdjArrayUndir::from(&[
            (0, 1),
            (1, 4),
            (2, 2),
            (2, 4),
            (3, 3),
            (3, 4),
            (4, 3),
            (4, 0),
            (5, 4),
        ]);

        let test_pre_process = PreprocessorReduction::from(graph);
        test_pre_process
    }

    #[test]
    fn unconfined() {
        let mut graph = AdjArrayUndir::from(&[(0, 1), (1, 0)]);
        let mut fvs = Vec::new();
        assert!(apply_rule_unconfined(&mut graph, &mut fvs));
    }

    #[test]
    fn stress_rule1() {
        // this is not terribly useful, since the kernels have no loops
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_1(graph, fvs)));
    }

    #[test]
    fn stress_rule3() {
        stress_test_kernel(|graph, _, _| Some(apply_rule_3(graph)));
    }

    #[test]
    fn stress_rule4() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_4(graph, fvs)));
    }

    #[test]
    fn stress_c4() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_c4(graph, fvs)));
    }

    #[test]
    fn stress_complete_node() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_complete_node(graph, fvs)));
    }

    #[test]
    fn stress_di_cliques() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_di_cliques(graph, fvs)));
    }

    #[test]
    fn stress_dome() {
        stress_test_kernel(|graph, _, _| Some(apply_rule_dome(graph)));
    }

    #[test]
    fn stress_dominance() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_dominance(graph, fvs)));
    }

    #[test]
    fn stress_domn() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_domn(graph, fvs)));
    }

    #[test]
    fn stress_pie() {
        stress_test_kernel(|graph, _, _| Some(apply_rule_pie(graph)));
    }

    #[test]
    fn stress_scc() {
        stress_test_kernel(|graph, _, _| Some(apply_rule_scc(graph)));
    }

    #[test]
    fn stress_unconfined() {
        stress_test_kernel(|graph, fvs, _| Some(apply_rule_unconfined(graph, fvs)));
    }

    #[test]
    #[should_panic]
    fn stress_rule_high_degree_too_low_ub() {
        stress_test_kernel(|graph, fvs, opt| {
            apply_rule_high_degree(graph, opt.saturating_sub(1), fvs)
        });
    }

    #[test]
    fn stress_rule_high_degree() {
        stress_test_kernel(|graph, fvs, opt| apply_rule_high_degree(graph, opt, fvs));
    }

    #[test]
    fn stress_rule_high_degree_higher_ub() {
        stress_test_kernel(|graph, fvs, opt| apply_rule_high_degree(graph, opt + 1, fvs));
    }
}
