DIRECTORY PERefresh USING [DisableSegmentRefresh, EnableSegmentRefresh], PETrajectoryOps, PETypes; PETrajectoryOpsImpl: CEDAR PROGRAM IMPORTS PERefresh EXPORTS PETrajectoryOps = BEGIN OPEN PERefresh, PETrajectoryOps, PETypes; ForAllVertices: PUBLIC PROCEDURE [vertexList: VertexList, proc: VertexProc] = { v: VertexNode; FOR v _ vertexList, v.rest UNTIL v = NIL DO proc[v]; ENDLOOP; }; ForAllSegments: PUBLIC PROCEDURE [segmentList: SegmentList, proc: SegmentProc] = { s: SegmentNode; IF segmentList # NIL THEN { proc[segmentList]; FOR s _ segmentList.rest, s.rest UNTIL s = NIL OR s = segmentList DO proc[s]; ENDLOOP; }; }; ForAllTrajectories: PUBLIC PROCEDURE [trajectoryList: TrajectoryList, proc: TrajectoryProc] = { t: TrajectoryNode; FOR t _ trajectoryList, t.rest UNTIL t = NIL DO proc[t]; ENDLOOP; }; IsAKnot: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isAKnot: BOOLEAN] = { RETURN [vertexNode # NIL AND vertexNode.rest = NIL]; }; IsAControlPoint: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isAControlPoint: BOOLEAN] = { RETURN [~IsAKnot[vertexNode]]; }; IsFirstVertex: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isFirst: BOOLEAN] = { RETURN [vertexNode # NIL AND vertexNode.preceding = NIL]; }; IsLastVertex: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isLast: BOOLEAN] = { RETURN [vertexNode # NIL AND vertexNode.rest = NIL]; }; InsertVertex: PUBLIC PROCEDURE [vertexList: VertexList, vertex: Vertex, node: VertexNode] RETURNS [newVertexList: VertexList, newNode: VertexNode] = { IF vertexList = NIL OR node = NIL THEN { newNode _ NEW[VertexNodeRec _ [preceding: NIL, first: vertex, rest: vertexList]]; IF vertexList # NIL THEN vertexList.preceding _ newNode; newVertexList _ newNode; } ELSE { newNode _ NEW[VertexNodeRec _ [preceding: node, first: vertex, rest: node.rest]]; IF node.rest # NIL THEN node.rest.preceding _ newNode; node.rest _ newNode; newVertexList _ vertexList; }; }; RemoveVertex: PUBLIC PROCEDURE [vertexList: VertexList, vertex: VertexNode] RETURNS [newVertexList: VertexList, prevVertex: VertexNode] = { prevVertex _ vertex.preceding; IF vertex.rest # NIL THEN vertex.rest.preceding _ vertex.preceding; IF vertex.preceding = NIL THEN newVertexList _ vertexList.rest ELSE { vertex.preceding.rest _ vertex.rest; newVertexList _ vertexList; }; FreeVertexNode[vertex]; -- break the back links }; LastVertexNode: PUBLIC PROCEDURE [list: VertexList] RETURNS [vertexNode: VertexNode] = { AssignNode: VertexProc = { vertexNode _ v; }; vertexNode _ NIL; ForAllVertices[list, AssignNode]; }; PrecedingVertex: PUBLIC PROCEDURE [vertex: VertexNode, segment: SegmentNode] RETURNS [pVertex: VertexNode, pSegment: SegmentNode] = { SELECT TRUE FROM vertex = NIL OR segment = NIL => RETURN[NIL, NIL]; ~IsFirstVertex[vertex] => RETURN [vertex.preceding, segment]; ~IsFirstSegment[segment] => RETURN [LastVertexNode[segment.preceding.first.vertices], segment.preceding]; ENDCASE => RETURN [NIL, NIL]; }; FollowingVertex: PUBLIC PROCEDURE [vertex: VertexNode, segment: SegmentNode] RETURNS [fVertex: VertexNode, fSegment: SegmentNode] = { SELECT TRUE FROM vertex = NIL OR segment = NIL => RETURN[NIL, NIL]; ~IsLastVertex[vertex] => RETURN [vertex.rest, segment]; ~IsLastSegment[segment] => RETURN [segment.rest.first.vertices, segment.rest]; ENDCASE => RETURN [NIL, NIL]; }; FreeVertexList: PUBLIC PROCEDURE [vertexList: VertexList] = { FreeNode: VertexProc = { FreeVertexNode[v]; }; ForAllVertices[vertexList, FreeNode]; }; FreeVertexNode: PRIVATE PROCEDURE [vertexNode: VertexNode] = { IF vertexNode = NIL THEN RETURN; vertexNode.preceding _ NIL; }; VertexListLength: PUBLIC PROCEDURE [list: VertexList] RETURNS [length: CARDINAL] = { IncrementLength: VertexProc = { length _ length + 1; }; length _ 0; ForAllVertices[list, IncrementLength]; }; VertexListAppend: PUBLIC PROCEDURE [list1: VertexList, list2: VertexList _ NIL] RETURNS [list: VertexList] = { lastNode: VertexNode _ LastVertexNode[list1]; IF lastNode = NIL THEN list _ list2 ELSE { lastNode.rest _ list2; IF list2 # NIL THEN list2.preceding _ lastNode; list _ list1; }; }; VertexListNthElement: PUBLIC PROCEDURE [list: VertexList, n: INTEGER] RETURNS [vertex: Vertex] = { length: CARDINAL _ VertexListLength[list]; vertexNode: VertexNode _ list; IF n = 0 OR ABS[n] > length THEN vertex _ NIL ELSE { IF n < 0 THEN n _ length + n + 1; FOR i: INTEGER IN [1..n-1] DO vertexNode _ vertexNode.rest; ENDLOOP; vertex _ vertexNode.first; }; }; IsFirstSegment: PUBLIC PROCEDURE [segmentNode: SegmentNode] RETURNS [isFirst: BOOLEAN] = { RETURN [segmentNode # NIL AND (segmentNode.preceding = NIL OR segmentNode.first.type = moveTo)]; }; IsLastSegment: PUBLIC PROCEDURE [segmentNode: SegmentNode] RETURNS [isLast: BOOLEAN] = { RETURN [segmentNode # NIL AND (segmentNode.rest = NIL OR segmentNode.rest.first.type = moveTo)]; }; InsertSegment: PUBLIC PROCEDURE [segmentList: SegmentList, segment: Segment, node: SegmentNode] RETURNS [newSegmentList: SegmentList, newNode: SegmentNode] = { newNode _ NEW[SegmentNodeRec _ [preceding: NIL, first: segment, rest: NIL]]; newSegmentList _ LinkSegments[segmentList: segmentList, node: node, newNodes: newNode]; }; LinkSegments: PRIVATE PROCEDURE [segmentList: SegmentList, node: SegmentNode, newNodes: SegmentList] RETURNS [newSegmentList: SegmentList] = { lastNode: SegmentNode _ LastSegmentNode[newNodes]; IF node = NIL THEN { IF segmentList # NIL THEN { newNodes.preceding _ segmentList.preceding; lastNode.rest _ segmentList; IF segmentList.preceding # NIL THEN segmentList.preceding.rest _ newNodes; segmentList.preceding _ lastNode; } ELSE { newNodes.preceding _ lastNode; lastNode.rest _ newNodes; }; newSegmentList _ newNodes; } ELSE { newNodes.preceding _ node; lastNode.rest _ node.rest; IF node.rest # NIL THEN node.rest.preceding _ lastNode; node.rest _ newNodes; newSegmentList _ segmentList; }; SetFP[newNodes]; SetFP[lastNode.rest]; }; SetFP: PUBLIC PROCEDURE [segment: SegmentNode] = { IF segment = NIL THEN RETURN; segment.first.fp _ SELECT segment.first.type FROM curveTo => IF segment.preceding # NIL THEN LastVertexNode[segment.preceding.first.vertices].first ELSE NIL, ENDCASE => NIL; }; RemoveSegment: PUBLIC PROCEDURE [segmentList: SegmentList, segment: SegmentNode] RETURNS [newSegmentList: SegmentList, prevSegment: SegmentNode] = { prevSegment _ segment.preceding; [newSegmentList: newSegmentList] _ UnlinkSegments[segmentList: segmentList, node: segment]; FreeSegmentNode[segment]; -- break the back links }; UnlinkSegments: PRIVATE PROCEDURE [segmentList: SegmentList, node: SegmentNode, n: CARDINAL _ 1] RETURNS [newSegmentList: SegmentList, unlinkedSegments: SegmentList] = { lastNode: SegmentNode _ node; DisableRefresh: SegmentProc = { DisableSegmentRefresh[s.first]; }; IF n = 0 OR segmentList = NIL OR node = NIL THEN RETURN [newSegmentList: segmentList, unlinkedSegments: NIL]; FOR i: CARDINAL IN [1..n-1] DO IF lastNode.rest # node THEN { lastNode _ lastNode.rest; IF lastNode = segmentList THEN segmentList _ segmentList.rest; }; ENDLOOP; IF lastNode.rest = node THEN newSegmentList _ NIL ELSE { lastNode.rest.preceding _ node.preceding; node.preceding.rest _ lastNode.rest; newSegmentList _ IF node = segmentList THEN lastNode.rest ELSE segmentList; SetFP[lastNode.rest]; }; lastNode.rest _ node; node.preceding _ lastNode; ForAllSegments[node, DisableRefresh]; unlinkedSegments _ node; }; LastSegmentNode: PUBLIC PROCEDURE [list: SegmentList] RETURNS [segmentNode: SegmentNode] = { AssignNode: SegmentProc = { segmentNode _ s; }; segmentNode _ NIL; ForAllSegments[list, AssignNode]; }; FreeSegmentList: PUBLIC PROCEDURE [segmentList: SegmentList] = { FreeNode: SegmentProc = { FreeSegmentNode[s]; }; ForAllSegments[segmentList, FreeNode]; }; FreeSegmentNode: PRIVATE PROCEDURE [segmentNode: SegmentNode] = { IF segmentNode = NIL THEN RETURN; FreeVertexList[segmentNode.first.vertices]; segmentNode.first.fp _ NIL; segmentNode.preceding _ NIL; segmentNode.first.refresh _ FALSE; }; SwapSegments: PUBLIC PROCEDURE [segmentList: SegmentList, newSegments: SegmentList, oldSegment: SegmentNode, n: CARDINAL _ 1] RETURNS [newSegmentList, oldSegments: SegmentList] = { prevSegment: SegmentNode; lastNode: SegmentNode _ oldSegment; protectedSegment: SegmentNode _ NIL; protectedSegmentRefresh: BOOLEAN _ FALSE; IF lastNode # NIL THEN { FOR i: CARDINAL IN [1..n-1] DO IF lastNode.rest # NIL AND lastNode.rest # oldSegment THEN lastNode _ lastNode.rest; ENDLOOP; protectedSegment _ lastNode.rest; IF protectedSegment # NIL THEN { protectedSegmentRefresh _ protectedSegment.first.refresh; DisableSegmentRefresh[protectedSegment.first]; }; }; prevSegment _ IF oldSegment # NIL AND ~IsFirstSegment[oldSegment] AND oldSegment.preceding # lastNode THEN oldSegment.preceding ELSE NIL; [newSegmentList, oldSegments] _ UnlinkSegments[segmentList, oldSegment, n]; newSegmentList _ LinkSegments[newSegmentList, prevSegment, newSegments]; IF protectedSegmentRefresh THEN EnableSegmentRefresh[protectedSegment.first]; }; InsertTrajectory: PUBLIC PROCEDURE [trajectoryList: TrajectoryList, trajectory: Trajectory, node: TrajectoryNode] RETURNS [newTrajectoryList: TrajectoryList, newNode: TrajectoryNode] = { IF trajectoryList = NIL OR node = NIL THEN { newNode _ NEW[TrajectoryNodeRec _ [preceding: NIL, first: trajectory, rest: trajectoryList]]; IF trajectoryList # NIL THEN trajectoryList.preceding _ newNode; newTrajectoryList _ newNode; } ELSE { newNode _ NEW[TrajectoryNodeRec _ [preceding: node, first: trajectory, rest: node.rest]]; IF node.rest # NIL THEN node.rest.preceding _ newNode; node.rest _ newNode; newTrajectoryList _ trajectoryList; }; }; RemoveTrajectory: PUBLIC PROCEDURE [trajectoryList: TrajectoryList, trajectory: TrajectoryNode] RETURNS [newTrajectoryList: TrajectoryList, prevTrajectory: TrajectoryNode] = { prevTrajectory _ trajectory.preceding; IF trajectory.rest # NIL THEN trajectory.rest.preceding _ trajectory.preceding; IF trajectory.preceding = NIL THEN newTrajectoryList _ trajectoryList.rest ELSE { trajectory.preceding.rest _ trajectory.rest; newTrajectoryList _ trajectoryList; }; FreeTrajectoryNode[trajectory]; -- break the back links }; LastTrajectoryNode: PUBLIC PROCEDURE [list: TrajectoryList] RETURNS [trajectoryNode: TrajectoryNode] = { AssignNode: TrajectoryProc = { trajectoryNode _ t; }; trajectoryNode _ NIL; ForAllTrajectories[list, AssignNode]; }; FreeTrajectoryList: PUBLIC PROCEDURE [trajectoryList: TrajectoryList] = { FreeNode: TrajectoryProc = { FreeTrajectoryNode[t]; }; ForAllTrajectories[trajectoryList, FreeNode]; }; FreeTrajectoryNode: PRIVATE PROCEDURE [trajectoryNode: TrajectoryNode] = { IF trajectoryNode = NIL THEN RETURN; FreeSegmentList[trajectoryNode.first.segments]; trajectoryNode.preceding _ NIL; trajectoryNode.first.refresh _ FALSE; }; END. ŽPETrajectoryOpsImpl.mesa Written by Darlene Plebon on August 23, 1983 10:07 am Vertex, segment, and trajectory data structure manipulation routines for the Path Editor. Vertex, segment, and trajectory list traversal routines. This routine traverses a vertex list, calling the client supplied routine for each vertex node. This routine traverses a segment list, calling the client supplied routine for each segment node. This routine traverses a trajectory list, calling the client supplied routine for each trajectory node. Vertex manipulation routines. This routine determines whether the specified vertex is a knot. This routine determines whether the specified vertex is a control point. This routine determines whether the specified vertex node is the first vertex of the vertex list (segment) containing it. This routine determines whether the specified vertex node is the last vertex of the vertex list (segment) containing it. This routine inserts the specified vertex into vertexList immediately following the specified node. If the node is NIL, the vertex is inserted at the start of the vertex list. This routine returns the new vertexList, and the new node (for the new vertex). This routine removes the specified vertex from vertexList. This routine returns the new vertexList, along with the vertex node which preceded vertex in the original list. This routine returns the last node in a vertex list. Given a vertex and the segment containing it, this routine returns the preceding vertex in the segment list and the segment containing it. Given a vertex and the segment containing it, this routine returns the following vertex in the segment list and the segment containing it. This routine NILs all the back pointers in a vertex list, so that the garbage collector can collect it. This routine NILs all the back pointers in a vertex node, so that the garbage collector can collect it. List operators for Vertex lists. These are similar to the ones in the List interface. This routine returns NIL if the vertex list has too few elements, unlike the corresponding routine in the list interface which raises a signal. Segment manipulation routines. This routine determines whether the specified segment node is the first segment of the segment list (trajectory) containing it. This routine determines whether the specified segment node is the last segment of the segment list (trajectory) containing it. This routine inserts the specified segment into segmentList immediately following the specified node. If the node is NIL, the segment is inserted at the start of the segment list. This routine returns the new segmentList, and the new node (for the new segment). Note that segment lists are doubly linked circular lists. This routine links a list of segment nodes into the specified segment list directly following the specified node. The new segment list is returned. This routine sets the first point field of a segment according to its context (i.e. the nodes around it). This routine removes the specified segment from segmentList. This routine returns the new segmentList, along with the segment node which preceded segment in the original list. This routine unlinks the specified number of segments from the specified segment list starting with the specified node. The new segment list is returned, along with the list of unlinked nodes. This routine returns the last node in a segment list. This routine NILs all the back pointers in a segment list (including those in all of its segment and vertex nodes), so that the garbage collector can collect it. This routine also prevents freed nodes from being refreshed. This routine NILs all the back pointers in a segment node (including those in all of its vertex nodes), so that the garbage collector can collect it. This routine also prevents the freed node from being refreshed. This routine replaces a number of segments in the specified segment list. newSegments is a list of replacements, not necessarily the same length as the piece being removed. oldSegment is the first segment to be replaced in segmentList. n is the number of segments to be replaced. This routine returns the new segment list along with a list of removed segments. Trajectory manipulation routines. This routine inserts the specified trajectory into trajectoryList immediately following the specified node. If the node is NIL, the trajectory is inserted at the start of the trajectory list. This routine returns the new trajectoryList, and the new node (for the new trajectory). This routine removes the specified trajectory from trajectoryList. This routine returns the new trajectoryList, along with the trajectory node which preceded trajectory in the original list. This routine returns the last node in a trajectory list. This routine NILs all the back pointers for a trajectory list (including all those in its trajectory, segment and vertex nodes), so that the garbage collector can collect it. This routine also prevents freed nodes from being refreshed. This routine NILs all the back pointers for a trajectory node (including those in its segment and vertex nodes), so that the garbage collector can collect it. This routine also prevents freed nodes from being refreshed. Ê Ì˜Jšœ™Jšœ5™5J˜J™YJ˜šÏk ˜ Jšœ œ/˜>Jšœ˜Jšœ˜J˜—šœœ˜"Jšœ ˜Jšœ˜—J˜Jšœœ%˜/J™J™8J™šÏnœœ/˜OJ™_J˜šœœœ˜+Jšœ˜Jšœ˜—J˜—J˜šžœœ2˜RJ™aJšœ˜šœœœ˜Jšœ˜š œœœœ˜DJšœ˜Jšœ˜—J˜—J˜—J˜šžœœ;˜_J™gJšœ˜šœœœ˜/Jšœ˜Jšœ˜—J˜—J˜J™J™šžœœœ œ˜QJ™?Jšœœœœ˜4J˜—J˜šžœœœœ˜aJ™HJšœ˜J˜—J˜š ž œœ œœ œ˜WJ™yJšœœœœ˜9J˜—J˜š ž œœ œœ œ˜UJ™xJšœœœœ˜4J˜—J˜šž œœ<œ5˜–J™š œœœœœ˜(Jšœ œœ$˜QJšœœœ ˜8Jšœ˜J˜—šœ˜Jšœ œD˜QJšœ œœ˜6J˜Jšœ˜Jšœ˜—J˜—J˜šž œœ.œ8˜‹J™«Jšœ˜Jšœœœ*˜CJšœœœ ˜>šœ˜Jšœ$˜$Jšœ˜J˜—JšœÏc˜2J˜—J˜šžœœœ˜XJ™4šž œ˜Jšœ˜J˜—Jšœ œ˜J˜!J˜—J˜šžœœ,œ1˜…J™Ššœœ˜Jš œ œœ œœœœ˜2Jšœœ˜=JšœœG˜iJšœœœœ˜—J˜—J˜šžœœ,œ1˜…J™Ššœœ˜Jš œ œœ œœœœ˜2Jšœœ˜7Jšœœ-˜NJšœœœœ˜—J˜—J˜šžœœ˜=J™gšžœ˜Jšœ˜J˜—Jšœ%˜%J˜—J˜šžœœ˜>J™gJšœœœœ˜ Jšœœ˜J˜—J™J™VJ˜šžœœœ œ˜Tšžœ˜J˜J˜—J˜ Jšœ&˜&J˜—J˜šžœœ)œœ˜nJšœ-˜-Jšœ œœ ˜#šœ˜J˜Jšœ œœ˜/J˜ J˜—J˜—J˜šžœœœœ˜bJ™Jšœœ˜*Jšœ˜Jš œœœ œ ˜-šœ˜Jšœœ˜!šœœœ ˜J˜Jšœ˜—J˜J˜—J˜—J˜J™J™šžœœœ œ˜ZJ™Jš œœœœœ#˜`J˜—J˜šž œœœ œ˜XJ™~Jš œœœœœ(˜`J˜—J˜šž œœAœ8˜ŸJ™ÂJšœ œœœ˜LJšœW˜WJ˜—J˜šž œœFœ"˜ŽJ™”Jšœ2˜2šœœœ˜šœœœ˜Jšœ,˜,Jšœ˜Jšœœœ'˜JJšœ!˜!Jšœ˜—šœ˜Jšœ˜Jšœ˜Jšœ˜—Jšœ˜J˜—šœ˜Jšœ˜Jšœ˜Jšœ œœ ˜7Jšœ˜Jšœ˜Jšœ˜—Jšœ˜Jšœ˜J˜—J˜šžœœ˜2J™iJšœ œœœ˜šœœ˜1Jš œ œœœ8œœ˜kJšœœ˜—J˜—J˜šž œœ2œ<˜”J™°Jšœ ˜ Jšœ[˜[JšœŸ˜2J˜—J˜šžœœ2œœA˜©J™ÁJšœ˜šžœ˜Jšœ˜J˜—Jšœœœœœœœ1œ˜mšœœœ ˜šœœ˜Jšœ˜Jšœœ ˜>J˜—Jšœ˜—Jšœœ˜1šœ˜Jšœ)˜)Jšœ$˜$Jšœœœœ ˜KJšœ˜Jšœ˜—Jšœ˜Jšœ˜J˜%J˜J˜—J˜šžœœœ˜\J™5šž œ˜Jšœ˜J˜—Jšœœ˜J˜!J˜—J˜šžœœ˜@Jšœß™ßšžœ˜J˜J˜—Jšœ&˜&J˜—J˜šžœœ˜AJšœÖ™ÖJšœœœœ˜!Jšœ+˜+Jšœœ˜Jšœœ˜Jšœœ˜"J˜—J˜šž œœRœœ/˜´J™ìJšœ˜Jšœ#˜#Jšœ œ˜$Jšœœ˜)šœ œœ˜šœœœ ˜Jšœœœœ˜TJšœ˜—Jšœ!˜!šœœœ˜ Jšœ9˜9Jšœ.˜.J˜—J˜—Jšœœœœœ!œœœ˜‰JšœK˜KJšœH˜HJšœœ.˜MJšœ˜—J™J™!J˜šžœœPœA˜ºJšœ™™™š œœœœœ˜,Jšœ œ!œ,˜]Jšœœœ$˜@Jšœ˜J˜—šœ˜Jšœ œL˜YJšœ œœ˜6J˜Jšœ#˜#Jšœ˜—J˜—J˜šžœœ>œH˜¯Jšœ¿™¿Jšœ&˜&Jšœœœ2˜OJšœœœ(˜Jšœ˜Jšœ,˜,Jšœ#˜#J˜—Jšœ#Ÿ˜:J˜—J˜šžœœœ%˜hJ™8šž œ˜Jšœ˜J˜—Jšœœ˜Jšœ%˜%J˜—J˜šžœœ%˜IJšœì™ìšžœ˜Jšœ˜J˜—Jšœ-˜-J˜—J˜šžœœ œ%˜JJšœÜ™ÜJšœœœœ˜$Jšœ/˜/Jšœœ˜Jšœœ˜%J˜—J˜Jš˜J˜—…—*BKœ