1 //
2 // Code for expanding the assignments in a level.
3 //
4
5 bool
fullyExpandAssignments()6 WordLevel::fullyExpandAssignments()
7 {
8 //
9 // Expand assignments to fixed-point.
10 //
11 for (;;)
12 {
13 Result result = expandAssignments();
14 if (result == FAIL)
15 return false;
16 if (result == DONE)
17 break;
18 }
19 return true;
20 }
21
22 WordLevel::Result
expandAssignments()23 WordLevel::expandAssignments()
24 {
25 //
26 // Expand each assignment.
27 //
28 bool changed = false;
29 int nrAssignments = partialSolution.size();
30 for (int i = 0; i < nrAssignments; ++i)
31 {
32 Result result = expandAssignment(i, partialSolution[i]);
33 if (result == FAIL)
34 return FAIL;
35 if (result == CHANGED)
36 changed = true;
37 }
38 return changed ? CHANGED : DONE;
39 }
40
41 WordLevel::Result
expandAssignment(int var,Word & word)42 WordLevel::expandAssignment(int var, Word& word)
43 {
44 //
45 // Check if assignment needs expansion, i.e. that a variable in
46 // range has an assignment different from itself.
47 //
48 FOR_EACH_CONST(i, Word, word)
49 {
50 int var2 = *i;
51 if (var2 == var)
52 return word.size() == 1 ? DONE : FAIL; // either identity mapping or occur-check failure
53
54 Word& assigned = partialSolution[var2];
55 if (!(assigned.size() == 1 && assigned[0] == var2))
56 return reallyExpandAssignment(var, word, i, assigned) ? CHANGED : FAIL;
57 }
58 return DONE;
59 }
60
61 bool
reallyExpandAssignment(int var,Word & word,Word::const_iterator firstToExpand,const Word & expansion)62 WordLevel::reallyExpandAssignment(int var,
63 Word& word,
64 Word::const_iterator firstToExpand,
65 const Word& expansion)
66 {
67 //
68 // Do the actual expansion; return false if there was an occur-check failure.
69 //
70 Word newWord;
71 //
72 // Copy in any variables that didn't need expansion.
73 //
74 for (Word::const_iterator i = word.begin(); i != firstToExpand; ++i)
75 newWord.append(*i);
76 //
77 // Copy in the assignment of the first variable that needed expansion.
78 //
79 if (!append(newWord, expansion, var))
80 return false;
81 //
82 // Got through remaining variables, expanding those that are assigned non-identity values.
83 //
84 const Word::const_iterator e = word.end();
85 for (++firstToExpand; firstToExpand != e; ++firstToExpand)
86 {
87 int var2 = *firstToExpand;
88 if (var2 == var)
89 return false; // occur-check failure
90
91 Word& assigned = partialSolution[var2];
92 if (assigned.size() == 1 && assigned[0] == var2)
93 newWord.append(var2);
94 else
95 {
96 if (!(append(newWord, assigned, var)))
97 return false;
98 }
99 }
100 //
101 // Replace the range with its expansion.
102 //
103 word.swap(newWord);
104 return true;
105 }
106
107 bool
append(Word & newWord,const Word & word,int var)108 WordLevel::append(Word& newWord, const Word& word, int var)
109 {
110 FOR_EACH_CONST(i, Word, word)
111 {
112 int var2 = *i;
113 if (var2 == var)
114 return false; // occur-check failure
115 newWord.append(var2);
116 }
117 return true;
118 }
119