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

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