import java.util.*;

public class myListGraph
{
	protected String[] names;	// 1-d array to store the vertices
	protected LinkList[] Edges;	// 1-d array to store adjacencies between vertices,

	protected int numVertices;	
	protected int numEdges;

	// Default constructor. Sets aside enough capacity for one vertex
	public myListGraph( )		
	{			
		this(1);
	}

	// Constructor that sets aside as much capacity as specified by the user
	public myListGraph(int capacity)	
	{			
		names = new String[capacity];
		Edges = new LinkList[capacity];
		for (int i = 0 ; i < capacity ; i ++) {
			Edges [i] = new LinkList();
		}

	}
	
	public int numberOfVertices()
   	{
       	         return numVertices;
        }

        public int numberOfEdges()
        {
       	         return numEdges;
        }

	// Finds the location at which a vertex is stored in Vertices. 
	// Returns -1 if vertex not found
	public int getIndex(String vertex)
	{
		for(int i = 0; i < numVertices; i++)
			if(vertex.equals(names[i]))
				return i;

		return -1;
	}

	// Resizes the array of vertices. Can make it larger or smaller, depending
	// on what newSize is. 
	protected String[] resize(String[] array, int newSize)
	{
		String[] temp = new String[newSize];
		
		int smallerSize = newSize;
		if(array.length < smallerSize)
			smallerSize = array.length;

		for(int i = 0; i < smallerSize; i++)
			temp[i] = array[i];

		return temp;
	}

	protected LinkList[] resize (LinkList[] array, int newSize)
	{
		LinkList[] temp = new LinkList[newSize];
		
		int smallerSize = newSize;
		if(array.length < smallerSize)
			smallerSize = array.length;

		for(int i = 0; i < smallerSize; i++)
			temp[i] = array[i];

		for (int i = smallerSize ; i < temp.length ; i ++)
			temp [i] = new LinkList();

		return temp;
	}

	// Adds a new vertex
	public void addVertex(String newVertex)
	{
		if(getIndex(newVertex) != -1)
		{
			System.out.print("addVertex: ");
			System.out.print(newVertex);
			System.out.println(" failed -- vertex already exists.");
			return;
		}
		
		// if array of vertices is full, we need to expand it and 
		// also expand Edges
		if (names.length == numVertices)
		{
			names = resize(names, 2*numVertices+1);
			Edges = resize(Edges, 2*numVertices+1);
		}
			
		names[numVertices++] = newVertex;
	}


	// Adds a new edge
	public void addEdge(String vertex1, String vertex2)
	{
		int i = getIndex(vertex1);
		if(i == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex1);
			System.out.println(" does not exist.");
            		return;
        	}

		int j = getIndex(vertex2);
		if(j == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex2);
			System.out.println(" does not exist.");
            		return;
        	}

		Edges [i].insertFirst (names [j]);
		Edges [j].insertFirst (names [i]);


		numEdges++;
	}

	public void printAdjacencyList (String vertex)
	{
		int i = getIndex(vertex);
		if(i == -1)
		{
			System.out.print("addEdge failed: ");
			System.out.print(vertex);
			System.out.println(" does not exist.");
            		return;
        	}

		System.out.print (vertex + " is connected to ");
		Edges [i].displayList();		
	}
} // end of class