package nl.camilstaps.cs.graphs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * A Graph is a list of Nodes.
 *
 * @author Camil Staps
 */
public class Graph {
    private final List<Node> nodes;
    private final Stack<List<Node>> removedStack = new Stack<>();

    public Graph() {
        this.nodes = new ArrayList<>();
        restorePoint();
    }

    public Graph(List<Node> nodes) {
        this.nodes = nodes;
        restorePoint();
    }

    public int maximumIndependentSetSize() {
        if (nodes.size() <= 1)
            return nodes.size();

        int mis = 0;
        restorePoint();

        Graph partition = findPartition();
        if (partition.size() == size()) {
            Collections.sort(nodes);
            Node A = nodes.get(0);
            Collections.sort(A.getNeighbourhood(), Collections.reverseOrder());
            Node B = A.getNeighbourhood().get(0);

            int try_1, try_2;
            switch (A.getDegree()) {
                case 1:
                    removeNodes(A.getInclusiveNeighbourhood());
                    mis = 1 + maximumIndependentSetSize();
                    break;
                case 2:
                    Node B_ = A.getNeighbourhood().get(1);
                    if (B.getNeighbourhood().contains(B_)) {
                        removeNodes(A.getInclusiveNeighbourhood());
                        mis = 1 + maximumIndependentSetSize();
                    } else {
                        restorePoint();
                        removeNodes(B.getInclusiveNeighbourhood());
                        removeNodes(B_.getInclusiveNeighbourhood());
                        try_1 = 2 + maximumIndependentSetSize();
                        restore();
                        removeNodes(A.getInclusiveNeighbourhood());
                        try_2 = 1 + maximumIndependentSetSizeWith2From(A.getSecondNeighbourhood());
                        mis = Math.max(try_1, try_2);
                    }
                    break;
                case 3:
                    removeNode(A);
                    try_1 = maximumIndependentSetSizeWith2From(A.getNeighbourhood());
                    removeNodes(A.getNeighbourhood());
                    try_2 = 1 + maximumIndependentSetSize();
                    mis = Math.max(try_1, try_2);
                    break;
                default:
                    if (A.dominates(B)) {
                        removeNode(B);
                        mis = maximumIndependentSetSize();
                    } else {
                        removeNode(B);
                        try_1 = maximumIndependentSetSize();
                        removeNodes(B.getNeighbourhood());
                        try_2 = 1 + maximumIndependentSetSize();
                        mis = Math.max(try_1, try_2);
                    }
                    break;
            }
        } else {
            mis = partition.maximumIndependentSetSize();
            removeNodes(partition.nodes);
            mis += maximumIndependentSetSize();
        }

        restore();
        return mis;
    }

    private int maximumIndependentSetSizeWith1From(Node s_1, Node s_2) {
        assert s_1.getDegree() <= s_2.getDegree();

        int mis = 0;
        restorePoint();

        if (s_1.getDegree() <= 1) {
            mis = maximumIndependentSetSize();
        } else if (s_1.getNeighbourhood().contains(s_2)) {
            if (s_1.getDegree() <= 3) {
                mis = maximumIndependentSetSize();
            } else {
                int try_1, try_2;
                restorePoint();
                removeNodes(s_1.getInclusiveNeighbourhood());
                try_1 = maximumIndependentSetSize();
                restore();
                removeNodes(s_2.getInclusiveNeighbourhood());
                try_2 = maximumIndependentSetSize();
                mis = Math.max(try_1, try_2) + 1;
            }
        } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
            removeNodes(s_1.neighbourhoodIntersection(s_2));
            mis = maximumIndependentSetSizeWith1From(s_1, s_2);
        } else if (s_2.getDegree() == 2) {
            Node E = s_1.getNeighbourhood().get(0), F = s_1.getNeighbourhood().get(1);
            if (E.getNeighbourhood().contains(F)) {
                removeNodes(s_1.getInclusiveNeighbourhood());
                mis = 1 + maximumIndependentSetSize();
            } else {
                boolean subset = true;
                for (Node n : E.getNeighbourhood())
                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
                        subset = false;
                for (Node n : F.getNeighbourhood())
                    if (n != s_1 && !s_2.getNeighbourhood().contains(n))
                        subset = false;
                if (subset) {
                    removeNodes(s_1.getInclusiveNeighbourhood());
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    mis = 3 + maximumIndependentSetSize();
                } else {
                    int try_1, try_2;
                    removeNodes(s_1.getInclusiveNeighbourhood());
                    try_1 = 1 + maximumIndependentSetSize();
                    removeNodes(E.getInclusiveNeighbourhood());
                    removeNodes(F.getInclusiveNeighbourhood());
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    try_2 = 3 + maximumIndependentSetSize();
                    mis = Math.max(try_1, try_2);
                }
            }
        } else {
            int try_1, try_2;
            restorePoint();
            removeNodes(s_2.getInclusiveNeighbourhood());
            try_1 = maximumIndependentSetSize();
            restore();
            removeNodes(s_1.getInclusiveNeighbourhood());
            removeNode(s_2);
            try_2 = maximumIndependentSetSizeWith2From(s_2.getNeighbourhood());
            mis = Math.max(try_1, try_2);
        }

        restore();
        return mis;
    }

    private int maximumIndependentSetSizeWith2From(Collection<Node> Scol) {
        List<Node> S = new ArrayList<>(Scol);
        int mis = 0;
        restorePoint();

        if (S.size() < 2) {
            mis = 0;
        } else if (S.size() == 2) {
            if (S.get(0).getNeighbourhood().contains(S.get(1)))
                mis = 0;
            else {
                removeNodes(S.get(0).getInclusiveNeighbourhood());
                removeNodes(S.get(1).getInclusiveNeighbourhood());
                mis = 2 + maximumIndependentSetSize();
            }
        } else if (S.size() == 3) {
            Node s_1 = S.get(0), s_2 = S.get(1), s_3 = S.get(2);
            if (s_1.getDegree() == 0) {
                removeNode(s_1);
                mis = maximumIndependentSetSizeWith1From(s_2, s_3);
            } else if (s_1.getNeighbourhood().contains(s_2) &&
                    s_2.getNeighbourhood().contains(s_3) &&
                    s_3.getNeighbourhood().contains(s_1)) {
                mis = 0;
            } else if (s_1.getNeighbourhood().contains(s_2) || s_1.getNeighbourhood().contains(s_3)){
                Node s_i, s_j, s_k;
                s_i = s_j = s_k = null;
                if (s_1.getNeighbourhood().contains(s_2) && s_1.getNeighbourhood().contains(s_3)) {
                    s_i = s_1; s_j = s_2; s_k = s_3;
                } else if (s_2.getNeighbourhood().contains(s_1) && s_2.getNeighbourhood().contains(s_3)) {
                    s_i = s_2; s_j = s_1; s_k = s_3;
                }  else if (s_3.getNeighbourhood().contains(s_1) && s_3.getNeighbourhood().contains(s_2)) {
                    s_i = s_3; s_j = s_1; s_k = s_2;
                }

                if (s_i != null) { // Case two edges
                    removeNodes(s_j.getInclusiveNeighbourhood());
                    removeNodes(s_k.getInclusiveNeighbourhood());
                    mis = 2 + maximumIndependentSetSize();
                } else if (s_1.getNeighbourhood().contains(s_2)) { // Case one edge
                    removeNodes(s_3.getInclusiveNeighbourhood());
                    mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_2);
                } else if (s_1.getNeighbourhood().contains(s_3)) { // Case one edge
                    removeNodes(s_2.getInclusiveNeighbourhood());
                    mis = 1 + maximumIndependentSetSizeWith1From(s_1, s_3);
                }
            } else if (s_2.getNeighbourhood().contains(s_3)) {
                // Case si-sj with i=2, j=3
                removeNodes(s_1.getInclusiveNeighbourhood());
                mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
            } else if (!s_1.neighbourhoodsDisjoint(s_2)) {
                removeNode(s_1.neighbourhoodIntersection(s_2).get(0));
                mis = maximumIndependentSetSizeWith2From(Scol);
            } else if (!s_1.neighbourhoodsDisjoint(s_3)) {
                removeNode(s_1.neighbourhoodIntersection(s_3).get(0));
                mis = maximumIndependentSetSizeWith2From(Scol);
            } else if (!s_2.neighbourhoodsDisjoint(s_3)) {
                removeNode(s_2.neighbourhoodIntersection(s_3).get(0));
                mis = maximumIndependentSetSizeWith2From(Scol);
            } else if (s_1.getDegree() == 1) {
                removeNodes(s_1.getInclusiveNeighbourhood());
                mis = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
            } else {
                int try_1, try_2;
                restorePoint();
                removeNodes(s_1.getInclusiveNeighbourhood());
                try_1 = 1 + maximumIndependentSetSizeWith1From(s_2, s_3);
                restore();
                removeNodes(s_2.getInclusiveNeighbourhood());
                removeNodes(s_3.getInclusiveNeighbourhood());
                removeNode(s_1);
                try_2 = maximumIndependentSetSizeWith2From(s_1.getNeighbourhood());
                mis = Math.max(try_1, try_2);
            }
        } else if (S.size() == 4) {
            Collections.sort(nodes);
            if (nodes.get(0).getDegree() <= 3) {
                mis = maximumIndependentSetSize();
            } else {
                Node s_1 = S.get(0);
                int try_1, try_2;
                removeNode(s_1);
                S.remove(s_1);
                try_1 = maximumIndependentSetSizeWith2From(S);
                removeNodes(s_1.getNeighbourhood());
                try_2 = 1 + maximumIndependentSetSize();
                mis = Math.max(try_1, try_2);
            }
        }

        restore();
        return mis;
    }

    private Graph findPartition() {
        if (nodes.isEmpty())
            return this;

        List<Node> seen = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(nodes.get(0));
        while (!queue.isEmpty()) {
            Node n = queue.remove();
            queue.addAll(n.getNeighbourhood().stream().filter(x -> !seen.contains(x)).collect(Collectors.toList()));
            seen.add(n);
        }

        return new Graph(seen);
    }

    /**
     * Add a Node
     * @param node
     */
    public void addNode(Node node) {
        this.nodes.add(node);
        for (Node n : node.getNeighbourhood())
            if (nodes.contains(n))
                if (!n.getNeighbourhood().contains(node))
                    n.getNeighbourhood().add(node);
        removedStack.peek().remove(node);
    }

    /**
     * Get a Node
     * @param i
     * @return
     */
    public Node getNode(int i) {
        return this.nodes.get(i);
    }

    /**
     * Remove a node
     * @param node
     */
    private void removeNode(Node node) {
        nodes.remove(node);
        for (Node n : node.getNeighbourhood())
            if (nodes.contains(n))
                n.getNeighbourhood().remove(node);
        removedStack.peek().add(node);
    }

    /**
     * Remove a list of nodes, and update all references
     * @param ns
     */
    private void removeNodes(Collection<Node> ns) {
        nodes.removeAll(ns);
        for (Node n : nodes)
            n.getNeighbourhood().removeAll(ns);
        removedStack.peek().addAll(ns);
    }

    private void restorePoint() {
        removedStack.push(new ArrayList<>());
    }

    private void restore() {
        List<Node> removed = removedStack.pop();
        Collections.reverse(removed);
        for (Node node : removed) {
            this.nodes.add(node);
            for (Node n : node.getNeighbourhood())
                if (nodes.contains(n))
                    if (!n.getNeighbourhood().contains(node))
                        n.getNeighbourhood().add(node);
        }
        removed.clear();
    }

    public int size() {
        return nodes.size();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("Graph:");
        for (Node n : nodes) {
            sb.append("\n  ").append(n).append(":   ");
            for (Node n2 : n.getNeighbourhood()) sb.append(" - ").append(n2);
        }
        return sb.toString();
    }
}