package chap15;

import chap3.EmptyCollectionException;

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;

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]);
	}

	@Override
	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++;

	}

	/**
	 * 扩大容量的函数
	 */
	private 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;

	}

	@Override
	public void removeVertex(T vertex) {
		if (isEmpty()) {
			throw new EmptyCollectionException("Graph");
		}

	}

	@Override
	public void addEdge(T v1,  T v2) {
		addEdge(getIndex(v1), getIndex(v2));
	}

	/**
	 * 两个索引标号之间添加链接
	 */
	private void addEdge(int index1, int index2) {
		if (indexIsValid(index1) && indexIsValid(index2)) {
			adjMatrix[index1][index2] = true;
			adjMatrix[index2][index1] = true;
			modCount++;
		}

	}

	private boolean indexIsValid(int index) {
		if (index < vertices.length) {
			return true;
		}
		return false;
	}

	/**
	 * 获取结点的索引标号
	 */
	private int getIndex(T v) {
		int index = vertices.length;
		// boolean flag =
		for (int i = 0; i < vertices.length; i++) {
			if (v.equals(vertices[i])) {
				index = i;
				break;
			}

		}

		return index;
	}

	@Override
	public void removeEdge(T v1, T v2) {
		removeEdge(getIndex(v1), getIndex(v2));

	}

	private void removeEdge(int index1, int index2) {
		if (indexIsValid(index1) && indexIsValid(index2)) {
			adjMatrix[index1][index2] = false;
			adjMatrix[index2][index1] = false;
			modCount++;
		}

	}

	@Override
	public Iterator iteratorBFS(T startVertex) {
		return iteratorBFS(getIndex(startVertex));
	}

	private Iterator iteratorBFS(int startIndex) {
		Integer x;
		Queue<Integer> tq = new LinkedList<Integer>();
		List<T> rls = new ArrayList<T>();

		if (!indexIsValid(startIndex)) {
			return rls.iterator();
		}

		boolean[] visited = new boolean[numVertices];
		for (int i = 0; i < numVertices; i++) {
			visited[i] = false;
		}
		tq.add(new Integer(startIndex));

		visited[startIndex] = true;
		while (!tq.isEmpty()) {
			// 出队列
			x = tq.poll();
			// 遍历记录表
			rls.add(vertices[x.intValue()]);
			for (int i = 0; i < numVertices; i++) {
				if (adjMatrix[x.intValue()][i] && !visited[i]) {
					tq.offer(new Integer(i));
					visited[i] = true;
				}
			}

		}
		return new GraphIterator(rls.iterator());

	}

	@Override
	public Iterator iteratorDFS(T startIndex) {
		return iteratorDFS(getIndex(startIndex));
	}

	/**
	 * 深度优先遍历的实现
	 */
	private Iterator iteratorDFS(int startIndex) {
		Integer x;
		Stack<Integer> ts = new Stack<Integer>();
		List<T> rls = new ArrayList<T>();
		boolean found;

		if (!indexIsValid(startIndex)) {
			return rls.iterator();
		}

		boolean[] visited = new boolean[numVertices];
		for (int i = 0; i < numVertices; i++) {
			visited[i] = false;
		}

		ts.push(new Integer(startIndex));
		rls.add(vertices[startIndex]);
		visited[startIndex] = true;

		while (!ts.isEmpty()) {
			x = ts.peek();
			found = false;///用于作为栈顶是否是活顶点的标志变量

			for (int i = 0; (i < numVertices) && !found; i++) {
				if (adjMatrix[x.intValue()][i] && !visited[i]) {
					ts.push(new Integer(i));
					rls.add(vertices[i]);
					visited[i] = true;
					found = true;
				}
			}
			//如果栈顶结点不是活结点并且栈不为空
			if (!found && !ts.isEmpty())
				ts.pop();
		}

		return new GraphIterator(rls.iterator());
	}

	@Override
	public Iterator iteratorShortestPath(T startVertex, T targetVertex) {
		 return iteratorShortestPath(getIndex(startVertex), 
                 getIndex(targetVertex));
	}

	/**
	 * 查找两个顶点之间的最近路径
	 * @param startIndex
	 * @param targetIndex
	 * @return
	 */
	private Iterator iteratorShortestPath(int startIndex, int targetIndex) {
		
		List<T> resultList = new ArrayList<T>();
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return resultList.iterator();

        //获取结点集合的迭代器对象
        Iterator<Integer> it = iteratorShortestPathIndices(startIndex, 
                                      targetIndex);        
        while (it.hasNext())
            resultList.add(vertices[((Integer)it.next()).intValue()]);
        return new GraphIterator(resultList.iterator());
	}

	/**
	 * 构建从开始到结束的节点集合的迭代器对象
	 * @param startIndex
	 * @param targetIndex
	 * @return
	 */
	private Iterator<Integer> iteratorShortestPathIndices(int startIndex,
			int targetIndex) {
		
		
		int index = startIndex;
        int[] pathLength = new int[numVertices];
        int[] predecessor = new int[numVertices];
        
        Queue<Integer> traversalQueue = new LinkedList<Integer>();
        List<Integer> resultList = new ArrayList<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.offer(new Integer(startIndex));
        visited[startIndex] = true;
        pathLength[startIndex] = 0;
        predecessor[startIndex] = -1;

        while (!traversalQueue.isEmpty() && (index != targetIndex))
        {
            index = (traversalQueue.poll()).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.offer(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        if (index != targetIndex)  // no path must have been found
            return resultList.iterator();

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

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

	 

    /**
     * Returns the weight of the least weight path in the network.  
     * Returns positive infinity if no path is found.
     *
     * @param startIndex the starting index
     * @param targetIndex the target index
     * @return the integer weight of the least weight path
     *                in the network
     */
    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;
    }

    /**
     * Returns the weight of the least weight path in the network.  
     * Returns positive infinity if no path is found.
     *
     * @param startVertex the starting vertex
     * @param targetVertex the target vertex
     * @return the integer weight of teh least weight path
     *            in the network
     */
    public int shortestPathLength(T startVertex, T targetVertex)
    {
        return shortestPathLength(getIndex(startVertex), getIndex(targetVertex));
    }

    /**
     * MST算法实现
     *
     * @return a minimum spanning tree of the graph
     */
    public Graph getMST()
    {
        int x, y;
        int[] edge = new int[2];
        Stack<int[]> vertexStack = new Stack<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;

        // Add all edges that are adjacent to vertex 0 to the stack. 
        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())
        {
            // Pop an edge off the stack and add it to the 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;

            // Add all unvisited edges that are adjacent to vertex y
            // to the stack. 
            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;
    }
	
	
	
	@Override
	public boolean isEmpty() {
		return (numVertices == 0);
	}

	@Override
	public boolean isConnected() {
		boolean flag = true;
		for(int i=0;i<vertices.length;i++){
			int temp=0;
			temp=getSizeOfIterator(this.iteratorBFS(vertices[i]));
			if(temp!=vertices.length){
				flag = false;
				break;
			}
		}
		
		return flag;
	}

	/**
	 * 获取迭代器中顶点的数目
	 * @param it
	 * @return
	 */
	private int getSizeOfIterator(Iterator it) {
		int size = 0;
		while(it.hasNext()){
			size++;
			it.next();
		}
		
		return 0;
	}

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

	@Override
	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;
	}
/**--------------------------------下面是自定义的内部迭代器的实现方式-----------------------------------***/
	
	/**
     * Inner class to represent an iterator over the elements of this graph
     */
    protected class GraphIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;
        
        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a graph traversal
         */
        public GraphIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        
        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        
        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }
        
        /**
         * The remove operation is not supported.
         * 
         * @throws UnsupportedOperationException if the remove operation is called
         */
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
    
    /**
     * Inner class to represent an iterator over the indexes of this graph
     */
    protected class GraphIndexIterator implements Iterator<Integer>
    {
        private int expectedModCount;
        private Iterator<Integer> iter;
        
        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a graph traversal
         */
        public GraphIndexIterator(Iterator<Integer> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        
        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();
            
            return (iter.hasNext());
        }
        
        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        public Integer next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else 
                throw new NoSuchElementException();
        }
        
        /**
         * The remove operation is not supported.
         * 
         * @throws UnsupportedOperationException if the remove operation is called
         */
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}