DIRECTORY
Rope USING [ROPE, Concat, Equal, Cat],
Convert USING[RopeFromInt],
RefTab USING [Create, Pairs, EachPairAction, Fetch, Store, Delete, GetSize],
IO,
Imager USING[Context, MaskStroke, PathProc, SetXY, ShowRope, SetGray],
List USING [AList, Assoc, PutAssoc],
CCG,
IP,
IPCB,
IPConstants USING[Black],
IPParams USING[ChDefaultWidth, ChMinLSeparation, ChMinLength],
IPCTG;
IPCTGImpl:
CEDAR
PROGRAM
IMPORTS RefTab, Imager, IO, Rope, Convert, List, CCG, IP, IPParams, IPCB
EXPORTS IPCTG = BEGIN OPEN IPCTG;
HorChPrefix: Rope.ROPE = "h";
VerChPrefix: Rope.ROPE = "v";
ChannelTypeMismatch: PUBLIC ERROR = CODE;
CyclicConstraints: PUBLIC ERROR [negCh, posCh: Channel] = CODE;
Create:
PUBLIC
PROC[]
RETURNS[Ref] ={
RETURN[NEW[Rep ← [horCCG: CCG.Create[], verCCG: CCG.Create[], extConstraintsTable: RefTab.Create[]]]]
}; --Create--
DescribeSelf:
PUBLIC
PROC[ctg: Ref, stream:
IO.
STREAM] ={
pI: EachIntersectionAction ={stream.PutF[" %g %g", IO.rope[i.ch.name], IO.int[i.type]]}; --pI--
pCh1: EachChannelAction ={
stream.PutF["%g\t%g %g %g\n", IO.rope[ch.name], IO.rope[SELECT ch.type FROM hor => "hor", ver => "ver", ENDCASE => ERROR], IO.int[ch.coord], IO.int[ch.width]];
}; --pCh1--
pCh2: EachChannelAction ={
stream.PutF["%g\t", IO.rope[ch.name]];
[] ← pI[End[ch, neg]];
[] ← pI[End[ch, pos]];
stream.PutF[" ("];
[] ← Intersections[ch, neg, pI];
stream.PutF[") "];
stream.PutF["("];
[] ← Intersections[ch, pos, pI];
stream.PutF[")\n"];}; --pCh2--
pCon: RefTab.EachPairAction
-- [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- = {
quit ← FALSE;
stream.PutF["\n%g\t[", IO.rope[NARROW[key, Channel].name]];
FOR l: List.AList ←
NARROW[val], l.rest
UNTIL l =
NIL
DO
stream.PutF[" %g %g", IO.rope[NARROW[l.first.key, Channel].name], IO.int[NARROW[l.first.val, REF INT]^]];
ENDLOOP;
stream.PutF["]"];
}; -- pCon--
stream.PutF["\nBeginCTG"];
stream.PutF["\n%g \t--Number of channels\n", IO.int[ctg.horCCG.Size + ctg.verCCG.Size]];
stream.PutF["%g %g\t--Horzontal & Vertical channel name counters\n", IO.int[ctg.horChNameCounter], IO.int[ctg.verChNameCounter]];
[] ← Channels[ctg, pCh1];
[] ← Channels[ctg, pCh2];
stream.PutF["\n%g \t--Number of external constraints", IO.int[ctg.extConstraintsTable.GetSize]];
[] ← ctg.extConstraintsTable.Pairs[pCon];
stream.PutF["\nEndCTG\n"];
}; --DescribeSelf--
ReconstructSelf:
PUBLIC
PROC[stream:
IO.
STREAM]
RETURNS [ctg: Ref] ={
makeCh:
PROC ={
name: Rope.ROPE ← stream.GetID;
type: ChType ← IF Rope.Equal[stream.GetID, "ver"] THEN ver ELSE hor;
coord: INT ← stream.GetInt;
width: NAT ← stream.GetInt;
[] ← CreateChannel[ctg, type, width, coord, name]}; --makeCh--
makeI:
PROC
RETURNS [Intersection] ={
RETURN [NEW[IntersectionRep ← [GetChannel[ctg, stream.GetID], stream.GetInt]]]}; --makeI--
makeIs:
PROC
RETURNS [
LIST
OF Intersection] ={
lHd, lTl: LIST OF Intersection;
lHd← lTl ← CONS[NIL, NIL];
[] ← stream.GetCedarTokenRope;
WHILE stream.PeekChar # ')
DO
lTl.rest ← CONS[NEW[IntersectionRep ← [GetChannel[ctg, stream.GetID], stream.GetInt]], NIL];
lTl ← lTl.rest;
ENDLOOP;
[] ← stream.GetCedarTokenRope;
RETURN [lHd.rest]}; --makeIs--
chCount: NAT ← stream.GetInt;
ctg ← Create[];
ctg.horChNameCounter ← stream.GetInt;
ctg.verChNameCounter ← stream.GetInt;
--Create the channels--
THROUGH [0..chCount)
DO
makeCh
ENDLOOP;
THROUGH [0..chCount)
DO
ch: Channel ← GetChannel[ctg, stream.GetID];
negEnd: Intersection ← makeI[];
posEnd: Intersection ← makeI[];
negSide: LIST OF Intersection ← makeIs[];
posSide: LIST OF Intersection ← makeIs[];
IPCB.SetBoundary[ch.boundary, negEnd, posEnd, negSide, posSide];
ENDLOOP;
--Create the external constraints--
THROUGH [0..stream.GetInt)
DO
ch: Channel ← GetChannel[ctg, stream.GetID];
[] ← stream.GetCedarTokenRope;
WHILE stream.PeekChar # ']
DO
nCh: Channel ← GetChannel[ctg, stream.GetID];
wt: NAT ← stream.GetInt;
SetExternalConstraint[ctg, ch, nCh, wt]
ENDLOOP;
[] ← stream.GetChar;
ENDLOOP;
IF NOT Rope.Equal[stream.GetID, "EndCTG"] THEN ERROR;
};--ReconstructSelf--
CheckSelf:
PUBLIC
PROC[ctg: Ref] ={
pCh: EachChannelAction ={
cbRef: IPCB.Ref ← ch.boundary;
IF NOT ch.chNode IN [1..Size[ctg, ch.type]] THEN ERROR;
IF GetChannel[ctg, ch.name] # ch THEN ERROR;
IF cbRef.owner # ch THEN ERROR;
IPCB.CheckSelf[cbRef];
BEGIN
negIs: LIST OF IPCB.IntersectionNode ← NIL;
pI: IPCB.EachINodeAction ={negIs ← CONS[iNd, negIs]};
IPCB.IntersectionNodes[cbRef, pI, neg];
FOR l:
LIST
OF
IPCB.IntersectionNode ← negIs, l.rest
UNTIL l =
NIL
DO
i: Intersection ← l.first.intersection;
iNd: IPCB.IntersectionNode;
SELECT i.type
FROM
IPCB.TNeg => IF IPCB.GetINode[cbRef, i.ch, pos] # NIL THEN ERROR;
IPCB.Cross =>
IF (iNd ←
IPCB.GetINode[cbRef, i.ch, pos]) =
NIL
THEN
ERROR
ELSE {
IF iNd.dual = l.first.dual OR iNd.intersection = i THEN ERROR}; --Different copies--
ENDCASE => ERROR;
ENDLOOP;
END;
BEGIN
pCo: EachComponentAction ={IF co = NIL OR co.active THEN NULL ELSE ERROR}; --pCo--
[] ← IPCB.Components[ch.boundary, neg, pCo];
[] ← IPCB.Components[ch.boundary, pos, pCo];
END;
}; --pCh--
[] ← Channels[ctg, pCh];}; --CheckSelf--
DestroySelf:
PUBLIC
PROC[ctg: Ref] ={
p: EachChannelAction ={IPCB.Destroy[ch.boundary]; ch.boundary ← NIL}; --p--
[] ← Channels[ctg, p]
}; -- DestroySelf--
PaintSelf:
PUBLIC
PROC[ctg: Ref, context: Imager.Context, xOffset, yOffset:
REAL ← 0.0, scaleFactor:
REAL ← 1.0, showChName:
BOOL ←
TRUE] ={
p: EachChannelAction ={PaintChannel[ch, context, xOffset, yOffset, scaleFactor, showChName]}; --p--
[] ← Channels[ctg, p];
}; --PaintSelf--
CreateChannel:
PUBLIC
PROC[ctg: Ref, type: ChType, width:
NAT ← IPParams.ChDefaultWidth, coord:
INT ← 0, name: Rope.
ROPE ←
NIL]
RETURNS[ch: Channel] ={
SELECT type
FROM
hor => {
ch ← NEW[ChannelRep ← [type: type, name: name, slack:, width: width, coord: coord]];
ch.chNode ← ctg.horCCG.CreateNode[ch];
IF name = NIL THEN {ch.name ← Rope.Concat[HorChPrefix, Convert.RopeFromInt[ctg.horChNameCounter ← ctg.horChNameCounter.SUCC]]}
};
ver => {
ch ← NEW[ChannelRep ← [type: type, name: name, slack:, width: width, coord: coord]];
ch.chNode ← ctg.verCCG.CreateNode[ch];
IF name = NIL THEN {ch.name ← Rope.Concat[VerChPrefix, Convert.RopeFromInt[ctg.verChNameCounter ← ctg.verChNameCounter.SUCC]]};
};
ENDCASE => ERROR;
ch.boundary ← IPCB.Create[ch];
RETURN[ch]}; --CreateChannel--
DeActivateChannel:
PUBLIC
PROC[ctg: Ref, ch: Channel] ={
p: CCG.CleanUpChsProc ={NARROW[chToMove, Channel].chNode ← ch.chNode}; --p--
SELECT ch.type
FROM
hor => ctg.horCCG.DestroyNode[ch.chNode, p];
ver => ctg.verCCG.DestroyNode[ch.chNode, p];
ENDCASE => ERROR;
ch.chNode ← 0;
ch.boundary ← NIL;
}; --DeActivateChannel--
ReActivateChannel:
PUBLIC
PROC[ctg: Ref, ch: Channel] ={
ch.boundary ← IPCB.Create[ch];
SELECT ch.type
FROM
hor => ch.chNode ← ctg.horCCG.CreateNode[ch];
ver => ch.chNode ← ctg.verCCG.CreateNode[ch];
ENDCASE => ERROR;
}; --ReActivateChannel--
Size:
PUBLIC
PROC[ctg: Ref, type: ChType]
RETURNS[
NAT] ={
SELECT type
FROM
hor => {RETURN [ctg.horCCG.Size]};
ver => {RETURN [ctg.verCCG.Size]};
ENDCASE => ERROR;}; --Size--
GetChannel:
PUBLIC
PROC[ctg: Ref, name: Rope.
ROPE, raiseError:
BOOL ←
TRUE]
RETURNS[channel: Channel ←
NIL] ={
findName: EachChannelAction = {
IF Rope.Equal[name, ch.name] THEN {channel ← ch; quit ← TRUE}}; -- findName--
[] ← Channels[ctg, findName];
IF channel = NIL AND raiseError THEN ERROR IP.Error[missingRegistration, Rope.Cat[name, " is not a channel name"]];
}; --GetChannel--
DirectedChannels:
PUBLIC PROC[ctg: Ref, p: EachChannelAction, chType: ChType]
RETURNS[
BOOL] = {
-- Enumerate all channels of chType (hor or ver) or until p returns true. Returns TRUE <=> p returns FALSE ON ALL Channels.
p1: CCG.EachChAction ={RETURN[p[NARROW[ch]]]}; --p1--
SELECT chType
FROM
hor => {RETURN[ctg.horCCG.Chs[p1]]};
ver => {RETURN[ctg.verCCG.Chs[p1]]};
ENDCASE => ERROR;
};
Channels:
PUBLIC
PROC[ctg: Ref, p: EachChannelAction, horChsFirst:
BOOL ←
TRUE]
RETURNS[
BOOL] ={
p1: CCG.EachChAction ={RETURN[p[NARROW[ch]]]}; --p1--
IF horChsFirst
THEN {IF ctg.horCCG.Chs[p1] THEN RETURN[ctg.verCCG.Chs[p1]]}
ELSE {IF ctg.verCCG.Chs[p1] THEN RETURN[ctg.horCCG.Chs[p1]]};
RETURN [FALSE]
}; --Channels--
ConstrainChannels:
PUBLIC
PROC[ctg: Ref, negCh, posCh: Channel, wt:
INT] = {
ConstrainChannels0[ctg, negCh, posCh, wt + negCh.width/2 + posCh.width/2]}; --ConstrainChannels--
ConstrainChannels0:
PUBLIC
PROC [ctg: Ref, negCh, posCh: Channel, wt:
INT] ={
IF negCh.type # posCh.type THEN ERROR ChannelTypeMismatch;
SELECT negCh.type
FROM
hor => {ctg.horCCG.ConstrainNodes[negCh.chNode, posCh.chNode, wt]};
ver => {ctg.verCCG.ConstrainNodes[negCh.chNode, posCh.chNode, wt]};
ENDCASE => ERROR;}; --ConstrainChannels0--
SetExternalConstraint:
PUBLIC
PROC[ctg: Ref, negCh, posCh: Channel, wt:
INT] ={
found: BOOL;
val: REF;
alist: List.AList;
IF negCh.type # posCh.type THEN ERROR ChannelTypeMismatch;
SELECT negCh.type
FROM
hor => {IF ctg.horCCG.CyclicConstrainp[negCh.chNode, posCh.chNode] THEN ERROR CyclicConstraints[negCh, posCh]};
ver => {IF ctg.verCCG.CyclicConstrainp[negCh.chNode, posCh.chNode] THEN ERROR CyclicConstraints[negCh, posCh]};
ENDCASE => ERROR;
[found, val] ← ctg.extConstraintsTable.Fetch[negCh];
IF found
THEN {
refWt: REF;
alist ← NARROW[val];
IF (refWt ← List.Assoc[posCh, alist]) # NIL AND NARROW[refWt, REF INT]^ >= wt THEN RETURN};
[] ← ctg.extConstraintsTable.Store[negCh, List.PutAssoc[posCh, NEW[INT←wt], alist]];
}; --SetExternalConstraint--
ClearExternalConstraints:
PUBLIC
PROC[ctg: Ref, negCh: Channel, posCh: Channel ←
NIL] ={
found: BOOL;
val: REF;
alist: List.AList;
IF posCh = NIL THEN {[] ← ctg.extConstraintsTable.Delete[negCh]; RETURN};
IF negCh.type # posCh.type THEN ERROR ChannelTypeMismatch;
[found, val] ← ctg.extConstraintsTable.Fetch[negCh];
IF found
THEN {
alist ← NARROW[val];
[]← ctg.extConstraintsTable.Store[negCh, List.PutAssoc[posCh, NIL, alist]];
}
}; --ClearExternalConstraints --
ClearAllExternalConstraints:
PUBLIC
PROC[ctg: Ref] ={
ctg.extConstraintsTable ← RefTab.Create[];
}; -- ClearAllExternalConstraints--
AddTopologicalConstraints:
PUBLIC
PROC[ctg: Ref] ={
p: EachChannelAction ={
IF End[ch, pos].type #
IPCB.TEnd
OR End[ch, neg].type #
IPCB.TEnd
THEN {
IF End[ch, pos].type * End[ch, neg].type =
IPCB.LNeg
AND NoIntersection[ch, pos]
AND NoIntersection[ch, neg]
THEN{
ConstrainChannels0[ctg, End[ch, neg].ch, End[ch, pos].ch, IPParams.ChMinLength]} ELSE {
SELECT End[ch, pos].type
FROM
IPCB.Cross => NULL;
IPCB.LNeg => IF NthIntersection[ch, pos, -1] # NIL AND NthIntersection[ch, pos, -1].type # IPCB.Cross THEN ConstrainChannels0[ctg, NthIntersection[ch, pos, -1].ch, End[ch, pos].ch, IPParams.ChMinLSeparation];
IPCB.LPos => IF NthIntersection[ch, neg, -1] # NIL AND NthIntersection[ch, neg, -1].type # IPCB.Cross THEN ConstrainChannels0[ctg, NthIntersection[ch, neg, -1].ch, End[ch, pos].ch, IPParams.ChMinLSeparation];
ENDCASE => ERROR;
SELECT End[ch, neg].type
FROM
IPCB.Cross => NULL;
IPCB.LNeg => IF NthIntersection[ch, pos, 1] # NIL AND NthIntersection[ch, pos, 1].type # IPCB.Cross THEN ConstrainChannels0[ctg, End[ch, neg].ch, NthIntersection[ch, pos, 1].ch, IPParams.ChMinLSeparation];
IPCB.LPos => IF NthIntersection[ch, neg, 1] # NIL AND NthIntersection[ch, neg, 1].type # IPCB.Cross THEN ConstrainChannels0[ctg, End[ch, neg].ch, NthIntersection[ch, neg, 1].ch, IPParams.ChMinLSeparation];
ENDCASE => ERROR;}
}}; --p--
}; --AddTopologicalConstraints --
AddExternalConstraints:
PUBLIC
PROC[ctg: Ref] = {
EachConstraintIter: RefTab.EachPairAction
-- [key: RefTab.Key, val: RefTab.Val] RETURNS [quit: BOOLEAN] -- = {
negCh: Channel ← NARROW[key];
quit ← FALSE;
FOR alist: List.AList ←
NARROW[val], alist.rest
UNTIL alist =
NIL
DO
posCh: Channel ← NARROW[alist.first.key];
wt: INT ← NARROW[alist.first.val, REF INT]^;
ConstrainChannels0[ctg, negCh, posCh, wt];
ENDLOOP;
}; --EachConstraintIter --
[] ← ctg.extConstraintsTable.Pairs[EachConstraintIter];
}; -- AddExternalConstraints--
RefreshAllConstraints:
PUBLIC
PROC [ctg: Ref] ={
ctg.verCCG.ResetAllNodes;
ctg.horCCG.ResetAllNodes;
}; --RefreshAllConstraints--
ComputeGeometry:
PUBLIC
PROC[ctg: Ref, xPosition, yPosition:
INT, horPosSense, verPosSense:
BOOL ←
TRUE]={
AssignCoordAndComputeSlack: EachChannelAction = {
posSense:
BOOL ←
SELECT ch.type
FROM
hor => horPosSense,
ver => verPosSense,
ENDCASE => ERROR;
chGraph:
CCG.Ref ←
SELECT ch.type
FROM
hor => ctg.horCCG,
ver => ctg.verCCG,
ENDCASE => ERROR;
ch.slack.neg ← chGraph.NodePosition[ch.chNode, pos]; --ch.slack.neg <= ch.slack.pos
ch.slack.pos ← chGraph.NodePosition[ch.chNode, neg];
ch.coord ← chGraph.NodePosition[ch.chNode, IF posSense THEN pos ELSE neg];
chGraph.ResetNode[ch.chNode];
}; --AssignCoordAndComputeSlack --
hCCG: CCG.Ref = ctg.horCCG;
vCCG: CCG.Ref = ctg.verCCG;
hRoot, vRoot: CCG.NodeIndex;
hRoot ← hCCG.FindRoot[pos];
vRoot ← vCCG.FindRoot[pos];
hCCG.SetNodePosition[hRoot, pos, yPosition];
vCCG.SetNodePosition[vRoot, pos, xPosition];
hCCG.PosAssignNodePosition[hRoot];
vCCG.PosAssignNodePosition[vRoot];
hRoot ← hCCG.FindRoot[neg];
vRoot ← vCCG.FindRoot[neg];
hCCG.SetNodePosition[hRoot, neg, hCCG.NodePosition[hRoot, pos]];
vCCG.SetNodePosition[vRoot, neg, vCCG.NodePosition[vRoot, pos]];
hCCG.NegAssignNodePosition[hRoot];
vCCG.NegAssignNodePosition[vRoot];
[] ← Channels[ctg, AssignCoordAndComputeSlack];
}; --ComputeGeometry --
GetBoundingChannels:
PUBLIC
PROC[ctg: Ref]
RETURNS [southMost, eastMost, northMost, westMost: Channel] ={
hCCG: CCG.Ref = ctg.horCCG;
vCCG: CCG.Ref = ctg.verCCG;
hRoot, vRoot: CCG.NodeIndex;
hRoot ← hCCG.FindRoot[pos];
vRoot ← vCCG.FindRoot[pos];
southMost ← NARROW[hCCG.GetCh[hRoot]];
westMost ← NARROW[vCCG.GetCh[vRoot]];
hRoot ← hCCG.FindRoot[neg];
vRoot ← vCCG.FindRoot[neg];
northMost ← NARROW[hCCG.GetCh[hRoot]];
eastMost ← NARROW[vCCG.GetCh[vRoot]];
}; --GetBoundingChannels--
PaintChannel:
PUBLIC
PROC [ch: Channel, context: Imager.Context, xOffset, yOffset:
REAL ← 0.0, scaleFactor:
REAL ← 1.0, showName:
BOOL ←
TRUE] ={
negCh: Channel ← End[ch, neg].ch;
posCh: Channel ← End[ch, pos].ch;
Imager.SetGray[context, IPConstants.Black];
SELECT ch.type
FROM
ver => {x:
REAL ← xOffset + (ch.coord * scaleFactor);
-- Imager.SetXYI[context, x, yOffset + (negCh.coord * scaleFactor)];
-- Imager.DrawTo[context, x, yOffset + (posCh.coord * scaleFactor)];
path: Imager.PathProc ~ {
moveTo[[x, yOffset + (negCh.coord * scaleFactor)]];
lineTo[[x, yOffset + (posCh.coord * scaleFactor)]];
};
Imager.MaskStroke[context, path];
Imager.SetXY[context, [x, yOffset + (negCh.coord + posCh.coord) *scaleFactor/2]];
IF showName THEN Imager.ShowRope[context, ch.name];
};
hor => {y:
REAL ← yOffset + (ch.coord * scaleFactor);
-- Imager.SetXYI[context, xOffset + (negCh.coord * scaleFactor), y];
-- Graphics.DrawTo[context, xOffset + (posCh.coord * scaleFactor), y];
path: Imager.PathProc ~ {
moveTo[[xOffset + (negCh.coord * scaleFactor), y]];
lineTo[[xOffset + (posCh.coord * scaleFactor), y]];
};
Imager.MaskStroke[context, path];
Imager.SetXY[context, [xOffset + (negCh.coord + posCh.coord) *scaleFactor/ 2, y]];
IF showName THEN Imager.ShowRope[context, ch.name];
};
ENDCASE => ERROR};--PaintChannel--
--##################--
End:
PUBLIC
PROC[ch: Channel, which: Side]
RETURNS[Intersection] = {
RETURN[IPCB.End[ch.boundary, which]]}; --End --
NthComponent: PUBLIC PROC [ch: Channel, which: Side, n: INT] RETURNS[Component] = {RETURN[IPCB.NthComponent[ch.boundary, which, n]]};
NthIntersection:
PUBLIC
PROC[ch: Channel, which: Side, n:
INT]
RETURNS[Intersection] = {
RETURN[IPCB.NthIntersection[ch.boundary, which, n]]
}; -- NthIntersection--
NoIntersection:
PUBLIC PROC[ch: Channel, which: Side]
RETURNS[
BOOL] = {
RETURN[IPCB.NoIntersection[ch.boundary, which]]
}; -- NoIntersection--
NoComponent:
PUBLIC PROC[ch: Channel, which: Side]
RETURNS[
BOOL] = {
RETURN[IPCB.NoComponent[ch.boundary, which]]
}; -- NoComponent--
Components: PUBLIC PROC[ch: Channel, which: Side, p: EachComponentAction] RETURNS[BOOL] = {RETURN[IPCB.Components[ch.boundary, which, p]]}; -- Components--
Intersections: PUBLIC PROC[ch: Channel, which: Side, p: EachIntersectionAction] RETURNS[BOOL] = {RETURN[IPCB.Intersections[ch.boundary, which, p]];}; -- Intersections--
##################--
END.