Robust/src/Benchmarks/Java-Single/Labyrinth3D/Original/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 public class Maze {
  76     Grid gridPtr;
  77     Queue_t workQueuePtr;
  78     Vector_t wallVectorPtr; /* contains source/destination pairs to route */
  79     Vector_t srcVectorPtr;  /* obstacles */
  80     Vector_t dstVectorPtr;  /* destinations */
  81
  82     public int GRID_POINT_FULL;
  83     public int GRID_POINT_EMPTY;
  84
  85     public Maze()
  86     {
  87         GRID_POINT_FULL = -2;
  88         GRID_POINT_EMPTY = -1;
  89     }
  90
  91
  92 /* =============================================================================
  93  * maze_alloc
  94  * =============================================================================
  95  maze_t* maze_alloc ();
  96  */
  97    public static Maze alloc()
  98    {
  99        Maze mazePtr = new Maze();
 100
 101        mazePtr.gridPtr = null;
 102        mazePtr.workQueuePtr = Queue_t.queue_alloc(1024);
 103        mazePtr.wallVectorPtr = Vector_t.vector_alloc(1);
 104        mazePtr.srcVectorPtr = Vector_t.vector_alloc(1);
 105        mazePtr.dstVectorPtr = Vector_t.vector_alloc(1);
 106
 107
 108        return mazePtr;
 109    }
 110
 111 /* =============================================================================
 112  * maze_free
 113  * =============================================================================
 114  void maze_free (maze_t* mazePtr);
 115  */
 116     public static void free(Maze m)
 117     {
 118         m = null;
 119     }
 120
 121 /* =============================================================================
 122  * addToGrid
 123  * =============================================================================
 124  */
 125     private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type)
 126     {
 127         int i;
 128         int n = vectorPtr.vector_getSize();
 129
 130         for(i = 0; i < n; i++) {
 131             Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i);
 132             if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z))
 133             {
 134                 System.out.println("Error: " + type + " (" + coordinatePtr.x +
 135                                                       ", " + coordinatePtr.y +
 136                                                       ", " + coordinatePtr.z);
 137                 System.exit(1);
 138             }
 139         }
 140         gridPtr.addPath(vectorPtr);
 141     }
 142 /* =============================================================================
 143  * maze_read
 144  * -- Return number of path to route
 145  * =============================================================================
 146  long maze_read (maze_t* mazePtr, char* inputFileName);
 147  */
 148     public int readMaze(String inputFileName)
 149     {
 150         //TODO remove TRY
 151         try
 152         {
 153 //          FileInputStream in = new FileInputStream(inputFileName);
 154                 //TODO remove this and uncomment the line above.
 155                 Scanner in = new Scanner(new File(inputFileName));
 156             /*
 157              * Parse input file
 158              */
 159             int lineNumber = 0;
 160             int height = -1;
 161             int width = -1;
 162             int depth = -1;
 163             boolean isParseError = false;
 164             List_t workListPtr = List_t.alloc(1); // List.alloc(Coordinate.comparePair);
 165             String line;
 166
 167             //TODO change this back as well
 168 //          while((line = in.readLine()) != null) {
 169             while(in.hasNextLine()){
 170                 line = in.nextLine();
 171             //TODO remove the above
 172
 173                 String code;
 174                 int[] xy = new int[6];  // equivalent to x1,y1,z1,x2,y2,z2
 175                 int numToken = 0;
 176
 177                 StringTokenizer tok = new StringTokenizer(line);
 178
 179                 if((numToken = tok.countTokens()) < 1 ) {
 180                     continue;
 181                 }
 182
 183                 code = tok.nextToken();
 184
 185                 if(code.equals("#")) {
 186                     /* comment line */
 187                     continue;
 188                 }
 189                 for(int i=0;i<numToken-1;i++) {
 190                     xy[i] = Integer.parseInt(tok.nextToken());
 191                 }
 192
 193                 if(code.equals("d")) {
 194                       /* dimensions (format: d x y z) */
 195                      if(numToken != 4) {
 196                         isParseError = true;
 197                      }
 198                      else {
 199                         width = xy[0];
 200                         height = xy[1];
 201                         depth = xy[2];
 202                         if(width < 1 || height < 1 || depth <1)
 203                             isParseError = true;
 204                      }
 205                  }else if(code.equals("p")) { /* paths (format: p x1 y1 z1 x2 y2 z2) */
 206                     if(numToken != 7) {
 207                         isParseError = true;
 208                     }
 209                     else {
 210                         Coordinate srcPtr = Coordinate.alloc(xy[0],xy[1],xy[2]);
 211                         Coordinate dstPtr = Coordinate.alloc(xy[3],xy[4],xy[5]);
 212
 213                         if(Coordinate.isEqual(srcPtr,dstPtr)) {
 214                             isParseError = true;
 215                         }
 216                         else {
 217                             Pair coordinatePairPtr = Pair.alloc(srcPtr,dstPtr);
 218                             boolean status = workListPtr.insert(coordinatePairPtr);
 219                             srcVectorPtr.vector_pushBack(srcPtr);
 220                             dstVectorPtr.vector_pushBack(dstPtr);
 221
 222                         }
 223                     }
 224                 }else if(code.equals("w")) {
 225                          /* walls (format: w x y z) */
 226                         if(numToken != 4) {
 227                             isParseError = true;
 228                         } else {
 229                             Coordinate wallPtr = Coordinate.alloc(xy[0],xy[1],xy[2]);
 230                             wallVectorPtr.vector_pushBack(wallPtr);
 231                         }
 232                 }else { /* error */
 233                        isParseError = true;
 234                 }
 235
 236                 if(isParseError)  {/* Error */
 237                     System.out.println("Error: line " + lineNumber + " of " + inputFileName + "invalid");
 238                     System.exit(1);
 239                 }
 240             }
 241             /* iterate over lines in put file */
 242
 243             in.close();
 244             /*
 245              * Initialize grid contents
 246              */
 247             if(width < 1 || height < 1 || depth < 1) {
 248                 System.out.println("Error : Invalid dimensions ( " + width + ", " + height + ", "+ depth + ")");
 249                 System.exit(1);
 250             }
 251
 252             Grid gridPtr = Grid.alloc(width,height,depth);
 253             this.gridPtr = gridPtr;
 254             addToGrid(gridPtr,wallVectorPtr,"wall");
 255             addToGrid(gridPtr,srcVectorPtr, "source");
 256             addToGrid(gridPtr,dstVectorPtr, "destination");
 257             System.out.println("Maze dimensions = " + width + " x " + height + " x " + depth);
 258             System.out.println("Paths to route  = " + workListPtr.getSize());
 259
 260             /*
 261              * Initialize work queue
 262              */
 263             List_Iter it = new List_Iter();
 264             it.reset(workListPtr);
 265             while(it.hasNext(workListPtr)) {
 266                 Pair coordinatePairPtr = (Pair)it.next(workListPtr);
 267                 workQueuePtr.queue_push(coordinatePairPtr);
 268             }
 269
 270             List_t.free(workListPtr);
 271
 272             return srcVectorPtr.vector_getSize();
 273         } //TODO remove this parenthesis (goes with Try) and the below
 274         catch(Exception e)
 275         {
 276                 System.out.println("The File is non-existant: " + inputFileName);
 277                 e.getStackTrace();
 278                 return -1;
 279         }
 280     }
 281
 282
 283 /* =============================================================================
 284  * maze_checkPaths
 285  * =============================================================================
 286  bool_t maze_checkPaths (maze_t* mazePtr, list_t* pathListPtr, bool_t doPrintPaths);
 287  */
 288     public boolean checkPaths(List_t pathVectorListPtr,boolean doPrintPaths)
 289     {
 290         int i;
 291
 292         /* Mark walls */
 293         Grid testGridPtr = Grid.alloc(gridPtr.width,gridPtr.height,gridPtr.depth);
 294         testGridPtr.addPath(wallVectorPtr);
 295
 296         /* Mark sources */
 297         int numSrc = srcVectorPtr.vector_getSize();
 298 //        System.out.println("numSrc = " +numSrc);
 299 //        System.exit(1);
 300         for(i = 0; i < numSrc; i++) {
 301             Coordinate srcPtr = (Coordinate)srcVectorPtr.vector_at(i);
 302             testGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
 303         }
 304
 305         /* Mark destinations */
 306         int numdst = dstVectorPtr.vector_getSize();
 307         for(i = 0; i < numdst; i++) {
 308             Coordinate dstPtr = (Coordinate)dstVectorPtr.vector_at(i);
 309             testGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,0);
 310         }
 311
 312 //        testGridPtr.print();
 313
 314         /* Make sure path is contiguous and does not overlap */
 315         int id = 0;
 316         List_Iter it = new List_Iter();
 317         it.reset(pathVectorListPtr);
 318
 319         int height = gridPtr.height;
 320         int width = gridPtr.width;
 321         int area = height * width;
 322
 323         while(it.hasNext(pathVectorListPtr)) {
 324             Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr);
 325             int numPath = pathVectorPtr.vector_getSize();
 326
 327             for(i = 0; i < numPath; i++) {
 328                 id++;
 329                 Vector_t pointVectorPtr = (Vector_t)pathVectorPtr.vector_at(i);
 330                 /* Check start */
 331                 int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
 332
 333                 int z=prevGridPointIndex/area;
 334                 int index2d=prevGridPointIndex%area;
 335                 int y=index2d/width;
 336                 int x=index2d%width;
 337
 338                 if(testGridPtr.getPoint(x,y,z) != 0) {
 339                     return false;
 340                 }
 341
 342                 Coordinate prevCoordinate = new Coordinate();
 343                 prevCoordinate.x = x;
 344                 prevCoordinate.y = y;
 345                 prevCoordinate.z = z;
 346
 347
 348                 int numPoint = pointVectorPtr.vector_getSize();
 349                 int j;
 350
 351                 for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
 352                     int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 353                     Coordinate currCoordinate = new Coordinate();
 354
 355                     z=currGridPointIndex/area;
 356                     index2d=currGridPointIndex%area;
 357                     y=index2d/width;
 358                     x=index2d%width;
 359
 360                     currCoordinate.x = x;
 361                     currCoordinate.y = y;
 362                     currCoordinate.z = z;
 363
 364                     if(!Coordinate.areAdjacent(currCoordinate,prevCoordinate)) {
 365                         System.out.println("you there?");
 366                         return false;
 367                     }
 368
 369                     prevCoordinate = currCoordinate;
 370                     int xx = currCoordinate.x;
 371                     int yy = currCoordinate.y;
 372                     int zz = currCoordinate.z;
 373                     if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY) {
 374                         return false;
 375                     } else {
 376                         testGridPtr.setPoint(xx,yy,zz,id);
 377                     }
 378                 }
 379                 /* Check end */
 380                 int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
 381                 z=lastGridPointIndex/area;
 382                 index2d=lastGridPointIndex%area;
 383                 y=index2d/width;
 384                 x=index2d%width;
 385                 if(testGridPtr.getPoint(x,y,z) != 0) {
 386                     return false;
 387                 }
 388             } /* iterate over pathVector */
 389         } /* iterate over pathVectorList */
 390
 391         if(doPrintPaths) {
 392             System.out.println("\nRouted Maze:");
 393             testGridPtr.print();
 394         }
 395
 396
 397         return true;
 398     }
 399
 400  }
 401 /* =============================================================================
 402  *
 403  * End of maze.h
 404  *
 405  * =============================================================================
 406  */