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