////////////////////////////////////////////////////////////////////////
//
// Intro to AI Assignment #3
//
// File:          Assign3.java
//
// Authors:       Jeff Stephenson       
// Date:          November 6, 1997         
// JDK Version:   1.1.1  
// Machine Type:  PC/Win95 
// Comments:      TA Solution to Assignment #3     
//          
////////////////////////////////////////////////////////////////////////

import java.io.*;
import java.util.Vector;
import java.util.StringTokenizer;
import java.util.Random;

import MapValues;
import CityMap;
import CityInfo;
import MapException;
import Path_element;

public class Assign3 implements MapValues
{
  /**
   * This method sets up the map simulator and calls the students methods
   * with start and goal states.  Ten calls are made for each stage.
   * Between stages, the map is randomly changed by calling randomizeMap().
   */
   
   public static Vector table[][];     //memoizing table
   public static CityMap theMap;

   public static void main(String args[])
   {

      int i;
      int j;
      String filename;
      
      if (args.length != 1)
      {
         System.out.println("Syntax: java Assign3 <filename> ");
         return;
      }
      
      filename = ("./" + args[0]);
      
      theMap = new CityMap();
      mapFromFile(filename, theMap);
      int numberCities = theMap.getNumberCities();
      
      System.out.println("Number of cities:  "+numberCities);  

      Random genr = new Random();
      int startIndex;
      String start;
      int goalIndex;
      String goal;

      table  = new Vector[numberCities][numberCities];
      for(i=0;i<numberCities; i++)
      {
         for(j=0; j<numberCities; j++)
         {
            table[i][j] = new Vector();
         }
      }
      
      Vector result;

      for(i=0; i<10; i++)
      {
         startIndex = (int) ((genr.nextFloat() * numberCities));
         goalIndex = (int) (genr.nextFloat() * numberCities);
         start = theMap.getCityByNumber(startIndex);
         goal = theMap.getCityByNumber(goalIndex);

         result = simple_expansion(start, goal);

         System.out.println("Stage #1 Query #" + i +": ");
         printPathVector(result, start, goal);
      }

      theMap.randomizeMap();

      for(i=0; i<10; i++)
      {
         startIndex = (int) (genr.nextFloat() * numberCities);
         goalIndex = (int) (genr.nextFloat() * numberCities);
         start = theMap.getCityByNumber(startIndex);
         goal = theMap.getCityByNumber(goalIndex);

         result = path_validation(start, goal);
         System.out.println("Stage #2 Query #" + i +": ");
         printPathVector(result, start, goal);
      }
          
      
   }
   
  
  /**
   * Filled in by the student.  See assignment document.
   * Stage #1 method
   */
   public static Vector simple_expansion(String start, String goal)
   {
   
      Vector path = null;
      int indexStart = theMap.getIndexofCity(start);
      int indexGoal = theMap.getIndexofCity(goal);

      Vector lookup;
      
      lookup = table[indexStart][indexGoal];
      if (lookup != null)
      {
         if (lookup.size() != 0)
         {
            return ((Vector) lookup.clone());
         }
      }
      
      if (start.equals(goal))
      {
         return null;  
      }
      else
      {
         boolean goalFound = false;
         boolean impossible = false;
         int depth =0;
         int maxdepthwent;
         path = new Vector();
         path.addElement(new Path_element("X", start));
         while(!goalFound && !impossible)
         {
            depth++;
            maxdepthwent = iterative_deepening(start, goal, path, depth, 0);
            if(maxdepthwent == -1)
            {
               goalFound = true;
            }
            else
            {
               if (maxdepthwent < depth)
               {
                  impossible = true;
               }
            } 
         }
         
         if (goalFound)
         {
            path = table[indexStart][indexGoal];
         }
         else
         {
            path = new Vector();
            path.addElement(new Path_element("X", "NO PATH"));
         }  
      }

      return path;

   }

  /**
   * Iterative deepening method implements a bounded depth-first search.  When
   * called with increasing depth parameters the breadth-first search invariant
   * is maintained (ply n fully examined before ply n+1).  The function returns
   * -1 if it finds a win, else it returns the maximum depth that it was able to
   * get to in the tree.
   *
   */

   public static int iterative_deepening(String current, String goal,Vector path, int depth, int maxdepthwent)
   {
   
      if (depth == 0)
      {
      
         Vector pathCopy = (Vector) path.clone();
         Path_element head;
         Path_element tail;
         String headCity;
         String tailCity;
         
         if (pathCopy.size() != 0)
         {
            head = (Path_element) pathCopy.elementAt(0);
            tail = (Path_element) pathCopy.lastElement();
            headCity = head.getCityInThatDirection();
            tailCity = tail.getCityInThatDirection();
            
            while (!headCity.equals(tailCity))
            {
               pathCopy.removeElementAt(0);
               table[theMap.getIndexofCity(headCity)][theMap.getIndexofCity(tailCity)] = (Vector) pathCopy.clone();
               head = (Path_element) pathCopy.elementAt(0);
               headCity = head.getCityInThatDirection();
            }
         }
                 
         if (current.equals(goal))
         {
            return -1;      
         }
         else
         {
            return maxdepthwent;
         } 
      }
      else
      {
         int temp[];
         temp = new int[4];
      
         maxdepthwent++; //?
         
         try
         {
            String NNeighbor = theMap.queryMap(current, "N");
            String ENeighbor = theMap.queryMap(current, "E");
            String SNeighbor = theMap.queryMap(current, "S");
            String WNeighbor = theMap.queryMap(current, "W");

            if (!NNeighbor.equals(NO_NEIGHBOR) && !path_contains(path, NNeighbor))
            {
               path.addElement(new Path_element("N", NNeighbor));
               temp[0]=iterative_deepening(NNeighbor, goal, path, depth-1, maxdepthwent);
               path.removeElement(path.lastElement());
               if (temp[0]==-1)
               {
                  return -1;
               }

            }
          
            if (!ENeighbor.equals(NO_NEIGHBOR) && !path_contains(path, ENeighbor))
            {
               path.addElement(new Path_element("E", ENeighbor));
               temp[1]=iterative_deepening(ENeighbor, goal, path, depth-1, maxdepthwent);
               path.removeElement(path.lastElement());
               if (temp[1]==-1)
               {
                  return -1;
               }
   
            }
   
            if (!SNeighbor.equals(NO_NEIGHBOR) && !path_contains(path, SNeighbor))
            {
               path.addElement(new Path_element("S", SNeighbor));
               temp[2]=iterative_deepening(SNeighbor, goal, path, depth-1, maxdepthwent);
               path.removeElement(path.lastElement());
               if (temp[2]==-1)
               {
                  return -1;
               }
   
            }
            
            if (!WNeighbor.equals(NO_NEIGHBOR) && !path_contains(path, WNeighbor))
            {
               path.addElement(new Path_element("W", WNeighbor));
               temp[3]=iterative_deepening(WNeighbor, goal, path, depth-1, maxdepthwent);
               path.removeElement(path.lastElement());
               if (temp[3]==-1)
               {
                  return -1;
               }
            }
      
         }
         catch (MapException e)
         {
            System.out.println(e);
         }
         
         

         int i;
      
         maxdepthwent = temp[0];
         for (i=1; i<4; i++)
         {
            if (temp[i]>maxdepthwent)
            {
               maxdepthwent = temp[i];
            }
         }
     
      }
      
      return maxdepthwent;
               
   }
   
  /**
   * A helper method.  Returns true if the Vector path contains an
   * element with the String cityName.  Returns false otherwise.
   */
   
   public static boolean path_contains(Vector path, String cityName)
   {
      int i;
      int vsize;

      if (path != null)
      {
         vsize = path.size();
      }
      else
      {
         vsize = 0;
      }
      
      Path_element temp;

        
      for (i=0; i<vsize; i++)
      {
         temp = (Path_element) path.elementAt(i);
         if (temp.getCityInThatDirection().equals(cityName))
         {
            return true;  //already in path
         }
      }
      
      return false;  //not in path   
   }
   
  /**
   * This method implements the original algorithm for stage 2.
   * 
   * Filled in by the student.  See assignment document.
   * Stage #2 method
   */
   public static Vector path_validation(String start, String goal)
   {
      Vector path;
      Vector retPath = null;
      
      int startIndex = theMap.getIndexofCity(start);
      int goalIndex = theMap.getIndexofCity(goal);
      
      path = table[startIndex][goalIndex];
      
      if (path.size() != 0)
      {
         Vector updatedPath = new Vector();
         check_path(path, updatedPath, start, start, goal);
         retPath = table[startIndex][goalIndex];  //path now checked and updated
      }
      else
      {
         //have to resort to plain search (no path stored)
         retPath = simple_expansion(start, goal);   
         
      }

      return retPath;

   }

  /**
   * This method is a recursive function that validates a path.
   */ 
   
   
   public static boolean check_path(Vector pathtoCheck, Vector updatedPath, String current, String start, String goal)
   {
      int startIndex = theMap.getIndexofCity(start);
      int currentIndex = theMap.getIndexofCity(current);
      int goalIndex = theMap.getIndexofCity(goal);
      
      if (current.equals(goal))
      {
         table[startIndex][goalIndex] = (Vector) updatedPath.clone(); 
         return true;
      }
      
      boolean foundCity = false;
      boolean expected = false;
                                    
      String nextCityShouldBe;
      String nextCityIs;
      String direction;
      Path_element next = (Path_element) pathtoCheck.firstElement();
      
      direction = next.getDirection();
      nextCityShouldBe = next.getCityInThatDirection();
      
      try{
         nextCityIs = theMap.queryMap(current, direction);
         
         if (nextCityShouldBe.equals(nextCityIs))
         {
            expected = true;
            Vector pathCopy = (Vector) pathtoCheck.clone();
            pathCopy.removeElementAt(0);
            updatedPath.addElement(next);
            foundCity = check_path(pathCopy, updatedPath, nextCityIs, start, goal);       
            updatedPath.removeElement(updatedPath.lastElement());
         }
         else
         {
            //we've discovered an invalid path, so we will clear it
            table[currentIndex][goalIndex] = new Vector();
                                                           
         }
         
         if (!foundCity)
         {
           
            int index;
            Vector possiblePath;
            String NNeighbor = theMap.queryMap(current, "N");
            String ENeighbor = theMap.queryMap(current, "E");
            String SNeighbor = theMap.queryMap(current, "S");
            String WNeighbor = theMap.queryMap(current, "W");

            if (!NNeighbor.equals(NO_NEIGHBOR) && !path_contains(updatedPath, NNeighbor))
            {
               if (!NNeighbor.equals(nextCityShouldBe) || !expected)
               {
                  index = theMap.getIndexofCity(NNeighbor);
                  possiblePath = table[index][goalIndex];
                  if (possiblePath.size() != 0)
                  {
                     updatedPath.addElement(new Path_element("N", NNeighbor));
                     foundCity=check_path(possiblePath, updatedPath, NNeighbor, start, goal);
                     updatedPath.removeElement(updatedPath.lastElement());
                  }
                     
               }

            }
          
            if (!foundCity && !ENeighbor.equals(NO_NEIGHBOR) && !path_contains(updatedPath, ENeighbor))
            {
               if (!ENeighbor.equals(nextCityShouldBe) || !expected)
               {
                  index = theMap.getIndexofCity(ENeighbor);
                  possiblePath = table[index][goalIndex];
                  if (possiblePath.size() != 0)
                  {
                     updatedPath.addElement(new Path_element("E", ENeighbor));
                     foundCity=check_path(possiblePath, updatedPath, ENeighbor, start, goal);
                     updatedPath.removeElement(updatedPath.lastElement());
                  }

               }

   
            }
   
            if (!foundCity && !SNeighbor.equals(NO_NEIGHBOR) && !path_contains(updatedPath, SNeighbor))
            {
               if (!SNeighbor.equals(nextCityShouldBe) || !expected)
               {
                  index = theMap.getIndexofCity(SNeighbor);
                  possiblePath = table[index][goalIndex];
                  if (possiblePath.size() != 0)
                  {
                     updatedPath.addElement(new Path_element("S", SNeighbor));
                     foundCity=check_path(possiblePath, updatedPath, SNeighbor, start, goal);
                     updatedPath.removeElement(updatedPath.lastElement());
                  }

               }

 
            }
            
            if (!foundCity && !WNeighbor.equals(NO_NEIGHBOR) && !path_contains(updatedPath, WNeighbor))
            {
               if (!WNeighbor.equals(nextCityShouldBe) || !expected)
               {
                  index = theMap.getIndexofCity(WNeighbor);
                  possiblePath = table[index][goalIndex];
                  if (possiblePath.size() != 0)
                  {
                     updatedPath.addElement(new Path_element("W", WNeighbor));
                     foundCity=check_path(possiblePath, updatedPath, WNeighbor, start, goal);
                     updatedPath.removeElement(updatedPath.lastElement());
                  }
  
               }

            }
            
            if (!foundCity)
            {
               possiblePath = simple_expansion(current, goal);
               if (!path_contains(possiblePath, "NO PATH"))
               {
                  int i;
                  int vsize = possiblePath.size();

                  Path_element temp;
                  
                  for (i=0; i<vsize; i++)
                  {
                     temp = (Path_element) possiblePath.elementAt(i);
                     updatedPath.addElement(temp);
                  }  
         
                  table[startIndex][goalIndex] = updatedPath;
                  foundCity = true;
               }  
            }
              
         }      
            
        
      }
      catch (MapException e)
      {
         System.out.println(e);
      }
      
      return foundCity;
   } 

  /**
   * Converts a text file to a CityMap object
   *
   */
   public static void mapFromFile(String filename, CityMap theMap)
   {
      StringBuffer buffer = new StringBuffer ();
     
      try
      {
         File inputFile = new File (filename);
         FileInputStream fis = new FileInputStream (inputFile);
        
         int c, j=0;
         while ((c = fis.read()) != -1)
            buffer.append ((char) c);
         fis.close ();
      }
   
      catch (IOException e)
      {
         System.out.println ("Error: " + e);
      }
      
      StringTokenizer sToken = new StringTokenizer(buffer.toString());
      
      CityInfo temp;
      
      while (sToken.hasMoreTokens())
      {
         temp = new CityInfo(sToken.nextToken());
         temp.setNorthNeighbor(sToken.nextToken());
         temp.setEastNeighbor(sToken.nextToken());
         temp.setSouthNeighbor(sToken.nextToken());
         temp.setWestNeighbor(sToken.nextToken());
         
         try
         {
            theMap.insertCity(temp);
         }
         catch (MapException e)
         {
            System.out.println(e);
         }  
         
      }
   }
   
   
  /**
   * Prints the information for a path through the map.  The 
   * vector must contain Path_element objects.
   */
   public static void printPathVector(Vector path, String start, String goal)
   {
      int i;
      int vsize;

      if (path != null)
      {
         vsize = path.size();
      }
      else
      {
         vsize = 0;
      }
      
      Path_element temp;

      System.out.println("Start: "+start);
      
      for (i=0; i<vsize; i++)
      {
         temp = (Path_element) path.elementAt(i);
         System.out.println(temp);
      }

      System.out.println("Goal: "+goal);
      System.out.println();
   }
}