-
Notifications
You must be signed in to change notification settings - Fork 131
Expand file tree
/
Copy pathtrynext.cc
More file actions
158 lines (144 loc) · 6.18 KB
/
trynext.cc
File metadata and controls
158 lines (144 loc) · 6.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*************************************************************************//**
* \file trynext.cc *
* *
* Description: Contains the tryNext() functions for the EntList descen- *
* dants. Their purpose is to search for additional branches *
* of OrList's to try the next available untried solution. AND *
* and ANDOR iterate through their children looking for OR's. *
* OR tries the next branch of its children if more remain. *
* *
* Created by: David Rosenfeld *
* Date: 10/24/96 *
*****************************************************************************/
#include "complexSupport.h"
#include "scl_memmgr.h"
// Local function prototypes:
static EntList * firstCandidate( EntList * );
static EntList * nextCandidate( EntList * );
/**
* Loops backwards through the children of this, recursively searching for
* alternate solutions (i.e., OR's which have alternate paths we haven't
* tried yet). We loop through all MultList type children which may have
* an OR with additional choices. (Which children to try is determined in
* a local function. We loop backwards because this is the reverse of the
* order we set the OR's. Later choices must be redone before earlier
* (reasons discussed in notes, 10/17). This function is the tryNext()
* for AND and ANDOR; the OR version is redefined.
*/
MatchType MultList::tryNext( EntNode * ents ) {
MatchType retval;
EntList * child = getLast();
child = firstCandidate( child );
while( child != NULL ) {
if( ( retval = ( ( MultList * )child )->tryNext( ents ) ) == MATCHALL ) {
// We're done - a good solution was found.
return MATCHALL;
}
if( retval == NEWCHOICE ) {
// If a new viable choice was found below, we must now reset all
// later OR's to their first choice. (That's what acceptChoice()
// does when choice = LISTEND.) This is necessary so that we can
// exhaust every possibility with this new choice. To do this we
// first reset all our children, and then return NEWCHOICE so that
// our parent (if exists) will also know to reset all its later OR
// children.
while( ( child = nextCandidate( child ) ) != NULL ) {
if( child->acceptChoice( ents ) && ents->allMarked() ) {
return MATCHALL;
}
}
return NEWCHOICE;
}
child = firstCandidate( child->prev );
}
// If we got here, we didn't find any new OR choices:
return NOMORE;
}
/**
* Finds an EntList from child's list which may have an OR with more
* choices below it. The acceptable choices are described in commenting
* below.
*/
static EntList * firstCandidate( EntList * child ) {
EntList * ent = child->lastNot( SIMPLE );
while( ent != NULL ) {
if( ent->viableVal() >= MATCHSOME ) {
// Return any non-SIMPLE ent where viable >= MATCHSOME. We even
// want to check an OR where numChoices = 1, because it may have
// an OR descendant with more choices.
return ent;
}
ent = ent->prevNot( SIMPLE );
}
return ent;
}
/**
* Same as prev function, searches forwards from ent after child.
*/
static EntList * nextCandidate( EntList * child ) {
EntList * ent = child->nextNot( SIMPLE );
while( ent != NULL ) {
if( ent->viableVal() >= MATCHSOME ) {
return ent;
}
ent = ent->nextNot( SIMPLE );
}
return ent;
}
/**
* Tries out the next choice of this. Basic algorithm is to first recurse
* to check for other solutions in the descendants of the current choice,
* and then to try our next choice.
*/
MatchType OrList::tryNext( EntNode * ents ) {
MatchType retval;
EntList * child;
if( choice == LISTEND ) {
// if we've already exhausted all the choices in this OR,
return NOMORE;
}
// First try other choices of descendants of current choice:
child = getChild( choice );
if( child->multiple() ) {
// I.e., if there are (or may be) more choices within the current
// choice, try those first. We must be sure to exhaust all choices in
// our descendants before moving on.
retval = ( ( MultList * )child )->tryNext( ents );
if( retval == MATCHALL ) {
return MATCHALL;
}
if( retval == NEWCHOICE ) {
// I.e., we found a next choice to go to, return so that the
// EntLists on the higher levels (if there are) can retry all the
// later choices with the new choice we just found. Otherwise,
// we'll continue below looking into our next choice.
return NEWCHOICE;
}
}
// No other choices among our descendants. Look for new choice at our
// level:
child->unmarkAll( ents );
if( choiceCount == 1 ) {
// Quick way to determine that there won't be any more choices here.
// (Also, it's nec. to unmark now, as we did above before returning and
// before the calling tryNext() tries earlier OR's - see notes, 11/12.)
choice = LISTEND;
return NOMORE;
}
// Otherwise, try our next:
if( acceptNextChoice( ents ) ) {
if( ents->allMarked() ) {
return MATCHALL;
}
return NEWCHOICE;
} else {
// Must have been no next choice (or none which mark anything new).
// acceptNextChoice() has set choice to LISTEND. We leave this OR
// unset and return NOMORE. If our calling function finds another
// choice elsewhere, it will reloop forwards and set all later OR's to
// their first choices, so that we'll be able to test every possibility
// with the new choice. At that time, this OrList will be reset to its
// first choice too.
return NOMORE;
}
}