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

   1 /*=============================================================================
   2  *
   3  * Maze.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * =============================================================================
  11  *
  12  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  13  * of the files.
  14  *
  15  * ------------------------------------------------------------------------
  16  *
  17  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of ssca2, please see ssca2/COPYRIGHT
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  26  * header of the files.
  27  *
  28  * ------------------------------------------------------------------------
  29  *
  30  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  31  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  32  *
  33  * ------------------------------------------------------------------------
  34  *
  35  * Unless otherwise noted, the following license applies to STAMP files:
  36  *
  37  * Copyright (c) 2007, Stanford University
  38  * All rights reserved.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions are
  42  * met:
  43  *
  44  *     * Redistributions of source code must retain the above copyright
  45  *       notice, this list of conditions and the following disclaimer.
  46  *
  47  *     * Redistributions in binary form must reproduce the above copyright
  48  *       notice, this list of conditions and the following disclaimer in
  49  *       the documentation and/or other materials provided with the
  50  *       distribution.
  51  *
  52  *     * Neither the name of Stanford University nor the names of its
  53  *       contributors may be used to endorse or promote products derived
  54  *       from this software without specific prior written permission.
  55  *
  56  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  57  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  58  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  59  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  60  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  61  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  62  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  63  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  64  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  65  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  66  * THE POSSIBILITY OF SUCH DAMAGE.
  67  *
  68  * =============================================================================
  69  */
  70
  71 //#define GRID_POINT_FULL -2
  72 //#define GRID_POINT_EMPTY -1
  73
  74 //TODO change these back and delete class variables.
  75
  76 public class Maze
  77 {
  78         private static int GRID_POINT_FULL;
  79         private static int GRID_POINT_EMPTY;
  80
  81     Grid gridPtr;
  82     Queue_t workQueuePtr;
  83     Vector_t wallVectorPtr; /* contains source/destination pairs to route */
  84     Vector_t srcVectorPtr;  /* obstacles */
  85     Vector_t dstVectorPtr;  /* destinations */
  86
  87     public Maze()
  88     {
  89         //these were changed from #defines
  90         GRID_POINT_FULL = -2;
  91         GRID_POINT_EMPTY = -1;
  92     }
  93
  94
  95 /* =============================================================================
  96  * maze_alloc
  97  * =============================================================================
  98  maze_t* maze_alloc ();
  99  */
 100    public Maze alloc()
 101    {
 102        Maze mazePtr = new Maze();
 103
 104        if(mazePtr != null) {
 105            Vector_t vector_t = new Vector_t();
 106            Queue_t queue_t = new Queue_t();
 107
 108            mazePtr.gridPtr = null;
 109            mazePtr.workQueuePtr = queue_t.queue_alloc(1024);
 110            mazePtr.wallVectorPtr = vector_t.vector_alloc(1);
 111            mazePtr.srcVectorPtr = vector_t.vector_alloc(1);
 112            mazePtr.dstVectorPtr = vector_t.vector_alloc(1);
 113
 114        }
 115
 116        return mazePtr;
 117    }
 118
 119 /* =============================================================================
 120  * maze_free
 121  * =============================================================================
 122  void maze_free (maze_t* mazePtr);
 123  */
 124     public static void free(Maze m)
 125     {
 126         m = null;
 127     }
 128
 129 /* =============================================================================
 130  * addToGrid
 131  * =============================================================================
 132  */
 133     private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type)
 134     {
 135         int i;
 136         int n = vectorPtr.vector_getSize();
 137
 138         for(i = 0; i < n; i++) {
 139             Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i);
 140             if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z))
 141             {
 142                 System.out.println("Error: " + type + " (" + coordinatePtr.x +
 143                                                       ", " + coordinatePtr.y +
 144                                                       ", " + coordinatePtr.z);
 145                 System.exit(1);
 146             }
 147         }
 148         gridPtr.addPath(vectorPtr);
 149     }
 150 /* =============================================================================
 151  * maze_read
 152  * -- Return number of path to route
 153  * =============================================================================
 154  long maze_read (maze_t* mazePtr, char* inputFileName);
 155  */
 156     public int readMaze(String inputFileName)
 157     {
 158                 Coordinate coordinate = new Coordinate();
 159             FileInputStream in = new FileInputStream(inputFileName);
 160
 161
 162             /*
 163              * Parse input file
 164              */
 165             int lineNumber = 0;
 166             int height = -1;
 167             int width = -1;
 168             int depth = -1;
 169             boolean isParseError = false;
 170             List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair);
 171             String line;
 172
 173             while((line = in.readLine()) != null) {
 174                 String code;
 175                 int[] xy = new int[6];  // equivalent to x1,y1,z1,x2,y2,z2
 176                 int numToken = 0;
 177
 178                 StringTokenizer tok = new StringTokenizer(line);
 179
 180                 if((numToken = tok.countTokens()) < 1 ) {
 181                     continue;
 182                 }
 183
 184                 code = tok.nextToken();
 185
 186                 if(code.equals("#")) {
 187                     /* comment line */
 188                     continue;
 189                 }
 190                 for(int i=0;i<numToken-1;i++) {
 191                     xy[i] = Integer.parseInt(tok.nextToken());
 192                 }
 193
 194                 if(code.equals("d")) {
 195                       /* dimensions (format: d x y z) */
 196                      if(numToken != 4) {
 197                         isParseError = true;
 198                      }
 199                      else {
 200                         width = xy[0];
 201                         height = xy[1];
 202                         depth = xy[2];
 203                         if(width < 1 || height < 1 || depth <1)
 204                             isParseError = true;
 205                      }
 206                  }else if(code.equals("p")) { /* paths (format: p x1 y1 z1 x2 y2 z2) */
 207                     if(numToken != 7) {
 208                         isParseError = true;
 209                     }
 210                     else {
 211                         Coordinate srcPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
 212                         Coordinate dstPtr = coordinate.alloc(xy[3],xy[4],xy[5]);
 213
 214                         if(Coordinate.isEqual(srcPtr,dstPtr)) {
 215                             isParseError = true;
 216                         }
 217                         else {
 218                             Pair coordinatePairPtr = Pair.alloc(srcPtr,dstPtr);
 219                             boolean status = workListPtr.insert(coordinatePairPtr);
 220                             if(!status) {
 221                                 System.out.println("LIST_INSERT????");
 222                                 System.exit(1);
 223                             }
 224                             srcVectorPtr.vector_pushBack(srcPtr);
 225                             dstVectorPtr.vector_pushBack(dstPtr);
 226
 227                         }
 228                     }
 229                 }else if(code.equals("w")) {
 230                          /* walls (format: w x y z) */
 231                         if(numToken != 4) {
 232                             isParseError = true;
 233                         } else {
 234                             Coordinate wallPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
 235                             wallVectorPtr.vector_pushBack(wallPtr);
 236                         }
 237                 }else { /* error */
 238                        isParseError = true;
 239                 }
 240
 241                 if(isParseError)  {/* Error */
 242                     System.out.println("Error: line " + lineNumber + " of " + inputFileName + "invalid");
 243                     System.exit(1);
 244                 }
 245             }
 246             /* iterate over lines in put file */
 247
 248             in.close();
 249             /*
 250              * Initialize grid contents
 251              */
 252             if(width < 1 || height < 1 || depth < 1) {
 253                 System.out.println("Error : Invalid dimensions ( " + width + ", " + height + ", "+ depth + ")");
 254                 System.exit(1);
 255             }
 256
 257             Grid grid = new Grid();
 258             Grid gridPtr = grid.alloc(width,height,depth);
 259             this.gridPtr = gridPtr;
 260             addToGrid(gridPtr,wallVectorPtr,"wall");
 261             addToGrid(gridPtr,srcVectorPtr, "source");
 262             addToGrid(gridPtr,dstVectorPtr, "destination");
 263             System.out.println("Maze dimensions = " + width + " x " + height + " x " + depth);
 264             System.out.println("Paths to route  = " + workListPtr.getSize());
 265
 266             /*
 267              * Initialize work queue
 268              */
 269             List_Iter it = new List_Iter();
 270             it.reset(workListPtr);
 271             while(it.hasNext(workListPtr)) {
 272                 Pair coordinatePairPtr = (Pair)it.next(workListPtr);
 273                 workQueuePtr.queue_push(coordinatePairPtr);
 274             }
 275
 276             List_t.free(workListPtr);
 277
 278             return srcVectorPtr.vector_getSize();
 279     }
 280
 281
 282 /* =============================================================================
 283  * maze_checkPaths
 284  * =============================================================================
 285  bool_t maze_checkPaths (maze_t* mazePtr, list_t* pathListPtr, bool_t doPrintPaths);
 286  */
 287     public boolean checkPaths(List_t pathVectorListPtr,boolean doPrintPaths)
 288     {
 289         int i;
 290         Grid grid = new Grid();
 291         /* Mark walls */
 292         Grid testGridPtr = grid.alloc(gridPtr.width, gridPtr.height, gridPtr.depth);
 293         testGridPtr.addPath(wallVectorPtr);
 294
 295         /* Mark sources */
 296         int numSrc = srcVectorPtr.vector_getSize();
 297 //        System.out.println("numSrc = " +numSrc);
 298 //        System.exit(1);
 299         for(i = 0; i < numSrc; i++) {
 300             Coordinate srcPtr = (Coordinate)srcVectorPtr.vector_at(i);
 301             testGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 302         }
 303
 304         /* Mark destinations */
 305         int numdst = dstVectorPtr.vector_getSize();
 306         for(i = 0; i < numdst; i++) {
 307             Coordinate dstPtr = (Coordinate)dstVectorPtr.vector_at(i);
 308             testGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,0);
 309         }
 310
 311         /* Make sure path is contiguous and does not overlap */
 312         int id = 0;
 313         List_Iter it = new List_Iter();
 314         it.reset(pathVectorListPtr);
 315         while(it.hasNext(pathVectorListPtr)) {
 316             Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr);
 317             int numPath = pathVectorPtr.vector_getSize();
 318
 319             for(i = 0; i < numPath; i++) {
 320                 id++;
 321                 Vector_t pointVectorPtr = (Vector_t)pathVectorPtr.vector_at(i);
 322                 /* Check start */
 323                 int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
 324                 int[] x = new int[1];
 325                 int[] y = new int[1];
 326                 int[] z = new int[1];
 327                 gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 328
 329                 if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 330                     Grid.free(testGridPtr);
 331                     return false;
 332                 }
 333                 Coordinate prevCoordinate = new Coordinate();
 334                 x = new int[1];
 335                 y = new int[1];
 336                 z = new int[1];
 337                 gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 338                 prevCoordinate.x = x[0];
 339                 prevCoordinate.y = y[0];
 340                 prevCoordinate.z = z[0];
 341
 342
 343                 int numPoint = pointVectorPtr.vector_getSize();
 344                 int j;
 345
 346                 for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
 347                     int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 348                     Coordinate currCoordinate = new Coordinate();
 349                     x = new int[1];
 350                     y = new int[1];
 351                     z = new int[1];
 352                     gridPtr.getPointIndices(currGridPointIndex,x,y,z);
 353                     currCoordinate.x = x[0];
 354                     currCoordinate.y = y[0];
 355                     currCoordinate.z = z[0];
 356
 357                     if(!Coordinate.areAdjacent(currCoordinate,prevCoordinate)) {
 358                         System.out.println("you there?");
 359                         Grid.free(testGridPtr);
 360                         return false;
 361                     }
 362
 363                     prevCoordinate = currCoordinate;
 364                     int xx = currCoordinate.x;
 365                     int yy = currCoordinate.y;
 366                     int zz = currCoordinate.z;
 367                     if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY) {
 368                         Grid.free(testGridPtr);
 369                         return false;
 370                     } else {
 371                         testGridPtr.setPoint(xx,yy,zz,id);
 372                     }
 373                 }
 374                 /* Check end */
 375                 int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 376                 gridPtr.getPointIndices(lastGridPointIndex,x,y,z);
 377                 if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 378                     Grid.free(testGridPtr);
 379                     return false;
 380                 }
 381             } /* iterate over pathVector */
 382         } /* iterate over pathVectorList */
 383
 384         if(doPrintPaths) {
 385             System.out.println("\nRouted Maze:");
 386             testGridPtr.print();
 387         }
 388
 389         Grid.free(testGridPtr);
 390
 391         return true;
 392     }
 393
 394     /* =============================================================================
 395      * maze check A path
 396      * Implemented for rblocks
 397      * =============================================================================
 398      */
 399     public boolean checkPath(CoordPathWrapper singlePath, Grid localGrid, int id)
 400     {
 401         Grid testGridPtr = localGrid.alloc(localGrid.width, localGrid.height, localGrid.depth);
 402         testGridPtr.copy(testGridPtr, localGrid);
 403         Vector_t pointVectorPtr = singlePath.thePath;
 404         Coordinate srcPtr = (Coordinate) singlePath.coordinatePair.first;
 405         Coordinate dstPtr = (Coordinate) singlePath.coordinatePair.second;
 406
 407         /* mark source and destination */
 408         testGridPtr.setPoint(srcPtr.x, srcPtr.y, srcPtr.z, 0);
 409         testGridPtr.setPoint(dstPtr.x, dstPtr.y, dstPtr.z, 0);
 410
 411         /* makes sure path is contiguous and does not overlap */
 412         /* Check start */
 413         int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
 414         int[] x = new int[1];
 415         int[] y = new int[1];
 416         int[] z = new int[1];
 417         gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 418
 419         if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 420             Grid.free(testGridPtr);
 421             return false;
 422         }
 423         Coordinate prevCoordinate = new Coordinate();
 424         x = new int[1];
 425         y = new int[1];
 426         z = new int[1];
 427         gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 428         prevCoordinate.x = x[0];
 429         prevCoordinate.y = y[0];
 430         prevCoordinate.z = z[0];
 431
 432
 433         int numPoint = pointVectorPtr.vector_getSize();
 434         int j;
 435
 436         for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
 437             int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 438             Coordinate currCoordinate = new Coordinate();
 439             x = new int[1];
 440             y = new int[1];
 441             z = new int[1];
 442             gridPtr.getPointIndices(currGridPointIndex,x,y,z);
 443             currCoordinate.x = x[0];
 444             currCoordinate.y = y[0];
 445             currCoordinate.z = z[0];
 446
 447             if(!Coordinate.areAdjacent(currCoordinate,prevCoordinate)) {
 448                 System.out.println("you there?");
 449                 Grid.free(testGridPtr);
 450                 return false;
 451             }
 452
 453             prevCoordinate = currCoordinate;
 454             int xx = currCoordinate.x;
 455             int yy = currCoordinate.y;
 456             int zz = currCoordinate.z;
 457             if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY)
 458             {
 459                 Grid.free(testGridPtr);
 460                 return false;
 461             }
 462             else
 463             {
 464                 testGridPtr.setPoint(xx,yy,zz,id);
 465             }
 466         }
 467         /* Check end */
 468         int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 469         gridPtr.getPointIndices(lastGridPointIndex,x,y,z);
 470         if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 471             Grid.free(testGridPtr);
 472             return false;
 473         }
 474
 475         return true;
 476     }
 477
 478
 479
 480  }
 481 /* =============================================================================
 482  *
 483  * End of maze.h
 484  *
 485  * =============================================================================
 486  */