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.
DIRECTORY
PERefresh USING [DisableSegmentRefresh, EnableSegmentRefresh],
PETrajectoryOps,
PETypes;
PETrajectoryOpsImpl: CEDAR PROGRAM
IMPORTS PERefresh
EXPORTS PETrajectoryOps =
BEGIN OPEN PERefresh, PETrajectoryOps, PETypes;
Vertex, segment, and trajectory list traversal routines.
ForAllVertices: PUBLIC PROCEDURE [vertexList: VertexList, proc: VertexProc] = {
This routine traverses a vertex list, calling the client supplied routine for each vertex node.
v: VertexNode;
FOR v ← vertexList, v.rest UNTIL v = NIL DO
proc[v];
ENDLOOP;
};
ForAllSegments: PUBLIC PROCEDURE [segmentList: SegmentList, proc: SegmentProc] = {
This routine traverses a segment list, calling the client supplied routine for each segment node.
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] = {
This routine traverses a trajectory list, calling the client supplied routine for each trajectory node.
t: TrajectoryNode;
FOR t ← trajectoryList, t.rest UNTIL t = NIL DO
proc[t];
ENDLOOP;
};
Vertex manipulation routines.
IsAKnot: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isAKnot: BOOLEAN] = {
This routine determines whether the specified vertex is a knot.
RETURN [vertexNode # NIL AND vertexNode.rest = NIL];
};
IsAControlPoint: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isAControlPoint: BOOLEAN] = {
This routine determines whether the specified vertex is a control point.
RETURN [~IsAKnot[vertexNode]];
};
IsFirstVertex: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isFirst: BOOLEAN] = {
This routine determines whether the specified vertex node is the first vertex of the vertex list (segment) containing it.
RETURN [vertexNode # NIL AND vertexNode.preceding = NIL];
};
IsLastVertex: PUBLIC PROCEDURE [vertexNode: VertexNode] RETURNS [isLast: BOOLEAN] = {
This routine determines whether the specified vertex node is the last vertex of the vertex list (segment) containing it.
RETURN [vertexNode # NIL AND vertexNode.rest = NIL];
};
InsertVertex: PUBLIC PROCEDURE [vertexList: VertexList, vertex: Vertex, node: VertexNode] RETURNS [newVertexList: VertexList, newNode: VertexNode] = {
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).
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] = {
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.
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] = {
This routine returns the last node in a vertex list.
AssignNode: VertexProc = {
vertexNode ← v;
};
vertexNode ← NIL;
ForAllVertices[list, AssignNode];
};
PrecedingVertex: PUBLIC PROCEDURE [vertex: VertexNode, segment: SegmentNode] RETURNS [pVertex: VertexNode, pSegment: SegmentNode] = {
Given a vertex and the segment containing it, this routine returns the preceding vertex in the segment list and the segment containing it.
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] = {
Given a vertex and the segment containing it, this routine returns the following vertex in the segment list and the segment containing it.
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] = {
This routine NILs all the back pointers in a vertex list, so that the garbage collector can collect it.
FreeNode: VertexProc = {
FreeVertexNode[v];
};
ForAllVertices[vertexList, FreeNode];
};
FreeVertexNode: PRIVATE PROCEDURE [vertexNode: VertexNode] = {
This routine NILs all the back pointers in a vertex node, so that the garbage collector can collect it.
IF vertexNode = NIL THEN RETURN;
vertexNode.preceding ← NIL;
};
List operators for Vertex lists. These are similar to the ones in the List interface.
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] = {
This routine returns NIL if the vertex list has too few elements, unlike the corresponding routine in the list interface which raises a signal.
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;
};
};
Segment manipulation routines.
IsFirstSegment: PUBLIC PROCEDURE [segmentNode: SegmentNode] RETURNS [isFirst: BOOLEAN] = {
This routine determines whether the specified segment node is the first segment of the segment list (trajectory) containing it.
RETURN [segmentNode # NIL AND (segmentNode.preceding = NIL OR segmentNode.first.type = moveTo)];
};
IsLastSegment: PUBLIC PROCEDURE [segmentNode: SegmentNode] RETURNS [isLast: BOOLEAN] = {
This routine determines whether the specified segment node is the last segment of the segment list (trajectory) containing it.
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] = {
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.
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] = {
This routine links a list of segment nodes into the specified segment list directly following the specified node. The new segment list is returned.
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] = {
This routine sets the first point field of a segment according to its context (i.e. the nodes around it).
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] = {
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.
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] = {
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.
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] = {
This routine returns the last node in a segment list.
AssignNode: SegmentProc = {
segmentNode ← s;
};
segmentNode ← NIL;
ForAllSegments[list, AssignNode];
};
FreeSegmentList: PUBLIC PROCEDURE [segmentList: SegmentList] = {
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.
FreeNode: SegmentProc = {
FreeSegmentNode[s];
};
ForAllSegments[segmentList, FreeNode];
};
FreeSegmentNode: PRIVATE PROCEDURE [segmentNode: SegmentNode] = {
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.
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] = {
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.
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];
};
Trajectory manipulation routines.
InsertTrajectory: PUBLIC PROCEDURE [trajectoryList: TrajectoryList, trajectory: Trajectory, node: TrajectoryNode] RETURNS [newTrajectoryList: TrajectoryList, newNode: TrajectoryNode] = {
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).
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] = {
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.
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] = {
This routine returns the last node in a trajectory list.
AssignNode: TrajectoryProc = {
trajectoryNode ← t;
};
trajectoryNode ← NIL;
ForAllTrajectories[list, AssignNode];
};
FreeTrajectoryList: PUBLIC PROCEDURE [trajectoryList: TrajectoryList] = {
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.
FreeNode: TrajectoryProc = {
FreeTrajectoryNode[t];
};
ForAllTrajectories[trajectoryList, FreeNode];
};
FreeTrajectoryNode: PRIVATE PROCEDURE [trajectoryNode: TrajectoryNode] = {
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.
IF trajectoryNode = NIL THEN RETURN;
FreeSegmentList[trajectoryNode.first.segments];
trajectoryNode.preceding ← NIL;
trajectoryNode.first.refresh ← FALSE;
};
END.