DIRECTORY
OrderedRefArray,
IP,
IPCB,
IPCoTab,
IPCTG,
IPTop,
IPTopOps,
IPBasicOps,
IPTopOpRecs,
IPPlaceKit;

IPPlaceKitImpl: CEDAR PROGRAM
IMPORTS OrderedRefArray, IP, IPBasicOps, IPCoTab, IPCTG, IPCB, IPTopOps
EXPORTS IPPlaceKit = BEGIN OPEN IPPlaceKit;

Execute: PUBLIC PROC[top: IPTop.Ref, trial: REF] ={
WITH trial SELECT FROM
gr: REF GrowRec => [] _ IPTopOps.Grow[top, gr.co, gr.chToSplit, gr.negBnd, gr.posBnd, TRUE];
com: IPTopOpRecs.RComposite => IPTopOps.Redo[top, com];
ENDCASE => ERROR IP.Error[callingError, "Execute doesnt know about this type"]
}; --Execute

CreateChEnumData: PUBLIC PROC[refCh: IPCTG.Channel] RETURNS [ChEnumData] ={
RETURN [NEW[ChEnumDataRep _ [IPCB.End[refCh.boundary, neg].ch, IPCB.End[refCh.boundary, pos].ch, refCh.boundary.negSideHd, refCh.boundary.posSideHd]]]};--CreateChEnumData

GetChSucc: PUBLIC PROC[data: ChEnumData, getXOnce: BOOL _ TRUE] RETURNS [IPCTG.Channel] ={
countXOnce: BOOL _ TRUE;
chSucc: IPCTG.Channel _ data.nextCh;
negSide: LIST OF REF IP.IntersectionNodeRep _ data.negSidePtr;
posSide: LIST OF REF IP.IntersectionNodeRep _ data.posSidePtr;
IF negSide = NIL OR posSide = NIL 
THEN {
IF chSucc = NIL THEN RETURN [NIL];
IF negSide # NIL THEN {data.nextCh _ negSide.first.intersection.ch; data.negSidePtr _ data.negSidePtr.rest};
IF posSide # NIL THEN {data.nextCh _posSide.first.intersection.ch; data.posSidePtr _ data.posSidePtr.rest};

IF negSide = NIL AND  posSide = NIL THEN {
IF chSucc = data.finalCh 
THEN data.nextCh _ NIL
ELSE data.nextCh _ data.finalCh;};
}
ELSE {
negCh: IPCTG.Channel _ negSide.first.intersection.ch;
posCh: IPCTG.Channel _ posSide.first.intersection.ch;
IF IPCTG.GetCoord[negCh] > IPCTG.GetCoord[posCh] 
THEN {data.nextCh _ posCh; data.posSidePtr _ data.posSidePtr.rest}
ELSE {data.nextCh _ negCh; data.negSidePtr _ data.negSidePtr.rest};
IF getXOnce AND negCh = posCh THEN data.posSidePtr _ data.posSidePtr.rest;
};  --endIF
RETURN [chSucc];
};--GetChSucc

AllChGrowSites: PUBLIC PROC[refCh: IPCTG.Channel, action: EachChGrowSiteAction] ={
negBnd: ChEnumData _ CreateChEnumData[refCh];
posBnd: ChEnumData _ CreateChEnumData[refCh];
negCh, posCh: IPCTG.Channel;
DO
negCh _ GetChSucc[negBnd, TRUE];
IF negCh = NIL THEN EXIT;
posBnd^ _ negBnd^;
DO
next, quit: BOOL;
posCh _ GetChSucc[posBnd, TRUE];
IF posCh = NIL THEN EXIT; 
[next, quit] _ action[negCh, posCh];
IF quit THEN RETURN;
IF next THEN EXIT;
ENDLOOP;
ENDLOOP;
}; --AllChGrowSites

ChGrowSites: PUBLIC PROC[refCh: IPCTG.Channel, whichSide: IP.PolarityTypes, action: EachChGrowSiteAction]= {
filterSites: EachChGrowSiteAction ={
IF ~IPCTG.ArmOn[refCh, negBnd, whichSide] OR ~IPCTG.ArmOn[refCh, posBnd, whichSide]
THEN RETURN;
[next, quit] _ action[negBnd, posBnd]
}; --filterSites

AllChGrowSites[refCh, filterSites]
}; --ChGrowSites

AllTopGrow1Sites: PUBLIC PROC[top: IPTop.Ref, action: EachTopGrow1SiteAction] ={
eachComp: IPCoTab.EachComponentAction = {
FOR corner: IPCoTab.CornerTypes IN [sw..nw] UNTIL quit DO
IF CoCornerFree[co, corner] THEN quit _ action[co, corner]
ENDLOOP;
}; --eachComp
IPCoTab.Components[top.coTab, eachComp]
}; --AllTopGrow1Sites

SideComponents: PUBLIC PROC[refCh: IPCTG.Channel, which: IPCTG.Side, action: IPCoTab.EachComponentAction] ={
filteredAction: IPCTG.EachComponentAction ={
IF co # NIL THEN RETURN [action[co]]}; --filteredAction
[] _ IPCTG.Components[refCh, which, filteredAction]
}; --SideComponents

SideChannels: PUBLIC PROC[refCh: IPCTG.Channel, which: IPCTG.Side, action: IPCTG.EachChannelAction] ={
intersectionAction: IPCTG.EachIntersectionAction ={
RETURN [action[i.ch]]
}; --intersectionAction
[] _ IPCTG.Intersections[refCh, which, intersectionAction]
}; --SideChannels
NonActiveComps: PUBLIC PROC [top: IPTop.Ref, action: IPCoTab.EachComponentAction] ={
nonActiveComps: IPCoTab.EachComponentAction ={
IF IPCoTab.CoActive[co] 
THEN NULL
ELSE RETURN [action[co]]
}; --nonActiveComps
IPCoTab.AllComponents[top.coTab, nonActiveComps];
}; --NonActiveComps

CountComps: PUBLIC PROC[comps: Components] RETURNS [count: NAT _ 0] ={
UNTIL comps = NIL DO
count _ count.SUCC;
comps _ comps.rest;
ENDLOOP
}; --CountComps

CopyCompsHead: PUBLIC PROC[comps: Components, head: NAT] RETURNS [compHd, compRest: Components] ={
IF head = 0 OR comps = NIL 
THEN RETURN [NIL, comps]
ELSE {
compTl: Components _ LIST[comps.first];
compHd _ compTl;
DO
head _ head.PRED;
comps _ comps.rest;
IF comps = NIL OR head = 0 THEN {compRest _ comps; EXIT};
compTl.rest _ LIST[comps.first];
compTl _ compTl.rest
ENDLOOP;
};
}; --CopyCompsHead

GetComponents: PUBLIC PROC[remTrack: LIST OF REF] RETURNS [comps: Components _ NIL] ={
getCo: PROC[step: REF] ={
WITH step SELECT FROM
s1: IPTopOpRecs.FRShrink1 => comps _ CONS[s1.co, comps];
rc: IPTopOpRecs.FRRemoveCo => comps _ CONS[rc.co, comps];
cm: IPTopOpRecs.RComposite => getCo[cm.first];
ENDCASE => 
ERROR IP.Error[callingError, "GetComponents doesn't know about this type"];
}; --getCo
UNTIL remTrack = NIL DO
getCo[remTrack.first];
remTrack _ remTrack.rest
ENDLOOP;

}; --GetComponents

GetComponentArea: PUBLIC PROC[comp: IPCoTab.Component, minusUsedCorners, minusFreeCorners: BOOL _ TRUE] RETURNS [area: INT] ={
xDim, yDim: INT;

[xDim, yDim] _ IPCoTab.GetDim[comp];
area _ (xDim * yDim);

FOR corner: IP.CornerTypes IN [sw..nw] DO
cornerChs: IPCoTab.CornerChannels _ IPCoTab.GetCornerChs[comp, corner];
cornerSp: IPCoTab.CornerSpace _ IPCoTab.GetCornerSp[comp, corner];
areaDecr: INT;
IF cornerSp = NIL 
THEN areaDecr _ 0
ELSE {
[xDim, yDim] _ cornerSp^;
areaDecr _ (xDim * yDim);
};
IF cornerChs = NIL 
THEN {
IF minusFreeCorners THEN area _ (area - areaDecr)
}
ELSE {
IF minusUsedCorners THEN area _ (area - areaDecr)
}
ENDLOOP;

}; --GetComponentArea

CoCornerFree: PUBLIC PROC[co: IPCoTab.Component, corner: IPCoTab.CornerTypes] RETURNS [BOOL] ={
RETURN [IPCoTab.GetCornerSp[co, corner] # NIL AND (IPCoTab.GetCornerChs[co, corner] = NIL OR  ~IPCoTab.CoActive[co])]
}; --CoCornerBitible

ComputeZType: PUBLIC PROC[corner: IPCoTab.CornerTypes, refChType: IPCTG.ChType] RETURNS [IP.PolarityTypes] ={
SELECT refChType FROM
hor => RETURN [IF corner = sw OR corner = ne THEN pos ELSE neg];
ver => RETURN [IF corner = sw OR corner = ne THEN neg ELSE pos];
ENDCASE => ERROR;
}; --ComputeZType



CompactComp0: PUBLIC PROC[
top: IPTop.Ref,
comp: IPCoTab.Component,
direction: IPCTG.ChType,
placeEval: PlaceEvaluator, -- Simply use as an eval function no prunning
results: OrderedRefArray.Ref,
resultsAfter: NAT,
keepInitTrack: BOOL _ TRUE, --Provided for convenience
formZOk: BOOL _ TRUE -- This means okay to formz during compaction
] ={
directnFlipped: IPCTG.ChType _ IPBasicOps.OTFlip[direction];
addTrack: PROC ={
value: INT _ placeEval[top, NIL].value;
OrderedRefArray.Insert[results, IPTopOps.GetTrack[top, resultsAfter], value]
}; --addTrack
biteCorner: PROC[corner: IPCoTab.CornerTypes] ={
IF IPCoTab.GetCornerSp[comp, corner] # NIL THEN {
refCh: IPCTG.Channel _ IPCoTab.GetPrinCh[comp, IPBasicOps.CTResolveFor[corner, directnFlipped]];
chSide: IPCTG.Side _ IPBasicOps.CTDirectnFor[corner, direction];
tToLAction: IPCTG.EachChannelAction ={
[] _ IPTopOps.TtoL[top, comp, ch, IPBasicOps.CTDirectnFor[corner, directnFlipped],  TRUE];
addTrack[];
IF corner # nw THEN biteCorner[corner.SUCC];
[] _ IPTopOps.Undo1[top];
};--tToLAction
fZAction: IPCoTab.EachComponentAction ={
cornerDiag: IPCoTab.CornerTypes _ IPBasicOps.CTDiag[corner];
IF IPTopOps.FormZChk[top, co, comp, ComputeZType[corner, directnFlipped]]
THEN {
[] _ IPTopOps.FormZ[top, co, comp, ComputeZType[corner, directnFlipped], TRUE];
addTrack[];
IF corner # nw THEN biteCorner[corner.SUCC];
[] _ IPTopOps.Undo1[top];

};
}; --fZAction
SideChannels[refCh, chSide, tToLAction];
IF formZOk THEN SideComponents[refCh, chSide, fZAction];
}; --endIf
IF corner # nw THEN biteCorner[corner.SUCC];
};--biteCorner
IF keepInitTrack THEN addTrack[];
biteCorner[sw];
}; --CompactComp0

CompactComp1: PUBLIC PROC[
top: IPTop.Ref,
comp: IPCoTab.Component,
direction: IPCTG.ChType,
placeEval: PlaceEvaluator, -- Simply use as an eval function no prunning
results: OrderedRefArray.Ref, -- improvement added here
resultsAfter: NAT,
keepInitTrack: BOOL _ TRUE --Provided for convenience
] ={
eachNeighborAction: IPCoTab.EachComponentAction = {
CompactComp0[top, comp, direction, placeEval, results, resultsAfter, FALSE, FALSE]
}; --eachNeighborAction

CompactComp0[top, comp, direction, placeEval, results, resultsAfter, keepInitTrack, TRUE];
SELECT direction FROM
hor => {
SideComponents[IPCoTab.GetPrinCh[comp, west], neg, eachNeighborAction];
SideComponents[IPCoTab.GetPrinCh[comp, east], pos, eachNeighborAction];
direction _ IPBasicOps.OTFlip[direction];
SideComponents[IPCoTab.GetPrinCh[comp, south], neg, eachNeighborAction];
SideComponents[IPCoTab.GetPrinCh[comp, north], pos, eachNeighborAction];
};
ver => {
SideComponents[IPCoTab.GetPrinCh[comp, south], neg, eachNeighborAction];
SideComponents[IPCoTab.GetPrinCh[comp, north], pos, eachNeighborAction];
direction _ IPBasicOps.OTFlip[direction];
SideComponents[IPCoTab.GetPrinCh[comp, west], neg, eachNeighborAction];
SideComponents[IPCoTab.GetPrinCh[comp, east], pos, eachNeighborAction];
};
ENDCASE => ERROR;
}; --CompactComp1

FTPerturbTop: PUBLIC PROC[  --FT = FlipT
top: IPTop.Ref,
placeEval: PlaceEvaluator, -- Simply use as an eval function no prunning
depth: NAT,
results: OrderedRefArray.Ref,
resultsAfter: NAT,
keepInitTrack: BOOL _ TRUE --Provided for convenience
] ={
whichEnd: IP.PolarityTypes;
eachTrialAction: EachChGrowSiteAction ={
IF IPTopOps.FlipTChk[top, negBnd, posBnd, whichEnd] THEN {
[] _ IPTopOps.FlipT[top, negBnd, posBnd, whichEnd, TRUE];
FTPerturbTop[top, placeEval, depth.PRED, results, resultsAfter, TRUE];
[] _ IPTopOps.Undo1[top]
};
IF IPTopOps.FlipTChk[top, posBnd, negBnd, whichEnd] THEN {
[] _ IPTopOps.FlipT[top, posBnd, negBnd, whichEnd, TRUE];
FTPerturbTop[top, placeEval, depth.PRED, results, resultsAfter, TRUE];
[] _ IPTopOps.Undo1[top]
};
}; --eachTrackAction
eachChAction:  IPCTG.EachChannelAction = {
whichEnd _ neg; -- info used above
ChGrowSites[ch, neg, eachTrialAction];
whichEnd _ pos; -- info used above
ChGrowSites[ch, pos, eachTrialAction];
}; --eachChAction
IF keepInitTrack THEN OrderedRefArray.Insert[results, IPTopOps.GetTrack[top, resultsAfter], placeEval[top, NIL].value];
IF depth > 0 THEN [] _ IPCTG.Channels[top.ctg, eachChAction]
};--FTPerturbTop

END.



D--File: IPPlaceKitImpl.mesa
Last Edited by: CSChow, January 25, 1985 12:43:58 pm PST
-- Operation to execute a trial
--Trials Generating Primitives: : 
--(0) chSucc = NIL
--(1) negSide # NIL

--(2) posSide # NIL
--(3) Both NILs 
-- negCh = posCh => IPCTG.GetCoord[negCh] = IPCTG.GetCoord[posCh]
-- => data.negSidePtr has been incremented. 
-- So if getXOnce then need to increment data.posSidePtr 

-- Useful routines
--(1) Compute area of outline
--(2) Subtract area of corners

--High level routines
--(1) Apply compaction to comp
-- Perhaps should do prunning, but how??
Κυ˜Jš
œ™J™8J˜š
Οk	˜	J˜J˜Jšœ
˜J˜Jšœ
˜J˜Icode˜	K˜Kš
œ˜Kš
œ˜—J˜šœœ
˜Jšœ*œœ˜GJšœœ
œ˜+J˜K™šΟnœœ
œœ˜3šœœ
˜KšœœOœ˜\Kš
œ7˜7Kšœœ
œ;˜N—KšœΟc	˜—J˜KšœŸœ™"š
žœœ
œœ
œ˜KKšœœœœ
žœQŸ˜ͺ
—K˜šž	œœ
œœœœœ˜ZKšœœœ
˜Kšœœ˜$Kš	œ	œ
œ
œ
œ'˜>Kš	œ	œ
œ
œ
œ'˜>šœœ
œœ
˜"šœ˜Kš
œ™Kš
œ
œ
œ
œœ˜"K™Kšœœ
œW˜lK™Kš
Ÿ™Kšœœ
œV˜kK˜Kš
œ™š
œœ
œœ
œ˜*šœ˜Kšœ˜Kšœ˜"——Kš
œ
˜
—šœ˜Kšœœ)˜5Kšœœ)˜5šœ
œœ˜1Kšœ>˜BKšœ?˜C—šœ
œœ(˜JKšœœœ™AKš
œ,™,Kš
œ9™9—KšœŸ˜——Kšœ
˜KšœŸ˜
—K˜šžœœ
œœ*˜RKš
œ-˜-Kš
œ-˜-Kšœœ	˜š
˜Kšœœ˜ Kšœ	œ
œ
œ
˜Kš
œ˜š
˜Kšœœ
˜Kšœœ˜ Kšœ	œ
œ
œ˜Kš
œ$˜$Kšœœ
œ
˜Kšœœ
œ
˜Kšœ
˜—Kšœ
˜—KšœŸ˜—J˜š
žœœ
œœœ0˜lš
œ$˜$šœœ!œœ ˜SKšœ
œ
˜—Kš
œ%˜%KšœŸ
˜—K˜Kš
œ"˜"KšœŸ
˜—K˜šžœœ
œ3˜Pš
œ)˜)šœœ
œ˜9Kšœœ˜:Kš
˜—KšœŸ
˜
—K˜'KšœŸ˜—J˜š
žœœ
œœœ.˜lš
œ,˜,Kš	œœ
œ
œŸ˜7—Kšœœ)˜3JšœŸ˜—J˜šžœœ
œœœœ˜fšœœ˜3Kšœ˜JšœŸ˜—Jšœœ0˜:JšœŸ˜—J™J™šžœœ
œ9˜Tš
œ.˜.šœ˜Kšœ
˜	Kšœ
œ
˜—KšœŸ˜—Kš
œ1˜1KšœŸ˜—K˜š
ž
œœ
œœ	œ˜Fšœ	œ
˜Kšœœ
˜K˜Kš
˜—KšœŸ˜—K˜š
ž
œœ
œœœ"˜bšœ
œ	œ
˜Kšœ
œœ˜šœ˜Kšœœ˜'Kš
œ˜š
˜Kšœœ
˜K˜Kš
œ	œ
œœœ˜9Kšœœ˜ Kš
œ˜Kšœ
˜—K˜——KšœŸ˜—K˜šž
œœ
œœ
œ
œœœ˜Všœœœ˜šœœ
˜Kšœ%œ˜8Kšœ&œ˜9K˜.šœ˜Kšœ
œ
Οbœ=˜K——KšœŸ˜
—šœœ
˜Kš
œ˜Kš
œ˜Kš
˜—K˜KšœŸ˜—K˜šžœœ>œœœœ˜~Jšœœ
˜J˜J™Jš
œ$˜$Jš
œ˜J˜J™šœ	œ
œ
˜)Jš
œG˜GJš
œB˜BJšœ
œ
˜šœœ
˜Kšœ
˜šœ˜Kš
œ˜Kš
œ˜Kš
œ˜——šœ
œ
˜šœ˜Kšœœ˜1Kš
œ
˜
—šœ˜Kšœœ˜1K˜
——Jšœ
˜—J˜KšœŸ˜—K˜š
žœœ
œ4œœ˜_Kš
œ$œ
œ%œ
œ˜uKšœŸ˜—K˜šžœœ
œ)œ	œœ˜mšœ˜Kš	œ
œ
œ
œœ˜@Kšœœœ
œ
œœ˜@Kšœœ
˜—KšœŸ˜—K˜K™K™K˜K˜šžœœ
œ
˜K˜Kš
œ˜Kšœœ˜KšœŸ-˜HKš
œ˜Kšœ˜Kšœœœ
Ÿ˜6Kšœ	œœ
Ÿ-˜BKš
œ˜Kšœœ'˜<šœ
œ˜Kšœœœ˜'Kš
œL˜LKšœŸ
˜
—šœœ ˜0šœ%œ
œ˜1KšœœT˜`Kšœœ3˜@šœœ˜&KšœTœ˜ZKš
œ˜Kšœœœ˜,K˜KšœŸ˜—š
œ(˜(Kš
œ<˜<šœG˜Išœ˜KšœIœ˜OKš
œ˜Kšœ
œœ˜,K˜K˜Kš
œ˜——KšœŸ
˜
—Kš
œ(˜(Kšœ	œ)˜8KšœŸ˜
—Kšœ
œœ˜,KšœŸ˜—Kšœœ˜!Kš
œ˜KšœŸ˜—K˜šžœœ
˜K˜Kš
œ˜Kšœœ˜KšœŸ-˜HKšœŸ˜7Kšœ˜Kšœœœ
Ÿ˜5Kš
œ˜š
œ3˜3KšœEœœ
˜RKšœŸ˜—K˜K™KšœTœ˜Zšœ˜˜K˜GK˜GKš
œ)˜)K˜HK˜HK˜—˜K˜HK˜HKš
œ)˜)K˜GK˜GK˜—Kšœœ
˜—KšœŸ˜—K˜šžœœŸ˜(K˜KšœŸ-˜HKšœœ
˜Kš
œ˜Kšœ˜Kšœœœ
Ÿ˜5Kš
œ˜Kšœ
œ˜š
œ(˜(K™(šœ2œ˜:Kšœ3œ˜9Kšœ#œœ˜FKš
œ˜Kš
œ˜—šœ2œ˜:Kšœ3œ˜9Kšœ#œœ˜FKš
œ˜Kš
œ˜—KšœŸ˜—šœœ˜*KšœŸ˜"Kš
œ&˜&KšœŸ˜"Kš
œ&˜&KšœŸ˜—KšœœVœ	˜wKšœ
œœ ˜<KšœŸ˜—K˜Kšœ
˜K˜K˜—J˜—…—(f7Ÿ