common.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00017 * $Revision: 11192 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Set { namespace Sequence { 00045 00046 inline ExecStatus 00047 propagateSeq(Space& home, bool& modified, bool& assigned, 00048 ViewArray<SetView>& x) { 00049 int lastElem = x.size()-1; 00050 int cur_max = BndSet::MAX_OF_EMPTY; 00051 int cur_min = BndSet::MIN_OF_EMPTY; 00052 00053 Region r(home); 00054 Support::DynamicArray<int,Region> ub(r); 00055 00056 for (int i=0; i<lastElem; i++) { 00057 if (x[i].glbSize() > 0) 00058 cur_max = std::max(cur_max, x[i].glbMax()); 00059 if (x[i].cardMin() > 0) 00060 cur_max = std::max(cur_max, x[i].lubMinN(x[i].cardMin()-1)); 00061 if (cur_max >= Limits::min) 00062 GECODE_SET_ME_CHECK_VAL_B(modified, 00063 x[i+1].exclude(home, Limits::min, 00064 cur_max), 00065 assigned); 00066 00067 if (x[lastElem-i].lubSize() > 0) { 00068 cur_min = std::min(cur_min, x[lastElem-i].glbMin()); 00069 if (x[lastElem-i].cardMin() > 0) { 00070 // Compute n-th largest element in x[lastElem-i].lub 00071 // for n = x[lastElem-i].cardMin()-1 00072 int maxN = BndSet::MAX_OF_EMPTY; 00073 int j=0; 00074 for (LubRanges<SetView> ubr(x[lastElem-i]); ubr(); ++ubr, ++j) { 00075 ub[2*j]=ubr.min(); ub[2*j+1]=ubr.max(); 00076 } 00077 unsigned int xcm = x[lastElem-i].cardMin()-1; 00078 while (j--) { 00079 unsigned int width = static_cast<unsigned int>(ub[2*j+1]-ub[2*j]+1); 00080 if (width > xcm) { 00081 maxN = static_cast<int>(ub[2*j+1]-xcm); 00082 break; 00083 } 00084 xcm -= width; 00085 } 00086 cur_min = std::min(cur_min, maxN); 00087 } 00088 } 00089 if (Limits::max>=cur_min) 00090 GECODE_SET_ME_CHECK_VAL_B(modified, 00091 x[lastElem-i-1].exclude(home, cur_min, 00092 Limits::max), 00093 assigned); 00094 } 00095 return ES_NOFIX; 00096 } 00097 00098 }}} 00099 00100 // STATISTICS: set-prop