// License: GPL. For details, see LICENSE file.
package org.openstreetmap.josm.plugins.JunctionChecker.junctionchecking;

import static org.openstreetmap.josm.tools.I18n.tr;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

import org.openstreetmap.josm.gui.progress.ProgressMonitor;
import org.openstreetmap.josm.plugins.JunctionChecker.datastructure.Channel;
import org.openstreetmap.josm.plugins.JunctionChecker.datastructure.ChannelDiGraph;

/**
 * Testet, dass ein subgraph keine kleinere Junction enth�lt
 * @author  Jörg Possin, Simon Scheider
 */
public class JMinimality {

    private boolean CheckMinimal = true;
    private final ArrayList<Channel> E;
    private final int[][] Grid;
    private final ArrayList<Channel> OrEn;
    private final ArrayList<Channel> OrEx;
    private final int n;
    private final List<List<Object>> L = new ArrayList<>(); //The list of columns to be sorted
    private final HashSet<Channel> subgraph = new HashSet<>(); //The candidate subgraph to be tested
    private ProgressMonitor pm;
    private final boolean pmenabled;
    private final ArrayList<HashSet<Channel>> junctions = new ArrayList<>();
    private final boolean searchFirstJunction;
    private final ArrayList<Channel> subJunction = new ArrayList<>();
    private final JPrepare jprepare;
    private boolean Check = false;
    private Iterator<int[]> it;

    public JMinimality(int[][] Grid, int n,
            ArrayList<Channel> E,
            ArrayList<Channel> entries,
            ArrayList<Channel> exits,
            ChannelDiGraph channeldigraph,
            boolean junctionsearch) {

        this.E = E;
        this.n = n;
        this.Grid = Grid;
        this.OrEn = entries;
        this.OrEx = exits;
        this.pmenabled = false;
        this.searchFirstJunction = junctionsearch;
        this.jprepare = new JPrepare(channeldigraph);
    }

    public JMinimality(int[][] Grid, int n,
            ArrayList<Channel> E,
            ArrayList<Channel> entries,
            ArrayList<Channel> exits,
            ChannelDiGraph channeldigraph,
            ProgressMonitor pm,
            boolean junctionsearch) {

        this.E = E;
        this.n = n;
        this.Grid = Grid;
        this.OrEn = entries;
        this.OrEx = exits;
        this.pm = pm;
        this.pmenabled = true;
        this.searchFirstJunction = junctionsearch;
        this.jprepare = new JPrepare(channeldigraph);
        //this.jCheck= new JCheck();
    }

    public void GenerateSubcolumns() { //Generates all combinations of subcolumns in the grid
        if (pmenabled) {
            pm.setCustomText(tr("generate all combinations from entrie/exit candidates"));
        }

        Combination c = new Combination(Grid.length, n);
        //EEovern = (int) Combination.Choose(Grid.length*Grid.length, n*n);
        long ans = c.Choose(); //This is the number of subcolumns to be generated
        int[][] v; // this is a column variable containing n y-index entries plus true false values (0/1)
        List<Object> C; //The column is packed together with 2 indices into this variable
        for (int i = 0; i < Grid.length; i++) {
            int h = 0;    //this is the index denoting the "n out of Grid.length"- combination, indicating a subcolumn of length n
            do {
                int missing = 0;
                C = new ArrayList<>(3);
                v = new int[n][2];
                C.add(i); //the first position of column variable C is the column index
                C.add(h); //the second is the entry-subset index
                for (int t = 0; t < c.data.length; t++) {
                    if (Grid[(int) c.data[t]][i] == 0) {
                        missing++;
                        v[t][1] = 0; //false
                    } else {
                        v[t][1] = 1;
                    } //true
                    v[t][0] = (int) c.data[t];    //Write a y index of the combination into column
                }
                if (missing <= 1) { //If column has at most one missing entry
                    C.add(v); //insert column as the third position of column variable C
                    L.add(C); //Insert C in list to be ordered
                }
                h++; //Iterate through all subcolumns
                if (h < ans) {
                    c = c.Successor(); //generate the next combination
                }
            } while (h < ans);
            c = new Combination(Grid.length, n); //For each original column in the grid, generate new subcolumns
        }
        Collections.sort(L, new Comparator<List<Object>>() {
            @Override
            public int compare(List<Object> o1, List<Object> o2) {
                return (Integer) o1.get(1) - (Integer) o2.get(1); //sort according to h index in each column
            } });
    }

    public boolean IterateThroughKn() { //Iterates through all K_{n-1} subgrids of the Grid and tests them
        if (L.size() == 0) {
            return true;
        }
        if (pmenabled) {
            pm.setTicksCount(L.size());
            pm.setCustomText("Iterates through all K_{n-1} subgrids of the Grid and tests them");
        }
        Combination c;
        Iterator<List<Object>> l = L.listIterator();
        List<Object> C;
        ArrayList<int[]> CandidateK = new ArrayList<>(n*n); //saves the candidate K_{n-1} in entry-exit pairs
        long lindex = 0;
        int h = 0;
        int m = 0;
        int[][] v;
        int x_i;
        int y_j;
        int progressmonitorcounter = 1;
        boolean mchanged = false;
        boolean hchanged = false;
        C = l.next();
        do { //Loop over list of columns L
            if (mchanged) {
                C = l.next(); //Iterator in L
                lindex++; //Index in L
                if (hchanged) {
                    m = 1;
                    hchanged = false;
                }
            }
            if ((Integer) C.get(1) == h && l.hasNext()) { //m counts the set of columns with index h
                m++;
                mchanged = true;
            } else {
                if (l.hasNext() == false) {
                    m++;
                    lindex++;
                } //At the end of L, counter are set one up
                c = new Combination(m, n);
                long ans = c.Choose();
                int missing = 0;
                boolean smallerjunction = false;
                //Makes sure that subset of m columns contains an n*n subgrid, because ans = m over n would be 0 otherwise
                for (int k = 0; k < ans; k++) {
                    for (int y = 0; y < n; y++) { //Iterates over all rows of subgrid k
                        missing = 0;    //test = "";
                        for (int x = 0; x < c.data.length; x++) { //Iterates over all columns of subgrid k
                            x_i = ((Integer) L.get((int) (lindex-m+c.data[x])).get(0)); //columnindex in grid
                            v = ((int[][]) L.get((int) (lindex-m+c.data[x])).get(2)); //subcolumn of grid
                            y_j = v[y][0]; //rowindex in grid
                            if (v[y][1] == 0) {
                                missing++;
                            } else {
                                CandidateK.add(new int[]{y_j, x_i});
                            } //save entry/exit tuple
                            if (!smallerjunction && (!OrEn.contains(E.get(v[y][0]))
                                    && !OrEx.contains(E.get(x_i)))) { // Tests, whether y or x is not an original entry/exit
                                smallerjunction = true; //Then k identifies a different junction than the original one
                            }
                            //test = test+" ("+y_j+", "+x_i+", "+v[y][1]+")";
                        }
                        if (missing > 1) {
                            break;
                        } //If a row has more than one missing value, break
                    }
                    if (missing <= 1 && smallerjunction) { //The k-subgrid is a different junction candidate satisfying total reachability
                        CheckMinimal = !CheckSmallJunction(CandidateK); // If the candidate is a smaller junction, then minimality is false
                        //log.info("durchlauf: " + durchlauf + " Wert von CheckMinimal: " + CheckMinimal);
                        if (!CheckMinimal) {
                            break;
                        }
                    }
                    CandidateK.clear();
                    if (k+1 < ans) {
                        c = c.Successor();
                    } //Produces the m over n combinations
                }
                m = 1; //Sets m to the first column with next index h+1
                h++;
                mchanged = false;
                hchanged = true;
            }
            if (pmenabled) {
                progressmonitorcounter++;
                pm.setTicks(progressmonitorcounter);
            }
        }
        while (l.hasNext() && CheckMinimal);
        return CheckMinimal;
    }

    /**
     * gibt true zurück, wenn Kandidat eine Kreuzung ist, aber nicht, wenn junctionsearch auf true gesetzt ist
     */
    public boolean CheckSmallJunction(ArrayList<int[]> CandidateK) {
        Check = false;
        subgraph.clear(); //Zu konstruierender Subgraph
        it = CandidateK.iterator();
        //Reconstruct small Junction from paths
        while (it.hasNext()) {
            int[]point = it.next();
            for (int j = 0; j < E.get(point[0]).getReachableNodes().size(); j++) {
                if (E.get(point[0]).getReachableNodeAt(j).equals(E.get(point[1]))) {
                    subgraph.addAll(E.get(point[0]).getPathsAt(E.get(point[0]).getReachableNodeAt(j)));
                    subgraph.add(E.get(point[0]));
                }
            }
        }
        jprepare.jPrepare(new ArrayList<>(subgraph));
        JCheck jCheck = new JCheck();
        Check = jCheck.jCheck(jprepare.getEntries(), jprepare.getExits(), n);
        jprepare.resetSubgraph();
        if (Check) {
            subJunction.clear();
            subJunction.addAll(subgraph);
            //soll mehr als ein Kandidat gesucht werden? Dann Kandidaten speichern und Check wieder auf false stellen, damit die Hauptschleife weitergeht
            if (!searchFirstJunction) {
                boolean isin = false;
                for (int i = 0; i < junctions.size(); i++) {
                    //log.debug("Kreuzung " + i +" hat Channels: " + junctions.get(i).size() + " subgraph: " + subgraph.size());
                    if (junctions.get(i).size() == subgraph.size()) {
                        Iterator<Channel> it = subgraph.iterator();
                        isin = true;
                        while (it.hasNext()) {
                            if (!junctions.get(i).contains(it.next())) {
                                isin = false;
                                //log.info("nicht drin");
                            }
                        }
                    }
                }
                if (isin == false) {
                    junctions.add(new HashSet<>(subgraph));
                    //log.info("Kreuzungskandidat der Liste zugefügt" + junctions.size());
                }
                Check = false;
            }
        }
        return Check;
    }

    /**
     * enthält alle Channels des zuletzt durchlaufenden Kreuzungskandidaten (muß keine gültige Kreuzung sein)
     */
    public ArrayList<Channel> getSubJunctionCandidate() {
        return new ArrayList<>(subgraph);
    }

    /**
     * gibt alle gefundenen Kreuzungskandidaten zurück (ist leer, wenn junctionsearch auf true gesetzt wurde)
     */
    public ArrayList<HashSet<Channel>> getJunctionCandidates() {
        return junctions;
    }
}
