///////////////////////////////////////////////////////////////////////////////
// For information as to what this class does, see the Javadoc, below.       //
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
// 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
// Ramsey, and Clark Glymour.                                                //
//                                                                           //
// This program is free software; you can redistribute it and/or modify      //
// it under the terms of the GNU General Public License as published by      //
// the Free Software Foundation; either version 2 of the License, or         //
// (at your option) any later version.                                       //
//                                                                           //
// This program is distributed in the hope that it will be useful,           //
// but WITHOUT ANY WARRANTY; without even the implied warranty of            //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             //
// GNU General Public License for more details.                              //
//                                                                           //
// You should have received a copy of the GNU General Public License         //
// along with this program; if not, write to the Free Software               //
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
///////////////////////////////////////////////////////////////////////////////

package edu.cmu.tetrad.search;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * **************************************************************************
 *
 * @author Trevor Burns
 * <p>
 * Provides a static method which implements a correct version of Reiter's hitting set algorithm as described by
 * Greiner, Smith, and Wilkerson in "A Correction to the Algorithm in Reiter's Theory of Diagnosis" Artificial
 * Intellegence 41 (1989) (see for detailed specification). However, this is not a general implementation, it is
 * tailored for use in the ION search by dealing with GraphChange objects instead of something more general.
 * <p>
 * Varies mainly in that no explicit DAG is constructed, it is only implied by the structure of the calls. This is
 * because this implementation is concerned solely with finding the hitting sets and once a node is processed its
 * information is never again accessed if one stores the necessary path of edge labels in newly constructed nodes.
 * <p>
 * There is one exception to the above claim. If one follows the revised algorithm strictly, in Enhancement Step 3 one
 * does need information from previous levels. The author decided this step was easier to code if one precomputes
 * instead of doing it on the fly, so this exception is inconsiquential.
 */
public class IonHittingSet {

    /**
     * takes a List of HashSets of GraphChanges, and returns a List of GraphChanges.
     */
    public static List<GraphChange> findHittingSet(List<Set<GraphChange>> Forig) {

        LinkedList<HsNode> currentLevel = new LinkedList<>();
        LinkedList<HsNode> nextLevel = new LinkedList<>();
        List<GraphChange> hittingSets = new ArrayList<>();
        List<Set<GraphChange>> F;

        /* Enhancement Step 3 */
        F = precompute(Forig);

        /* Revised Step 1 */
        currentLevel.addFirst(new HsNode(new GraphChange(), 0));

        /* Revised Step 2: Loop processes all of one level of nodes before
         * starting the next. Only breaks when there are no more nodes in
         * getModel and next levels */
        while (!currentLevel.isEmpty()) {
            HsNode n = currentLevel.removeFirst();

            /* check redundency here in case of new hitting sets since node creation */
            if (nodeRedundant(n, hittingSets)) {
            } // do nothing
            else {
                int nextUCSigma = findNextUCSigma(F, n);

                /* Path intersects with all elements of F, add to hittingSets */
                if (nextUCSigma == -1)
                    hittingSets.add(n.getPath());

                    /* Node is labeled with first non-intersection */
                else {
                    n.updateLabel(nextUCSigma);

                    /* All possible downward arcs examined; either added or ignored */
                    for (GraphChange nextLCSigma : (F.get(nextUCSigma))) {
                        GraphChange newPath = new GraphChange(n.getPath());

                        if (newPath.isConsistent(nextLCSigma)) {
                            newPath.union(nextLCSigma);
                            if (pathNecessary(newPath, nextLevel))
                                nextLevel.add(new HsNode(newPath, n.getLabel()));
                        }
                    }
                }
            }

            /* if there are no nodes left in the getModel level, continue onto the next */
            if (currentLevel.isEmpty()) {
                currentLevel = nextLevel;
                nextLevel = new LinkedList<>();
            }
        }
        return hittingSets;
    }


    /**
     * Implements one of the listed enhancements, checking if there is a node on the next level which already has the
     * new path. Returns true if a new node should be created with that path and false if a new node is unnecessary.
     */
    private static boolean pathNecessary(GraphChange path, LinkedList<HsNode> nextLevel) {
        boolean necessary = true;

        /* Enhancement Step 1 */
        for (HsNode m : nextLevel) {
            if ((m.getPath()).equals(path)) {
                necessary = false;
                break;
            }
        }

        return necessary;
    }


    /**
     * Implements one of the listed enhancements, checking if the path for the given node n contains a known hitting
     * set. Returns true if the node is redundant and false if the node should be processed.
     */
    private static boolean nodeRedundant(HsNode n, List<GraphChange> hittingSets) {
        boolean redundant = false;

        /* Enhancement Step 2 */
        for (GraphChange hs : hittingSets) {
            if (n.getPath().contains(hs)) {
                redundant = true;
                break;
            }
        }

        return redundant;
    }


    /**
     * Given a node and the List of HashSets returns the index of the first HashSet in F that the node does not
     * intersect or -1 if all are intersected
     */
    private static int findNextUCSigma(List<Set<GraphChange>> F, HsNode n) {
        /* nodes are created with their parent's labels to make this function faster */
        int index = n.getLabel();
        GraphChange path = n.getPath();

        /* loop through elements of F */
        for (; index < F.size(); index++) {
            Set<GraphChange> sigma = F.get(index);
            boolean intersect = false;

            for (GraphChange aSigma : sigma) {
                if (path.contains(aSigma)) {
                    intersect = true;
                    break;
                }
            }
            if (!intersect) return index;
        }
        return -1;
    }


    /**
     * Takes a List of HashSets of GraphChanges, returns the same. Runs through List linearly, checking against all
     * later HashSets in the List (both ways) marking supersets with the addition of an empty GraphChange. Supersets are
     * removed at the end in order to avoid the O(n) removal for each set individually. This effectively implements
     * Enhancement step 3, just not the on-the-fly way specified.
     */
    private static List precompute(List<Set<GraphChange>> F) {
        int size = F.size();
        List<Set<GraphChange>> pruned = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            Set<GraphChange> setI = F.get(i);

            for (int j = (i + 1); j < size; j++) {
                Set<GraphChange> setJ = F.get(j);
                /* if one set is already marked, the following check is unnecessary */
                boolean notMarked = !setJ.contains(new GraphChange());

                if (notMarked && setI.containsAll(setJ)) {
                    setI.add(new GraphChange());
                    break;
                } else if (notMarked && setJ.containsAll(setI))
                    setJ.add(new GraphChange());
            }

            if (!setI.contains(new GraphChange()))
                pruned.add(F.get(i));
        }
        return pruned;
    }


    /**
     * Structure for containing the pair of the path (potential hitting set) and label (index of element of F which is
     * first non-intersection). Allows for label updating on the assumption that the node will be created with its
     * parent's label, to be used for a more efficient run of findNextUCSigma
     */
    private static class HsNode {
        private GraphChange path;
        private int label;

        public HsNode(GraphChange path, int label) {
            this.path = path;
            this.label = label;
        }

        public void updateLabel(int label) {
            this.label = label;
        }

        public GraphChange getPath() {
            return path;
        }

        public int getLabel() {
            return label;
        }
    }
}