////////////////////////////////////////////////////////////////////////
//
// Intro to AI Assignment #4
//
// File:  Assign4.java
//
// Authors:       Jeff Stephenson       
// Date:          November 11, 1997         
// JDK Version:   1.1.1  
// Machine Type:  PC 
// Comments:      TA Solution to Assignment #4     
//          
////////////////////////////////////////////////////////////////////////


import java.util.Vector;
import java.util.StringTokenizer;
import java.net.*;

import Link;
import LinkHandler;


public class Assign4
{
   public static void main(String args[])
   {
      //Main function calls your graph building function
         
      Graph g = new Graph();

      if (args.length != 2)
      {
         System.out.println("Syntax:  java Assign4 <pageAddress> <MAX_VERTICIES>");
         return;
      }
      
      String pageAddress = args[0];
      int MAX_VERTICIES = Integer.parseInt(args[1]);

      fillTheGraph(g, MAX_VERTICIES, pageAddress);
      
      g.printGraph();
            
      

   }


   //The filltheGraph function performs a breadth first search on the 
   //web starting at the String page address and ending when MAX_VERTICIES
   //has been reached.  A queue is used to facilitate the breadth first search
   //process.  
   public static void fillTheGraph(Graph g, int MAX_VERTICIES, String page)
   {
      Vector queue;
      queue = new Vector();
      boolean done=false;
      
      String temp;
      queue.addElement(page);
      
      Vector linkList;
      Vertex tempVer;
      LinkHandler handler;
      handler = new LinkHandler();
      Link tempLink;
        
      g.insertVertex(page);
            
      while (!queue.isEmpty() && !done)
      {
         temp = (String) queue.firstElement();
         queue.removeElementAt(0);
         linkList = handler.getListOfLinks(temp);
         while (!linkList.isEmpty())
         {
            tempLink = (Link) linkList.firstElement();
            tempVer = g.getVertexbyName(tempLink.getAddress());
            if ((tempVer == null) && !done)
            {
               g.insertVertex(tempLink.getAddress());
               queue.addElement(tempLink.getAddress());  
            }
            if ((g.getNumberOfVerticies()-1) >= MAX_VERTICIES)
            {
               done = true;
            } 
            
            g.insertEdgebyNameExpanded(temp, tempLink.getAddress(), tempLink.getContext(), sortTheContext(tempLink.getContext()));
            linkList.removeElementAt(0);   
         }   
      
      }
   }

   //sortTheContext implements a classic bucket sort (sorting into bins).  The string
   //context is broken into words using a StringTokenizer and the words are put into
   //Vector bins based on their first letter (a - z)
   public static Vector sortTheContext(String context)
   {      
      Vector temp;  
      StringTokenizer tokens = new StringTokenizer(context.toLowerCase());
      String someString;
      char someChar;
      int someInt;
      int i = 0;
      
      Vector sortedContext = new Vector(26);
      for (i=0; i<26; i++)
      {
         sortedContext.addElement(new Vector());   
      }
      
      
      while (tokens.hasMoreTokens())
      {
         someString = tokens.nextToken();
         someChar = someString.charAt(0);
         someInt = (int) someChar;
         
         //someInt should now contain a Unicode index for the first character
         //of the token a = 97, b = 98, c = 99, ....... z = 122 (using the JDK
         //character set) Throw out strings that don't start with a lower case
         //letter (where someInt is less than 97 or greater  than 122).
         
         if ((someInt >= 97) && (someInt <= 122))
         {
            someInt = someInt - 97;
            temp = (Vector) sortedContext.elementAt(someInt);
            temp.addElement(someString);
         }
              
      }
      
      return sortedContext;
   }

}


/**
 * This class contains the fields and methods needed for 
 * the representation of a graph Vertex
 */

class Vertex
{
   String pageAddress;     //the page address (http://www. ....)
   Edge_List edges;     //LList of edges

   //Constructor
   public Vertex (String pageAddress)
   {
      this.pageAddress = pageAddress;
      edges = null;
   }

   //returns pageAddress
   public String getPageAddress()
   {
      return pageAddress;
   }

   //sets pageAddress
   public void setPageAddress(String pageAddress)
   {
      this.pageAddress = pageAddress;
   }


   public void insertEdgeBasic(String neighborAddress, int indexOfNeighbor, String context)
   {
      Edge_List temp;
      Edge_List iter;      
      boolean found = false;
      
      iter = edges;
      
      while ((iter != null) && !found)
      {
         if (neighborAddress.equals(iter.getNeighborAddress()))
         {
            found = true;
         }
         
         iter = iter.getNext();   
      }
      
      if (!found)
      {
         temp = new Edge_List(neighborAddress, indexOfNeighbor, context);
         temp.setNext(edges);
         edges = temp;
      }   
   }

   public void insertEdgeExpanded(String neighborAddress, int indexOfNeighbor, String context, Vector sortedContext)
   {
      insertEdgeBasic(neighborAddress, indexOfNeighbor, context);
      if (edges.getNeighborAddress().equals(neighborAddress))
      {
         edges.setSortedContext(sortedContext);
      }     
   }
  
   public String toString()
   {
      String printString = "";
      Edge_List iter;
      
      iter = edges;
      printString = printString + "Vertex:  "+pageAddress + "\n";
      
      while (iter != null)
      {
         printString = printString + "\tEdge:  "+iter.getNeighborAddress() + "\n";
         iter = iter.getNext();
      }
      
      return printString;
   }
   
}


class Edge_List
{
   String neighborAddress;  //address of neighbor (http://www. ...)
   int indexOfNeighbor;  //index of neighbor in Vector of verticies
   String context;          //context of the link
   Vector sortedContext;    //sorted context of the link (third part of assignment)
   Edge_List next;          //the next edge in the list

   //Constructor
   public Edge_List (String neighborAddress, int indexOfNeighbor, String context)
   {
      this.neighborAddress = neighborAddress;
      this.indexOfNeighbor = indexOfNeighbor;
      this.context = context;
      sortedContext = null; 
      next = null;
   }
   
   //Returns neighborAddress
   public String getNeighborAddress()
   {
      return neighborAddress;
   }

   //Returns indexOfNeighbor
   public int getIndexOfNeighbor()
   {
      return indexOfNeighbor;
   }

   //Returns next edge
   public Edge_List getNext()
   {
      return next;
   }

   //Return context
   public String getContext()
   {
      return context;
   }

   //Returns sorted context
   public Vector getSortedContext()
   {
      return sortedContext;
   }

   //Sets neighborAddress
   public void setNeighborAddress(String neighborAddress)
   {
      this.neighborAddress = neighborAddress;
   }

   //Sets indexOfNeighbor
   public void setIndexOfNeighbor(int index)
   {
      this.indexOfNeighbor = index;
   }

   //Sets next edge
   public void setNext(Edge_List next)
   {
      this.next = next;
   }

   //Sets context
   public void setContext(String context)
   {
      this.context = context;
   }

   //Sets sortedContext
   public void setSortedContext(Vector sortedContext)
   {
      this.sortedContext = sortedContext;
   }
}



class Graph
{
   Vector verticies;  //the vector of vertex objects
   int numberOfVerticies;

   public Graph()
   {
      verticies = new Vector();
      numberOfVerticies = 0;
   }

   public int getNumberOfVerticies()
   {
      return numberOfVerticies;
   }

   public void insertVertex(String pageAddress)
   {
      Vertex newVer;
      Vertex temp;
      boolean found = false;
      int i=0;
      
      while ((i<numberOfVerticies) && !found)
      {
         temp = (Vertex) verticies.elementAt(i);
         if (temp.getPageAddress().equals(pageAddress))
         {
            found = true;
         }
         
         i++;   
      }
      
      if (!found)
      {
         newVer = new Vertex(pageAddress);
         verticies.addElement(newVer);
         numberOfVerticies++;
      }
   }

   public void insertEdgebyNameBasic(String fromThisAddress, String toThisAddress, String context)
   {
      Vertex from;
      Vertex toVer;
      
      from = getVertexbyName(fromThisAddress);
      toVer = getVertexbyName(toThisAddress);
      
      if ((from != null) && (toVer != null))
      {
         from.insertEdgeBasic(toVer.getPageAddress(), verticies.indexOf(toVer), context);
      } 
   }

   public void insertEdgebyNumberBasic(int fromIndex, int toIndex, String context)
   {
      Vertex from;
      Vertex toVer;
      
      from = getVertexbyNumber(fromIndex);
      toVer = getVertexbyNumber(toIndex);
      
      if ((from != null) && (toVer != null))
      {
         from.insertEdgeBasic(toVer.getPageAddress(), toIndex, context);
      }
      
   }

   
   public void insertEdgebyNameExpanded(String fromThisAddress, String toThisAddress, String context, Vector sortedContext)
   {
      Vertex from;
      Vertex toVer;
      
      from = getVertexbyName(fromThisAddress);
      toVer = getVertexbyName(toThisAddress);
      
      if ((from != null) && (toVer != null))
      {
         from.insertEdgeExpanded(toVer.getPageAddress(), verticies.indexOf(toVer), context, sortedContext);
      } 

   }

   public void insertEdgebyNumberExpanded(int fromIndex, int toIndex, String context, Vector sortedContext)
   {
      Vertex from;
      Vertex toVer;
      
      from = getVertexbyNumber(fromIndex);
      toVer = getVertexbyNumber(toIndex);
      
      if ((from != null) && (toVer != null))
      {
         from.insertEdgeExpanded(toVer.getPageAddress(), toIndex, context, sortedContext);
      }
  
   }

   public Vertex getVertexbyName(String address)
   {
      int i;
      Vertex temp;
      
      for (i=0; i<numberOfVerticies; i++)
      {
         temp = (Vertex) verticies.elementAt(i);
         if (temp.getPageAddress().equals(address))
         {
            return temp;
         }   
      }

      return null;
   }

   public Vertex getVertexbyNumber(int index)
   {
      if (index < numberOfVerticies)
      {
         return ((Vertex) verticies.elementAt(index));
      }
      
      return null; 
   }

   public void printGraph()
   {
      int i;
      Vertex temp;
      
      for (i=0; i<numberOfVerticies; i++)
      {
         temp = (Vertex) verticies.elementAt(i);
         System.out.println(temp);  
      }
   }

}