Generated on Thu Apr 11 13:59:13 2019 for Gecode by doxygen 1.6.3

ranges-inter.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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <algorithm>
00035 
00036 namespace Gecode { namespace Iter { namespace Ranges {
00037 
00043   template<class I, class J>
00044   class Inter : public MinMax {
00045   protected:
00047     I i;
00049     J j;
00050   public:
00052 
00053 
00054     Inter(void);
00056     Inter(I& i, J& j);
00058     void init(I& i, J& j);
00060 
00062 
00063 
00064     void operator ++(void);
00066   };
00067 
00068 
00074   class NaryInter : public RangeListIter {
00075   protected:
00077     RangeList* f;
00078   public:
00080 
00081 
00082     NaryInter(void);
00084     template<class I>
00085     NaryInter(Region& r, I& i);
00087     template<class I, class J>
00088     NaryInter(Region& r, I& i, J& j);
00090     template<class I>
00091     NaryInter(Region& r, I* i, int n);
00093     template<class I>
00094     void init(Region& r, I& i);
00096     template<class I, class J>
00097     void init(Region& r, I& i, J& j);
00099     template<class I>
00100     void init(Region& r, I* i, int n);
00102     template<class I>
00103     void operator &=(I& i);
00105     NaryInter& operator =(const NaryInter& m);
00107   };
00108 
00109 
00110 
00111   /*
00112    * Binary intersection
00113    *
00114    */
00115 
00116   template<class I, class J>
00117   inline void
00118   Inter<I,J>::operator ++(void) {
00119     if (!i() || !j()) goto done;
00120     do {
00121       while (i() && (i.max() < j.min())) ++i;
00122       if (!i()) goto done;
00123       while (j() && (j.max() < i.min())) ++j;
00124       if (!j()) goto done;
00125     } while (i.max() < j.min());
00126     // Now the intervals overlap: consume the smaller interval
00127     ma = std::min(i.max(),j.max());
00128     mi = std::max(i.min(),j.min());
00129     if (i.max() < j.max()) ++i; else ++j;
00130     return;
00131   done:
00132     finish();
00133   }
00134 
00135   template<class I, class J>
00136   forceinline
00137   Inter<I,J>::Inter(void) {}
00138 
00139   template<class I, class J>
00140   forceinline
00141   Inter<I,J>::Inter(I& i0, J& j0)
00142     : i(i0), j(j0) {
00143     operator ++();
00144   }
00145 
00146   template<class I, class J>
00147   forceinline void
00148   Inter<I,J>::init(I& i0, J& j0) {
00149     i = i0; j = j0;
00150     operator ++();
00151   }
00152 
00153 
00154   /*
00155    * Nary intersection
00156    *
00157    */
00158 
00159   forceinline
00160   NaryInter::NaryInter(void) {}
00161 
00162   template<class I>
00163   forceinline void
00164   NaryInter::init(Region& r, I& i) {
00165     RangeListIter::init(r);
00166     f = NULL;
00167     set(copy(i));
00168   }
00169 
00170   template<class I, class J>
00171   forceinline void
00172   NaryInter::init(Region& r, I& i, J& j) {
00173     RangeListIter::init(r);
00174     f = NULL;
00175     RangeList*  h;
00176     RangeList** c = &h;
00177     while (i() && j()) {
00178       do {
00179         while (i() && (i.max() < j.min())) ++i;
00180         if (!i()) goto done;
00181         while (j() && (j.max() < i.min())) ++j;
00182         if (!j()) goto done;
00183       } while (i.max() < j.min());
00184       // Now the intervals overlap: consume the smaller interval
00185       RangeList* t = range(std::max(i.min(),j.min()),
00186                            std::min(i.max(),j.max()));
00187       *c = t; c = &t->next;
00188       if (i.max() < j.max()) ++i; else ++j;
00189     }
00190   done:
00191     *c = NULL;
00192     set(h);
00193   }
00194 
00195   template<class I>
00196   forceinline void
00197   NaryInter::init(Region& r, I* i, int n) {
00198     RangeListIter::init(r);
00199     f = NULL;
00200     if ((n > 0) && i[0]()) {
00201       RangeList*  h;
00202       RangeList** c = &h;
00203 
00204       int min = i[0].min();
00205       while (i[0]()) {
00206         // Initialize with last interval
00207         int max = i[0].max();
00208         // Intersect with all other intervals
00209       restart:
00210         for (int j=n; j--;) {
00211           // Skip intervals that are too small
00212           while (i[j]() && (i[j].max() < min))
00213             ++i[j];
00214           if (!i[j]())
00215             goto done;
00216           if (i[j].min() > max) {
00217             min=i[j].min();
00218             max=i[j].max();
00219             goto restart;
00220           }
00221           // Now the intervals overlap
00222           if (min < i[j].min())
00223             min = i[j].min();
00224           if (max > i[j].max())
00225             max = i[j].max();
00226         }
00227         RangeList* t = range(min,max);
00228         *c = t; c = &t->next;
00229         // The next interval must be at least two elements away
00230         min = max + 2;
00231       }
00232     done:
00233       *c = NULL;
00234       set(h);
00235     }
00236   }
00237 
00238   template<class I>
00239   forceinline
00240   NaryInter::NaryInter(Region& r, I& i) {
00241     init(r, i);
00242   }
00243   template<class I, class J>
00244   forceinline
00245   NaryInter::NaryInter(Region& r, I& i, J& j) {
00246     init(r, i, j);
00247   }
00248   template<class I>
00249   forceinline
00250   NaryInter::NaryInter(Region& r, I* i, int n) {
00251     init(r, i, n);
00252   }
00253 
00254   template<class I>
00255   forceinline void
00256   NaryInter::operator &=(I& i) {
00257     RangeList* j = get();
00258     // The new rangelist
00259     RangeList* h;
00260     RangeList** c = &h;
00261     while (i() && (j != NULL)) {
00262       do {
00263         while (i() && (i.max() < j->min))
00264           ++i;
00265         if (!i()) goto done;
00266         while ((j != NULL) && (j->max < i.min())) {
00267           RangeList* t = j->next;
00268           j->next = f; f = j;
00269           j = t;
00270         }
00271         if (j == NULL) goto done;
00272       } while (i.max() < j->min);
00273       // Now the intervals overlap: consume the smaller interval
00274       RangeList* t = range(std::max(i.min(),j->min),
00275                            std::min(i.max(),j->max),f);
00276       *c = t; c = &t->next;
00277       if (i.max() < j->max) {
00278         ++i;
00279       } else {
00280         RangeList* tn = j->next;
00281         j->next = f; f = j;
00282         j = tn;
00283       }
00284     }
00285   done:
00286     // Put remaining elements into freelist
00287     while (j != NULL) {
00288       RangeList* t = j->next;
00289       j->next = f; f = j;
00290       j = t;
00291     }
00292     *c = NULL;
00293     set(h);
00294   }
00295 
00296   forceinline NaryInter&
00297   NaryInter::operator =(const NaryInter& m) {
00298     f = NULL;
00299     return static_cast<NaryInter&>(RangeListIter::operator =(m));
00300   }
00301 
00302 }}}
00303 
00304 // STATISTICS: iter-any
00305