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