/**
 * Maria Sales N� 41748 MIEI
 * Ricardo Silva N� 37798 LEI
 */

import java.awt.Point;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Graph {
	
	private static final int DAYS = 7;
	
	private char[][] table;
	private int nRows;
	private HashMap<Integer,Integer> map;
	private List<Point>[] graph;

	public Graph(int nRows) {
		this.nRows = nRows;
		table = new char[nRows][DAYS];
		map = new HashMap<Integer,Integer>(DAYS*26+2);
	}

	public void add(char actividade, int row, int dia) {
		table[row][dia] = actividade;		
		
		if(actividade != '-'){
			int key = dia*10000 + Character.getNumericValue(actividade);
			
			if(!map.containsKey(key))
				map.put(key, map.size());
		}
	}

	@SuppressWarnings("unchecked")
	public void constructGraph(){
		
		Point current;
		int key;
		
		List<Point> aux = new LinkedList<Point>();;
		
		graph = new LinkedList[map.size()];
		
		for(int i = 0; i < map.size(); i++){
			graph[i] = new LinkedList<Point>();
		}
		
		for(int i = 0; i < nRows; i++){
			//aux = new LinkedList<Point>();
			
			aux.clear();
			for(int j = 0; j < DAYS; j++){
				if(table[i][j] != '-'){
					
					key = j*10000 + Character.getNumericValue(table[i][j]);
					
					current = new Point(map.get(key), j);
					for(Point n : aux)
					{						
						graph[n.x].add(new Point(current.x, j-n.y));
						graph[current.x].add(new Point(n.x, 7-(j-n.y)));
					}
					aux.add(current);
				}
			}
		}		
	}
		
	public int dijkstra(int origin, int destiny) {

		boolean[] selected = new boolean[map.size()];
		boolean[] appeared = new boolean[map.size()];
		int[] length = new int[map.size()];	
		
		for(int i = 0; i < map.size(); i++){
			length[i] = Integer.MAX_VALUE;
		}
		int key, min = Integer.MAX_VALUE;
		
		Queue<Point> connected = new PriorityQueue<Point>(DAYS, new ComparatorPoints());
		
		for(int i = 0; i < DAYS; i++){
			if(table[origin][i]!='-'){		
				
				key = i*10000 + Character.getNumericValue(table[origin][i]);
				key = map.get(key);
				connected.add(new Point(key,0));
				length[key] = 0;
			}
		}
			
		while(!connected.isEmpty()){

			Point vertex = connected.remove();
			if(!appeared[vertex.x]){
				appeared[vertex.x] = true;
				selected[vertex.x] = true;
				
				exploreVertex(vertex.x, selected, length, connected);
			}
		}
		
		
		for(int i = 0; i < DAYS; i++){
			if(table[destiny][i]!='-'){
				key = i*10000 + Character.getNumericValue(table[destiny][i]);		
				
				key = map.get(key);
								
				if(length[key] < min)
					min = length[key] ;
			}			
		}
		
		return min;
	}
	
	private void exploreVertex(int source, boolean[] selected, int[] length, Queue<Point> connected){
				
		int newLength;
		
		for(Point e: graph[source]){
			if(!selected[e.x]){
				newLength = length[source]+e.y;				
				if(newLength < length[e.x]){
					length[e.x] = newLength;
					connected.add(new Point(e.x, length[e.x]));				
				}
			}
		}
	}

}