*/
public class Maze {
- Grid gridPtr;
- Queue_t workQueuePtr;
- Vector_t wallVectorPtr; /* contains source/destination pairs to route */
- Vector_t srcVectorPtr; /* obstacles */
- Vector_t dstVectorPtr; /* destinations */
-
- public int GRID_POINT_FULL;
- public int GRID_POINT_EMPTY;
-
- public Maze()
- {
- GRID_POINT_FULL = -2;
- GRID_POINT_EMPTY = -1;
+ Grid gridPtr;
+ Queue_t workQueuePtr;
+ Vector_t wallVectorPtr; /* contains source/destination pairs to route */
+ Vector_t srcVectorPtr; /* obstacles */
+ Vector_t dstVectorPtr; /* destinations */
+
+ public int GRID_POINT_FULL;
+ public int GRID_POINT_EMPTY;
+
+ public Maze() {
+ GRID_POINT_FULL = -2;
+ GRID_POINT_EMPTY = -1;
+ }
+
+ /*
+ * ============================================================================
+ * = maze_alloc
+ * ================================================================
+ * ============= maze_t* maze_alloc ();
+ */
+ public Maze alloc() {
+ Maze mazePtr = new Maze();
+ Vector_t vector_t = new Vector_t();
+ Queue_t queue_t = new Queue_t();
+
+ mazePtr.gridPtr = null;
+ mazePtr.workQueuePtr = queue_t.queue_alloc(1024);
+ mazePtr.wallVectorPtr = vector_t.vector_alloc(1);
+ mazePtr.srcVectorPtr = vector_t.vector_alloc(1);
+ mazePtr.dstVectorPtr = vector_t.vector_alloc(1);
+
+ return mazePtr;
+ }
+
+ /*
+ * ============================================================================
+ * = maze_free
+ * ================================================================
+ * ============= void maze_free (maze_t* mazePtr);
+ */
+ public void free(Maze m) {
+ m = null;
+ }
+
+ /*
+ * ============================================================================
+ * = addToGrid
+ * ================================================================
+ * =============
+ */
+ private void addToGrid(Grid gridPtr, Vector_t vectorPtr, String type) {
+ int i;
+ int n = vectorPtr.vector_getSize();
+
+ for (i = 0; i < n; i++) {
+ Coordinate coordinatePtr = (Coordinate) vectorPtr.vector_at(i);
+ if (!gridPtr.isPointValid(coordinatePtr.x, coordinatePtr.y, coordinatePtr.z)) {
+ System.out.println("Error: " + type + " (" + coordinatePtr.x + ", " + coordinatePtr.y
+ + ", " + coordinatePtr.z);
+ System.exit(1);
+ }
+ }
+ gridPtr.addPath(vectorPtr);
+ }
+
+ /*
+ * ============================================================================
+ * = maze_read -- Return number of path to route
+ * ==============================
+ * =============================================== long maze_read (maze_t*
+ * mazePtr, char* inputFileName);
+ */
+ public int readMaze(String inputFileName) {
+ // Added for mlp compatiability
+ List_t list_t = new List_t();
+ Coordinate coordinate = new Coordinate();
+ Pair pair = new Pair();
+
+ FileInputStream in = new FileInputStream(inputFileName);
+
+ /*
+ * Parse input file
+ */
+ int lineNumber = 0;
+ int height = -1;
+ int width = -1;
+ int depth = -1;
+ boolean isParseError = false;
+ List_t workListPtr = list_t.alloc(1); // List.alloc(Coordinate.comparePair);
+ String line;
+
+ while ((line = in.readLine()) != null) {
+ String code;
+ int[] xy = new int[6]; // equivalent to x1,y1,z1,x2,y2,z2
+ int numToken = 0;
+
+ StringTokenizer tok = new StringTokenizer(line);
+
+ if ((numToken = tok.countTokens()) < 1) {
+ continue;
+ }
+
+ code = tok.nextToken();
+
+ if (code.equals("#")) {
+ /* comment line */
+ continue;
+ }
+ for (int i = 0; i < numToken - 1; i++) {
+ xy[i] = Integer.parseInt(tok.nextToken());
+ }
+
+ if (code.equals("d")) {
+ /* dimensions (format: d x y z) */
+ if (numToken != 4) {
+ isParseError = true;
+ } else {
+ width = xy[0];
+ height = xy[1];
+ depth = xy[2];
+ if (width < 1 || height < 1 || depth < 1)
+ isParseError = true;
+ }
+ } else if (code.equals("p")) { /* paths (format: p x1 y1 z1 x2 y2 z2) */
+ if (numToken != 7) {
+ isParseError = true;
+ } else {
+ Coordinate srcPtr = coordinate.alloc(xy[0], xy[1], xy[2]);
+ Coordinate dstPtr = coordinate.alloc(xy[3], xy[4], xy[5]);
+
+ if (coordinate.isEqual(srcPtr, dstPtr)) {
+ isParseError = true;
+ } else {
+ Pair coordinatePairPtr = pair.alloc(srcPtr, dstPtr);
+ boolean status = workListPtr.insert(coordinatePairPtr);
+ srcVectorPtr.vector_pushBack(srcPtr);
+ dstVectorPtr.vector_pushBack(dstPtr);
+
+ }
+ }
+ } else if (code.equals("w")) {
+ /* walls (format: w x y z) */
+ if (numToken != 4) {
+ isParseError = true;
+ } else {
+ Coordinate wallPtr = coordinate.alloc(xy[0], xy[1], xy[2]);
+ wallVectorPtr.vector_pushBack(wallPtr);
+ }
+ } else { /* error */
+ isParseError = true;
+ }
+
+ if (isParseError) {/* Error */
+ System.out.println("Error: line " + lineNumber + " of " + inputFileName + "invalid");
+ System.exit(1);
+ }
+ }
+ /* iterate over lines in put file */
+
+ in.close();
+ /*
+ * Initialize grid contents
+ */
+ if (width < 1 || height < 1 || depth < 1) {
+ System.out.println("Error : Invalid dimensions ( " + width + ", " + height + ", " + depth
+ + ")");
+ System.exit(1);
}
+ Grid grid = new Grid();
+ Grid gridPtr = grid.alloc(width, height, depth);
+ this.gridPtr = gridPtr;
+ addToGrid(gridPtr, wallVectorPtr, "wall");
+ addToGrid(gridPtr, srcVectorPtr, "source");
+ addToGrid(gridPtr, dstVectorPtr, "destination");
+ System.out.println("Maze dimensions = " + width + " x " + height + " x " + depth);
+ System.out.println("Paths to route = " + workListPtr.getSize());
+
+ /*
+ * Initialize work queue
+ */
+ List_Iter it = new List_Iter();
+ it.reset(workListPtr);
+ while (it.hasNext(workListPtr)) {
+ Pair coordinatePairPtr = (Pair) it.next(workListPtr);
+ workQueuePtr.queue_push(coordinatePairPtr);
+ }
-/* =============================================================================
- * maze_alloc
- * =============================================================================
- maze_t* maze_alloc ();
- */
- public Maze alloc()
- {
- Maze mazePtr = new Maze();
- Vector_t vector_t = new Vector_t();
- Queue_t queue_t = new Queue_t();
-
- mazePtr.gridPtr = null;
- mazePtr.workQueuePtr = queue_t.queue_alloc(1024);
- mazePtr.wallVectorPtr = vector_t.vector_alloc(1);
- mazePtr.srcVectorPtr = vector_t.vector_alloc(1);
- mazePtr.dstVectorPtr = vector_t.vector_alloc(1);
+ list_t.free(workListPtr);
+
+ return srcVectorPtr.vector_getSize();
+ }
+
+ /*
+ * ============================================================================
+ * = maze_checkPaths
+ * ==========================================================
+ * =================== bool_t maze_checkPaths (maze_t* mazePtr, list_t*
+ * pathListPtr, bool_t doPrintPaths);
+ */
+ public boolean checkPaths(List_t pathVectorListPtr, boolean doPrintPaths) {
+ int i;
+
+ /* Mark walls */
+ Grid grid = new Grid();
+ Grid testGridPtr = grid.alloc(gridPtr.width, gridPtr.height, gridPtr.depth);
+ testGridPtr.addPath(wallVectorPtr);
+
+ /* Mark sources */
+ int numSrc = srcVectorPtr.vector_getSize();
+ // System.out.println("numSrc = " +numSrc);
+ // System.exit(1);
+ for (i = 0; i < numSrc; i++) {
+ Coordinate srcPtr = (Coordinate) srcVectorPtr.vector_at(i);
+ testGridPtr.setPoint(srcPtr.x, srcPtr.y, srcPtr.z, 0);
+ }
+ /* Mark destinations */
+ int numdst = dstVectorPtr.vector_getSize();
+ for (i = 0; i < numdst; i++) {
+ Coordinate dstPtr = (Coordinate) dstVectorPtr.vector_at(i);
+ testGridPtr.setPoint(dstPtr.x, dstPtr.y, dstPtr.z, 0);
+ }
- return mazePtr;
- }
+ // testGridPtr.print();
-/* =============================================================================
- * maze_free
- * =============================================================================
- void maze_free (maze_t* mazePtr);
- */
- public void free(Maze m)
- {
- m = null;
- }
+ /* Make sure path is contiguous and does not overlap */
+ int id = 0;
+ List_Iter it = new List_Iter();
+ it.reset(pathVectorListPtr);
-/* =============================================================================
- * addToGrid
- * =============================================================================
- */
- private void addToGrid(Grid gridPtr,Vector_t vectorPtr,String type)
- {
- int i;
- int n = vectorPtr.vector_getSize();
-
- for(i = 0; i < n; i++) {
- Coordinate coordinatePtr = (Coordinate)vectorPtr.vector_at(i);
- if(!gridPtr.isPointValid(coordinatePtr.x,coordinatePtr.y,coordinatePtr.z))
- {
- System.out.println("Error: " + type + " (" + coordinatePtr.x +
- ", " + coordinatePtr.y +
- ", " + coordinatePtr.z);
- System.exit(1);
- }
- }
- gridPtr.addPath(vectorPtr);
- }
-/* =============================================================================
- * maze_read
- * -- Return number of path to route
- * =============================================================================
- long maze_read (maze_t* mazePtr, char* inputFileName);
- */
- public int readMaze(String inputFileName)
- {
- //Added for mlp compatiability
- List_t list_t = new List_t();
- Coordinate coordinate = new Coordinate();
- Pair pair = new Pair();
-
- FileInputStream in = new FileInputStream(inputFileName);
-
- /*
- * Parse input file
- */
- int lineNumber = 0;
- int height = -1;
- int width = -1;
- int depth = -1;
- boolean isParseError = false;
- List_t workListPtr = list_t.alloc(1); // List.alloc(Coordinate.comparePair);
- String line;
-
- while((line = in.readLine()) != null) {
- String code;
- int[] xy = new int[6]; // equivalent to x1,y1,z1,x2,y2,z2
- int numToken = 0;
-
- StringTokenizer tok = new StringTokenizer(line);
-
- if((numToken = tok.countTokens()) < 1 ) {
- continue;
- }
-
- code = tok.nextToken();
-
- if(code.equals("#")) {
- /* comment line */
- continue;
- }
- for(int i=0;i<numToken-1;i++) {
- xy[i] = Integer.parseInt(tok.nextToken());
- }
-
- if(code.equals("d")) {
- /* dimensions (format: d x y z) */
- if(numToken != 4) {
- isParseError = true;
- }
- else {
- width = xy[0];
- height = xy[1];
- depth = xy[2];
- if(width < 1 || height < 1 || depth <1)
- isParseError = true;
- }
- }else if(code.equals("p")) { /* paths (format: p x1 y1 z1 x2 y2 z2) */
- if(numToken != 7) {
- isParseError = true;
- }
- else {
- Coordinate srcPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
- Coordinate dstPtr = coordinate.alloc(xy[3],xy[4],xy[5]);
-
- if(coordinate.isEqual(srcPtr,dstPtr)) {
- isParseError = true;
- }
- else {
- Pair coordinatePairPtr = pair.alloc(srcPtr,dstPtr);
- boolean status = workListPtr.insert(coordinatePairPtr);
- srcVectorPtr.vector_pushBack(srcPtr);
- dstVectorPtr.vector_pushBack(dstPtr);
-
- }
- }
- }else if(code.equals("w")) {
- /* walls (format: w x y z) */
- if(numToken != 4) {
- isParseError = true;
- } else {
- Coordinate wallPtr = coordinate.alloc(xy[0],xy[1],xy[2]);
- wallVectorPtr.vector_pushBack(wallPtr);
- }
- }else { /* error */
- isParseError = true;
- }
-
- if(isParseError) {/* Error */
- System.out.println("Error: line " + lineNumber + " of " + inputFileName + "invalid");
- System.exit(1);
- }
- }
- /* iterate over lines in put file */
-
- in.close();
- /*
- * Initialize grid contents
- */
- if(width < 1 || height < 1 || depth < 1) {
- System.out.println("Error : Invalid dimensions ( " + width + ", " + height + ", "+ depth + ")");
- System.exit(1);
- }
+ int height = gridPtr.height;
+ int width = gridPtr.width;
+ int area = height * width;
- Grid grid = new Grid();
- Grid gridPtr = grid.alloc(width,height,depth);
- this.gridPtr = gridPtr;
- addToGrid(gridPtr,wallVectorPtr,"wall");
- addToGrid(gridPtr,srcVectorPtr, "source");
- addToGrid(gridPtr,dstVectorPtr, "destination");
- System.out.println("Maze dimensions = " + width + " x " + height + " x " + depth);
- System.out.println("Paths to route = " + workListPtr.getSize());
-
- /*
- * Initialize work queue
- */
- List_Iter it = new List_Iter();
- it.reset(workListPtr);
- while(it.hasNext(workListPtr)) {
- Pair coordinatePairPtr = (Pair)it.next(workListPtr);
- workQueuePtr.queue_push(coordinatePairPtr);
- }
+ while (it.hasNext(pathVectorListPtr)) {
+ Vector_t pathVectorPtr = (Vector_t) it.next(pathVectorListPtr);
+ int numPath = pathVectorPtr.vector_getSize();
- list_t.free(workListPtr);
+ for (i = 0; i < numPath; i++) {
+ id++;
+ Vector_t pointVectorPtr = (Vector_t) pathVectorPtr.vector_at(i);
+ /* Check start */
+ int prevGridPointIndex = ((Integer) pointVectorPtr.vector_at(0)).intValue();
- return srcVectorPtr.vector_getSize();
- }
-
+ int z = prevGridPointIndex / area;
+ int index2d = prevGridPointIndex % area;
+ int y = index2d / width;
+ int x = index2d % width;
-/* =============================================================================
- * maze_checkPaths
- * =============================================================================
- bool_t maze_checkPaths (maze_t* mazePtr, list_t* pathListPtr, bool_t doPrintPaths);
- */
- public boolean checkPaths(List_t pathVectorListPtr,boolean doPrintPaths)
- {
- int i;
-
- /* Mark walls */
- Grid grid = new Grid();
- Grid testGridPtr = grid.alloc(gridPtr.width,gridPtr.height,gridPtr.depth);
- testGridPtr.addPath(wallVectorPtr);
-
- /* Mark sources */
- int numSrc = srcVectorPtr.vector_getSize();
-// System.out.println("numSrc = " +numSrc);
-// System.exit(1);
- for(i = 0; i < numSrc; i++) {
- Coordinate srcPtr = (Coordinate)srcVectorPtr.vector_at(i);
- testGridPtr.setPoint(srcPtr.x,srcPtr.y,srcPtr.z,0);
+ if (testGridPtr.getPoint(x, y, z) != 0) {
+ return false;
}
- /* Mark destinations */
- int numdst = dstVectorPtr.vector_getSize();
- for(i = 0; i < numdst; i++) {
- Coordinate dstPtr = (Coordinate)dstVectorPtr.vector_at(i);
- testGridPtr.setPoint(dstPtr.x,dstPtr.y,dstPtr.z,0);
+ Coordinate prevCoordinate = new Coordinate();
+ prevCoordinate.x = x;
+ prevCoordinate.y = y;
+ prevCoordinate.z = z;
+
+ int numPoint = pointVectorPtr.vector_getSize();
+ int j;
+
+ for (j = 1; j < (numPoint - 1); j++) { /* no need to check endpoints */
+ int currGridPointIndex = ((Integer) pointVectorPtr.vector_at(j)).intValue();
+ Coordinate currCoordinate = new Coordinate();
+
+ z = currGridPointIndex / area;
+ index2d = currGridPointIndex % area;
+ y = index2d / width;
+ x = index2d % width;
+
+ currCoordinate.x = x;
+ currCoordinate.y = y;
+ currCoordinate.z = z;
+
+ if (!currCoordinate.areAdjacent(currCoordinate, prevCoordinate)) {
+ System.out.println("you there?");
+ return false;
+ }
+
+ prevCoordinate = currCoordinate;
+ int xx = currCoordinate.x;
+ int yy = currCoordinate.y;
+ int zz = currCoordinate.z;
+ if (testGridPtr.getPoint(xx, yy, zz) != GRID_POINT_EMPTY) {
+ return false;
+ } else {
+ testGridPtr.setPoint(xx, yy, zz, id);
+ }
}
-
-// testGridPtr.print();
-
- /* Make sure path is contiguous and does not overlap */
- int id = 0;
- List_Iter it = new List_Iter();
- it.reset(pathVectorListPtr);
-
- int height = gridPtr.height;
- int width = gridPtr.width;
- int area = height * width;
-
- while(it.hasNext(pathVectorListPtr)) {
- Vector_t pathVectorPtr = (Vector_t)it.next(pathVectorListPtr);
- int numPath = pathVectorPtr.vector_getSize();
-
- for(i = 0; i < numPath; i++) {
- id++;
- Vector_t pointVectorPtr = (Vector_t)pathVectorPtr.vector_at(i);
- /* Check start */
- int prevGridPointIndex = ((Integer)pointVectorPtr.vector_at(0)).intValue();
-
- int z=prevGridPointIndex/area;
- int index2d=prevGridPointIndex%area;
- int y=index2d/width;
- int x=index2d%width;
-
- if(testGridPtr.getPoint(x,y,z) != 0) {
- return false;
- }
-
- Coordinate prevCoordinate = new Coordinate();
- prevCoordinate.x = x;
- prevCoordinate.y = y;
- prevCoordinate.z = z;
-
-
- int numPoint = pointVectorPtr.vector_getSize();
- int j;
-
- for(j = 1; j< (numPoint - 1) ;j++) { /* no need to check endpoints */
- int currGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
- Coordinate currCoordinate = new Coordinate();
-
- z=currGridPointIndex/area;
- index2d=currGridPointIndex%area;
- y=index2d/width;
- x=index2d%width;
-
- currCoordinate.x = x;
- currCoordinate.y = y;
- currCoordinate.z = z;
-
- if(!currCoordinate.areAdjacent(currCoordinate,prevCoordinate)) {
- System.out.println("you there?");
- return false;
- }
-
- prevCoordinate = currCoordinate;
- int xx = currCoordinate.x;
- int yy = currCoordinate.y;
- int zz = currCoordinate.z;
- if(testGridPtr.getPoint(xx,yy,zz) != GRID_POINT_EMPTY) {
- return false;
- } else {
- testGridPtr.setPoint(xx,yy,zz,id);
- }
- }
- /* Check end */
- int lastGridPointIndex = ((Integer)pointVectorPtr.vector_at(j)).intValue();
- z=lastGridPointIndex/area;
- index2d=lastGridPointIndex%area;
- y=index2d/width;
- x=index2d%width;
- if(testGridPtr.getPoint(x,y,z) != 0) {
- return false;
- }
- } /* iterate over pathVector */
- } /* iterate over pathVectorList */
-
- if(doPrintPaths) {
- System.out.println("\nRouted Maze:");
- testGridPtr.print();
+ /* Check end */
+ int lastGridPointIndex = ((Integer) pointVectorPtr.vector_at(j)).intValue();
+ z = lastGridPointIndex / area;
+ index2d = lastGridPointIndex % area;
+ y = index2d / width;
+ x = index2d % width;
+ if (testGridPtr.getPoint(x, y, z) != 0) {
+ return false;
}
+ } /* iterate over pathVector */
+ } /* iterate over pathVectorList */
-
- return true;
+ if (doPrintPaths) {
+ System.out.println("\nRouted Maze:");
+ testGridPtr.print();
}
-
- }
-/* =============================================================================
- *
+
+ return true;
+ }
+
+}
+/*
+ * =============================================================================
+ *
* End of maze.h
- *
+ *
* =============================================================================
*/
* ================================================================
* ============
*/
- public boolean PdoExpansion(Router routerPtr, Grid myGridPtr, Queue_Int queuePtr, Coordinate srcPtr, Coordinate dstPtr) {
+ public boolean PdoExpansion(Router routerPtr, Grid myGridPtr, Queue_Int queuePtr,
+ Coordinate srcPtr, Coordinate dstPtr) {
int xCost = routerPtr.xCost;
int yCost = routerPtr.yCost;
int zCost = routerPtr.zCost;
* ============================================================
* ================
*/
- private void traceToNeighbor(Grid myGridPtr, Point currPtr, Point movePtr, boolean useMomentum, int bendCost,
- Point nextPtr) {
+ private void traceToNeighbor(Grid myGridPtr, Point currPtr, Point movePtr, boolean useMomentum,
+ int bendCost, Point nextPtr) {
int x = currPtr.x + movePtr.x;
int y = currPtr.y + movePtr.y;
int z = currPtr.z + movePtr.z;
- if (myGridPtr.isPointValid(x, y, z) && !myGridPtr.isPointEmpty(x, y, z) && !myGridPtr.isPointFull(x, y, z)) {
+ if (myGridPtr.isPointValid(x, y, z) && !myGridPtr.isPointEmpty(x, y, z)
+ && !myGridPtr.isPointFull(x, y, z)) {
int value = myGridPtr.getPoint(x, y, z);
int b = 0;
return pointVectorPtr;
}
-
- public boolean isEmpty(Queue_t q){
- return (((q.pop + 1) % q.capacity == q.push) ? true : false);
- }
/*
* ============================================================================
* ==============================================================
* =============== void router_solve (void* argPtr);
*/
- public void solve(Object argPtr) {
- Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
- Router routerPtr = routerArgPtr.routerPtr;
- Maze mazePtr = routerArgPtr.mazePtr;
- int workload = routerArgPtr.rblock_workload;
- List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr;
-
- Queue_t masterWorkQueuePtr = mazePtr.workQueuePtr;
- Grid masterGridPtr = mazePtr.gridPtr;
- int bendCost = routerPtr.bendCost;
-
- int id = 0;
-
- while(!masterWorkQueuePtr.queue_isEmpty() ) {
- Queue_t redoQueue = masterWorkQueuePtr.Pqueue_alloc(masterWorkQueuePtr.capacity);
- while(!masterWorkQueuePtr.queue_isEmpty()) {
- Queue_t localWorkQueue = masterWorkQueuePtr.queue_getUpTo(workload);
+ public void solve(Object argPtr)
+ {
+
+ // initialization
+ Solve_Arg routerArgPtr = (Solve_Arg) argPtr;
+ Router routerPtr = routerArgPtr.routerPtr;
+ Maze mazePtr = routerArgPtr.mazePtr;
+ int workload = routerArgPtr.rblock_workload;
+ int bendCost = routerPtr.bendCost;
+ List_t pathVectorListPtr = routerArgPtr.pathVectorListPtr;
+ Queue_t masterWorkQueue = mazePtr.workQueuePtr;
+ Grid masterGrid=mazePtr.gridPtr;
+ Queue_Int queue_int=new Queue_Int();
+ Vector_t vt=new Vector_t();
- sese P {
- //Clone needed since new paths are added to local Grid. Cannot add to master Grid because of rBlock p conflicts
- Grid MGClone = masterGridPtr.alloc(masterGridPtr.width, masterGridPtr.height, masterGridPtr.depth);
- masterGridPtr.copy(MGClone, masterGridPtr);
-
- Vector_t computedPaths = solveLogic(localWorkQueue, MGClone, routerPtr, bendCost, workload);
- }
-
- sese S {
- Vector_t sucessfulPaths = computedPaths.vector_alloc(workload);
- CoordPathWrapper singlePathSolution = (CoordPathWrapper) computedPaths.vector_popBack();
- while(singlePathSolution != null) {
- if(masterGridPtr.TM_addPath(singlePathSolution.pathVector)) {
- //fail
- redoQueue.queue_push(singlePathSolution.coordinatePair);
- } else {
- //success
- sucessfulPaths.vector_pushBack(singlePathSolution.pathVector);
- System.out.println("Path # " + ++id + " added sucessfully!");
- }
- singlePathSolution = (CoordPathWrapper)computedPaths.vector_popBack();
- }
- pathVectorListPtr.insert(sucessfulPaths);
- }//end of sese S
- }//end of inner while
- masterWorkQueuePtr = redoQueue;
- }//end of outer while
- }
-
- private Vector_t solveLogic(Queue_t localWorkQueue, Grid MGCopyPtr, Router routerPtr, int bendCost, int workload) {
- /*
- * Iterate over work list to route each path. This involves an 'expansion'
- * and 'traceback' phase for each source/destination pair.
- */
-
- Vector_t vector_t = new Vector_t();
- Queue_Int queue_int = new Queue_Int();
- Vector_t computedPathsPtr = vector_t.vector_alloc(workload + 2);
- while (true) {
- Pair coordinatePairPtr;
- Queue_Int myExpansionQueuePtr = queue_int.queue_alloc(-1);
-
- if (localWorkQueue.queue_isEmpty()) {
- coordinatePairPtr = null;
- } else {
- coordinatePairPtr = (Pair) localWorkQueue.queue_pop();
- }
-
- if (coordinatePairPtr == null)
- break;
-
- Coordinate srcPtr = (Coordinate) coordinatePairPtr.first;
- Coordinate dstPtr = (Coordinate) coordinatePairPtr.second;
-
- // System.out.println("SRC x = " + srcPtr.x + " y = " + srcPtr.y +
- // " z = " +srcPtr.z);
- Vector_t pointVectorPtr = null;
-
- // Copy needed here since PdoExpansion fills grid with misc data
- Grid tempGrid = MGCopyPtr.alloc(MGCopyPtr.width, MGCopyPtr.height, MGCopyPtr.depth);
- MGCopyPtr.copy(tempGrid, MGCopyPtr); /* ok if not most up-to-date */
-
- if (routerPtr.PdoExpansion(routerPtr, tempGrid, myExpansionQueuePtr, srcPtr, dstPtr)) {
- pointVectorPtr = routerPtr.PdoTraceback(tempGrid, dstPtr, bendCost);
- if (pointVectorPtr != null) {
- // Cannot add to master grid as original due to rBlocks conflicting
- if (MGCopyPtr.TM_addPath(pointVectorPtr)) {
- pointVectorPtr = null;
- } else {
- // Success!
- CoordPathWrapper currPath = new CoordPathWrapper(coordinatePairPtr, pointVectorPtr);
- computedPathsPtr.vector_pushBack(currPath);
+ Vector_t pathArray[]=new Vector_t[workload];
+ Grid gridArray[]=new Grid[workload];
+ Pair workItemArray[]=new Pair[workload];
+
+ for(int i=0;i<gridArray.length;i++){
+ gridArray[i]=masterGrid.scratchalloc(masterGrid.width, masterGrid.height, masterGrid.depth);
+ }
+
+ while(!masterWorkQueue.queue_isEmpty()){
+ Vector_t myPathVectorPtr=vt.vector_alloc(workload);
+ //System.out.println("\nnew round");
+ for(int i=0;i<workload;i++){
+ pathArray[i]=null;
+ }
+
+ //gets work item
+ for(int i=0;i<workload;i++){
+ Pair coordinatePairPtr=null;
+ if(!masterWorkQueue.queue_isEmpty()){
+ coordinatePairPtr=(Pair)masterWorkQueue.queue_pop();
+ }
+ workItemArray[i]=coordinatePairPtr;
+ }
+
+ //parallel loop
+ for(int i=0;i<workload;i++){
+
+ Pair coordinatePairPtr=workItemArray[i];
+ if(coordinatePairPtr==null){
+ break;
+ }
+ Coordinate srcPtr = (Coordinate) coordinatePairPtr.first;
+ Coordinate dstPtr = (Coordinate) coordinatePairPtr.second;
+
+ Grid myGrid=gridArray[i];
+ Vector_t path=null;
+ sese parallel{
+ myGrid.copy(myGrid, masterGrid);
+ Queue_Int myExpansionQueuePtr=queue_int.queue_alloc(-1);
+ if(routerPtr.PdoExpansion(routerPtr, myGrid, myExpansionQueuePtr, srcPtr, dstPtr)){
+ path=routerPtr.PdoTraceback(myGrid, dstPtr, bendCost);
+ }
+ }
+ sese serial{
+ pathArray[i]=path;
+ }
}
+
+ //check path
+ for(int i=0;i<workload;i++){
+ if(pathArray[i]!=null){
+ if(masterGrid.TM_addPath(pathArray[i])){
+ //fail
+ //System.out.print("F ");
+ masterWorkQueue.queue_push(workItemArray[i]);
+ }else{
+ //success
+ //System.out.print("S ");
+ myPathVectorPtr.vector_pushBack(pathArray[i]);
+ }
+ }
+ }
+ pathVectorListPtr.insert(myPathVectorPtr);
}
- }
- }
- return computedPathsPtr;
- }
+ }
}
/*
* =============================================================================
projects / IRC.git / commitdiff