GGSequenceImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last edited by Bier on January 14, 1987 11:36:39 pm PST
Contents: Sequences are a way to describe some part of a trajectory without actually pulling the trajectory apart. The new definition of sequence is that it is ANY subset of the parts of a trajectory (joints and/or segments). Procedures are provided which make sequences, perform boolean operations on them, and step through them.
Pier, January 15, 1987 1:59:18 pm PST
Kurlander July 28, 1986 2:41:32 pm PDT
DIRECTORY
GGBoundBox, GGBasicTypes, GGError, GGModelTypes, GGSegmentTypes, GGSelect, GGSequence, GGTraj, GGUtility, Rope;
GGSequenceImpl:
CEDAR
PROGRAM
IMPORTS GGBoundBox, GGError, GGSelect, GGSequence, GGTraj, GGUtility
EXPORTS GGSequence = BEGIN
BitMatrix: TYPE = REF BitMatrixObj;
BitMatrixObj: TYPE = GGBasicTypes.BitMatrixObj;
BitVector: TYPE = REF BitVectorObj;
BitVectorObj: TYPE = GGBasicTypes.BitVectorObj;
BoundBox: TYPE = GGBasicTypes.BoundBox;
ControlPointGenerator: TYPE = REF ControlPointGeneratorObj;
ControlPointGeneratorObj: TYPE = GGModelTypes.ControlPointGeneratorObj;
Joint: TYPE = GGModelTypes.Joint;
JointGenerator: TYPE = REF JointGeneratorObj;
JointGeneratorObj: TYPE = GGModelTypes.JointGeneratorObj;
Point: TYPE = GGBasicTypes.Point;
PointAndDone: TYPE = GGModelTypes.PointAndDone;
SegAndIndex: TYPE = GGSequence.SegAndIndex;
Segment: TYPE = GGSegmentTypes.Segment;
SegmentGenerator: TYPE = REF SegmentGeneratorObj;
SegmentGeneratorObj: TYPE = GGModelTypes.SegmentGeneratorObj;
Sequence: TYPE = REF SequenceObj;
SequenceObj: TYPE = GGModelTypes.SequenceObj;
SequenceGenerator: TYPE = REF SequenceGeneratorObj;
SequenceGeneratorObj: TYPE = GGModelTypes.SequenceGeneratorObj;
Traj: TYPE = GGModelTypes.Traj;
TrajEnd: TYPE = GGModelTypes.TrajEnd;
TrajPartType: TYPE = GGModelTypes.TrajPartType;
Problem: PUBLIC SIGNAL [msg: Rope.ROPE] = GGError.Problem;
Sequence Creation
CreateFromSegments:
PUBLIC
PROC [traj: Traj, startSeg, endSeg:
NAT]
RETURNS [seq: Sequence] = {
The sequence created will include all of the segments from startSeg to endSeg inclusive, and all of the joints which they touch. startSeg and endSeg must be legal Sequence numbers for this trajectory. If the trajectory is closed, then startSeg > endSeg is allowed, in which case the segment sequence wraps around.
If startSeg = endSeg, then one segment is added.
If startSeg = endSeg + 1 (modulo the number of segments in traj), then the whole trajectory is selected.
segCount, temp: NAT;
IF startSeg >= traj.segCount OR endSeg >= traj.segCount THEN ERROR;
IF startSeg = endSeg THEN {seq ← CreateFromSegment[traj, startSeg]; RETURN};
IF traj.role = open
THEN {
IF startSeg > endSeg THEN {temp ← startSeg; startSeg ← endSeg; endSeg ← temp};
segCount ← endSeg - startSeg + 1;
}
ELSE {
IF startSeg = (endSeg + 1) MOD traj.segCount THEN {seq ← CreateComplete[traj]; RETURN};
segCount ← ((endSeg - startSeg + traj.segCount) MOD traj.segCount) + 1;
};
seq ←
NEW[SequenceObj ← [
traj: traj,
boundBox: GGBoundBox.CopyBoundBox[traj.boundBox],
segments: NewBitVector[traj.segCount],
joints: NewBitVector[GGTraj.HiJoint[traj] + 1],
controlPoints: NewBitMatrix[traj],
segCount: segCount,
controlPointCount: 0, -- will be updated by FillInControlPoints
jointCount: 0 -- will be updated by FillInJoints
]];
IF startSeg < endSeg
THEN {
FOR i:
NAT
IN [startSeg..endSeg]
DO
seq.segments[i] ← TRUE;
ENDLOOP;
FillInJoints[seq];
FillInControlPoints[seq];
}
ELSE {
FOR i:
NAT
IN [startSeg..traj.segCount-1]
DO
seq.segments[i] ← TRUE;
ENDLOOP;
FOR i:
NAT
IN [0..endSeg]
DO
seq.segments[i] ← TRUE;
ENDLOOP;
FillInJoints[seq];
FillInControlPoints[seq];
};
};
CreateJointToJoint:
PUBLIC
PROC [traj: Traj, startJoint, endJoint:
NAT]
RETURNS [seq: Sequence] = {
IF the traj is open, then select all segments in the interval [startJoint..endJoint]. If the traj is closed, there are three cases: 1) IF startJoint < endJoint then proceed as for an open traj (but there is no way to select the whole trajectory. 2) IF startJoint = endJoint then select a single joint. 3) IF endJoint < startJoint, wrap around, selecting all segments above startJoint, all segments below endJoint, all joints above startJoint including startJoint, all joints below endJoint, including endJoint.
temp, hiJoint: NAT;
hiJoint ← GGTraj.HiJoint[traj];
IF traj.role = open
AND startJoint = 0
AND endJoint = hiJoint
THEN {
seq ← CreateComplete[traj]; RETURN};
IF traj.role = open
OR startJoint < endJoint
THEN {
IF startJoint > endJoint THEN {temp ← startJoint; startJoint ← endJoint; endJoint ← temp};
IF startJoint < 0 OR endJoint > hiJoint THEN ERROR;
seq ←
NEW[SequenceObj ← [
traj: traj,
boundBox: GGBoundBox.CopyBoundBox[traj.boundBox],
segments: NewBitVector[traj.segCount],
joints: NewBitVector[hiJoint+1],
controlPoints: NewBitMatrix[traj],
segCount: endJoint - startJoint,
controlPointCount: 0, -- initialized by FillInControlPoints
jointCount: endJoint - startJoint + 1
]];
FOR i:
NAT
IN [startJoint..endJoint-1]
DO
seq.segments[i] ← TRUE;
seq.joints[i] ← TRUE;
ENDLOOP;
seq.joints[endJoint] ← TRUE;
}
ELSE {
IF startJoint = endJoint THEN {seq ← CreateFromJoint[traj, startJoint]; RETURN};
Closed trajectory with endJoint < startJoint (Case 3).
seq ←
NEW[SequenceObj ← [
traj: traj,
boundBox: GGBoundBox.CopyBoundBox[traj.boundBox],
segments: NewBitVector[traj.segCount],
joints: NewBitVector[hiJoint+1],
controlPoints: NewBitMatrix[traj],
segCount: traj.segCount - startJoint + endJoint,
controlPointCount: 0,
jointCount: traj.segCount - startJoint + endJoint + 1
]];
FOR i:
NAT
IN [startJoint..traj.segCount-1]
DO
seq.segments[i] ← TRUE;
seq.joints[i] ← TRUE;
ENDLOOP;
FOR i:
NAT
IN [0..endJoint-1]
DO
seq.segments[i] ← TRUE;
seq.joints[i] ← TRUE;
ENDLOOP;
seq.joints[endJoint] ← TRUE;
};
FillInControlPoints[seq]; -- after all is said and done
};
CreateEmpty:
PUBLIC
PROC [traj: Traj]
RETURNS [seq: Sequence] = {
seq ←
NEW[SequenceObj ← [
traj: traj,
boundBox: NIL,
segments: NewBitVector[traj.segCount],
joints: NewBitVector[GGTraj.HiJoint[traj]+1],
controlPoints: NewBitMatrix[traj],
segCount: 0,
controlPointCount: 0,
jointCount: 0
]];
};
CreateComplete:
PUBLIC
PROC [traj: Traj]
RETURNS [seq: Sequence] = {
Returns a sequence which represents the entire trajectory.
jointCount: NAT ← GGTraj.HiJoint[traj] + 1;
seq ←
NEW[SequenceObj ← [
traj: traj,
boundBox: IF traj.boundBox = NIL THEN NIL ELSE GGBoundBox.CopyBoundBox[traj.boundBox],
segments: NewBitVector[traj.segCount],
joints: NewBitVector[jointCount],
controlPoints: NewBitMatrix[traj],
segCount: traj.segCount,
controlPointCount: 0, -- set by FillInControlPoints
jointCount: jointCount
]];
FOR i:
NAT
IN [0..GGTraj.HiSegment[traj]]
DO
seq.segments[i] ← TRUE;
seq.joints[i] ← TRUE;
ENDLOOP;
seq.joints[jointCount-1] ← TRUE; -- will be redundant for open trajectories
FillInControlPoints[seq]; -- after all is said and done
};
CreateFromJoint:
PUBLIC
PROC [traj: Traj, jointNum:
NAT]
RETURNS [seq: Sequence] = {
seq ← CreateEmpty[traj];
seq.joints[jointNum] ← TRUE;
seq.jointCount ← 1;
};
CreateFromSegment:
PUBLIC
PROC [traj: Traj, segNum:
NAT]
RETURNS [seq: Sequence] = {
seq ← CreateEmpty[traj];
seq.segments[segNum] ← TRUE;
seq.segCount ← 1;
FillInJoints[seq];
FillInControlPoints[seq]; -- after all is said and done
};
CreateSimpleFromSegment:
PUBLIC
PROC [traj: Traj, segNum:
NAT]
RETURNS [seq: Sequence] = {
seq ← CreateEmpty[traj];
seq.segments[segNum] ← TRUE;
seq.segCount ← 1;
};
CreateFromControlPoint:
PUBLIC
PROC [traj: Traj, segNum:
NAT, controlPointNum:
NAT]
RETURNS [seq: Sequence] = {
seq ← CreateEmpty[traj];
seq.controlPoints[segNum][controlPointNum] ← TRUE;
seq.controlPointCount ← 1;
};
Copy:
PUBLIC
PROC [seq: Sequence]
RETURNS [copy: Sequence] = {
hiSegment: NAT;
IF IsObsolete[seq] THEN ERROR;
hiSegment ← GGTraj.HiSegment[seq.traj];
copy ←
NEW[SequenceObj ← [
traj: seq.traj,
boundBox: NIL,
segments: NewBitVector[seq.traj.segCount],
joints: NewBitVector[GGTraj.HiJoint[seq.traj]+1],
controlPoints: NewBitMatrix[seq.traj],
segCount: seq.segCount,
controlPointCount: seq.controlPointCount,
jointCount: seq.jointCount
]];
FOR i:
NAT
IN [0..hiSegment]
DO
cpCount: NAT ← seq.controlPoints[i].len;
copy.segments[i] ← seq.segments[i];
copy.joints[i] ← seq.joints[i];
FOR j:
NAT
IN [0..cpCount)
DO
copy.controlPoints[i][j] ← seq.controlPoints[i][j]; -- KAP. April 4, 1986
ENDLOOP;
ENDLOOP;
IF seq.traj.role = open THEN copy.joints[hiSegment + 1] ← seq.joints[hiSegment + 1];
Augment:
PUBLIC
PROC [seq: Sequence, trajEnd: TrajEnd, extend:
BOOL]
RETURNS [bigger: Sequence] = {
A segment (and joint) have been added to one end (the trajEnd end) of seq.traj, making seq obsolete. Create a new sequence bigger which refers to the same joints and segments that seq did, but for the new trajectory. If extend is TRUE, then bigger will include the newly added segment if seq included the old joint which it was attached to.
IF seq.traj.role = hole
OR seq.traj.role = fence
THEN {
bigger ← AugmentClosed[seq, extend];
RETURN;
};
bigger ←
NEW[SequenceObj ← [
traj: seq.traj,
boundBox: NIL,
segments: NewBitVector[seq.segments.len+1],
joints: NewBitVector[seq.joints.len+1],
controlPoints: NewBitMatrix[seq.traj], -- new BitMatrix one segment bigger
segCount: seq.segCount,
controlPointCount: seq.controlPointCount,
jointCount: seq.jointCount
]];
IF trajEnd = hi
THEN {
FOR i:
NAT
IN [0..seq.segments.len)
DO
cpCount: NAT ← seq.controlPoints[i].len;
bigger.segments[i] ← seq.segments[i];
bigger.joints[i] ← seq.joints[i];
FOR j:
NAT
IN [0..cpCount)
DO
bigger.controlPoints[i][j] ← seq.controlPoints[i][j]; -- KAP. April 4, 1986
ENDLOOP;
ENDLOOP;
At this point bigger.segCount, bigger.jointCount, bigger.controlPointCount are consistent with the segments, joints, and controlPoints bit vectors.
IF seq.joints[seq.joints.len - 1]
THEN {
-- final joint included ??
bigger.joints[seq.joints.len - 1] ← TRUE; -- yes, so include it in bigger
IF extend
THEN {
bigger.segments[seq.segments.len] ← TRUE;
bigger.joints[seq.joints.len] ← TRUE;
SetAllBits[bigger.controlPoints[seq.segments.len], TRUE];
bigger.segCount ← bigger.segCount + 1;
bigger.jointCount ← bigger.jointCount + 1;
bigger.controlPointCount ← bigger.controlPointCount + bigger.controlPoints[seq.segments.len].len
};
};
}
ELSE {
FOR i:
NAT
IN [0..seq.segments.len)
DO
cpCount: NAT ← seq.controlPoints[i].len;
bigger.segments[i+1] ← seq.segments[i];
bigger.joints[i+2] ← seq.joints[i+1];
FOR j:
NAT
IN [0..cpCount)
DO
bigger.controlPoints[i+1][j] ← seq.controlPoints[i][j]; -- KAP. April 4, 1986
ENDLOOP;
ENDLOOP;
At this point bigger.segCount, bigger.jointCount, bigger.controlPointCount are consistent with the segments, joints, and controlPoints bit vectors.
IF seq.joints[0]
THEN {
-- first joint included ??
bigger.joints[1] ← TRUE; -- yes, so include it in bigger
IF extend
THEN {
bigger.segments[0] ← TRUE;
bigger.joints[0] ← TRUE;
SetAllBits[bigger.controlPoints[0], TRUE];
bigger.segCount ← bigger.segCount + 1;
bigger.jointCount ← bigger.jointCount + 1;
bigger.controlPointCount ← bigger.controlPointCount + bigger.controlPoints[0].len
};
};
};
};
AugmentClosed:
PUBLIC
PROC [seq: Sequence, extend:
BOOL]
RETURNS [bigger: Sequence] = {
A segment has been added to one end (the high end) of seq.traj, making seq obsolete. Create a new sequence bigger which refers to the same joints and segments that seq did, but for the new trajectory. If extend is TRUE, then bigger will include the newly added segment if seq included the old joint which it was attached to.
bigger ←
NEW[SequenceObj ← [
traj: seq.traj,
boundBox: NIL,
segments: NewBitVector[seq.segments.len+1],
joints: NewBitVector[seq.joints.len],
controlPoints: NewBitMatrix[seq.traj], -- new BitMatrix one segment bigger
segCount: seq.segCount,
controlPointCount: seq.controlPointCount,
jointCount: seq.jointCount
]];
FOR i:
NAT
IN [0..seq.segments.len)
DO
cpCount: NAT ← seq.controlPoints[i].len;
bigger.segments[i] ← seq.segments[i];
bigger.joints[i] ← seq.joints[i];
FOR j:
NAT
IN [0..cpCount)
DO
bigger.controlPoints[i][j] ← seq.controlPoints[i][j]; -- KAP. April 4, 1986
ENDLOOP;
ENDLOOP;
IF seq.joints[seq.joints.len - 1]
THEN {
-- final joint included ??
bigger.joints[seq.joints.len - 1] ← TRUE; -- yes, so include it in bigger
At this point bigger.segCount, bigger.jointCount, bigger.controlPointCount are consistent with the segments, joints, and controlPoints bit vectors.
IF extend
THEN {
bigger.segments[seq.segments.len] ← TRUE;
SetAllBits[bigger.controlPoints[seq.segments.len], TRUE];
bigger.segCount ← bigger.segCount + 1;
bigger.controlPointCount ← bigger.controlPointCount + bigger.controlPoints[seq.segments.len].len;
};
};
};
Bounding Box
UpdateBoundBox:
PUBLIC
PROC [seq: Sequence] = {
seq.boundBox ← ComputeBoundBox[seq];
};
ComputeBoundBox:
PUBLIC
PROC [seq: Sequence]
RETURNS [box: BoundBox] = {
halfJointSize: REAL = GGModelTypes.halfJointSize + 1;
Algorithm:
ForAllJointsInSeq, if joint does not touch a segmentInSeq then update bound box with joint bound box.
ForAllCPInSeq, update bound box with cp bound box.
ForAllSegsInSeq, update bound box with segment bound box.
Sequences often arrives here with seq.boundBox = copy of their traj.boundBox (and thus too big), or with seq.boundBox=NIL. We ignore the current contents and calculate the update from scratch.
traj: Traj ← seq.traj;
box ← GGBoundBox.NullBoundBox[];
ForAllJointsInSeq, if joint does not touch a segmentInSeq then update bound box with joint bound box.
IF seq.jointCount#0
THEN {
-- ForAllJointsInTraj
IF traj.role = open
THEN {
-- ForAllJointsInOpenTraj
IF seq.joints[0] AND NOT seq.segments[0] THEN UpdateBySquare[box, GGTraj.FetchJointPos[traj, 0], halfJointSize]; -- boundary case for joint 0
FOR i:
NAT
IN [1..traj.segCount-1]
DO
-- loop for inner joints
IF seq.joints[i] AND NOT seq.segments[i] AND NOT seq.segments[i-1] THEN UpdateBySquare[box, GGTraj.FetchJointPos[traj, i], halfJointSize];
ENDLOOP;
IF seq.joints[traj.segCount] AND NOT seq.segments[traj.segCount-1] THEN UpdateBySquare[box, GGTraj.FetchJointPos[traj, traj.segCount], halfJointSize]; -- boundary case for last joint
}
ELSE {
-- ForAllJointsInClosedTraj
FOR i:
NAT
IN [0..seq.traj.segCount-1]
DO
IF seq.joints[i] AND NOT seq.segments[i] AND NOT seq.segments[(i -1 + seq.traj.segCount) MOD seq.traj.segCount] THEN UpdateBySquare[box, GGTraj.FetchJointPos[traj, i], halfJointSize];
ENDLOOP;
};
};
ForAllCPInSeq, update bound box with cp bound box.
IF seq.controlPointCount#0
THEN {
-- if some control point is in the sequence then ...
FOR i:
NAT
IN [0..seq.traj.segCount)
DO
-- for each segment in the traj
IF
NOT seq.segments[i]
AND SomeSegCPInSeq[i, seq]
THEN {
-- if this segment is not already in the sequence and any control point of this segment is selected then ...
seg: Segment ← GGTraj.FetchSegment[traj, i]; -- get the segment
cpCount: NAT ← seq.controlPoints[i].len;
FOR j:
NAT
IN [0..cpCount)
DO
-- for all control points in the segment
IF seq.controlPoints[i][j]
THEN {
-- if this cp is in the sequence
point: Point ← seg.class.controlPointGet[seg, j];
UpdateBySquare[box, point, halfJointSize];
-- update the bounding box with the control point
};
ENDLOOP;
};
ENDLOOP;
};
ForAllSegsInSeq, update bound box with segment bound box.
IF seq.segCount#0
THEN {
-- if some segment is in the sequence
FOR s:
NAT
IN [0..seq.traj.segCount-1]
DO
-- for each segment in the traj
IF seq.segments[s]
THEN {
-- if this segment is in the sequence
seg: Segment ← GGTraj.FetchSegment[traj, s]; -- get the segment
GGBoundBox.EnlargeByBox[bBox: box, by: seg.class.boundBox[seg]]; -- update the bounding box with the segment
};
ENDLOOP;
};
seq.boundBox ← box; -- and, finally, store the new result
};
ComputeTightBox:
PUBLIC
PROC [seq: Sequence]
RETURNS [box: BoundBox] = {
halfJointSize: REAL = GGModelTypes.halfJointSize + 1;
Algorithm:
ForAllSegsInSeq, update bound box with segment tight box.
traj: Traj ← seq.traj;
box ← GGBoundBox.NullBoundBox[];
ForAllSegsInSeq, update bound box with segment bound box.
IF seq.segCount#0
THEN {
FOR s:
NAT
IN [0..seq.traj.segCount-1]
DO
-- for each segment in the traj
IF seq.segments[s]
THEN {
-- if this segment is in the sequence
seg: Segment ← GGTraj.FetchSegment[traj, s];
GGBoundBox.EnlargeByBox[bBox: box, by: seg.class.tightBox[seg]];
};
ENDLOOP;
};
seq.boundBox ← box; -- and, finally, store the new result
};
Procedures which mutate Segments (use with caution)
CopyInto:
PUBLIC
PROC [to: Sequence, from: Sequence] = {
hiSegment: NAT;
IF IsObsolete[from] THEN ERROR;
hiSegment ← GGTraj.HiSegment[from.traj];
to.traj ← from.traj;
to.boundBox ← NIL;
FOR i:
NAT
IN [0..GGTraj.HiSegment[from.traj]]
DO
cpCount: NAT ← from.controlPoints[i].len;
to.segments[i] ← from.segments[i];
FOR j:
NAT
IN [0..cpCount)
DO
to.controlPoints[i][j] ← from.controlPoints[i][j]; -- KAP. April 4, 1986
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..GGTraj.HiJoint[from.traj]]
DO
to.joints[i] ← from.joints[i];
ENDLOOP;
to.segCount ← from.segCount;
to.controlPointCount ← from.controlPointCount;
to.jointCount ← from.jointCount;
FillInJoints:
PUBLIC
PROC [seq: Sequence] = {
a sequence with segments filled in. Fill in all the joints for each segment in the sequence, and calculate the new joint count. Leave in all isolated joints as well.
jointCount: NAT ← 0;
IF IsObsolete[seq] THEN ERROR;
IF seq.segCount=0 THEN RETURN; -- can't do anything. seq may have a single joint or CP
FOR j: NAT IN [0..seq.joints.len) DO seq.joints[j] ← FALSE; ENDLOOP;
IF seq.traj.role = open
THEN {
FOR i:
NAT
IN [0..seq.traj.segCount-1]
DO
IF seq.segments[i] THEN {seq.joints[i] ← TRUE; seq.joints[i+1] ← TRUE};
ENDLOOP;
}
ELSE {
FOR i:
NAT
IN [0..seq.traj.segCount-1]
DO
IF seq.segments[i] THEN {seq.joints[i] ← TRUE; seq.joints[(i+1) MOD seq.traj.segCount] ← TRUE;};
ENDLOOP;
};
FOR i:
NAT
IN [0..GGTraj.HiJoint[seq.traj]]
DO
IF seq.joints[i] THEN jointCount ← jointCount + 1;
ENDLOOP;
seq.jointCount ← jointCount;
FillInControlPoints:
PUBLIC
PROC [seq: Sequence] = {
-- a sequence with segs and joints filled in. IF there are segments then fill in all the control points for each segment in the sequence, and calculate the new control point count.
segGen: SegmentGenerator;
next: SegAndIndex;
cpCount: NAT;
IF IsObsolete[seq] THEN ERROR; -- expensive, June 24, 1986, Bier
IF seq.segCount=0 THEN RETURN; -- can't do anything. seq may have a single joint or CP.
seq.controlPointCount ← 0;
segGen ← SegmentsInSequence[seq];
FOR next ←
NextSegmentAndIndex[segGen],
NextSegmentAndIndex[segGen]
UNTIL next.seg=
NIL
DO
IF NOT seq.segments[next.index] THEN ERROR; -- seq must have this seg, by definition
cpCount ← next.seg.class.controlPointCount[next.seg]; -- number of cps in this segment
FOR j:
NAT
IN [0..cpCount)
DO
-- fill them all in
seq.controlPoints[next.index][j] ← TRUE;
seq.controlPointCount ← seq.controlPointCount + 1;
ENDLOOP;
ENDLOOP;
};
TrimSelectedParts:
PUBLIC
PROC [seq: Sequence, selectedList:
LIST
OF
REF
ANY] = {
Modifies, mutes, and munges seq, so that it no longer includes any parts mentioned in selectedList. Used by GGAlign.RemoveMoving.
selSeq: Sequence;
selSeq ← GGSelect.FindSequenceInList[seq.traj, selectedList];
IF selSeq = NIL THEN RETURN; -- no selected parts, so nothing to trim
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
FOR j:
NAT
IN [0..seq.controlPoints[i].len)
DO
IF selSeq.controlPoints[i][j]
AND seq.controlPoints[i][j]
THEN {
seq.controlPoints[i][j] ← FALSE;
seq.controlPointCount ← seq.controlPointCount - 1;
};
ENDLOOP;
IF selSeq.segments[i]
AND seq.segments[i]
THEN {
seq.segments[i] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
FOR i:
NAT
IN [0..GGTraj.HiJoint[seq.traj]]
DO
IF selSeq.joints[i]
AND seq.joints[i]
THEN {
seq.joints[i] ← FALSE;
seq.jointCount ← seq.jointCount -1;
};
ENDLOOP;
};
TrimSelectedControlPointSegments:
PUBLIC
PROC [seq: Sequence, selectedList:
LIST
OF
REF
ANY] = {
Modifies, mutes, and munges seq, so that it no longer includes any segments whose control points are mentioned in selectedList. Used by GGAlign.RemoveMoving.
SomeSelectedCP:
PROC [i:
NAT]
RETURNS [
BOOL] = {
FOR j:
NAT
IN [0..selSeq.controlPoints[i].len)
DO
IF selSeq.controlPoints[i][j] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
selSeq: Sequence;
selSeq ← GGSelect.FindSequenceInList[seq.traj, selectedList];
IF selSeq = NIL THEN RETURN; -- no CPs selected, so nothing to trim
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i]
AND SomeSelectedCP[i]
THEN {
seq.segments[i] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
};
TrimSelectedJointSegments:
PUBLIC
PROC [seq: Sequence, selectedList:
LIST
OF
REF
ANY] = {
Modifies, mutes, and munges seq, so that it no longer includes any segments whose joints are mentioned in selectedList. Used by GGAlign.RemoveMoving.
SomeSelectedJoint:
PROC [i:
NAT]
RETURNS [
BOOL] = {
RETURN[
selSeq.joints[i] OR selSeq.joints[GGTraj.FollowingJoint[seq.traj, i]]
];
};
selSeq: Sequence;
selSeq ← GGSelect.FindSequenceInList[seq.traj, selectedList];
IF selSeq = NIL THEN RETURN; -- no joints selected, so nothing to trim
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i]
AND SomeSelectedJoint[i]
THEN {
seq.segments[i] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
};
TrimDanglingSegments:
PUBLIC
PROC [seq: Sequence] = {
For all runs in seq, if either end of the run is a segment (not a joint), remove that segment.
runGen: SequenceGenerator;
runCount: NAT;
haveTrimmed: BOOL;
firstSegNum, firstJointNum, lastSegNum, lastJointNum: INT;
IF IsComplete[seq] THEN RETURN; -- nothing is dangling if all joints are included
[runGen, runCount] ← RunsInSequence[seq];
FOR run: Sequence ← NextSequence[runGen], NextSequence[runGen]
UNTIL run =
NIL
DO
haveTrimmed ← FALSE;
firstSegNum ← FirstSegNum[run];
firstJointNum ← FirstJointNum[run];
lastSegNum ← LastSegNum[run, firstSegNum];
lastJointNum ← LastJointNum[run, firstJointNum];
IF firstJointNum = -1
THEN {
there are no joints in the run. It only has one segment. Remove that segment.
IF firstSegNum = -1 THEN ERROR; -- there must be something in the run
IF NOT seq.segments[firstSegNum] THEN ERROR;
seq.segments[firstSegNum] ← FALSE;
seq.segCount ← seq.segCount - 1;
LOOP;
};
IF lastJointNum = -1 THEN ERROR; -- if there was a first joint, there must be a last one (it is equal to the first joint if there is only one).
IF firstSegNum = -1 THEN LOOP; -- there are no segments so there is nothing to trim
IF lastSegNum = -1 THEN ERROR; -- if there was a first segment, there must be a last.
Assert: If we reach this point, there is at least one joint and at least one segment.
IF firstJointNum # firstSegNum
THEN {
IF NOT seq.segments[lastSegNum] THEN ERROR;
seq.segments[firstSegNum] ← FALSE;
seq.segCount ← seq.segCount - 1;
haveTrimmed ← TRUE;
};
IF ((seq.traj.role = open
AND lastSegNum + 1 # lastJointNum)
OR
(seq.traj.role # open AND ((lastSegNum + 1) MOD seq.traj.segCount) # lastJointNum))
AND (
NOT haveTrimmed
OR lastSegNum # firstSegNum)
THEN {
IF NOT seq.segments[lastSegNum] THEN ERROR;
seq.segments[lastSegNum] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
};
TrimControlPointSegments:
PUBLIC
PROC [seq: Sequence, controlPointOn:
BOOL] = {
trim segments with any included control points
SomeIncludedCP:
PROC [i:
NAT]
RETURNS [
BOOL] = {
FOR j:
NAT
IN [0..seq.controlPoints[i].len)
DO
IF seq.controlPoints[i][j] = controlPointOn THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
IF IsObsolete[seq] THEN ERROR;
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i]
AND SomeIncludedCP[i]
THEN {
seq.segments[i] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
};
TrimJointSegments:
PUBLIC
PROC [seq: Sequence, jointOn:
BOOL] = {
If jointOn then for all segments in seq, remove those that have a joint mentioned in seq. Otherwise, remove those segments that do NOT have a joint mentioned.
SomeSelectedJoint:
PROC [i:
NAT]
RETURNS [
BOOL] = {
RETURN[
seq.joints[i] = jointOn OR seq.joints[GGTraj.FollowingJoint[seq.traj, i]] = jointOn
];
};
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i]
AND SomeSelectedJoint[i]
THEN {
seq.segments[i] ← FALSE;
seq.segCount ← seq.segCount - 1;
};
ENDLOOP;
};
DDifference:
PUBLIC
PROC [mutable, negative: Sequence] = {
This is a destructive form of the Difference operation. mutable ← mutable - negative.
hiJoint: NAT;
IF IsObsolete[mutable] OR IsObsolete[negative] THEN ERROR;
IF mutable.traj # negative.traj THEN ERROR;
FOR i:
NAT
IN [0..GGTraj.HiSegment[mutable.traj]]
DO
cpCount: NAT ← mutable.controlPoints[i].len;
mutable.segments[i] ← mutable.segments[i] AND NOT negative.segments[i];
FOR j:
NAT
IN [0..cpCount)
DO
mutable.controlPoints[i][j] ← mutable.controlPoints[i][j] AND NOT negative.controlPoints[i][j];
ENDLOOP;
mutable.joints[i] ← mutable.joints[i] AND NOT negative.joints[i];
ENDLOOP;
hiJoint ← GGTraj.HiJoint[mutable.traj];
mutable.joints[hiJoint] ← mutable.joints[hiJoint] AND NOT negative.joints[hiJoint];
mutable.segCount ← CountSegments[mutable];
mutable.jointCount ← CountJoints[mutable];
mutable.controlPointCount ← CountControlPoints[mutable];
};
Utility Routines
NewBitMatrix:
PROC [traj: Traj]
RETURNS [bitMatrix: BitMatrix] = {
j: NAT ← 0;
segGen: SegmentGenerator ← GGSequence.SegmentsInTraj[traj];
bitMatrix ← NEW[BitMatrixObj[traj.segCount]];
FOR seg: Segment ← GGSequence.NextSegment[segGen], GGSequence.NextSegment[segGen]
UNTIL seg =
NIL
DO
bitMatrix[j] ← NewBitVector[seg.class.controlPointCount[seg]];
j ← j+1;
ENDLOOP;
};
NewBitVector:
PROC [length:
NAT]
RETURNS [bitVec: BitVector] = {
bitVec ← NEW[BitVectorObj[length]];
SetAllBits[bitVec, FALSE];
};
SetAllBits:
PROC [bitVec: BitVector, bool:
BOOL] = {
FOR i:
NAT
IN [0..bitVec.len)
DO
bitVec[i] ← bool;
ENDLOOP;
};
SomeSegCPInSeq:
PROC [segNum:
NAT, seq: Sequence]
RETURNS [
BOOL] = {
cpCount: NAT ← seq.controlPoints[segNum].len;
FOR j:
NAT
IN [0..cpCount)
DO
IF seq.controlPoints[segNum][j] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
UpdateBySquare:
PROC [bBox: BoundBox, p: Point, halfSquareSide:
REAL] ~ {
-- updates the accumulating bBox by a joint or CP
pHalf: REAL ← halfSquareSide + 1;
loX, loY, hiX, hiY: REAL;
IF bBox.infinite THEN RETURN;
loX ← p.x-pHalf; loY ← p.y-pHalf; hiX ← p.x+pHalf; hiY ← p.y+pHalf;
IF bBox.null
THEN {
bBox.loX ← loX;
bBox.hiX ← hiX;
bBox.loY ← loY;
bBox.hiY ← hiY;
bBox.null ← FALSE;
RETURN;
};
IF loX < bBox.loX THEN bBox.loX ← loX;
IF hiX > bBox.hiX THEN bBox.hiX ← hiX;
IF loY < bBox.loY THEN bBox.loY ← loY;
IF hiY > bBox.hiY THEN bBox.hiY ← hiY;
};
Boolean Operations on Sequences
Union:
PUBLIC
PROC [a, b: Sequence]
RETURNS [union: Sequence] = {
hiJoint: NAT;
IF IsObsolete[a] OR IsObsolete[b] THEN ERROR;
IF a.traj # b.traj THEN ERROR;
union ← CreateEmpty[a.traj];
FOR i:
NAT
IN [0..GGTraj.HiSegment[a.traj]]
DO
cpCount: NAT ← a.controlPoints[i].len;
union.segments[i] ← a.segments[i] OR b.segments[i];
FOR j:
NAT
IN [0..cpCount)
DO
union.controlPoints[i][j] ← a.controlPoints[i][j] OR b.controlPoints[i][j];
ENDLOOP;
union.joints[i] ← a.joints[i] OR b.joints[i];
ENDLOOP;
hiJoint ← GGTraj.HiJoint[a.traj];
union.joints[hiJoint] ← a.joints[hiJoint] OR b.joints[hiJoint];
union.segCount ← CountSegments[union];
union.jointCount ← CountJoints[union];
union.controlPointCount ← CountControlPoints[union];
};
Difference:
PUBLIC
PROC [a, b: Sequence]
RETURNS [aMinusB: Sequence] = {
hiJoint: NAT;
IF IsObsolete[a] OR IsObsolete[b] THEN ERROR;
IF a.traj # b.traj THEN ERROR;
aMinusB ← CreateEmpty[a.traj];
FOR i:
NAT
IN [0..GGTraj.HiSegment[a.traj]]
DO
cpCount: NAT ← a.controlPoints[i].len;
aMinusB.segments[i] ← a.segments[i] AND NOT b.segments[i];
FOR j:
NAT
IN [0..cpCount)
DO
aMinusB.controlPoints[i][j] ← a.controlPoints[i][j] AND NOT b.controlPoints[i][j];
ENDLOOP;
aMinusB.joints[i] ← a.joints[i] AND NOT b.joints[i];
ENDLOOP;
hiJoint ← GGTraj.HiJoint[a.traj];
aMinusB.joints[hiJoint] ← a.joints[hiJoint] AND NOT b.joints[hiJoint];
aMinusB.segCount ← CountSegments[aMinusB];
aMinusB.jointCount ← CountJoints[aMinusB];
aMinusB.controlPointCount ← CountControlPoints[aMinusB];
};
Intersection:
PUBLIC
PROC [a, b: Sequence]
RETURNS [intersection: Sequence] = {
hiJoint: NAT;
IF IsObsolete[a] OR IsObsolete[b] THEN ERROR;
IF a.traj # b.traj THEN ERROR;
intersection ← CreateEmpty[a.traj];
FOR i:
NAT
IN [0..GGTraj.HiSegment[a.traj]]
DO
cpCount: NAT ← a.controlPoints[i].len;
intersection.segments[i] ← a.segments[i] AND b.segments[i];
FOR j:
NAT
IN [0..cpCount)
DO
intersection.controlPoints[i][j]← a.controlPoints[i][j] AND b.controlPoints[i][j];
ENDLOOP;
intersection.joints[i] ← a.joints[i] AND b.joints[i];
ENDLOOP;
hiJoint ← GGTraj.HiJoint[a.traj];
intersection.joints[hiJoint] ← a.joints[hiJoint] AND b.joints[hiJoint];
intersection.segCount ← CountSegments[intersection];
intersection.jointCount ← CountJoints[intersection];
intersection.controlPointCount ← CountControlPoints[intersection];
};
Queries
IsObsolete:
PUBLIC
PROC [seq: Sequence]
RETURNS [
BOOL] = {
TEST if this sequence cannot possibly encode its trajectory, probably because the trajectory has been modified. Not a guarantee that it accurately encodes anything.
j: NAT ← 0;
segGen: SegmentGenerator;
IF seq.segments.len # seq.traj.segCount THEN RETURN[TRUE];
IF seq.joints.len # (GGTraj.HiJoint[seq.traj] + 1) THEN RETURN[TRUE];
segGen ← SegmentsInTraj[seq.traj];
FOR nextSeg: Segment ← GGSequence.NextSegment[segGen], GGSequence.NextSegment[segGen]
UNTIL nextSeg=
NIL
DO
IF nextSeg.class.controlPointCount[nextSeg]#seq.controlPoints[j].len THEN RETURN[TRUE];
j ← j+1;
ENDLOOP;
RETURN[FALSE];
};
IsEmpty:
PUBLIC
PROC [seq: Sequence]
RETURNS [
BOOL] = {
RETURN[seq.jointCount = 0 AND seq.segCount = 0 AND seq.controlPointCount = 0];
};
ControlPointsOnly:
PUBLIC
PROC [seq: Sequence]
RETURNS [
BOOL] = {
RETURN[seq.jointCount = 0 AND seq.segCount = 0];
};
IsComplete:
PUBLIC
PROC [seq: Sequence]
RETURNS [
BOOL] = {
RETURN[seq.segCount = seq.traj.segCount
AND
(seq.jointCount = GGTraj.HiJoint[seq.traj] + 1)];
};
Overlap:
PUBLIC
PROC [seq1, seq2: Sequence]
RETURNS [
BOOL] = {
IF IsObsolete[seq1] OR IsObsolete[seq2] THEN ERROR;
IF seq1.traj # seq2.traj THEN ERROR;
Compare the segment bit vectors.
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq1.traj]]
DO
IF seq1.segments[i] AND seq2.segments[i] THEN RETURN[TRUE];
ENDLOOP;
Compare the joint bit vectors.
FOR i:
NAT
IN [0..GGTraj.HiJoint[seq1.traj]]
DO
IF seq1.joints[i] AND seq2.joints[i] THEN RETURN[TRUE];
ENDLOOP;
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq1.traj]]
DO
cpCount: NAT ← seq1.controlPoints[i].len;
FOR j:
NAT
IN [0..cpCount)
DO
IF seq1.controlPoints[i][j] AND seq2.controlPoints[i][j] THEN RETURN[TRUE];
ENDLOOP;
ENDLOOP;
RETURN[FALSE];
};
CountSegments:
PROC [seq: Sequence]
RETURNS [segCount:
NAT] = {
segCount ← 0;
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i] THEN segCount ← segCount + 1;
ENDLOOP;
};
CountJoints:
PROC [seq: Sequence]
RETURNS [jointCount:
NAT] = {
jointCount ← 0;
FOR i:
NAT
IN [0..GGTraj.HiJoint[seq.traj]]
DO
IF seq.joints[i] THEN jointCount ← jointCount + 1;
ENDLOOP;
};
CountControlPoints:
PROC [seq: Sequence]
RETURNS [count:
NAT ← 0] = {
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
cpCount: NAT ← seq.controlPoints[i].len;
FOR j:
NAT
IN [0..cpCount)
DO
IF seq.controlPoints[i][j] THEN count ← count + 1;
ENDLOOP;
ENDLOOP;
};
ContainsSegment:
PUBLIC
PROC [seq: Sequence, segNum:
NAT]
RETURNS [
BOOL] = {
RETURN[seq.segments[segNum]];
};
ContainsSegmentParts:
PUBLIC
PROC [seq: Sequence, segNum:
NAT]
RETURNS [
BOOL] = {
Returns TRUE if the sequence contains any part of a segment, including its end joints, its control points, or the segment proper.
RETURN [seq#
NIL
AND (seq.segments[segNum]
OR
NOT GGUtility.AllFalse[seq.controlPoints[segNum]] OR
seq.joints[segNum] OR
seq.joints[IF seq.traj.role=open THEN segNum+1 ELSE (segNum+1) MOD seq.traj.segCount]) ];
};
FirstSegment:
PROC [seq: Sequence]
RETURNS [index:
NAT] ~ {
hiSeg: NAT ← GGTraj.HiSegment[seq.traj];
IF IsObsolete[seq] THEN ERROR;
IF seq.traj.role = open
THEN {
FOR i:
NAT
IN [0..hiSeg]
DO
IF seq.segments[i] THEN GOTO Found;
REPEAT
Found => index ← i;
FINISHED => SIGNAL Problem[msg: "the first run begins with a segment."];
ENDLOOP;
}
ELSE {
FOR i:
NAT
IN [0..hiSeg]
DO
IF NOT seq.segments[(i - 1 + seq.traj.segCount) MOD seq.traj.segCount] AND seq.joints[i] THEN GOTO Found;
IF NOT seq.joints[i] AND seq.segments[i] THEN GOTO Found;
REPEAT
Found => index ← i;
FINISHED => SIGNAL Problem[msg: "there is no break in the sequence."];
ENDLOOP;
};
};
FirstSegNum:
PUBLIC
PROC [run: Sequence]
RETURNS [
INT] = {
run had better be a run (a single non-empty contiguous sequence).
IF run.segCount = 0 THEN RETURN[-1];
IF GGSequence.IsComplete[run] THEN RETURN[0]; --DJK, to make work with complete, closed sequences
RETURN[FirstTransitionInRun[run]];
};
LastSegNum:
PUBLIC
PROC [run: Sequence, firstSegNum:
INT]
RETURNS [lastNum:
INT] = {
run had better be a run (a single non-empty contiguous sequence).
IF firstSegNum = -1 THEN RETURN[-1];
IF run.traj.role = open THEN lastNum ← firstSegNum + run.segCount - 1
ELSE lastNum ← (firstSegNum + run.segCount - 1 + run.traj.segCount) MOD run.traj.segCount;
};
ContainsJoint:
PUBLIC
PROC [seq: Sequence, jointNum:
NAT]
RETURNS [
BOOL] = {
RETURN[seq.joints[jointNum]];
};
FirstJointNum:
PUBLIC
PROC [run: Sequence]
RETURNS [
INT] = {
run had better be a run (a single non-empty contiguous sequence).
firstSeg, nextJoint: NAT;
IF run.jointCount = 0 THEN RETURN[-1];
firstSeg ← FirstTransitionInRun[run];
IF run.joints[firstSeg]
THEN
RETURN[firstSeg]
ELSE {
IF run.traj.role = open
THEN {
IF run.joints[firstSeg + 1] THEN RETURN[firstSeg + 1]
ELSE ERROR Problem[msg: "Broken invariant."];
}
ELSE {
nextJoint ← GGTraj.FollowingJoint[run.traj, firstSeg];
IF run.joints[nextJoint] THEN RETURN[nextJoint]
ELSE ERROR Problem[msg: "Broken invariant."];
};
};
};
LastJointNum:
PUBLIC
PROC [run: Sequence, firstJointNum:
INT]
RETURNS [lastNum:
INT] = {
IF firstJointNum = -1 THEN RETURN[-1];
IF run.traj.role = open THEN lastNum ← firstJointNum + run.jointCount - 1
ELSE lastNum ← (firstJointNum + run.jointCount - 1 + run.traj.segCount) MOD run.traj.segCount;
};
LastSegAndJoint:
PUBLIC
PROC [traj: Traj, trajEnd: TrajEnd]
RETURNS [segAndJoint: Sequence] = {
segAndJoint ← CreateEmpty[traj];
IF traj.role = open
THEN {
segAndJoint.jointCount ← 1;
segAndJoint.segCount ← 1;
IF trajEnd = lo
THEN {
segAndJoint.segments[0] ← TRUE;
segAndJoint.joints[0] ← TRUE;
}
ELSE {
hiSeg: NAT ← GGTraj.HiSegment[traj];
segAndJoint.segments[hiSeg] ← TRUE;
segAndJoint.joints[hiSeg+1] ← TRUE;
};
}
ELSE ERROR;
};
UnpackOnePointSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [isACP:
BOOL, segNum, cpNum, jointNum:
NAT] = {
seq is asserted to be either a single joint or a single control point. Return the [segNum, cpNum] pair or the jointNum as appropriate.
seg: Segment;
FOR i:
NAT
IN [0..GGTraj.HiJoint[seq.traj]]
DO
IF seq.joints[i]
THEN {
isACP ← FALSE;
segNum ← 999;
cpNum ← 999;
jointNum ← i;
RETURN;
}
ENDLOOP;
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
seg ← GGTraj.FetchSegment[seq.traj, i];
FOR j:
NAT
IN [0..seg.class.controlPointCount[seg] - 1]
DO
IF seq.controlPoints[i][j]
THEN {
isACP ← TRUE;
segNum ← i;
cpNum ← j;
jointNum ← 999;
RETURN;
}
ENDLOOP;
ENDLOOP;
ERROR;
};
UnpackOneSegmentSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [segNum:
NAT] = {
FOR i:
NAT
IN [0..GGTraj.HiSegment[seq.traj]]
DO
IF seq.segments[i]
THEN {
segNum ← i;
RETURN;
}
ENDLOOP;
ERROR;
};
UnpackSimpleSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [success:
BOOL, partType: TrajPartType ← none, traj: Traj, joint: Joint ←
NIL, jointNum:
NAT ← 999, cp: Point ← [0,0], cpNum:
NAT ← 999, seg: Segment ←
NIL, segNum:
NAT ← 999] = {
jointFound, cpFound, segFound:
BOOL ← FALSE;
Look for a joint.
traj ← seq.traj;
FOR i:
NAT
IN [0..GGTraj.HiJoint[traj]]
DO
IF seq.joints[i]
THEN {
IF jointFound THEN {success ← FALSE; RETURN};
jointNum ← i;
joint ← GGTraj.FetchJoint[traj, i];
jointFound ← TRUE;
partType ← joint;
}
ENDLOOP;
FOR i:
NAT
IN [0..GGTraj.HiSegment[traj]]
DO
thisSeg: Segment ← GGTraj.FetchSegment[traj, i];
FOR j:
NAT
IN [0..thisSeg.class.controlPointCount[thisSeg])
DO
IF seq.controlPoints[i][j]
THEN {
IF cpFound THEN {success ← FALSE; RETURN};
segNum ← i;
seg ← thisSeg;
cpNum ← j;
cp ← thisSeg.class.controlPointGet[thisSeg, cpNum];
cpFound ← TRUE;
partType ← controlPoint;
}
ENDLOOP;
ENDLOOP;
IF jointFound AND cpFound THEN {success ← FALSE; RETURN};
FOR i:
NAT
IN [0..GGTraj.HiSegment[traj]]
DO
IF seq.segments[i]
THEN {
IF segFound THEN {success ← FALSE; RETURN};
segNum ← i;
seg ← GGTraj.FetchSegment[traj, i];
segFound ← TRUE;
partType ← segment;
}
ENDLOOP;
IF (jointFound AND segFound) OR (cpFound AND segFound) THEN {success ← FALSE; RETURN};
IF NOT jointFound AND NOT cpFound AND NOT segFound THEN ERROR;
success ← TRUE;
};
Generators
RunsInSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [seqGen: SequenceGenerator, runCount:
NAT] = {
A run is a sequence with only one contiguous piece. In other words, each joint in the run touches at least one segment in the run (unless the run is a single joint), and each segment in the run touches at least one joint in the run (unless the run is a single segment). The run whose lowest joint has the lowest index will be returned first by NextSequence. The other runs will follow in ascending order.
IF IsObsolete[seq] THEN ERROR;
IF seq.traj.role = open THEN [seqGen, runCount] ← RunsInSequenceOpen[seq]
ELSE [seqGen, runCount] ← RunsInSequenceClosed[seq];
};
RunsInSequenceOpen:
PROC [seq: Sequence]
RETURNS [seqGen: SequenceGenerator, runCount:
NAT] = {
in: BOOL ← FALSE;
thisSeq: Sequence;
hiSeg: NAT ← GGTraj.HiSegment[seq.traj];
hiJoint: NAT ← hiSeg + 1;
seqGen ← NEW[SequenceGeneratorObj ← [NIL]];
runCount ← 0;
IF IsEmpty[seq] THEN RETURN;
FOR i:
NAT
IN [0..hiSeg]
DO
[in, seqGen.list, thisSeq, runCount] ← ConsiderJoint[in, seqGen.list, seq, thisSeq, runCount, i];
[in, seqGen.list, thisSeq, runCount] ← ConsiderSegment[in, seqGen.list, seq, thisSeq, runCount, i];
ENDLOOP;
[in, seqGen.list, thisSeq, runCount] ← ConsiderJoint[in, seqGen.list, seq, thisSeq, runCount, hiJoint];
IF in THEN seqGen.list ← AppendToList[seqGen.list, CONS[thisSeq, NIL]];
};
RunsInSequenceClosed:
PROC [seq: Sequence]
RETURNS [seqGen: SequenceGenerator, runCount:
NAT] = {
This is done in two parts. First we find the first joint or segment that is preceded by a segment or joint that is not in the sequence. Then we proceed as for open but mod traj.segCount.
in: BOOL ← FALSE;
thisSeq: Sequence;
start: NAT;
natGen: NATGenerator;
seqGen ← NEW[SequenceGeneratorObj ← [NIL]];
runCount ← 0;
IF ControlPointsOnly[seq] THEN RETURN;
start ← FirstTransitionInRun[seq];
in ← FALSE;
natGen ← NATsInInterval[start, seq.traj.segCount, seq.traj.segCount];
FOR i:
INT ← NextNAT[natGen], NextNAT[natGen]
UNTIL i = -1
DO
[in, seqGen.list, thisSeq, runCount] ← ConsiderJoint[in, seqGen.list, seq, thisSeq, runCount, i];
[in, seqGen.list, thisSeq, runCount] ← ConsiderSegment[in, seqGen.list, seq, thisSeq, runCount, i];
ENDLOOP;
IF in THEN seqGen.list ← AppendToList[seqGen.list, CONS[thisSeq, NIL]];
};
NextSequence:
PUBLIC
PROC [seqGen: SequenceGenerator]
RETURNS [seq: Sequence] = {
IF seqGen.list = NIL THEN RETURN[NIL];
seq ← seqGen.list.first;
seqGen.list ← seqGen.list.rest;
};
FirstTransitionInRun:
PROC [seq: Sequence]
RETURNS [transitionNum:
NAT] = {
Finds the first transition from a joint that's not in the sequence to a segment in the sequence, or from a segment that's not in the sequence to a joint that's in the sequence. For example, with sequence 0 (0) 1 (1) 2 (2) 3 (3) 4, transition segment (1) -> joint 2 returns 2. joint 1 -> segment (2) returns 2. Hence, if the first run has any segments at all, transitionNum will be the number of the first segment.
hiSeg: NAT ← GGTraj.HiSegment[seq.traj];
IF seq.traj.role = open
THEN {
FOR i:
NAT
IN [0..hiSeg]
DO
IF seq.joints[i] THEN RETURN[i];
IF seq.segments[i] THEN RETURN[i];
ENDLOOP;
IF seq.joints[hiSeg+1] THEN RETURN[hiSeg+1];
SIGNAL Problem[msg: "there is no break in the sequence."];
}
ELSE {
FOR i:
NAT
IN [0..hiSeg]
DO
IF NOT seq.segments[(i -1 + seq.traj.segCount) MOD seq.traj.segCount] AND seq.joints[i] THEN GOTO FoundStart;
IF NOT seq.joints[i] AND seq.segments[i] THEN GOTO FoundStart;
REPEAT
FoundStart => transitionNum ← i;
FINISHED => SIGNAL Problem[msg: "there is no break in the sequence."];
ENDLOOP;
};
};
AppendToList:
PUBLIC
PROC [list1, list2:
LIST
OF Sequence]
RETURNS [result:
LIST
OF Sequence] = {
pos: LIST OF Sequence;
newCell: LIST OF Sequence;
Non-destructive (copies the first list).
IF list1 = NIL THEN RETURN[list2];
result ← CONS[list1.first, NIL];
pos ← result;
FOR l:
LIST
OF Sequence ← list1.rest, l.rest
UNTIL l =
NIL
DO
newCell ← CONS[l.first, NIL];
pos.rest ← newCell;
pos ← newCell;
ENDLOOP;
pos.rest ← list2;
};
ConsiderJoint:
PROC [in:
BOOL, list:
LIST
OF Sequence, seq: Sequence, thisSeq: Sequence, runCount:
NAT, i:
NAT]
RETURNS [newIn:
BOOL, newList:
LIST
OF Sequence, newThisSeq: Sequence, newCount:
NAT] = {
newIn ← in;
newList ← list;
newThisSeq ← thisSeq;
newCount ← runCount;
SELECT TRUE FROM
NOT seq.joints[i] AND NOT in => {};
NOT seq.joints[i]
AND in => {
newIn ← FALSE;
newList ← AppendToList[list, CONS[thisSeq, NIL]];
newThisSeq ← NIL};
seq.joints[i]
AND
NOT in => {
newIn ← TRUE;
newThisSeq ← CreateEmpty[seq.traj];
runCount ← runCount + 1; -- BUG! KAP March 11, 1986
newCount ← newCount + 1;
newThisSeq.joints[i] ← TRUE;
newThisSeq.jointCount ← newThisSeq.jointCount + 1;
};
seq.joints[i]
AND in => {
newThisSeq.joints[i] ← TRUE;
newThisSeq.jointCount ← newThisSeq.jointCount + 1;
};
ENDCASE => ERROR;
};
ConsiderSegment:
PROC [in:
BOOL, list:
LIST
OF Sequence, seq: Sequence, thisSeq: Sequence, runCount:
NAT, i:
NAT]
RETURNS [newIn:
BOOL, newList:
LIST
OF Sequence, newThisSeq: Sequence, newCount:
NAT] = {
newIn ← in;
newList ← list;
newThisSeq ← thisSeq;
newCount ← runCount;
SELECT
TRUE
FROM
NOT seq.segments[i] AND NOT in => {};
NOT seq.segments[i]
AND in => {
newIn ← FALSE;
newList ← AppendToList[list, CONS[thisSeq, NIL]];
newThisSeq ← NIL};
seq.segments[i]
AND
NOT in => {
newIn ← TRUE;
newThisSeq ← CreateEmpty[seq.traj];
newCount ← newCount + 1;
newThisSeq.segments[i] ← TRUE;
newThisSeq.segCount ← newThisSeq.segCount + 1;
ControlPointsTrue[newThisSeq, i];
};
seq.segments[i]
AND in => {
newThisSeq.segments[i] ← TRUE;
newThisSeq.segCount ← newThisSeq.segCount + 1;
ControlPointsTrue[newThisSeq, i];
};
ENDCASE => ERROR;
};
ControlPointsTrue:
PROC [seq: Sequence, segNum:
NAT] = {
seg: Segment ← GGTraj.FetchSegment[seq.traj, segNum];
cpCount: NAT ← seg.class.controlPointCount[seg];
FOR i:
NAT
IN [0..cpCount-1]
DO
IF
NOT seq.controlPoints[segNum][i]
THEN {
seq.controlPoints[segNum][i] ← TRUE;
seq.controlPointCount ← seq.controlPointCount + 1;
};
ENDLOOP;
};
NATGenerator: TYPE = REF NATGeneratorObj;
NATGeneratorObj:
TYPE =
RECORD [
toGo: NAT,
next: NAT,
mod: NAT
];
NATsInInterval:
PROC [start, length, mod:
NAT]
RETURNS [natGen: NATGenerator] = {
natGen ←
NEW[NATGeneratorObj ← [
toGo: length,
next: start,
mod: mod]];
};
NextNAT:
PROC [natGen: NATGenerator]
RETURNS [nextNAT:
INT] = {
IF natGen.toGo = 0 THEN RETURN[-1];
natGen.toGo ← natGen.toGo - 1;
nextNAT ← natGen.next;
natGen.next ← (natGen.next + 1) MOD natGen.mod;
};
SegmentsInTraj:
PUBLIC
PROC [traj: Traj]
RETURNS [segGen: SegmentGenerator] = {
We special case the complete trajectory case to reduce allocations.
segGen ←
NEW[SegmentGeneratorObj ← [
traj: traj,
toGo: traj.segCount,
index: 0,
seq: NIL,
completeSeq: TRUE
]];
SegmentsInSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [segGen: SegmentGenerator] = {
IF IsObsolete[seq] THEN ERROR; -- expensive, June 24, 1986, Bier
IF IsComplete[seq] THEN RETURN[SegmentsInTraj[seq.traj]];
segGen ←
NEW[SegmentGeneratorObj ← [
traj: seq.traj,
toGo: seq.segCount,
index: 0,
seq: seq, -- should we copy it? Bier January 27, 1986 5:37:01 pm PST
completeSeq: FALSE
]];
};
OrderedSegmentsInSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [segGen: SegmentGenerator] = {
Returns a generator for all segments in seq, beginning with the lowest numbered one (in the case of open trajectories), or the first segment that follows a segment that is not in seq (for closed trajectories). If seq.traj is complete, then begins with segment 0.
IF IsEmpty[seq] THEN ERROR; -- why an error?? KAP December 22, 1986
IF IsObsolete[seq] THEN ERROR;
IF IsComplete[seq] THEN RETURN[SegmentsInTraj[seq.traj]];
segGen ←
NEW[SegmentGeneratorObj ← [
traj: seq.traj,
toGo: seq.segCount,
index: IF seq.segCount=0 THEN 0 ELSE FirstSegment[seq], -- KAP December 22, 1986
seq: seq, -- should we copy it? Bier January 27, 1986
completeSeq: FALSE
]];
};
NextSegment:
PUBLIC
PROC [segGen: SegmentGenerator]
RETURNS [next: Segment] = {
Termination: segGen.toGo is always decremented.
Invariants:
1) When this procedure is called, seq.segments[segGen.index] has not yet been looked at OR segGen.toGo = 0.
2) touched < segCount OR segGen.toGo = 0.
seq: Sequence ← segGen.seq;
segCount: NAT ← GGTraj.HiSegment[segGen.traj] + 1;
IF segGen.toGo = 0 THEN RETURN[NIL];
IF
NOT segGen.completeSeq
THEN {
-- If we are stepping through a complete traj, seq = NIL
UNTIL seq.segments[segGen.index]
DO
segGen.index ← (segGen.index + 1) MOD segCount;
segGen.touched ← segGen.touched + 1;
IF segGen.touched >= segCount THEN SIGNAL Problem[msg: "Broken invariant"];
ENDLOOP;
};
3) At this point in the procedure, seq.segments[segGen.index] is TRUE.
4) At this point, touched < segCount.
next ← GGTraj.FetchSegment[segGen.traj, segGen.index];
segGen.index ← (segGen.index + 1) MOD segCount;
segGen.touched ← segGen.touched + 1;
segGen.toGo ← segGen.toGo - 1;
};
NextSegmentAndIndex:
PUBLIC
PROC [segGen: SegmentGenerator]
RETURNS [next: SegAndIndex] = {
Termination: segGen.toGo is always decremented.
Invariants:
1) When this procedure is called, seq.segments[segGen.index] has not yet been looked at OR segGen.toGo = 0.
2) touched < segCount OR segGen.toGo = 0.
seq: Sequence ← segGen.seq;
segCount: NAT ← GGTraj.HiSegment[segGen.traj] + 1;
IF segGen.toGo = 0 THEN RETURN[[NIL, 999]];
IF
NOT segGen.completeSeq
THEN {
-- If we are stepping through a complete traj, seq = NIL
UNTIL seq.segments[segGen.index]
DO
segGen.index ← (segGen.index + 1) MOD segCount;
segGen.touched ← segGen.touched + 1;
IF segGen.touched >= segCount THEN SIGNAL Problem[msg: "Broken invariant"];
ENDLOOP;
};
3) At this point in the procedure, seq.segments[segGen.index] is TRUE.
4) At this point, touched < segCount.
next.seg ← GGTraj.FetchSegment[segGen.traj, segGen.index];
next.index ← segGen.index;
segGen.index ← (segGen.index + 1) MOD segCount;
segGen.touched ← segGen.touched + 1;
segGen.toGo ← segGen.toGo - 1;
};
ControlPointsInSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [cpGen: ControlPointGenerator] = {
IF IsEmpty[seq] THEN ERROR; -- Why an error?? KAP December 22, 1986
IF IsObsolete[seq] THEN ERROR;
cpGen ←
NEW[ControlPointGeneratorObj ← [
toGo: seq.controlPointCount,
segIndex: 0,
cpIndex: 0,
seq: seq
]];
};
NextControlPoint:
PUBLIC
PROC [cpGen: ControlPointGenerator]
RETURNS [next: PointAndDone] = {
seq: Sequence ← cpGen.seq;
seg: Segment;
segIndex: NAT ← cpGen.segIndex;
cpIndex: NAT ← cpGen.cpIndex;
hiSeg: NAT ← GGTraj.HiSegment[cpGen.seq.traj];
IF cpGen.toGo = 0 THEN RETURN[[[0,0], TRUE]];
FOR i:
NAT
IN [segIndex..hiSeg]
DO
FOR j:
NAT
IN [cpIndex..seq.controlPoints[i].len)
DO
IF seq.controlPoints[i][j]
THEN {
segIndex ← i;
cpIndex ← j;
GOTO Found;
};
ENDLOOP;
cpIndex ← 0;
REPEAT
Found => {
seg ← GGTraj.FetchSegment[cpGen.seq.traj, segIndex];
next.point ← seg.class.controlPointGet[seg, cpIndex];
next.done ← FALSE;
};
FINISHED => ERROR;
ENDLOOP;
cpGen.segIndex ← segIndex;
cpGen.cpIndex ← cpIndex + 1;
cpGen.toGo ← cpGen.toGo - 1;
};
NextSegNumAndCPNum:
PUBLIC
PROC [cpGen: ControlPointGenerator]
RETURNS [segNum, cpNum:
NAT, done:
BOOL] = {
seq: Sequence ← cpGen.seq;
segIndex: NAT ← cpGen.segIndex;
cpIndex: NAT ← cpGen.cpIndex;
hiSeg: NAT ← GGTraj.HiSegment[cpGen.seq.traj];
IF cpGen.toGo = 0 THEN RETURN[0, 0, TRUE];
FOR i:
NAT
IN [segIndex..hiSeg]
DO
FOR j:
NAT
IN [cpIndex..seq.controlPoints[i].len)
DO
IF seq.controlPoints[i][j]
THEN {
segIndex ← i;
cpIndex ← j;
GOTO Found;
};
ENDLOOP;
cpIndex ← 0;
REPEAT
Found => {
segNum ← segIndex;
cpNum ← cpIndex;
done ← FALSE;
};
FINISHED => ERROR;
ENDLOOP;
cpGen.segIndex ← segIndex;
cpGen.cpIndex ← cpIndex + 1;
cpGen.toGo ← cpGen.toGo - 1;
};
JointsInSequence:
PUBLIC
PROC [seq: Sequence]
RETURNS [jointGen: JointGenerator] = {
It would be nice to have a hiJoint field in the JointGeneratorObj, Bier, January 7, 1987
IF IsObsolete[seq] THEN ERROR;
jointGen ←
NEW[JointGeneratorObj ← [
traj: seq.traj,
toGo: seq.jointCount,
index: 0,
seq: seq,
completeSeq:
FALSE
-- I'll use this for optimization later, Bier March 10, 1986 5:03:42 pm PST
I did use for optimization. Bier, January 7, 1987 0:54:51 am PST.
]];
};
JointsInTraj:
PUBLIC
PROC [traj: Traj]
RETURNS [jointGen: JointGenerator] = {
jointGen ←
NEW[JointGeneratorObj ← [
traj: traj,
toGo: GGTraj.HiJoint[traj] + 1,
index: 0,
seq: NIL,
completeSeq: TRUE
]];
};
NextJoint:
PUBLIC
PROC [jointGen: JointGenerator]
RETURNS [next:
INT] = {
seq: Sequence;
index: NAT ← jointGen.index;
IF jointGen.toGo = 0 THEN RETURN[-1];
IF jointGen.completeSeq
THEN {
next ← index;
}
ELSE {
hiJoint: NAT ← GGTraj.HiJoint[jointGen.traj];
seq ← jointGen.seq;
UNTIL seq.joints[index]
OR index > hiJoint
DO
index ← index + 1;
ENDLOOP;
IF index > hiJoint THEN ERROR;
next ← index;
};
jointGen.index ← index + 1;
jointGen.toGo ← jointGen.toGo - 1;
};
SetStrokeWidth:
PUBLIC
PROC [seq: Sequence, strokeWidth:
REAL] = {
segGen: SegmentGenerator;
segGen ← GGSequence.SegmentsInSequence[seq];
FOR seg: Segment ← GGSequence.NextSegment[segGen], GGSequence.NextSegment[segGen]
UNTIL seg =
NIL
DO
seg.class.setStrokeWidth[seg, strokeWidth];
ENDLOOP;
};
GetStrokeWidth:
PUBLIC
PROC [seq: Sequence]
RETURNS [strokeWidth:
REAL ← 1.0] = {
segGen: SegmentGenerator ← GGSequence.SegmentsInSequence[seq];
seg: Segment ← GGSequence.NextSegment[segGen];
IF seg#NIL THEN strokeWidth ← seg.strokeWidth
ELSE ERROR Problem[msg: "No segments to get a stroke width from"];
};
END.