package chap15;

import chap10.ArrayUnorderedList;
import chap10.UnorderedListADT;
import chap3.StackADT;
import chap4.LinkedStack;
import chap5.LinkedQueue;
import chap5.QueueADT;

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

public class GraphList<T> implements GraphADT<T> {
    protected int numVertices;
    protected ArrayList<VNode> arrayList = new ArrayList<VNode>();
    protected T[] vertices;
    protected int modCount;
    @Override
    public void addVertex(T vertex) {
        VNode vertexNode = new VNode(vertex);
        arrayList.add(vertexNode);
        numVertices++;
        modCount++;
    }

    @Override
    public void removeVertex(T vertex) {
        VNode vertexNode = new VNode(vertex);
        arrayList.remove(vertexNode);
        numVertices--;
        modCount++;
    }
    public void removeVertex(int index){
        removeVertex(vertices[index]);
    }
    @Override
    public void addEdge(T v1, T v2) {
        if(getIndex(v1)!=-1&&getIndex(v2)!=-1){
            VNode<T> vertexNode1 = arrayList.get(getIndex(v1));
            VNode<T> vertexNode2 = arrayList.get(getIndex(v2));
            VNode<T> temp1 = new VNode<>(v1);
            VNode<T> temp2 = new VNode<>(v2);
            while(vertexNode1.getNext() !=null)
                vertexNode1 = vertexNode1.getNext();
            vertexNode1.setNext(temp2);
            while(vertexNode2.getNext() !=null)
                vertexNode2 = vertexNode2.getNext();
            vertexNode2.setNext(temp1);
        }
    }
    public void addEdge(int index1, int index2){
        addEdge(vertices[index1],vertices[index2]);
    }

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

        if(getIndex(v1)!=-1&&getIndex(v2)!=-1){
            VNode<T> vertexNode1 = arrayList.get(getIndex(v1));
            VNode<T> vertexNode2 = arrayList.get(getIndex(v2));
            VNode<T> temp1 = null,temp2 = null;

            while(vertexNode1.getElement() != v2 ) {
              temp1 = vertexNode1;
              vertexNode1 = vertexNode1.getNext();
            }
            if(vertexNode1.getNext()==null)
                temp1.setNext(null);
            else{
                VNode<T> temp = vertexNode1.getNext();
                temp1.setNext(temp);
                }


                while(vertexNode2.getElement() != v1  ) {
                    temp2 = vertexNode2;
                    vertexNode2 = vertexNode2.getNext();
                }
                if(vertexNode2.getNext()==null)
                    temp2.setNext(null);
                else{
                    VNode<T> temp = vertexNode2.getNext();
                    temp2.setNext(temp);
                }
            }
        }
    public void removeEdge(int index1, int index2){
        removeEdge(vertices[index1],vertices[index2]);
    }
    public Iterator iteratorDFS(T startVertex) {
        return iteratorDFS(getIndex(startVertex));

    }
    public Iterator<T> iteratorDFS(int startIndex)
    {
        Integer x;
        boolean found;
        this.vertices = (T[])(new Object[numVertices]);
        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((T) arrayList.get(startIndex).getElement());
        visited[startIndex] = true;

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


            for (int i = 0; (i < numVertices) && !found; i++)
            {
                if (isEdge(x,i) && !visited[i])
                {
                    traversalStack.push(i);
                    resultList.addToRear((T) arrayList.get(i).getElement());
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new GraphIterator(resultList.iterator());
    }

    @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((T) arrayList.get(x).getElement());


            for (int i = 0; i < numVertices; i++)
            {
                if (isEdge(x,i) && !visited[i])
                {
                    traversalQueue.enqueue(i);
                    visited[i] = true;
                }

            }
        }
        return new GraphIterator(resultList.iterator());
    }
    protected boolean indexIsValid(int index)
    {
        if (index<numVertices)
            return true;
        else
            return false;
    }
    public boolean isEdge(int i, int j){
        if(i==j)
            return false;
        VNode vertexNode1 = arrayList.get(i);
        VNode vertexNode2 = arrayList.get(j);
        while(vertexNode1!=null) {
            if (vertexNode1.getElement() == vertexNode2.getElement())
                return true;
            vertexNode1 =vertexNode1.getNext();
        }
        return false;
    }

    @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((T) arrayList.get(((Integer)it.next())).getElement());
        return new GraphIterator(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 (isEdge(index,i) && !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 GraphIndexIterator(resultList.iterator());
    }
    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;
    }
    public int shortestPathLength(T startVertex, T targetVertex){
        return shortestPathLength(getIndex(startVertex),getIndex(targetVertex));
    }
    public int getIndex(T vertex){
        VNode vertexNode = new VNode(vertex);
        for(int i = 0;i<numVertices;i++){
            if(arrayList.get(i).getElement()==vertex)
                return i;
        }
        return -1;
    }
    @Override
    public boolean isEmpty() {
        if(numVertices ==0)
            return true;
        else
            return false;
    }

    @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 String toString(){
        if (numVertices == 0)
            return "Graph is empty";

        String result="顶点：";
        for (int i = 0; i < arrayList.size(); i++) {
            result += arrayList.get(i).getElement() + " ";
        }
        result += "\n\n边：\n";
        for (int i=0;i<numVertices;i++)
        {
            VNode<T> temp = arrayList.get(i);
            while(temp != null){
                result += temp.getElement() + ",";
                temp = temp.getNext();
            }
            result += "\n";
        }

        return result;
    }

    public class GraphIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;


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