/*
 * BSD License
 *
 * Copyright (c) 2007, The University of Manchester (UK)
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *     - Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     - Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *     - Neither the name of the University of Manchester nor the names
 *       of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written
 *       permission.

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * Simple Transactional Lee's Routing Algorithm
 * See LeeTM description at http://dx.doi.org/10.1109/PACT.2007.4336228
 *
 * @author Ian Watson (watson@cs.manchester.ac.uk)
 * @author Chris Kirham (chris@cs.manchester.ac.uk)
 * @author Mikel Lujan (mikel@cs.manchester.ac.uk)
 * @version 1.0, 3/Oct/2007
 */

import java.io.*;
import java.util.*;

public class Lee_TM {
   final static int cyan = 0x00FFFF;
   final static int magenta = 0xFF00FF;
   final static int yellow = 0xFFFF00;
   final static int green = 0x00FF00;
   final static int red = 0xFF0000;
   final static int blue = 0x0000FF;
   final static int GRID_SIZE = 600;
   final static int EMPTY = 0;
   final static int TEMP_EMPTY = 10000;
   final static int OCC = 6000;
   final static int VIA = 7000;
   final static int BVIA = 7001;
   final static int ROUTE = 16384;
   final static int GOAL = 2048;
   final static int MAX_WEIGHT = 1;
   private static int printDest = 0; // 1 for file, 0 for screen.
   final static int dx[][] = {{-1, 1, 0, 0},{ 0, 0,-1, 1}};      // dx NSEW array
   final static int dy[][] = {{ 0, 0,-1, 1},{-1, 1, 0, 0}};       // dy NSEW array

   static Viewer view = null ; // new Viewer(); - removed from Lee
   static int failures = 0;
   static int num_vias = 0;
   static int forced_vias = 0;

   static int numLocalVias, numLocalForcedVias ; // added to Lee
   static int transFails, transComms ; // added to Lee

   static BufferedReader inputFile;
   static String input_line;
   static int linepos = 0;

    private static void nextLine() throws IOException {
	input_line = inputFile.readLine();
	linepos = 0;
    }

   private static char readChar() {
       while ((input_line.charAt(linepos) == ' ')&&(input_line.charAt(linepos) == '\t'))
	   linepos++;
       char c = input_line.charAt(linepos);
       if (linepos < input_line.length()-1) linepos++;
       return c;
   }

   private static int readInt() {
       while ((input_line.charAt(linepos) == ' ')||(input_line.charAt(linepos) == '\t'))
	   linepos++;
       int fpos = linepos;
       while ((linepos < input_line.length())&&(input_line.charAt(linepos) != ' ')
	      &&(input_line.charAt(linepos) != '\t')) linepos++;
       int n = Integer.parseInt(input_line.substring(fpos,linepos));
       return n;
   }

   public static void main(String[] args)
   {    
      if (args.length < 2)
      {
         System.out.println("Error parameters: wrong number of parameters");
         System.out.println("Usage: java Lee_TM fileName batchSize");
	 System.out.println("Usage example: java Lee_TM mainboard.txt 100\n\n");
	 System.exit(1);
      }
      int [][][] g = new int [2][GRID_SIZE][GRID_SIZE];            // the Lee 2D Grid
      String fileName = args[0];
      int maxPerIteration = -1;
      try
      {
         maxPerIteration = (new Integer(args[1])).intValue() ; // added to Lee
      }
      catch(NumberFormatException exception)
      {
         System.out.println("Error: parameter batchSize must be an integer");
         System.out.println("       cannot convert " + args[1] + " to an integer");
         System.out.println("Usage: java Lee_TM fileName batchSize");
	 System.out.println("Usage example: java Lee_TM mainboard.txt 100\n\n");
	 System.exit(1);
      }
      if (maxPerIteration <= 0) maxPerIteration = Integer.MAX_VALUE ; // added to Lee
      int netNo = 0;
      emptyGrid(g);
      WorkQueue work = new WorkQueue(); // empty
      // Read description
      try
      {

	 inputFile = new BufferedReader (new InputStreamReader(new FileInputStream(args[0])));
         while (true)
         {
	    nextLine();
            char c = readChar();
            if (c=='E') break;            // end of file
            if (c=='C')                   // chip bounding box
            {
               int x0 = readInt();
               int y0 = readInt();
               int x1 = readInt();
               int y1 = readInt();
               occupy(x0, y0, x1, y1, g);
            }
            if (c=='P')                   // pad
            {
               int x0 = readInt();
               int y0 = readInt();
               occupy(x0, y0, x0, y0, g);
            }
            if (c=='J')                   // join connection pts
            {
               int x0 = readInt();
               int y0 = readInt();
               int x1 = readInt();
               int y1 = readInt();
               netNo++;
               work.next = work.enQueue(x0, y0, x1, y1, netNo);
            }
          }
      }
       catch (FileNotFoundException exception)
       {
          System.out.println("Cannot open file: " + fileName);
          System.exit(1);
       }
       catch (IOException exception)
       {
         System.out.println(exception);
	 exception.printStackTrace();
       }
       addweights(g);

       int transLoop = 1 ; // added to Lee
       int totalWork = 0 ; // added to Lee
       int [][][] initg = new int [2][GRID_SIZE][GRID_SIZE] ; // added to Lee
       do { // added to Lee
           System.out.println("In transaction iteration " + transLoop) ; // added to Lee
           transFails = 0 ;  transComms = 0 ; // added to Lee
           transLoop++ ; // added to Lee
           work.sort();
           // System.out.println("Starting to Route"); - monitoring removed
           WorkQueue newWork = new WorkQueue(); // empty - added to Lee
           HashSet modsMade = new HashSet() ; // added to Lee
           for (int i = 0 ; i < GRID_SIZE ; i++)  // added to Lee
              for (int j = 0; j < GRID_SIZE ; j++) // added to Lee
                { initg[0][i][j] = g[0][i][j] ; // added to Lee
                  initg[1][i][j] = g[1][i][j] ; // added to Lee
                } // added to Lee
           for (int count = maxPerIteration ; work.next != null && count > 0 ; count--) { // modified from Lee
  	        WorkQueue q = work.deQueue();
	        // start transaction
                totalWork++ ; // added to Lee
                numLocalVias = 0 ; numLocalForcedVias = 0 ;
	        if (!connect(q.x1, q.y1 , q.x2, q.y2, q.nn, initg, modsMade, g)) // modified from Lee
                      newWork.next = newWork.enQueue(q.x1, q.y1, q.x2, q.y2, q.nn) ; // added to Lee
	       // end transaction
           }
           while (work.next != null) { // copy unattempted work to new queue - added to Lee
              WorkQueue fred = work.deQueue();
              newWork.next = newWork.enQueue(fred.x1, fred.y1, fred.x2, fred.y2, fred.nn);
              }

           work=newWork ;
           System.out.println("Commits: " + transComms + " successful; " + transFails + " failed") ;
       } while (work.next != null) ;

       // dispGrid(g,0); removed from Lee
       // dispGrid(g,1); removed from Lee
       System.out.println("Total Routes "+netNo+" Failures "+failures+" Vias "+num_vias+
			  " Forced Vias "+forced_vias);
       System.out.println("Total number of connection attempts made: " + totalWork) ;
       // view.display(); removed from Lee
    }

    public static void addweights(int [][][] g)
    {      
	// this attempts to keep routes away from pins
       for (int i=0; i< MAX_WEIGHT;i++) {
         for (int z = 0; z< 2; z++)	   
	   for (int x=1; x<GRID_SIZE-1; x++)
	       {
		   for (int y=1; y<GRID_SIZE-1; y++)
		       {
			   if (g[z][x][y] == OCC) {
			       if (g[z][x][y+1] == EMPTY) g[z][x][y+1] = MAX_WEIGHT;
			       if (g[z][x+1][y] == EMPTY) g[z][x+1][y] = MAX_WEIGHT;
			       if (g[z][x][y-1] == EMPTY) g[z][x][y-1] = MAX_WEIGHT;
			       if (g[z][x-1][y] == EMPTY) g[z][x-1][y] = MAX_WEIGHT;
			   }
			   else if (g[z][x][y] != EMPTY) {
			       if (g[z][x][y+1] == EMPTY) g[z][x][y+1] = g[z][x][y] - 1;
			       if (g[z][x+1][y] == EMPTY) g[z][x+1][y] = g[z][x][y] - 1;
			       if (g[z][x][y-1] == EMPTY) g[z][x][y-1] = g[z][x][y] - 1;
			       if (g[z][x-1][y] == EMPTY) g[z][x-1][y] = g[z][x][y] - 1;
			   }
		       }
	       } 
       }
    }

    public static void emptyGrid(int [][][] g)
    {      
       for (int x=0; x<GRID_SIZE; x++)
       {
          for (int y=0; y<GRID_SIZE; y++)
          {
              g[0][x][y] = EMPTY; // initialises the whole grid to be empty
              g[1][x][y] = EMPTY; // initialises the whole grid to be empty
          }
       } 
    }

    public static void occupy(int loX, int loY, int upX, int upY, int [][][] g)
    {
        int x=0; int y=0;
        for (x=loX; x<=upX; x++) {
            for (y=loY; y<=upY; y++) {
		g[0][x][y] = OCC; // occupies the given bounding box with the occupied tag
		g[1][x][y] = OCC; // occupies the given bounding box with the occupied tag
            }
        }
       
    }

    public static boolean ok(int x, int y)
    {
       return (x>0 && x<GRID_SIZE-1 && y>0 && y <GRID_SIZE-1); // checks that point is actually within the bounds of grid array
    }


    public static boolean expandFromTo(int x, int y, int xGoal, int yGoal, int num, int tempg [][][], int [][][] g,
                                             Vector readList, Hashtable writeList)  // last two parameters added!
    {
       // this method expands from (x,y) to (xGoal, yGoal)
       // it returns true if the goal is found otherwise false
	// System.out.println("Expanding "+x+" "+y+" "+xGoal+" "+yGoal); - monitoring removed
	Frontier_List front = new Frontier_List();
	Frontier_List tmp_front = new Frontier_List();
	tempg[0][x][y]=1; // set grid (x,y) as 1
	tempg[1][x][y]=1; // set grid (x,y) as 1
	boolean trace1 = false;
	front.addElement(x,y,0);
	front.addElement(x,y,1);  // we can start from either side
	int extra_iterations = 50;
	boolean reached0 = false;
	boolean reached1 = false;
        Frontier f = new Frontier();
        int [] ff = new int[3];
	while (!front.isEmpty()){
	      while (!front.isEmpty()){
	        int weight,prev_val;
		ff = front.getElement();
		f.x = ff[0]; f.y = ff[1]; f.z = ff[2];
		if (trace1) System.out.println("X "+f.x+" Y "+f.y+" Z "+f.z+" processing - val "+
		                    tempg[f.z][f.x][f.y]);
		int dir_weight = 1;
		weight = g[f.z][f.x][f.y+1]+1;
		readList.addElement(new Integer((f.x * GRID_SIZE + f.y + 1) << 1 + f.z)) ; // added to Lee
		prev_val = tempg[f.z][f.x][f.y+1];
		boolean reached = (f.x==xGoal)&&(f.y+1==yGoal);
		if ((prev_val > tempg[f.z][f.x][f.y]+weight)&&(weight < OCC)||reached) {
		    if (ok(f.x,f.y+1)){
		         tempg[f.z][f.x][f.y+1]= tempg[f.z][f.x][f.y]+weight; // looking north
                         writeList.put(new Integer(((f.x*GRID_SIZE+f.y+1)<<1) + f.z), new Integer(g[f.z][f.x][f.y+1])) ; // added
		         if (!reached) tmp_front.addElement(f.x,f.y+1,f.z);
                    }
		}
		weight = g[f.z][f.x+1][f.y]+1;
		readList.addElement(new Integer(((f.x +1) * GRID_SIZE + f.y) << 1 + f.z)) ; // added to Lee
		prev_val = tempg[f.z][f.x+1][f.y];
		reached = (f.x+1==xGoal)&&(f.y==yGoal);
		if ((prev_val > tempg[f.z][f.x][f.y]+weight)&&(weight < OCC)||reached) {
		    if (ok(f.x+1,f.y)){
			   tempg[f.z][f.x+1][f.y]= tempg[f.z][f.x][f.y]+weight; // looking east
                           writeList.put(new Integer((((f.x+1)*GRID_SIZE+f.y)<<1) + f.z), new Integer(g[f.z][f.x+1][f.y])) ; //added
			   if (!reached) tmp_front.addElement(f.x+1,f.y,f.z);
                    }
		}
		weight = g[f.z][f.x][f.y-1]+1;
		readList.addElement(new Integer((f.x * GRID_SIZE + f.y - 1) << 1 + f.z)) ; // added to Lee
		prev_val = tempg[f.z][f.x][f.y-1];
		reached = (f.x==xGoal)&&(f.y-1==yGoal);
		if ((prev_val > tempg[f.z][f.x][f.y]+weight)&&(weight < OCC)||reached) {
		    if (ok(f.x,f.y-1)){
			   tempg[f.z][f.x][f.y-1]= tempg[f.z][f.x][f.y]+weight; // looking south
                           writeList.put(new Integer(((f.x*GRID_SIZE+f.y-1)<<1) + f.z), new Integer(g[f.z][f.x][f.y-1])) ; // added
			   if (!reached) tmp_front.addElement(f.x,f.y-1,f.z);
                    }
		}
		weight = g[f.z][f.x-1][f.y]+1;
		readList.addElement(new Integer(((f.x - 1)* GRID_SIZE + f.y) << 1 + f.z)) ; // added to Lee
		prev_val = tempg[f.z][f.x-1][f.y];
		reached = (f.x-1==xGoal)&&(f.y==yGoal);
		if ((prev_val > tempg[f.z][f.x][f.y]+weight)&&(weight < OCC)||reached) {
		    if (ok(f.x-1,f.y)){
			   tempg[f.z][f.x-1][f.y]= tempg[f.z][f.x][f.y]+weight; // looking west
                           writeList.put(new Integer((((f.x-1)*GRID_SIZE+f.y)<<1) + f.z), new Integer(g[f.z][f.x-1][f.y])) ; // added
			   if (!reached) tmp_front.addElement(f.x-1,f.y,f.z);
                    }
		}
		if (f.z == 0){
		    weight = g[1][f.x][f.y]+1;
		    readList.addElement(new Integer((f.x * GRID_SIZE + f.y) << 1 + 1)) ; // added to Lee
		    if ((tempg[1][f.x][f.y] > tempg[0][f.x][f.y])&&(weight < OCC)) {
 			tempg[1][f.x][f.y] = tempg[0][f.x][f.y];
                        writeList.put(new Integer(((f.x*GRID_SIZE+f.y)<<1) + 1), new Integer(g[1][f.x][f.y])) ; // added
			tmp_front.addElement(f.x,f.y,1);
		    }
		}
		else {
		    weight = g[0][f.x][f.y]+1;
		    readList.addElement(new Integer((f.x * GRID_SIZE + f.y) << 1)) ; // added to Lee
		    if ((tempg[0][f.x][f.y] > tempg[1][f.x][f.y])&&(weight < OCC)) {
 			tempg[0][f.x][f.y] = tempg[1][f.x][f.y];
                        writeList.put(new Integer(((f.x*GRID_SIZE+f.y)<<1) + 0), new Integer(g[0][f.x][f.y])) ; // added
			tmp_front.addElement(f.x,f.y,0);
		    }	
		}
						// must check if found goal, if so return TRUE
		reached0 = tempg[0][xGoal][yGoal]!=TEMP_EMPTY;
		reached1 = tempg[1][xGoal][yGoal]!=TEMP_EMPTY;
		if ((reached0 && !reached1) || (!reached0 && reached1)) extra_iterations = 100;
		if ((extra_iterations == 0) && (reached0 || reached1) || (reached0 && reached1)) {
		       return true; // if (xGoal, yGoal) can be found in time
		}
		else extra_iterations--;
	      }
	    Frontier_List tf;
	    tf = front;
	    front = tmp_front;
	    tmp_front = tf;
	}
	return false;
    }

    private static boolean pathFromOtherSide(int[][][] g,int X,int Y,int Z, Vector readList){
// g is the shared array, so all accesses to it need to be recorded.
// This means that this method is completely rewritten to handle the
// complicated boolean expression correctly.
      boolean ok;
      int Zo;
      Zo = 1 - Z; //other side
      int sqval = g[Zo][X][Y];
      readList.addElement(
		new Integer((X * GRID_SIZE + Y) << 1 + Zo)) ;
      if ((sqval == VIA) || (sqval == BVIA)) return false;
      ok = (g[Zo][X][Y] <= g[Z][X][Y]);
      readList.addElement(
		new Integer((X * GRID_SIZE + Y) << 1 + Z)) ;
      if (ok) {
	if (g[Zo][X-1][Y] < sqval) {
          readList.addElement(
		new Integer((X * GRID_SIZE - GRID_SIZE + Y) << 1 + Zo)) ;
	  return true ; }
	if (g[Zo][X+1][Y] < sqval){
          readList.addElement(
		new Integer((X * GRID_SIZE + GRID_SIZE + Y) << 1 + Zo)) ;
	  return true ; }
	if (g[Zo][X][Y-1] < sqval){
          readList.addElement(
		new Integer((X * GRID_SIZE + Y - 1) << 1 + Zo)) ;
	  return true ; }
        if (g[Zo][X][Y+1] < sqval){
          readList.addElement(
		new Integer((X * GRID_SIZE + Y + 1) << 1 + Zo)) ;
          return true; }
        }
      return false;
    }
    
    private static int tlength (int x1,int y1,int x2, int y2){
      int sq = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
      return (int)Math.sqrt((double)sq);
    }

    private static int ratio (int x1,int y1,int x2, int y2){
	int xdiff = x2-x1;
	int ydiff = y2-y1;
	if (xdiff < 0) xdiff = -xdiff;
	if (ydiff < 0) ydiff = -ydiff;
	if (xdiff > ydiff) {
	    if (ydiff == 0) return 100000;
	    else return xdiff/ydiff;
	}
	else {
	    if (xdiff == 0) return 100000;
	    else return ydiff/xdiff;
	}
    }

    private static int deviation (int x1,int y1,int x2, int y2){
	int xdiff = x2-x1;
	int ydiff = y2-y1;
	if (xdiff < 0) xdiff = -xdiff;
	if (ydiff < 0) ydiff = -ydiff;
	if (xdiff < ydiff) return xdiff; else return ydiff;
    }
    
    public static Hashtable backtrackFrom(int xGoal, int yGoal, int xStart, int yStart, int routeNo, int [][][] tempg, // int [][][] g,
                              Hashtable initHt, Vector readList) // removed parameter and added another
    {
      // this method backtracks from the goal position (xGoal, yGoal)
      // to the starting position (xStart, yStart) filling in the
      // grid array g with the specified route number routeNo ( + ROUTE).

      int count = 100;
      // System.out.println("Route "+routeNo+" backtrack "+"Length "+tlength(xStart,yStart,xGoal,yGoal)); monitoring removed
      boolean trace = false;
      int zGoal;
      int distsofar = 0;
      Hashtable writeList = initHt ; // added to Lee
      if (Math.abs(xGoal-xStart) > Math.abs(yGoal-yStart)) zGoal = 0; else zGoal = 1;
      if (tempg[zGoal][xGoal][yGoal] == TEMP_EMPTY) {
	  zGoal = 1-zGoal;
      }
      int tempY = yGoal; int tempX = xGoal; int tempZ = zGoal;
      int lastdir = -10;
      while((tempX != xStart) || (tempY != yStart)) { // PDL: until back at starting point
	  boolean advanced = false;
	  int mind = 0;
	  int dir = 0;
	  int min_square = 100000;
	  int d;
	  for(d = 0; d < 4;d++){  // PDL: Find dir to start back from current position
	      if ((tempg[tempZ][tempX+dx[tempZ][d]][tempY+dy[tempZ][d]] < tempg[tempZ][tempX][tempY])
                                     && (tempg[tempZ][tempX+dx[tempZ][d]][tempY+dy[tempZ][d]] != TEMP_EMPTY)) {
		  if (tempg[tempZ][tempX+dx[tempZ][d]][tempY+dy[tempZ][d]] < min_square){
		      min_square = tempg[tempZ][tempX+dx[tempZ][d]][tempY+dy[tempZ][d]];
		      mind = d;
		      dir = dx[tempZ][d] * 2 + dy[tempZ][d]; //hashed dir
		      if (lastdir < -2) lastdir = dir;
		      advanced = true; 
		  }
	      }
	  }
	  if (advanced) distsofar++;
	  if (pathFromOtherSide(tempg,tempX,tempY,tempZ,readList)&&
	      (
	       (mind > 1) &&    // not preferred dir for this layer
	       (distsofar > 15) &&
	       (tlength(tempX,tempY,xStart,yStart) > 15) ||
	       (!advanced && ((tempg[tempZ][tempX][tempY] != VIA)&&(tempg[tempZ][tempX][tempY] != BVIA)))
              )
             ){
	      int tZ = 1 - tempZ; // 0 if 1, 1 if 0
	      int viat;
	      if (advanced) viat = VIA; else viat = BVIA; // BVIA is nowhere else to go
	      // g[tempZ][tempX][tempY] = - removed ....
              tempg[tempZ][tempX][tempY] = viat; // mark via
              writeList.put(new Integer(((tempX*GRID_SIZE+tempY)<<1) + tempZ), new Integer(viat)) ; // added to Lee
	      tempZ = tZ;
	      // g[tempZ][tempX][tempY] = - removed ....
              tempg[tempZ][tempX][tempY] = viat; // and the other side
              writeList.put(new Integer(((tempX*GRID_SIZE+tempY)<<1) + tempZ), new Integer(viat)) ; // added to Lee
	      numLocalVias++; // change
	      if (!advanced) numLocalForcedVias++; // change
	      distsofar = 0;
	  }
	  else {
	      if (tempg[tempZ][tempX][tempY] < OCC) // g[tempZ][tempX][tempY] = ROUTE; // PDL: fill in route unless connection point
                 { tempg[tempZ][tempX][tempY] = ROUTE ; // added
                   writeList.put(new Integer(((tempX*GRID_SIZE+tempY)<<1) + tempZ), new Integer(ROUTE)) ; }  // added
	      tempX = tempX+dx[tempZ][mind]; // PDL: updating current position on x axis
	      tempY = tempY+dy[tempZ][mind]; // PDL: updating current position on y axis
      	  }
      	  lastdir = dir;
      }
      //      System.out.println("Route "+routeNo+" completed");
      return writeList ; // added
    }

    public static boolean connect(int xs, int ys, int xg, int yg, int netNo, int [][][] g,
                    HashSet mods, int [][][] updateG) // added parameters
    {
	// System.out.println("In Connect"); monitoring removed
        // calls expandFrom and backtrackFrom to create connection
        int [][][] tempg = new int [2][GRID_SIZE][GRID_SIZE];            // Lee 2D Grid copy
	// This is the only real change needed to make the program transactional.
	// Instead of using the grid 'in place' to do the expansion, we take a copy
	// but the backtrack writes to the original grid.
	// This is not a correctness issue. The transactions would still complete eventually without it.
	// However the expansion writes are only temporary and do not logically conflict.
	// There is a question as to whether a copy is really necessary as a transaction will anyway create
	// its own copy. if we were then to distinguish between writes not to be committed (expansion) and
	// those to be committed (backtrack), we would not need an explicit copy.
	// Taking the copy is not really a computational(time) overhead because it avoids the grid 'reset' phase
	// needed if we do the expansion in place.
	for (int x=0; x<GRID_SIZE; x++) {
	    for (int y=0; y<GRID_SIZE; y++) {
		for (int z = 0; z<2; z++) tempg[z][x][y] = TEMP_EMPTY;
	    }
	}
        Vector readList = new Vector() ; // added
        Hashtable writeList = new Hashtable() ; // added
	boolean found = expandFromTo(xs, ys, xg, yg, GRID_SIZE*5, tempg, g,
                     readList, writeList); // call the expansion method to return found/not found boolean
        if (found)
        {
	    Hashtable writeTab = backtrackFrom(xg, yg, xs, ys, netNo, tempg, writeList, readList); // call the backtrack method - modified
            boolean tempb = commit(mods, readList, writeTab, updateG) ;
            if (tempb) // System.out.println(" succeeded in commiting") ;
                { transComms++ ; 
                  num_vias += numLocalVias ;
                  forced_vias += numLocalForcedVias ;
                }
            else // System.out.println(" failed to commit") ;
                transFails++ ;
            return tempb ;
	} // print outcome of expansion method
        else  {
           System.out.println("Failed to route "+xs+" "+ys+" to "+xg+"  "+yg);
           failures++;
           return true ;
        }
    }

    public static void dispGrid(int [][][] g, int z)
    {
       int laycol;
       if (z==0) laycol = magenta; else laycol=green;
       for (int y = GRID_SIZE-1; y>=0; y--)
       {
          for (int x = 0; x<GRID_SIZE; x++)
          {
             int cell = g[z][x][y];
	     if (cell==OCC) { view.point(x,y,cyan); continue; }
             if (cell==VIA) { view.point(x,y,yellow); continue; }
             if (cell==BVIA) { view.point(x,y,red); continue; }
	     if (cell == ROUTE) {view.point(x,y,laycol); continue; } //
	  }  
       }
    }

    public static boolean commit(HashSet mods, Vector reads, Hashtable writes, int [][][] g) {
      for (Enumeration en = reads.elements() ; en.hasMoreElements() ;)
          if (mods.contains(en.nextElement())) return false ;
      for (Enumeration en = writes.keys() ; en.hasMoreElements() ;)
         { Integer pos = (Integer) en.nextElement() ;
           mods.add(pos) ; int value = ((Integer)writes.get(pos)).intValue() ;
           int codedPos = pos.intValue() ;
           int zpos = codedPos & 1 ; codedPos >>= 1 ;
           g[zpos][codedPos/GRID_SIZE][codedPos%GRID_SIZE]=value ;
         }
      return true ;
    }

}