Generated on Sat Feb 12 2011 17:40:59 for Gecode by doxygen 1.7.3

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: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $
00011  *     $Revision: 11390 $
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 #include <algorithm>
00039 
00040 namespace Gecode { namespace Iter { namespace Ranges {
00041 
00047   template<class I, class J>
00048   class Union : public MinMax {
00049   protected:
00051     I i;
00053     J j;
00054   public:
00056 
00057 
00058     Union(void);
00060     Union(I& i, J& j);
00062     void init(I& i, J& j);
00064 
00066 
00067 
00068     void operator ++(void);
00070   };
00071 
00072 
00078   template<class I>
00079   class NaryUnion : public RangeListIter {
00080   protected:
00082     RangeList* range(RangeList*& f, int min, int max);
00084     RangeList* range(RangeList*& f, I& i);
00085   public:
00087 
00088 
00089     NaryUnion(void);
00091     NaryUnion(Region& r, I* i, int n);
00093     void init(Region& r, I* i, int n);
00095     NaryUnion& operator =(const NaryUnion& m);
00097   };
00098 
00099 
00100 
00101 
00102   /*
00103    * Binary union
00104    *
00105    */
00106 
00107   template<class I, class J>
00108   inline void
00109   Union<I,J>::operator ++(void) {
00110     if (!i() && !j()) {
00111       finish(); return;
00112     }
00113 
00114     if (!i() || (j() && (j.max()+1 < i.min()))) {
00115       mi = j.min(); ma = j.max(); ++j; return;
00116     }
00117     if (!j() || (i() && (i.max()+1 < j.min()))) {
00118       mi = i.min(); ma = i.max(); ++i; return;
00119     }
00120 
00121     mi = std::min(i.min(),j.min());
00122     ma = std::max(i.max(),j.max());
00123 
00124     ++i; ++j;
00125 
00126   next:
00127     if (i() && (i.min() <= ma+1)) {
00128       ma = std::max(ma,i.max()); ++i;
00129       goto next;
00130     }
00131     if (j() && (j.min() <= ma+1)) {
00132       ma = std::max(ma,j.max()); ++j;
00133       goto next;
00134     }
00135   }
00136 
00137 
00138   template<class I, class J>
00139   forceinline
00140   Union<I,J>::Union(void) {}
00141 
00142   template<class I, class J>
00143   forceinline
00144   Union<I,J>::Union(I& i0, J& j0)
00145     : i(i0), j(j0) {
00146     operator ++();
00147   }
00148 
00149   template<class I, class J>
00150   forceinline void
00151   Union<I,J>::init(I& i0, J& j0) {
00152     i = i0; j = j0;
00153     operator ++();
00154   }
00155 
00156 
00157 
00158   /*
00159    * Nary Union
00160    *
00161    */
00162 
00163   template<class I>
00164   forceinline
00165   NaryUnion<I>::NaryUnion(void) {}
00166 
00167   template<class I>
00168   forceinline RangeListIter::RangeList*
00169   NaryUnion<I>::range(RangeList*& f, int min, int max) {
00170     RangeList* t;
00171     // Take element from freelist if possible
00172     if (f != NULL) {
00173       t = f; f = f->next;
00174     } else {
00175       t = new (*rlio) RangeList;
00176     }
00177     t->min = min; t->max = max;
00178     return t;
00179   }
00180 
00181   template<class I>
00182   forceinline RangeListIter::RangeList*
00183   NaryUnion<I>::range(RangeList*& f, I& i) {
00184     return range(f,i.min(),i.max());
00185   }
00186 
00187   template<class I>
00188   void
00189   NaryUnion<I>::init(Region& r, I* i, int n) {
00190     RangeListIter::init(r);
00191 
00192     // Freelist for allocation
00193     RangeList* f = NULL;
00194 
00195     // Rangelist for union
00196     RangeList* u = NULL;
00197 
00198     int m = 0;
00199     while ((m < n) && !i[m]())
00200       m++;
00201 
00202     // Union is empty
00203     if (m >= n)
00204       return;
00205 
00206     n--;
00207     while (!i[n]())
00208       n--;
00209 
00210     if (m == n) {
00211       // Union is just a single iterator
00212       RangeList** c = &u;
00213       
00214       for ( ; i[m](); ++i[m]) {
00215         RangeList* t = range(f,i[m]);
00216         *c = t; c = &t->next;
00217       }
00218       *c = NULL;
00219     } else {
00220       // At least two iterators
00221 
00222       // Compute the union for just two iterators
00223       {
00224         // The current rangelist
00225         RangeList** c = &u;
00226         
00227         while (i[m]() && i[n]())
00228           if (i[m].max()+1 < i[n].min()) {
00229             RangeList* t = range(f,i[m]); ++i[m];
00230             *c = t; c = &t->next;
00231           } else if (i[n].max()+1 < i[m].min()) {
00232             RangeList* t = range(f,i[n]); ++i[n];
00233             *c = t; c = &t->next;
00234           } else {
00235             int min = std::min(i[m].min(),i[n].min());
00236             int max = std::max(i[m].max(),i[n].max());
00237             ++i[m]; ++i[n];
00238 
00239           nexta:
00240             if (i[m]() && (i[m].min() <= max+1)) {
00241               max = std::max(max,i[m].max()); ++i[m];
00242               goto nexta;
00243             }
00244             if (i[n]() && (i[n].min() <= max+1)) {
00245               max = std::max(max,i[n].max()); ++i[n];
00246               goto nexta;
00247             }
00248  
00249             RangeList* t = range(f,min,max);
00250             *c = t; c = &t->next;
00251           }
00252         for ( ; i[m](); ++i[m]) {
00253           RangeList* t = range(f,i[m]);
00254           *c = t; c = &t->next;
00255         }
00256         for ( ; i[n](); ++i[n]) {
00257           RangeList* t = range(f,i[n]);
00258           *c = t; c = &t->next;
00259         }
00260         *c = NULL;
00261         m++; n--;
00262       }
00263 
00264       // Insert the remaining iterators
00265       for ( ; m<=n; m++) {
00266         // The current rangelist
00267         RangeList** c = &u;
00268         
00269         while ((*c != NULL) && i[m]())
00270           if ((*c)->max+1 < i[m].min()) {
00271             // Keep range from union
00272             c = &(*c)->next;
00273           } else if (i[m].max()+1 < (*c)->min) {
00274             // Copy range from iterator
00275             RangeList* t = range(f,i[m]); ++i[m];
00276             // Insert
00277             t->next = *c; *c = t; c = &t->next;
00278           } else {
00279             // Ranges overlap
00280             // Compute new minimum
00281             (*c)->min = std::min((*c)->min,i[m].min());
00282             // Compute new maximum
00283             int max = std::max((*c)->max,i[m].max());
00284             
00285             // Scan from the next range in the union
00286             RangeList* s = (*c)->next; 
00287             ++i[m];
00288             
00289           nextb:
00290             if ((s != NULL) && (s->min <= max+1)) {
00291               max = std::max(max,s->max);
00292               RangeList* t = s;
00293               s = s->next;
00294               // Put deleted element into freelist
00295               t->next = f; f = t;
00296               goto nextb;
00297             }
00298             if (i[m]() && (i[m].min() <= max+1)) {
00299               max = std::max(max,i[m].max()); ++i[m];
00300               goto nextb;
00301             }
00302             // Store computed max and shunt skipped ranges from union
00303             (*c)->max = max; (*c)->next = s;
00304           }
00305         if (*c == NULL) {
00306           // Copy remaining ranges from iterator
00307           for ( ; i[m](); ++i[m]) {
00308             RangeList* t = range(f,i[m]);
00309             *c = t; c = &t->next;
00310           }
00311           *c = NULL;
00312         }
00313       }
00314     }
00315     set(u);
00316   }
00317 
00318   template<class I>
00319   forceinline
00320   NaryUnion<I>::NaryUnion(Region& r, I* i, int n) {
00321     init(r,i,n);
00322   }
00323 
00324   template<class I>
00325   forceinline NaryUnion<I>&
00326   NaryUnion<I>::operator =(const NaryUnion<I>& m) {
00327     return static_cast<NaryUnion&>(RangeListIter::operator =(m));
00328   }
00329 
00330 }}}
00331 
00332 // STATISTICS: iter-any
00333