Generated on Mon May 5 05:53:58 2008 for Gecode by doxygen 1.5.5

order.icc

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: 2007-11-08 15:53:26 +0100 (Thu, 08 Nov 2007) $ by $Author: tack $
00011  *     $Revision: 5219 $
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, class Tuple, bool Perm>
00048   inline void
00049   sort_sigma(ViewArray<Tuple>& xz, bool) {
00050     int xs = xz.size();
00051 
00052     // test for equal bounds
00053     if (Perm) {
00054       TupleMinIncExt<Tuple> min_inc;
00055       Support::quicksort<Tuple, TupleMinIncExt<Tuple> >(&xz[0], xs, min_inc);
00056     } else {
00057       TupleMinInc<Tuple> min_inc;
00058       Support::quicksort<Tuple, TupleMinInc<Tuple> >(&xz[0], xs, min_inc);
00059     }
00060   }
00061 
00070   template <class View, class Tuple, bool Perm>
00071   inline void
00072   sort_tau(ViewArray<Tuple>& xz, int tau[]) {
00073     int xs = xz.size();
00074 
00075     if (Perm) {
00076       TupleMaxIncExt<Tuple> ltmax(xz);
00077       Support::quicksort(&(*tau), xs, ltmax);
00078     } else {
00079       TupleMaxInc<Tuple> ltmax(xz);
00080       Support::quicksort(&(*tau), xs, ltmax);
00081     }
00082   }
00083 
00091   template <class View, class Tuple>
00092   inline bool
00093   normalize(Space* home,
00094             ViewArray<View>& y,
00095             ViewArray<Tuple>& xz,
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 = xz.size();
00114     for (int i = xs; i--; ) {
00115       ModEvent me = xz[i][0].gq(home, y[0].min());
00116       if (me_failed(me))
00117         return false;
00118       nofix |= (me_modified(me) && xz[i][0].min() != y[0].min());
00119 
00120       me = xz[i][0].lq(home, y[xs - 1].max());
00121       if (me_failed(me))
00122         return false;
00123       nofix |= (me_modified(me) && xz[i][0].max() != y[xs - 1].max());
00124     }
00125     return true;
00126   }
00127 
00138   template<class View, class Tuple, bool Perm>
00139   inline bool
00140   perm_bc(Space* home, int tau[],
00141           SccComponent sinfo[],        
00142           int scclist[],
00143           ViewArray<Tuple>& xz,
00144           bool& crossingedge,
00145           bool& nofix) {
00146 
00147     int ps = xz.size();
00148 
00149     for (int i = 1; i < ps; i++) {
00150       // if there are "crossed edges"
00151       if (xz[i - 1][0].min() < xz[i][0].min()) {
00152         if (xz[i - 1][1].min() > xz[i][1].min()) {
00153           if (xz[i][1].min() != sinfo[scclist[i]].leftmost) {
00154             // edge does not take part in solution
00155             if (xz[i][1].assigned()) { // vital edge do not remove it
00156               if (xz[i - 1][0].max() < xz[i][0].min()) {
00157                 // invalid permutation
00158                 // the upper bound sorting cannot fix this
00159                 return false;
00160               }
00161             } else {
00162               crossingedge = true;
00163               // and the permutation can still be changed
00164               // fix the permutation, i.e. modify z
00165               ModEvent me_z = xz[i][1].gq(home, xz[i - 1][1].min());
00166               if (me_failed(me_z)) {
00167                 return false;
00168               }
00169               nofix |= ( me_modified(me_z) &&
00170                          xz[i - 1][1].min() != xz[i][1].min());
00171             }
00172           }
00173         }
00174       }
00175     }
00176 
00177     // the same check as above for the upper bounds
00178     for (int i = ps - 1; i--; ) {
00179       if (xz[tau[i]][0].max() < xz[tau[i + 1]][0].max()) {
00180         if (xz[tau[i]][1].max() > xz[tau[i + 1]][1].max()) {
00181           if (xz[tau[i]][1].max() != sinfo[scclist[tau[i]]].rightmost) {
00182             // edge does not take part in solution
00183             if (xz[tau[i]][1].assigned()) {
00184               if (xz[tau[i + 1]][0].min() > xz[tau[i]][0].max()) {
00185                 // invalid permutation
00186                 return false;
00187               }
00188             } else {
00189               crossingedge = true;
00190               ModEvent me_z = xz[tau[i]][1].lq(home, xz[tau[i + 1]][1].max());
00191               if (me_failed(me_z)) {
00192                 return false;
00193               }
00194               nofix |= (me_modified(me_z) &&
00195                         xz[tau[i + 1]][1].max() != xz[tau[i]][1].max());
00196             }
00197           }
00198         }
00199       }
00200     }
00201 
00202     return true;
00203   }
00204 
00205 }}}
00206 
00207 // STATISTICS: int-prop
00208