Robust/src/Benchmarks/oooJava/labyrinth/RouterSingle.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  * rBlock Compilation
  15  * Author: Stephen Yang
  16  * University of California, Irvine
  17  *
  18  * =============================================================================
  19  *
  20  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  21  * of the files.
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  26  *
  27  * ------------------------------------------------------------------------
  28  *
  29  * For the license of ssca2, please see ssca2/COPYRIGHT
  30  *
  31  * ------------------------------------------------------------------------
  32  *
  33  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  34  * header of the files.
  35  *
  36  * ------------------------------------------------------------------------
  37  *
  38  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  39  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  40  *
  41  * ------------------------------------------------------------------------
  42  *
  43  * Unless otherwise noted, the following license applies to STAMP files:
  44  *
  45  * Copyright (c) 2007, Stanford University
  46  * All rights reserved.
  47  *
  48  * Redistribution and use in source and binary forms, with or without
  49  * modification, are permitted provided that the following conditions are
  50  * met:
  51  *
  52  *     * Redistributions of source code must retain the above copyright
  53  *       notice, this list of conditions and the following disclaimer.
  54  *
  55  *     * Redistributions in binary form must reproduce the above copyright
  56  *       notice, this list of conditions and the following disclaimer in
  57  *       the documentation and/or other materials provided with the
  58  *       distribution.
  59  *
  60  *     * Neither the name of Stanford University nor the names of its
  61  *       contributors may be used to endorse or promote products derived
  62  *       from this software without specific prior written permission.
  63  *
  64  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  65  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  66  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  67  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  68  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  69  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  70  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  71  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  72  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  73  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  74  * THE POSSIBILITY OF SUCH DAMAGE.
  75  *
  76  * =============================================================================
  77  */
  78
  79 public class Router {
  80   public int xCost;
  81   public int yCost;
  82   public int zCost;
  83   public int bendCost;
  84   public Point MOVE_POSX;
  85   public Point MOVE_POSY;
  86   public Point MOVE_POSZ;
  87   public Point MOVE_NEGX;
  88   public Point MOVE_NEGY;
  89   public Point MOVE_NEGZ;
  90
  91   private int MOMENTUM_ZERO;
  92   private int MOMENTUM_POSX;
  93   private int MOMENTUM_POSY;
  94   private int MOMENTUM_POSZ;
  95   private int MOMENTUM_NEGX;
  96   private int MOMENTUM_NEGY;
  97   private int MOMENTUM_NEGZ;
  98   private int GRID_POINT_FULL;
  99   private int GRID_POINT_EMPTY;
 100
 101   public Router() {
 102     // Replaced #defines
 103     MOMENTUM_ZERO = 0;
 104     MOMENTUM_POSX = 1;
 105     MOMENTUM_POSY = 2;
 106     MOMENTUM_POSZ = 3;
 107     MOMENTUM_NEGX = 4;
 108     MOMENTUM_NEGY = 5;
 109     MOMENTUM_NEGZ = 6;
 110     GRID_POINT_FULL = -2;
 111     GRID_POINT_EMPTY = -1;
 112   }
 113
 114   /*
 115    * ============================================================================
 116    * = router_alloc
 117    * ==============================================================
 118    * =============== router_t* router_alloc (long xCost, long yCost, long zCost,
 119    * long bendCost);
 120    */
 121   public Router alloc(int xCost, int yCost, int zCost, int bendCost) {
 122     Router routerPtr = new Router();
 123
 124     routerPtr.MOVE_POSX = new Point(1, 0, 0, 0, MOMENTUM_POSX);
 125     routerPtr.MOVE_POSY = new Point(0, 1, 0, 0, MOMENTUM_POSY);
 126     routerPtr.MOVE_POSZ = new Point(0, 0, 1, 0, MOMENTUM_POSZ);
 127     routerPtr.MOVE_NEGX = new Point(-1, 0, 0, 0, MOMENTUM_NEGX);
 128     routerPtr.MOVE_NEGY = new Point(0, -1, 0, 0, MOMENTUM_NEGY);
 129     routerPtr.MOVE_NEGZ = new Point(0, 0, -1, 0, MOMENTUM_NEGZ);
 130
 131     routerPtr.xCost = xCost;
 132     routerPtr.yCost = yCost;
 133     routerPtr.zCost = zCost;
 134     routerPtr.bendCost = bendCost;
 135
 136     return routerPtr;
 137   }
 138
 139   /*
 140    * ============================================================================
 141    * PexpandToneighbor
 142    * ==========================================================
 143    * ==================
 144    */
 145   private void PexpandToNeighbor(Grid myGridPtr, int x, int y, int z, int value, Queue_Int queuePtr) {
 146     if (myGridPtr.isPointValid(x, y, z)) {
 147       int neighborValue = myGridPtr.points_unaligned[x][y][z];
 148       if (neighborValue == GRID_POINT_EMPTY) {
 149         int neighborGridPointIndex = myGridPtr.getPointIndex(x, y, z);
 150         myGridPtr.points_unaligned[x][y][z] = value;
 151         queuePtr.queue_push(neighborGridPointIndex);
 152       } else if (neighborValue != GRID_POINT_FULL) {
 153         if (value < neighborValue) {
 154           int neighborGridPointIndex = myGridPtr.getPointIndex(x, y, z);
 155           myGridPtr.points_unaligned[x][y][z] = value;
 156           queuePtr.queue_push(neighborGridPointIndex);
 157         }
 158       }
 159     }
 160   }
 161
 162   /*
 163    * ============================================================================
 164    * PdoExpansion
 165    * ================================================================
 166    * ============
 167    */
 168   public boolean PdoExpansion(Router routerPtr, Grid myGridPtr, Queue_Int queuePtr,
 169       Coordinate srcPtr, Coordinate dstPtr) {
 170     int xCost = routerPtr.xCost;
 171     int yCost = routerPtr.yCost;
 172     int zCost = routerPtr.zCost;
 173
 174     /*
 175      * Potential Optimization: Make 'src' the one closet to edge. This will
 176      * likely decrease the area of the emitted wave.
 177      */
 178
 179     queuePtr.queue_clear();
 180
 181     int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x, srcPtr.y, srcPtr.z);
 182
 183     queuePtr.queue_push(srcGridPointIndex);
 184
 185     myGridPtr.setPoint(srcPtr.x, srcPtr.y, srcPtr.z, 0);
 186     myGridPtr.setPoint(dstPtr.x, dstPtr.y, dstPtr.z, GRID_POINT_EMPTY);
 187     int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x, dstPtr.y, dstPtr.z);
 188     boolean isPathFound = false;
 189     int height = myGridPtr.height;
 190     int width = myGridPtr.width;
 191     int area = height * width;
 192     while (!queuePtr.queue_isEmpty()) {
 193       int gridPointIndex = queuePtr.queue_pop();
 194
 195       if (gridPointIndex == dstGridPointIndex) {
 196         isPathFound = true;
 197         break;
 198       }
 199
 200       int z = gridPointIndex / area;
 201       int index2d = gridPointIndex % area;
 202       int y = index2d / width;
 203       int x = index2d % width;
 204       int value = myGridPtr.points_unaligned[x][y][z];
 205
 206       /*
 207        * Check 6 neighbors
 208        *
 209        * Potential Optimization: Only need to check 5 of these
 210        */
 211       PexpandToNeighbor(myGridPtr, x + 1, y, z, (value + xCost), queuePtr);
 212       PexpandToNeighbor(myGridPtr, x - 1, y, z, (value + xCost), queuePtr);
 213       PexpandToNeighbor(myGridPtr, x, y + 1, z, (value + yCost), queuePtr);
 214       PexpandToNeighbor(myGridPtr, x, y - 1, z, (value + yCost), queuePtr);
 215       PexpandToNeighbor(myGridPtr, x, y, z + 1, (value + zCost), queuePtr);
 216       PexpandToNeighbor(myGridPtr, x, y, z - 1, (value + zCost), queuePtr);
 217
 218     } /* iterate over work queue */
 219
 220     return isPathFound;
 221   }
 222
 223   /*
 224    * ============================================================================
 225    * traceToNeighbor
 226    * ============================================================
 227    * ================
 228    */
 229   private void traceToNeighbor(Grid myGridPtr, Point currPtr, Point movePtr, boolean useMomentum,
 230       int bendCost, Point nextPtr) {
 231     int x = currPtr.x + movePtr.x;
 232     int y = currPtr.y + movePtr.y;
 233     int z = currPtr.z + movePtr.z;
 234
 235     if (myGridPtr.isPointValid(x, y, z) && !myGridPtr.isPointEmpty(x, y, z)
 236         && !myGridPtr.isPointFull(x, y, z)) {
 237       int value = myGridPtr.getPoint(x, y, z);
 238       int b = 0;
 239
 240       if (useMomentum && (currPtr.momentum != movePtr.momentum)) {
 241         b = bendCost;
 242       }
 243       if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */
 244         nextPtr.x = x;
 245         nextPtr.y = y;
 246         nextPtr.z = z;
 247         nextPtr.value = value;
 248         nextPtr.momentum = movePtr.momentum;
 249       }
 250     }
 251   }
 252
 253   /*
 254    * ============================================================================
 255    * = PdoTraceback
 256    * ==============================================================
 257    * ===============
 258    */
 259
 260   private Vector_t PdoTraceback(Grid myGridPtr, Coordinate dstPtr, int bendCost) {
 261     Vector_t vector_t = new Vector_t();
 262     Vector_t pointVectorPtr = vector_t.vector_alloc(1);
 263
 264     Point next = new Point();
 265     next.x = dstPtr.x;
 266     next.y = dstPtr.y;
 267     next.z = dstPtr.z;
 268     next.value = myGridPtr.getPoint(next.x, next.y, next.z);
 269     next.momentum = MOMENTUM_ZERO;
 270
 271     while (true) {
 272       int gridPointIndex = myGridPtr.getPointIndex(next.x, next.y, next.z);
 273       pointVectorPtr.vector_pushBack(new Integer(gridPointIndex));
 274       myGridPtr.setPoint(next.x, next.y, next.z, GRID_POINT_FULL);
 275
 276       /* Check if we are done */
 277       if (next.value == 0) {
 278         break;
 279       }
 280       Point curr = new Point();
 281       curr.x = next.x;
 282       curr.y = next.y;
 283       curr.z = next.z;
 284       curr.value = next.value;
 285       curr.momentum = next.momentum;
 286
 287       /*
 288        * Check 6 neibors
 289        */
 290
 291       traceToNeighbor(myGridPtr, curr, MOVE_POSX, true, bendCost, next);
 292       traceToNeighbor(myGridPtr, curr, MOVE_POSY, true, bendCost, next);
 293       traceToNeighbor(myGridPtr, curr, MOVE_POSZ, true, bendCost, next);
 294       traceToNeighbor(myGridPtr, curr, MOVE_NEGX, true, bendCost, next);
 295       traceToNeighbor(myGridPtr, curr, MOVE_NEGY, true, bendCost, next);
 296       traceToNeighbor(myGridPtr, curr, MOVE_NEGZ, true, bendCost, next);
 297       /*
 298        * Because of bend costs, none of the neighbors may appear to be closer.
 299        * In this case, pick a neighbor while ignoring momentum.
 300        */
 301
 302       if ((curr.x == next.x) && (curr.y == next.y) && (curr.z == next.z)) {
 303         next.value = curr.value;
 304         traceToNeighbor(myGridPtr, curr, MOVE_POSX, false, bendCost, next);
 305         traceToNeighbor(myGridPtr, curr, MOVE_POSY, false, bendCost, next);
 306         traceToNeighbor(myGridPtr, curr, MOVE_POSZ, false, bendCost, next);
 307         traceToNeighbor(myGridPtr, curr, MOVE_NEGX, false, bendCost, next);
 308         traceToNeighbor(myGridPtr, curr, MOVE_NEGY, false, bendCost, next);
 309         traceToNeighbor(myGridPtr, curr, MOVE_NEGZ, false, bendCost, next);
 310
 311         if ((curr.x == next.x) && (curr.y == next.y) && (curr.z == next.z)) {
 312           System.out.println("Dead");
 313           return null;
 314         }
 315       }
 316     }
 317
 318     return pointVectorPtr;
 319   }
 320
 321   /*
 322    * ============================================================================
 323    * = router_solve
 324    * ==============================================================
 325    * =============== void router_solve (void* argPtr);
 326    */
 327   public void solve(Object argPtr)
 328     {
 329                 //Grabs Data
 330         Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
 331         Router routerPtr = routerArgPtr.routerPtr;
 332         Maze mazePtr = routerArgPtr.mazePtr;
 333         int bendCost = routerPtr.bendCost;
 334         List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr;
 335         Queue_t masterWorkQueue = mazePtr.workQueuePtr;
 336         Grid masterGrid=mazePtr.gridPtr;
 337         Queue_Int queue_int=new Queue_Int();
 338         Vector_t vt=new Vector_t();
 339
 340         //initialization
 341         Grid myGrid = masterGrid.scratchalloc(masterGrid.width, masterGrid.height, masterGrid.depth);
 342         Vector_t myPathVectorPtr=vt.vector_alloc(-1);
 343
 344
 345         while(!masterWorkQueue.queue_isEmpty()){
 346           Pair coordinatePairPtr =(Pair)masterWorkQueue.queue_pop();
 347           if(coordinatePairPtr == null)
 348                   break;
 349
 350           Coordinate srcPtr = (Coordinate) coordinatePairPtr.first;
 351           Coordinate dstPtr = (Coordinate) coordinatePairPtr.second;
 352           myGrid.copy(myGrid, masterGrid);
 353
 354           Queue_Int myExpansionQueuePtr=queue_int.queue_alloc(-1);
 355           if(routerPtr.PdoExpansion(routerPtr, myGrid, myExpansionQueuePtr, srcPtr, dstPtr)){
 356                   Vector_t path = routerPtr.PdoTraceback(myGrid, dstPtr, bendCost);
 357
 358               //if successful
 359                   if(path != null && !masterGrid.TM_addPath(path))
 360                           myPathVectorPtr.vector_pushBack(path);
 361                 }
 362         }
 363
 364         pathVectorListPtr.insert(myPathVectorPtr);
 365     }
 366 }
 367 /*
 368  * =============================================================================
 369  *
 370  * End of router.java
 371  *
 372  * =============================================================================
 373  */