import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;


public class BF{

    ArrayList<ArrayList<BitSet>> statesList;
    Comparator<Node> comparator;
    PriorityQueue<Node> nodeQueue;
    ArrayList<BitSet> finalState;
    String order;
    char[] strategy;
    String solution="";
    boolean isSolved=false;
    int depth=0;
    int size;




    public ArrayList<ArrayList<BitSet>> getStatesList() {
        return statesList;
    }

    public void setStatesList(ArrayList<ArrayList<BitSet>> statesList) {
        this.statesList = statesList;
    }

    public PriorityQueue<Node> getNodeQueue() {
        return nodeQueue;
    }

    public void setNodeQueue(PriorityQueue<Node> nodeQueue) {
        this.nodeQueue = nodeQueue;
    }

    public ArrayList<BitSet> getFinalState() {
        return finalState;
    }

    public void setFinalState(ArrayList<BitSet> finalState) {
        this.finalState = finalState;
    }

    public String getOrder() {
        return order;
    }

    public void setOrder(String order) {
        this.order = order;
    }

    public char[] getStrategy() {
        return strategy;
    }

    public void setStrategy(char[] strategy) {
        this.strategy = strategy;
    }

    public String getSolution() {
        return solution;
    }

    public void setSolution(String solution) {
        this.solution = solution;
    }

    public boolean isSolved() {
        return isSolved;
    }

    public void setSolved(boolean isSolved) {
        this.isSolved = isSolved;
    }

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public BF(int size) {
        this.statesList = new ArrayList<ArrayList<BitSet>>();
        this.finalState = new ArrayList<BitSet>();
        this.comparator = new Sort();
        this.nodeQueue = new PriorityQueue<Node>(3000,comparator);
        this.size = size;
    }

    public void addToStatesList(ArrayList<BitSet> state)
    {
        statesList.add(state);

    }

    public void createFinalState()
    {
        if(this.size==4)
        {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(1);tmp.add(2);tmp.add(3);tmp.add(4);
            tmp.add(5);tmp.add(6);tmp.add(7);tmp.add(8);
            tmp.add(9);tmp.add(10);tmp.add(11);tmp.add(12);
            tmp.add(13);tmp.add(14);tmp.add(15);tmp.add(0);
            Converter con = new Converter(tmp);
            this.finalState = con.covertToBitSet();
        }
        else if (this.size==3)
        {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(1);tmp.add(2);tmp.add(3);
            tmp.add(4);tmp.add(5);tmp.add(6);
            tmp.add(7);tmp.add(8);tmp.add(0);
            Converter con = new Converter(tmp);
            this.finalState = con.covertToBitSet();
        }
    }

    public boolean isFinished(ArrayList<BitSet> st)
    {
        ArrayList<BitSet> tmp = new ArrayList<BitSet>(st);
        int comp=0;
        for(int i=0;i<tmp.size();i++)
        {
            if(tmp.get(i).toString().compareTo(finalState.get(i).toString())==0) comp++;
            else return false;

        }

        if(comp==tmp.size()) return true;
        else
            return false;
    }

    public int heuristic1(ArrayList<BitSet> st){
        ArrayList<BitSet> tmp = new ArrayList<BitSet>(st);
        int comp=0;
        for(int i=0;i<tmp.size();i++)
        {
            if(!(tmp.get(i).toString().compareTo(finalState.get(i).toString())==0)) comp++;
        }

        return comp;

    }

    public boolean isStateUnique(ArrayList<BitSet> tmp)
    {

        int comp;

        for(int j=0;j<statesList.size();j++)
        {
            comp=0;

            ArrayList<BitSet> tmp2 = new ArrayList<BitSet>(statesList.get(j));

            for(int i=0;i<tmp.size();i++)
            {
                if(tmp.get(i).toString().compareTo(tmp2.get(i).toString())==0) comp++;
            }

            if(comp==tmp.size())
            {
                return false;
            }
        }

        return true;
    }

    public int findEmpty(ArrayList<BitSet> st)
    {
        int zero=0;

        ArrayList<BitSet> tmp = st;

        for(int i=0;i<tmp.size();i++)
        {
            if(tmp.get(i).toString().compareTo("{}")==0) zero=i;

        }

        return zero;
    }


    public void searchBF(Node n){

        System.out.println("Glebokosc: "+(++depth));

        if(isSolved==false)
        {

            ArrayList<BitSet> newState;
            int zero;
            zero = findEmpty(n.nodeState);
            System.out.println("zero"+zero);

            if(zero%size!=0 &&isSolved==false)
            {
                System.out.println("L");
                newState = new ArrayList<BitSet>(n.nodeState);
                Collections.swap(newState, zero, zero-1);

                if(isStateUnique(newState)==true && isFinished(newState)==false)
                {
                    Node tmpNode = new Node(n.path+'L',n.path,statesList.get(statesList.size()-1), heuristic1(newState));
                    nodeQueue.add(tmpNode);

                }
                if(isFinished(newState)==true)
                {
                    isSolved=true;
                    solution=(n.path)+'L';
                    return;
                }
            }

            if((zero%size)!=(size-1) &&isSolved==false )
            {
                System.out.println("P");
                newState = new ArrayList<BitSet>(n.nodeState);
                Collections.swap(newState, zero, zero+1);

                if(isStateUnique(newState)==true && isFinished(newState)==false)
                {
                    System.out.println("PPPPP");
                    System.out.println(newState.toString());
                    Node tmpNode = new Node(n.path+'P',n.path,statesList.get(statesList.size()-1), heuristic1(newState));
                    System.out.println(heuristic1(newState));
                    nodeQueue.add(tmpNode);

                }
                if(isFinished(newState)==true)
                {
                    isSolved=true;
                    solution=(n.path)+'P';
                    return;
                }
            }

            if(zero >= size &&isSolved==false)
            {
                System.out.println("G");
                newState = new ArrayList<BitSet>(n.nodeState);
                Collections.swap(newState, zero, zero-size);

                if(isStateUnique(newState)==true && isFinished(newState)==false)
                {
                    System.out.println("GGGG");
                    System.out.println(heuristic1(newState));
                    Node tmpNode = new Node(n.path+'G',n.path,statesList.get(statesList.size()-1), heuristic1(newState));
                    nodeQueue.add(tmpNode);

                }
                if(isFinished(newState)==true)
                {
                    isSolved=true;
                    solution=(n.path)+'G';
                    return;
                }
            }


            if(zero < size*size-size &&isSolved==false)
            {

                System.out.println("D");
                newState = new ArrayList<BitSet>(n.nodeState);
                Collections.swap(newState, zero, zero+size);

                if(isStateUnique(newState)==true && isFinished(newState)==false)
                {
                    Node tmpNode = new Node(n.path+'D',n.path,statesList.get(statesList.size()-1), heuristic1(newState));
                    nodeQueue.add(tmpNode);

                }
                if(isFinished(newState)==true)
                {
                    isSolved=true;
                    solution=(n.path)+'D';
                    return;
                }
            }

            addToStatesList(n.nodeState);

            if(!nodeQueue.isEmpty()&& isSolved==false ){
                System.out.println("wracaj");
                searchBF(nodeQueue.poll());
            }
        }
        else return;
    }


}