package aed.caminos;

import es.upm.aedlib.Entry;
import es.upm.aedlib.positionlist.PositionList;
import es.upm.aedlib.positionlist.NodePositionList;
import es.upm.aedlib.set.Set;
import es.upm.aedlib.set.PositionListSet;
import es.upm.aedlib.priorityqueue.PriorityQueue;
import es.upm.aedlib.priorityqueue.HeapPriorityQueue;
import es.upm.aedlib.map.Map;
import es.upm.aedlib.map.HashTableMap;
import es.upm.aedlib.graph.Edge;
import es.upm.aedlib.graph.Vertex;
import es.upm.aedlib.graph.DirectedGraph;
import es.upm.aedlib.graph.DirectedAdjacencyListGraph;


public class Transportistas {
  private DirectedGraph<Point,Integer> graph;
  private Map<Point,Vertex<Point>> points2vertices = new HashTableMap<Point,Vertex<Point>>();

  private int coste(Point a, Point b, Integer[][] map) {
	  return Math.max(map[b.getX()][b.getY()] - map[a.getX()][a.getY()], 0) + 1;
  }

  public Transportistas(Integer[][] map) {
	  graph = new DirectedAdjacencyListGraph<Point,Integer>();
	  for(int i = 0; i< map[0].length; i++) {
		  for(int j = 0; j< map.length; j++) {
			  if(map[j][i] != null) {
				  Point temp = new Point(j,i);
				  points2vertices.put(temp, graph.insertVertex(temp));

			  }
		  }
	  }
	  for(Vertex<Point> p : graph.vertices()) {
		  int x = p.element().getX();
		  int y = p.element().getY();
		  for(Vertex<Point> v : graph.vertices()) {
			  int otherX = v.element().getX();
			  int otherY = v.element().getY();
	         if(otherX == (x+1) && otherY == y){
	        	 graph.insertDirectedEdge(p, v, coste(p.element(), v.element(),map));
	         }
	         if(otherX == (x-1) && otherY == y){
	        	 graph.insertDirectedEdge(p, v, coste(p.element(), v.element(),map));
	         }
	         if(otherX == (x) && otherY == (y+1)){
	        	 graph.insertDirectedEdge(p, v, coste(p.element(), v.element(),map));
	         }
	         if(otherX == (x) && otherY == (y-1)){
	        	 graph.insertDirectedEdge(p, v, coste(p.element(), v.element(),map));
	         }



	      }

      }

  }

  public PositionList<Point> pathFromTo(Point fromPoint, Point toPoint) {
   PositionList<Point> res = new NodePositionList<Point>();
   Set<Edge<Integer>> lista = new PositionListSet<Edge<Integer>>();
   search(points2vertices.get(fromPoint), points2vertices.get(toPoint), lista);
   for(Edge<Integer> v : lista) {
	   res.addLast(graph.endVertex(v).element());
   }
   res.addFirst(fromPoint);

   if(res.isEmpty())
	   res = null;
   return res;
  }

  private Set<Edge<Integer>> search(Vertex<Point> inicial, Vertex<Point> ultimo ,Set<Edge<Integer>> lista){
	 if(inicial==ultimo)
		 return lista;
	 if(lista.contains(graph.outgoingEdges(inicial)))
		 return null;
	 for(Edge<Integer> v : graph.outgoingEdges(inicial)) {
		 lista.add(v);
		 if(search(graph.endVertex(v),ultimo,lista) != null)
			 return lista;
		 else
			 lista.remove(v);
	 }
	  return lista;
  }

  public PositionList<Point> bestPathFromTo(Point fromPoint,Point toPoint) {
    return null;
  }
}