ranges-union.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 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 Iter { namespace Ranges { 00039 00046 template<class I, class J> 00047 class Union : public MinMax { 00048 private: 00050 IsRangeIter<I> _checkI; 00052 IsRangeIter<J> _checkJ; 00053 private: 00055 I i; 00057 J j; 00058 public: 00060 00061 00062 Union(void); 00064 Union(I& i, J& j); 00066 void init(I& i, J& j); 00068 00070 00071 00072 void operator ++(void); 00074 }; 00075 00076 00082 template<class I> 00083 class NaryUnion : public MinMax { 00084 private: 00086 IsRangeIter<I> _checkI; 00087 protected: 00089 class RangeUnionOrder { 00090 public: 00091 bool operator ()(const I&, const I&) const; 00092 }; 00094 RangeUnionOrder order; 00096 PriorityQueue<I,RangeUnionOrder> r; 00097 public: 00099 00100 00101 NaryUnion(void); 00103 NaryUnion(I* i, int n); 00105 void init(I* i, int n); 00107 00109 00110 00111 void operator ++(void); 00113 }; 00114 00115 00116 00117 /* 00118 * Binary union 00119 * 00120 */ 00121 00122 template<class I, class J> 00123 inline void 00124 Union<I,J>::operator ++(void) { 00125 if (!i() && !j()) { 00126 finish(); return; 00127 } 00128 if (!i()) { 00129 mi = j.min(); ma = j.max(); ++j; return; 00130 } 00131 if (!j()) { 00132 mi = i.min(); ma = i.max(); ++i; return; 00133 } 00134 if (i.min() < j.min()) { 00135 mi = i.min(); ma = i.max(); ++i; 00136 } else { 00137 mi = j.min(); ma = j.max(); ++j; 00138 } 00139 bool goOn; 00140 do { 00141 goOn = false; 00142 if (i() && (i.min() <= ma+1)) { 00143 ma = std::max(ma,i.max()); ++i; goOn=true; 00144 } 00145 if (j() && (j.min() <= ma+1)) { 00146 ma = std::max(ma,j.max()); ++j; goOn=true; 00147 } 00148 } while (goOn); 00149 } 00150 00151 00152 template<class I, class J> 00153 forceinline 00154 Union<I,J>::Union(void) {} 00155 00156 template<class I, class J> 00157 forceinline 00158 Union<I,J>::Union(I& i0, J& j0) 00159 : i(i0), j(j0) { 00160 operator ++(); 00161 } 00162 00163 template<class I, class J> 00164 forceinline void 00165 Union<I,J>::init(I& i0, J& j0) { 00166 i = i0; j = j0; 00167 operator ++(); 00168 } 00169 00170 00171 00172 /* 00173 * Nary Union 00174 * 00175 */ 00176 00177 template<class I> 00178 forceinline bool 00179 NaryUnion<I>::RangeUnionOrder::operator ()(const I& a, const I& b) const { 00180 return a.min() > b.min(); 00181 } 00182 00183 template<class I> 00184 inline void 00185 NaryUnion<I>::operator ++(void) { 00186 if (r.empty()) { 00187 finish(); return; 00188 } 00189 mi = r.top().min(); 00190 ma = r.top().max(); 00191 do { 00192 if (ma < r.top().max()) 00193 ma = r.top().max(); 00194 ++(r.top()); 00195 if (!(r.top())()) { 00196 r.remove(); 00197 if (r.empty()) 00198 return; 00199 } else { 00200 r.fix(); 00201 } 00202 } while (ma+1 >= r.top().min()); 00203 } 00204 00205 00206 template<class I> 00207 forceinline 00208 NaryUnion<I>::NaryUnion(void) {} 00209 00210 template<class I> 00211 inline 00212 NaryUnion<I>::NaryUnion(I* r0, int n) 00213 : order(), r(n,order) { 00214 for (int i = n; i--; ) 00215 if (r0[i]()) 00216 r.insert(r0[i]); 00217 operator ++(); 00218 } 00219 00220 template<class I> 00221 inline void 00222 NaryUnion<I>::init(I* r0, int n) { 00223 r.init(n,order); 00224 for (int i = n; i--; ) 00225 if (r0[i]()) 00226 r.insert(r0[i]); 00227 operator ++(); 00228 } 00229 00230 }}} 00231 00232 // STATISTICS: iter-any 00233