Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Router.java

   1 /* =============================================================================
   2  *
   3  * Router.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * Ported to Java
  11  * Author: Jihoon Lee
  12  * University of California, Irvine
  13  *
  14  * =============================================================================
  15  *
  16  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  17  * of the files.
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of ssca2, please see ssca2/COPYRIGHT
  26  *
  27  * ------------------------------------------------------------------------
  28  *
  29  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  30  * header of the files.
  31  *
  32  * ------------------------------------------------------------------------
  33  *
  34  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  35  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  36  *
  37  * ------------------------------------------------------------------------
  38  *
  39  * Unless otherwise noted, the following license applies to STAMP files:
  40  *
  41  * Copyright (c) 2007, Stanford University
  42  * All rights reserved.
  43  *
  44  * Redistribution and use in source and binary forms, with or without
  45  * modification, are permitted provided that the following conditions are
  46  * met:
  47  *
  48  *     * Redistributions of source code must retain the above copyright
  49  *       notice, this list of conditions and the following disclaimer.
  50  *
  51  *     * Redistributions in binary form must reproduce the above copyright
  52  *       notice, this list of conditions and the following disclaimer in
  53  *       the documentation and/or other materials provided with the
  54  *       distribution.
  55  *
  56  *     * Neither the name of Stanford University nor the names of its
  57  *       contributors may be used to endorse or promote products derived
  58  *       from this software without specific prior written permission.
  59  *
  60  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  61  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  62  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  63  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  64  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  65  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  66  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  67  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  68  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  69  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  70  * THE POSSIBILITY OF SUCH DAMAGE.
  71  *
  72  * =============================================================================
  73  */
  74
  75 //#define MOMENTUM_ZERO 0
  76 //#define MOMENTUM_POSX 1
  77 //#define MOMENTUM_POSY 2
  78 //#define MOMENTUM_POSZ 3
  79 //#define MOMENTUM_NEGX 4
  80 //#define MOMENTUM_NEGY 5
  81 //#define MOMENTUM_NEGZ 6
  82 //#define GRID_POINT_FULL -2
  83 //#define GRID_POINT_EMPTY -1
  84
  85 public class Router {
  86         private static int  MOMENTUM_ZERO;
  87         private static int  MOMENTUM_POSX;
  88         private static int  MOMENTUM_POSY;
  89         private static int  MOMENTUM_POSZ;
  90         private static int  MOMENTUM_NEGX;
  91         private static int  MOMENTUM_NEGY;
  92         private static int  MOMENTUM_NEGZ;
  93         private static int  GRID_POINT_FULL;
  94         private static int  GRID_POINT_EMPTY;
  95
  96
  97     public int xCost;
  98     public int yCost;
  99     public int zCost;
 100     public int bendCost;
 101     public static Point MOVE_POSX;
 102     public static Point MOVE_POSY;
 103     public static Point MOVE_POSZ;
 104     public static Point MOVE_NEGX;
 105     public static Point MOVE_NEGY;
 106     public static Point MOVE_NEGZ;
 107
 108     public Router()
 109     {
 110         //Replaced #defines
 111         MOMENTUM_ZERO = 0;
 112         MOMENTUM_POSX = 1;
 113         MOMENTUM_POSY = 2;
 114         MOMENTUM_POSZ = 3;
 115         MOMENTUM_NEGX = 4;
 116         MOMENTUM_NEGY = 5;
 117         MOMENTUM_NEGZ = 6;
 118         GRID_POINT_FULL = -2;
 119         GRID_POINT_EMPTY = -1;
 120
 121     }
 122
 123 /* =============================================================================
 124  * router_alloc
 125  * =============================================================================
 126  * router_t* router_alloc (long xCost, long yCost, long zCost, long bendCost);
 127  */
 128     public static Router alloc(int xCost,int yCost,int zCost,int bendCost)
 129     {
 130         Router routerPtr = new Router();
 131
 132         //added lines of code to account for the #defines
 133         routerPtr.MOVE_POSX = new Point(1,0,0,0, routerPtr.MOMENTUM_POSX);
 134         routerPtr.MOVE_POSY = new Point(0,1,0,0, routerPtr.MOMENTUM_POSY);
 135         routerPtr.MOVE_POSZ = new Point(0,0,1,0, routerPtr.MOMENTUM_POSZ);
 136         routerPtr.MOVE_NEGX = new Point(-1,0,0,0, routerPtr.MOMENTUM_NEGX);
 137         routerPtr.MOVE_NEGY = new Point(0,-1,0,0, routerPtr.MOMENTUM_NEGY);
 138         routerPtr.MOVE_NEGZ = new Point(0,0,-1,0, routerPtr.MOMENTUM_NEGZ);
 139
 140         if(routerPtr != null) {
 141             routerPtr.xCost = xCost;
 142             routerPtr.yCost = yCost;
 143             routerPtr.zCost = zCost;
 144             routerPtr.bendCost = bendCost;
 145         }
 146
 147         return routerPtr;
 148     }
 149
 150
 151
 152
 153 /* =============================================================================
 154  * router_free
 155  * =============================================================================
 156  * void router_free (router_t* routerPtr);
 157  */
 158     public static void free(Router routerPtr)
 159     {
 160         routerPtr = null;
 161     }
 162
 163 /* ============================================================================
 164  * PexpandToneighbor
 165  * ============================================================================
 166  */
 167     private void PexpandToNeighbor(Grid myGridPtr,
 168                                     int x,int y,int z, int value,Queue_Int queuePtr)
 169     {
 170         if (myGridPtr.isPointValid(x,y,z)) {
 171             int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z);
 172             int neighborValue = myGridPtr.points_unaligned[neighborGridPointIndex][0];
 173             if (neighborValue == GRID_POINT_EMPTY) {
 174                 myGridPtr.points_unaligned[neighborGridPointIndex][0] = value;
 175                 queuePtr.queue_push(neighborGridPointIndex);
 176             } else if (neighborValue != GRID_POINT_FULL) {
 177
 178                 if (value < neighborValue) {
 179                     myGridPtr.points_unaligned[neighborGridPointIndex][0] = value;
 180                     queuePtr.queue_push(neighborGridPointIndex);
 181                 }
 182             }
 183         }
 184     }
 185
 186
 187 /* ============================================================================
 188  * PdoExpansion
 189  * ============================================================================
 190  */
 191     //will not write to Router ptr
 192     public boolean PdoExpansion (Router routerPtr,Grid myGridPtr,Queue_Int queuePtr,
 193                                   Coordinate srcPtr,Coordinate dstPtr)
 194     {
 195         int xCost = routerPtr.xCost;
 196         int yCost = routerPtr.yCost;
 197         int zCost = routerPtr.zCost;
 198
 199         /*
 200          * Potential Optimization: Make 'src' the one closet to edge.
 201          * This will likely decrease the area of the emitted wave.
 202          */
 203
 204         queuePtr.queue_clear();
 205
 206         int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x,srcPtr.y,srcPtr.z);
 207
 208         queuePtr.queue_push(srcGridPointIndex);
 209  //       System.out.println("dstPtr :\tx = " + dstPtr.x + "\ty = " + dstPtr.y + "\tz = " + dstPtr.z);
 210         myGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 211         myGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,GRID_POINT_EMPTY);
 212         int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x,dstPtr.y,dstPtr.z);
 213         boolean isPathFound = false;
 214         int[] x = new int[1];
 215         int[] y = new int[1];
 216         int[] z = new int[1];
 217
 218         while (!queuePtr.queue_isEmpty()) {
 219             int gridPointIndex = queuePtr.queue_pop();
 220
 221 //            System.out.println("gridPointIndex = " +gridPointIndex);
 222             if(gridPointIndex == dstGridPointIndex) {
 223                 isPathFound = true;
 224                 break;
 225             }
 226
 227             myGridPtr.getPointIndices(gridPointIndex,x,y,z);
 228             int value = myGridPtr.points_unaligned[gridPointIndex][0];
 229
 230             /*
 231              * Check 6 neighbors
 232              *
 233              * Potential Optimization: Only need to check 5 of these
 234              */
 235           PexpandToNeighbor(myGridPtr, x[0]+1, y[0],   z[0],   (value + xCost), queuePtr);
 236           PexpandToNeighbor(myGridPtr, x[0]-1, y[0],   z[0],   (value + xCost), queuePtr);
 237           PexpandToNeighbor(myGridPtr, x[0], y[0]+1,   z[0],   (value + yCost), queuePtr);
 238           PexpandToNeighbor(myGridPtr, x[0], y[0]-1,   z[0],   (value + yCost), queuePtr);
 239           PexpandToNeighbor(myGridPtr, x[0], y[0],   z[0]+1,   (value + zCost), queuePtr);
 240           PexpandToNeighbor(myGridPtr, x[0], y[0],   z[0]-1,   (value + zCost), queuePtr);
 241
 242         } /* iterate over work queue */
 243
 244         return isPathFound;
 245     }
 246
 247
 248 /* ============================================================================
 249  * traceToNeighbor
 250  * ============================================================================
 251  */
 252     private void traceToNeighbor(Grid myGridPtr,
 253                                  Point currPtr,
 254                                  Point movePtr,
 255                                  boolean useMomentum,
 256                                  int bendCost,
 257                                  Point nextPtr)
 258     {
 259         int x = currPtr.x + movePtr.x;
 260         int y = currPtr.y + movePtr.y;
 261         int z = currPtr.z + movePtr.z;
 262
 263         if (myGridPtr.isPointValid(x,y,z) &&
 264                 !myGridPtr.isPointEmpty(x,y,z) &&
 265                 !myGridPtr.isPointFull(x,y,z))
 266         {
 267             int value = myGridPtr.getPoint(x,y,z);
 268             int b = 0;
 269
 270             if (useMomentum && (currPtr.momentum != movePtr.momentum)) {
 271                 b = bendCost;
 272             }
 273             if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */
 274                 nextPtr.x = x;
 275                 nextPtr.y = y;
 276                 nextPtr.z = z;
 277                 nextPtr.value = value;
 278                 nextPtr.momentum = movePtr.momentum;
 279             }
 280         }
 281     }
 282 /* =============================================================================
 283  * PdoTraceback
 284  * =============================================================================
 285  */
 286
 287     //will not modify global variables
 288     private Vector_t PdoTraceback(Grid gridPtr,Grid myGridPtr,
 289                                   Coordinate dstPtr, int bendCost)
 290     {
 291         Vector_t vector_t = new Vector_t();
 292         Vector_t pointVectorPtr = vector_t.vector_alloc(1);
 293
 294         Point next = new Point();
 295         next.x = dstPtr.x;
 296         next.y = dstPtr.y;
 297         next.z = dstPtr.z;
 298         next.value = myGridPtr.getPoint(next.x,next.y,next.z);
 299         next.momentum = MOMENTUM_ZERO;
 300
 301         while(true) {
 302             int gridPointIndex = gridPtr.getPointIndex(next.x,next.y,next.z);
 303             pointVectorPtr.vector_pushBack(new Integer(gridPointIndex));
 304             myGridPtr.setPoint(next.x,next.y,next.z,GRID_POINT_FULL);
 305
 306             /* Check if we are done */
 307             if (next.value == 0) {
 308                 break;
 309             }
 310             Point curr = new Point();
 311             curr.x = next.x;
 312             curr.y = next.y;
 313             curr.z = next.z;
 314             curr.value = next.value;
 315             curr.momentum = next.momentum;
 316
 317             /*
 318              * Check 6 neibors
 319              */
 320
 321             traceToNeighbor(myGridPtr,curr,MOVE_POSX,true, bendCost, next);
 322             traceToNeighbor(myGridPtr,curr,MOVE_POSY,true, bendCost, next);
 323             traceToNeighbor(myGridPtr,curr,MOVE_POSZ,true, bendCost, next);
 324             traceToNeighbor(myGridPtr,curr,MOVE_NEGX,true, bendCost, next);
 325             traceToNeighbor(myGridPtr,curr,MOVE_NEGY,true, bendCost, next);
 326             traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,true, bendCost, next);
 327
 328             /*
 329              * Because of bend costs, none of the neighbors may appear to be closer.
 330              * In this case, pick a neighbor while ignoring momentum.
 331              */
 332
 333 //            System.out.println("next x = " + next.x + " y = " + next.y + " z = " + next.z);
 334
 335             if ((curr.x == next.y) &&
 336                 (curr.y == next.y) &&
 337                 (curr.z == next.z))
 338             {
 339                 next.value = curr.value;
 340                 traceToNeighbor(myGridPtr,curr,MOVE_POSX,false, bendCost, next);
 341                 traceToNeighbor(myGridPtr,curr,MOVE_POSY,false, bendCost, next);
 342                 traceToNeighbor(myGridPtr,curr,MOVE_POSZ,false, bendCost, next);
 343                 traceToNeighbor(myGridPtr,curr,MOVE_NEGX,false, bendCost, next);
 344                 traceToNeighbor(myGridPtr,curr,MOVE_NEGY,false, bendCost, next);
 345                 traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,false, bendCost, next);
 346
 347                 if ((curr.x == next.x) &&
 348                     (curr.y == next.y) &&
 349                     (curr.z == next.z))
 350                 {
 351                     pointVectorPtr.vector_free();
 352                     System.out.println("Dead");
 353                     return null;
 354                 }
 355             }
 356         }
 357
 358         return pointVectorPtr;
 359     }
 360
 361 /* =============================================================================
 362  * router_solve
 363  * =============================================================================
 364  * void router_solve (void* argPtr);
 365  */
 366     public static void solve(Object argPtr) {
 367         Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
 368
 369         //dummy labyrinth object so we can use the global variable later
 370         Labyrinth labyrinth = new Labyrinth();
 371
 372         //this is where all the paths will be stored
 373         List_t GlobalPathVectorPtr = routerArgPtr.pathVectorListPtr;
 374
 375         Router routerPtr = routerArgPtr.routerPtr;
 376         Maze mazePtr = routerArgPtr.mazePtr;
 377         Queue_t masterWorkQueue = mazePtr.workQueuePtr;
 378         Grid masterGrid = mazePtr.gridPtr;
 379
 380         //used in identification of solved paths (unique)
 381         int id = 0;
 382
 383         while(!masterWorkQueue.queue_isEmpty())
 384         {
 385                 //This will ensure that we'll always have space for the worst case and
 386                 //reduce overhead from array expansions
 387                 Queue_t redoQueue = masterWorkQueue.Pqueue_alloc(masterWorkQueue.capacity);
 388
 389                 Grid MGClone = masterGrid.alloc(masterGrid.width, masterGrid.height, masterGrid.depth);
 390                 masterGrid.copy(MGClone, masterGrid);
 391
 392                 while(!masterWorkQueue.queue_isEmpty())
 393                 {
 394                         sese p
 395                         {
 396                                 //Gets a certain number of paths for the rblock and works on it
 397                                 Queue_t localWorkQueue = masterWorkQueue.get(labyrinth.global_workload, masterWorkQueue);
 398                                 Vector_t myPathVectorPtr = routerPtr.solveLogic(localWorkQueue, MGClone, routerPtr);
 399                         }
 400
 401                         sese s
 402                         {
 403                                 Vector_t vector_t = new Vector_t();
 404                                 Vector_t syncPathVectorPtr = vector_t.vector_alloc(labyrinth.global_workload);
 405
 406                          CoordPathWrapper singlePathSolution = (CoordPathWrapper) myPathVectorPtr.vector_popBack();
 407                          while(singlePathSolution != null)
 408                          {
 409                                  //checkPath will automatically clone GridPtr to prevent screwing with it
 410                                  if(mazePtr.checkPath(singlePathSolution, masterGrid, ++id))
 411                                  {
 412                                          masterGrid.TM_addPath(singlePathSolution.thePath);
 413                                          syncPathVectorPtr.vector_pushBack(singlePathSolution.thePath);
 414                                  }
 415                                  else
 416                                  {
 417                                          id--;
 418                                          redoQueue.queue_push(singlePathSolution.coordinatePair);
 419                                  }
 420
 421                                  singlePathSolution = (CoordPathWrapper) myPathVectorPtr.vector_popBack();
 422                          }
 423
 424                          GlobalPathVectorPtr.insert(syncPathVectorPtr);
 425                         }
 426                 }
 427                 masterWorkQueue = redoQueue;
 428         }
 429     }
 430
 431
 432     private Vector_t solveLogic(Queue_t localWorkQueue, Grid gridPtr, Router routerPtr)
 433     {
 434         Vector_t vector_t = new Vector_t();
 435         Vector_t localPathVectorPtr = vector_t.vector_alloc(1);
 436
 437         Queue_Int myExpansionQueuePtr = Queue_Int.queue_alloc(-1);
 438
 439         Grid MGCopy = gridPtr.alloc(gridPtr.width, gridPtr.height, gridPtr.depth);
 440         MGCopy.copy(MGCopy, gridPtr); /* ok if not most up-to-date */
 441
 442         //need to create ANOTHER copy since apparently the expand function fills the grid with misc data
 443         Grid tempGridPtr = MGCopy.alloc(MGCopy.width, MGCopy.height, MGCopy.depth);
 444
 445         while(!localWorkQueue.queue_isEmpty())
 446         {
 447             Pair coordinatePairPtr = (Pair) localWorkQueue.queue_pop();
 448             if(coordinatePairPtr == null)
 449                 break;
 450
 451             Coordinate srcPtr = (Coordinate)coordinatePairPtr.first;
 452             Coordinate dstPtr = (Coordinate)coordinatePairPtr.second;
 453 //            System.out.println("SRC x = " + srcPtr.x + "  y = " + srcPtr.y + " z = " +srcPtr.z);
 454
 455             boolean success = false;
 456             Vector_t pointVectorPtr = null;
 457
 458             tempGridPtr.copy(tempGridPtr, MGCopy); /* ok if not most up-to-date */
 459
 460             //If solving fails here, then it fails silently
 461             if(routerPtr.PdoExpansion(routerPtr,tempGridPtr,myExpansionQueuePtr,srcPtr,dstPtr)) {
 462                 pointVectorPtr = routerPtr.PdoTraceback(MGCopy,tempGridPtr,dstPtr, routerPtr.bendCost);
 463
 464                 if (pointVectorPtr != null)
 465                 {
 466                         //changed to use local copy of this, will store point ptr in another queue.
 467                     MGCopy.TM_addPath(pointVectorPtr);
 468                     success = true;
 469                 }
 470             }
 471
 472             if(success)
 473             {
 474                 CoordPathWrapper currPath = new CoordPathWrapper(coordinatePairPtr, pointVectorPtr);
 475                 boolean status = localPathVectorPtr.vector_pushBack(currPath);
 476
 477                 if(!status)
 478                 {
 479                         //if it fails to push on a Vector, then we've run out of space
 480                         //and there's really nothing to do but to just exit the system
 481                     System.out.println("Assert in Router_Solve");
 482                     System.exit(1);
 483                 }
 484             }
 485         }
 486
 487         return localPathVectorPtr;
 488     }
 489
 490 }
 491
 492
 493 /* =============================================================================
 494  *
 495  * End of router.java
 496  *
 497  * =============================================================================
 498  */