00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace Sorted {
00039
00057 template <class View, class Tuple, bool Perm>
00058 inline bool
00059 glover(Space*,
00060 ViewArray<Tuple>& xz,
00061 ViewArray<View>& y,
00062 int tau[],
00063 int phi[],
00064 OfflineMinItem sequence[],
00065 int vertices[]) {
00066
00067 int xs = xz.size();
00068 OfflineMin seq(sequence, vertices, xs);
00069 int s = 0;
00070 seq.makeset();
00071
00072 for (int z = 0; z < xs; z++) {
00073 int maxy = y[z].max();
00074
00075 for( ; s <xs && xz[s][0].min() <= maxy; s++) {
00076 seq[s].iset = z;
00077 seq[z].rank++;
00078 }
00079 }
00080
00081
00082 for (int i = 0; i < xs; i++) {
00083
00084 int perm = tau[i];
00085
00086 int iter = seq[perm].iset;
00087 if (iter<0)
00088 return false;
00089 int j = 0;
00090 j = seq.find_pc(iter);
00091
00092 if (j >= xs)
00093 return false;
00094
00095
00096 if (xz[perm][0].max() < y[j].min())
00097 return false;
00098 phi[j] = perm;
00099 seq[perm].iset = -5;
00100 int sqjsucc = seq[j].succ;
00101 if (sqjsucc < xs) {
00102 seq.unite(j,sqjsucc,sqjsucc);
00103 } else {
00104 seq[seq[j].root].name = sqjsucc;
00105 }
00106
00107
00108 int pr = seq[j].pred;
00109 if (pr != -1)
00110 seq[pr].succ = sqjsucc;
00111 if (sqjsucc != xs)
00112 seq[sqjsucc].pred = pr;
00113 }
00114 return true;
00115 }
00116
00121 template <class View, class Tuple, bool Perm>
00122 inline bool
00123 revglover(Space*,
00124 ViewArray<Tuple>& xz,
00125 ViewArray<View>& y,
00126 int tau[],
00127 int phiprime[],
00128 OfflineMinItem sequence[],
00129 int vertices[]) {
00130
00131 int xs = xz.size();
00132 OfflineMin seq(sequence, vertices, xs);
00133 int s = xs - 1;
00134 seq.makeset();
00135
00136 int miny = 0;
00137 for (int z = xs; z--; ) {
00138 miny = y[z].min();
00139
00140 for ( ; s > -1 && xz[tau[s]][0].max() >= miny; s--) {
00141 seq[tau[s]].iset = z;
00142 seq[z].rank++;
00143 }
00144 }
00145
00146
00147 for (int i = xs; i--; ) {
00148 int perm = i;
00149 int iter = seq[perm].iset;
00150 if (iter < 0)
00151 return false;
00152 int j = 0;
00153 j = seq.find_pc(iter);
00154 if (j <= -1)
00155 return false;
00156
00157
00158 if (xz[perm][0].min() > y[j].max())
00159 return false;
00160 phiprime[j] = perm;
00161 seq[perm].iset = -5;
00162 int sqjsucc = seq[j].pred;
00163 if (sqjsucc >= 0) {
00164 seq.unite(j, sqjsucc, sqjsucc);
00165 } else {
00166 seq[seq[j].root].name = sqjsucc;
00167 }
00168
00169
00170 int pr = seq[j].succ;
00171 if (pr != xs)
00172 seq[pr].pred = sqjsucc;
00173 if (sqjsucc != -1)
00174 seq[sqjsucc].succ = pr;
00175 }
00176 return true;
00177 }
00178
00179 }}}
00180
00181
00182