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


public class MyListGraph extends MyAbstractGraph
{
	protected Vector map;
	protected Vector adjList;
	protected int numEdges;
	protected int numVertices;

	public MyListGraph()
	{
		map = new Vector();
		adjList = new Vector();
		numVertices = 0;
		numEdges = 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;

		// add the vertex to the map and adjacency list
		map.add( v );
		adjList.add( new DoublyLinkedList() );
		numVertices++;
	}

	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( ((DoublyLinkedList)adjList.get(a)).indexOf(v) != -1 )
			return;

		// add the edge
		((DoublyLinkedList)adjList.get(a)).addLast(v);
		((DoublyLinkedList)adjList.get(b)).addLast(u);
		numEdges++;
	}

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

		// first delete it from the map and adjacency list
		map.removeElementAt( index );
		adjList.removeElementAt( index );

		// adjust the count
		numVertices--;

		// 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( ((DoublyLinkedList)adjList.get(i)).remove(v) != null )
				numEdges--;
		}
	}

	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();
		
		if( ((DoublyLinkedList)adjList.get(a)).indexOf(v) != -1 )
		{
			((DoublyLinkedList)adjList.get(a)).remove(v);
			((DoublyLinkedList)adjList.get(b)).remove(u);
			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 one is in the other's edge list
		if( ((DoublyLinkedList)adjList.get(a)).indexOf(v) != -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;
	}

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

		for( int i = 0; i < numVertices; i++ )
		{
			neighbors = (DoublyLinkedList)adjList.get(i);
			DoublyLinkedListIterator iter = (DoublyLinkedListIterator)neighbors.iterator();
			while( iter.hasNext() )
			{
				// we're looking at all the neighbors of this vertex. If the neighbor
				// we're looking at has a lower index than the current index, it means
				// we've already looked at that vertex, and so this edge has already
				// been added, so we can ignore it instead of adding it a second time.
				int index = map.indexOf( iter.get() );
				if( index > i )
				{
					results.set( 0, edges, map.get(i) );
					results.set( 1, edges, map.get(index) );
					edges++;
				}
				iter.next();
			}
		}
		return results;
	}

	public Vector getNeighbors( Object v )
	{
		DoublyLinkedList neighbors;
		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 adjacency list, look at the neighbors, and populate the vector
		neighbors = (DoublyLinkedList)adjList.get(index);
		DoublyLinkedListIterator iter = (DoublyLinkedListIterator)neighbors.iterator();
		while( iter.hasNext() )
		{
			results.add( iter.get() );
			iter.next();
		}
		return results;
	}
}