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

   1 import java.io.File;
   2 import java.util.Scanner;
   3 import java.util.StringTokenizer;
   4
   5 /*=============================================================================
   6  *
   7  * Maze.java
   8  *
   9  * =============================================================================
  10  *
  11  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
  12  * Author: Chi Cao Minh
  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 GRID_POINT_FULL -2
  76 //#define GRID_POINT_EMPTY -1
  77
  78 //TODO change these back and delete class variables.
  79
  80 public class Maze
  81 {
  82         private static int GRID_POINT_FULL;
  83         private static int GRID_POINT_EMPTY;
  84
  85     Grid gridPtr;
  86     Queue_t workQueuePtr;
  87     Vector_t wallVectorPtr; /* contains source/destination pairs to route */
  88     Vector_t srcVectorPtr;  /* obstacles */
  89     Vector_t dstVectorPtr;  /* destinations */
  90
  91     public Maze()
  92     {
  93         //these were changed from #defines
  94         GRID_POINT_FULL = -2;
  95         GRID_POINT_EMPTY = -1;
  96     }
  97
  98
  99 /* =============================================================================
 100  * maze_alloc
 101  * =============================================================================
 102  maze_t* maze_alloc ();
 103  */
 104    public Maze alloc()
 105    {
 106        Maze mazePtr = new Maze();
 107
 108        if(mazePtr != null) {
 109            Vector_t vector_t = new Vector_t();
 110            Queue_t queue_t = new Queue_t();
 111
 112            mazePtr.gridPtr = null;
 113            mazePtr.workQueuePtr = queue_t.queue_alloc(1024);
 114            mazePtr.wallVectorPtr = vector_t.vector_alloc(1);
 115            mazePtr.srcVectorPtr = vector_t.vector_alloc(1);
 116            mazePtr.dstVectorPtr = vector_t.vector_alloc(1);
 117
 118        }
 119
 120        return mazePtr;
 121    }
 122
 123 /* =============================================================================
 124  * maze_free
 125  * =============================================================================
 126  void maze_free (maze_t* mazePtr);
 127  */
 128     public static void free(Maze m)
 129     {
 130         m = null;
 131     }
 132
 133 /* =============================================================================
 134  * addToGrid
 135  * =============================================================================
 136  */
 137     private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type)
 138     {
 139         int i;
 140         int n = vectorPtr.vector_getSize();
 141
 142         for(i = 0; i < n; i++) {
 143             Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i);
 144             if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z))
 145             {
 146                 System.out.println("Error: " + type + " (" + coordinatePtr.x +
 147                                                       ", " + coordinatePtr.y +
 148                                                       ", " + coordinatePtr.z);
 149                 System.exit(1);
 150             }
 151         }
 152         gridPtr.addPath(vectorPtr);
 153     }
 154 /* =============================================================================
 155  * maze_read
 156  * -- Return number of path to route
 157  * =============================================================================
 158  long maze_read (maze_t* mazePtr, char* inputFileName);
 159  */
 160     public int readMaze(String inputFileName)
 161     {
 162
 163         //TODO remove TRY
 164         try
 165         {
 166                 Coordinate coordinate = new Coordinate();
 167 //            FileInputStream in = new FileInputStream(inputFileName);
 168                 //TODO remove this and uncomment the line above.
 169                 Scanner in = new Scanner(new File(inputFileName));
 170
 171             /*
 172              * Parse input file
 173              */
 174             int lineNumber = 0;
 175             int height = -1;
 176             int width = -1;
 177             int depth = -1;
 178             boolean isParseError = false;
 179             List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair);
 180             String line;
 181
 182             //TODO change this back as well
 183 //            while((line = in.readLine()) != null) {
 184             while(in.hasNextLine())
 185             {
 186
 187                 line = in.nextLine();
 188
 189                 String code;
 190                 int[] xy = new int[6];  // equivalent to x1,y1,z1,x2,y2,z2
 191                 int numToken = 0;
 192
 193                 StringTokenizer tok = new StringTokenizer(line);
 194
 195                 if((numToken = tok.countTokens()) < 1 ) {
 196                     continue;
 197                 }
 198
 199                 code = tok.nextToken();
 200
 201                 if(code.equals("#")) {
 202                     /* comment line */
 203                     continue;
 204                 }
 205                 for(int i=0;i<numToken-1;i++) {
 206                     xy[i] = Integer.parseInt(tok.nextToken());
 207                 }
 208
 209                 if(code.equals("d")) {
 210                       /* dimensions (format: d x y z) */
 211                      if(numToken != 4) {
 212                         isParseError = true;
 213                      }
 214                      else {
 215                         width = xy[0];
 216                         height = xy[1];
 217                         depth = xy[2];
 218                         if(width < 1 || height < 1 || depth <1)
 219                             isParseError = true;
 220                      }
 221                  }else if(code.equals("p")) { /* paths (format: p x1 y1 z1 x2 y2 z2) */
 222                     if(numToken != 7) {
 223                         isParseError = true;
 224                     }
 225                     else {
 226                         Coordinate srcPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
 227                         Coordinate dstPtr = coordinate.alloc(xy[3],xy[4],xy[5]);
 228
 229                         if(Coordinate.isEqual(srcPtr,dstPtr)) {
 230                             isParseError = true;
 231                         }
 232                         else {
 233                             Pair coordinatePairPtr = Pair.alloc(srcPtr,dstPtr);
 234                             boolean status = workListPtr.insert(coordinatePairPtr);
 235                             if(!status) {
 236                                 System.out.println("LIST_INSERT????");
 237                                 System.exit(1);
 238                             }
 239                             srcVectorPtr.vector_pushBack(srcPtr);
 240                             dstVectorPtr.vector_pushBack(dstPtr);
 241
 242                         }
 243                     }
 244                 }else if(code.equals("w")) {
 245                          /* walls (format: w x y z) */
 246                         if(numToken != 4) {
 247                             isParseError = true;
 248                         } else {
 249                             Coordinate wallPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
 250                             wallVectorPtr.vector_pushBack(wallPtr);
 251                         }
 252                 }else { /* error */
 253                        isParseError = true;
 254                 }
 255
 256                 if(isParseError)  {/* Error */
 257                     System.out.println("Error: line " + lineNumber + " of " + inputFileName + "invalid");
 258                     System.exit(1);
 259                 }
 260             }
 261             /* iterate over lines in put file */
 262
 263             in.close();
 264             /*
 265              * Initialize grid contents
 266              */
 267             if(width < 1 || height < 1 || depth < 1) {
 268                 System.out.println("Error : Invalid dimensions ( " + width + ", " + height + ", "+ depth + ")");
 269                 System.exit(1);
 270             }
 271
 272             Grid grid = new Grid();
 273             Grid gridPtr = grid.alloc(width,height,depth);
 274             this.gridPtr = gridPtr;
 275             addToGrid(gridPtr,wallVectorPtr,"wall");
 276             addToGrid(gridPtr,srcVectorPtr, "source");
 277             addToGrid(gridPtr,dstVectorPtr, "destination");
 278             System.out.println("Maze dimensions = " + width + " x " + height + " x " + depth);
 279             System.out.println("Paths to route  = " + workListPtr.getSize());
 280
 281             /*
 282              * Initialize work queue
 283              */
 284             List_Iter it = new List_Iter();
 285             it.reset(workListPtr);
 286             while(it.hasNext(workListPtr)) {
 287                 Pair coordinatePairPtr = (Pair)it.next(workListPtr);
 288                 workQueuePtr.queue_push(coordinatePairPtr);
 289             }
 290
 291             List_t.free(workListPtr);
 292
 293             return srcVectorPtr.vector_getSize();
 294         } //TODO remove this parenthesis (goes with Try) and the below
 295         catch(Exception e)
 296         {
 297                 System.out.println("The File is non-existant: " + inputFileName);
 298                 e.getStackTrace();
 299                 return -1;
 300         }
 301     }
 302
 303
 304 /* =============================================================================
 305  * maze_checkPaths
 306  * =============================================================================
 307  bool_t maze_checkPaths (maze_t* mazePtr, list_t* pathListPtr, bool_t doPrintPaths);
 308  */
 309     public boolean checkPaths(List_t pathVectorListPtr,boolean doPrintPaths)
 310     {
 311         int i;
 312         Grid grid = new Grid();
 313         /* Mark walls */
 314         Grid testGridPtr = grid.alloc(gridPtr.width, gridPtr.height, gridPtr.depth);
 315         testGridPtr.addPath(wallVectorPtr);
 316
 317         /* Mark sources */
 318         int numSrc = srcVectorPtr.vector_getSize();
 319 //        System.out.println("numSrc = " +numSrc);
 320 //        System.exit(1);
 321         for(i = 0; i < numSrc; i++) {
 322             Coordinate srcPtr = (Coordinate)srcVectorPtr.vector_at(i);
 323             testGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 324         }
 325
 326         /* Mark destinations */
 327         int numdst = dstVectorPtr.vector_getSize();
 328         for(i = 0; i < numdst; i++) {
 329             Coordinate dstPtr = (Coordinate)dstVectorPtr.vector_at(i);
 330             testGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,0);
 331         }
 332
 333         /* Make sure path is contiguous and does not overlap */
 334         int id = 0;
 335         List_Iter it = new List_Iter();
 336         it.reset(pathVectorListPtr);
 337         while(it.hasNext(pathVectorListPtr)) {
 338             Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr);
 339             int numPath = pathVectorPtr.vector_getSize();
 340
 341             for(i = 0; i < numPath; i++) {
 342                 id++;
 343                 Vector_t pointVectorPtr = (Vector_t)pathVectorPtr.vector_at(i);
 344                 /* Check start */
 345                 int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
 346                 int[] x = new int[1];
 347                 int[] y = new int[1];
 348                 int[] z = new int[1];
 349                 gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 350
 351                 if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 352                     Grid.free(testGridPtr);
 353                     return false;
 354                 }
 355                 Coordinate prevCoordinate = new Coordinate();
 356                 x = new int[1];
 357                 y = new int[1];
 358                 z = new int[1];
 359                 gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 360                 prevCoordinate.x = x[0];
 361                 prevCoordinate.y = y[0];
 362                 prevCoordinate.z = z[0];
 363
 364
 365                 int numPoint = pointVectorPtr.vector_getSize();
 366                 int j;
 367
 368                 for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
 369                     int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 370                     Coordinate currCoordinate = new Coordinate();
 371                     x = new int[1];
 372                     y = new int[1];
 373                     z = new int[1];
 374                     gridPtr.getPointIndices(currGridPointIndex,x,y,z);
 375                     currCoordinate.x = x[0];
 376                     currCoordinate.y = y[0];
 377                     currCoordinate.z = z[0];
 378
 379                     if(!Coordinate.areAdjacent(currCoordinate,prevCoordinate)) {
 380                         System.out.println("you there?");
 381                         Grid.free(testGridPtr);
 382                         return false;
 383                     }
 384
 385                     prevCoordinate = currCoordinate;
 386                     int xx = currCoordinate.x;
 387                     int yy = currCoordinate.y;
 388                     int zz = currCoordinate.z;
 389                     if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY) {
 390                         Grid.free(testGridPtr);
 391                         return false;
 392                     } else {
 393                         testGridPtr.setPoint(xx,yy,zz,id);
 394                     }
 395                 }
 396                 /* Check end */
 397                 int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 398                 gridPtr.getPointIndices(lastGridPointIndex,x,y,z);
 399                 if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 400                     Grid.free(testGridPtr);
 401                     return false;
 402                 }
 403             } /* iterate over pathVector */
 404         } /* iterate over pathVectorList */
 405
 406         if(doPrintPaths) {
 407             System.out.println("\nRouted Maze:");
 408             testGridPtr.print();
 409         }
 410
 411         Grid.free(testGridPtr);
 412
 413         return true;
 414     }
 415
 416     /* =============================================================================
 417      * maze check A path
 418      * Implemented for rblocks
 419      * =============================================================================
 420      */
 421     public boolean checkPath(CoordPathWrapper singlePath, Grid localGrid, int id)
 422     {
 423         Grid testGridPtr = localGrid.alloc(localGrid.width, localGrid.height, localGrid.depth);
 424         testGridPtr.copy(testGridPtr, localGrid);
 425         Vector_t pointVectorPtr = singlePath.thePath;
 426         Coordinate srcPtr = (Coordinate) singlePath.coordinatePair.first;
 427         Coordinate dstPtr = (Coordinate) singlePath.coordinatePair.second;
 428
 429         /* mark source and destination */
 430         testGridPtr.setPoint(srcPtr.x, srcPtr.y, srcPtr.z, 0);
 431         testGridPtr.setPoint(dstPtr.x, dstPtr.y, dstPtr.z, 0);
 432
 433         /* makes sure path is contiguous and does not overlap */
 434         /* Check start */
 435         int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
 436         int[] x = new int[1];
 437         int[] y = new int[1];
 438         int[] z = new int[1];
 439         gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 440
 441         if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 442             Grid.free(testGridPtr);
 443             return false;
 444         }
 445         Coordinate prevCoordinate = new Coordinate();
 446         x = new int[1];
 447         y = new int[1];
 448         z = new int[1];
 449         gridPtr.getPointIndices(prevGridPointIndex,x,y,z);
 450         prevCoordinate.x = x[0];
 451         prevCoordinate.y = y[0];
 452         prevCoordinate.z = z[0];
 453
 454
 455         int numPoint = pointVectorPtr.vector_getSize();
 456         int j;
 457
 458         for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
 459             int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 460             Coordinate currCoordinate = new Coordinate();
 461             x = new int[1];
 462             y = new int[1];
 463             z = new int[1];
 464             gridPtr.getPointIndices(currGridPointIndex,x,y,z);
 465             currCoordinate.x = x[0];
 466             currCoordinate.y = y[0];
 467             currCoordinate.z = z[0];
 468
 469             if(!Coordinate.areAdjacent(currCoordinate,prevCoordinate)) {
 470                 System.out.println("you there?");
 471                 Grid.free(testGridPtr);
 472                 return false;
 473             }
 474
 475             prevCoordinate = currCoordinate;
 476             int xx = currCoordinate.x;
 477             int yy = currCoordinate.y;
 478             int zz = currCoordinate.z;
 479             if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY)
 480             {
 481                 Grid.free(testGridPtr);
 482                 return false;
 483             }
 484             else
 485             {
 486                 testGridPtr.setPoint(xx,yy,zz,id);
 487             }
 488         }
 489         /* Check end */
 490         int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 491         gridPtr.getPointIndices(lastGridPointIndex,x,y,z);
 492         if(testGridPtr.getPoint(x[0],y[0],z[0]) != 0) {
 493             Grid.free(testGridPtr);
 494             return false;
 495         }
 496
 497         return true;
 498     }
 499
 500
 501
 502  }
 503 /* =============================================================================
 504  *
 505  * End of maze.h
 506  *
 507  * =============================================================================
 508  */