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 week_5.LanmoyunExperiment.LinearNode;

import java.util.*;

public class IndirectedGraph<T> implements GraphADT{

      protected LinearNode[] vertices;    // values of vertices 保存顶点值的数组
      protected int numVertices;    // number of vertices in the graph 表中的顶点
      protected LinearNode head ;//设置一个头结点
      protected int modCount;

   public IndirectedGraph()
   {
      vertices= new LinearNode[10];
      numVertices=0;

   }

    @Override
    public void addVertex(Object vertex) {
      LinearNode node = new LinearNode();
      node.setElement(vertex);

      vertices[numVertices] = node;
      numVertices++;
    }

    @Override
    public void removeVertex(Object vertex) {

      for(int m = 0 ;m <vertices.length;m++){
          LinearNode currentNode = vertices[m].getNext();
          while(currentNode!=null)
          {
              if(currentNode.getNext() == vertices[getIndex((T) vertex)])
                  currentNode = currentNode.getNext();
          }
      }
        for(int a = (int) vertex; a < vertices.length;a++) {
            vertices[getIndex((T) vertex)] = vertices[getIndex((T) vertex)+1];
        }

        numVertices--;
    }


    @Override
    public void addEdge(Object vertex1, Object vertex2) {

      int a  = getIndex((T) vertex1);
      int b =  getIndex((T) vertex2);
      LinearNode current1 = vertices[a].getNext();
      LinearNode current2 = vertices[b].getNext();
      if(current1==null)
          current1.setNext(vertices[b]) ;
      else
      {
          while(current1.getNext()!=null){
              current1 = current1.getNext();
          }
          current1.setNext(vertices[b]);

      }
        if(current2==null)
            current2.setNext(vertices[a]) ;
        else
        {
            while(current2.getNext()!=null){
                current2 = current2.getNext();
            }
            current2.setNext(vertices[a]);
        }
    }

    @Override
    public void removeEdge(Object vertex1, Object vertex2) {
        int a  = getIndex((T) vertex1);
        int b =  getIndex((T) vertex2);
        while(vertices[a].getNext()!= vertices[b])
        {
            vertices[a]= vertices[a].getNext();
        }
        vertices[a] = vertices[a].getNext().getNext();

        while(vertices[b].getNext()!= vertices[a])
        {
            vertices[b]= vertices[b].getNext();
        }
        vertices[b] = vertices[b].getNext().getNext();

    }

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


    public Iterator 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(new Integer(startIndex));
        visited[startIndex] = true;

        while (!traversalQueue.isEmpty())
        {
            x = traversalQueue.dequeue();
            resultList.addToRear((T) 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 (vertices[x].getNext()!= null && !visited[i])
                {
                    traversalQueue.enqueue((Integer) vertices[x].getNext().getElement());
                    visited[i] = true;
                }
            }
        }
        return new GraphIterator(resultList.iterator());
    }

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

        public GraphIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }
        @Override
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        @Override
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }
    }
    @Override
    public Iterator iteratorDFS(Object startVertex) {
        return iteratorDFS(getIndex((T) 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(new Integer(startIndex));
        resultList.addToRear((T) 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 (vertices[i]!=null && !visited[i])
                {
                    traversalStack.push(new Integer(i));
                    resultList.addToRear((T) vertices[i].getNext().getElement());
                    visited[i] = true;
                    found = true;
                }
            }
            if (!found && !traversalStack.isEmpty())
                traversalStack.pop();
        }
        return new GraphIterator(resultList.iterator());
    }
    @Override
    public Iterator iteratorShortestPath(Object startVertex, Object targetVertex) {
        return iteratorShortestPath(getIndex((T) startVertex),
                getIndex((T) targetVertex));
    }

    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(new Integer(startIndex));
        visited[startIndex] = true;
        pathLength[startIndex] = 0;
        predecessor[startIndex] = -1;//从-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 (vertices[i]!=null && !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<Integer>();
        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 GraphIndexIterator(resultList.iterator());
    }

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


    /**
     * Returns an iterator that contains the shortest path between
     * the two vertices.
     *
     * @param startIndex the starting index
     * @param targetIndex the target index
     * @return an iterator that contains the shortest path
     *           between the given vertices
     */
    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) vertices[((Integer)it.next()).intValue()]);
        return new GraphIterator(resultList.iterator());
    }


    @Override
    public boolean isEmpty() {
        if(vertices.length == 0)
            return true;
        else
            return false;
    }

    @Override
    public boolean isConnected() {
        boolean mobile = true;
        LinkedQueue queue =new LinkedQueue();
        for(int m = 0;m<numVertices-1;m++) {
            Iterator iterator = iteratorBFS(m);
            while (iterator.hasNext()) {
                queue.enqueue(iterator.next());
            }
            if (queue.size() == numVertices) {
                mobile=true;
            } else {
                mobile=false;
            }
        }
        return mobile;
    }

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

    public int getIndex(T vertex) {
        int a = 0;
        for (a = 0; a < vertices.length; a++) {
            if (vertex == vertices[a])
                break;
        }
        return a;
    }

    protected boolean indexIsValid(int index)
    {
        if(vertices[index]!=null&&index<vertices.length)
            return true;
        else
            return false;

    }

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

        String result = new String("");

        result += "Adjacency List\n";
        result += "----------------\n";
        result += "index\t";

        for (int i = 0; i < vertices.length; i++) {
            LinearNode nodes = vertices[i];
            result += "顶点：" + vertices[i].getElement();
            while (nodes.getNext() != null) {
                result+=" --> " + nodes.getNext().getElement();
                nodes = nodes.getNext();
            }
            result+="\n";
        }

        return result;
    }
}