package exp4.test2;

import ch15.LinkedQueue;
import exp4.test1.Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by 春旺 on 2017/11/22.
 */
public class CrossGraph<T>  {
    private int count =0;
    private int EdgeNumber =0;
     List<VertexNode> Vertex = new ArrayList<>();
    List<EdgeNode> Edge = new ArrayList<>();

    // 添加顶点
    public  void addVertex(T e){
        VertexNode vex = new VertexNode();
        vex.Vertex(e);
        Vertex.add(vex);
        count ++;
    }

    //删除顶点
    public void removeVex (T e){
        VertexNode vex = new VertexNode();
        vex.Vertex(e);
        for (int index = 0; index< Edge.size(); index++){
            if (Edge.get(index).head== Vertex.indexOf(vex)){
                Edge.remove(index);
                EdgeNumber --;
                index=0;
            }
            if ( Edge.get(index).tail== Vertex.indexOf(vex)){
                Edge.remove(index);
                EdgeNumber --;
                index=0;
            }
        }
        Vertex.remove(vex);
        count--;
    }

    public int find(VertexNode vex){
        return Vertex.indexOf(vex);
    }


    //添加边
    public void addEdge(EdgeNode edge) {
        EdgeNode edge1 = new EdgeNode(edge.data,edge.head,edge.tail);
        EdgeNode edge2 = new EdgeNode(edge.data,edge.head,edge.tail);
        Edge.add(edge);
        int headIndexOf = edge.head,tailIndexOf = edge.tail;
        VertexNode headVex = Vertex.get(headIndexOf);
        VertexNode tailVex = Vertex.get(tailIndexOf);
        if (headVex.OutEdge == null) {
            headVex.OutEdge = edge1;
            EdgeNumber ++;

        } else {
            EdgeNode tempEdge = headVex.OutEdge;
            // 找到最后一个结点
            for (EdgeNode node = tempEdge.sameHeadVertex; node != null;
                 tempEdge = tempEdge.sameHeadVertex){
            }
            // 赋值
            tempEdge.sameHeadVertex = edge1;
                 EdgeNumber ++;
        }

        if (tailVex.InEdge == null) {
            tailVex.InEdge = edge2;

        } else {
            EdgeNode tempEdge = tailVex.InEdge;
            for (EdgeNode node = tempEdge.sameHeadVertex;node!= null;
                 tempEdge = tempEdge.sameTailVertex)
            tempEdge.sameTailVertex = edge2;

        }
    }

    // 删除边
    public void removeEdge(EdgeNode edge){
        Edge.remove(edge);
        EdgeNumber --;
    }

    // 返回大小（边的数目）
    public int size(){
        return count;
    }
    // 返回边的数目
    public int getEdgeNumber(){
        return EdgeNumber;
    }


    public boolean isEmpty(){
       return count == 0;
    }

    //广度优先遍历

    public ArrayList iteratorBFS(int indexOf){
         LinkedQueue queue = new LinkedQueue();
         ArrayList list = new ArrayList();
        int visitedNum =0;
        boolean[] broadVisited = new boolean[count];
        if (!broadVisited[ indexOf]){
            queue.enqueue(Vertex.get( indexOf).data);
            broadVisited[ indexOf]=true;
            visitedNum++;
        }
        ArrayList vexIndex = new ArrayList();
        while (visitedNum != Vertex.size()){
            EdgeNode tempEdge1 = Vertex.get( indexOf).InEdge;
            if (tempEdge1!=null){
                VertexNode vex = Vertex.get(Vertex.get( indexOf).InEdge.head);
                vexIndex.add(Vertex.get( indexOf).InEdge.head);
                if (!broadVisited[Vertex.get( indexOf).InEdge.head]) {
                    queue.enqueue(vex.data);
                    broadVisited[Vertex.get( indexOf).InEdge.head] = true;
                    visitedNum++;
                }
                for (EdgeNode node = tempEdge1.sameHeadVertex;node!= null;
                     tempEdge1 = tempEdge1.sameTailVertex){
                    tempEdge1 = tempEdge1.sameTailVertex;
                    vexIndex.add(tempEdge1.head);
                    vex = Vertex.get(tempEdge1.head);
                    if (!broadVisited[Vertex.indexOf(vex)]){
                        queue.enqueue(vex.data);
                        broadVisited[Vertex.indexOf(vex)]=true;
                        visitedNum++;
                    }
                }
            }

            EdgeNode tempEdge2 = Vertex.get( indexOf).OutEdge;
            if (tempEdge2 !=null){
                VertexNode vex = Vertex.get(Vertex.get( indexOf).OutEdge.tail);
                vexIndex.add(Vertex.get( indexOf).OutEdge.tail);
                if (!broadVisited[Vertex.get( indexOf).OutEdge.tail]) {
                    queue.enqueue(vex.data);
                    broadVisited[Vertex.get( indexOf).OutEdge.tail] = true;
                    visitedNum++;
                }
               while (tempEdge2.sameHeadVertex != null)
                {
                    tempEdge2 = tempEdge2.sameHeadVertex;
                    vexIndex.add(tempEdge2.tail);
                    vex = Vertex.get(tempEdge2.tail);
                    if (!broadVisited[Vertex.indexOf(vex)]){
                        queue.enqueue(vex.data);
                        broadVisited[Vertex.indexOf(vex)]=true;
                        visitedNum++;
                    }
                }
            }
             indexOf = (int) vexIndex.remove(0);
        }
        while (!queue.isEmpty()){
            list.add(queue.dequeue());
        }

      return list;
    }

    //深度优先遍历
    public ArrayList iteratorBDFS(int indexOf){
        VertexNode vex =  Vertex.get(indexOf);
        ArrayList List = new ArrayList();
        boolean[] visited;
        visited = new boolean[Vertex.size()];
        traverse(vex,List,visited);
        return List;
    }
    private void traverse(VertexNode vex,ArrayList list,boolean [] visited){
        list.add(vex.data);
        visited[Vertex.indexOf(vex)]=true;

        if (vex.OutEdge!=null) {
            VertexNode tempVex1= Vertex.get(vex.OutEdge.tail);
            traverse(tempVex1,list,visited);
            EdgeNode edge = vex.OutEdge;
            while (edge.sameHeadVertex != null && !visited[edge.sameHeadVertex.tail]) {
                VertexNode tempVex2 = Vertex.get(edge.sameHeadVertex.tail);
                visited[Vertex.indexOf(tempVex2)] = true;
                edge = edge.sameHeadVertex;
                traverse(tempVex2,list,visited);
            }
        }
    }
}