package exp4;

import chapter15.javaFoundations2nd.LinkedQueue;

import java.util.ArrayList;

/**
 * Created by 蜡笔小新丶 on 2017/11/20.
 */
public class OrthogonalList<E> {
    private ArrayList<SZNode<E>> node; //结点列表
    private SZSide headSide;
    private int [] S;  //最短路径数组
    private boolean [][] M;//边的矩阵
    private final int MAX = -1;

    public OrthogonalList(){
       node = new ArrayList<>();
    }

    //添加结点的方法
    public boolean addNode(E point){
       boolean result = node.add(new SZNode<>(point));
       restart();
       return result;
    }

    //添加边的方法
    public boolean addSide(int mag, E A,E B) throws Exception {
        int num1 = -1,num2 = -1;
        boolean result = false;
        for(int i=0;i<node.size();i++){
            if(node.get(i).data.equals(A))
                num1 = i;
            else if(node.get(i).data.equals(B))
                num2 = i;
        }
        if(num1 == -1|| num2==-1){
            throw new Exception("找不到该结点！");
        }else {
            add(mag,num1,num2);
            result = true;
        }
        return result;
    }

    //私有的添加方法
    private void add(int mag,int num1,int num2){
        SZSide side = new SZSide(mag, num1, num2);
        if(node.get(num1).firstOut==null)
            node.get(num1).firstOut = side;
        else {
            headSide = node.get(num1).firstOut;
            while (headSide.nextSameToVertex!=null){
                headSide = headSide.nextSameToVertex;
            }
            headSide.nextSameToVertex = side;
        }
        if(node.get(num2).firstIn==null)
            node.get(num2).firstIn = side;
        else {
            headSide = node.get(num2).firstIn;
            while (headSide.nextSameFromVertex!=null){
                headSide = headSide.nextSameFromVertex;
            }
            headSide.nextSameFromVertex = side;
        }
    }

    //删除结点
    public boolean removeNode(E m){
        int A = -1;
        boolean result = false;
        for(int i=0;i<node.size();i++){
            if(node.get(i).data.equals(m))
                A = i;
        }
        node.remove(A);
        if(A!=-1)
            result = true;
        return result;
    }

    //删除一条边
    public boolean removeSide(E A,E B) throws Exception {
        boolean result = false;
        int num1 = -1,num2 = -1;
        for(int i=0;i<node.size();i++){
            if(node.get(i).data.equals(A))
                num1 = i;
            else if(node.get(i).data.equals(B))
                num2 = i;
        }
        if(num1!=-1 && num2 != -1){
            remove(num1,num2);
            result = true;
        }else
            throw new Exception("找不到该边！");
        return result;
    }

    //私有的删除方法
    private void remove(int num1,int num2){
        SZSide node1,node2;
        node1 = node.get(num1).firstOut;
        node2 = node.get(num2).firstIn;
        if(node1.toVertexIndex==num2)
            node.get(num1).firstOut = node1.nextSameToVertex;
        else {
            while (node1.nextSameToVertex.toVertexIndex != num2){
                node1 = node1.nextSameToVertex;
            }
            node1.nextSameToVertex = (node1.nextSameToVertex).nextSameToVertex;
        }
        if (node2.fromVertexIndex == num1){
            node.get(num2).firstIn = node1.nextSameFromVertex;
        }else {
            while (node2.nextSameFromVertex.fromVertexIndex != num2){
                node2 = node2.nextSameFromVertex;
            }
            node1.nextSameFromVertex = (node1.nextSameFromVertex).nextSameFromVertex;
        }
    }

    //图的大小
    public int size(){
        return node.size();
    }

    //判断图是否为空
    public boolean isEmpty(){
        return (node.size()==0);
    }

    //图的遍历方法
    public ArrayList<E> iteratorBFS(int start) throws Exception {
        SZSide head;
        int currentVertex;
        int next = -1;
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
        ArrayList<E> iter = new ArrayList<>();
        boolean[] visited = new boolean[node.size()];
        for (int i = 0; i < visited.length; i++)
            visited[i] = false;
        traversalQueue.enqueue(start);
        visited[start] = true;

        while (!traversalQueue.isEmpty()) {
            currentVertex = traversalQueue.dequeue();
            iter.add(node.get(currentVertex).data);
            for (int j = 0; j < visited.length; j++) {
                head = node.get(j).firstOut;
                while (head!=null){
                    if(!visited[head.toVertexIndex]) {
                        traversalQueue.enqueue(head.toVertexIndex);
                        visited[head.toVertexIndex] = true;
                    }
                    head = head.nextSameToVertex;
                }
            }
        }
        return iter;
    }

    //查询最短路径
    public String Min(E A,E B) throws Exception {
        int num1 = -1,num2 = -1;
        String result = null;
        for(int i=0;i<node.size();i++){
            if(node.get(i).data.equals(A))
                num1 = i;
            else if(node.get(i).data.equals(B))
                num2 = i;
        }
        S[num1] = 0;
        update(num1);
        result = S[num2] + "";
        restart();
        if(result.equals("-1"))
            result = "两结点间无路径！";
        return result;
    }

    //更新最短路径数组
    private void update(int num1){
        SZSide head = node.get(num1).firstOut;
        ArrayList<Integer> arr = find(num1);
        while (head!=null&&!arr.isEmpty()){
            int temp = head.toVertexIndex;
            if(S[temp]==-1)
                S[temp] = S[num1] + head.data;
            else if(S[temp]>S[num1] + head.data){
                S[temp] = S[num1] + head.data;
            }
            head = head.nextSameToVertex;
        }
        for (int i:arr)
            update(i);
    }
    //查找相邻结点
    private ArrayList<Integer> find(int num1){
        ArrayList<Integer> arr = new ArrayList<>();
        SZSide head =  node.get(num1).firstOut;
        while (head!=null){
            if(!M[head.fromVertexIndex][head.toVertexIndex]) {
                arr.add(head.toVertexIndex);
                M[head.fromVertexIndex][head.toVertexIndex] = true;
            }
            head = head.nextSameToVertex;
        }
        return arr;
    }

    private void restart(){
        S = new int[node.size()];
        M = new boolean[node.size()][node.size()];
        for(int i=0;i<S.length;i++)
            S[i] = MAX;
    }

    @Override
    public String toString() {
        String result = "";
        for(SZNode i:node)
        {
            result += i.toString()+"\n";
        }
        return result;
    }
}