package nl.camilstaps.cs;

import nl.camilstaps.cs.graphs.Graph;
import nl.camilstaps.cs.graphs.Node;

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

/**
 * The garbage collection map is simply a Graph with extended functionality.
 *
 * @author Camil Staps
 */
class GarbageCollectionMap extends Graph {

    public GarbageCollectionMap() {
        super();
    }

    private GarbageCollectionMap(Graph g) {
        super(g);
    }

    /**
     * We want to choose a node with few neighbours, to minimise the branching factor at each reduction step.
     * @return the node with the fewest neighbours
     */
    protected Node bestNode() {
        Node best = null;
        for (Node n : nodes)
            if (best == null || best.getNeighbours().size() > n.getNeighbours().size())
                best = n;
        return best;
    }

    /**
     * Check if we can place N bins in this map.
     *
     *  - Choose the {@link #bestNode} and try if we can place N-1 bins if we remove this node and all its neighbours
     *  - If not, remove the node and try for all its neighbours the same thing.
     *  - If it doesn't work for the best node or for one of its neighbours, it is impossible to place N bins.
     *
     * @param bins the number of bins we want to place
     * @return whether this is possible
     */
    protected boolean canPlaceNBins(int bins) {
        if (this.nodes.size() < bins)
            return false;
        if (bins < 1)
            return true;

        // A queue with the nodes we want to check
        Queue<Node> q = new LinkedList<>();
        boolean first_go = true;

        q.add(bestNode());
        while (!q.isEmpty()) {
            Node n = q.remove();
            removeNode(n);

            // Recursively check the subgraph without the node we're checking and its children
            GarbageCollectionMap gcm = new GarbageCollectionMap(this);
            gcm.removeNodes(n.getNeighbours());
            if (gcm.canPlaceNBins(bins - 1))
                return true;

            // Check children
            if (first_go)
                q.addAll(n.getNeighbours().stream().filter(nodes::contains).collect(Collectors.toList()));

            // Restore graph
            addNode(n);
            nodes.remove(n);
            first_go = false;
        }

        return false;
    }

}