package kui;

import java.util.ArrayList;
import java.util.List;

public class AStar extends InformedSearchingAlgorithm
{
    
/******************************************************************************/
    /**
     * Pomocná třída - do seznamu opened
     */
    class polozka
    {
        Node uzel;
        double h;
        double g;

        public polozka(Node uzel,double g, double h)
        {
            this.uzel=uzel;
            this.g=g;
            this.h=h;            
        }

        public Node   vratitUzel(){return uzel;}
        public double vratitGplH(){return g+h;}
        public double vratitG()   {return g;}
        public double vratitH()   {return h;}
    }

/******************************************************************************/
    /**
     * Pomocná třída pro uchování vlastnosti následovník - předchůdce
     */
    class uzelApredek
    {
        Node u,p;
        public uzelApredek(Node uzel,Node predek)
        {
            u=uzel;p=predek;
        }

        public Node vratitUzel() {return u;}
        public Node vratitPredka(){return p;}
    }

/******************************************************************************/
    ArrayList<Node> closed=new ArrayList();
    ArrayList<polozka> opened=new ArrayList();

    List<Node> hotovaCesta=new ArrayList();
    List<Node> expandovaneUzly;

    ArrayList<uzelApredek> uzelAjehoPredek=new ArrayList();
    
/******************************************************************************/
    /*
     * Vzdálenost     
     */
    private double velikostVektoru(double x,double y)
    {
        return Math.hypot(x,y);
    }

/******************************************************************************/
    /**
     * HLavní metoda celého algoritmu
     */
    @Override
    public List<Node> findWay(Node startNode, Node endNode)
    {
        /* STRUKTURA A nápad:
         * expanduji uzly, propočítám každému vzálenost od předka a vzdálenost do cíle
         * vložím do opened,
         * z opened vybírám prvek s nejmenší hodnotou
         * po otevření potomků, daný uzel přidám do množiny closed
         */

        //vynulujeme
        opened.clear();
        closed.clear();
        hotovaCesta.clear();
        //do opened přidáme startovní uzel
        opened.add( new polozka(startNode,0,0) );

        
        //nyní už jen cyklicky projdeme tak dlouho než najdeme cíl        
        polozka p;       //zpracovávaná položka
        Node zpracovany; //zpracovávaný uzel - ze zpracovávané položky


        
        double Ex=endNode.getX(),Ey=endNode.getY(); //END x,y - pozice koncového uzlu
        double x,y; //pozice současného uzlu
        double Sx=startNode.getX(),Sy=startNode.getY();
        
        double vzdalenostOdKonce;
        double vzdalenostOdPredka;
        double vzdalenostOdStartu;
         double vzdalenostOdStartu2;

        boolean uspech;


        

        
        //dokud máme co procházet, budeme tak činit
        while( !opened.isEmpty() )
        {
            //Fáze 1: najdu prvek s nejlepší vlastností, pokud je to cíl, ukončím algoritmus
            p=vratitPolozku();
            zpracovany=p.vratitUzel();

            if( zpracovany.isTarget() )break;

            //Fáze 2: odebereme uzel z otevřených, expandujeme uzel, dáme ho do closed
            opened.remove(p);
            closed.add(zpracovany);
            expandovaneUzly=zpracovany.expand();

            //Fáze 3: projdeme expandované uzly, pokud je closed, přeskočíme
            x=zpracovany.getX();y=zpracovany.getY();
            vzdalenostOdStartu=velikostVektoru(Sx-x,Sy-y);
            
            for(Node n:expandovaneUzly)
            {
                uspech=false;
                if( !closed.contains(n) )
                {
                    //Fáze 4 - spočteme vzdálenost, pokud uzel není open, dáme ho tam
                    vzdalenostOdPredka=velikostVektoru(x-n.getX(),y-n.getY());
                    vzdalenostOdKonce=velikostVektoru(n.getX()-Ex,n.getY()-Ey);
                    vzdalenostOdStartu2=velikostVektoru(n.getX()-Sx,n.getY()-Sy);

                    polozka pp;                    
                    pp=jeVopened(n);

                    if(pp==null)
                    {
                        //přidáme do opened
                        uzelAjehoPredek.add(0, new uzelApredek(n,zpracovany) );
                        opened.add( new polozka(n,p.vratitG()+vzdalenostOdPredka,vzdalenostOdKonce));
                        uspech=true;
                    
                    }else if( p.vratitG()+vzdalenostOdPredka<pp.vratitG() ){
                        //tento je lepší než ten samý v opnede, nahradíme
                        opened.remove(pp);
                        pp=( new polozka(n,p.vratitG()+vzdalenostOdPredka,vzdalenostOdKonce));
                        uzelAjehoPredek.add(0, new uzelApredek(n,zpracovany) );
                        opened.add(pp);
                    }

                    //
                }

            }
           

        }

        //nyní již jen sestavíme zpětně cestu
        Node u=endNode;

        //jdeme do předchůdce
        while( !u.equals(startNode) )
        {
            hotovaCesta.add(0,u); //přidáme uzel
            u=najitPredka(u);   //najdeme jeho předchůdce
        }
        //nakonec přidáme startovní uzel
        hotovaCesta.add(0,startNode);

        //
        return hotovaCesta;
    }


/******************************************************************************/
    /**
     * Test je li uzel v opened
     */
    private polozka jeVopened(Node n)
    {
        for(polozka p:opened)
        {
            if(p.vratitUzel().equals(n))return p;
        }
        //
        return null;
    }

/******************************************************************************/
    /**
     * Projdeme, hledáme minimum k cíli
     */
    private polozka vratitPolozku()
    {
        double min=Double.POSITIVE_INFINITY;
        polozka pol=null;
        //
        for(polozka p: opened)
        {
            if(p.vratitGplH()<min)
            {
                min=p.vratitGplH();
                pol=p;
            }
        }
        //odebereme z opened
        opened.remove(pol);
        //
        return pol;
    }

/******************************************************************************/
    /**
     * Funkce, která vrátí předka daného uzlu
     */
    private Node najitPredka(Node u)
    {
        for(uzelApredek n:uzelAjehoPredek)
        {
            if( n.vratitUzel().equals(u) )
            {
                return n.vratitPredka();
            }
        }
        //neúspěch
        return null;
    }

}