
    <<MatchImpl.mesa>>
        <<Last edited by: David Kurlander -  September 2, 1987 8:28:50 pm PDT>>

    DIRECTORY
        AtomButtons, AtomButtonsTypes, Feedback, GList, GGBasicTypes, GGCaret, GGContainer, GGFont, GGInterfaceTypes, GGModelTypes, 
        GGOutline, GGScene, GGSegmentTypes, GGSelect, GGSequence, GGSlice, GGTraj, GGUserInput, GGUtility, GGWindow, Imager, 
        ImagerTransformation, Match, MatchTurtle, MatchViewer, Real, RealFns, Rope, SlackProcess, ViewerClasses;

        MatchImpl: CEDAR PROGRAM
            IMPORTS AtomButtons, GList, GGCaret, GGOutline, GGScene, GGSelect, GGSequence, GGSlice, GGTraj, GGUtility, GGWindow, 
            ImagerTransformation, Match,  MatchTurtle, MatchViewer, Real, RealFns, Rope
            EXPORTS Match = BEGIN

        BoundBox: TYPE = GGModelTypes.BoundBox;
        Caret: TYPE = GGInterfaceTypes.Caret;
        ChoiceData: TYPE = MatchViewer.ChoiceData;
        DashInfo: TYPE = Match.DashInfo;
        DashInfoObj: TYPE = Match.DashInfoObj;
        GGData: TYPE = GGInterfaceTypes.GGData;
        ItemID: TYPE = Match.ItemID;
        ItemMatch: TYPE = Match.ItemMatch;
        ItemMatchObj: TYPE = Match.ItemMatchObj;
        LooksInfo: TYPE = Match.LooksInfo;
        LooksInfoObj: TYPE = Match.LooksInfoObj;
        MatchData: TYPE = MatchViewer.MatchData;
        MatchDescriptor: TYPE = Match.MatchDescriptor;
        MatchDObj: TYPE = Match.MatchDObj;
        PositionDescriptor: TYPE = MatchTurtle.PositionDescriptor;
        Point: TYPE = GGBasicTypes.Point;
        SearchInfo: TYPE = Match.SearchInfo;
        SearchInfoObj: TYPE = Match.SearchInfoObj;
        SearchState: TYPE = Match.SearchState;
        Segment: TYPE = GGSegmentTypes.Segment;
        SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator;
        Sequence: TYPE = GGModelTypes.Sequence;
        Scene: TYPE = GGModelTypes.Scene;
        Slice: TYPE = GGModelTypes.Slice;
        SliceDescriptor: TYPE = GGModelTypes.SliceDescriptor;
        SliceDescriptorGenerator: TYPE = GGModelTypes.SliceDescriptorGenerator;
        SliceDescriptorObj: TYPE = GGModelTypes.SliceDescriptorObj;
        SliceGenerator: TYPE = GGModelTypes.SliceGenerator;
        SliceParts: TYPE = REF ANY;
        Traj: TYPE = GGModelTypes.Traj;
        TrajGenerator: TYPE = GGModelTypes.TrajGenerator;
        TurtleHeader: TYPE = MatchTurtle.TurtleHeader;
        TurtleInfo: TYPE = MatchTurtle.TurtleInfo;

    <<Feature Fetching **************************>>
    <<>>
    SearchEvent: PUBLIC GGUserInput.UserInputProc = {
    toSearch: GGData _ MatchViewer.GetGGInputFocus[];
    IF toSearch # NIL THEN [] _ Search[toSearch, event];
        };

Search: PUBLIC PROC [toSearch: GGData, event: LIST OF REF ANY] RETURNS [found: BOOL] = {
    matchData: MatchData _ MatchViewer.GetMatchData[];
    SELECT matchData.searchOp FROM
        disjunction => found _ NewSearch4[toSearch, event];
        conjunction => found _ Match.Search6[toSearch, event];
        ENDCASE => MatchViewer.ErrorFeedback["This SearchOp unimplemented."];
        };

AfterDescriptor: PUBLIC PROC [sliceD: SliceDescriptor, direction: REF ANY] RETURNS [after: SearchInfo _ NIL] = {
SELECT sliceD.slice.class.type FROM
$Outline => {
<<First set up trajs part of SearchInfo>>
matchData: MatchData _ MatchViewer.GetMatchData[];
outlineParts: GGOutline.OutlineParts _ NARROW[sliceD.parts];
seqList: LIST OF Sequence _ outlineParts.seqs;
children: LIST OF Traj _ GGOutline.TrajectoriesOfOutline[sliceD.slice];
after _ NEW[SearchInfoObj _ [slice: sliceD.slice, reverse: direction=$SearchAbove]];
IF NOT after.reverse THEN {
seqList _ NARROW[GList.Reverse[seqList], LIST OF Sequence];
children _ NARROW[GList.Reverse[children], LIST OF Traj];
};
FOR seqList _ seqList, seqList.rest UNTIL seqList=NIL OR seqList.first#NIL DO
after.trajs _ CONS[children.first, after.trajs];
children _ children.rest;
ENDLOOP;
<<That was quick.  Now set up segs if necessary.>>
IF matchData.matchLevel = anywhere THEN {
seq: Sequence _ IF seqList#NIL AND seqList.first#NIL THEN seqList.first ELSE NIL;
IF seqList#NIL AND seqList.first#NIL THEN after.trajs _ CONS[seq.traj, after.trajs];
    IF seq=NIL OR GGSequence.IsEmpty[seq] THEN AddSegs[after] -- add ALL segs
    ELSE {
    IF NOT after.reverse THEN
    FOR i: INT DECREASING IN [0..seq.traj.segCount) UNTIL seq.segments[i] DO
    after.segs _ CONS[GGTraj.FetchSegment[seq.traj, i], after.segs];
    ENDLOOP
    ELSE
    FOR i: INT IN [0..seq.traj.segCount) UNTIL seq.segments[i] DO
    after.segs _ CONS[GGTraj.FetchSegment[seq.traj, i], after.segs];
    ENDLOOP;
    after.closedTraj _ FALSE; -- only some segs of the traj are included
    };
};
};
$Box => RETURN[AfterBoxDescriptor[sliceD, direction]];
ENDCASE => after _ NIL;
};

AfterBoxDescriptor: PROC [sliceD: SliceDescriptor, direction: REF ANY] RETURNS [after: SearchInfo _ NIL] = {
matchData: MatchData _ MatchViewer.GetMatchData[];
IF matchData.matchLevel = anywhere THEN {
after _ NEW[SearchInfoObj _ [slice: sliceD.slice, reverse: direction=$SearchAbove, segs: NIL]];
IF sliceD.slice.class.isEmptyParts[sliceD] THEN AddSegs[after] -- add ALL segs
ELSE IF NOT sliceD.slice.class.isCompleteParts[sliceD] THEN {
<<creatively avoiding looking at the BoxData>>
segGen: SegmentGenerator _ GGSlice.SegmentsInDescriptor[sliceD];
firstSeg: Segment _ GGSlice.NextSegment[segGen];
lastSeg: Segment _ firstSeg;
FOR seg: Segment _ GGSlice.NextSegment[segGen], GGSlice.NextSegment[segGen] UNTIL seg = NIL DO
lastSeg _ seg;
ENDLOOP;
IF after.reverse THEN {
FOR i: INT IN [0..4) DO
nextSeg: Segment _ GGSlice.BoxFetchSegment[sliceD.slice, i];
IF nextSeg = firstSeg THEN EXIT;
after.segs _ CONS[nextSeg, after.segs];
ENDLOOP;
}
ELSE FOR i: INT DECREASING IN [0..4) DO
nextSeg: Segment _ GGSlice.BoxFetchSegment[sliceD.slice, i];
IF nextSeg = lastSeg THEN EXIT;
after.segs _ CONS[nextSeg, after.segs];
ENDLOOP;
after.closedTraj _ FALSE; -- only some segs of the box are included
};
};
};


IsEmptySearchInfo: PUBLIC PROC [searchInfo: SearchInfo] RETURNS [BOOL _ FALSE] = {
IF searchInfo = NIL OR searchInfo.empty = TRUE THEN RETURN[TRUE];
IF searchInfo.slice.class.type = $Outline AND searchInfo.trajs = NIL THEN RETURN[TRUE];
};

<<IsFullSearchInfo: PROC [searchInfo: SearchInfo] RETURNS [BOOL _ FALSE] = {>>
<<IF searchInfo = NIL THEN RETURN[FALSE];>>
<<IF searchInfo.complete THEN RETURN[TRUE];>>
<<};>>
<<>>
CreateSearchInfo: PUBLIC PROC [slice: Slice, direction: REF ANY] RETURNS [searchInfo: SearchInfo] = {
<<Creates a new, complete SearchInfo for the specified slice>>
matchData: MatchData _ MatchViewer.GetMatchData[];
searchInfo _ NEW[SearchInfoObj _ [slice: slice, reverse: direction = $SearchAbove]];
    SELECT slice.class.type FROM
        $Outline => {
        searchInfo.trajs _ GGOutline.TrajectoriesOfOutline[slice];
        IF searchInfo.reverse THEN searchInfo.trajs _ NARROW[GList.Reverse[searchInfo.trajs], LIST OF Traj];
        IF matchData.matchLevel = anywhere THEN AddSegs[searchInfo];
        };
    $Box => IF matchData.matchLevel = anywhere THEN AddSegs[searchInfo];
        ENDCASE;
    };

GetSourceLooks: PUBLIC PROC RETURNS [looksList: LIST OF REF ANY _ NIL] = {
    matchData: MatchData _ MatchViewer.GetMatchData[];
    fromData: GGData _ MatchViewer.GetFromData[];
    sliceGen: SliceGenerator _ GGScene.SlicesInScene[fromData.scene];
    FOR slice: Slice _ GGScene.NextSlice[sliceGen], GGScene.NextSlice[sliceGen] UNTIL slice = NIL DO
        looksList _ CONS[GetLooksOfSlice[slice, matchData.from], looksList];
        ENDLOOP;
    };

GetTargetLooks: PUBLIC PROC RETURNS [looksList: LIST OF REF ANY _ NIL] = {
    matchData: MatchData _ MatchViewer.GetMatchData[];
    toData: GGData _ MatchViewer.GetToData[];
    sliceGen: SliceGenerator _ GGScene.SlicesInScene[toData.scene];
    FOR slice: Slice _ GGScene.NextSlice[sliceGen], GGScene.NextSlice[sliceGen] UNTIL slice = NIL DO
        looksList _ CONS[GetLooksOfSlice[slice, matchData.to], looksList];
        ENDLOOP;
    };

    GetLooksOfSlice: PROC [slice: Slice, choice: ChoiceData] RETURNS [REF ANY] = {
        targetParts: SliceParts _ slice.class.newParts[slice, NIL, slice].parts;
        looks: LooksInfo _ NEW[LooksInfoObj];
        IF slice.class.type = $Outline OR slice.class.type = $Box THEN RETURN [GetCompositeLooksOfSlice[slice, choice]];
        looks.owner.slice _ slice; -- this will suffice
        IF AtomButtons.GetBinaryState[choice.class] THEN { -- Class
            looks.classDef _ TRUE;
            looks.class _ slice.class.type;
            };
        IF AtomButtons.GetBinaryState[choice.type] THEN { -- Type
            looks.typeDef _ TRUE;
            looks.type _ slice.class.type;
            };
        IF AtomButtons.GetBinaryState[choice.shape] THEN { -- Shape
            looks.shapeDef _ TRUE;
            looks.shape _ MatchTurtle.GetShapeOfSlice[slice];
            };
        IF AtomButtons.GetBinaryState[choice.color] THEN { -- Color
            looks.colorDef _ TRUE;
            looks.color _ slice.class.getStrokeColor[slice, targetParts];
            };
        IF AtomButtons.GetBinaryState[choice.fillColor] THEN { -- Fill Color
            looks.fillColorDef _ TRUE;
            looks.fillColor _ slice.class.getFillColor[slice];
            };
        IF AtomButtons.GetBinaryState[choice.string] THEN { -- String
            IF slice.class.type = $Text THEN {
                looks.stringDef _ TRUE;
                looks.string _ GGSlice.GetText[slice];
                }
            ELSE MatchViewer.ErrorFeedback["Can't do string matches on non-text objects!"];
            };
        IF AtomButtons.GetBinaryState[choice.font] THEN { -- Font
            looks.fontDef _ TRUE;
            looks.font _ GGSlice.GetFontData[slice];
            };
        IF AtomButtons.GetBinaryState[choice.fontTform] THEN { -- Font & Transform
            looks.fontTformDef _ TRUE;
            looks.fontTform _ GGSlice.GetFontData[slice];
            };
        IF AtomButtons.GetBinaryState[choice.dash] THEN { -- Dashes
            looks.dashesDef _ TRUE;
            looks.dashes _ NEW[DashInfoObj];
            [dashed: looks.dashes.dashed, pattern: looks.dashes.pattern, offset: looks.dashes.offset, length: looks.dashes.length] _ 
            slice.class.getDashed[slice, targetParts];
            };
        IF AtomButtons.GetBinaryState[choice.joints] THEN { -- Joints
            looks.jointsDef _ TRUE;
            looks.joints _ slice.class.getStrokeJoint[slice, targetParts];
            };
        IF AtomButtons.GetBinaryState[choice.ends] THEN { -- Ends
            looks.endsDef _ TRUE;
            looks.ends _ slice.class.getStrokeEnd[slice, targetParts];
            };
        IF AtomButtons.GetBinaryState[choice.width] THEN { -- Width
            looks.widthDef _ TRUE;
            looks.width _ slice.class.getStrokeWidth[slice, targetParts];
            };
        RETURN [looks];
        };

    GetCompositeLooksOfSlice: PROC [slice: Slice, choice: ChoiceData] RETURNS [looksList: LIST OF LIST OF LooksInfo _ NIL] = {
        GetLooksOfSegment: GGModelTypes.WalkProc = {
            looks: LooksInfo _ NEW[LooksInfoObj];
            looks.owner.slice _ slice;
            looks.owner.traj _ traj;
            looks.owner.seg _ seg;
            IF AtomButtons.GetBinaryState[choice.shape] THEN { -- Shape
                looks.shapeDef _ TRUE;
                looks.shape _ shape;
                };
            IF AtomButtons.GetBinaryState[choice.class] THEN { -- Class
                looks.classDef _ TRUE;
                looks.class _ class;
                };
            IF AtomButtons.GetBinaryState[choice.type] THEN { -- Type
                looks.typeDef _ TRUE;
                looks.type _ seg.class.type;
                };
            IF AtomButtons.GetBinaryState[choice.color] THEN { -- Color
                looks.colorDef _ TRUE;
                looks.color _ seg.color;
                };
            IF AtomButtons.GetBinaryState[choice.fillColor] THEN { -- Fill Color
                looks.fillColorDef _ TRUE;
                looks.fillColor _ fillColor;
                };
            IF AtomButtons.GetBinaryState[choice.dash] THEN { -- Dashes
                looks.dashesDef _ TRUE;
                looks.dashes _ NEW[DashInfoObj _ [dashed: seg.dashed, pattern: seg.pattern, offset: seg.offset, length: seg.length]];
                };
            IF AtomButtons.GetBinaryState[choice.joints] THEN { -- Joints
                looks.jointsDef _ TRUE;
                looks.joints _ joints;
                };
            IF AtomButtons.GetBinaryState[choice.ends] THEN { -- Ends
                looks.endsDef _ TRUE;
                looks.ends _ seg.strokeEnd;
                };
            IF AtomButtons.GetBinaryState[choice.width] THEN { -- Width
                looks.widthDef _ TRUE;
                looks.width _ seg.strokeWidth;
                };
            subList _ CONS[looks, subList];
            };
        subList: LIST OF LooksInfo _ NIL;
        fillColor: Imager.Color;
        joints: Imager.StrokeJoint;
        shape: TurtleHeader;
        traj: Traj _ NIL; -- must be defined here so it's defined at GetLooksInSegment call-back
        class: ATOM _ slice.class.type; -- for use in call-back
        IF AtomButtons.GetBinaryState[choice.fillColor] THEN fillColor _ slice.class.getFillColor[slice];
        IF slice.class.type = $Outline THEN {
            trajGen: TrajGenerator _ GGOutline.TrajsInOutline[slice];
        FOR traj _ GGScene.NextTraj[trajGen], GGScene.NextTraj[trajGen] UNTIL traj = NIL DO
            subList _ NIL;
            IF AtomButtons.GetBinaryState[choice.joints] THEN joints _ GGTraj.GetTrajStrokeJoint[traj];
            IF AtomButtons.GetBinaryState[choice.shape] THEN shape _ MatchTurtle.TrajToTurtle[traj];
            WalkSegmentsInTraj[traj, GetLooksOfSegment];
            looksList _ CONS[NARROW[GList.DReverse[subList], LIST OF LooksInfo], looksList];
            ENDLOOP;
            }
        ELSE {
            IF AtomButtons.GetBinaryState[choice.shape] THEN shape _ MatchTurtle.GetShapeOfSlice[slice];
            [] _ GGSlice.WalkSegments[slice, GetLooksOfSegment];
            looksList _ CONS[NARROW[GList.DReverse[subList], LIST OF LooksInfo], looksList];
            };
        looksList _ NARROW[GList.DReverse[looksList], LIST OF LIST OF LooksInfo];
        };

    WalkSegmentsInTraj: PROC [traj: Traj, walkProc: GGModelTypes.WalkProc] = {
        <<walks the segments of a trajectory, but unlike most of the segment walk routines, does not return a sequence>>
        segGen: SegmentGenerator _ GGSequence.SegmentsInTraj[traj];
        FOR seg: Segment _ GGSequence.NextSegment[segGen], GGSequence.NextSegment[segGen] UNTIL seg = NIL DO
            [] _ walkProc[seg, NIL];
            ENDLOOP;
        };

    FindMatchInSlice: PUBLIC PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, direction: REF ANY, matchD: MatchDescriptor] RETURNS 
    [match: SliceDescriptor _ NIL, rest: SearchInfo _ NIL] = {
    IF domain.empty THEN RETURN[NIL, domain];
    SELECT domain.slice.class.type FROM
    $Circle => [match, rest] _ FindMatchInCircle[domain, fromLooks, matchD];
    $Text => [match, rest] _ FindMatchInText[domain, fromLooks, matchD];
    $Box => [match, rest] _ FindMatchInBox[domain, fromLooks, matchD];
    $Outline => [match, rest] _ FindMatchInOutline[domain, fromLooks, matchD];
    ENDCASE; -- can't match on this kind of slice
    };

FindMatchInCircle: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: SliceDescriptor, 
rest: SearchInfo] = {
entireCircle: SliceDescriptor _ domain.slice.class.newParts[domain.slice, NIL, slice];
looks: LooksInfo;
complexLooks: LIST OF LIST OF LooksInfo;
FOR fromLooks _ fromLooks, fromLooks.rest UNTIL fromLooks=NIL DO
WITH fromLooks.first SELECT FROM
simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
complex: LIST OF LIST OF LooksInfo => {
looks _ complex.first.first;
complexLooks _ complex;
};
ENDCASE => ERROR;
IF GList.Length[complexLooks] > 1 THEN LOOP;
IF looks.typeDef AND complexLooks#NIL THEN LOOP;
IF SimpleMatch[entireCircle, looks, matchD] THEN RETURN[entireCircle, MakeEmpty[domain]];
ENDLOOP;
RETURN[NIL, MakeEmpty[domain]];
};

FindMatchInText: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: SliceDescriptor, 
rest: SearchInfo] = {
entireText: SliceDescriptor _ domain.slice.class.newParts[domain.slice, NIL, slice];
looks: LooksInfo;
complexLooks: LIST OF LIST OF LooksInfo;
FOR fromLooks _ fromLooks, fromLooks.rest UNTIL fromLooks=NIL DO
WITH fromLooks.first SELECT FROM
simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
complex: LIST OF LIST OF LooksInfo => {
looks _ complex.first.first;
complexLooks _ complex;
};
ENDCASE => ERROR;
IF GList.Length[complexLooks] > 1 THEN LOOP;
IF looks.typeDef AND complexLooks#NIL THEN LOOP;
IF SimpleMatch[entireText, looks, matchD] THEN RETURN[entireText, MakeEmpty[domain]];
ENDLOOP;
RETURN[NIL, MakeEmpty[domain]];
};

FindMatchInBox: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: SliceDescriptor, 
rest: SearchInfo] = {
matchLevel: MatchViewer.MatchLevel _ MatchViewer.GetMatchData[].matchLevel;
entireBox: SliceDescriptor _ domain.slice.class.newParts[domain.slice, NIL, slice];
looks: LooksInfo;
complexLooks: LIST OF LIST OF LooksInfo;
IF matchLevel = anywhere THEN {
[match, rest] _ FindAnywhereMatchInBox[domain, fromLooks, matchD];
RETURN[match, rest];
};
FOR fromLooks _ fromLooks, fromLooks.rest UNTIL fromLooks=NIL DO
WITH fromLooks.first SELECT FROM
simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
complex: LIST OF LIST OF LooksInfo => {
looks _ complex.first.first;
complexLooks _ complex;
};
ENDCASE => ERROR;
IF matchLevel = trajLevel OR matchLevel = sliceLevel THEN {
IF (looks.typeDef OR looks.shapeDef) AND GList.Length[complexLooks] > 1 THEN LOOP; -- boxes are connected entities
IF looks.typeDef THEN {
IF ComplexMatch[entireBox, complexLooks, matchD] THEN RETURN[entireBox, MakeEmpty[domain]];
}
ELSE {
IF SimpleMatch[entireBox, looks, matchD] THEN RETURN[entireBox, MakeEmpty[domain]];
};
}
ELSE ERROR;
ENDLOOP;
RETURN[NIL, MakeEmpty[domain]];
};

FindAnywhereMatchInBox: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: 
SliceDescriptor, rest: SearchInfo] = {
SelectInRange: GGModelTypes.WalkProc = {
keep _ IF segNum >= first AND segNum <= last THEN TRUE ELSE FALSE;
segNum _ segNum + 1;
};
segCount: NAT = 4; -- 4 segs per box
segNum: NAT _ 0;
start, length: NAT; -- refer to the span of segments on domain.segs
first, last: NAT; -- refer to the span of segments relative to the box
startSeg: Segment;
[start, length] _ SegLooksMatch[domain, fromLooks, matchD]; -- note: start is relative to start of list, not start of traj
IF length < 1 THEN RETURN[NIL, NIL];
<<Make a sliceD for the match, and a rest>>
startSeg _ NARROW[GList.NthElement[domain.segs, start+1], Segment];
FOR i:INT IN [0..4) DO
IF GGSlice.BoxFetchSegment[domain.slice, i] = startSeg THEN {first _ i; EXIT;};
ENDLOOP;
IF NOT domain.reverse THEN {
last _ (first + length - 1) MOD segCount;
}
ELSE {
last _ first;
first _ (first - length + 1 + segCount) MOD segCount; -- + segCount to keep positive
};
<<Now we have to splice out the used segments from domain.segs>>
match _ GGSlice.WalkSegments[domain.slice, SelectInRange];
domain _ CopySearchInfo[domain];
domain.segs _ NARROW[GList.NthTail[domain.segs, start + length], LIST OF Segment];
RETURN[match, domain];
};


FindAnywhereMatchInOutline: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: 
SliceDescriptor, rest: SearchInfo] = {
matchSeq: Sequence;
traj: Traj _ domain.trajs.first;
startSeg: Segment;
start, length: NAT; -- refer to a span of segments on domain.segs
first, last: NAT; -- refer to a span of segments in the new sequence (ie, relative to the traj)
domain _ CopySearchInfo[domain];
[start, length] _ SegLooksMatch[domain, fromLooks, matchD]; -- note: start is relative to start of list, not start of traj
IF length < 1 THEN { -- nothing on interest on this traj, go directly to next
domain.trajs _ domain.trajs.rest;
AddSegs[domain];
RETURN[NIL, domain];
};
<<Make a sliceD out of it and a rest, and return>>
startSeg _ NARROW[GList.NthElement[domain.segs, start+1], Segment];
FOR i:INT IN [0..traj.segCount) DO
IF GGTraj.FetchSegment[traj, i] = startSeg THEN {first _ i; EXIT;};
ENDLOOP;
IF NOT domain.reverse THEN {
last _ (first + length - 1) MOD traj.segCount;
}
ELSE {
last _ first;
first _ (first - length + 1 + traj.segCount) MOD traj.segCount; -- + segCount to keep positive
};
<<Now we have to splice out the used segments from domain.segs>>
domain.segs _ NARROW[GList.NthTail[domain.segs, start + length], LIST OF Segment];
matchSeq _ GGSequence.CreateFromSegments[traj, first, last];
match _ GGOutline.DescriptorFromSequence[domain.slice, matchSeq];
RETURN[match, domain];
};

AddSegs: PUBLIC PROC [domain: SearchInfo] = {
<<Fills out the segs field of a SearchInfo to contain all the segs in the first trajectory/box>>
domain.segs _ NIL;
SELECT domain.slice.class.type FROM
$Outline => {
traj: Traj;
IF domain.trajs = NIL THEN RETURN; -- nothing to fill in
traj _ domain.trajs.first;
FOR i: INT IN [0..traj.segCount) DO
domain.segs _ CONS[GGTraj.FetchSegment[traj, i], domain.segs];
ENDLOOP;
IF NOT domain.reverse THEN domain.segs _ NARROW[GList.DReverse[domain.segs], LIST OF Segment];
<<Fill in closedTraj field>>
IF traj.role # open OR ManhattanDistance[GGTraj.FetchJointPos[traj, 0], GGTraj.FetchJointPos[traj, traj.segCount]] < 1.0 THEN 
domain.closedTraj _ TRUE
ELSE domain.closedTraj _ FALSE;
};
$Box => {
FOR i: INT IN [0..4) DO
domain.segs _ CONS[GGSlice.BoxFetchSegment[domain.slice, i], domain.segs];
ENDLOOP;
IF NOT domain.reverse THEN domain.segs _ NARROW[GList.DReverse[domain.segs], LIST OF Segment];
domain.closedTraj _ TRUE;
};
ENDCASE => ERROR;
};

ManhattanDistance: PROC [pt1, pt2: Point] RETURNS [REAL] = {
RETURN[ABS[pt2.x - pt1.x] + ABS[pt2.y - pt1.y]];
};

SegLooksMatch: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [start, length: NAT _ 0] = {
noneFound: BOOL _ TRUE;
newStart, newLength: NAT;
looks: LooksInfo;
complexLooks: LIST OF LooksInfo;
reverse: BOOL _ FALSE;
mapping: LIST OF ItemMatch _ NIL;
saveDObj, bestDObj: Match.MatchDObj;
fromLooks _ FlattenOutSliceLooks[fromLooks];
FOR fromLooks _ fromLooks, fromLooks.rest UNTIL fromLooks=NIL DO
WITH fromLooks.first SELECT FROM
simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
complex: LIST OF LooksInfo => { -- not LIST OF LIST OF, since we've flattened slices
looks _ complex.first;
complexLooks _ complex;
};
ENDCASE => ERROR;
IF NOT SliceLevelMatch[domain.slice, IF domain.trajs = NIL THEN NIL ELSE domain.trajs.first, looks] THEN LOOP;
saveDObj _ matchD^;
IF NOT looks.typeDef THEN [newStart, newLength, reverse] _ SimpleSegMatch[domain, looks, matchD]
ELSE [newStart, newLength, reverse] _ CompoundSegMatch[domain, complexLooks, matchD];
IF newLength > 0 THEN { -- we've found a match, but is it the (closest, longest) match?
IF start = newStart AND newLength > length THEN length _ newLength;
IF noneFound OR newStart < start THEN {
start _ newStart;
length _ newLength;
mapping _ MakeSegMapping[domain, start, length, reverse, looks, complexLooks];
bestDObj _ saveDObj;
};
noneFound _ FALSE;
};
ENDLOOP;
IF length > 0 THEN {
matchD^ _ bestDObj;
matchD.mapping _ NARROW[GList.Append[mapping, matchD.mapping]];
};
};

MakeSegMapping: PROC [domain: SearchInfo, start, length: NAT, reverse: BOOL, looks: LooksInfo, complexLooks: LIST OF LooksInfo] 
RETURNS [mapping: LIST OF ItemMatch _ NIL] = {
segList: LIST OF Segment _ NARROW[GList.NthTail[domain.segs, start]];
traj: Traj _ IF domain.slice.class.type = $Outline THEN domain.trajs.first ELSE NIL;
<<IF reverse AND looks.typeDef THEN segList _ NARROW[GList.Reverse[segList]];>>
THROUGH [0..length) DO
newItem: ItemMatch;
IF looks.typeDef THEN {
newItem _ NEW[ItemMatchObj _ [matcher: complexLooks.first.owner, matchee: [slice: domain.slice, traj: traj, seg: segList.first], 
backwards: reverse]];
complexLooks _ complexLooks.rest;
}
ELSE {
 newItem _ NEW[ItemMatchObj _ [matcher: looks.owner, matchee: [slice: domain.slice, traj: traj, seg: segList.first], backwards: 
reverse]];
};
mapping _ CONS[newItem, mapping];
segList _ segList.rest;
ENDLOOP;
};

FlattenOutSliceLooks: PROC [looksList: LIST OF REF ANY] RETURNS [newList: LIST OF REF ANY _ NIL] = {
FOR looksList _ looksList, looksList.rest UNTIL looksList=NIL DO
WITH looksList.first SELECT FROM
simple: LooksInfo => newList _ CONS[simple, newList];
complex: LIST OF LIST OF LooksInfo => {
FOR complex _ complex, complex.rest UNTIL complex=NIL DO
newList _ CONS[complex.first, newList];
ENDLOOP;
};
ENDCASE => ERROR;
ENDLOOP;
newList _ NARROW[GList.DReverse[newList], LIST OF REF ANY];
};

SimpleSegMatch: PROC [domain: SearchInfo, looks: LooksInfo, matchD: MatchDescriptor] RETURNS [start, length: NAT _ 0, reverse: 
BOOL] = {
IF NOT looks.shapeDef THEN { -- Grab first run that fits description
index: NAT _ 0;
FOR segs: LIST OF Segment _ domain.segs, segs.rest UNTIL segs=NIL DO
match: BOOL _ SegmentMatch[segs.first, looks];
IF match AND length < 1 THEN start _ index;
IF match THEN length _ length + 1;
IF length > 0 AND NOT match THEN EXIT;
index _ index + 1;
ENDLOOP;
}
ELSE {
[start, length, reverse] _ ShapeDrivenSegMatch[domain, looks, matchD];
RETURN[start, length, reverse];
};
};

ShapeDrivenSegMatch: PROC [domain: SearchInfo, looks: LooksInfo, matchD: MatchDescriptor] RETURNS [start, length: NAT _ 0, reverse: 
BOOL] = {
<<looks.shapeDef is TRUE, looks.typeDef is FALSE>>
matchData: MatchData _ MatchViewer.GetMatchData[];
revCheck: BOOL _ NOT AtomButtons.GetBinaryState[matchData.polarity];
matchList: LIST OF Segment _ NIL;
IF looks.shapeDef AND looks.shape.closed THEN revCheck _ FALSE; -- can't flip closed turtles!
FOR segs: LIST OF Segment _ domain.segs, segs.rest UNTIL segs = NIL DO
tail: LIST OF TurtleInfo _ NIL;
ends: LIST OF LIST OF TurtleInfo _ NIL;
<<Find longest run, starting at subList.first, for which we have a basic match>>
FOR subList: LIST OF Segment _ segs, subList.rest UNTIL subList=NIL DO
IF SegmentMatch[subList.first, looks] THEN {
matchList _ CONS[subList.first, matchList];
tail _ MatchTurtle.SegmentToTurtle[subList.first, tail, domain.reverse];
ends _ CONS[MatchTurtle.CopyTurtleTail[tail], ends]; -- list of backwards turtleTails
}
ELSE EXIT;
ENDLOOP;
<<Now we must find the longest sub-run with a shape match in matchList>>
FOR matchList _ matchList, matchList.rest UNTIL matchList = NIL DO -- matchList is backwards
turtle: TurtleHeader _ MatchTurtle.PackageTurtleTail[ends.first];
revTurtle: TurtleHeader _ turtle;
IF domain.reverse THEN turtle _ MatchTurtle.FlipTurtle[turtle] -- so polarity works right
ELSE IF revCheck THEN revTurtle _ MatchTurtle.FlipTurtle[revTurtle];
IF MatchTurtle.TurtleEqual[looks.shape, turtle, MatchViewer.GetMatchTolerance[], matchD.posD] THEN RETURN[start, 
GList.Length[matchList], FALSE];
IF revCheck AND MatchTurtle.TurtleEqual[looks.shape, revTurtle, MatchViewer.GetMatchTolerance[], matchD.posD] THEN RETURN[start, 
GList.Length[matchList], TRUE];
ends _ ends.rest;
ENDLOOP;
start _ start + 1;
ENDLOOP;
};

CompoundSegMatch: PROC [domain: SearchInfo, looks: LIST OF LooksInfo, matchD: MatchDescriptor] RETURNS [start, length: NAT _ 0, 
reverse: BOOL _ FALSE] = {
<<We're being called, since typeDef is TRUE (shapeDef may be TRUE)>>
matchData: MatchData _ MatchViewer.GetMatchData[];
revCheck: BOOL _ NOT AtomButtons.GetBinaryState[matchData.polarity];
single: LooksInfo;
matchLength: NAT _ GList.Length[looks];
revLooks: LIST OF LooksInfo;
IF looks=NIL THEN RETURN ELSE single _ looks.first; -- if looks is NIL, target not compound
IF single.shapeDef AND single.shape.closed THEN revCheck _ FALSE; -- can't flip closed turtles!
revLooks _ IF revCheck THEN FlipLooks[looks] ELSE NIL;
FOR subList: LIST OF Segment _ domain.segs, subList.rest UNTIL subList = NIL DO
foreMatch: BOOL _ TRUE;
backMatch: BOOL _ revCheck;
foreLooks: LIST OF LooksInfo _ looks;
backLooks: LIST OF LooksInfo _ revLooks;
segs: LIST OF Segment _ subList;
tail: LIST OF TurtleInfo _ NIL;
turtle: TurtleHeader;
THROUGH [0..matchLength) DO
IF segs=NIL THEN RETURN; -- No matches found (signaled by length _ 0)
IF foreMatch AND NOT SegmentMatch[segs.first, foreLooks.first] THEN foreMatch _ FALSE;
IF backMatch AND NOT SegmentMatch[segs.first, backLooks.first] THEN backMatch _ FALSE;
IF NOT foreMatch AND NOT backMatch THEN EXIT;
IF single.shapeDef THEN tail _ MatchTurtle.SegmentToTurtle[segs.first, tail, domain.reverse];
segs _ segs.rest; -- do list bookkeeping . . .
foreLooks _ foreLooks.rest;
IF backLooks # NIL THEN backLooks _ backLooks.rest;
ENDLOOP;
IF single.shapeDef AND (foreMatch OR backMatch) THEN {
turtle _ MatchTurtle.PackageTurtleTail[tail];
IF domain.reverse THEN turtle _ MatchTurtle.FlipTurtle[turtle];
};
IF foreMatch THEN {
IF NOT single.shapeDef OR MatchTurtle.TurtleEqual[single.shape, turtle, MatchViewer.GetMatchTolerance[], matchD.posD] THEN 
RETURN[start, matchLength, FALSE];
};
IF backMatch THEN {
IF NOT single.shapeDef OR MatchTurtle.TurtleEqual[single.shape, MatchTurtle.FlipTurtle[turtle], MatchViewer.GetMatchTolerance[], 
matchD.posD] THEN RETURN[start, matchLength, TRUE];
};
start _ start + 1;
ENDLOOP;
<<No matches found (signaled by length _ 0)>>
};

FlipLooks: PROC [looksList: LIST OF LooksInfo] RETURNS [newList: LIST OF LooksInfo] = {
newList _ NARROW[GList.Reverse[looksList], LIST OF LooksInfo];
<<And more to come!!>>
};

FindMatchInOutline: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: SliceDescriptor, 
rest: SearchInfo] = {
entireSlice: SliceDescriptor _ domain.slice.class.newParts[domain.slice, NIL, slice];
looks: LooksInfo;
complexLooks: LIST OF LIST OF LooksInfo;
matchLevel: MatchViewer.MatchLevel _ MatchViewer.GetMatchData[].matchLevel;
IF matchLevel = trajLevel THEN {
[match, rest] _ FindTrajMatchInOutline[domain, fromLooks, matchD];
RETURN[match, rest];
};
IF matchLevel = anywhere THEN {
[match, rest] _ FindAnywhereMatchInOutline[domain, fromLooks, matchD];
RETURN[match, rest];
};
FOR fromLooks _ fromLooks, fromLooks.rest UNTIL fromLooks=NIL DO
WITH fromLooks.first SELECT FROM
simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
complex: LIST OF LIST OF LooksInfo => {
looks _ complex.first.first;
complexLooks _ complex;
};
ENDCASE => ERROR;
IF matchLevel = sliceLevel THEN {
trajList: LIST OF Traj _ GGOutline.TrajectoriesOfOutline[domain.slice];
IF (looks.typeDef OR looks.shapeDef) AND complexLooks # NIL THEN {
    IF GList.Length[complexLooks] # GList.Length[trajList] THEN LOOP; -- different traj count
IF ComplexMatch[entireSlice, complexLooks, matchD] THEN RETURN[entireSlice, MakeEmpty[domain]];
}
ELSE {
IF SimpleMatch[entireSlice, looks, matchD] THEN RETURN[entireSlice, MakeEmpty[domain]];
};
}
ENDLOOP;
RETURN[NIL, MakeEmpty[domain]];
};

    FindTrajMatchInOutline: PROC [domain: SearchInfo, fromLooks: LIST OF REF ANY, matchD: MatchDescriptor] RETURNS [match: 
    SliceDescriptor, rest: SearchInfo] = {
    looks: LooksInfo;
    complexLooks: LIST OF LIST OF LooksInfo;
    domain _ CopySearchInfo[domain];
    FOR trajs: LIST OF Traj _ domain.trajs, trajs.rest UNTIL trajs=NIL DO
    currentTraj: Traj _ trajs.first;
    domain.trajs _ trajs.rest;
    FOR fromList: LIST OF REF ANY _ fromLooks, fromList.rest UNTIL fromList=NIL DO
    WITH fromList.first SELECT FROM
    simple: LooksInfo => {looks _ simple; complexLooks _ NIL;};
    complex: LIST OF LIST OF LooksInfo => {
    looks _ complex.first.first;
    complexLooks _ complex;
    };
    ENDCASE => ERROR;
    IF complexLooks=NIL THEN { -- ie, simple
    seq: Sequence _ GGSequence.CreateComplete[currentTraj];
    sliceD: SliceDescriptor _ GGOutline.DescriptorFromSequence[domain.slice, seq];
    IF SimpleMatch[sliceD, looks, matchD] THEN RETURN[sliceD, domain];
        }
        ELSE {
            FOR list: LIST OF LIST OF LooksInfo _ complexLooks, list.rest UNTIL list=NIL DO
                IF TrajMatch[currentTraj, list.first, matchD] THEN {
                seq: Sequence _ GGSequence.CreateComplete[currentTraj];
                match _ GGOutline.DescriptorFromSequence[domain.slice, seq];
                RETURN[match, domain];
                };
                ENDLOOP;
            };
        ENDLOOP;
        ENDLOOP;
        RETURN[NIL, domain];
        };

    SimpleMatch: PROC [sliceD: SliceDescriptor, looks: LooksInfo, matchD: MatchDescriptor _ NIL, checkShape: BOOL _ TRUE] RETURNS 
    [match: BOOL _ TRUE] = {
    slice: Slice _ sliceD.slice;
    IF looks.typeDef AND looks.type # slice.class.type THEN RETURN[FALSE];
    IF looks.classDef AND looks.class # slice.class.type THEN RETURN[FALSE];
    IF looks.colorDef AND NOT ColorEqual[looks.color, slice.class.getStrokeColor[slice, sliceD.parts]] THEN RETURN[FALSE];
    IF looks.fillColorDef AND NOT ColorEqual[looks.fillColor, slice.class.getFillColor[slice]] THEN RETURN[FALSE];
    IF looks.stringDef AND (slice.class.type # $Text OR NOT Rope.Equal[GGSlice.GetText[slice], looks.string]) THEN RETURN[FALSE];
    IF looks.fontDef AND NOT FontEqual[looks.font, GGSlice.GetFontData[slice].fontData] THEN RETURN[FALSE];
    IF looks.fontTformDef AND NOT FontAndTransformEqual[looks.fontTform, GGSlice.GetFontData[slice].fontData] THEN RETURN[FALSE];
    IF looks.dashesDef THEN {
    dashInfo: DashInfo _ NEW[DashInfoObj];
        [dashed: dashInfo.dashed, pattern: dashInfo.pattern, offset: dashInfo.offset, length: dashInfo.length] _ 
        slice.class.getDashed[slice, sliceD.parts];
        IF NOT DashEqual[dashInfo, looks.dashes] THEN RETURN[FALSE];
        };
    IF looks.jointsDef AND looks.joints # slice.class.getStrokeJoint[slice, sliceD.parts] THEN RETURN[FALSE];
    IF looks.endsDef AND looks.ends # slice.class.getStrokeEnd[slice, sliceD.parts] THEN RETURN[FALSE];
    IF looks.widthDef AND looks.width # slice.class.getStrokeWidth[slice, sliceD.parts] THEN RETURN[FALSE];
    IF checkShape AND looks.shapeDef THEN {
    IF slice.class.type = $Outline THEN {
    seqs: LIST OF Sequence _ GGOutline.SequencesOfOutline[sliceD];
    IF seqs=NIL OR seqs.rest#NIL THEN RETURN[FALSE]; -- can't match multiple spans
    IF NOT MatchTurtle.TurtleEqual2[looks.shape, MatchTurtle.TrajToTurtle[seqs.first.traj], MatchViewer.GetMatchTolerance[], 
    matchD.posD] THEN RETURN[FALSE];
    }
    ELSE IF NOT MatchTurtle.TurtleEqual2[looks.shape, MatchTurtle.GetShapeOfSlice[slice], MatchViewer.GetMatchTolerance[], matchD.posD] 
    THEN RETURN[FALSE];
    };
    IF checkShape THEN AddMatch[matchD, looks.owner, SliceDToItemID[sliceD]];
    };

AddMatch: PROC [matchD: MatchDescriptor, matcher, matchee: ItemID, backwards: BOOL _ FALSE] = {
newMatch: ItemMatch _ NEW[ItemMatchObj _ [matcher: matcher, matchee: matchee, backwards: backwards]];
matchD.mapping _ CONS[newMatch, matchD.mapping];
};

SliceDToItemID: PROC [sliceD: SliceDescriptor] RETURNS [itemID: ItemID] = {
<<NOTE: only works for SliceDescriptors of entire slices (if slice is not an outline) or SliceDesriptors of single trajectories (if 
slice is an outline)>>
itemID.slice _ sliceD.slice;
IF sliceD.slice.class.type = $Outline THEN {
seqs: LIST OF Sequence _ GGOutline.SequencesOfOutline[sliceD];
IF seqs=NIL OR seqs.rest#NIL THEN ERROR; -- must include a single trajectory
itemID.traj _ seqs.first.traj;
};
};

ComplexMatch: PROC [sliceD: SliceDescriptor, sliceLooks: LIST OF LIST OF LooksInfo, matchD: MatchDescriptor] RETURNS [BOOL _ TRUE] 
= {
<<At this point it is known that the slice is either a box or an outline, and sliceLooks is of complex form>>
SELECT sliceD.slice.class.type FROM
$Outline => RETURN[ComplexOutlineMatch[sliceD, sliceLooks, matchD]];
$Box => RETURN[ComplexBoxMatch[sliceD, sliceLooks, matchD]];
ENDCASE => ERROR;
};

ComplexBoxMatch: PROC [sliceD: SliceDescriptor, sliceLooks: LIST OF LIST OF LooksInfo, matchD: MatchDescriptor] RETURNS [BOOL _ 
TRUE] = {
GatherSegs: GGModelTypes.WalkProc = {segList _ CONS[seg, segList];};
segList: LIST OF Segment _ NIL;
looks: LooksInfo;
slice: Slice _ sliceD.slice;
IF GList.Length[sliceLooks.first] # 4 THEN RETURN[FALSE]; -- boxes have 4 segs.  We may have to change this later on if we allow 
wildcard segs
<<First do slice specific checks>>
    looks _ sliceLooks.first.first;
    IF looks.fillColorDef AND NOT ColorEqual[looks.fillColor, slice.class.getFillColor[slice]] THEN RETURN [FALSE];
    IF looks.shapeDef AND NOT MatchTurtle.TurtleEqual2[looks.shape, MatchTurtle.GetShapeOfSlice[slice], 
    MatchViewer.GetMatchTolerance[], matchD.posD] THEN RETURN [FALSE]; -- shape may be out of phase with segments!
<<Looks good so far.  Now we match against the individual segments>>
[] _ GGSlice.WalkSegments[slice, GatherSegs];
segList _ NARROW[GList.DReverse[segList]];
IF NOT SegListMatch[segList, sliceLooks.first] THEN RETURN [FALSE];
FOR looksList: LIST OF LooksInfo _ sliceLooks.first, looksList.rest UNTIL looksList = NIL DO
AddMatch[matchD, looksList.first.owner, [slice: sliceD.slice, seg: segList.first]];
segList _ segList.rest;
ENDLOOP; -- register matches
};

SegListMatch: PROC [segList: LIST OF Segment, looks: LIST OF LooksInfo] RETURNS [BOOL _ TRUE] = {
IF GList.Length[segList] # GList.Length[looks] THEN RETURN[FALSE]; -- this will change with advent of wildcards
FOR segList _ segList, segList.rest UNTIL segList=NIL DO
IF NOT SegmentMatch[segList.first, looks.first] THEN RETURN[FALSE];
looks _ looks.rest;
ENDLOOP;
};

ComplexOutlineMatch: PROC [sliceD: SliceDescriptor, sliceLooks: LIST OF LIST OF LooksInfo, matchD: MatchDescriptor] RETURNS [BOOL _ 
FALSE] = {
<<We're matching on the shape or type (or both) of the Outline trajectories>>
matchData: MatchData _ MatchViewer.GetMatchData[];
structure: BOOL _ TRUE;
trajs: LIST OF Traj _ GGOutline.TrajectoriesOfOutline[sliceD.slice]; -- sliceD is complete
IF structure THEN {
copyD: MatchDescriptor _ NEW[MatchDObj _ matchD^];
traj: Traj _ trajs.first;
trajLooks: LIST OF LooksInfo _ sliceLooks.first;
looks: LooksInfo _ trajLooks.first;
matcher: MatchTurtle.Matcher;
next: PositionDescriptor;
IF matchD.posD.valid THEN RETURN[OutlineMatchAux[trajs, sliceLooks, structure, matchD]]; -- ie, we already have an orientation to 
match on.
<<Try to match traj with looks, for every possible orientation...>>
    IF NOT TrajMatch[traj, trajLooks, copyD, FALSE] THEN RETURN[FALSE];
    IF NOT looks.shapeDef THEN RETURN[OutlineMatchAux[trajs.rest, sliceLooks.rest, structure, NIL]];
    matcher _ MatchTurtle.CreateMatcher[looks.shape, MatchTurtle.TrajToTurtle[traj], MatchViewer.GetMatchTolerance[]];
    WHILE (next _ MatchTurtle.NextMatch[matcher]) # NIL DO
        copyD.posD _ next;
        IF OutlineMatchAux[trajs.rest, sliceLooks.rest, structure, copyD] THEN {
            matchD^ _ copyD^;
            RETURN[TRUE];
            };
        ENDLOOP;
    }
    ELSE {
        MatchViewer.ErrorFeedback["Only can deal with structure matches now."];
        };
    };

OutlineMatchAux: PROC [trajs: LIST OF Traj, sliceLooks: LIST OF LIST OF LooksInfo, structure: BOOL, matchD: MatchDescriptor] 
RETURNS [BOOL _ TRUE] = {
<<We're matching on the shape or type (or both) of the Outline trajectories.>>
IF trajs=NIL THEN RETURN[TRUE]; -- base case
IF structure THEN {
traj: Traj _ trajs.first;
trajLooks: LIST OF LooksInfo _ sliceLooks.first;
looks: LooksInfo _ trajLooks.first;
    segGen: SegmentGenerator _ GGSequence.SegmentsInTraj[traj];
copyD: MatchDescriptor _ NEW[MatchDObj _ matchD^];
IF NOT TrajMatch[traj, trajLooks, copyD, FALSE] THEN RETURN[FALSE];
    IF looks.shapeDef AND NOT MatchTurtle.TurtleEqual[looks.shape, MatchTurtle.TrajToTurtle[traj], MatchViewer.GetMatchTolerance[], 
    matchD.posD] THEN RETURN[FALSE];
    IF NOT OutlineMatchAux[trajs.rest, sliceLooks.rest, structure, copyD] THEN RETURN[FALSE]
    ELSE matchD^ _ copyD^; -- only make changes in the descriptor if there's a match!
    }
    ELSE {
        MatchViewer.ErrorFeedback["Only can deal with structure matches now."];
        RETURN[FALSE];
        };
    };

TrajMatch: PROC [traj: Traj, trajLooks: LIST OF LooksInfo, matchD: MatchDescriptor, checkShape: BOOL _ TRUE] RETURNS [BOOL _ TRUE] 
= {
    <<We're matching on shape or type (or both) of Outline trajectories>>
    segGen: SegmentGenerator _ GGSequence.SegmentsInTraj[traj];
    looks: LooksInfo _ trajLooks.first;
    localMapping: LIST OF ItemMatch _ NIL;
    IF looks.typeDef THEN {
        <<First do traj & slice specific checks>>
        IF looks.classDef AND looks.class # $Outline THEN RETURN[FALSE];
        IF looks.jointsDef AND looks.joints # GGTraj.GetTrajStrokeJoint[traj] THEN RETURN[FALSE];
        IF looks.fillColorDef AND NOT ColorEqual[looks.fillColor, traj.parent.class.getFillColor[traj.parent]] THEN RETURN [FALSE];
        <<Next do lower level segment checks if typeDef is TRUE>>
        IF traj.segCount # GList.Length[trajLooks] THEN RETURN[FALSE];
        FOR seg: Segment _ GGSequence.NextSegment[segGen], GGSequence.NextSegment[segGen] UNTIL seg = NIL DO
            IF NOT SegmentMatch[seg, trajLooks.first] THEN RETURN[FALSE];
            localMapping _ CONS[NEW[ItemMatchObj _ [matcher: trajLooks.first.owner, matchee: [slice: traj.parent, traj: traj, seg: seg]]], 
            localMapping]; -- looks good so far
            trajLooks _ trajLooks.rest;
            ENDLOOP;
        }
    ELSE { -- match the looks characteristics on the traj as a whole
        seq: Sequence _ GGSequence.CreateComplete[traj];
        sliceD: SliceDescriptor _ GGOutline.DescriptorFromSequence[traj.parent, seq];
    IF NOT SimpleMatch[sliceD, looks, matchD, FALSE] THEN RETURN[FALSE];
    localMapping _ LIST[NEW[ItemMatchObj _ [matcher: looks.owner, matchee: [slice: traj.parent, traj: traj]]]];
    };
    IF checkShape AND looks.shapeDef AND NOT MatchTurtle.TurtleEqual2[looks.shape, MatchTurtle.TrajToTurtle[traj], 
    MatchViewer.GetMatchTolerance[], matchD.posD] THEN RETURN [FALSE];
    matchD.mapping _ NARROW[GList.Append[localMapping, matchD.mapping]]; -- save mapping
    };

SegmentMatch: PROC [seg: Segment, looks: LooksInfo] RETURNS [BOOL _ TRUE] = {
<<Segment-Level checks >>
IF looks.typeDef AND looks.type # seg.class.type THEN RETURN[FALSE];
IF looks.colorDef AND NOT ColorEqual[looks.color, seg.color] THEN RETURN[FALSE];
IF looks.dashesDef THEN {
dashInfo: DashInfo _ NEW[DashInfoObj _ [dashed: seg.dashed, pattern: seg.pattern, offset: seg.offset, length: seg.length]];
    IF NOT DashEqual[dashInfo, looks.dashes] THEN RETURN[FALSE];
    };
IF looks.endsDef AND looks.ends # seg.strokeEnd THEN RETURN[FALSE];
IF looks.widthDef AND looks.width # seg.strokeWidth THEN RETURN[FALSE];
};

SliceLevelMatch: PROC [slice: Slice, traj: Traj _ NIL, looks: LooksInfo] RETURNS [BOOL _ TRUE] = {
<<Slice-Level checks>>
IF looks.classDef AND looks.class # slice.class.type THEN RETURN[FALSE];
IF looks.fillColorDef AND NOT ColorEqual[looks.fillColor, slice.class.getFillColor[slice]] THEN RETURN[FALSE];
IF slice.class.type = $Outline AND looks.jointsDef AND traj # NIL AND looks.joints # GGTraj.GetTrajStrokeJoint[traj] THEN 
RETURN[FALSE];
};

<<Characteristics Equivalence Routines>>

LooksEqual: PUBLIC PROC [l1, l2: LooksInfo] RETURNS [BOOL _ TRUE] = {
<<Doesn't compare the shape fields>>
IF l1 = l2 THEN RETURN[TRUE];
IF l1 = NIL OR l2 = NIL THEN RETURN[FALSE];
IF (l1.classDef # l2.classDef) OR (l1.typeDef # l2.typeDef) OR (l1.colorDef # l2.colorDef) OR (l1.fillColorDef # l2.fillColorDef) 
OR (l1.stringDef # l2.stringDef) OR (l1.fontDef # l2.fontDef) OR (l1.fontTformDef # l2.fontTformDef) OR (l1.dashesDef # 
l2.dashesDef) OR (l1.jointsDef # l2.jointsDef) OR (l1.endsDef # l2.endsDef) OR (l1.widthDef # l2.widthDef) THEN RETURN[FALSE];
IF l1.classDef AND l1.class # l2.class THEN RETURN[FALSE];
IF l1.typeDef AND l1.type # l2.type THEN RETURN[FALSE];
IF l1.colorDef AND NOT ColorEqual[l1.color, l2.color] THEN RETURN[FALSE];
IF l1.fillColorDef AND NOT ColorEqual[l1.fillColor, l2.fillColor] THEN RETURN[FALSE];
IF l1.stringDef AND NOT Rope.Equal[l1.string, l2.string] THEN RETURN[FALSE];
IF l1.fontDef AND NOT FontEqual[l1.font, l2.font] THEN RETURN[FALSE];
IF l1.fontTformDef AND NOT FontAndTransformEqual[l1.fontTform, l2.fontTform] THEN RETURN[FALSE];
IF l1.dashesDef AND NOT DashEqual[l1.dashes, l2.dashes] THEN RETURN[FALSE];
IF l1.jointsDef AND l1.joints # l2.joints THEN RETURN[FALSE];
IF l1.endsDef AND l1.ends # l2.ends THEN RETURN[FALSE];
IF l1.widthDef AND l1.width # l2.width THEN RETURN[FALSE];
};

FontAndTransformEqual: PROC [f1, f2: GGFont.FontData] RETURNS [match: BOOL _ FALSE] = {
<<Uses the criteria of GGEvent.SelectMatchingData>>
    maxPixels: REAL = 10000.0;
IF f1 # NIL AND f2 # NIL AND Rope.Equal[f1.literal, f2.literal, FALSE] AND RealFns.AlmostEqual[f1.storedSize, f2.storedSize, -9] 
AND ImagerTransformation.CloseToTranslation[f1.transform, f2.transform, maxPixels] THEN RETURN[TRUE];
};

FontEqual: PROC [f1, f2: GGFont.FontData] RETURNS [match: BOOL _ FALSE] = {
IF f1 # NIL AND f2 # NIL AND Rope.Equal[f1.literal, f2.literal, FALSE] AND RealFns.AlmostEqual[f1.storedSize, f2.storedSize, -9] 
THEN RETURN[TRUE];
};

DashEqual: PROC [d1, d2: DashInfo] RETURNS [match: BOOL _ TRUE] = {
IF d1.dashed = FALSE AND d2.dashed = FALSE THEN RETURN [TRUE];
IF d1.dashed # d2.dashed OR d1.offset # d2.offset OR d1.length # d2.length OR d1.pattern.len # d2.pattern.len THEN RETURN [FALSE];
FOR i:INT IN [0..d1.pattern.len) DO
IF d1.pattern[i] # d2.pattern[i] THEN RETURN[FALSE];
ENDLOOP;
};

ColorEqual: PROC [c1, c2: Imager.Color] RETURNS [BOOL] = {
epsilon: REAL = 1.0E-2;
r1, g1, b1, r2, g2, b2: REAL;
IF c1 = c2 THEN RETURN [TRUE];
IF c1 = NIL OR c2 = NIL THEN RETURN[FALSE];
[r1, g1, b1] _ GGUtility.ExtractRGB[c1];
[r2, g2, b2] _ GGUtility.ExtractRGB[c2];
RETURN [(r1=r2 AND g1=g2 AND b1=b2) OR (ABS[r1-r2]<epsilon AND ABS[g1-g2]<epsilon AND ABS[b1-b2]<epsilon)];
};

<<>>
<<*** New Search Code *** >>

    NewSearch4: PROC [them: GGData, event: LIST OF REF ANY] RETURNS [found: BOOL] = {
        <<Find any object that matches an object in the From viewer (searchOp = disjunction)>>
        matchData: MatchData _ MatchViewer.GetMatchData[];
    searchState: SearchState _ Match.GetSearchState[];
    IF them # matchData.theirData OR GGCaret.GetPoint[them.caret] # matchData.lastCaretPos OR event.rest.first = $SearchFromTop THEN {
    searchState.ahead _ RemakeSearchList[them, event.rest.first, TRUE];
    matchData.theirData _ them;
        matchData.lastCaretPos _ GGCaret.GetPoint[them.caret];
    } --searching in new viewer or caret position changed or starting search from top
    ELSE IF event.rest.first # searchState.lastDirection THEN {
    normalGen: SliceDescriptorGenerator _ GGSelect.SelectedSlices[them.scene, normal];
    matchSelectD: SliceDescriptor _ NIL;
    FOR normalD: SliceDescriptor _ GGSelect.NextSliceDescriptor[normalGen], GGSelect.NextSliceDescriptor[normalGen] UNTIL normalD = NIL 
    DO
    GGSelect.SelectSlice[normalD, them.scene, match];
    ENDLOOP; -- make all normal-selected objects "match selected", so they're not included in search
    IF searchState.ahead # NIL THEN {
    firstSlice: Slice _ searchState.ahead.first.slice;
    matchSelectD _ GGSelect.FindSelectedSlice[firstSlice, them.scene, match];
    IF matchSelectD = NIL THEN matchSelectD _ firstSlice.class.newParts[firstSlice, NIL, none];
    };
    searchState.ahead _ RemakeSearchList[them, event.rest.first, TRUE];
    RemoveSelected[searchState.ahead, matchSelectD];  --do bookkeeping so that search will begin (in the other direction) where the 
    last search left off
    }; --search direction changed
    searchState.lastDirection _ IF event.rest.first = $SearchFromTop THEN $SearchBelow ELSE event.rest.first;
    [searchState.ahead, found] _ NewSearch4Aux[searchState.ahead, event.rest.first];
    IF NOT found THEN MatchViewer.ErrorFeedback["No match found."];
    };

NewSearch4Aux: PUBLIC PROC [searchList: LIST OF SearchInfo, direction: REF ANY] RETURNS [newSearchList: LIST OF SearchInfo, found: 
BOOL] = {
target: SliceDescriptor _ NIL;
    matchData: MatchData _ MatchViewer.GetMatchData[];
    check, checkNext: SearchInfo _ NIL;
    fromLooks: LIST OF REF ANY _ GetSourceLooks[];
matchD: MatchDescriptor _ Match.CreateMatchDescriptor[];
    DO
    IF NOT IsEmptySearchInfo[check] THEN { -- something left of this slice to match on
    [target, checkNext] _ FindMatchInSlice[check, fromLooks, direction, matchD];
        AdjustBitsOfDifference[check, checkNext, matchData.theirData.scene];
        IF target = NIL THEN check _ checkNext -- no match
        ELSE { -- we've matched something!
            fromData: GGData _ MatchViewer.GetFromData[];
            GGSelect.DeselectAll[matchData.theirData.scene, normal];
            IF NOT AtomButtons.GetBinaryState[matchData.contextSensitive] THEN Match.SelectMapped[matchData.theirData.scene, matchD.mapping]
            ELSE Match.SelectMapped[matchData.theirData.scene, Match.SelectionFilter[fromData.scene, matchD.mapping]];
            matchData.lastCaretPos _ [GGCaret.GetPoint[matchData.theirData.caret].x, target.slice.boundBox.hiY];
            GGCaret.SetAttractor[matchData.theirData.caret, matchData.lastCaretPos, [0, -1], NIL];
            GGWindow.RestoreScreenAndInvariants[paintAction: $SelectionChanged, ggData: matchData.theirData, remake: none, backgndOK: TRUE, 
            edited: FALSE, okToClearFeedback: TRUE];
            Match.SetLastMatchDescriptor[matchD];
            IF checkNext = NIL THEN ERROR --RETURN [searchList, TRUE]
            ELSE RETURN[CONS[checkNext, searchList], TRUE];
            };
        }
        ELSE -- no more interesting stuff in slice
            IF searchList # NIL THEN {
                IF check # NIL THEN GGSelect.DeselectEntireSlice[check.slice, matchData.theirData.scene, match];
                check _ searchList.first;
                searchList _ searchList.rest;
                }
            ELSE {
                GGSelect.DeselectAll[matchData.theirData.scene, normal];
                GGWindow.RestoreScreenAndInvariants[paintAction: $SelectionChanged, ggData: matchData.theirData, remake: none, backgndOK: TRUE, 
                edited: FALSE, okToClearFeedback: TRUE];
                Match.SetLastMatchDescriptor[NIL];
                RETURN[NIL, FALSE];
                };
        ENDLOOP;
    };

    AdjustBitsOfDifference: PROC [first, next: SearchInfo, scene: Scene] = {
        SegmentsInInfo: GGModelTypes.WalkProc = { RETURN[GList.Member[seg, next.segs]]; };
        <<If the next SearchInfo is Empty, then deselect the entire slice described by first>>
        IF IsEmptySearchInfo[next] THEN GGSelect.DeselectEntireSlice[first.slice, scene, match]
        ELSE { -- a bit more complicated (part of next still remains to be searched)
            SELECT first.slice.class.type FROM
                $Box => {
                    newSelection: SliceDescriptor _ GGSlice.WalkSegments[next.slice, SegmentsInInfo];
                    GGSelect.DeselectEntireSlice[first.slice, scene, match];
                    GGSelect.SelectSlice[newSelection, scene, match];
                    };
                $Outline => {
                    newSelection: SliceDescriptor _ GGSlice.WalkSegments[next.slice, SegmentsInInfo];
                    FOR trajList: LIST OF Traj _ next.trajs.rest, trajList.rest UNTIL trajList = NIL DO
                    seq: Sequence _ GGSequence.CreateComplete[trajList.first];
                    trajD: SliceDescriptor _ GGOutline.DescriptorFromSequence[seq.traj.parent, seq];
                    newSelection _ next.slice.class.unionParts[newSelection, trajD];
                        ENDLOOP;
                    GGSelect.DeselectEntireSlice[first.slice, scene, match];
                    GGSelect.SelectSlice[newSelection, scene, match];
                    };
                ENDCASE => GGSelect.DeselectEntireSlice[first.slice, scene, match];
            };
        };

    RemoveSelected: PUBLIC PROC [infoList: LIST OF SearchInfo, sliceD: SliceDescriptor] = {
        IF sliceD = NIL THEN RETURN;
        FOR iList: LIST OF SearchInfo _ infoList, iList.rest UNTIL iList = NIL DO
            IF sliceD.slice = iList.first.slice THEN RemoveDescriptorFromInfo[sliceD, iList.first];
            ENDLOOP;
        };

    RemoveDescriptorFromInfo: PUBLIC PROC [sliceD: SliceDescriptor, info: SearchInfo] = {
        FilterSegs: PROC [sliceD: SliceDescriptor, info: SearchInfo] = {
        segList, revSegs: LIST OF Segment _ NIL;
        segGen: SegmentGenerator _ GGSlice.SegmentsInDescriptor[sliceD];
        FOR seg: Segment _ GGSlice.NextSegment[segGen], GGSlice.NextSegment[segGen] UNTIL seg = NIL DO
        segList _ CONS [seg, segList];
        ENDLOOP; -- we've formed a list of segments in the descriptor
        revSegs _ NARROW[GList.Reverse[info.segs]];
        info.segs _ NIL;
        FOR infoSegs: LIST OF Segment _ revSegs, infoSegs.rest UNTIL infoSegs = NIL DO
        IF GList.Member[infoSegs.first, segList] THEN EXIT
        ELSE info.segs _ CONS[infoSegs.first, info.segs];
        ENDLOOP;
        };
        matchLevel: MatchViewer.MatchLevel _ MatchViewer.GetMatchData[].matchLevel;
        IF info.slice # sliceD.slice THEN RETURN; -- sliceD and info must relate to same slice
        IF sliceD.slice.class.isEmptyParts[sliceD] THEN RETURN; -- nothing to remove
        SELECT sliceD.slice.class.type FROM
            $Box => {
                IF matchLevel = sliceLevel OR matchLevel = trajLevel THEN info.empty _ TRUE
                ELSE FilterSegs[sliceD, info]; -- matchLevel = anywhere
            };
            $Outline => {
            IF matchLevel = sliceLevel THEN info.empty _ TRUE
            ELSE IF matchLevel = trajLevel THEN {
            revTrajs: LIST OF Traj _ NARROW[GList.Reverse[info.trajs]];
            info.trajs _ NIL;
            FOR trajs: LIST OF Traj _ revTrajs, trajs.rest UNTIL trajs = NIL DO
            seq: Sequence _ GGOutline.FindTrajInDescriptor[sliceD, trajs.first];
            IF NOT GGSequence.IsEmpty[seq] THEN EXIT
            ELSE info.trajs _ CONS[trajs.first, info.trajs];
            ENDLOOP;
            }
            ELSE { -- matchLevel = anywhere
            oldTrajs: LIST OF Traj _ info.trajs;
            revTrajs: LIST OF Traj _ NARROW[GList.Reverse[info.trajs]];
            info.trajs _ NIL;
            FOR trajs: LIST OF Traj _ revTrajs, trajs.rest UNTIL trajs = NIL DO
            seq: Sequence _ GGOutline.FindTrajInDescriptor[sliceD, trajs.first];
            info.trajs _ CONS[trajs.first, info.trajs];
            IF NOT GGSequence.IsEmpty[seq] THEN EXIT;
            ENDLOOP;
            IF info.trajs.first # oldTrajs.first THEN {
            info.segs _ NIL;
            AddSegs[info];
            };
                FilterSegs[sliceD, info];
            };
            };
        ENDCASE => info.empty _ TRUE;
    };

    RemakeSearchList: PUBLIC PROC [theirData: GGData, direction: REF ANY, select: BOOL] RETURNS [toSearch: LIST OF SearchInfo] = {
    <<toSearch will hold SearchInfo's for objects whose boundBox is below the caret if the search is progressing in a downwards 
    direction, and above the caret if the search is progressing upwards.  If select is true, then all slices ahead will be match 
    selected (and those behind will be cleared).  This routine is called during disjunction search.>>
    GetOrderedSlices: PROC [ggData: GGData, direction: REF ANY] RETURNS [sliceList: LIST OF Slice _ NIL] = {
    sliceGen: SliceGenerator _ GGScene.SlicesInScene[ggData.scene];
    caretPos: Point _ GGCaret.GetPoint[ggData.caret];
    SELECT direction FROM
    $SearchBelow => {
    FOR slice: Slice _ GGScene.NextSlice[sliceGen], GGScene.NextSlice[sliceGen] UNTIL slice = NIL DO
    IF caretPos.y >= slice.class.getBoundBox[slice].hiY THEN sliceList _ CONS[slice, sliceList];
    ENDLOOP;
    };
    $SearchAbove => {
    FOR slice: Slice _ GGScene.NextSlice[sliceGen], GGScene.NextSlice[sliceGen] UNTIL slice = NIL DO
    IF caretPos.y <= slice.class.getBoundBox[slice].hiY THEN sliceList _ CONS[slice, sliceList];
    ENDLOOP;
    };
    $SearchFromTop => {
    FOR slice: Slice _ GGScene.NextSlice[sliceGen], GGScene.NextSlice[sliceGen] UNTIL slice = NIL DO
    sliceList _ CONS[slice, sliceList];
    ENDLOOP;
    };
    ENDCASE => ERROR;
    sliceList _ HeightSort[sliceList, IF direction = $SearchAbove THEN FALSE ELSE TRUE];
    };
        caretPos: Point _ GGCaret.GetPoint[theirData.caret];
        slices: LIST OF Slice _ GetOrderedSlices[theirData, direction];
        IF select THEN GGSelect.DeselectAll[theirData.scene, match]; -- makes the subsequent selections zoom!
    FOR sList: LIST OF Slice _ slices, sList.rest UNTIL sList = NIL DO
    IF select THEN GGSelect.SelectEntireSlice[sList.first, theirData.scene, match];
    toSearch _ CONS[CreateSearchInfo[sList.first, direction], toSearch];
    ENDLOOP;
    };
<<>>
HeightSort: PUBLIC PROC [slices: LIST OF Slice, ascending: BOOL] RETURNS [LIST OF Slice] = {
    <<Height sorts slices by upper left of bounding box (according to the ascending BOOL).  Breaks ties by using loX values (ordered 
    according to the complement of the ascending BOOL), so if ascending = FALSE, search will proceed downwards and left to right.>>
    CompareProc: GList.CompareProc = {
        <<[ref1: REF ANY, ref2: REF ANY] RETURNS [Basics.Comparison]>>
        slice1: Slice _ NARROW[ref1];
        slice2: Slice _ NARROW[ref2];
        priority1: REAL _ slice1.class.getBoundBox[slice1].hiY;
        priority2: REAL _ slice2.class.getBoundBox[slice2].hiY;
        IF priority1 = priority2 THEN {
            priority1 _ slice2.class.getBoundBox[slice2].loX; -- slices swapped intentionally
            priority2 _ slice1.class.getBoundBox[slice1].loX;
            };
        IF ascending THEN RETURN[Real.CompareREAL[priority1, priority2]]
        ELSE RETURN[Real.CompareREAL[priority2, priority1]];
        };
slices _ NARROW[GList.Sort[slices, CompareProc]];
RETURN[slices];
};

CopySearchInfo: PROC [info: SearchInfo] RETURNS [newInfo: SearchInfo] = {
<<Since only non-destructive list operations are permitted on the field of SearchInfo's, we can just copy the SearchInfoObj>>
newInfo _ NEW[SearchInfoObj _ info^];
};

MakeEmpty: PROC [info: SearchInfo] RETURNS [newInfo: SearchInfo] = {
newInfo _ CopySearchInfo[info];
newInfo.empty _ TRUE;
};

END.