DIRECTORY
Rope,
IO,
FS,
Imager,
RatNums,
EuclideanGraphs;

EuclideanGraphsImpl: CEDAR PROGRAM
IMPORTS IO, FS, RatNums
EXPORTS EuclideanGraphs

= BEGIN OPEN RN: RatNums, EuclideanGraphs;

vertexIndex: PUBLIC CARDINAL; -- count of vertices allocated


MakePointFromRatNums: PUBLIC PROC[x1, y1: RN.RatNum] RETURNS [p: Point] = {
p _ [x: x1, y: y1 ];
RETURN[ p ];
};

MakePointFromReals: PUBLIC PROC[x1, y1: REAL] RETURNS [p: Point] = {
p _ [x: RN.RatNumFromREAL[x1], y: RN.RatNumFromREAL[y1] ];
RETURN[ p ];
};

ImagerVecFromPoint: PUBLIC PROC[p: Point] RETURNS [q: Imager.VEC] = {
q _ [ RN.RatNumToREAL[p.x], RN.RatNumToREAL[p.y] ];
RETURN[ q ];
};

PointEqual: PUBLIC PROC[p, q: Point] RETURNS [BOOLEAN] = {
RETURN[ RN.RatNumEqual[p.x, q.x] AND RN.RatNumEqual[ p.y, q.y ] ];
};

VerticalEdge: PUBLIC PROC[ p, q: Point ] RETURNS[BOOLEAN] = {
RETURN[ RN.RatNumEqual[p.x, q.x] ];
};

DistanceSquare: PUBLIC PROC[ p, q: Point ] RETURNS [d: RN.RatNum] = {
deltax, deltay: RN.RatNum;
deltax _ RN.RatNumSubtract[ q.x, p.x];
deltay _ RN.RatNumSubtract[ q.y, p.y];
RETURN[ RN.RatNumAdd[
RN.RatNumMultiply[ deltax, deltax ], RN.RatNumMultiply[ deltay, deltay ]
] ]
}; 

PointLineTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointLineRelation _ ONLINE ] = {
relation: RN.RatNumRelation;
IF PointEqual[start, end] THEN ERROR;
relation _ RN.RatNumCompare[
RN.RatNumMultiply[
RN.RatNumSubtract[ end.x , start.x ], 
RN.RatNumSubtract[ test.y , start.y]
],
RN.RatNumMultiply[
RN.RatNumSubtract[ test.x , start.x ],
RN.RatNumSubtract[ end.y , start.y ]
] 
];
SELECT relation FROM
ratLess => RETURN[ RIGHTOFLINE ];
ratEqual => RETURN[ ONLINE ];
ratGreater => RETURN[ LEFTOFLINE ];
ENDCASE;
};

PointDirectedEdgeTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointDirectedEdgeRelation _ LEFTOFEDGE] = {
pointLineRelation: PointLineRelation;
firstbool, secondbool: BOOL;
pointLineRelation _ PointLineTest[start, end, test];
SELECT pointLineRelation FROM
LEFTOFLINE => RETURN[ LEFTOFEDGE ];
RIGHTOFLINE => RETURN[ RIGHTOFEDGE ];
ONLINE => {
IF PointEqual[start, test] THEN RETURN[ EQUALSTART ];
IF PointEqual[end, test] THEN RETURN[ EQUALEND ];
firstbool _ RN.RatNumGreater[ DistanceSquare[start, end], DistanceSquare[start, test] ];
secondbool _ RN.RatNumGreater[ DistanceSquare[end, start], DistanceSquare[end, test] ];
IF firstbool AND secondbool THEN RETURN[BETWEENSTARTEND];
IF RN.RatNumGreater[ DistanceSquare[test, start], DistanceSquare[test, end] ] THEN RETURN[AFTEREND] ELSE RETURN[BEFORESTART];
};
ENDCASE;
};

IntersectLines: PUBLIC PROC [start1, end1, start2, end2: Point] RETURNS [intersection: Point] = {
slope1, slope2, intercept1, intercept2, xIntersect, yIntersect: RN.RatNum;
vertical1: BOOL _ VerticalEdge[start1, end1];
vertical2: BOOL _ VerticalEdge[start2, end2];
IF vertical1 AND vertical2 THEN ERROR;
IF NOT vertical1 THEN slope1 _ RN.RatNumDivide[
RN.RatNumSubtract[ end1.y, start1.y ],
RN.RatNumSubtract[ end1.x, start1.x ]
];
IF NOT vertical2 THEN slope2 _ RN.RatNumDivide[
RN.RatNumSubtract[ end2.y, start2.y ],
RN.RatNumSubtract[ end2.x, start2.x ]
];
IF NOT vertical1 THEN intercept1 _ RN.RatNumSubtract[ start1.y, RN.RatNumMultiply[ slope1, start1.x ] ];
IF NOT vertical2 THEN intercept2 _ RN.RatNumSubtract[ start2.y, RN.RatNumMultiply[ slope2, start2.x ] ];
IF NOT vertical1 AND NOT vertical2 THEN {  -- neither edge vertical
xIntersect _ RN.RatNumDivide[
RN.RatNumSubtract[intercept2, intercept1 ],
RN.RatNumSubtract[slope1, slope2 ]
];
yIntersect _ RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ];
}
ELSE IF vertical1 THEN { -- 1st edge is vertical, 2nd edge not vertical
xIntersect _ start1.x;
yIntersect _ RN.RatNumAdd[ intercept2, RN.RatNumMultiply[ slope2, xIntersect] ]
}
ELSE { -- IF vertical2, i.e. 1st edge not vertical, 2nd edge is vertical
xIntersect _ start2.x;
yIntersect _ RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ]
};
intersection _ MakePointFromRatNums[xIntersect, yIntersect];
};

BiasedEdgeCompare: PUBLIC PROC [outerStart, outerEnd, innerStart, innerEnd: Vertex] RETURNS [outcome: BiasedEdgeCompareStatus _ Disjoint] = {
firstRelation, secondRelation: PointDirectedEdgeRelation;
intersection: Point;
firstRelation _ PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerEnd.coordinates];
SELECT firstRelation FROM
BEFORESTART, AFTEREND, RIGHTOFEDGE => RETURN[Disjoint];
EQUALSTART => RETURN[OuterEndEqInnerStart];
BETWEENSTARTEND => RETURN[OuterEndInInner];
EQUALEND => RETURN[OuterEndEqInnerEnd];
LEFTOFEDGE => {
intersection _ IntersectLines[outerStart.coordinates, outerEnd.coordinates, innerStart.coordinates, innerEnd.coordinates];
secondRelation _ PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, intersection];
SELECT secondRelation FROM
BEFORESTART, AFTEREND => RETURN[Disjoint];
EQUALSTART => RETURN[InnerStartInOuter];
BETWEENSTARTEND => RETURN[ProperIntersection];
EQUALEND => RETURN[InnerEndInOuter];
ENDCASE => ERROR;  -- intersection must be on the line [innerStart, innerEnd].
};
ENDCASE;
};

FindAdjacency: PUBLIC PROC[v, w: Vertex] RETURNS [vTow, wTov: Adjacency]= {
ahlv, ahlw: AdjacencyList;
ahlv _ v.adjacentVertices;
ahlw _ w.adjacentVertices;
WHILE ahlv.first.vertex # w DO
ahlv _ ahlv.rest;
ENDLOOP;
WHILE ahlw.first.vertex # v DO
ahlw _ ahlw.rest;
ENDLOOP;
RETURN[ ahlv.first, ahlw.first ];
};

CountAdjacencies: PUBLIC PROC[v: Vertex] RETURNS [number: CARDINAL] ~ {
adjacencies: AdjacencyList _ v.adjacentVertices;
adjHead: AdjacencyList _ v.adjacentVertices;
IF adjacencies = NIL THEN RETURN[0];
number _ 1;  adjacencies _ adjacencies.rest;
WHILE adjacencies # adjHead DO
number _ number + 1;
adjacencies _ adjacencies.rest;
ENDLOOP;
};

AdjacentVertices: PUBLIC PROC[v: Vertex] RETURNS [vertices: LIST OF Vertex] ~ {
adjacencies: AdjacencyList _ v.adjacentVertices;
adjHead: AdjacencyList _ v.adjacentVertices;
verticesLast: LIST OF Vertex;
IF adjacencies = NIL THEN RETURN[NIL];
verticesLast _ vertices _ LIST[adjacencies.first.vertex];  adjacencies _ adjacencies.rest;
WHILE adjacencies # adjHead DO
verticesLast.rest _ LIST[adjacencies.first.vertex];  verticesLast _ verticesLast.rest;
adjacencies_ adjacencies.rest;
ENDLOOP;
};

Adjacent: PUBLIC PROC[v, w: Vertex] RETURNS [BOOL] ~ {
adjacencies: AdjacencyList _ v.adjacentVertices;
adjHead: AdjacencyList _ v.adjacentVertices;
IF adjacencies = NIL THEN RETURN[FALSE];
IF adjacencies.first.vertex = w THEN RETURN[TRUE];
adjacencies _ adjacencies.rest;
WHILE adjacencies # adjHead DO
IF adjacencies.first.vertex = w THEN RETURN[TRUE];
adjacencies_ adjacencies.rest;
ENDLOOP;
RETURN[FALSE];
};

SetFigureVisitedValues: PUBLIC PROC[v: Vertex, visitedValue: BOOLEAN] = {
IF v = NIL THEN RETURN; -- no vertices 
IF v.adjacentVertices = NIL THEN { v.visited _ visitedValue; RETURN }; -- one vertex
SetFigureVisitedValuesSubr[v, visitedValue ]; -- two or more vertices
RETURN;
};

SetFigureVisitedValuesSubr: PROC[v: Vertex, visitedValue: BOOLEAN] = {
vAdjList: AdjacencyList _ v.adjacentVertices;
nextAdjacency: Adjacency;
lastVertex, nextVertex: Vertex;
done: BOOL _ FALSE;

v.visited _ visitedValue; -- record that have visited this vertex

lastVertex _ vAdjList.first.vertex; 
vAdjList _ vAdjList.rest;  -- shift past marker vertex (i.e. first iteration of loop begins after it)
done _ FALSE;
WHILE NOT done DO
nextAdjacency _ vAdjList.first;
nextVertex _ nextAdjacency.vertex;
IF nextVertex = lastVertex THEN done _ TRUE;  -- test for last vertex to be processed 
IF (nextVertex.visited # visitedValue) THEN SetFigureVisitedValuesSubr[ nextVertex, visitedValue]; -- Recursive call for w
vAdjList _ vAdjList.rest;
ENDLOOP;

RETURN;
};

FindVertexForPoint: PUBLIC PROC [v: EuclideanGraph, test: Point] RETURNS [w: Vertex] ~ {
visitedValue: BOOL;
currentDist: RN.RatNum;
IF v = NIL OR v.adjacentVertices = NIL THEN RETURN[v] -- no vertices 
ELSE {
visitedValue _ v.adjacentVertices.first.vertex.visited;
currentDist _ DistanceSquare[v.coordinates, test];
[w, currentDist] _ FindVertexForPointSubr[v, NOT visitedValue, test, v, currentDist]; -- specify toggling of visitedValue
RETURN[w];
};
};
FindVertexForPointSubr: PROC[v: Vertex, visitedValue: BOOL, test: Point, currentBest: Vertex, currentBestDist: RN.RatNum] RETURNS [best: Vertex, bestDist: RN.RatNum] = {
vAdjList: AdjacencyList _ v.adjacentVertices;
lastVertex, nextVertex:  Vertex;
vDist: RN.RatNum;
done: BOOL;

v.visited _ visitedValue; -- record that we've visited this vertex

vDist _ DistanceSquare[v.coordinates, test];
IF RN.RatNumLess[ vDist, currentBestDist] THEN {
currentBest _ v;
currentBestDist _ vDist
};

best _ currentBest;
bestDist _ currentBestDist;
lastVertex _ vAdjList.first.vertex; 
vAdjList _ vAdjList.rest;  -- shift past marker vertex (i.e. first iteration of loop begins after it)
done _ FALSE;
WHILE NOT done DO
nextVertex _ vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done _ TRUE;  -- test for last vertex to be processed 
IF (nextVertex.visited # visitedValue) THEN [best, bestDist] _ FindVertexForPointSubr[ nextVertex, visitedValue, test, best, bestDist]; 
vAdjList _ vAdjList.rest;
ENDLOOP;

RETURN;
};
TestEdgeOverlap: PUBLIC PROC [root, testEnd: Vertex] RETURNS [overlap: BOOL, overlappedVertex: Vertex _ NIL] ~ {
status: BracketingAdjacenciesRelation;
priorPosition, followingPosition: AdjacencyList;
[status, priorPosition, followingPosition] _ BracketingAdjacencies[root, testEnd.coordinates];
IF status = Overlaps THEN
RETURN[TRUE, priorPosition.first.vertex]
ELSE
RETURN[FALSE, NIL];
};

CreateVertex: PUBLIC PROC [point: Point, vertexData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newVertex: Vertex] ~ {
newVertex _ NEW[VertexRec _ [coordinates: point, index: vertexIndex, adjacentVertices: NIL, data: vertexData, visited: visitedValue] ];
vertexIndex _ vertexIndex + 1;
};
CreateEdge: PUBLIC PROC [endVertex: Vertex, edgeData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newAdjacency: Adjacency] ~ {
newAdjacency _ NEW[AdjacencyRec _ [vertex: endVertex, data: edgeData, visited: visitedValue] ];
};
AddEdge: PUBLIC PROC [root, adjacentVertex: Vertex, data: REF _ NIL, visitedValue: BOOL _ FALSE] ~ {
status: BracketingAdjacenciesRelation;
priorPosition, followingPosition, aList: AdjacencyList;
adjacency: Adjacency _ CreateEdge[adjacentVertex, data, visitedValue];
IF root.adjacentVertices = NIL THEN {
aList _ LIST[adjacency];
aList.rest _ aList; --- Make circular
root.adjacentVertices _ aList;
}
ELSE {
[status, priorPosition, followingPosition] _ BracketingAdjacencies[root, adjacentVertex.coordinates];
IF status = EqualRoot THEN ERROR;
priorPosition.rest _ LIST[adjacency];
priorPosition.rest.rest _ followingPosition;
root.adjacentVertices _ priorPosition;  -- this statement needed, but why??
};
};
DeleteEdge: PUBLIC PROC [root, adjacentVertex: Vertex] =  {
l, l1: AdjacencyList;
l1 _ root.adjacentVertices;
l _ l1.rest;
WHILE l.first.vertex # adjacentVertex DO
l1 _ l;
l _ l.rest;
ENDLOOP;
IF l=l1 THEN root.adjacentVertices _ NIL ELSE {
l1.rest _ l.rest;
root.adjacentVertices _ l1;
};
};

InsertVertexInEdges: PUBLIC PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex] ~ {
vTow, wTov: Adjacency;
z: Vertex _ CreateVertex[p, vertexData, v.visited];
[vTow, wTov] _ FindAdjacency[v, w];
AddEdge[z, w, vTow.data, vTow.visited];
DeleteEdge[v, w];
AddEdge[v, z, vTow.data, vTow.visited];
AddEdge[z, v, wTov.data, wTov.visited];
DeleteEdge[w, v];
AddEdge[w, z, wTov.data, wTov.visited];
RETURN[z];
};

SplitVertex: PUBLIC PROC [v, distinguishedAdjacentVertex: Vertex] RETURNS [newVertex: Vertex] ~ {
vAdj, vAdjHead: AdjacencyList;
fromV, toV: Adjacency;
newVertex _ CreateVertex[v.coordinates];
vAdj _ vAdjHead _ v.adjacentVertices;
vAdj _ vAdj.rest;
vAdjHead.rest _ NIL;  -- break circularity
v.adjacentVertices _ NIL;  -- reinitialize list of v's adjacencies to NIL
WHILE vAdj # NIL DO
fromV _ vAdj.first;
IF fromV.vertex = distinguishedAdjacentVertex THEN
AddEdge[v, distinguishedAdjacentVertex, fromV.data, fromV.visited]  -- restore edge
ELSE {
w: Vertex _ fromV.vertex;
ahlw: AdjacencyList _ w.adjacentVertices;
WHILE ahlw.first.vertex # v DO
ahlw _ ahlw.rest;
ENDLOOP;
toV _ ahlw.first;  -- edge from w to v
toV.vertex _ newVertex; -- now it's an edge from w to newVertex
AddEdge[newVertex, w, fromV.data, fromV.visited];
};
vAdj _ vAdj.rest
ENDLOOP;
};

MergeVertices: PUBLIC PROC [u, v: Vertex] ~ {
vAdj, vAdjHead: AdjacencyList;
fromV, toV: Adjacency;
w: Vertex;
ahlw: AdjacencyList;

vAdj _ vAdjHead _ v.adjacentVertices;
IF vAdj=NIL THEN RETURN; -- do nothing if v has no adjacencies
vAdj _ vAdj.rest;
vAdjHead.rest _ NIL;  -- break circularity
v.adjacentVertices _ NIL;  -- complete isolation of v (so it can be garbage collected)
WHILE vAdj # NIL DO
fromV _ vAdj.first;
w _ fromV.vertex;
ahlw _ w.adjacentVertices;
WHILE ahlw.first.vertex # v DO
ahlw _ ahlw.rest;
ENDLOOP;
toV _ ahlw.first;  -- edge from w to v
toV.vertex _ u; -- now it's an edge from w to u
AddEdge[u, w, fromV.data, fromV.visited];
vAdj _ vAdj.rest
ENDLOOP;
};
DeleteVertex: PUBLIC PROC [v: Vertex] ~ {
vAdj, vAdjHead: AdjacencyList;
w: Vertex;

vAdj _ vAdjHead _ v.adjacentVertices;
vAdj _ vAdj.rest;
vAdjHead.rest _ NIL;  -- break circularity
v.adjacentVertices _ NIL;  -- complete isolation of v (so it can be garbage collected)
WHILE vAdj # NIL DO
w _ vAdj.first.vertex;
DeleteEdge[w, v];
vAdj _ vAdj.rest
ENDLOOP;
};
SeparateVertices: PUBLIC PROC [v, w: Vertex] ~ {
DeleteEdge[v, w];
DeleteEdge[w, v];
};
BracketingAdjacencies: PUBLIC PROC[root: Vertex, test: Point] RETURNS [status: BracketingAdjacenciesRelation, priorPosition, followingPosition: AdjacencyList] ~ {
AngleType: TYPE = {Zero, Acute, Flat, Obtuse};
successiveAdjacencyAngle: AngleType;
getAdjacencyAngle, testOnPriorLine: PointDirectedEdgeRelation;
testToPrior, testToFollowing: PointLineRelation;
numAdjacencies: CARDINAL _ CountAdjacencies[root];
priorPosition _ root.adjacentVertices;
IF priorPosition = NIL THEN ERROR;  -- error if we're called with a vertex with no adjacencies
followingPosition _ priorPosition.rest;
FOR I:CARDINAL IN [1..numAdjacencies] DO
getAdjacencyAngle _ PointDirectedEdgeTest[priorPosition.first.vertex.coordinates, root.coordinates, followingPosition.first.vertex.coordinates];
SELECT getAdjacencyAngle FROM
BEFORESTART,  EQUALSTART, BETWEENSTARTEND  => successiveAdjacencyAngle _ Zero; -- one adjacency, or overlapping adjacencies present
AFTEREND  => successiveAdjacencyAngle _ Flat;
LEFTOFEDGE  => successiveAdjacencyAngle _ Acute;
RIGHTOFEDGE  => successiveAdjacencyAngle _ Obtuse;
ENDCASE => ERROR;  -- EQUALEND => following vertex = root
testToPrior _ PointLineTest[root.coordinates, priorPosition.first.vertex.coordinates, test];
testToFollowing _ PointLineTest[root.coordinates, followingPosition.first.vertex.coordinates, test];
SELECT testToPrior FROM
ONLINE => {
testOnPriorLine _ PointDirectedEdgeTest[root.coordinates, priorPosition.first.vertex.coordinates, test];
SELECT testOnPriorLine FROM
EQUALSTART  => RETURN[EqualRoot, NIL, NIL];
BEFORESTART  => SELECT successiveAdjacencyAngle FROM
Zero, Acute => NULL;
Flat => NULL; -- we'll pick up overlap with following vertex in next loop iteration. 
Obtuse =>  RETURN[Interior, priorPosition, followingPosition];
ENDCASE;
BETWEENSTARTEND, EQUALEND, AFTEREND  => RETURN[Overlaps, priorPosition, followingPosition];
ENDCASE => ERROR;   -- we're supposed to be ONLINE
};
RIGHTOFLINE => SELECT successiveAdjacencyAngle FROM
Zero => NULL; 
Acute => SELECT testToFollowing FROM
LEFTOFLINE => RETURN[Interior, priorPosition, followingPosition];
RIGHTOFLINE => NULL;
ONLINE => NULL;  -- ignore overlap with following vertex until next iteration when it has become prior 
ENDCASE;
Flat, Obtuse => RETURN[Interior, priorPosition, followingPosition];
ENDCASE;
LEFTOFLINE => SELECT successiveAdjacencyAngle FROM
Zero => NULL;
Acute, Flat => NULL;
Obtuse => SELECT testToFollowing FROM
LEFTOFLINE => RETURN[Interior, priorPosition, followingPosition];
RIGHTOFLINE => NULL;
ONLINE => NULL;  -- ignore overlap with following vertex until next iteration when it has become prior 
ENDCASE;
ENDCASE;
ENDCASE;
priorPosition _ followingPosition;  followingPosition _ followingPosition.rest;
ENDLOOP;
RETURN[Interior, priorPosition, followingPosition]; -- this statement should be reached if and only if the only adjacencies of root are one or more edges, which all overlap each other, and which do not overlap [root, test].
};

DumpGraph: PUBLIC PROC [v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, filename: Rope.ROPE, clientProc1, clientProc2: RopeFromRefProc _ NIL]  ~ {
visitedValue: BOOL;
out: IO.STREAM _ FS.StreamOpen[filename, $create];
IF v = NIL THEN { out.Close[]; RETURN }; -- no vertices 
IF v.adjacentVertices = NIL THEN { -- one vertex
out.PutF["\n%g: ", IO.int[v. index]];
out.PutF[" ( %g , %g )  []", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ];
}
ELSE { -- two or more vertices
visitedValue _ v.adjacentVertices.first.vertex.visited;
DumpGraphSubr[v, ropeFromEdgeData, NOT visitedValue, out, clientProc1, clientProc2]; -- specify toggling of visitedValue
};
out.PutChar['\n]; out.PutChar['.];
out.Close[];
RETURN;
};

DumpGraphSubr: PROC[v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, visitedValue: BOOL, out: IO.STREAM, clientProc1, clientProc2: RopeFromRefProc _ NIL] = {
vAdjList: AdjacencyList _ v.adjacentVertices;
lastVertex, nextVertex:  Vertex;
nextAdj: Adjacency;
dataRope: Rope.ROPE;
done: BOOL;

v.visited _ visitedValue; -- record that we've visited this vertex

out.PutF["\n%g: ", IO.int[v.index]];
out.PutF[" ( %g , %g )  [", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ];

lastVertex _ vAdjList.first.vertex; 
vAdjList _ vAdjList.rest;  -- shift past marker vertex (i.e. first iteration of loop begins after it)
done _ FALSE;
WHILE NOT done DO
nextAdj _ vAdjList.first;
nextVertex _ nextAdj.vertex;
IF nextVertex = lastVertex THEN done _ TRUE;  -- test for last vertex to be processed 
dataRope _ ropeFromEdgeData[nextAdj.data, clientProc1, clientProc2];
out.PutF[" ( %g , %g )  ", IO.int[nextVertex.index], IO.rope[dataRope] ];
vAdjList _ vAdjList.rest;
ENDLOOP;
out.PutChar[']];

lastVertex _ vAdjList.first.vertex; 
vAdjList _ vAdjList.rest;  -- shift past marker vertex (i.e. first iteration of loop begins after it)
done _ FALSE;
WHILE NOT done DO
nextVertex _ vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done _ TRUE;  -- test for last vertex to be processed 
IF (nextVertex.visited # visitedValue) THEN DumpGraphSubr[ nextVertex, ropeFromEdgeData, visitedValue, out, clientProc1]; 
vAdjList _ vAdjList.rest;
ENDLOOP;
RETURN;
};

ClientDataProc: IO.BreakProc =
{RETURN[SELECT char FROM
'   => sepr,
ENDCASE => other]};  -- get blank delimited rope

ReadIOGraphFromFile: PUBLIC PROC [filename: Rope.ROPE, edgeDataFromRope: EdgeDataFromRope, MessageStream: IO.STREAM, clientProc1, clientProc2: RefFromRopeProc _ NIL] RETURNS [iOGraph: IOGraph] ~ {
done: BOOL _ FALSE;
ratNumOK, doneAdj: BOOL;
dataRope: Rope.ROPE;
charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list
dataRead: REF;
indexRead, adjIndexRead: INT;
xRead, yRead: RN.RatNum;
ioAList: IOAdjacencyList;
ioVHandle: IOVertex;
iOAdjacency: IOAdjacency;
puncChar: CHAR;
in: IO.STREAM _ FS.StreamOpen[filename, $read];
iOGraph _ NIL;
[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '. THEN done _ TRUE;

WHILE NOT done DO

indexRead _ in.GetInt[ ];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ': THEN MessageStream.PutF["Colon expected"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
[ xRead, ratNumOK] _ RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[ yRead, ratNumOK] _ RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"];

[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"];

doneAdj _ FALSE;
ioAList _ NIL;
[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '] THEN doneAdj _ TRUE;

WHILE NOT doneAdj DO

[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
adjIndexRead _ in.GetInt[];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[]_ in.SkipWhitespace[];
[dataRope, charsSkipped ] _ in.GetTokenRope[ClientDataProc];
dataRead _ edgeDataFromRope[dataRope, clientProc1, clientProc2];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];

iOAdjacency _ NEW[IOAdjacencyRec _ [ vertex: adjIndexRead,  data: dataRead, visited: FALSE ]  ];
ioAList _ CONS[iOAdjacency , ioAList]; -- adjacencies in ioAList are in backwards (counterclockwise) order; will be put back in right order by GraphFromIOGraph.

[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '] THEN doneAdj _ TRUE;

ENDLOOP;

[ ] _ in.GetChar[ ]; -- toss right square bracket

ioVHandle _ NEW[ IOVertexRec _ [coordinates: MakePointFromRatNums[xRead, yRead], 
index: indexRead, adjacentVertices: ioAList ] ];
iOGraph _ CONS[ ioVHandle, iOGraph ];

[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '. THEN done _ TRUE;

ENDLOOP;

};

VertexVerifyIOGraph: PUBLIC PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [maxVertexIndex: CARDINAL _ 0] ~ {
VERTEXDATA: TYPE = { PRESENT, ADJACENCY, NOTPRESENT };
MAXFIGUREVERTICES: CARDINAL = 2000;  -- maximum number of vertices in figure for verifier.
done: BOOL _ FALSE;
ratNumOK, doneAdj: BOOL;
dataRope: Rope.ROPE;
charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list
indexRead, adjIndexRead: INT;
xRead, yRead: RN.RatNum;
puncChar: CHAR;
in: IO.STREAM _ FS.StreamOpen[filename, $read];
vertices:  ARRAY [1..MAXFIGUREVERTICES] OF VERTEXDATA _ ALL[ NOTPRESENT ];
I: INT;
minVertexIndex: CARDINAL _ MAXFIGUREVERTICES;  -- minimum vertex index seen

[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '. THEN done _ TRUE;

WHILE NOT done DO

indexRead _ in.GetInt[ ];
vertices[ indexRead ] _ PRESENT;
IF indexRead < minVertexIndex THEN minVertexIndex _ indexRead;
IF indexRead > maxVertexIndex THEN maxVertexIndex _ indexRead;
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ': THEN MessageStream.PutF["Colon expected"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
[ xRead, ratNumOK] _ RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[ yRead, ratNumOK] _ RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"];

[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"];

doneAdj _ FALSE;
[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '] THEN doneAdj _ TRUE;

WHILE NOT doneAdj DO

[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
adjIndexRead _ in.GetInt[];
IF adjIndexRead < minVertexIndex THEN minVertexIndex _ adjIndexRead;
IF adjIndexRead > maxVertexIndex THEN maxVertexIndex _ adjIndexRead;
IF vertices[ adjIndexRead ] = NOTPRESENT THEN
vertices[ adjIndexRead ] _ ADJACENCY;
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[dataRope, charsSkipped ] _ in.GetTokenRope[ClientDataProc];
[]_ in.SkipWhitespace[];  puncChar _ in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];

[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '] THEN doneAdj _ TRUE;

ENDLOOP;

[ ] _ in.GetChar[ ]; -- toss right square bracket
[]_ in.SkipWhitespace[];   
IF in.PeekChar[] = '. THEN done _ TRUE;

ENDLOOP;

MessageStream.PutF["\nMinimum vertex index read is %g",  IO.int[ minVertexIndex] ];
MessageStream.PutF["\nMaximum vertex index read is %g",  IO.int[ maxVertexIndex] ];
I _ minVertexIndex - 1;
WHILE I < maxVertexIndex DO
I _ I + 1;
IF vertices[ I ] # PRESENT THEN  {
IF vertices[ I ] = ADJACENCY THEN 
MessageStream.PutF["\nVertex No. %g is only referred to in an adjacency", IO.int[ I] ]
ELSE
MessageStream.PutF["\nVertex No. %g is not present", IO.int[ I] ]
};
ENDLOOP;

};

SearchVertexList: PUBLIC PROC [list: VertexList, key: INT] RETURNS [Vertex] ~ {
WHILE list # NIL DO
IF list.first.index = key THEN RETURN [list.first ];
list _ list.rest;
ENDLOOP;
RETURN [NIL];
};

END.

	ZEuclideanGraphsImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:37:28 pm PDT

****************  Point and Edge Manipulation ****************
Bundle up two real numbers as an point
Bundle up two real numbers as an point
Test whether points p and q are the same.
Test whether points p and q are the same.
Compute square of distance between two points.
Determine the relation of the point test to the line [start, end].
*** Perhaps instead of DistanceSquare, can use the test IF ( (ytest - p1.y) * (p2.y - ytest) > 0 ) AND ( (xtest - p1.x) * (p2.x - xtest) > 0 ) THEN between (assuming nonvertical and nonhorizontal points).

****************  Structure Manipulation ****************
 v and w are adjacent vertices. Search and find the Adjacencys with each points to the other.
CountAdjacencies: PUBLIC PROC[v: Vertex] RETURNS [number: CARDINAL] ~ {
vAdjList: AdjacencyList _ v.adjacentVertices;
lastVertex: Vertex _ vAdjList.first.vertex;
nextVertex: Vertex;
done: BOOL _ FALSE;
IF vAdjList = NIL THEN RETURN[0];
number _ 0;  vAdjList _ vAdjList.rest;
WHILE NOT done DO
nextVertex _ vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done _ TRUE;  -- test for last vertex to be processed 
number _ number + 1;
vAdjList _ vAdjList.rest;
ENDLOOP;
};

Set visited field of all vertices in figure to visitedValue. Does Depth First Search. Flag fields (visited, intersectionPolygonEdge) left unchanged.
Assumes two or more vertices
Process adjacent vertices. Set all flag fields of edges to these vertices to visitedValue.  Recursive call on the vertex if and only if we haven't been there yet.
Find vertex closest to test point
Record that we've visited v
Compute distance to test point
Recursive calls for adjacencies of v


****************  New Basic Ops ****************

No adjacencies.



Go through adjacencies between v and vertices w, changeing edge from w to point to u instead of v, and setting up a new edge from u to w.

Set v's adjacency list to NIL, then go through adjacencies between v and vertices w, deleting edge from w to v.

No error checks implemented.


****************  Input and Output ****************

Dump a Vertex to a file. Does Depth First Search.   Doesn't write vertex data.
Assumes two or more vertices
Record that we've visited v
Write v
Write adjacencies of v
Recursive calls for adjacencies of v
Search vertexList for the element whose index is key;

Κυ˜š
œ™J™3J™—š
Οk	˜	J˜Jšœ
˜Jšœ
˜Jš
œ˜Jš
œ˜Jš
œ˜—J˜
head2šœœ
˜"Inamešœ
œœ	˜Jšœ˜J˜—Jšœœ
œ
œ˜*J˜Jšœ
œ
œΟc˜<J˜J™>J˜š
Οnœœ
œ	œ	œ˜KJ™&Jš
œ˜Jšœ˜J˜J˜—š
Ÿœœ
œ	œœ˜DJ™&Jšœœœ˜:Jšœ˜J˜J˜—š
Ÿœœ
œœœ˜EJšœœœ˜3Jšœ˜J˜J˜—š
Ÿ
œœ
œœœ˜:Jš
œ)™)Jšœœœ
œ˜BJ˜J˜—š
Ÿœœ
œœ
œ˜=Jš
œ)™)Jšœœ˜#J˜J˜—š
Ÿœœ
œœœ˜EJš
œ.™.Jšœœ˜Jšœ	œ˜&Jšœ	œ˜&šœœ˜Jšœ#œ!˜HJš
œ˜—Jš
œ˜J˜—š
Ÿ
œœ
œœœ˜]Jš
œB™BJšœ
œ˜Icodešœœ
œ
˜%šœœ˜šœ˜Jšœ$˜&Jšœ"˜$Jš
œ˜—šœ˜Jšœ$˜&Jšœ"˜$Jš
œ˜—Jš
œ˜—šœ
˜Mšœœœ˜!Mšœœœ˜Mšœœ
œ˜#Mšœ
˜—M˜M˜—š
Ÿœœ
œœ
œ˜pJšœ8œ)œ)=™Μ
Jš
œ%˜%Jšœœ
˜Jš
œ4˜4šœ˜Mš
œœ
œ˜#Mšœœœ˜%šœ˜Jšœœ
œ
œ˜5Jšœœ
œœ˜1JšœœJ˜XJšœ
œH˜WJš
œœœ
œ
œ˜9Jšœ
œIœ
œ
œœ
œ
œ˜}J˜—Mšœ
˜—J˜J˜—šŸœœ
œ%œ˜aJšœ@œ˜JJšœœ˜-Jšœœ˜-Jšœœœ
œ
˜&šœ
œœ
œ˜/Jšœ$˜&Jšœ#˜%J˜—šœ
œœ
œ˜/Jšœ$˜&Jšœ#˜%J˜—Jš
œ
œœœœ&˜hJš
œ
œœœœ&˜hšœ
œœ
œœž˜Cšœ
œ˜Jšœ)˜+Jšœ ˜"J˜—Jšœ
œœ'˜PJ˜
—šœ
œœž.˜GJš
œ˜Jšœ
œœ&˜OJ˜
—šœžA˜HJš
œ˜Jšœ
œœ&˜OJ˜—Jš
œ<˜<Jš
œ˜J˜—šŸœœ
œ6œ2˜
Jš
œ9˜9J˜Jš
œj˜jšœ˜Mšœœœœ˜7Mš
œœ˜+Mšœœ˜+Mšœœ˜'š
œ˜Mš
œz˜zJš
œc˜cšœ˜Mšœœœ˜*Mš
œœ˜(Mšœœ˜.Mšœœ˜$Mšœœž;˜N—M˜—Mšœ
˜—Jš
œ˜—J™™9J˜—šŸ
œœ
œœ˜KJ•commentTRUEš
œ]™]Jš
œ˜Jš
œ˜Jš
œ˜šœ˜J˜Jšœ
˜—šœ˜J˜Jšœ
˜—Jšœ˜!J˜J˜—š
Ÿœœ
œœ
œ˜GJš
œ0˜0Jš
œ,˜,Jšœœ
œ
œ˜$Jš
œ,˜,šœ˜Jš
œ˜Jš
œ˜Jšœ
˜—J˜J˜š
Ÿœœ
œœ
œ™GJš
œ-™-Jš
œ+™+Jš
œ™Jšœœœ
™Jšœœ
œ
œ™!Jš
œ&™&šœ
œ™Jš
œ#™#Jšœœœž(™VJš
œ™Jš
œ™Jšœ
™—J™J™——šŸœœ
œœœ
œ
œ˜OJš
œ0˜0Jš
œ,˜,Jšœœ
œ
œ
˜Jš
œœ
œ
œ
œ˜&Jšœœ<˜Zšœ˜Jšœœ>˜VJš
œ˜Jšœ
˜—J˜J˜—š
Ÿœœ
œœœ˜6Jš
œ0˜0Jš
œ,˜,Jš
œœ
œ
œ
œ˜(Jšœœ
œ
œ˜2Jš
œ˜šœ˜Jšœœ
œ
œ˜2Jš
œ˜Jšœ
˜—Jšœ
œ˜J˜J˜—šŸœœ
œœ˜IJ–TRUEš
œ”
™”
Jš	œœ
œ
œž˜'Jš	œœ
œ	œ
ž
˜TJšœ.ž˜EJšœ
˜J˜J˜—šŸœœœ˜FJš
ž™Jš
œ-˜-Jš
œ˜Jš
œ˜Jšœœœ
˜J˜Jšœž'˜AJ˜Jš
œ’
™’
Jš
œ$˜$JšœžJ˜eJšœœ
˜
šœ
œ˜Jš
œ˜Jš
œ"˜"Jšœœœž(˜VJšœ%ž
œ7ž˜zJš
œ˜Jšœ
˜—J˜Jšœ
˜Jš
œ˜J˜—šŸœœ
œ"œ˜XMš
œ!™!Jšœœ
˜Jš
œ˜Jšœœ
œœ
œž˜Ešœ˜Jš
œ7˜7Jš
œ2˜2Jšœ-œ&ž#˜yJšœ˜
J˜—J˜—šŸœœœ5œ	œœ˜©
Jš
œ-˜-Jš
œ ˜ Jšœœ˜Jšœœ
˜J˜Jš
œ™Jšœž(˜BJ˜Jš
œ™Jš
œ,˜,šœ
œ%œ˜0Jš
œ˜Jš
œ˜Jš
œ˜—J˜J™$Jš
œ˜Jš
œ˜Jš
œ$˜$JšœžJ˜eJšœœ
˜
šœ
œ˜Jš
œ#˜#Jšœœœž(˜VJšœ%œ]˜ˆ
Jš
œ˜Jšœ
˜—J˜Jšœ
˜J˜—J™J™™0J™—šŸœœ
œœœœ˜pMš
œ&˜&Mš
œ0˜0Mš
œ^˜^šœ˜Mšœ
œ˜(—š
˜Mšœ
œœ˜—M˜M˜—šŸœœ
œœœœœœ˜{M™JšœœHœ-˜‡
Jš
œ˜M˜M™—šŸ
œœ
œœœœœœ˜‚
JšœœM˜_M˜M™—šŸœœ
œ&œœœœ˜dMš
œ&˜&Mš
œ7˜7Mš
œF˜Fšœœ
œ˜%Mšœœ˜Mšœž˜%M˜M˜
—šœ˜Mš
œe˜eMšœœ
œ
˜!Mšœœ˜%Mš
œ,˜,Mšœ(ž#˜KM˜—M˜M™—šŸ
œœ
œ$˜;Mš
œ˜Mš
œ˜M˜šœ!˜(M˜M˜Mšœ
˜—šœœœ
œ˜/M˜Mš
œ˜M˜—Mš
œ˜—M˜šŸœœ
œ&œœœ˜pM˜Mš
œ3˜3M˜#Mš
œ'˜'Mš
œ˜Mš
œ'˜'Mš
œ'˜'Mš
œ˜Mš
œ'˜'Mšœ˜
M˜M˜—šŸœœ
œ*œ˜aM˜Mš
œ˜Mš
œ(˜(M˜%M˜Mšœœž˜*Mšœœž.˜Išœœ
˜Mš
œ˜šœ,˜2MšœDž˜S—šœ˜Mš
œ˜Jš
œ)˜)šœ˜J˜Jšœ
˜—Jšœž˜&Jšœž'˜?Mš
œ1˜1M˜—M˜Mšœ
˜—˜M˜——šŸ
œœ˜-M˜Mš
œ˜Mš
œ
˜
Jš
œ˜M˜M™‰
M˜%Mš	œœ
œ
œž%˜>M˜Mšœœž˜*Mšœœž;˜Všœœ
˜Mš
œ˜Mš
œ˜Jš
œ˜šœ˜J˜Jšœ
˜—Jšœž˜&Jšœž˜/Mš
œ)˜)M˜Mšœ
˜—M˜M™—šŸœœ
œ˜)M˜Mš
œ
˜
M˜M™oM˜%M˜Mšœœž˜*Mšœœž;˜Všœœ
˜Mš
œ˜M˜M˜Mšœ
˜—M˜M™—šŸœœ
œ˜0Mš
œ™Mš
œ˜Mš
œ˜M˜M™—šŸœœ
œœ]˜’
Jšœœ˜.Jš
œ$˜$Jš
œ>˜>Jš
œ0˜0Jšœœ˜2Jš
œ&˜&Jš	œœ
œ
œž:˜^Jš
œ'˜'šœœ
œ˜(Jš
œ
˜
šœ˜Mšœ
œœ&ž4˜ƒ
Mšœ%˜-Mš
œ&˜0Mšœ'˜2Mšœœž&˜9—Mš
œ\˜\Mš
œd˜dšœ
˜šœ˜Jš
œh˜hšœ˜Mš
œœœœ˜+šœœ˜4Mšœœ
˜MšœœžG˜UMšœœ-˜>Mšœ
˜—Mšœœœœ-˜[Mšœœž˜2M˜——šœœ˜3Mšœœ˜šœ	œ˜$Mš
œœ-˜AMšœœ
˜MšœœžV˜gMšœ
˜—Mšœœ-˜CMšœ
˜—š
œœ˜2Mšœœ
˜
Mšœœ
˜šœ
œ˜%Mš
œœ-˜AMšœœ
˜MšœœžV˜gMšœ
˜—Mšœ
˜—Mšœ
˜—Mš
œO˜OMšœ
˜—Mšœ.ž«
˜ί
M˜J˜—J™™3J™—š
Ÿ	œœ
œHœ,œ˜™
Jš
œN™NJšœœ
˜Jšœœ
œœ˜2Jš	œœ
œœž˜8šœœ
œž
˜0Jšœœ˜%Jšœœœ"œœœœ"œœ˜”
J˜
—šœž˜Jš
œ7˜7Jšœ!œ/ž#˜xJ˜—J˜"Jš
œ˜Jšœ
˜J˜J˜—šŸ
œœFœœ
œ,œ˜£
Jš
ž™Jš
œ-˜-Jš
œ ˜ Jš
œ˜Jšœœ
˜Jšœœ
˜J˜Jš
œ™Jšœž(˜BJ˜Jš
œ™Jšœœ˜$Jšœœœ"œœœœ"œœ˜“
J˜Jš
œ™Jš
œ$˜$JšœžJ˜eJšœœ
˜
šœ
œ˜Jš
œ˜Jš
œ˜Jšœœœž(˜VJš
œD˜DJšœœœ˜IJš
œ˜Jšœ
˜—J˜J˜Jš
œ$™$Jš
œ$˜$JšœžJ˜eJšœœ
˜
šœ
œ˜Jš
œ#˜#Jšœœœž(˜VJšœ%œO˜zJš
œ˜Jšœ
˜—Jšœ
˜J˜J˜—šœœ˜šœ
œ
œ˜Mš
œ˜Mšœž˜0—J˜—šŸœœ
œœ5œ
œ.œœ˜Δ
Jšœœœ
˜Jšœœ
˜Jšœœ
˜Jšœœž/˜BJšœ
œ
˜Jšœœ
˜Jšœœ˜Jš
œ˜J˜Jš
œ˜Jšœ
œ
˜Jšœœ
œœ˜/Jšœ
œ
˜Jš
œ˜Jšœœœ
˜'J˜Jšœ
œ˜˜Jš
œ˜Jš
œ3˜3Jšœœ&˜;Jš
œ3˜3Jšœœ+˜@Jšœœ˜(Jšœ
œ
œ2˜FJš
œ3˜3Jšœœ&˜;Jšœœ˜(Jšœ
œ
œ2˜FJ˜Jš
œ3˜3Jšœœ,˜AJš
œ3˜3Jšœœ4˜IJ˜Jšœ
œ
˜Jšœ
œ
˜Jš
œ˜Jšœœœ
˜*J˜šœ
œ	˜J˜Jš
œ3˜3Jšœœ+˜@Jš
œ˜Jš
œ3˜3Jšœœ&˜;Jš
œ˜Jš
œ<˜<Jš
œ@˜@Jš
œ3˜3Jšœœ,˜AJ˜JšœœDœ˜`Jšœ
œžy˜ 
J˜Jš
œ˜Jšœœœ
˜*J˜Jšœ
˜—J˜Jšœž˜1J˜šœœB˜QJš
œ0˜0—Jšœ
œ˜%J˜Jš
œ˜Jšœœœ
˜'J˜Jšœ
˜—J˜J˜J˜—šŸœœ
œœœ
œœœ	˜{Jš

œœœ	œ
œ˜6Jšœœ
ž5˜ZJšœœœ
˜Jšœœ
˜Jšœœ
˜Jšœœž/˜BJšœœ
˜Jšœœ˜Jšœ
œ
˜Jšœœ
œœ˜/Jš
œœœœ

œœ
œ˜JJšœœ
˜Jšœœœž˜KJ˜Jš
œ˜Jšœœœ
˜'J˜Jšœ
œ˜˜Jš
œ˜Jšœœ
˜ Jšœœ˜>Jšœœ˜>Jš
œ3˜3Jšœœ&˜;Jš
œ3˜3Jšœœ+˜@Jšœœ˜(Jšœ
œ
œ2˜FJš
œ3˜3Jšœœ&˜;Jšœœ˜(Jšœ
œ
œ2˜FJ˜Jš
œ3˜3Jšœœ,˜AJš
œ3˜3Jšœœ4˜IJ˜Jšœ
œ
˜Jš
œ˜Jšœœœ
˜*J˜šœ
œ	˜J˜Jš
œ3˜3Jšœœ+˜@Jš
œ˜Jšœœ˜DJšœœ˜Dšœ
œ
˜-Jšœ	œ
˜%—Jš
œ3˜3Jšœœ&˜;Jš
œ<˜<Jš
œ3˜3Jšœœ,˜AJ˜Jš
œ˜Jšœœœ
˜*J˜Jšœ
˜—J˜Jšœž˜1Jš
œ˜Jšœœœ
˜'J˜Jšœ
˜—J˜Jšœ9œ˜SJšœ9œ˜SJš
œ˜šœ˜Jš
œ
˜
šœœ
œ˜"šœ	œ
œ
˜"JšœJœ
˜V—š
˜Jšœ5œ
˜A—J˜—Jšœ
˜—J˜J˜—š
Ÿœœ
œœœ
˜OJš
œ5™5šœœ
˜Jšœœ
œ˜4Jš
œ˜Jšœ
˜—Jšœœ˜
J˜J˜—M™Jšœ
˜J˜—…—a܈+