package shiyan3;




import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;



public class Map implements Serializable {
private List2D map;
private ArrayList<String> idList;
public Map(){
	map=new List2D();
	idList=new ArrayList<String>();
}
public void addDot(String id,int[] length){
	map.addDot(length);
	idList.add(id);
}
public void addDot(){
	map.addDot();
}
public void addLine(int dot1,int dot2,int length){
	map.addLine(dot1, dot2, length);
}
public void deleteDot(int index){
	map.deleteDot(index);
	idList.remove(index);
}
public void deleteDot(String id){
	int index=idList.indexOf(id);
	idList.remove(index);
}
public int getSize(){
	return map.size();
	
}
public ArrayList<Integer> getArray(int index){
	return map.getArray(index);
}
public ArrayList<Integer> getPath(int dot1,int dot2){
	ArrayList<Integer> preDot=new ArrayList<Integer>();//記錄先序點
	ArrayList<Integer> d=new ArrayList<Integer>();//記錄最短距離
    ArrayList<Integer> dotArray=new ArrayList<Integer>();
	for (int i = 0; i < map.size(); i++) {//初始化predot
		preDot.add(-1);
		d.add(-1);
		if(map.getLength(dot1, i)>0){
		dotArray.add(i);
	}}
	preDot.set(dot1, dot1);
	d.set(dot1, 0);
	
	
	/*依次取出與已經確定最短路徑相連并且還沒有確定最小路徑的點中，
	 * 計算（d+這個路徑）并找到最短的那條加到以確定路徑的數組中，
	 * 依次計算，直到dot2也在這個數組中為止
	 */
	
	while(preDot.get(dot2)==-1){
	int minD=Integer.MAX_VALUE;
	int indexj=-1;
	int indexi=-1;
	for (int i = 0; i < map.getArray(0).size(); i++) {
		
		if (d.get(i)!=-1) {
			for (int j = 0; j < map.getArray(i).size(); j++) {
				if (map.getArray(i).get(j)!=-1&&d.get(j)==-1&&d.get(i)

+map.getLength(i, j)<minD) {
					minD=d.get(i)+map.getLength(i, j);
					indexj=j;
					indexi=i;
				}
			}
		}
		
	}
	preDot.set(indexj, indexi);
	d.set(indexj, minD);
	}
	int dot=dot2;
ArrayList<Integer> result=new ArrayList<Integer>();//輸出點的順序
result.add(dot);
	while(dot!=dot1){
		dot=preDot.get(dot);
		result.add(dot);
	}
	for (int i = 0; i < result.size()/2; i++) {
		int j=result.size()-i-1;
		int mid=result.get(j);
		result.set(j, result.get(i));
		result.set(i, mid);
	}
	return result;
}

public static void main(String[] args) throws IOException {
	Map m=new Map();
	m.addDot("A", new int[]{0});
	m.addDot("B", new int[]{33});
	m.addDot("C", new int[]{-1,34});
	m.addDot("D", new int[]{-1,-1,49});
	m.addDot("E", new int[]{-1,-1,65,32});
	
	System.out.println(m.getPath(4,0));

	  }
}