Generated on Sun Feb 17 15:24:19 2019 for Gecode by doxygen 1.6.3

bnd-sup.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  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2004
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2009
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode { namespace Int { namespace GCC {
00041 
00053   class UnReachable {
00054   public:
00056     int minb;
00058     int maxb;
00060     int eq;
00062     int le;
00064     int gr;
00065   };
00066 
00072   template<class Card>
00073   ExecStatus
00074   prop_card(Space& home,
00075             ViewArray<IntView>& x, ViewArray<Card>& k) {
00076     int n = x.size();
00077     int m = k.size();
00078     Region r;
00079     UnReachable* rv = r.alloc<UnReachable>(m);
00080     for(int i = m; i--; )
00081       rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0;
00082 
00083     for (int i = n; i--; ) {
00084       int min_idx;
00085       if (!lookupValue(k,x[i].min(),min_idx))
00086         return ES_FAILED;
00087       if (x[i].assigned()) {
00088         rv[min_idx].minb++;
00089         rv[min_idx].maxb++;
00090         rv[min_idx].eq++;
00091       } else {
00092         // count the number of variables
00093         // with lower bound k[min_idx].card()
00094         rv[min_idx].minb++;
00095         int max_idx;
00096         if (!lookupValue(k,x[i].max(),max_idx))
00097           return ES_FAILED;
00098         // count the number of variables
00099         // with upper bound k[max_idx].card()
00100         rv[max_idx].maxb++;
00101       }
00102     }
00103 
00104     rv[0].le = 0;
00105     int c_min = 0;
00106     for (int i = 1; i < m; i++) {
00107       rv[i].le = c_min + rv[i - 1].maxb;
00108       c_min += rv[i - 1].maxb;
00109     }
00110 
00111     rv[m-1].gr = 0;
00112     int c_max = 0;
00113     for (int i = m-1; i--; ) {
00114       rv[i].gr = c_max + rv[i + 1].minb;
00115       c_max += rv[i + 1].minb;
00116     }
00117 
00118     for (int i = m; i--; ) {
00119       int reachable = x.size() - rv[i].le - rv[i].gr;
00120       if (!k[i].assigned()) {
00121         GECODE_ME_CHECK(k[i].lq(home, reachable));
00122         GECODE_ME_CHECK(k[i].gq(home, rv[i].eq));
00123       } else {
00124         // check validity of the cardinality value
00125         if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable))
00126           return ES_FAILED;
00127       }
00128     }
00129 
00130     return ES_OK;
00131   }
00132 
00133 
00137   template<class Card>
00138   forceinline bool
00139   card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) {
00140     int smin = 0;
00141     int smax = 0;
00142     for (int i = k.size(); i--; ) {
00143       smax += k[i].max();
00144       smin += k[i].min();
00145     }
00146     // Consistent if number of variables within cardinality bounds
00147     return (smin <= x.size()) && (x.size() <= smax);
00148   }
00149 
00154   class Rank {
00155   public:
00160     int min;
00165     int max;
00166   };
00167 
00175   template<class View>
00176   class MaxInc {
00177   protected:
00179     ViewArray<View> x;
00180   public:
00182     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00184     forceinline bool
00185     operator ()(const int i, const int j) {
00186       return x[i].max() < x[j].max();
00187     }
00188   };
00189 
00190 
00198   template<class View>
00199   class MinInc {
00200   protected:
00202     ViewArray<View> x;
00203   public:
00205     MinInc(const ViewArray<View>& x0) : x(x0) {}
00207     forceinline bool
00208     operator ()(const int i, const int j) {
00209       return x[i].min() < x[j].min();
00210     }
00211   };
00212 
00213 
00220   template<class Card>
00221   class MinIdx {
00222   public:
00224     forceinline bool
00225     operator ()(const Card& x, const Card& y) {
00226       return x.card() < y.card();
00227     }
00228   };
00229 
00236   template<class Card>
00237   class PartialSum {
00238   private:
00240     int* sum;
00242     int size;
00243   public:
00245     int firstValue, lastValue;
00247 
00248 
00249     PartialSum(void);
00251     void init(Space& home, ViewArray<Card>& k, bool up);
00253     void reinit(void);
00255     operator bool(void) const;
00257 
00258 
00259 
00260     int sumup(int from, int to) const;
00262     int minValue(void) const;
00264     int maxValue(void) const;
00266     int skipNonNullElementsRight(int v) const;
00268     int skipNonNullElementsLeft(int v) const;
00270 
00271 
00272 
00279     bool check_update_min(ViewArray<Card>& k);
00287     bool check_update_max(ViewArray<Card>& k);
00289   };
00290 
00291 
00292   template<class Card>
00293   forceinline
00294   PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {}
00295 
00296   template<class Card>
00297   forceinline
00298   PartialSum<Card>::operator bool(void) const {
00299     return size != -1;
00300   }
00301   template<class Card>
00302   inline void
00303   PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) {
00304     int i = 0;
00305     int j = 0;
00306 
00307     // Determine number of holes in the index set
00308     int holes = 0;
00309     for (i = 1; i < elements.size(); i++) {
00310       if (elements[i].card() != elements[i-1].card() + 1)
00311         holes += elements[i].card()-elements[i-1].card()-1;
00312     }
00313 
00314     // we add three elements at the beginning and two at the end
00315     size  = elements.size() + holes + 5;
00316 
00317     // memory allocation
00318     if (sum == NULL) {
00319       sum = home.alloc<int>(2*size);
00320     }
00321     int* ds  = &sum[size];
00322 
00323     int first = elements[0].card();
00324 
00325     firstValue = first - 3;
00326     lastValue  = first + elements.size() + holes + 1;
00327 
00328     // the first three elements
00329     for (i = 3; i--; )
00330       sum[i] = i;
00331 
00332     /*
00333      * copy the bounds into sum, filling up holes with zeroes
00334      */
00335     int prevCard = elements[0].card()-1;
00336     i = 0;
00337     for (j = 2; j < elements.size() + holes + 2; j++) {
00338       if (elements[i].card() != prevCard + 1) {
00339         sum[j + 1] = sum[j];
00340       } else if (up) {
00341         sum[j + 1] = sum[j] + elements[i].max();
00342         i++;
00343       } else {
00344         sum[j + 1] = sum[j] + elements[i].min();
00345         i++;
00346       }
00347       prevCard++;
00348     }
00349     sum[j + 1] = sum[j] + 1;
00350     sum[j + 2] = sum[j + 1] + 1;
00351 
00352     // Compute distances, eliminating zeroes
00353     i = elements.size() + holes + 3;
00354     j = i + 1;
00355     for ( ; i > 0; ) {
00356       while(sum[i] == sum[i - 1]) {
00357         ds[i] = j;
00358         i--;
00359       }
00360       ds[j] = i;
00361       i--;
00362       j = ds[j];
00363     }
00364     ds[j] = 0;
00365     ds[0] = 0;
00366   }
00367 
00368   template<class Card>
00369   forceinline void
00370   PartialSum<Card>::reinit(void) {
00371     size = -1;
00372   }
00373 
00374 
00375   template<class Card>
00376   forceinline int
00377   PartialSum<Card>::sumup(int from, int to) const {
00378     if (from <= to) {
00379       return sum[to - firstValue] - sum[from - firstValue - 1];
00380     } else {
00381       assert(to - firstValue - 1 >= 0);
00382       assert(to - firstValue - 1 < size);
00383       assert(from - firstValue >= 0);
00384       assert(from - firstValue < size);
00385       return sum[to - firstValue - 1] - sum[from - firstValue];
00386     }
00387   }
00388 
00389   template<class Card>
00390   forceinline int
00391   PartialSum<Card>::minValue(void) const {
00392     return firstValue + 3;
00393   }
00394   template<class Card>
00395   forceinline int
00396   PartialSum<Card>::maxValue(void) const {
00397     return lastValue - 2;
00398   }
00399 
00400 
00401   template<class Card>
00402   forceinline int
00403   PartialSum<Card>::skipNonNullElementsRight(int value) const {
00404     value -= firstValue;
00405     int* ds  = &sum[size];
00406     return (ds[value] < value ? value : ds[value]) + firstValue;
00407   }
00408   template<class Card>
00409   forceinline int
00410   PartialSum<Card>::skipNonNullElementsLeft(int value) const {
00411     value -= firstValue;
00412     int* ds  = &sum[size];
00413     return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00414   }
00415 
00416   template<class Card>
00417   inline bool
00418   PartialSum<Card>::check_update_max(ViewArray<Card>& k) {
00419     int j = 0;
00420     for (int i = 3; i < size - 2; i++) {
00421       int max = 0;
00422       if (k[j].card() == i+firstValue)
00423         max = k[j++].max();
00424       if ((sum[i] - sum[i - 1]) != max)
00425         return true;
00426     }
00427     return false;
00428   }
00429 
00430   template<class Card>
00431   inline bool
00432   PartialSum<Card>::check_update_min(ViewArray<Card>& k) {
00433     int j = 0;
00434     for (int i = 3; i < size - 2; i++) {
00435       int min = 0;
00436       if (k[j].card() == i+firstValue)
00437         min = k[j++].min();
00438       if ((sum[i] - sum[i - 1]) != min)
00439         return true;
00440     }
00441     return false;
00442   }
00443 
00444 
00456   class HallInfo {
00457   public:
00459     int bounds;
00465     int t;
00473     int d;
00482     int h;
00484     int s;
00486     int ps;
00493     int newBound;
00494   };
00495 
00496 
00505 
00506   forceinline void
00507   pathset_ps(HallInfo hall[], int start, int end, int to) {
00508     int k, l;
00509     for (l=start; (k=l) != end; hall[k].ps=to) {
00510       l = hall[k].ps;
00511     }
00512   }
00514   forceinline void
00515   pathset_s(HallInfo hall[], int start, int end, int to) {
00516     int k, l;
00517     for (l=start; (k=l) != end; hall[k].s=to) {
00518       l = hall[k].s;
00519     }
00520   }
00522   forceinline void
00523   pathset_t(HallInfo hall[], int start, int end, int to) {
00524     int k, l;
00525     for (l=start; (k=l) != end; hall[k].t=to) {
00526       l = hall[k].t;
00527     }
00528   }
00530   forceinline void
00531   pathset_h(HallInfo hall[], int start, int end, int to) {
00532     int k, l;
00533     for (l=start; (k=l) != end; hall[k].h=to) {
00534       l = hall[k].h;
00535       assert(l != k);
00536     }
00537   }
00539 
00547 
00548   forceinline int
00549   pathmin_h(const HallInfo hall[], int i) {
00550     while (hall[i].h < i)
00551       i = hall[i].h;
00552     return i;
00553   }
00555   forceinline int
00556   pathmin_t(const HallInfo hall[], int i) {
00557     while (hall[i].t < i)
00558       i = hall[i].t;
00559     return i;
00560   }
00562 
00570 
00571   forceinline int
00572   pathmax_h(const HallInfo hall[], int i) {
00573     while (hall[i].h > i)
00574       i = hall[i].h;
00575     return i;
00576   }
00578   forceinline int
00579   pathmax_t(const HallInfo hall[], int i) {
00580     while (hall[i].t > i) {
00581       i = hall[i].t;
00582     }
00583     return i;
00584   }
00586   forceinline int
00587   pathmax_s(const HallInfo hall[], int i) {
00588     while (hall[i].s > i)
00589       i = hall[i].s;
00590     return i;
00591   }
00593   forceinline int
00594   pathmax_ps(const HallInfo hall[], int i) {
00595     while (hall[i].ps > i)
00596       i = hall[i].ps;
00597     return i;
00598   }
00600 
00601 }}}
00602 
00603 // STATISTICS: int-prop
00604