Generated on Mon Nov 30 23:53:26 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00016  *     $Date: 2009-09-30 14:52:38 +0200 (Wed, 30 Sep 2009) $ by $Author: tack $
00017  *     $Revision: 9787 $
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 Int { namespace GCC {
00045 
00058   class UnReachable {
00059   public:
00061     int minb;
00063     int maxb;
00065     int eq;
00067     int le;
00069     int gr;
00070   };
00071 
00077   template<class Card>
00078   ExecStatus
00079   prop_card(Space& home, 
00080             ViewArray<IntView>& x, ViewArray<Card>& k) {
00081     int n = x.size();
00082     int m = k.size();
00083     Region r(home);
00084     UnReachable* rv = r.alloc<UnReachable>(m);
00085     for(int i = m; i--; )
00086       rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0;
00087 
00088     for (int i = n; i--; ) {
00089       int min_idx;
00090       if (!lookupValue(k,x[i].min(),min_idx))
00091         return ES_FAILED;
00092       if (x[i].assigned()) {
00093         rv[min_idx].minb++;
00094         rv[min_idx].maxb++;
00095         rv[min_idx].eq++;
00096       } else {
00097         // count the number of variables
00098         // with lower bound k[min_idx].card()
00099         rv[min_idx].minb++;
00100         int max_idx;
00101         if (!lookupValue(k,x[i].max(),max_idx))
00102           return ES_FAILED;
00103         // count the number of variables
00104         // with upper bound k[max_idx].card()
00105         rv[max_idx].maxb++;
00106       }
00107     }
00108 
00109     rv[0].le = 0;
00110     int c_min = 0;
00111     for (int i = 1; i < m; i++) {
00112       rv[i].le = c_min + rv[i - 1].maxb;
00113       c_min += rv[i - 1].maxb;
00114     }
00115 
00116     rv[m-1].gr = 0;
00117     int c_max = 0;
00118     for (int i = m-1; i--; ) {
00119       rv[i].gr = c_max + rv[i + 1].minb;
00120       c_max += rv[i + 1].minb;
00121     }
00122 
00123     for (int i = m; i--; ) {
00124       int reachable = x.size() - rv[i].le - rv[i].gr;
00125       if (!k[i].assigned()) {
00126         GECODE_ME_CHECK(k[i].lq(home, reachable));
00127         GECODE_ME_CHECK(k[i].gq(home, rv[i].eq));
00128       } else {
00129         // check validity of the cardinality value
00130         if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable))
00131           return ES_FAILED;
00132       }
00133     }
00134 
00135     return ES_OK;
00136   }
00137 
00138 
00142   template<class Card>
00143   forceinline bool
00144   card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) {
00145     int smin = 0;
00146     int smax = 0;
00147     for (int i = k.size(); i--; ) {
00148       smax += k[i].max();
00149       smin += k[i].min();
00150     }
00151     // Consistent if number of variables within cardinality bounds
00152     return (smin <= x.size()) && (x.size() <= smax);
00153   }
00154 
00159   class Rank {
00160   public:
00165     int min;
00170     int max;
00171   };
00172 
00180   template<class View>
00181   class MaxInc {
00182   protected:
00184     ViewArray<View> x;
00185   public:
00187     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00189     forceinline bool
00190     operator ()(const int i, const int j) {
00191       return x[i].max() < x[j].max();
00192     }
00193   };
00194 
00195 
00203   template<class View>
00204   class MinInc {
00205   protected:
00207     ViewArray<View> x;
00208   public:
00210     MinInc(const ViewArray<View>& x0) : x(x0) {}
00212     forceinline bool
00213     operator ()(const int i, const int j) {
00214       return x[i].min() < x[j].min();
00215     }
00216   };
00217 
00218 
00225   template<class Card>
00226   class MinIdx {
00227   public:
00229     forceinline bool
00230     operator ()(const Card& x, const Card& y) {
00231       return x.card() < y.card();
00232     }
00233   };
00234 
00241   template<class Card>
00242   class PartialSum {
00243   private:
00245     int* sum;
00247     int size;
00248   public:
00250     int firstValue, lastValue;
00252 
00253 
00254     PartialSum(void);
00256     void init(Space& home, ViewArray<Card>& k, bool up);
00258     void reinit(void);
00260     bool initialized(void) const;
00262 
00263 
00264 
00265     int sumup(int from, int to) const;
00267     int minValue(void) const;
00269     int maxValue(void) const;
00271     int skipNonNullElementsRight(int v) const;
00273     int skipNonNullElementsLeft(int v) const;
00275 
00276 
00277 
00284     bool check_update_min(ViewArray<Card>& k);
00292     bool check_update_max(ViewArray<Card>& k);
00294   };
00295 
00296 
00297   template<class Card>
00298   forceinline
00299   PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {}
00300 
00301   template<class Card>
00302   forceinline bool
00303   PartialSum<Card>::initialized(void) const {
00304     return size != -1;
00305   }
00306   template<class Card>
00307   inline void
00308   PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) {
00309     int i = 0;
00310     int j = 0;
00311 
00312     // Determine number of holes in the index set
00313     int holes = 0;
00314     for (i = 1; i < elements.size(); i++) {
00315       if (elements[i].card() != elements[i-1].card() + 1)
00316         holes += elements[i].card()-elements[i-1].card()-1;
00317     }
00318 
00319     // we add three elements at the beginning and two at the end
00320     size  = elements.size() + holes + 5;
00321 
00322     // memory allocation
00323     if (sum == NULL) {
00324       sum = home.alloc<int>(2*size);
00325     }
00326     int* ds  = &sum[size];
00327 
00328     int first = elements[0].card();
00329 
00330     firstValue = first - 3;
00331     lastValue  = first + elements.size() + holes + 1;
00332 
00333     // the first three elements
00334     for (i = 3; i--; )
00335       sum[i] = i;
00336 
00337     /*
00338      * copy the bounds into sum, filling up holes with zeroes
00339      */
00340     int prevCard = elements[0].card()-1;
00341     i = 0;
00342     for (j = 2; j < elements.size() + holes + 2; j++) {
00343       if (elements[i].card() != prevCard + 1) {
00344         sum[j + 1] = sum[j];
00345       } else if (up) {
00346         sum[j + 1] = sum[j] + elements[i].max();
00347         i++;
00348       } else {
00349         sum[j + 1] = sum[j] + elements[i].min();
00350         i++;
00351       }
00352       prevCard++;
00353     }
00354     sum[j + 1] = sum[j] + 1;
00355     sum[j + 2] = sum[j + 1] + 1;
00356 
00357     // Compute distances, eliminating zeroes
00358     i = elements.size() + holes + 3;
00359     j = i + 1;
00360     for ( ; i > 0; ) {
00361       while(sum[i] == sum[i - 1]) {
00362         ds[i] = j;
00363         i--;
00364       }
00365       ds[j] = i;
00366       i--;
00367       j = ds[j];
00368     }
00369     ds[j] = 0;
00370     ds[0] = 0;
00371   }
00372 
00373   template<class Card>
00374   forceinline void
00375   PartialSum<Card>::reinit(void) {
00376     size = -1;
00377   }
00378 
00379 
00380   template<class Card>
00381   forceinline int
00382   PartialSum<Card>::sumup(int from, int to) const {
00383     if (from <= to) {
00384       return sum[to - firstValue] - sum[from - firstValue - 1];
00385     } else {
00386       assert(to - firstValue - 1 >= 0);
00387       assert(to - firstValue - 1 < size);
00388       assert(from - firstValue >= 0);
00389       assert(from - firstValue < size);
00390       return sum[to - firstValue - 1] - sum[from - firstValue];
00391     }
00392   }
00393 
00394   template<class Card>
00395   forceinline int
00396   PartialSum<Card>::minValue(void) const {
00397     return firstValue + 3;
00398   }
00399   template<class Card>
00400   forceinline int
00401   PartialSum<Card>::maxValue(void) const {
00402     return lastValue - 2;
00403   }
00404 
00405 
00406   template<class Card>
00407   forceinline int
00408   PartialSum<Card>::skipNonNullElementsRight(int value) const {
00409     value -= firstValue;
00410     int* ds  = &sum[size];
00411     return (ds[value] < value ? value : ds[value]) + firstValue;
00412   }
00413   template<class Card>
00414   forceinline int
00415   PartialSum<Card>::skipNonNullElementsLeft(int value) const {
00416     value -= firstValue;
00417     int* ds  = &sum[size];
00418     return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00419   }
00420 
00421   template<class Card>
00422   inline bool
00423   PartialSum<Card>::check_update_max(ViewArray<Card>& k) {
00424     int j = 0;
00425     for (int i = 3; i < size - 2; i++) {
00426       int max = 0;
00427       if (k[j].card() == i+firstValue)
00428         max = k[j++].max();
00429       if ((sum[i] - sum[i - 1]) != max)
00430         return true;
00431     }
00432     return false;
00433   }
00434 
00435   template<class Card>
00436   inline bool
00437   PartialSum<Card>::check_update_min(ViewArray<Card>& k) {
00438     int j = 0;
00439     for (int i = 3; i < size - 2; i++) {
00440       int min = 0;
00441       if (k[j].card() == i+firstValue)
00442         min = k[j++].min();
00443       if ((sum[i] - sum[i - 1]) != min)
00444         return true;
00445     }
00446     return false;
00447   }
00448 
00449 
00461   class HallInfo {
00462   public:
00464     int bounds;
00470     int t;
00478     int d;
00487     int h;
00489     int s;
00491     int ps;
00498     int newBound;
00499   };
00500 
00501 
00510 
00511   forceinline void
00512   pathset_ps(HallInfo hall[], int start, int end, int to) {
00513     int k, l;
00514     for (l=start; (k=l) != end; hall[k].ps=to) {
00515       l = hall[k].ps;
00516     }
00517   }
00519   forceinline void
00520   pathset_s(HallInfo hall[], int start, int end, int to) {
00521     int k, l;
00522     for (l=start; (k=l) != end; hall[k].s=to) {
00523       l = hall[k].s;
00524     }
00525   }
00527   forceinline void
00528   pathset_t(HallInfo hall[], int start, int end, int to) {
00529     int k, l;
00530     for (l=start; (k=l) != end; hall[k].t=to) {
00531       l = hall[k].t;
00532     }
00533   }
00535   forceinline void
00536   pathset_h(HallInfo hall[], int start, int end, int to) {
00537     int k, l;
00538     for (l=start; (k=l) != end; hall[k].h=to) {
00539       l = hall[k].h;
00540       assert(l != k);
00541     }
00542   }
00544 
00552 
00553   forceinline int
00554   pathmin_h(const HallInfo hall[], int i) {
00555     while (hall[i].h < i)
00556       i = hall[i].h;
00557     return i;
00558   }
00560   forceinline int
00561   pathmin_t(const HallInfo hall[], int i) {
00562     while (hall[i].t < i)
00563       i = hall[i].t;
00564     return i;
00565   }
00567 
00575 
00576   forceinline int
00577   pathmax_h(const HallInfo hall[], int i) {
00578     while (hall[i].h > i)
00579       i = hall[i].h;
00580     return i;
00581   }
00583   forceinline int
00584   pathmax_t(const HallInfo hall[], int i) {
00585     while (hall[i].t > i) {
00586       i = hall[i].t;
00587     }
00588     return i;
00589   }
00591   forceinline int
00592   pathmax_s(const HallInfo hall[], int i) {
00593     while (hall[i].s > i)
00594       i = hall[i].s;
00595     return i;
00596   }
00598   forceinline int
00599   pathmax_ps(const HallInfo hall[], int i) {
00600     while (hall[i].ps > i)
00601       i = hall[i].ps;
00602     return i;
00603   }
00605 
00606 }}}
00607 
00608 // STATISTICS: int-prop
00609