/* DefaultGraph.java
 * =========================================================================
 * This file is part of the GrInvIn project - http://www.grinvin.org
 * 
 * Copyright (C) 2005-2008 Universiteit Gent
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * A copy of the GNU General Public License can be found in the file
 * LICENSE.txt provided with the source distribution of this program (see
 * the META-INF directory in the source jar). This license can also be
 * found on the GNU website at http://www.gnu.org/licenses/gpl.html.
 * 
 * If you did not receive a copy of the GNU General Public License along
 * with this program, contact the lead developer, or write to the Free
 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

package org.grinvin.graphs;

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

import org.grinvin.gred.undoable.UndoableGraph;

/**
 * Default implementation of {@link UndoableGraph}.
 */
public class DefaultGraph implements UndoableGraph {
    
    /**
     * Creates a new empty graph.
     */
    public DefaultGraph() {
        vertices = new Vertex[10];
        numberOfVertices = 0;
        edges = new HashSet<Edge>();
        modCount = 0;
    }
    
    /* ============================================================
     * VERTEX LIST
     * ============================================================ */
    
    /* The list of vertices is implemented as a dynamic vector.
     * We do not use an ArrayList for reasons of speed and because
     * of problems with the implementation of the iterator.
     */
    
    //
    private Vertex vertices[];
    
    //
    private int numberOfVertices;
    
    //
    private int modCount;
    
    /**
     * Returns the modification count of this graph. This count is incremented
     * every time the graph is changed and serves as a kind of version
     * number for this object.
     */
    public int getModCount() {
        return modCount;
    }
    
    //
    private void ensureCapacity() {
        if (numberOfVertices == vertices.length) {
            Vertex[] oldVertices = vertices;
            int newSize = oldVertices.length == 1 ? 2 : oldVertices.length * 3 / 2;
            vertices = new Vertex[newSize];
            System.arraycopy(oldVertices, 0, vertices, 0, oldVertices.length);
        }
    }
    
    // implements GraphView
    public Vertex getVertex(int index) {
        if (index < 0 || index >= numberOfVertices)
            throw new IndexOutOfBoundsException("Invalid index for vertex");
        else
            return vertices[index];
    }
    
    /* ============================================================
     * INTERNALS
     * ============================================================ */
    
    // implements GraphView
    public int getNumberOfVertices() {
        return numberOfVertices;
    }
    
    /**
     * Collection of edges for this graph.
     */
    protected Collection<Edge> edges;
    
    // implements GraphView
    public int getNumberOfEdges() {
        return edges.size();
    }
    
    // implements Graph
    public Vertex addNewVertex() {
        Vertex v = new DefaultVertex(numberOfVertices);
        
        // add to list
        ensureCapacity();
        vertices[numberOfVertices] =  v;
        numberOfVertices++;
        modCount ++;
        
        return v;
    }
    
    // implements Graph
    public Edge addNewEdge(Vertex firstEndpoint, Vertex secondEndpoint) {
        if (!(contains(firstEndpoint) && contains(secondEndpoint)))
            throw new IllegalArgumentException("adjacent vertices do not belong to the graph");
        for (Iterator<Edge> iterator = edges.iterator(); iterator.hasNext();) {
            Edge edge = iterator.next();
            if ((edge.getFirstEndpoint() == firstEndpoint && edge.getSecondEndpoint() == secondEndpoint)
                    || (edge.getFirstEndpoint() == secondEndpoint && edge.getSecondEndpoint() == firstEndpoint))
                throw new IllegalArgumentException("edge already exists");
        }        
        Edge e = new DefaultEdge(firstEndpoint, secondEndpoint);
        edges.add(e);
        return e;
    }
    
    /**
     * This method is called after a vertex has been removed
     * by the method {@link #remove(Vertex)} or by {@link VertexIterator#remove}.
     * This implementation removes all edges having the given vertex
     * as an endpoint.
     */
    protected void finalizeRemoveVertex(Vertex v) {
        for (Iterator<Edge> iterator = edges.iterator(); iterator.hasNext();) {
            Edge edge = iterator.next();
            if (edge.getFirstEndpoint() == v || edge.getSecondEndpoint() == v)
                iterator.remove();
        }
    }
    
    /**
     * Remove vertex at given index position. The index is known to be
     * within range.<p>
     * Extension classes should override this method rather than
     * {@link #remove(Vertex)} which calls this method.
     * This method is also used by the vertex iterator of this class.
     */
    protected void remove(int index) {
    }
    
    // implements Graph
    public void remove(Vertex v) {
        if (v == null)
            throw new IllegalArgumentException("null vertex not allowed here");
        
        int index = v.getIndex();
        if (index < 0 || index >= numberOfVertices || vertices[index] != v)
            throw new IllegalArgumentException("Vertex does not belong to the graph");
        
        
        numberOfVertices --;
        if (index < numberOfVertices) {
            vertices[index] = vertices[numberOfVertices];
            vertices[index].setIndex(index);
        }
        vertices[numberOfVertices] = null; // enable gc
        modCount ++;
        finalizeRemoveVertex(v);
    }
    
    // implements UndoableGraph
    public void restore(Vertex v) {
        int index = v.getIndex();
        if (index != numberOfVertices) {
            vertices[numberOfVertices] = vertices[index];
            vertices[numberOfVertices].setIndex(numberOfVertices);
        }
        numberOfVertices ++;
        vertices[index] = v;
        modCount++;
    }
    
    // implements UndoableGraph
    public void restore(Edge e) {
        if (!contains(e.getFirstEndpoint())) {
            throw new IllegalArgumentException("First endpoint of edge does not belong to the graph");
        } else if (!contains(e.getSecondEndpoint())) {
            throw new IllegalArgumentException("Second endpoint of edge does not belong to the graph");
        } else {
            edges.add(e);
            modCount++;
        }
    }
    
    /**
     * This method is called after an edge has been removed
     * by the method {@link #remove(Edge)} or by {@link EdgeIterator#remove}.
     * This implementation is empty.
     */
    protected void finalizeRemoveEdge(Edge edge) {
        // nothing to be done
    }
    
    // implements Graph
    public void remove(Edge e) {
        if (e == null)
            throw new IllegalArgumentException("null edge not allowed here");
        if (edges.remove(e))
            finalizeRemoveEdge(e);
        else
            throw new IllegalArgumentException("Edge does not belong to the graph");
    }
    
    // implements GraphView
    public boolean areAdjacent(Vertex v1, Vertex v2) {
        for (Edge e: edges) {
            Vertex first = e.getFirstEndpoint();
            Vertex second = e.getSecondEndpoint();
            if (first == v1 && second == v2)
                return true;
            else if (first == v2 && second == v1)
                return true;
        }
        return false;
    }
    
    // implements GraphView
    public Edge getEdge(Vertex first, Vertex second) {
        for (Edge e: edges) {
            if (first == e.getFirstEndpoint() &&
                    second == e.getSecondEndpoint())
                return e;
        }
        return null;
    }
    
    // implements GraphView
    public boolean contains(Vertex vertex) {
        return vertex.getIndex() >= 0 && vertex.getIndex() < numberOfVertices
                && vertices[vertex.getIndex()] == vertex;
    }
    
    // implements GraphView
    public boolean contains(Edge edge) {
        return edges.contains(edge);
    }
    
    // implements Graph
    public void clear() {
        // clear vertices
        for (int i=0; i < numberOfVertices; i++) {
            vertices[i] = null; // enable gc
        }
        numberOfVertices = 0;
        modCount ++;
        
        edges.clear();
    }
    
    // implements Graph
    public void copy(GraphView original) {
        if (this == original)
            return;
        
        //[kc] cannot use clear because of extension classes
        for (int i=0; i < numberOfVertices; i++) {
            vertices[i] = null; // enable gc
        }
        edges.clear();
        
        //[kc] cannot use addNewVertex, addNewEdge because of extension classes
        numberOfVertices = original.getNumberOfVertices();
        vertices = new Vertex[numberOfVertices];
        for (int i=0; i < numberOfVertices; i++)
            vertices[i] = new DefaultVertex(i);
        for (Edge e: original.edges()) {
            Vertex first = vertices[e.getFirstEndpoint().getIndex()];
            Vertex second = vertices[e.getSecondEndpoint().getIndex()];
            edges.add(new DefaultEdge(first, second));
        }
        
        modCount ++;
    }
    
    /* ============================================================
     * ITERATION
     * ============================================================ */
    
    /**
     * Iterator over all vertices of this graph.
     */
    protected class VertexIterator implements Iterator<Vertex> {
        
        // based on the source code for the AbstractList.Itr
        // Copyright 2004 Sun Microsystems, Inc.
        
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;
        
        /**
         * Index of element returned by most recent call to next.
         * Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;
        
        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;
        
        
        // implements Iterator
        public boolean hasNext() {
            return cursor != numberOfVertices;
        }
        
        // implements Iterator
        public Vertex next() {
            checkForComodification();
            try {
                Vertex next = vertices[cursor];
                lastRet = cursor;
                cursor++;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        
        // implements Iterator
        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            
            try {
                DefaultGraph.this.remove(vertices[lastRet]);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }
        
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    
    // implements GraphView
    public Iterator<Vertex> vertexIterator() {
        return new VertexIterator();
    }
    
    // implements GraphView
    public Iterable<Vertex> vertices() {
        return new Iterable<Vertex> () {
            public Iterator<Vertex> iterator() {
                return new VertexIterator();
            }
        };
    }
    
    /**
     * Iterator over all edges of this graph. Delegates to
     * the set-iterator of the edge set, overriding the implementation
     * of {@code remove} by calling {@link #finalizeRemoveEdge}.
     */
    protected class EdgeIterator implements Iterator<Edge> {
        
        //
        private Edge last;
        
        //
        private Iterator<Edge> delegate;
        
        //
        public EdgeIterator() {
            this.last = null;
            this.delegate = edges.iterator();
        }
        
        // implements Iterator
        public boolean hasNext() {
            return delegate.hasNext();
        }
        
        // implements Iterator
        public Edge next() {
            last = delegate.next();
            return last;
        }
        
        // implements Iterator
        public void remove() {
            delegate.remove();
            finalizeRemoveEdge(last);
        }
        
    }
    
    // implements GraphView
    public Iterator<Edge> edgeIterator() {
        return new EdgeIterator();
    }
    
    // implements GraphView
    public Iterable<Edge> edges() {
        return new Iterable<Edge> () {
            public Iterator<Edge> iterator() {
                return new EdgeIterator();
            }
        };
    }
    
}