import java.util.*;


public class Algorithm {
    List<Vertex> openList;
    boolean[] closedList;
    Vertex[] vArray;
    Vertex root;
    List<String> output=new ArrayList<String>();

    public Algorithm(List<Vertex> vertexes, List<Edge> edges, int startID){
        openList=new ArrayList<Vertex>();
        output=new ArrayList<String>();

        closedList=new boolean[vertexes.size()+1];

        for(int i=0; i<closedList.length; i++){
            closedList[i]=false;
        }

        vArray=new Vertex[vertexes.size()+1];

        for(Vertex v:vertexes){
            vArray[v.id]=v;

        }
        root=vArray[startID];
        openList.add(root);
    }
    public void pedigree(Vertex w){
    //  System.out.println(w.id);
        output.add(0, String.valueOf(w.id));
        if(w.father!=root){
            pedigree(w.father);
        } else {
    //      System.out.println(root.id);
            output.add(0, String.valueOf(root.id));
        }
    }

    public void toOutput(){
        for(String s:output){
            System.out.println(s);
        }
    }

    public void BFS(){
        while(true){
            Vertex work=openList.remove(0);

            if(work.isTarget){
                pedigree(work);
                break;
            }


            closedList[work.id]=true;

            List<Integer> workList=new ArrayList<Integer>();
            Collections.sort(workList);
            for(Edge e:work.edges){
                if(e.id1==work.id){
                    Vertex temp=vArray[e.id2];
                    if(!closedList[temp.id]){
                        temp.father=work;
                        workList.add(temp.id);
                    }

                } else {
                    Vertex temp=vArray[e.id1];
                    if(!closedList[temp.id]){
                        temp.father=work;
                        workList.add(temp.id);
                    }
                }
            }
            /*if(openList.size()<5){
                System.out.println("sort előtt:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            Collections.sort(workList);
            Collections.reverse(workList);
            /*if(openList.size()<5){
                System.out.println("sort után:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            for(Integer i:workList){
                for(int j=1; j<vArray.length; j++){
                    if(i==vArray[j].id){
                        openList.add(vArray[j]);
                    }
                }
            }

        }
    }

    public void DFS(){
        while(true){
            Vertex work=openList.remove(0);

            if(work.isTarget){
                pedigree(work);
                break;
            }


            closedList[work.id]=true;

            List<Integer> workList=new ArrayList<Integer>();
            Collections.sort(workList);
            for(Edge e:work.edges){
                if(e.id1==work.id){
                    Vertex temp=vArray[e.id2];
                    if(!closedList[temp.id] && !openList.contains(temp)){
                        temp.father=work;
                        workList.add(temp.id);
                    }

                } else {
                    Vertex temp=vArray[e.id1];
                    if(!closedList[temp.id] && !openList.contains(temp)){
                        temp.father=work;
                        workList.add(temp.id);
                    }
                }
            }
            /*if(work.id==343){
                System.out.println("sort előtt:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            Collections.sort(workList);
            Collections.reverse(workList);
            /*if(work.id==343){
                System.out.println("sort után:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            for(Integer i:workList){
                for(int j=1; j<vArray.length; j++){
                    if(i==vArray[j].id){
                        openList.add(0, vArray[j]);
                    }
                }
            }

        }
    //  System.out.println("apa:"+vArray[363].father.id);
    }

    public void UCS(){
        while(true){
            Vertex work=openList.get(0);
            for(Vertex v:openList){
                if(work.weight>v.weight)
                    work=v;
            }
            openList.remove(work);

            if(work.isTarget){
                pedigree(work);
                break;
            }

            closedList[work.id]=true;

            for(Edge e:work.edges){
                Vertex temp;
                if(e.id1==work.id){
                    temp=vArray[e.id2];
                } else {
                    temp=vArray[e.id1];
                }
                if(!closedList[temp.id]){
                    if(!openList.contains(temp)){
                        temp.father=work;
                        temp.weight=work.weight+e.weight;
                        openList.add(temp);
                    } else {
                        if(temp.weight>(work.weight+e.weight)){
                            temp.weight=work.weight+e.weight;
                        }
                    }
                }
            }
            /*if(openList.size()<5){
                System.out.println("sort előtt:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            /*if(openList.size()<5){
                System.out.println("sort után:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/

        }
    }

    public void GBFS(int heuristic){
        while(true){
            Vertex work=openList.get(0);
            for(Vertex v:openList){
                if(work.weight>v.weight)
                    work=v;
            }
            openList.remove(work);

            if(work.isTarget){
                pedigree(work);
                break;
            }

            closedList[work.id]=true;

            for(Edge e:work.edges){
                Vertex temp;
                if(e.id1==work.id){
                    temp=vArray[e.id2];
                } else {
                    temp=vArray[e.id1];
                }
                if(!closedList[temp.id]){
                    if(!openList.contains(temp)){
                        temp.father=work;
                        temp.weight=work.weight+e.weight;
                        openList.add(temp);
                    } else {
                        if(temp.weight>(work.weight+e.weight)){
                            temp.weight=work.weight+e.weight;
                        }
                    }
                }
            }
            /*if(openList.size()<5){
                System.out.println("sort előtt:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/
            /*if(openList.size()<5){
                System.out.println("sort után:");
                for(Integer i:workList){
                    System.out.println(i);
                }
                System.out.println();
            }*/

        }
    }

    public void AStar(int heuristic){

    }
}