1 /* =============================================================================
5 * =============================================================================
7 * Copyright (C) Stanford University, 2006. All Rights Reserved.
12 * University of California, Irvine
14 * =============================================================================
16 * For the license of bayes/sort.h and bayes/sort.c, please see the header
19 * ------------------------------------------------------------------------
21 * For the license of kmeans, please see kmeans/LICENSE.kmeans
23 * ------------------------------------------------------------------------
25 * For the license of ssca2, please see ssca2/COPYRIGHT
27 * ------------------------------------------------------------------------
29 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
30 * header of the files.
32 * ------------------------------------------------------------------------
34 * For the license of lib/rbtree.h and lib/rbtree.c, please see
35 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
37 * ------------------------------------------------------------------------
39 * Unless otherwise noted, the following license applies to STAMP files:
41 * Copyright (c) 2007, Stanford University
42 * All rights reserved.
44 * Redistribution and use in source and binary forms, with or without
45 * modification, are permitted provided that the following conditions are
48 * * Redistributions of source code must retain the above copyright
49 * notice, this list of conditions and the following disclaimer.
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
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.
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.
72 * =============================================================================
75 //#define MOMENTUM_ZERO 0
76 //#define MOMENTUM_POSX 1
77 //#define MOMENTUM_POSY 2
78 //#define MOMENTUM_POSZ 3
79 //#define MOMENTUM_NEGX 4
80 //#define MOMENTUM_NEGY 5
81 //#define MOMENTUM_NEGZ 6
82 //#define GRID_POINT_FULL -2
83 //#define GRID_POINT_EMPTY -1
86 private static int MOMENTUM_ZERO;
87 private static int MOMENTUM_POSX;
88 private static int MOMENTUM_POSY;
89 private static int MOMENTUM_POSZ;
90 private static int MOMENTUM_NEGX;
91 private static int MOMENTUM_NEGY;
92 private static int MOMENTUM_NEGZ;
93 private static int GRID_POINT_FULL;
94 private static int GRID_POINT_EMPTY;
101 public static Point MOVE_POSX;
102 public static Point MOVE_POSY;
103 public static Point MOVE_POSZ;
104 public static Point MOVE_NEGX;
105 public static Point MOVE_NEGY;
106 public static Point MOVE_NEGZ;
118 GRID_POINT_FULL = -2;
119 GRID_POINT_EMPTY = -1;
123 /* =============================================================================
125 * =============================================================================
126 * router_t* router_alloc (long xCost, long yCost, long zCost, long bendCost);
128 public static Router alloc(int xCost,int yCost,int zCost,int bendCost)
130 Router routerPtr = new Router();
132 //added lines of code to account for the #defines
133 routerPtr.MOVE_POSX = new Point(1,0,0,0, routerPtr.MOMENTUM_POSX);
134 routerPtr.MOVE_POSY = new Point(0,1,0,0, routerPtr.MOMENTUM_POSY);
135 routerPtr.MOVE_POSZ = new Point(0,0,1,0, routerPtr.MOMENTUM_POSZ);
136 routerPtr.MOVE_NEGX = new Point(-1,0,0,0, routerPtr.MOMENTUM_NEGX);
137 routerPtr.MOVE_NEGY = new Point(0,-1,0,0, routerPtr.MOMENTUM_NEGY);
138 routerPtr.MOVE_NEGZ = new Point(0,0,-1,0, routerPtr.MOMENTUM_NEGZ);
140 if(routerPtr != null) {
141 routerPtr.xCost = xCost;
142 routerPtr.yCost = yCost;
143 routerPtr.zCost = zCost;
144 routerPtr.bendCost = bendCost;
153 /* =============================================================================
155 * =============================================================================
156 * void router_free (router_t* routerPtr);
158 public static void free(Router routerPtr)
163 /* ============================================================================
165 * ============================================================================
167 private void PexpandToNeighbor(Grid myGridPtr,
168 int x,int y,int z, int value,Queue_Int queuePtr)
170 if (myGridPtr.isPointValid(x,y,z)) {
171 int neighborGridPointIndex = myGridPtr.getPointIndex(x,y,z);
172 int neighborValue = myGridPtr.points_unaligned[neighborGridPointIndex][0];
173 if (neighborValue == GRID_POINT_EMPTY) {
174 myGridPtr.points_unaligned[neighborGridPointIndex][0] = value;
175 queuePtr.queue_push(neighborGridPointIndex);
176 } else if (neighborValue != GRID_POINT_FULL) {
178 if (value < neighborValue) {
179 myGridPtr.points_unaligned[neighborGridPointIndex][0] = value;
180 queuePtr.queue_push(neighborGridPointIndex);
187 /* ============================================================================
189 * ============================================================================
191 //will not write to Router ptr
192 public boolean PdoExpansion (Router routerPtr,Grid myGridPtr,Queue_Int queuePtr,
193 Coordinate srcPtr,Coordinate dstPtr)
195 int xCost = routerPtr.xCost;
196 int yCost = routerPtr.yCost;
197 int zCost = routerPtr.zCost;
200 * Potential Optimization: Make 'src' the one closet to edge.
201 * This will likely decrease the area of the emitted wave.
204 queuePtr.queue_clear();
206 int srcGridPointIndex = myGridPtr.getPointIndex(srcPtr.x,srcPtr.y,srcPtr.z);
208 queuePtr.queue_push(srcGridPointIndex);
209 // System.out.println("dstPtr :\tx = " + dstPtr.x + "\ty = " + dstPtr.y + "\tz = " + dstPtr.z);
210 myGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
211 myGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,GRID_POINT_EMPTY);
212 int dstGridPointIndex = myGridPtr.getPointIndex(dstPtr.x,dstPtr.y,dstPtr.z);
213 boolean isPathFound = false;
214 int[] x = new int[1];
215 int[] y = new int[1];
216 int[] z = new int[1];
218 while (!queuePtr.queue_isEmpty()) {
219 int gridPointIndex = queuePtr.queue_pop();
221 // System.out.println("gridPointIndex = " +gridPointIndex);
222 if(gridPointIndex == dstGridPointIndex) {
227 myGridPtr.getPointIndices(gridPointIndex,x,y,z);
228 int value = myGridPtr.points_unaligned[gridPointIndex][0];
233 * Potential Optimization: Only need to check 5 of these
235 PexpandToNeighbor(myGridPtr, x[0]+1, y[0], z[0], (value + xCost), queuePtr);
236 PexpandToNeighbor(myGridPtr, x[0]-1, y[0], z[0], (value + xCost), queuePtr);
237 PexpandToNeighbor(myGridPtr, x[0], y[0]+1, z[0], (value + yCost), queuePtr);
238 PexpandToNeighbor(myGridPtr, x[0], y[0]-1, z[0], (value + yCost), queuePtr);
239 PexpandToNeighbor(myGridPtr, x[0], y[0], z[0]+1, (value + zCost), queuePtr);
240 PexpandToNeighbor(myGridPtr, x[0], y[0], z[0]-1, (value + zCost), queuePtr);
242 } /* iterate over work queue */
248 /* ============================================================================
250 * ============================================================================
252 private void traceToNeighbor(Grid myGridPtr,
259 int x = currPtr.x + movePtr.x;
260 int y = currPtr.y + movePtr.y;
261 int z = currPtr.z + movePtr.z;
263 if (myGridPtr.isPointValid(x,y,z) &&
264 !myGridPtr.isPointEmpty(x,y,z) &&
265 !myGridPtr.isPointFull(x,y,z))
267 int value = myGridPtr.getPoint(x,y,z);
270 if (useMomentum && (currPtr.momentum != movePtr.momentum)) {
273 if ((value + b) <= nextPtr.value) { /* '=' favors neighbors over current */
277 nextPtr.value = value;
278 nextPtr.momentum = movePtr.momentum;
282 /* =============================================================================
284 * =============================================================================
287 //will not modify global variables
288 private Vector_t PdoTraceback(Grid gridPtr,Grid myGridPtr,
289 Coordinate dstPtr, int bendCost)
291 Vector_t vector_t = new Vector_t();
292 Vector_t pointVectorPtr = vector_t.vector_alloc(1);
294 Point next = new Point();
298 next.value = myGridPtr.getPoint(next.x,next.y,next.z);
299 next.momentum = MOMENTUM_ZERO;
302 int gridPointIndex = gridPtr.getPointIndex(next.x,next.y,next.z);
303 pointVectorPtr.vector_pushBack(new Integer(gridPointIndex));
304 myGridPtr.setPoint(next.x,next.y,next.z,GRID_POINT_FULL);
306 /* Check if we are done */
307 if (next.value == 0) {
310 Point curr = new Point();
314 curr.value = next.value;
315 curr.momentum = next.momentum;
321 traceToNeighbor(myGridPtr,curr,MOVE_POSX,true, bendCost, next);
322 traceToNeighbor(myGridPtr,curr,MOVE_POSY,true, bendCost, next);
323 traceToNeighbor(myGridPtr,curr,MOVE_POSZ,true, bendCost, next);
324 traceToNeighbor(myGridPtr,curr,MOVE_NEGX,true, bendCost, next);
325 traceToNeighbor(myGridPtr,curr,MOVE_NEGY,true, bendCost, next);
326 traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,true, bendCost, next);
329 * Because of bend costs, none of the neighbors may appear to be closer.
330 * In this case, pick a neighbor while ignoring momentum.
333 // System.out.println("next x = " + next.x + " y = " + next.y + " z = " + next.z);
335 if ((curr.x == next.y) &&
336 (curr.y == next.y) &&
339 next.value = curr.value;
340 traceToNeighbor(myGridPtr,curr,MOVE_POSX,false, bendCost, next);
341 traceToNeighbor(myGridPtr,curr,MOVE_POSY,false, bendCost, next);
342 traceToNeighbor(myGridPtr,curr,MOVE_POSZ,false, bendCost, next);
343 traceToNeighbor(myGridPtr,curr,MOVE_NEGX,false, bendCost, next);
344 traceToNeighbor(myGridPtr,curr,MOVE_NEGY,false, bendCost, next);
345 traceToNeighbor(myGridPtr,curr,MOVE_NEGZ,false, bendCost, next);
347 if ((curr.x == next.x) &&
348 (curr.y == next.y) &&
351 pointVectorPtr.vector_free();
352 System.out.println("Dead");
358 return pointVectorPtr;
361 /* =============================================================================
363 * =============================================================================
364 * void router_solve (void* argPtr);
366 public static void solve(Object argPtr) {
367 Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
369 //dummy labyrinth object so we can use the global variable later
370 Labyrinth labyrinth = new Labyrinth();
372 //this is where all the paths will be stored
373 List_t GlobalPathVectorPtr = routerArgPtr.pathVectorListPtr;
375 Router routerPtr = routerArgPtr.routerPtr;
376 Maze mazePtr = routerArgPtr.mazePtr;
377 Queue_t masterWorkQueue = mazePtr.workQueuePtr;
378 Grid masterGrid = mazePtr.gridPtr;
380 //used in identification of solved paths (unique)
383 while(!masterWorkQueue.queue_isEmpty())
385 //This will ensure that we'll always have space for the worst case and
386 //reduce overhead from array expansions
387 Queue_t redoQueue = masterWorkQueue.Pqueue_alloc(masterWorkQueue.capacity);
389 Grid MGClone = masterGrid.alloc(masterGrid.width, masterGrid.height, masterGrid.depth);
390 masterGrid.copy(MGClone, masterGrid);
392 while(!masterWorkQueue.queue_isEmpty())
396 //Gets a certain number of paths for the rblock and works on it
397 Queue_t localWorkQueue = masterWorkQueue.get(labyrinth.global_workload, masterWorkQueue);
398 Vector_t myPathVectorPtr = routerPtr.solveLogic(localWorkQueue, MGClone, routerPtr);
403 Vector_t vector_t = new Vector_t();
404 Vector_t syncPathVectorPtr = vector_t.vector_alloc(labyrinth.global_workload);
406 CoordPathWrapper singlePathSolution = (CoordPathWrapper) myPathVectorPtr.vector_popBack();
407 while(singlePathSolution != null)
409 //checkPath will automatically clone GridPtr to prevent screwing with it
410 if(mazePtr.checkPath(singlePathSolution, masterGrid, ++id))
412 masterGrid.TM_addPath(singlePathSolution.thePath);
413 syncPathVectorPtr.vector_pushBack(singlePathSolution.thePath);
418 redoQueue.queue_push(singlePathSolution.coordinatePair);
421 singlePathSolution = (CoordPathWrapper) myPathVectorPtr.vector_popBack();
424 GlobalPathVectorPtr.insert(syncPathVectorPtr);
427 masterWorkQueue = redoQueue;
432 private Vector_t solveLogic(Queue_t localWorkQueue, Grid gridPtr, Router routerPtr)
434 Vector_t vector_t = new Vector_t();
435 Vector_t localPathVectorPtr = vector_t.vector_alloc(1);
437 Queue_Int myExpansionQueuePtr = Queue_Int.queue_alloc(-1);
439 Grid MGCopy = gridPtr.alloc(gridPtr.width, gridPtr.height, gridPtr.depth);
440 MGCopy.copy(MGCopy, gridPtr); /* ok if not most up-to-date */
442 //need to create ANOTHER copy since apparently the expand function fills the grid with misc data
443 Grid tempGridPtr = MGCopy.alloc(MGCopy.width, MGCopy.height, MGCopy.depth);
445 while(!localWorkQueue.queue_isEmpty())
447 Pair coordinatePairPtr = (Pair) localWorkQueue.queue_pop();
448 if(coordinatePairPtr == null)
451 Coordinate srcPtr = (Coordinate)coordinatePairPtr.first;
452 Coordinate dstPtr = (Coordinate)coordinatePairPtr.second;
453 // System.out.println("SRC x = " + srcPtr.x + " y = " + srcPtr.y + " z = " +srcPtr.z);
455 boolean success = false;
456 Vector_t pointVectorPtr = null;
458 tempGridPtr.copy(tempGridPtr, MGCopy); /* ok if not most up-to-date */
460 //If solving fails here, then it fails silently
461 if(routerPtr.PdoExpansion(routerPtr,tempGridPtr,myExpansionQueuePtr,srcPtr,dstPtr)) {
462 pointVectorPtr = routerPtr.PdoTraceback(MGCopy,tempGridPtr,dstPtr, routerPtr.bendCost);
464 if (pointVectorPtr != null)
466 //changed to use local copy of this, will store point ptr in another queue.
467 MGCopy.TM_addPath(pointVectorPtr);
474 CoordPathWrapper currPath = new CoordPathWrapper(coordinatePairPtr, pointVectorPtr);
475 boolean status = localPathVectorPtr.vector_pushBack(currPath);
479 //if it fails to push on a Vector, then we've run out of space
480 //and there's really nothing to do but to just exit the system
481 System.out.println("Assert in Router_Solve");
487 return localPathVectorPtr;
493 /* =============================================================================
497 * =============================================================================