Generated on Fri Oct 19 11:25:09 2018 for Gecode by doxygen 1.6.3

order.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Copyright:
00007  *     Patrick Pekczynski, 2004
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Int { namespace Sorted {
00035 
00043   template<class View, bool Perm>
00044   inline void
00045   sort_sigma(ViewArray<View>& x, ViewArray<View>& z) {
00046     if (Perm) {
00047       Region r;
00048       ViewPair<View>* xz = r.alloc<ViewPair<View> >(x.size());
00049       for (int i=x.size(); i--; ) {
00050         xz[i].x=x[i]; xz[i].z=z[i];
00051       }
00052       TupleMinIncExt<View> min_inc;
00053       Support::quicksort<ViewPair<View>,TupleMinIncExt<View> >
00054         (&xz[0], x.size(), min_inc);
00055       for (int i=x.size(); i--; ) {
00056         x[i]=xz[i].x; z[i]=xz[i].z;
00057       }
00058     } else {
00059       TupleMinInc<View> min_inc;
00060       Support::quicksort<View,TupleMinInc<View> >(&x[0], x.size(), min_inc);
00061     }
00062   }
00063 
00072   template<class View, bool Perm>
00073   inline void
00074   sort_tau(ViewArray<View>& x, ViewArray<View>& z, int tau[]) {
00075     if (Perm) {
00076       TupleMaxIncExt<View> ltmax(x,z);
00077       Support::quicksort(&(*tau), x.size(), ltmax);
00078     } else {
00079       TupleMaxInc<View> ltmax(x);
00080       Support::quicksort(&(*tau), x.size(), ltmax);
00081     }
00082   }
00083 
00091   template<class View>
00092   inline bool
00093   normalize(Space& home,
00094             ViewArray<View>& y,
00095             ViewArray<View>& x,
00096             bool& nofix) {
00097 
00098     int ys = y.size();
00099     for (int i = 1; i < ys; i++) {
00100       ModEvent me_lb = y[i].gq(home, y[i - 1].min());
00101       if (me_failed(me_lb))
00102         return false;
00103       nofix |= (me_modified(me_lb) && y[i - 1].min() != y[i].min());
00104     }
00105 
00106     for (int i = ys - 1; i--; ) {
00107       ModEvent me_ub = y[i].lq(home, y[i + 1].max());
00108       if (me_failed(me_ub))
00109         return false;
00110       nofix |= (me_modified(me_ub) && y[i + 1].max() != y[i].max());
00111     }
00112 
00113     int xs = x.size();
00114     for (int i = xs; i--; ) {
00115       ModEvent me = x[i].gq(home, y[0].min());
00116       if (me_failed(me))
00117         return false;
00118       nofix |= (me_modified(me) && x[i].min() != y[0].min());
00119 
00120       me = x[i].lq(home, y[xs - 1].max());
00121       if (me_failed(me))
00122         return false;
00123       nofix |= (me_modified(me) && x[i].max() != y[xs - 1].max());
00124     }
00125     return true;
00126   }
00127 
00138   template<class View>
00139   inline bool
00140   perm_bc(Space& home, int tau[],
00141           SccComponent sinfo[],
00142           int scclist[],
00143           ViewArray<View>& x,
00144           ViewArray<View>& z,
00145           bool& crossingedge,
00146           bool& nofix) {
00147 
00148     int ps = x.size();
00149 
00150     for (int i = 1; i < ps; i++) {
00151       // if there are "crossed edges"
00152       if (x[i - 1].min() < x[i].min()) {
00153         if (z[i - 1].min() > z[i].min()) {
00154           if (z[i].min() != sinfo[scclist[i]].leftmost) {
00155             // edge does not take part in solution
00156             if (z[i].assigned()) { // vital edge do not remove it
00157               if (x[i - 1].max() < x[i].min()) {
00158                 // invalid permutation
00159                 // the upper bound sorting cannot fix this
00160                 return false;
00161               }
00162             } else {
00163               crossingedge = true;
00164               // and the permutation can still be changed
00165               // fix the permutation, i.e. modify z
00166               ModEvent me_z = z[i].gq(home, z[i - 1].min());
00167               if (me_failed(me_z)) {
00168                 return false;
00169               }
00170               nofix |= ( me_modified(me_z) &&
00171                          z[i - 1].min() != z[i].min());
00172             }
00173           }
00174         }
00175       }
00176     }
00177 
00178     // the same check as above for the upper bounds
00179     for (int i = ps - 1; i--; ) {
00180       if (x[tau[i]].max() < x[tau[i + 1]].max()) {
00181         if (z[tau[i]].max() > z[tau[i + 1]].max()) {
00182           if (z[tau[i]].max() != sinfo[scclist[tau[i]]].rightmost) {
00183             // edge does not take part in solution
00184             if (z[tau[i]].assigned()) {
00185               if (x[tau[i + 1]].min() > x[tau[i]].max()) {
00186                 // invalid permutation
00187                 return false;
00188               }
00189             } else {
00190               crossingedge = true;
00191               ModEvent me_z = z[tau[i]].lq(home, z[tau[i + 1]].max());
00192               if (me_failed(me_z)) {
00193                 return false;
00194               }
00195               nofix |= (me_modified(me_z) &&
00196                         z[tau[i + 1]].max() != z[tau[i]].max());
00197             }
00198           }
00199         }
00200       }
00201     }
00202 
00203     return true;
00204   }
00205 
00206 }}}
00207 
00208 // STATISTICS: int-prop
00209