file: utils.cc
/* VLSI CAD Project 3 */
/* Placement Tool */
/* Recursive MinCut */
/* Fall 2000 Anno Domini */
/* Written by Suraj Sudhir */
/* ssudhir@ece.cmu.edu */
#include "main.h"
// chip data
extern int ChipX, ChipY; //Chip Dimensions
extern float K1, K2; //Delay Constants
extern int GatesInSite, PinsInSite;//per site constraints
extern double G; // square root of GatesInSite
extern int NumGates, NumNets; //global - total # of gates, nets
extern gateList *GateArr; //holds all nets connected to each gate
extern int *gateX, *gateY; //holds the (x,y) coordinates of each gate
extern int *tempX1, *tempX2; //temporarily hold (x,y) during horiz
extern int *tempY1, *tempY2; //and vert cuts
extern netList *NetArr; //holds all gates connected to each net
extern int *GatesPerNet; //number of gates per net;
extern int *gatePart; //partition where the gate lies.
extern int *tempPart1, *tempPart2; //for cutline selection -
//temporarily hold partition info
extern padList *PadArr; //pad connected to each net, if any
extern int *PadsPerNet; //total pads to that net
extern int NumPinsConnNets; //total pins
extern pinList *PinConnList; //nets connected by pin
extern int NumTimingPaths; //number of components in each timing path
extern timingList *TimingPaths; // each timing path
extern double *netLen; //length of each net
extern double *netDelay; //delay on each net
extern double TotalWireLen; //total wire length, of course
// other globals
extern int Rotate ; //alternately cut horiz/vert if both cuts
//yield equal wirelength
extern wishGui myGui; //Tcl/Tk stuff
extern char OpFileName[20] ;//default;
extern int FirstRound ; //initialise hMetis only once
/////////////////////////////////////////////////
// performance parameters given at command line//
/////////////////////////////////////////////////
// number of partitions, for k-way
extern int NumPartitions ;
//how to handle balance correction during partitioning
extern int CapacityFix ;
//do the cutting step by step ? (debug)
extern int StepThru ;
//how many times to repeat mincut
extern int NumIters ;
//Metis Seed
extern int Seed ;
//Average net weight
extern int NetWeight ;
//initializing scheme
extern int InitScheme ;
//optimize for...
extern int Optimization ;
//minimize critical path ?
extern int CriticalPathMinimize ;
//compute the wirelength
//individual and total
double computeWireLen(int save, int Net)
{
int i=0;
double hpLength, hp1, hp2;
int minX = 0, maxX = 0, minY = 0, maxY = 0;
netList *netTemp, *Temp1;
double WireLen;
int start, end;
int Init = 0;
WireLen = 0.0;
if ( save == 2 )
{
start = Net;
end = Net+1;
}
else
{
start = 0;
end = NumNets;
}
for ( i=start;i<end;i++ )
{
hpLength = 0.0;
minX = 0; maxX = 0;
minY = 0; maxY = 0;
if ( save )
netLen[i] = 0.0;
netTemp = &NetArr[i];
Init = 0;
while (netTemp)
{
if ( netTemp->Type == GATE )
{
if (!Init)
{
minX = gateX[netTemp->GateID]; maxX = gateX[netTemp->GateID];
minY = gateY[netTemp->GateID]; maxY = gateY[netTemp->GateID];
Init = 1;
}
else
{
if ( gateX[netTemp->GateID] < minX )
minX = gateX[netTemp->GateID];
if ( gateX[netTemp->GateID] > maxX )
maxX = gateX[netTemp->GateID];
if ( gateY[netTemp->GateID] < minY )
minY = gateY[netTemp->GateID];
if ( gateY[netTemp->GateID] > maxY )
maxY = gateY[netTemp->GateID];
}
}
else
{
if ( !Init )
{
minX = PinConnList[netTemp->GateID].xSite;
maxX = PinConnList[netTemp->GateID].xSite;
minY = PinConnList[netTemp->GateID].ySite;
maxY = PinConnList[netTemp->GateID].ySite;
Init = 1;
}
else
{
if ( PinConnList[netTemp->GateID].xSite < minX )
minX = PinConnList[netTemp->GateID].xSite;
if ( PinConnList[netTemp->GateID].xSite > maxX )
maxX = PinConnList[netTemp->GateID].xSite;
if ( PinConnList[netTemp->GateID].ySite < minY )
minY = PinConnList[netTemp->GateID].ySite;
if ( PinConnList[netTemp->GateID].ySite < maxY )
maxY = PinConnList[netTemp->GateID].ySite;
}
}
Temp1 = netTemp->next;
while (Temp1)
{
//half perimeter length
if ((netTemp->Type == GATE) && (Temp1->Type == GATE))
{
if ( ( gateX[netTemp->GateID] == gateX[Temp1->GateID] ) && ( gateY[netTemp->GateID] == gateY[Temp1->GateID] ) )
hpLength += G;
}
else if ((netTemp->Type == PIN) && (Temp1->Type == PIN))
{
if ( ( PinConnList[netTemp->GateID].xSite == PinConnList[Temp1->GateID].xSite ) && ( PinConnList[netTemp->GateID].ySite == PinConnList[Temp1->GateID].ySite ) )
hpLength += G;
}
Temp1 = Temp1->next;
}
netTemp = netTemp->next;
}
if ( save )
netLen[i] = hpLength + (double)(maxX-minX+maxY-minY)*G;
WireLen += hpLength + (double)(maxX-minX+maxY-minY)*G;
}
return WireLen;
}
//check if the net cuts this partition
int cutsThisPartition ( int Net, int Partition )
{
netList *netTemp = &NetArr[Net];
int flag = 0;
while ( netTemp )
{
if ( netTemp->Type == GATE )
{
if ( gatePart[netTemp->GateID] == Partition )
if ( flag >= 2 )
return 1;
else
flag = 1;
if ( gatePart[netTemp->GateID] == Partition )
if ( flag == 1 )
return 1;
else
flag = 2;
}
else
{
if ( flag )
return 1;
else
flag = 3;
}
netTemp = netTemp->next;
}
return 0;
}
//just a debug procedure
void printWireLen()
{
int i;
printf("Gates:\n");
for(i=0;i<NumGates;i++)
{
printf("%f %f\n",gateX[i],gateY[i]);
}
for(i=0;i<NumPinsConnNets;i++)
{
printf("%d %d\n", PinConnList[i].xSite, PinConnList[i].ySite);
}
printf("NetLength:\n");
for(i=0;i<NumNets;i++)
{
printf("%d %f\n",i, netLen[i]);
}
printf("TotalWireLen: %f\n", computeWireLen(0,0));
}
//draw the chip on the TCL canvas
void drawChip()
{
int i,j;
char num[10];
int inkey;
myGui.clearAll();
//grid for squares
for (i=0;i<ChipX+1;i++)
myGui.drawLine(10+i*SQUARE,10,10+i*SQUARE,10+ChipY*SQUARE,"");
for (i=0;i<ChipY+1;i++)
myGui.drawLine(10,10+i*SQUARE,10+ChipX*SQUARE,10+i*SQUARE,"");
//pins as rectangles
for(i=0;i<NumPinsConnNets;i++)
{
myGui.drawRectangle(10+PinConnList[i].xSite*SQUARE+3,10+(ChipY-1-PinConnList[i].ySite)*SQUARE+3,10+(PinConnList[i].xSite+1)*SQUARE-3,10+(ChipY-1-(PinConnList[i].ySite-1))*SQUARE-3,"-fill red");
}
//draw just timing path nets..
//simple lines, as the crow flies
//no manhattan lines
for(i=0;i<NumTimingPaths;i++)
{
int sx, sy, ex, ey;
sx = PinConnList[TimingPaths[i].List[0]-1].xSite;
sy = PinConnList[TimingPaths[i].List[0]-1].ySite;
for(j=2;j<TimingPaths[i].NumObjects-1;j+=2)
{
ex = (int)gateX[TimingPaths[i].List[j]-1];
ey = (int)gateY[TimingPaths[i].List[j]-1];
sprintf(num,"%d",TimingPaths[i].List[j]);
myGui.drawText(10+sx*SQUARE + SQUARE/2, 10+(ChipY-1-sy)*SQUARE + SQUARE/2, num,"");
myGui.drawLine(10+sx*SQUARE + SQUARE/2, 10+(ChipY-1-sy)*SQUARE + SQUARE/2, 10+ex*SQUARE + SQUARE/2, 10+(ChipY-1-ey)*SQUARE + SQUARE/2,"");
sx = ex; sy = ey;
}
ex = PinConnList[TimingPaths[i].List[j]-1].xSite;
ey = PinConnList[TimingPaths[i].List[j]-1].ySite;
myGui.drawLine(10+sx*SQUARE + SQUARE/2, 10+(ChipY-1-sy)*SQUARE + SQUARE/2, 10+ex*SQUARE + SQUARE/2, 10+(ChipY-1-ey)*SQUARE + SQUARE/2,"");
}
//gates are just the number
for (i=0;i<NumGates;i++)
{
sprintf(num,"%d",i);
myGui.drawText(10+gateX[i]*SQUARE + SQUARE/2, 10+(ChipY-1-gateY[i])*SQUARE + SQUARE/2, num,"");
}
//wait for keypress
if ( StepThru )
inkey = getchar();
}
//how many gates within this box ?
int getCapacity(int sx, int sy, int ex, int ey)
{
return ( (ex-sx+1)*(ey-sy+1)*GatesInSite );
}
//middle of partition
void adjustGatePosition ( int Partition, int sx, int sy, int ex, int ey )
{
int i=0;
for(i=0;i<NumGates;i++)
{
if ( gatePart[i] == Partition )
{
gateX[i] = sx + (ex-sx)/2;
gateY[i] = sy + (ey-sy)/2;
}
}
}
//check if partition gates exceeds capacity
int foundViolations ( int Partition, int Cut, int Capacity1, int Capacity2 )
{
int NumPart = 0;
int i;
//count gates
for (i=0;i<NumGates;i++)
{
if ( Cut == 1 )
{
if (( gatePart[i] == Partition ) && !tempPart1[i])
NumPart++;
}
else
{
if (( gatePart[i] == Partition ) && !tempPart2[i])
NumPart++;
}
}
//yes, violation
if ( NumPart > Capacity1 )
return 1;
//count again
NumPart = 0;
for (i=0;i<NumGates;i++)
{
if ( Cut == 1 )
{
if (( gatePart[i] == Partition ) && tempPart1[i])
NumPart++;
}
else
{
if (( gatePart[i] == Partition ) && tempPart2[i])
NumPart++;
}
}
//yes violation
if ( NumPart > Capacity2 )
return 1;
else
return 0;
}
//fixes capaccity violations.
//different algorithms for this purpose
//performance varies by benchmark
void fixCapacityViolations(int Partition, int Capacity1, int Capacity2)
{
int NumPart1=0;
int NumPart2=0;
int i, pick;
for(i=0;i<NumGates;i++)
{
if ( gatePart[i] == Partition )
NumPart1++;
else if ( gatePart[i] == (Partition+1))
NumPart2++;
}
if ( NumPart1 > (Capacity1*GatesInSite) )
{
while (NumPart1 > (Capacity1*GatesInSite))
{
pick = pickGate(Partition, NumPart1);
moveToPartition(pick, Partition+1);
NumPart1--;
NumPart2++;
}
}
else if ( NumPart2 > (Capacity2*GatesInSite) )
{
while (NumPart2 > (Capacity2*GatesInSite))
{
pick = pickGate(Partition+1, NumPart2);
moveToPartition(pick, Partition);
NumPart2--;
NumPart1++;
}
}
}
//pick which gate to move... this is pretty crucial
//described during constant initialization
int pickGate(int Partition, int NGates)
{
int i,j,arbit, least;
double minLen = 0.0, tempLen, tempMin;
switch ( CapacityFix )
{
case FIRST:
for ( i=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
return i;
case LAST:
for ( i=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
j=i;
return j;
case CONSTRAINED:
arbit = INT_MAX;
minLen = 0.0;
for(i=0,j=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
{
least = i; //ensures first gate is picked
for (j=0;j<GateArr[i].netsOnGate;j++)
{
if ( PadsPerNet[GateArr[i].List[j]-1] )
break;
if ((GateArr[i].netsOnGate < arbit) && (getGateLen(i) > minLen))
{
least = i;
minLen = getGateLen(i);
arbit = GateArr[i].netsOnGate;
}
}
}
return least;
case CONSTR_OPT:
//hybrid of CONSTRAINED and MOSTLEN
arbit = INT_MAX;
minLen = 0.0;
for(i=0,j=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
{
tempLen = getGateLen(i);
if ( Partition % 2 )
moveToPartition(i,Partition+1);
else
moveToPartition(i,Partition-1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
tempMin = tempLen - getGateLen(i);
least = i; //ensures first gate is picked
for (j=0;j<GateArr[i].netsOnGate;j++)
{
if ( PadsPerNet[GateArr[i].List[j]-1] )
break;
if ((GateArr[i].netsOnGate <= arbit) && (tempMin >= minLen))
{
least = i;
minLen = tempMin;
arbit = GateArr[i].netsOnGate;
}
}
if ( Partition % 2 )
moveToPartition(i,gatePart[i]-1);
else
moveToPartition(i,gatePart[i]+1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
}
return least;
case LEASTLEN:
for(i=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
{
tempLen = getGateLen(i);
if ( Partition % 2 )
moveToPartition(i,Partition+1);
else
moveToPartition(i,Partition-1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
tempMin = tempLen - getGateLen(i);
if ( minLen == 0.0 )
{
minLen = tempMin;
least = i;
}
else
{
if ( tempMin <= minLen )
{
least = i;
minLen = tempMin;
}
}
if ( Partition % 2 )
moveToPartition(i,gatePart[i]-1);
else
moveToPartition(i,gatePart[i]+1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
}
return least;
case MOSTLEN:
for(i=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
{
tempLen = getGateLen(i);
if ( Partition % 2 )
moveToPartition(i,Partition+1);
else
moveToPartition(i,Partition-1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
tempMin = tempLen - getGateLen(i);
if ( minLen == 0.0 )
{
minLen = tempMin;
least = i;
}
else
{
if ( tempMin >= minLen )
{
least = i;
minLen = tempMin;
}
}
if ( Partition % 2 )
moveToPartition(i,gatePart[i]-1);
else
moveToPartition(i,gatePart[i]+1);
for(j=0;j<GateArr[i].netsOnGate;j++)
computeWireLen(2,GateArr[i].List[j]-1);
}
return least;
}
}
//move to this partition
void moveToPartition(int Gate, int Partition)
{
int i;
for(i=0;i<NumGates;i++)
if (gatePart[i] == Partition)
{
gateX[Gate] = gateX[i];
gateY[Gate] = gateY[i];
gatePart[Gate] = Partition;
break;
}
}
//get length of all nets connected to this gate
double getGateLen(int Gate)
{
int i;
double sum = 0.0;
for (i=0;i<GateArr[Gate].netsOnGate;i++)
{
sum += netLen[GateArr[Gate].List[i]-1];
}
return sum;
}
//compute the wire delay of individual nets
void computeWireDelay(void)
{
int i;
netList *netPtr;
int FanOut;
for (i=0;i<NumNets;i++)
{
netPtr = &(NetArr[i]);
FanOut = 0;
while (netPtr)
{
FanOut++;
netPtr = netPtr->next;
}
FanOut--; //one input
netDelay[i] = K1 * netLen[i] * netLen[i] + K2 * (float)FanOut * netLen[i];
}
}
//get the fanout of this net - how many gates/pads is it
//connected to ?
int getFanout ( int Net )
{
netList *netTemp = &NetArr[Net];
int i = 0;
while ( netTemp )
{
i++;
netTemp = netTemp->next;
}
return i;
}
//write output file
void writeOutput(void)
{
int i,j;
FILE *OpFP = fopen(OpFileName,"w");
double Delay;
for (i=0;i<NumGates;i++)
{
fprintf(OpFP,"%d %d %d\n",i+1,gateX[i],gateY[i]);
fflush(OpFP);
}
for(i=0;i<NumNets;i++)
{
fprintf(OpFP,"%d %f %f\n",i+1,netLen[i],netDelay[i]);
fflush(OpFP);
}
for(i=0;i<NumPinsConnNets;i++)
{
fprintf(OpFP,"%d %d %d\n",i+1, PinConnList[i].xSite, PinConnList[i].ySite);
fflush(OpFP);
}
for(i=0;i<NumTimingPaths;i++)
{
Delay = 0.0;
for (j=0;j<TimingPaths[i].NumObjects;j++)
{
if (!(j%2))
Delay += 1.0;
else
Delay += netDelay[j-1];
}
fprintf(OpFP,"%d %f\n",i+1,Delay);
fflush(OpFP);
}
fclose(OpFP);
}
//quadratic placement...
//incomplete
void quadPlace(int Partition, int sx, int sy, int ex, int ey)
{
SMatrixPtr C_;
VMatrixPtr Bx_, By_;
double EdgeWeight;
netList *netTemp, *Temp1;
int i,j;
int Gate;
int count=0;
int GateCount = 0;
for (i=0;i<NumGates;i++)
if ( gatePart[i] == Partition )
GateCount++;
C_ = new SMatrix ((size_t)NumGates, "C_");
Bx_ = new VMatrix ((size_t)NumGates, "Bx_");
By_ = new VMatrix ((size_t)NumGates, "By_");
for (i=0;i<NumNets;i++)
{
EdgeWeight = 2/((double)getFanout(i));
netTemp = &NetArr[i];
while( netTemp )
{
if ( ( netTemp->Type == PIN ) || ( ( netTemp->Type == GATE ) && ( gatePart[netTemp->GateID] != Partition ) ) )
{
netTemp = netTemp->next;
continue;
}
Gate = netTemp->GateID;
Temp1 = netTemp->next;
C_->Add(Gate+1, Gate+1, getGateLen(Gate) );
while (Temp1)
{
if ( gatePart[Temp1->GateID] == Partition )
{
C_->Add(Gate+1, 1+Temp1->GateID, -1*computeLen(Gate,Temp1->GateID) );
}
else
{
Bx_->Add(Gate+1, EdgeWeight * min (ex, gateX[Temp1->GateID]));
By_->Add(Gate+1, EdgeWeight * min (ey, gateY[Temp1->GateID]));
}
Temp1 = Temp1->next;
}
netTemp = netTemp->next;
}
padList *padTemp = &PadArr[i];
for(j=0;j<PadsPerNet[i];j++)
{
Bx_->Add(Gate+1,int(EdgeWeight * min (ex, max(sx, PinConnList[padTemp->PadID-1].xSite))) );
By_->Add(Gate+1,int(EdgeWeight * min (ey, max(sy, PinConnList[padTemp->PadID-1].ySite))) );
padTemp = padTemp->next;
}
}
VMatrixPtr XSolve = CGISolve(C_, Bx_, SOLVE_ACCURACY);
VMatrixPtr YSolve = CGISolve(C_, By_, SOLVE_ACCURACY);
for (i=0;i<NumGates;i++)
{
int x, y;
x = int(sx+(double)(ex-sx)*XSolve->Get((size_t)(i+1)));
y = int(sy+(double)(ey-sy)*YSolve->Get((size_t)(i+1)));
printf("gate %d: ",i);
printf("%d %d\n", int(sx+(double)(ex-sx)*XSolve->Get((size_t)(i+1))), int(sy+(double)(ey-sy)*YSolve->Get((size_t)(i+1))));
gateX[i] = x;
gateY[i] = y;
}
}
//initialize partitions
//for multiple iterations
void initParts(void)
{
int i;
for (i=0;i<NumGates;i++)
{
gatePart[i] = 0;
}
}
//this just didnt work well..
//swap the gates with max wirelengths
void greedySwap(int Partition)
{
int i;
int Max1=-1, Max2=-1;
double Len1, Len2, Len;
int tempX, tempY;
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == Partition )
{
Len = getGateLen(i);
if ( Max1 == -1 )
{
Max1 = i;
Len1 = Len;
}
else
if ( Len > Len1 )
{
Len1 = Len;
Max1 = i;
}
}
else if ( gatePart[i] == (Partition+1) )
{
Len = getGateLen(i);
if ( Max2 == -1 )
{
Max2 = i;
Len2 = Len;
}
else
if ( Len > Len2 )
{
Len2 = Len;
Max2 = i;
}
}
}
tempX = gateX[Max1];
tempY = gateY[Max1];
gateX[Max1] = gateX[Max2];
gateY[Max1] = gateY[Max2];
gateX[Max2] = tempX;
gateY[Max2] = tempY;
gatePart[Max1] = Partition+1;
gatePart[Max2] = Partition;
}
//another failure... variable partitioning,
//cut anywhere, not at the middle alone
//status: unused
double getRatio(int Partition, int Cut)
{
//wont stand up to k-way...
int i, part1=0, part2=0;
double Ratio;
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == Partition )
{
if ( Cut == 1 )
{
if ( !tempPart1[i] )
part1++;
else
part2++;
}
else
{
if ( !tempPart2[i] )
part1++;
else
part2++;
}
}
}
//return the ratio of the first partition
//to the total... helps set the cutline
//properly
Ratio = ((double)part1)/(part1+part2);
printf("ratio:%f part1:%d, total:%d\n", Ratio, part1, part1+part2);
return Ratio;
}
//distance between gates
double computeLen(int Gate1, int Gate2)
{
int x1=gateX[Gate1], x2=gateX[Gate2];
int y1=gateY[Gate1], y2=gateY[Gate2];
if (( x1 == x2 ) && ( y1 == y2 ))
return G;
return (max(x1,x2) - min(x1,x2) + max(y1,y2) - min(y1,y2))*G;
}
//violations in 4-way partitions are fixed in this function
void fixQuadViolations(int Partition, int sx, int sy, int ex, int ey, int Area1, int Area2, int Area3, int Area4)
{
int i;
//gates per quadrant
int NumPart1=0, NumPart2=0, NumPart3=0, NumPart4=0;
//total allowed capacity per quadrant
int Weight1 = Area1*GatesInSite, Weight2 = Area2*GatesInSite;
int Weight3 = Area3*GatesInSite, Weight4 = Area4*GatesInSite;
//gate to move
int victim;
//middle of quadcut
int mx = sx + (ex-sx)/2, my = sy + (ey-sy)/2;
int dx, dy;
//find gate Counts...
for (i=0;i<NumGates;i++)
{
if ( gatePart[i] == Partition )
NumPart1++;
else if ( gatePart[i] == (Partition+1))
NumPart2++;
else if ( gatePart[i] == (Partition+2) )
NumPart3++;
else if ( gatePart[i] == (Partition+3) )
NumPart4++;
}
while (1)
{
//loop serves to fix all imbalances...
if ( NumPart1 <= Weight1 )
{
if ( NumPart2 <= Weight2 )
{
if ( NumPart3 <= Weight3 )
{
if ( NumPart4 <= Weight4 )
{
return;
}
else
{
while ( NumPart4 > Weight4 )
{
victim = pickGate(Partition+3, NumPart4);
//where do I move it to ?
//'move to nearest legal quadrant'
//not sure this is the best thing
//to do but what the heck
//its giving great results!
dx = gateX[victim] - mx;
dy = gateX[victim] - my;
if ( dx < dy )
{
//should go into 3 if legal
if ( (NumPart3+1) <= Weight3 )
{
moveToPartition(victim, Partition+2);
NumPart4--;
NumPart3++;
}
else
{
if ( (NumPart2+1) < Weight2 )
{
moveToPartition(victim,Partition+1);
NumPart4--;
NumPart2++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition);
NumPart4--;
NumPart1++;
}
}
}
else
{
//should go into 2 if legal
if ( (NumPart2+1) <= Weight2 )
{
moveToPartition(victim, Partition+1);
NumPart4--;
NumPart2++;
}
else
{
if ( (NumPart3+1) < Weight3 )
{
moveToPartition(victim,Partition+2);
NumPart4--;
NumPart3++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition);
NumPart4--;
NumPart1++;
}
}
}
}
}
}
else
{
while ( NumPart3 > Weight3 )
{
victim = pickGate(Partition+2,NumPart3);
dx = gateX[victim] - mx;
dy = gateX[victim] - my;
if ( dx < dy )
{
//should go into 3 if legal
if ( (NumPart4+1) <= Weight4 )
{
moveToPartition(victim, Partition+3);
NumPart3--;
NumPart4++;
}
else
{
if ( (NumPart1+1) < Weight1 )
{
moveToPartition(victim,Partition);
NumPart3--;
NumPart1++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+1);
NumPart3--;
NumPart2++;
}
}
}
else
{
//should go into 2 if legal
if ( (NumPart1+1) <= Weight1 )
{
moveToPartition(victim, Partition);
NumPart3--;
NumPart1++;
}
else
{
if ( (NumPart4+1) < Weight4 )
{
moveToPartition(victim,Partition+3);
NumPart3--;
NumPart4++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+1);
NumPart3--;
NumPart2++;
}
}
}
}
}
}
else
{
while ( NumPart2 > Weight2 )
{
victim = pickGate(Partition+1,NumPart2);
dx = gateX[victim] - mx;
dy = gateX[victim] - my;
if ( dx < dy )
{
//should go into 3 if legal
if ( (NumPart1+1) <= Weight1 )
{
moveToPartition(victim, Partition);
NumPart2--;
NumPart1++;
}
else
{
if ( (NumPart4+1) < Weight4 )
{
moveToPartition(victim,Partition+3);
NumPart2--;
NumPart4++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+2);
NumPart2--;
NumPart3++;
}
}
}
else
{
//should go into 2 if legal
if ( (NumPart4+1) <= Weight4 )
{
moveToPartition(victim, Partition+3);
NumPart2--;
NumPart4++;
}
else
{
if ( (NumPart1+1) < Weight1 )
{
moveToPartition(victim,Partition);
NumPart2--;
NumPart1++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+2);
NumPart2--;
NumPart3++;
}
}
}
}
}
}
else
{
while ( NumPart1 > Weight1 )
{
victim = pickGate(Partition,NumPart1);
dx = gateX[i] - mx;
dy = gateX[i] - my;
if ( dx < dy )
{
//should go into 3 if legal
if ( (NumPart2+1) <= Weight2 )
{
moveToPartition(victim, Partition+1);
NumPart1--;
NumPart2++;
}
else
{
if ( (NumPart3+1) < Weight3 )
{
moveToPartition(victim,Partition+2);
NumPart1--;
NumPart3++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+3);
NumPart1--;
NumPart4++;
}
}
}
else
{
//should go into 2 if legal
if ( (NumPart3+1) <= Weight3 )
{
moveToPartition(victim, Partition+2);
NumPart1--;
NumPart3++;
}
else
{
if ( (NumPart2+1) < Weight2 )
{
moveToPartition(victim,Partition+1);
NumPart1--;
NumPart2++;
}
else // no check needed, gotta work
{
moveToPartition(victim,Partition+3);
NumPart1--;
NumPart4++;
}
}
}
}
}
}
}
C++ to HTML Conversion by ctoohtml