matching.hpp
Go to the documentation of this file.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 namespace Gecode { namespace Int { namespace Sorted {
00035
00053 template<class View>
00054 inline bool
00055 glover(ViewArray<View>& x, ViewArray<View>& y,
00056 int tau[], int phi[], OfflineMinItem sequence[], int vertices[]) {
00057
00058 int xs = x.size();
00059 OfflineMin seq(sequence, vertices, xs);
00060 int s = 0;
00061 seq.makeset();
00062
00063 for (int z = 0; z < xs; z++) {
00064 int maxy = y[z].max();
00065
00066 for( ; s <xs && x[s].min() <= maxy; s++) {
00067 seq[s].iset = z;
00068 seq[z].rank++;
00069 }
00070 }
00071
00072
00073 for (int i = 0; i < xs; i++) {
00074
00075 int perm = tau[i];
00076
00077 int iter = seq[perm].iset;
00078 if (iter<0)
00079 return false;
00080 int j = 0;
00081 j = seq.find_pc(iter);
00082
00083 if (j >= xs)
00084 return false;
00085
00086
00087 if (x[perm].max() < y[j].min())
00088 return false;
00089 phi[j] = perm;
00090 seq[perm].iset = -5;
00091 int sqjsucc = seq[j].succ;
00092 if (sqjsucc < xs) {
00093 seq.unite(j,sqjsucc,sqjsucc);
00094 } else {
00095 seq[seq[j].root].name = sqjsucc;
00096 }
00097
00098
00099 int pr = seq[j].pred;
00100 if (pr != -1)
00101 seq[pr].succ = sqjsucc;
00102 if (sqjsucc != xs)
00103 seq[sqjsucc].pred = pr;
00104 }
00105 return true;
00106 }
00107
00112 template<class View>
00113 inline bool
00114 revglover(ViewArray<View>& x, ViewArray<View>& y,
00115 int tau[], int phiprime[], OfflineMinItem sequence[],
00116 int vertices[]) {
00117
00118 int xs = x.size();
00119 OfflineMin seq(sequence, vertices, xs);
00120 int s = xs - 1;
00121 seq.makeset();
00122
00123 int miny = 0;
00124 for (int z = xs; z--; ) {
00125 miny = y[z].min();
00126
00127 for ( ; s > -1 && x[tau[s]].max() >= miny; s--) {
00128 seq[tau[s]].iset = z;
00129 seq[z].rank++;
00130 }
00131 }
00132
00133
00134 for (int i = xs; i--; ) {
00135 int perm = i;
00136 int iter = seq[perm].iset;
00137 if (iter < 0)
00138 return false;
00139 int j = 0;
00140 j = seq.find_pc(iter);
00141 if (j <= -1)
00142 return false;
00143
00144
00145 if (x[perm].min() > y[j].max())
00146 return false;
00147 phiprime[j] = perm;
00148 seq[perm].iset = -5;
00149 int sqjsucc = seq[j].pred;
00150 if (sqjsucc >= 0) {
00151 seq.unite(j, sqjsucc, sqjsucc);
00152 } else {
00153 seq[seq[j].root].name = sqjsucc;
00154 }
00155
00156
00157 int pr = seq[j].succ;
00158 if (pr != xs)
00159 seq[pr].pred = sqjsucc;
00160 if (sqjsucc != -1)
00161 seq[sqjsucc].succ = pr;
00162 }
00163 return true;
00164 }
00165
00166 }}}
00167
00168
00169