package week_9;


import week_1.practice.LinkedStack;
import week_1.practice.StackADT;
import week_2.homework.LinkedQueue;
import week_2.practice.QueueADT;
import week_4.practice.ArrayUnorderedList;
import week_4.practice.UnorderedListADT;

import java.util.*;

public class IndirectedNetwork<T> implements NetworkADT<T>
{
    protected final int DEFAULT_CAPACITY = 5;
    protected int numVertices;    // number of vertices in the graph
    protected Double[][] adjMatrix;    // adjacency matrix
    protected T[] vertices;    // values of vertices
    protected int modCount;

    public IndirectedNetwork() {
        numVertices = 0;
        this.adjMatrix = new Double[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        this.vertices = (T[])(new Object[DEFAULT_CAPACITY]);
    }

    public String toString()
    {
        if (numVertices == 0)
            return "IndirectedNetwork is empty";

        String result = new String("");

        result += "IndirectedNetwork\n";
        result += "------------------\n";

        for(int i = 0;i<numVertices;i++) {
            for (int j = 0; j < numVertices; j++) {
                result +=  String.valueOf(vertices[i]+"--->"+vertices[j])+"\t";
                result += adjMatrix[i][j]+"\t";
            }
            result +="\n";
        }

        result += "\n";
        return result;
    }

    @Override
    public void addEdge(T vertex1, T vertex2, double weight) {
        addEdge(getIndex(vertex1),getIndex(vertex2),weight);
    }

    public void addEdge(int index1, int index2, double weight) {
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] = weight;
            adjMatrix[index2][index1] = weight;
            modCount++;
        }
    }
    @Override
    public void addEdge(T vertex1, T vertex2) {

    }
    @Override
    public void removeEdge(T vertex1, T vertex2) {
        removeEdge(getIndex(vertex1),getIndex(vertex2));
    }
    public void removeEdge(int index1, int index2) {
        if (indexIsValid(index1) && indexIsValid(index2))
        {
            adjMatrix[index1][index2] =Double.POSITIVE_INFINITY;
            adjMatrix[index2][index1] = Double.POSITIVE_INFINITY;
            modCount++;
        }
    }

    @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] = Double.POSITIVE_INFINITY;
            adjMatrix[i][numVertices] = Double.POSITIVE_INFINITY;
        }
        numVertices++;
        modCount++;
    }
    protected void expandCapacity()
    {
        T[] largerVertices = (T[])(new Object[vertices.length*2]);
        Double[][] largerAdjMatrix =
                new Double[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) {
        removeVertex(getIndex(vertex));
    }



    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] = Double.POSITIVE_INFINITY;
                adjMatrix[i][numVertices] = Double.POSITIVE_INFINITY;
            }
            numVertices--;
            modCount++;
        }
    }


    @Override
    public Iterator iteratorBFS(T startVertex) {
        return iteratorBFS(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(startIndex);
        visited[startIndex] = true;

        while (!traversalQueue.isEmpty())
        {
            x = traversalQueue.dequeue();
            resultList.addToRear(vertices[x]);

            //Find all vertices adjacent to x that have not been visited
            //     and queue them up

            for (int i = 0; i < numVertices; i++)
            {
                if (adjMatrix[x][i]<Double.POSITIVE_INFINITY && !visited[i])
                {
                    traversalQueue.enqueue(i);
                    visited[i] = true;
                }
            }
        }
        return new NetworkIterator(resultList.iterator());
    }

    @Override
    public Iterator iteratorDFS(T startVertex) {
        return iteratorDFS(getIndex(startVertex));
    }
    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(startIndex);
        resultList.addToRear(vertices[startIndex]);
        visited[startIndex] = true;

        while (!traversalStack.isEmpty())
        {
            x = traversalStack.peek();
            found = false;

            //Find a vertex adjacent to x that has not been visited
            //     and push it on the stack
            for (int i = 0; (i < numVertices) && !found; i++)
            {
                if (adjMatrix[x][i]<Double.POSITIVE_INFINITY && !visited[i])
                {
                    traversalStack.push(i);
                    resultList.addToRear(vertices[i]);
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new NetworkIterator(resultList.iterator());
    }

    public int shortestPathLength(T startVertex, T targetVertex)
    {
        return shortestPathLength(getIndex(startVertex), getIndex(targetVertex));
    }

    public int shortestPathLength(int startIndex, int targetIndex)
    {
        int result = 0;
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return 0;

        int index1;
        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;
    }

    @Override
    public Iterator iteratorShortestPath(T startVertex, T targetVertex) {
        return iteratorShortestPath(getIndex(startVertex), getIndex(targetVertex));
    }
    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 NetworkIterator(resultList.iterator());
    }

    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(Integer.valueOf(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]<Double.POSITIVE_INFINITY && !visited[i])
                {
                    pathLength[i] = pathLength[index] + 1;
                    predecessor[i] = index;
                    traversalQueue.enqueue(Integer.valueOf(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(Integer.valueOf(index));
        do
        {
            index = predecessor[index];
            stack.push(Integer.valueOf(index));
        }
        while (index != startIndex);

        while (!stack.isEmpty())
            resultList.addToRear(((Integer)stack.pop()));

        return new NetworkIndexIterator(resultList.iterator());
    }
    @Override
    public double shortestPathWeight(T vertex1, T vertex2) {
        int index1 = getIndex(vertex1);
        int index2 = getIndex(vertex2);
        return shortestPathWeight(index1,index2);
    }

    public double shortestPathWeight(int index1,int index2) {

        int[] previous = new int[numVertices];//保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合
        Double[] weight = new Double[numVertices];
        boolean[] visit = new boolean[numVertices];// visit[i]来判断从源点到"顶点i"的最短路径是否被成功获取


        for (int i = 0; i < numVertices; i++) {
            visit[i] = false;
            previous[i] = 0;
            weight[i] = adjMatrix[index1][i];
        }
        visit[index1] = true;
        weight[index1] = 0.0;


        int k=0;
        StackADT<Integer> stack = new LinkedStack<Integer>();
        for (int i = 1; i < numVertices; i++) {
            Double min = Double.POSITIVE_INFINITY;
            for (int m = 0; m < numVertices; m++) {
                if (visit[m]==false && weight[m]<min) {
                    min = weight[m];
                    k = m;
                }
            }
            visit[k] = true;
            for (int j = 0; j < numVertices; j++) {
                double temp = (adjMatrix[k][j]==Double.POSITIVE_INFINITY
                        ?Double.POSITIVE_INFINITY : (min + adjMatrix[k][j]));
                if (visit[j]==false && (temp<weight[j]) ) {
                    weight[j] = temp;
                    previous[j] = k;
                }
            }

        }
        int index = index2;
        stack.push(index);
        do
        {
            index = previous[index];
            stack.push(index);
        }
        while (index != index1);
        if(weight[index2] < Double.POSITIVE_INFINITY)
        {
            String result = "";
            while (!stack.isEmpty())
                result += vertices[stack.pop()]+" ";
            System.out.println("最便宜的路径为："+result);
        }
        return weight[index2];
    }

    @Override
    public boolean isEmpty() {
        return numVertices==0;
    }

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

    public int getSizeOfIterator(Iterator iterator) {
        int size = 0;
        while(iterator.hasNext()){
            size++;
            iterator.next();
        }
        return size;
    }

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

    protected boolean indexIsValid(int index)
    {
        if (index<size())
            return true;
        else
            return false;
    }

    public int getIndex(T vertex)
    {

        int index = numVertices-1;

        for (int i = 0; i < numVertices; i++) {
            if (vertex.equals(vertices[i])) {
                index = i;
                break;
            }
        }
        return index;
    }
    protected class NetworkIterator 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 NetworkIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }


    protected class NetworkIndexIterator 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 NetworkIndexIterator(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();
        }
    }

}