/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package web;

import ejb.BestPaths;
import ejb.Cities;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.TreeMap;
import java.util.Vector;

/**
 *
 * @author zwergnase
 */
public class OptimumPath {
    List<Cities> citiesList;
    List<BestPaths> bestPathsList;
    TreeMap connections;
    Vector<Path> availablePaths;
    Long sourceId;
    Long destinationId;

    OptimumPath(Long source,Long destination,List<BestPaths> bp,List<Cities> ctl){
        System.out.println("constructing...");
        sourceId=source;
        destinationId=destination;
        bestPathsList=bp;
        citiesList=ctl;
        initialize();
        loadAllConnectionsFromDatabase();
        eliminateUnnecessaryConnections();
        computeAllDistances();
        findAllAlternativePaths();
        listAllProperPaths();
    }

    //allocates memory for the containers in this class
    void initialize(){
        System.out.println("initializing...");
        this.availablePaths=new Vector();
        this.connections=new TreeMap();
    }


    // initialize the connections map with all entries in the database
    private void loadAllConnectionsFromDatabase(){

        System.out.println("loading from database...");
        //NODE A

        // Typeler bir düzelsin paralel olsun.distance Integer mesela
        Iterator<BestPaths> i=bestPathsList.listIterator();
        while(i.hasNext())
        {
            // trace all entries in the database
            BestPaths bp=i.next();
            // get the id of the current city
            Long currentCityId=(Long)bp.getDeparturePlace();
            // if such a city is already inserted, update it
            if(connections.containsKey(currentCityId))
            {
                City alreadyInserted=(City)connections.get(currentCityId);
                alreadyInserted.connectedCities.addElement((Long)bp.getArrivalPlace());
                alreadyInserted.distances.addElement(((Float)bp.getDistance()).intValue());

            }
            else // make a new insertion
            {
                City currentCity=new City();
                currentCity.id=currentCityId;      //id
                Cities cityInDB=null;
                ListIterator<Cities> ci=citiesList.listIterator();
                while(ci.hasNext())
                {
                    Cities temp=ci.next();
                    //System.out.println(temp.getId());
                    //System.out.println(currentCityId);
                    if(temp.getId().equals(currentCityId))
                    {
                        cityInDB=temp;
                        break;
                    }

                }
                if(cityInDB==null)
                    System.out.println("HATAAAAAA");
                currentCity.name=cityInDB.getName();                        //name
                currentCity.x=((Float)cityInDB.getX_coor()).intValue();     //x_coor
                currentCity.y=((Float)cityInDB.getY_coor()).intValue();     //y_coor
                currentCity.connectedCities=new Vector();                   //vectors init
                currentCity.distances=new Vector();
                currentCity.connectedCities.addElement((Long)bp.getArrivalPlace());
                currentCity.distances.addElement(((Float)bp.getDistance()).intValue());
                connections.put(currentCityId, currentCity);                // insert to treeMap
            }

        }// end of while

//System.out.println("connectionsize " +connections.size());
    }// end of fnc
    /** eliminates the cities that cannot be in the alternative paths */
    private void eliminateUnnecessaryConnections(){
       System.out.println("eliminating unnecessary nodes...");
    // eliminate the cities that are not within the rectangle of source and destination 3 up 3 down
    Collection cities=connections.values();
    Iterator itr= cities.iterator();
    Vector idstodelete=new Vector();
        while(itr.hasNext())
        {
            City current=(City)itr.next();
             if(outOfAnalysis(current))
             {
                 idstodelete.addElement(current.id);
                 //System.out.println("deleting: "+current.id);
                 itr.remove();
             }
         }
    // eliminate it from the connected cities vector of each city and remove its distance
    itr= cities.iterator();
    int sizeoftodelete=idstodelete.size();
    while(itr.hasNext())// iteration of cities
    {
       City current= (City)itr.next();
       Vector conncities=current.connectedCities;
       Vector conndistances=current.distances;
       for(int j=0;j<sizeoftodelete;j++) //iteration of to delete
            if(conncities.contains(idstodelete.elementAt(j)))
            {
                int index=conncities.indexOf(idstodelete.elementAt(j));
               // System.out.println(index+" deleting: "+idstodelete.elementAt(j)+" and distance "+
                       // conndistances.elementAt(index) + " from: "+current.id);
                conndistances.remove(index);
                conncities.remove(index);
            }
    }

    }


    /** computes the shortest distance of all nodes from the target (BFS)*/
    private void computeAllDistances(){
        System.out.println("Computing shortest distances ...");

        //stack of BFS
        PriorityQueue stackOfCities=new PriorityQueue(1,new DistanceComparator());

    // source id and destination id are available but use them reversed for he sake of  k-best path algorithm

    City source=(City)connections.get(destinationId);
    source.distance=0;
    stackOfCities.add(source);

    while(stackOfCities.size()>0)
    {
        City currentCity=(City)stackOfCities.poll();
        //System.out.println("anlık city: "+currentCity.id);

        currentCity.visited=true;
        for(int i=0;i<currentCity.connectedCities.size();i++)
        {
            Long neighborId=(Long)currentCity.connectedCities.get(i);
            //System.out.println("komsu: "+neighborId);
            City neighbor=(City)connections.get(neighborId);
            if(!neighbor.visited)
            {
                // calculate the probable distance
                int probableDistance=currentCity.distance+(Integer)currentCity.distances.get(i);
                if(neighbor.distance==0 || neighbor.distance > probableDistance)
                {
                    if(stackOfCities.contains(neighbor))
                        stackOfCities.remove(neighbor);

                    neighbor.distance=probableDistance;
                    stackOfCities.add(neighbor);

                }
                else
                {
                    if(!stackOfCities.contains(neighbor))
                        stackOfCities.add(neighbor);
                }

            }
        }

       }
    }
    /** finds alternative paths in a range p=50% */


    private void findAllAlternativePaths(){
        System.out.println("finding all alternatives...");
        int range=((City)connections.get(sourceId)).distance*2;
        //System.out.println("range"+range);
        //hold paths here pair an id and path
        TreeMap<Integer,Path> Paths=new TreeMap();
        int pathNumber=0;

        //runtime vector
        Stack<stackElement> stck=new Stack();

        // initialization
        City source=(City)connections.get(sourceId);
        for(int i=0;i<source.connectedCities.size();i++)
        {
            City neighbor=(City)connections.get(source.connectedCities.elementAt(i));
            if((Integer)source.distances.get(i)+neighbor.distance<=range)
            {
                stackElement pe=new stackElement(pathNumber,sourceId,neighbor.id);
                //System.out.println("path: "+pathNumber+" city: "+sourceId+" neig: "+ neighbor.id+" pushed ");
                pe.distance=(Integer)source.distances.get(i);
                stck.add(pe);
                Path p= new Path();
                p.nodes=new Vector();
                p.id=pathNumber;
                Paths.put(p.id,p);

                pathNumber++;
            }
        } // initialization is completed

        pathNumber--;
        // main loop
        while(!stck.isEmpty())
        {
            //get the last element
            stackElement se=stck.pop();
            //System.out.println("currcity" +se.currentCityId + " nectcity "+se.nextCityId);
            //System.out.println(se.currentCityId+" "+ se.nextCityId+" popped");
            // get its path
            Path currentPath=Paths.get(se.pathid);
            // add the popped node to this path
            currentPath.nodes.addElement(se.currentCityId);


            // add neighbors of this node to the stack
            City currentCity=(City)connections.get(se.nextCityId);
            if(se.nextCityId.equals(destinationId))
             {
                currentPath.nodes.addElement(se.nextCityId);
                currentPath.distance=se.distance;
                availablePaths.add(currentPath);
                //System.out.println("yol: "+se.pathid+" distance: "+ se.distance);
                //currentPath.printPath();
                //Paths.remove(currentPath.id);
                continue;
            }


            int currentPathNumber=currentPath.id;
            boolean contributed=false;
            for(int i=0;i<currentCity.connectedCities.size();i++)
            {
              if(!currentPath.nodes.contains(currentCity.connectedCities.elementAt(i)))// if it is not in the prev path
              {
                    City neighbor=(City)connections.get(currentCity.connectedCities.elementAt(i));

                    if(se.distance+(Integer)currentCity.distances.get(i)+neighbor.distance<=range)
                    {

                        //stacke koyulacak yeni yol eklenecek
                        if(contributed)
                        {
                            pathNumber++;
                            stackElement se2=new stackElement(pathNumber,currentCity.id,neighbor.id);
                            //System.out.println("path: "+pathNumber+" city: "+currentCity.id+" neig: "+ neighbor.id+" pushed ");
                            se2.distance=se.distance+(Integer)currentCity.distances.get(i);
                            stck.add(se2);
                            Path p=currentPath.copyPath();
                            p.id=pathNumber;
                            Paths.put(p.id,p);
                        }
                        else // first node dont need to create a new path
                        {
                            stackElement se2=new stackElement(currentPathNumber,currentCity.id,neighbor.id);
                            //System.out.println("path: "+currentPathNumber+" city: "+currentCity.id+" neig: "+ neighbor.id+" pushed ");
                            se2.distance=se.distance+(Integer)currentCity.distances.get(i);
                            stck.add(se2);
                            contributed=true;

                        }

                    }
              }// else skip
            }//end of for

            if(!contributed)// it is dead end remove it from the map
            {
                Paths.remove(currentPath.id);
                //o path silinmeli
            }

        }


    }
    /** lists the proper solutions */
    private void listAllProperPaths()
    {
        //System.out.println("kac path var: "+availablePaths.size());
        for(int i=0;i<availablePaths.size();i++)
        {
            Path p=availablePaths.get(i);
            System.out.println("Path id: "+ p.id+" length: "+p.distance);
            p.printPath(connections);
        }

    }


    //TODO: better elimination can be made
    private boolean outOfAnalysis(City C)
    {
        City source=(City)connections.get(sourceId);
        City destination=(City)connections.get(destinationId);
        if(C.x< min(source.x-2,destination.x-2) ||C.x>max(source.x+2,destination.x+2) ||
                C.y<min(source.y-2,destination.y-2) || C.y>max(source.y+2,destination.y+2))
        return true;

        return false;
    }

    /*
    public static void main(String [ ] args){

        new OptimumPath(1,6);

    }*/

    private int min(int i, int j) {
        return (i<j) ? i:j;
    }

    private int max(int i, int j) {
        return (i>j)?i :j;
    }


}

class Path
{
    // an Long vector to hold the nodes in a path
    Vector<Long> nodes;
    int id;
    int distance;

    Path copyPath()
    {
        Path Path2=new Path();
        Path2.nodes=(Vector)this.nodes.clone();
        return Path2;
    }
    void printPath(TreeMap connections)
    {
        for(int i=0;i<nodes.size();i++)
        {
            if(i!=nodes.size()-1)
                System.out.print(((City)connections.get(nodes.get(i))).name+" -> ");
            else
                System.out.print(((City)connections.get(nodes.get(i))).name+" \n ");
        }
    }
}


class City
{
    /** database id of the city & key of the TreeMap*/
    Long id;
    /** x coordinate of the city */
    int x;
    /** y coordinate of the city */
    int y;
    /** shortest path from the target*/
    int distance=0;
    boolean visited=false;
    /** the Long vector of ids of the connected cities */
    Vector connectedCities;
    /** the integer vector of the distances from that city */
    Vector distances;
    /** the shortest distance from the target */
    String name;

}

class DistanceComparator implements Comparator<City>{

        public int compare(City c1, City c2){

            int c1dist =c1.distance ;
            int c2dist =c2.distance ;

            return (c1dist>c2dist) ? 1: ((c1dist<c2dist) ? -1 : 0);

            }

}

class stackElement
{
    int pathid;
    Long currentCityId;
    Long nextCityId;
    int distance;

    stackElement(int pi,Long cid,Long ncid)
    {
        pathid=pi;
        currentCityId=cid;
        nextCityId=ncid;

    }
    stackElement(){}
}