import structure.*;
import java.util.Iterator;
import java.util.Collection;


public class MyMatrixGraph extends MyAbstractGraph
{
    protected Vector map;
    protected Matrix adjacencyMatrix;
    protected int numEdges;
    protected int numVertices;

    protected Integer One;
    protected Integer Zero;

    public MyMatrixGraph()
    {
        this(1);
    }


    // the parameter this constructor takes is the expected number of
    // vertices... more can be added later, but this will pre-build the
    // matrix and vector to handle n vertices
    public MyMatrixGraph( int n )
    {
        map = new Vector(n);
        adjacencyMatrix = new Matrix(n,n);
        numVertices = 0;
        numEdges = 0;

        One = new Integer(1);
        Zero = new Integer(0);
    }


    public int numberOfVertices()
    {
        return numVertices;
    }

    public int numberOfEdges()
    {
        return numEdges;
    }

    public int getIndex( Object v )
    {
        return map.indexOf(v);
    }

    public Object getMapItem( int i )
    {
        return map.get(i);
    }

    public void addVertex( Object v )
    {
        int newIndex;

        // make sure the vertex isn't already there
        if( getIndex(v) != -1 )
            return;

        // the new vertex will be added at the end of the Vector, so its
        // index will be current number of vertices
        newIndex = numVertices;
        numVertices++;

        // add the vertex to the map
        map.add( v );

        // since the adjacency matrix is nxn, newIndex will work here too...
        if( numVertices > adjacencyMatrix.width() )
        {
            adjacencyMatrix.addRow( newIndex );
            adjacencyMatrix.addCol( newIndex );
        }

        // the newly added vertex has no edges, so fill in 0's in the matrix
        for( int i = 0; i < numVertices; i++ )
        {
            adjacencyMatrix.set( newIndex, i, Zero );
            adjacencyMatrix.set( i, newIndex, Zero );
        }
    }

    public void addEdge( Object u, Object v )
    {
        // get the map indices of u and v, and make sure both of them exist
        int a = getIndex(u);
        int b = getIndex(v);
        if( a == -1 || b == -1 )
            throw new IllegalArgumentException();

        // check to see if this edge already exists
        if( ((Integer)adjacencyMatrix.get(a,b)).intValue() == 1 )
            return;

        // add the edge
        adjacencyMatrix.set( a, b, One );
        adjacencyMatrix.set( b, a, One );
        numEdges++;
    }

    public void deleteVertex( Object v )
    {
        // get the index of the vertex, and make sure it exists
        int index = getIndex(v);
        if( index == -1 )
            throw new IllegalArgumentException();

        // all the edges of this vertex will disappear too, so the
        // edge count needs to be adjusted properly
        for( int i = 0; i < numVertices; i++ )
        {
            if( ((Integer)adjacencyMatrix.get(index,i)).intValue() == 1 )
                numEdges--;
        }

        // remove the vertex from the map and matrix
        map.remove( index );
        adjacencyMatrix.removeRow( index );
        adjacencyMatrix.removeCol( index );
        
        // adjust the count
        numVertices--;
    }

    public void deleteEdge( Object u, Object v )
    {
        // get the map indices of u and v, and make sure both of them exist
        int a = getIndex(u);
        int b = getIndex(v);
        if( a == -1 || b == -1 )
            throw new IllegalArgumentException();

        // set the edge to zero in the matrix and adjust the count...
        // but only if the edge was there in the first place
        if( ((Integer)adjacencyMatrix.get(a,b)).intValue() == 1 )
        {
            adjacencyMatrix.set( a, b, Zero );
            adjacencyMatrix.set( b, a, Zero );
            numEdges--;
        }
    }

    public boolean areNeighbors( Object u, Object v )
    {
        // get the map indices of u and v, and make sure both of them exist
        int a = getIndex(u);
        int b = getIndex(v);
        if( a == -1 || b == -1 )
            throw new IllegalArgumentException();

        // the two are neighbors if their entry in the matrix is 1
        if( ((Integer)adjacencyMatrix.get(a,b)).intValue() == 1 )
            return true;
        return false;
    }

    public Vector getVertices()
    {
        // we already have a Vector of the vertices - map - so just return a clone of that
        return (Vector)map.clone();
    }

    public Matrix getEdges()
    {
        Matrix results = new Matrix( 2, numEdges );
        int edges = 0;

        for( int i = 0; i < numVertices; i++ )
        {
            // by starting this inner loop at i, instead of zero, we only loop
            // through one diagonal of the matrix and thus avoid double counting
            for( int j = i; j < numVertices; j++ )
            {
                if( ((Integer)adjacencyMatrix.get(i,j)).intValue() == 1 )
                {
                    results.set( 0, edges, map.get(i) );
                    results.set( 1, edges, map.get(j) );
                    edges++;
                }
            }
        }
        return results;
    }

    public Vector getNeighbors( Object v )
    {
        Vector results;
        int index;

        // make a vector to return
        results = new Vector();
    
        // get v's index and make sure it exists
        index = getIndex(v);
        if( index == -1 )
            throw new IllegalArgumentException();

        // go through the matrix, look at the neighbors, and populate the matrix
        for( int i = 0; i < numVertices; i++ )
        {
            if( ((Integer)adjacencyMatrix.get(index,i)).intValue() == 1 )
                results.add( map.get(i) );
        }

        return results;
    }
}