package week9;

import jsjf.QueueADT;
import jsjf.StackADT;
import jsjf.exceptions.*;
import week2.LinkedStack;
import week3.LinkedQueue;
import week4.ArrayUnorderedList;
import week4.UnorderedListADT;

import java.util.*;

// 图表示图的邻接矩阵实现。
public class Graph<T> implements GraphADT<T>
{
    protected final int DEFAULT_CAPACITY = 5;
    protected int numVertices;    // 图中顶点的数量
    protected boolean[][] adjMatrix;    // 邻接矩阵
    protected T[] vertices;    // 顶点的值
    protected int modCount;

    // 创建一个空图。
    public Graph()
    {
        numVertices = 0;
        this.adjMatrix = new boolean[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        this.vertices = (T[])(new Object[DEFAULT_CAPACITY]);
    }

    // 返回邻接矩阵的字符串表示形式。
    public String toString()
    {
        if (numVertices == 0)
            return "Graph is empty";

        String result = new String("");

        result += "Adjacency Matrix\n";
        result += "----------------\n";
        result += "index\t";

        for (int i = 0; i < numVertices; i++) 
        {
            result += "" + i;
            if (i < 10)
                result += " ";
        }
        result += "\n\n";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i + "\t";
        
            for (int j = 0; j < numVertices; j++)
            {
                if (adjMatrix[i][j])
                    result += "1 ";
                else
                    result += "0 ";
            }
            result += "\n";
        }

        result += "\n\nVertex Values";
        result += "\n-------------\n";
        result += "index\tvalue\n\n";

        for (int i = 0; i < numVertices; i++)
        {
            result += "" + i + "\t";
            result += vertices[i].toString() + "\n";
        }
        result += "\n";
        return result;
    }

    // 在图的两个顶点之间插入一条边。
    public void addEdge(int index1, int index2)
    {
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] = true;
            adjMatrix[index2][index1] = true;
            modCount++;
        }
    }

    // 删除图中两个顶点之间的一条边。
    public void removeEdge(int index1, int index2)
    {
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] = false;
            adjMatrix[index2][index1] = false;
            modCount++;
        }
    }

    // 在图的两个顶点之间插入一条边。
    public void addEdge(T vertex1, T vertex2)
    {
        addEdge(getIndex(vertex1), getIndex(vertex2));
    }

    // 删除图中两个顶点之间的一条边。
    public void removeEdge(T vertex1, T vertex2)
    {
        removeEdge(getIndex(vertex1), getIndex(vertex2));
    }

    // 向图中添加一个顶点，如果需要，可以扩展图的容量。它还将对象与顶点关联。
    public void addVertex(T vertex)
    {        
        if ((numVertices + 1) == adjMatrix.length)
            expandCapacity();

        vertices[numVertices] = vertex;
        for (int i = 0; i < numVertices; i++)
        {
            adjMatrix[numVertices][i] = false;
            adjMatrix[i][numVertices] = false;
        }        
        numVertices++;
        modCount++;
    }

    // 从图中删除给定索引处的顶点。注意，这可能会影响其他顶点的索引值。
    public void removeVertex(int index)
    {
        if (indexIsValid(index))
        {
            for (int j = index;j<numVertices-1;j++)
            {
                vertices[j] = vertices[j+1];
            }
            vertices[numVertices-1] = null;


            for (int i = index; i < numVertices-1; i++)
            {
                for (int x=0;x<numVertices;x++)
                    adjMatrix[i][x] = adjMatrix[i+1][x];

            }

            for (int i = index; i < numVertices; i++)
            {
                for (int x=0;x<numVertices;x++)
                    adjMatrix[x][i] = adjMatrix[x][i+1];
            }

            for (int i = 0; i < numVertices; i++)
            {
                adjMatrix[numVertices][i] = false;
                adjMatrix[i][numVertices] = false;
            }
            numVertices--;
            modCount++;
        }
    }

    // 从图中删除具有给定值的单个顶点。
    public void removeVertex(T vertex)
    {
        removeVertex(getIndex(vertex));
    }

    // 返回一个迭代器，该迭代器执行从给定索引开始的深度优先遍历。
    public Iterator<T> iteratorDFS(int startIndex)
    {
        Integer x;
        boolean found;
        StackADT<Integer> traversalStack = new LinkedStack<Integer>();
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
        boolean[] visited = new boolean[numVertices];

        if (!indexIsValid(startIndex))
            return resultList.iterator();

        for (int i = 0; i < numVertices; i++)
            visited[i] = false;
        
        traversalStack.push(new Integer(startIndex));
        resultList.addToRear(vertices[startIndex]);
        visited[startIndex] = true;
        
        while (!traversalStack.isEmpty())
        {
            x = traversalStack.peek();
            found = false;

            // 找到与x相邻的一个没有访问过的顶点，并将其推入堆栈
            for (int i = 0; (i < numVertices) && !found; i++)
            {
                if (adjMatrix[x.intValue()][i] && !visited[i])
                {
                    traversalStack.push(new Integer(i));
                    resultList.addToRear(vertices[i]);
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new GraphIterator(resultList.iterator());
    }

    // 返回一个迭代器，该迭代器从给定顶点开始执行深度优先搜索遍历。
    public Iterator<T> iteratorDFS(T startVertex)
    {        
        return iteratorDFS(getIndex(startVertex));
    }

    // 返回一个迭代器，该迭代器从给定的索引开始执行广度优先遍历。
    public Iterator<T> iteratorBFS(int startIndex)
    {
        Integer x;
        QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();

        if (!indexIsValid(startIndex))
            return resultList.iterator();

        boolean[] visited = new boolean[numVertices];
        for (int i = 0; i < numVertices; i++)
            visited[i] = false;
        
        traversalQueue.enqueue(new Integer(startIndex));
        visited[startIndex] = true;
        
        while (!traversalQueue.isEmpty())
        {
            x = traversalQueue.dequeue();
            resultList.addToRear(vertices[x.intValue()]);

            // 查找x附近没有访问过的所有顶点，并将它们排队

            for (int i = 0; i < numVertices; i++)
            {
                if (adjMatrix[x.intValue()][i] && !visited[i])
                {
                    traversalQueue.enqueue(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        return new GraphIterator(resultList.iterator());
    }
    
    // 返回一个迭代器，该迭代器从给定顶点开始执行广度优先搜索遍历。
    public Iterator<T> iteratorBFS(T startVertex)
    {        
        return iteratorBFS(getIndex(startVertex));
    }

    // 返回一个迭代器，该迭代器包含两个给定顶点之间的最短路径中顶点的索引。
    protected Iterator<Integer> iteratorShortestPathIndices
                                        (int startIndex, int targetIndex)
    {
        int index = startIndex;
        int[] pathLength = new int[numVertices];
        int[] predecessor = new int[numVertices];
        QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
        UnorderedListADT<Integer> resultList = 
                                             new ArrayUnorderedList<Integer>();

        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex) || 
                                                    (startIndex == targetIndex))
            return resultList.iterator();

        boolean[] visited = new boolean[numVertices];
        for (int i = 0; i < numVertices; i++)
            visited[i] = false;
        
        traversalQueue.enqueue(new Integer(startIndex));
        visited[startIndex] = true;
        pathLength[startIndex] = 0;
        predecessor[startIndex] = -1;

        while (!traversalQueue.isEmpty() && (index != targetIndex))
        {
            index = (traversalQueue.dequeue()).intValue();

            //Update the pathLength for each unvisited vertex adjacent 
            //     to the vertex at the current index. 
            for (int i = 0; i < numVertices; i++)
            {
                if (adjMatrix[index][i] && !visited[i])
                {
                    pathLength[i] = pathLength[index] + 1;
                    predecessor[i] = index;
                    traversalQueue.enqueue(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        if (index != targetIndex)  // no path must have been found
            return resultList.iterator();

        StackADT<Integer> stack = new LinkedStack<Integer>();
        index = targetIndex;
        stack.push(new Integer(index));
        do
        {
            index = predecessor[index];
            stack.push(new Integer(index));
        } while (index != startIndex);
        
        while (!stack.isEmpty())
            resultList.addToRear(((Integer)stack.pop()));

        return new GraphIndexIterator(resultList.iterator());
    }

    // 返回一个迭代器，该迭代器包含两个顶点之间的最短路径。
    public Iterator<T> iteratorShortestPath(int startIndex, 
                                                         int targetIndex)
    {
        UnorderedListADT<T> resultList = new ArrayUnorderedList<T>();
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return resultList.iterator();

        Iterator<Integer> it = iteratorShortestPathIndices(startIndex, 
                                      targetIndex);        
        while (it.hasNext())
            resultList.addToRear(vertices[((Integer)it.next()).intValue()]);
        return new GraphIterator(resultList.iterator());
    }

    // 返回一个迭代器，该迭代器包含两个顶点之间的最短路径。
    public Iterator<T> iteratorShortestPath(T startVertex, T targetVertex)
    {
        return iteratorShortestPath(getIndex(startVertex), 
                                             getIndex(targetVertex));
    }

    // 返回网络中权值最小路径的权值。如果没有找到路径，返回正无穷。
    public int shortestPathLength(int startIndex, int targetIndex)
    {
        int result = 0;
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return 0;

        int index1, index2;
        Iterator<Integer> it = iteratorShortestPathIndices(startIndex, 
                                      targetIndex);

        if (it.hasNext())
            index1 = ((Integer)it.next()).intValue();
        else
            return 0;

        while (it.hasNext())
        {
            result++;
            it.next();
        }
        
        return result;
    }

    // 返回网络中权值最小路径的权值。如果没有找到路径，返回正无穷。
    public int shortestPathLength(T startVertex, T targetVertex)
    {
        return shortestPathLength(getIndex(startVertex), getIndex(targetVertex));
    }

    // 返回图的最小生成树。
    public Graph getMST()
    {
        int x, y;
        int[] edge = new int[2];
        StackADT<int[]> vertexStack = new LinkedStack<int[]>();
        Graph<T> resultGraph = new Graph<T>();

        if (isEmpty() || !isConnected())
            return resultGraph;
        
        resultGraph.adjMatrix = new boolean[numVertices][numVertices];
        
        for (int i = 0; i < numVertices; i++)
            for (int j = 0; j < numVertices; j++)
                resultGraph.adjMatrix[i][j] = false;
                
        resultGraph.vertices = (T[])(new Object[numVertices]);
        boolean[] visited = new boolean[numVertices];
        
        for (int i = 0; i < numVertices; i++)
            visited[i] = false;        
        
        edge[0] = 0;
        resultGraph.vertices[0] = this.vertices[0];
        resultGraph.numVertices++;
        visited[0] = true;

        // 将与顶点0相邻的所有边添加到堆栈中。
        for (int i = 0; i < numVertices; i++)
        {
            if (!visited[i] && this.adjMatrix[0][i])
            {
                edge[1] = i;
                vertexStack.push(edge.clone());
                visited[i] = true;
            }
        }

        while ((resultGraph.size() < this.size()) && !vertexStack.isEmpty())
        {
            // 从堆栈中取出一条边并将其添加到resultGraph中。
            edge = vertexStack.pop();
            x = edge[0];
            y = edge[1];
            resultGraph.vertices[y] = this.vertices[y];
            resultGraph.numVertices++;
            resultGraph.adjMatrix[x][y] = true;
            resultGraph.adjMatrix[y][x] = true;
            visited[y] = true;

            // 将与顶点y相邻的所有未访问的边添加到堆栈中。
            for (int i = 0; i < numVertices; i++)
            {
                if (!visited[i] && this.adjMatrix[i][y])
                {
                    edge[0] = y;
                    edge[1] = i;
                    vertexStack.push(edge.clone());
                    visited[i] = true;
                }
            }
        }

        return resultGraph;
    }

    // 创建新数组，以两倍容量存储图形的内容。
    protected void expandCapacity()
    {
        T[] largerVertices = (T[])(new Object[vertices.length*2]);
        boolean[][] largerAdjMatrix = 
                new boolean[vertices.length*2][vertices.length*2];

        for (int i = 0; i < numVertices; i++)
        {
            for (int j = 0; j < numVertices; j++)
            {
                largerAdjMatrix[i][j] = adjMatrix[i][j];
            }
            largerVertices[i] = vertices[i];
        }

        vertices = largerVertices;
        adjMatrix = largerAdjMatrix;
    }

    // 返回图中顶点的数量。
    public int size()
    {
        return numVertices;
    }

    // 如果图为空，返回true，否则返回false。
    public boolean isEmpty()
    {
        return numVertices == 0;
    }

    // 如果图连接，返回true;否则返回false。
    public boolean isConnected()
    {
        for (int x = 0; x < numVertices; x++)
        {
            int temp = 0;
            Iterator DFS = this.iteratorDFS(vertices[x]);
            while(DFS.hasNext())
            {
                temp++;
                DFS.next();
            }

            if (temp != numVertices)
                return false;
        }
        return true;
    }

    // 返回顶点第一次出现的索引值。如果没有找到键，返回-1。
    public int getIndex(T vertex)
    {
        int index = -1;

        for (int x = 0; x < numVertices; x++ )
        {
            if (vertex.equals(vertices[x]))
            {
                index = x;
            }
        }
        return index;
    }

    // 如果给定索引有效，则返回true。
    protected boolean indexIsValid(int index)
    {
        return index < vertices.length;
    }

    // 返回顶点数组的副本。
    public Object[] getVertices()
    {
        Object[] newVertices = vertices;
        return newVertices;
    }
    
    // 内部类表示这个图元素上的迭代器
    protected class GraphIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;
        
        // 使用指定的迭代器设置此迭代器。
        public GraphIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        
        // 如果迭代器在迭代中至少有一个元素要交付，则返回true。
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        
        // 返回迭代中的下一个元素。如果这个迭代中没有更多的元素，就会抛出NoSuchElementException。
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }
        
        // 不支持删除操作。
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
    
    // 内部类表示这个图的索引上的迭代器
    protected class GraphIndexIterator implements Iterator<Integer>
    {
        private int expectedModCount;
        private Iterator<Integer> iter;
        
        // 使用指定的迭代器设置此迭代器。
        public GraphIndexIterator(Iterator<Integer> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        
        // 如果迭代器在迭代中至少有一个元素要交付，则返回true。
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        
        // 返回迭代中的下一个元素。如果这个迭代中没有更多的元素，就会抛出NoSuchElementException。
        public Integer next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }
        
        // 不支持删除操作。
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}