sortsup.icc
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 namespace Gecode { namespace Int { namespace Sortedness {
00023
00037 template<class View, class Tuple, bool Perm>
00038 forceinline bool
00039 check_subsumption(Space* home,
00040 ViewArray<Tuple>& xz,
00041 ViewArray<View>& y,
00042 bool& subsumed,
00043 int& dropfst) {
00044
00045 dropfst = 0;
00046 subsumed = true;
00047 int xs = xz.size();
00048 for (int i = 0; i < xs ; i++) {
00049 if (Perm) {
00050 subsumed &= (xz[i][0].assigned() &&
00051 xz[i][1].assigned() &&
00052 y[xz[i][1].val()].assigned());
00053 if (subsumed) {
00054 if (xz[i][0].val() != y[xz[i][1].val()].val()) {
00055 return false;
00056 } else {
00057 if (xz[i][1].val() == i) {
00058 dropfst++;
00059 }
00060 }
00061 }
00062 } else {
00063 subsumed &= (xz[i][0].assigned() && y[i].assigned());
00064 if (subsumed) {
00065 if (xz[i][0].val() != y[i].val()) {
00066 return false;
00067 } else {
00068 dropfst++;
00069 }
00070 }
00071 }
00072 }
00073 return true;
00074 }
00075
00081 class OfflineMinItem{
00082 public:
00084 int root;
00086 int parent;
00088 int rank;
00090 int name;
00098 int iset;
00100 int succ;
00102 int pred;
00103 };
00104
00110 class OfflineMin{
00111 private:
00112 OfflineMinItem* sequence;
00113 int* vertices;
00114 int n;
00115 public:
00116 OfflineMin(void);
00117 ~OfflineMin(void);
00118 OfflineMin(OfflineMinItem[], int[], int);
00123 int find(int x);
00128 int find_pc(int x);
00130 void unite(int a, int b, int c);
00132 void makeset(void);
00134 int size(void);
00135 OfflineMinItem& operator[](int);
00136 };
00137
00138 OfflineMin::OfflineMin(void){
00139 n = 0;
00140 sequence = NULL;
00141 vertices = NULL;
00142 }
00143
00144 OfflineMin::OfflineMin(OfflineMinItem s[], int v[], int size){
00145 n = size;
00146 sequence = &s[0];
00147 vertices = &v[0];
00148 }
00149
00150 OfflineMin::~OfflineMin(void){
00151 sequence = NULL;
00152 vertices = NULL;
00153 }
00154
00155 forceinline int
00156 OfflineMin::find(int x) {
00157 while (sequence[x].parent != x) {
00158 x = sequence[x].parent;
00159 }
00160
00161
00162 return sequence[x].name;
00163 }
00164
00165 forceinline int
00166 OfflineMin::find_pc(int x){
00167 int vsize = 0;
00168 while (sequence[x].parent != x) {
00169 vertices[x] = x;
00170 x = sequence[x].parent;
00171 }
00172
00173 for (int i = vsize; i--; ) {
00174 sequence[vertices[i]].parent = x;
00175 }
00176
00177 return sequence[x].name;
00178 }
00179
00180 forceinline void
00181 OfflineMin::unite(int a, int b, int c){
00182
00183 int ra = sequence[a].root;
00184 int rb = sequence[b].root;
00185 int large = rb;
00186 int small = ra;
00187 if (sequence[ra].rank > sequence[rb].rank) {
00188 large = ra;
00189 small = rb;
00190 }
00191 sequence[small].parent = large;
00192 sequence[large].rank += sequence[small].rank;
00193 sequence[large].name = c;
00194 sequence[c].root = large;
00195 }
00196
00197 forceinline void
00198 OfflineMin::makeset(void){
00199 for(int i = n; i--; ){
00200 OfflineMinItem& cur = sequence[i];
00201 cur.rank = 0;
00202 cur.name = i;
00203 cur.root = i;
00204 cur.parent = i;
00205 cur.pred = i - 1;
00206 cur.succ = i + 1;
00207 cur.iset = -5;
00208 }
00209 }
00210
00211 forceinline int
00212 OfflineMin::size(void){
00213 return n;
00214 }
00215
00216 forceinline OfflineMinItem&
00217 OfflineMin::operator [](int i){
00218 return sequence[i];
00219 }
00220
00222 forceinline std::ostream&
00223 operator<<(std::ostream& os, OfflineMin seq){
00224 for (int i = 0; i < seq.size();i++) {
00225 os << "Succ(" <<seq[i].succ << ") "
00226 << "Pred(" <<seq[i].pred << ") "
00227 << "Root(" <<seq[i].root << ") "
00228 << "Par (" <<seq[i].parent << ") "
00229 << "Rank(" <<seq[i].rank << ") "
00230 << "Name(" <<seq[i].name << ") "
00231 << "Set (" <<seq[i].iset << ") \n";
00232 }
00233 return os;
00234 }
00235
00245 template <class Tuple>
00246 class TupleMaxInc {
00247 protected:
00248 ViewArray<Tuple> x;
00249 public:
00250 TupleMaxInc(const ViewArray<Tuple>& x0) : x(x0) {}
00251 bool operator()(const int i, const int j) {
00252 return x[i][0].max() < x[j][0].max();
00253 }
00254 };
00255
00265 template <class View>
00266 class TupleMinInc {
00267 public:
00268 bool operator()(const View& x, const View& y) {
00269 return x[0].min() < y[0].min();
00270 }
00271 };
00272
00281 template <class View>
00282 class TupleMinIncPerm {
00283 public:
00284 bool operator()(const View& x, const View& y) {
00285 return x[1].min() < y[1].min();
00286 }
00287 };
00288
00296 template<class View, class Tuple, bool Perm, bool shared>
00297 forceinline bool
00298 array_assigned(Space* home,
00299 ViewArray<Tuple>& xz,
00300 ViewArray<View>& y,
00301 bool& subsumed,
00302 bool& match_fixed,
00303 bool& nofix) {
00304
00305 bool x_complete = true;
00306 bool y_complete = true;
00307 bool z_complete = true;
00308
00309 for (int i = y.size(); i--; ) {
00310 x_complete &= xz[i][0].assigned();
00311 y_complete &= y[i].assigned();
00312 if (Perm) {
00313 z_complete &= xz[i][1].assigned();
00314 }
00315 }
00316
00317 if (x_complete) {
00318 for (int i = xz.size(); i--; ) {
00319 if (shared && y[i].modified()) {
00320 nofix = true;
00321 return true;
00322 }
00323 ModEvent me = y[i].eq(home, xz[i][0].val());
00324 if (me_failed(me)) {
00325 return false;
00326 }
00327 }
00328 if (Perm) {
00329 subsumed = false;
00330 } else {
00331 subsumed = true;
00332 }
00333 }
00334
00335 if (y_complete) {
00336 bool y_equality = true;
00337 for (int i = y.size() - 1; i--; ) {
00338 y_equality &= (y[i].val() == y[i + 1].val());
00339 }
00340 if (y_equality) {
00341 for (int i = xz.size(); i--; ) {
00342 if (shared && xz[i][0].modified()) {
00343 nofix = true;
00344 return true;
00345 }
00346 ModEvent me = xz[i][0].eq(home, y[i].val());
00347 if (me_failed(me)) {
00348 return false;
00349 }
00350 }
00351 if (Perm) {
00352 subsumed = false;
00353 } else {
00354 subsumed = true;
00355 }
00356 }
00357 }
00358
00359 if (Perm) {
00360 if (z_complete) {
00361 if (x_complete) {
00362 for (int i = xz.size(); i--; ) {
00363 ModEvent me = y[xz[i][1].val()].eq(home, xz[i][0].val());
00364 if (me_failed(me)) {
00365 return false;
00366 }
00367 }
00368 subsumed = true;
00369 return subsumed;
00370 }
00371 if (y_complete) {
00372 for (int i = xz.size(); i--; ) {
00373 if (shared && xz[i][0].modified()) {
00374 nofix = true;
00375 return true;
00376 }
00377
00378 ModEvent me = xz[i][0].eq(home, y[xz[i][1].val()].val());
00379 if (me_failed(me)) {
00380 return false;
00381 }
00382 }
00383 subsumed = true;
00384 return subsumed;
00385 }
00386
00387
00388 int sum = 0;
00389 for (int i = xz.size(); i--; ) {
00390 int pi = xz[i][1].val();
00391 if (xz[i][0].max() < y[pi].min() ||
00392 xz[i][0].min() > y[pi].max()) {
00393 return false;
00394 }
00395 sum += pi;
00396 }
00397 int n = xz.size();
00398 int gauss = ( (n * (n + 1)) / 2);
00399
00400
00401 if (sum != gauss - n) {
00402 return false;
00403 }
00404 match_fixed = true;
00405 }
00406 }
00407 return true;
00408 }
00409
00410 }}}
00411
00412
00413