package second_term.fifteenth_chapter;

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

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

public class ListGraph<T> implements GraphADT<T> {
    protected final int DEFAULT_CAPACITY = 5;
    protected  int numVertices;
    protected ArrayList<GraphNode<T>> list;
    protected int modCount;
    protected GraphNode[] vertices;

    public ListGraph(){
        numVertices = 0;
        modCount = 0;
        vertices = new GraphNode[DEFAULT_CAPACITY];
    }
    public ListGraph(int i){//指定个数的图
        numVertices = 0;
        modCount = 0;
        vertices =new GraphNode[i];
    }
    private boolean IsExist(T temp){
        for (int i=0;i<numVertices;i++){
            if (vertices[i]==temp)
                return true;
        }
        return false;
    }
    @Override
    public void addVertex(T vertex) {
        if ((numVertices + 1) == vertices.length)
            expandCapacity();

        GraphNode<T> node = new GraphNode<>(vertex);
        if (!IsExist(vertex))
            vertices[numVertices] = node;
        else
            System.out.println("已存在该结点！");

        numVertices ++;
        modCount++;
    }

    protected void expandCapacity() {
        GraphNode[] temp = new GraphNode[vertices.length*2];

        for (int i = 0 ; i<numVertices;i++){
            temp[i] = vertices [i];
        }

        vertices = temp;
    }

    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 = 0 ; i<numVertices-1 ;i ++){//删除有联系的边！
            GraphNode temp = vertices[i];

            while(temp.next!=null){
                if (temp.next.element ==vertices[index].element){
                   if (temp.next.next == null){
                       GraphNode temp0 = temp;
                       temp0.next = null;
                       temp = temp0; //当index的结点在最后一个位置 此时不存在temp.next.next
                   }
                   else
                       temp.next = temp.next.next;//不在最后一个位置  存在temp.next.next
                }
                else
                    temp = temp.next;
            }

        }

        numVertices--;
        modCount++;
    }

    private boolean indexIsValid(int index) {
        return (index>=0)&&(index<numVertices);
    }

    @Override
    public void removeVertex(T vertex) throws ElementNotFoundException {
        if (!IsExist(vertex))
            throw  new ElementNotFoundException("ListGraph");
        else{
            removeVertex(getIndex(vertex));
        }

    }
    public int getIndex(T vertex)
    {
        int result=-1;

        for (int i=0;i<numVertices;i++){
            if (vertex==vertices[i].getElement())
            { result=i;
                break;
            }
        }
        return result;
    }

    public void addEdge(int index10 , int index20){
       int  index1 =index10-1;
       int  index2 =index20-1;
        if (indexIsValid(index1)&&indexIsValid(index2)){
            GraphNode temp = vertices[index1];//得到首结点

            while (temp.getNext()!=null){
                if (temp.getNext().getElement() == vertices[index2].getElement()) {
                    System.out.println("已存在该边！");
                    break;
                }
                    temp = temp.next;
            }
            temp.next = new GraphNode(vertices[index2].getElement());//有index10--》index20
                //不能写成temp。next = vertices[index2]//否则会导致  连在一起

            GraphNode temp2 = vertices[index2];

            while (temp2.getNext()!=null){
                if (temp2.getNext().getElement() == vertices[index1].getElement()) {
                    System.out.println("已存在该边！");
                    break;
                }
                temp2 = temp2.next;
            }
            temp2.next = new GraphNode(vertices[index1].getElement());//有index20--》index10
        }

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

    public void removeEdge(int index10, int index20){
        int  index1 =index10-1;
        int  index2 =index20-1;

        if (indexIsValid(index1)&&indexIsValid(index2)) {
            GraphNode temp = vertices[index1];
            while (temp.next !=null){
                if (temp.next.element ==vertices[index2].element){
                    if (temp.next.next==null){
                        GraphNode temp0 = temp;
                        temp0.next = null;
                        temp = temp0;//当index的结点在最后一个位置 此时不存在temp.next.next
                    }
                    else
                        temp.next = temp.next.next;//不在最后一个位置  存在temp.next.next
                }
                else
                    temp = temp.next;
            }//删除index1与index2 的关系

            GraphNode temp2 = vertices[index2];
            while (temp2.next !=null){
                if (temp2.getNext().getElement() ==vertices[index1].getElement()){
                    if (temp2.next.next==null){
                        GraphNode temp0 = temp2;
                        temp0.next = null;
                        temp2 = temp0;//当index的结点在最后一个位置 此时不存在temp.next.next
                    }
                    else
                        temp2.next = temp2.next.next;//不在最后一个位置  存在temp.next.next
                }
                else
                    temp2 = temp2.next;
            }
        }
        modCount++;
    }
    @Override
    public void removeEdge(T vertex1, T vertex2) {
        removeEdge(getIndex(vertex1),getIndex(vertex2));
    }

    public Iterator iteratorBFS(int startIndex){
        Integer x;
        QueueADT<Integer> traversalQueue = new LinkedQueue<Integer>();
        UnorderedListADT<T> resultList = new UnorderedListArrayList<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) vertices[x].element);

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

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

            }
        }
        modCount++;
        return new GraphIterator(resultList.iterator());
    }

    public  boolean isEdge(int i, int j) {
        if(i==j)
            return false;
        GraphNode vertexNode1 = vertices[i];
        GraphNode vertexNode2 = vertices[j];
        while(vertexNode1!=null) {
            if (vertexNode1.getElement() == vertexNode2.getElement())
                return true;
            vertexNode1 =vertexNode1.getNext();
        }
        return false;
    }


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

    public Iterator iteratorDFS(int startIndex){
        Integer x;
        boolean found;
//       T [] vertices1 = (T[])(new Object[numVertices]);
        StackADT<Integer> traversalStack = new LinkedStack<Integer>();
        UnorderedListADT<T> resultList = new UnorderedListArrayList<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) vertices[startIndex].getElement());
        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 (isEdge(x,i) && !visited[i])
                {
                    traversalStack.push(i);
                    resultList.addToRear((T)vertices[i].getElement());
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new GraphIterator(resultList.iterator());
    }
    @Override
    public Iterator iteratorDFS(T startVertex) {
        return iteratorDFS(getIndex(startVertex));
    }

    public Iterator iteratorShortestPath(int startIndex, int targetIndex){
        UnorderedListADT<T> resultList = new UnorderedListArrayList<T>();
        if (!indexIsValid(startIndex) || !indexIsValid(targetIndex))
            return resultList.iterator();

        Iterator<Integer> it = iteratorShortestPathIndices(startIndex,
                targetIndex);
        while (it.hasNext())
            resultList.addToRear((T)vertices[((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 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(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());
    }

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

    @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(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 void printNodeList() {
        for (int i = 0; i < numVertices; i++) {//这里不能用vertices.length,因为 vertices.length> numVertices
            GraphNode nodes = vertices[i];
            System.out.print("顶点：" + vertices[i].getElement());
            while (nodes.getNext() != null) {
                System.out.print(" --> " + nodes.getNext().getElement());
                nodes = nodes.getNext();
            }
            System.out.println(";");
        }
    }

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

    class GraphNode<T>{
        public T element;
        public GraphNode<T> next;

        public GraphNode(T element)  // constructor
        {
            this.element = element;
            next = null;
        }


        //为节点添加邻接点
        public void setNext(GraphNode<T> ver){
            next = ver;
        }

        public GraphNode<T> getNext(){
            return next;
        }

        public T getElement() {
            return element;
        }
    }


}