///////////////////////////////////////////////////////////////////////////////
// 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.mb;

import edu.cmu.tetrad.graph.Node;
import edu.cmu.tetrad.search.IndependenceTest;
import edu.cmu.tetrad.search.MbSearch;
import edu.cmu.tetrad.util.DepthChoiceGenerator;
import edu.cmu.tetrad.util.TetradLogger;

import java.util.*;

/**
 * Implements the Min-Max Markov Blanks (MMMB) algorithm as defined in Tsamardinos, Aliferis, and Statnikov, Time and
 * Sample Efficient Discovery of Markov Blankets and Direct Causal Relations (KDD 2003).
 *
 * @author Joseph Ramsey
 */
public final class Mmmb implements MbSearch {

    /**
     * True if the symmetric algorithm is to be used.
     */
    private boolean symmetric = false;

    /**
     * The independence test used to perform the search.
     */
    private IndependenceTest independenceTest;

    /**
     * The list of variables being searched over. Must contain the target.
     */
    private List<Node> variables;

    /**
     * The maximum number of variables conditioned on.
     */
    int depth = -1;

    /**
     * Number of independence tests.
     */
    private int numIndTests = 0;

    /**
     * The function from nodes to their sets of parents and children.
     */
    Map<Node, List<Node>> pc;

    /**
     * Set of trimmed nodes (for the symmetric implementation).
     */
    private Set<Node> trimmed;

    //=============================CONSTRUCTOR=============================//

    /**
     * Constructs.
     *
     * @param test      The independence test used in the search.
     * @param depth     The maximum number of variables conditioned on.
     * @param symmetric True if the symmetric algorithm is to be used.
     */
    public Mmmb(IndependenceTest test, int depth, boolean symmetric) {
        if (test == null) {
            throw new NullPointerException();
        }

        if (depth < -1) {
            throw new IllegalArgumentException();
        }

        this.independenceTest = test;
        this.variables = test.getVariables();
        this.depth = depth;
        this.symmetric = symmetric;

        pc = new HashMap<>();
        trimmed = new HashSet<>();
    }

    //=============================PUBLIC METHODS=========================//

    /**
     * Searches for the Markov blanket of the node by the given name.
     *
     * @param targetName The name of the target node.
     * @return The Markov blanket of the target.
     */
    public List<Node> findMb(String targetName) {
        TetradLogger.getInstance().log("info", "target = " + targetName);
        numIndTests = 0;
        long time = System.currentTimeMillis();

        pc = new HashMap<>();
        trimmed = new HashSet<>();

        Node target = getVariableForName(targetName);
        List<Node> nodes = mmmb(target);

        long time2 = System.currentTimeMillis() - time;
        TetradLogger.getInstance().log("info", "Number of seconds: " + (time2 / 1000.0));
        TetradLogger.getInstance().log("info", "Number of independence tests performed: " +
                numIndTests);
        //        System.out.println("Number of calls to mmpc = " + pc.size());

        return nodes;
    }

    //===========================PRIVATE METHODS==========================//

    private List<Node> mmmb(Node t) {
        // MB <- {}
        Set<Node> mb = new HashSet<>();

        Set<Node> _pcpc = new HashSet<>();

        for (Node node : getPc(t)) {
            List<Node> f = getPc(node);
            this.pc.put(node, f);
            _pcpc.addAll(f);
        }

        List<Node> pcpc = new LinkedList<>(_pcpc);

        Set<Node> currentMb = new HashSet<>(getPc(t));
        currentMb.addAll(pcpc);
        currentMb.remove(t);

        HashSet<Node> diff = new HashSet<>(currentMb);
        diff.removeAll(getPc(t));
        diff.remove(t);

        //for each x in PCPC \ PC
        for (Node x : diff) {
            List<Node> s = null;

            // Find an S such PC such that x _||_ t | S
            DepthChoiceGenerator generator =
                    new DepthChoiceGenerator(pcpc.size(), depth);
            int[] choice;

            while ((choice = generator.next()) != null) {
                List<Node> _s = new LinkedList<>();

                for (int index : choice) {
                    _s.add(pcpc.get(index));
                }

                numIndTests++;
                if (independenceTest.isIndependent(t, x, _s)) {
                    s = _s;
                    break;
                }
            }

            if (s == null) {
                System.out.println("S not found.");
//                mb.add(x);
                continue;
            }

            // y_set <- {y in PC(t) : x in PC(y)}
            Set<Node> ySet = new HashSet<>();
            for (Node y : getPc(t)) {
                if (this.pc.get(y).contains(x)) {
                    ySet.add(y);
                }
            }

            //  For each y in y_set
            for (Node y : ySet) {
                if (x == y) continue;

                List<Node> _s = new LinkedList<>(s);
                _s.add(y);

                // If x NOT _||_ t | S U {y}
                numIndTests++;
                if (!independenceTest.isIndependent(t, x, _s)) {
                    mb.add(x);
                    break;
                }
            }
        }

        mb.addAll(getPc(t));
        return new LinkedList<>(mb);
    }

    private List<Node> mmpc(Node t) {
        List<Node> pc = new LinkedList<>();
        boolean pcIncreased = true;

        // First optimization: Don't consider adding again variables that have
        // already been found independent of t.
        List<Node> indepOfT = new LinkedList<>();

        // Phase 1
        while (pcIncreased) {
            pcIncreased = false;

            MaxMinAssocResult ret = maxMinAssoc(t, pc, indepOfT);
            Node f = ret.getNode();
            List<Node> assocSet = ret.getAssocSet();

            if (f == null) {
                break;
            }

            numIndTests++;

            if (!independenceTest.isIndependent(f, t, assocSet)) {
                pcIncreased = true;
                pc.add(f);
            }
        }

        // Phase 2.
        backwardsConditioning(pc, t);

        TetradLogger.getInstance().log("details", "PC(" + t + ") = " + pc);
        //        System.out.println("PC(" + t + ") = " + pc);

        return pc;
    }

    /**
     * @return a supserset of PC, or, if the symmetric algorithm is used, PC.
     */
    public List<Node> getPc(Node t) {
        if (!pc.containsKey(t)) {
            pc.put(t, mmpc(t));
        }

        if (symmetric && !trimmed.contains(t)) {
            trimPc(t);
            trimmed.add(t);
        }

        return pc.get(t);
    }

    /**
     * Trims away false positives from the given node. Used in the symmetric algorithm.
     */
    private void trimPc(Node t) {
        for (Node x : new LinkedList<>(pc.get(t))) {
            if (!pc.containsKey(x)) {
                pc.put(x, mmpc(x));
            }

            if (!pc.get(x).contains(t)) {
                pc.get(t).remove(x);
            }
        }
    }

    private MaxMinAssocResult maxMinAssoc(Node t, List<Node> pc,
                                          List<Node> indepOfT) {
        Node f = null;
        List<Node> maxAssocSet = null;
        double maxAssoc = 0.0;

        for (Node v : variables) {
            if (t == v) continue;
            if (pc.contains(v)) continue;

            if (indepOfT.contains(v)) {
                continue;
            }

            List<Node> minAssoc = minAssoc(v, t, pc);
            double assoc = association(v, t, minAssoc);

            // If v is conditionally independent of t, don't consider it
            // again. Note if this code is right, then we have to use the
            // association test as an independence test... ugh.
            if (assoc < 1.0 - independenceTest.getAlpha()) {
                indepOfT.add(v);
            }

            if (assoc > maxAssoc) {
                maxAssocSet = minAssoc;
                maxAssoc = assoc;
                f = v;
            }
        }

        return new MaxMinAssocResult(f, maxAssocSet);
    }

    private List<Node> minAssoc(Node x, Node target, List<Node> pc) {
        double assoc = 1.0;
        List<Node> set = new LinkedList<>();

        if (pc.contains(x)) throw new IllegalArgumentException();
        if (pc.contains(target)) throw new IllegalArgumentException();
        if (x == target) throw new IllegalArgumentException();

        DepthChoiceGenerator generator =
                new DepthChoiceGenerator(pc.size(), depth);
        int[] choice;

        while ((choice = generator.next()) != null) {
            List<Node> s = new LinkedList<>();

            for (int index : choice) {
                s.add(pc.get(index));
            }

            // Second optimization. In line 4, condider only conditioning
            // sets that contain the last node added to PC.
            if (pc.size() > 0 && !s.contains(pc.get(pc.size() - 1))) {
                continue;
            }

            double _assoc = association(x, target, s);

            if (_assoc < assoc) {
                assoc = _assoc;
                set = s;
            }
        }

        return set;
    }

    private void backwardsConditioning(List<Node> pc, Node target) {
        for (Node x : new LinkedList<>(pc)) {
            List<Node> _pc = new LinkedList<>(pc);
            _pc.remove(x);
            _pc.remove(target);

            List<Node> minAssoc = minAssoc(x, target, _pc);

            numIndTests++;

            if (independenceTest.isIndependent(x, target, minAssoc)) {
                pc.remove(x);
            }
        }
    }

    private double association(Node x, Node target, List<Node> s) {
        numIndTests++;

        independenceTest.isIndependent(x, target, s);
        return 1.0 - independenceTest.getPValue();
    }

    public String getAlgorithmName() {
        return symmetric ? "MMMB-SYM" : "MMMB";
    }

    public int getNumIndependenceTests() {
        return numIndTests;
    }

    private Node getVariableForName(String targetName) {
        Node target = null;

        for (Node V : variables) {
            if (V.getName().equals(targetName)) {
                target = V;
                break;
            }
        }

        if (target == null) {
            throw new IllegalArgumentException(
                    "Target variable not in dataset: " + targetName);
        }

        return target;
    }

    private static class MaxMinAssocResult {
        private Node node;
        private List<Node> assocSet;

        public MaxMinAssocResult(Node node, List<Node> assocSet) {
            this.node = node;
            this.assocSet = assocSet;
        }

        public Node getNode() {
            return node;
        }

        public List<Node> getAssocSet() {
            return assocSet;
        }
    }
}





