package second_term.fifteenth_chapter;

import second_term.first_week.StackADT;
import second_term.second_week.LinkedStack;
import second_term.sixth_chapter.UnorderedListADT;
import second_term.sixth_chapter.UnorderedListArrayList;
import second_term.third_week.LinkedQueue;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class NetworkGraph<T> implements  NetworkGraphADT<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 NetworkGraph() {
        numVertices = 0;
        this.adjMatrix = new Double[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        for (int i = 0; i < DEFAULT_CAPACITY; i++)
            for (int j = 0; j < DEFAULT_CAPACITY; j++)
                adjMatrix[i][j] = -1.0;
        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] != -1)
                    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";

        result += "Weight weight\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] != -1)
                    result += adjMatrix[i][j] + "  ";
                else
                    result += "0 " + "  ";
            }
            result += "\n";
        }
        return result;
    }

    public void addEdge(int index1, int index2) {
        if (indexIsValid(index1) && indexIsValid(index2)) {
            adjMatrix[index1][index2] = Double.POSITIVE_INFINITY;
            adjMatrix[index2][index1] = Double.POSITIVE_INFINITY;
            modCount++;
        }
    }

    public void removeEdge(int index1, int index2) {
        // To be completed as a Programming Project
        if (indexIsValid(index1) && indexIsValid(index2)) {
            adjMatrix[index1][index2] = -1.0;
            adjMatrix[index2][index1] = -1.0;
            modCount++;
        }
    }

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


    public void addEdge(int start, int end, double weight) {
        if (indexIsValid(start) && indexIsValid(end)) {
            adjMatrix[start][end] = weight;
            adjMatrix[end][start] = weight;
            modCount++;
        }
    }


    @Override
    public double shortestPathWeight(T vertex1, T vertex2) {
        return shortestPathWeight(getIndex(vertex1), getIndex(vertex2));
    }


    public double shortestPathWeight(int start, int end) {
        int[] previous = new int[numVertices];
        Double[] dist = new Double[numVertices];
        boolean[] flag = new boolean[numVertices];


        for (int i = 0; i < numVertices; i++) {
            flag[i] = false;
            previous[i] = 0;
            dist[i] = adjMatrix[start][i];
        }

        flag[start] = true;

        int k = 0;
        for (int i = 0; i < numVertices; i++) {

            Double min = Double.POSITIVE_INFINITY;
            for (int j = 0; j < numVertices; j++) {
                if (flag[j] == false && dist[j] < min && dist[j] != -1 && dist[j] != 0) {
                    min = dist[j];
                    k = j;
                }
            }
            flag[k] = true;

            for (int j = 0; j < numVertices; j++) {
                if (adjMatrix[k][j] != -1&&dist[j]!= -1) {
                    double temp = (adjMatrix[k][j] == Double.POSITIVE_INFINITY
                            ? Double.POSITIVE_INFINITY : (min + adjMatrix[k][j]));
                    if (flag[j] == false && (temp < dist[j])) {
                        dist[j] = temp;
                        previous[j] = k;
                    }
                }
            }
        }
        return dist[end];
    }


    @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] = -1.0;
            adjMatrix[i][numVertices] = -1.0;
        }
        numVertices++;
        modCount++;
    }

    @Override
    public void removeVertex(Object vertex) {

        removeVertex(getIndex((T) vertex));
        numVertices--;
    }

    public void removeVertex(int index) {
        for (int i = index; i < vertices.length - 1; i++) {

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

            }
        }

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


        for (int t = 0; t < numVertices; t++) {
            adjMatrix[index][t] = -1.0;
            adjMatrix[t][index] = -1.0;
        }
        modCount++;
        numVertices--;

    }

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

    @Override
    public void removeEdge(T vertex1, T vertex2) {
        removeEdge((getIndex(vertex1)), getIndex(vertex2));
    }


    public Iterator<T> iteratorDFS(int startIndex) {
        Integer x;
        boolean found;
        LinkedStack<Integer> traversalStack = new LinkedStack<Integer>();
        UnorderedListADT<T> resultList = new UnorderedListArrayList<>();
        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;

            //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.intValue()][i] != -1 && !visited[i]) {
                    traversalStack.push(new Integer(i));
                    resultList.addToRear(vertices[i]);
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new NetworkGraph.GraphIterator(resultList.iterator());
    }


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


    public Iterator<T> iteratorBFS(int startIndex) {
        Integer x;
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
        UnorderedListADT<T> resultList = new UnorderedListArrayList<>();

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

            for (int i = 0; i < numVertices; i++) {
                if (adjMatrix[x.intValue()][i] != -1 && !visited[i]) {
                    traversalQueue.enqueue(new Integer(i));
                    visited[i] = true;
                }
            }
        }
        return new NetworkGraph.GraphIterator(resultList.iterator());
    }


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

    protected Iterator<Integer> iteratorShortestPathIndices
            (int startIndex, int targetIndex) {
        int index = startIndex;
        int[] pathLength = new int[numVertices];
        int[] predecessor = new int[numVertices];
        LinkedQueue<Integer> traversalQueue = new LinkedQueue<>();
        UnorderedListADT<Integer> resultList =
                new UnorderedListArrayList<>();

        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] != -1 && !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<>();
        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 NetworkGraph.GraphIndexIterator(resultList.iterator());
    }


    public Iterator<T> iteratorShortestPath(int startIndex,
                                            int targetIndex) {
        UnorderedListADT<T> resultList = new UnorderedListArrayList<>();
        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 NetworkGraph.GraphIterator(resultList.iterator());
    }


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


    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 boolean isEmpty() {
        if (vertices[0].equals(null)) {
            return true;

        } else {
            return false;
        }
    }

    protected boolean indexIsValid(int index) {
        // To be completed as a Programming Project
        boolean a = true;
        if (vertices[index] == null) {
            a = false;
        }
        return a;
    }

    public int getIndex(T vertex) {
        // To be completed as a Programming Project
        int a = -1;
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].equals(vertex)) {
                a = i;
                break;
            }

        }

        return a;
    }

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

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


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

    public 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;
        }


        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 GraphIndexIterator implements Iterator<Integer> {
        private int expectedModCount;
        private Iterator<Integer> iter;


        public GraphIndexIterator(Iterator<Integer> iter) {
            this.iter = iter;
            expectedModCount = modCount;
        }


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

            return (iter.hasNext());
        }


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


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