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

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by 春旺 on 2017/11/18.
 */
public class MarGraph <T>implements Graph<T> {
    protected ArrayList<T> vertexList;
    private Object [][] edges;//邻接矩阵，用来存储边
    private int count = 0;
    private int  EdgesCont= 0;
    @Override
    public void Graph(int n) {
        edges = new Object[n][n];
        vertexList=new ArrayList(n);
        EdgesCont = 0;
    }
    @Override
    public void addVertex(T e) {
        vertexList.add(e);
        count ++;
    }
    @Override
    public void addEdges(T a, T b) {
        edges[vertexList.indexOf(a)][vertexList.indexOf(b)] = 1;
        edges[vertexList.indexOf(b)][vertexList.indexOf(a)] = 1;
        EdgesCont++;
    }
    @Override
    public T removeVertex(T e) {

        if (vertexList.contains(e) == false)
            System.out.println("没有该元素");
        else {
            int a = vertexList.indexOf(e);
            vertexList.remove(a);
            for (int ai = 0;ai< edges[a].length;ai++){
                if (  edges[a] [ai]!= null){
            edges[a] [ai]= null;
                EdgesCont--;
                }
            }
            for (int i =0;i< edges.length;i++){
                if (edges[i][a] != null)
                edges[i][a] = null;
            }
            count --;
        }
        return e;
    }
    @Override
    public void removeEdges( T a, T b) {
        int e1 = vertexList.indexOf(a);
        int e2 = vertexList.indexOf(b);
        edges[e1][e2]= null;
        edges[e2][e1] = null;
        EdgesCont--;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public boolean isEmpty() {
        return vertexList.isEmpty();
    }

    @Override
    public ArrayList iteratorBFS(int index) {
        ArrayList result = new ArrayList();
        LinkedQueue queue = new LinkedQueue();
        Object arr [][] = edges;
        result.add(vertexList.get(index));
        queue = BFS(arr,queue,index);
        while (!queue.isEmpty()){
            result.add(queue.dequeue());
        }
        return result;
    }
    private LinkedQueue BFS(Object[][] arr,LinkedQueue queue, int index){
        for (int ai = 0;ai<arr.length;ai++){
            arr[ai][index] = null;
        }
        for (int i =0;i< arr[index].length;i++)
            if (arr[index][i] != null){
            arr[index][i] = null;
            arr[i][index] = null;
                queue.enqueue(vertexList.get(i));
                for (int ai = 0;ai< edges.length;ai++) {
                    arr[ai][i] = null;

                }
                arr[i][index] = null;
                if (arr != null)
                   BFS(arr,queue,i);
            }

        return queue;
    }

    @Override
    public ArrayList iteratorDSF(int index) {
        ArrayList result = new ArrayList();
        Stack stack = new Stack();
        Object arr [][] = edges;
        result.add(vertexList.get(index));
        stack = DSF(arr,stack,index);
        while (!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }

    @Override
    public int edgesNumber() {
        return EdgesCont;
    }

    private Stack DSF(Object[][] arr,Stack stack, int index){
        for (int ai = 0;ai<arr.length;ai++){
            arr[ai][index] = null;
        }

        for (int i =0;i< arr[index].length;i++)
            if (arr[index][i] != null){
                arr[index][i] = null;
                arr[i][index] = null;
                stack.push(vertexList.get(i));
                for (int ai = 0;ai< edges.length;ai++) {
                    arr[ai][i] = null;

                }
                arr[i][index] = null;
                if (arr != null)
                    DSF(arr,stack,i);
            }
        return stack;
    }
}