Generated on Thu Mar 22 10:39:38 2012 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  *  Last modified:
00016  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00017  *     $Revision: 10684 $
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 
00057   class UnReachable {
00058   public:
00060     int minb;
00062     int maxb;
00064     int eq;
00066     int le;
00068     int gr;
00069   };
00070 
00076   template<class Card>
00077   ExecStatus
00078   prop_card(Space& home, 
00079             ViewArray<IntView>& x, ViewArray<Card>& k) {
00080     int n = x.size();
00081     int m = k.size();
00082     Region r(home);
00083     UnReachable* rv = r.alloc<UnReachable>(m);
00084     for(int i = m; i--; )
00085       rv[i].minb=rv[i].maxb=rv[i].le=rv[i].gr=rv[i].eq=0;
00086 
00087     for (int i = n; i--; ) {
00088       int min_idx;
00089       if (!lookupValue(k,x[i].min(),min_idx))
00090         return ES_FAILED;
00091       if (x[i].assigned()) {
00092         rv[min_idx].minb++;
00093         rv[min_idx].maxb++;
00094         rv[min_idx].eq++;
00095       } else {
00096         // count the number of variables
00097         // with lower bound k[min_idx].card()
00098         rv[min_idx].minb++;
00099         int max_idx;
00100         if (!lookupValue(k,x[i].max(),max_idx))
00101           return ES_FAILED;
00102         // count the number of variables
00103         // with upper bound k[max_idx].card()
00104         rv[max_idx].maxb++;
00105       }
00106     }
00107 
00108     rv[0].le = 0;
00109     int c_min = 0;
00110     for (int i = 1; i < m; i++) {
00111       rv[i].le = c_min + rv[i - 1].maxb;
00112       c_min += rv[i - 1].maxb;
00113     }
00114 
00115     rv[m-1].gr = 0;
00116     int c_max = 0;
00117     for (int i = m-1; i--; ) {
00118       rv[i].gr = c_max + rv[i + 1].minb;
00119       c_max += rv[i + 1].minb;
00120     }
00121 
00122     for (int i = m; i--; ) {
00123       int reachable = x.size() - rv[i].le - rv[i].gr;
00124       if (!k[i].assigned()) {
00125         GECODE_ME_CHECK(k[i].lq(home, reachable));
00126         GECODE_ME_CHECK(k[i].gq(home, rv[i].eq));
00127       } else {
00128         // check validity of the cardinality value
00129         if ((rv[i].eq > k[i].max()) || (k[i].max() > reachable))
00130           return ES_FAILED;
00131       }
00132     }
00133 
00134     return ES_OK;
00135   }
00136 
00137 
00141   template<class Card>
00142   forceinline bool
00143   card_consistent(ViewArray<IntView>& x, ViewArray<Card>& k) {
00144     int smin = 0;
00145     int smax = 0;
00146     for (int i = k.size(); i--; ) {
00147       smax += k[i].max();
00148       smin += k[i].min();
00149     }
00150     // Consistent if number of variables within cardinality bounds
00151     return (smin <= x.size()) && (x.size() <= smax);
00152   }
00153 
00158   class Rank {
00159   public:
00164     int min;
00169     int max;
00170   };
00171 
00179   template<class View>
00180   class MaxInc {
00181   protected:
00183     ViewArray<View> x;
00184   public:
00186     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00188     forceinline bool
00189     operator ()(const int i, const int j) {
00190       return x[i].max() < x[j].max();
00191     }
00192   };
00193 
00194 
00202   template<class View>
00203   class MinInc {
00204   protected:
00206     ViewArray<View> x;
00207   public:
00209     MinInc(const ViewArray<View>& x0) : x(x0) {}
00211     forceinline bool
00212     operator ()(const int i, const int j) {
00213       return x[i].min() < x[j].min();
00214     }
00215   };
00216 
00217 
00224   template<class Card>
00225   class MinIdx {
00226   public:
00228     forceinline bool
00229     operator ()(const Card& x, const Card& y) {
00230       return x.card() < y.card();
00231     }
00232   };
00233 
00240   template<class Card>
00241   class PartialSum {
00242   private:
00244     int* sum;
00246     int size;
00247   public:
00249     int firstValue, lastValue;
00251 
00252 
00253     PartialSum(void);
00255     void init(Space& home, ViewArray<Card>& k, bool up);
00257     void reinit(void);
00259     bool initialized(void) const;
00261 
00262 
00263 
00264     int sumup(int from, int to) const;
00266     int minValue(void) const;
00268     int maxValue(void) const;
00270     int skipNonNullElementsRight(int v) const;
00272     int skipNonNullElementsLeft(int v) const;
00274 
00275 
00276 
00283     bool check_update_min(ViewArray<Card>& k);
00291     bool check_update_max(ViewArray<Card>& k);
00293   };
00294 
00295 
00296   template<class Card>
00297   forceinline
00298   PartialSum<Card>::PartialSum(void) : sum(NULL), size(-1) {}
00299 
00300   template<class Card>
00301   forceinline bool
00302   PartialSum<Card>::initialized(void) const {
00303     return size != -1;
00304   }
00305   template<class Card>
00306   inline void
00307   PartialSum<Card>::init(Space& home, ViewArray<Card>& elements, bool up) {
00308     int i = 0;
00309     int j = 0;
00310 
00311     // Determine number of holes in the index set
00312     int holes = 0;
00313     for (i = 1; i < elements.size(); i++) {
00314       if (elements[i].card() != elements[i-1].card() + 1)
00315         holes += elements[i].card()-elements[i-1].card()-1;
00316     }
00317 
00318     // we add three elements at the beginning and two at the end
00319     size  = elements.size() + holes + 5;
00320 
00321     // memory allocation
00322     if (sum == NULL) {
00323       sum = home.alloc<int>(2*size);
00324     }
00325     int* ds  = &sum[size];
00326 
00327     int first = elements[0].card();
00328 
00329     firstValue = first - 3;
00330     lastValue  = first + elements.size() + holes + 1;
00331 
00332     // the first three elements
00333     for (i = 3; i--; )
00334       sum[i] = i;
00335 
00336     /*
00337      * copy the bounds into sum, filling up holes with zeroes
00338      */
00339     int prevCard = elements[0].card()-1;
00340     i = 0;
00341     for (j = 2; j < elements.size() + holes + 2; j++) {
00342       if (elements[i].card() != prevCard + 1) {
00343         sum[j + 1] = sum[j];
00344       } else if (up) {
00345         sum[j + 1] = sum[j] + elements[i].max();
00346         i++;
00347       } else {
00348         sum[j + 1] = sum[j] + elements[i].min();
00349         i++;
00350       }
00351       prevCard++;
00352     }
00353     sum[j + 1] = sum[j] + 1;
00354     sum[j + 2] = sum[j + 1] + 1;
00355 
00356     // Compute distances, eliminating zeroes
00357     i = elements.size() + holes + 3;
00358     j = i + 1;
00359     for ( ; i > 0; ) {
00360       while(sum[i] == sum[i - 1]) {
00361         ds[i] = j;
00362         i--;
00363       }
00364       ds[j] = i;
00365       i--;
00366       j = ds[j];
00367     }
00368     ds[j] = 0;
00369     ds[0] = 0;
00370   }
00371 
00372   template<class Card>
00373   forceinline void
00374   PartialSum<Card>::reinit(void) {
00375     size = -1;
00376   }
00377 
00378 
00379   template<class Card>
00380   forceinline int
00381   PartialSum<Card>::sumup(int from, int to) const {
00382     if (from <= to) {
00383       return sum[to - firstValue] - sum[from - firstValue - 1];
00384     } else {
00385       assert(to - firstValue - 1 >= 0);
00386       assert(to - firstValue - 1 < size);
00387       assert(from - firstValue >= 0);
00388       assert(from - firstValue < size);
00389       return sum[to - firstValue - 1] - sum[from - firstValue];
00390     }
00391   }
00392 
00393   template<class Card>
00394   forceinline int
00395   PartialSum<Card>::minValue(void) const {
00396     return firstValue + 3;
00397   }
00398   template<class Card>
00399   forceinline int
00400   PartialSum<Card>::maxValue(void) const {
00401     return lastValue - 2;
00402   }
00403 
00404 
00405   template<class Card>
00406   forceinline int
00407   PartialSum<Card>::skipNonNullElementsRight(int value) const {
00408     value -= firstValue;
00409     int* ds  = &sum[size];
00410     return (ds[value] < value ? value : ds[value]) + firstValue;
00411   }
00412   template<class Card>
00413   forceinline int
00414   PartialSum<Card>::skipNonNullElementsLeft(int value) const {
00415     value -= firstValue;
00416     int* ds  = &sum[size];
00417     return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00418   }
00419 
00420   template<class Card>
00421   inline bool
00422   PartialSum<Card>::check_update_max(ViewArray<Card>& k) {
00423     int j = 0;
00424     for (int i = 3; i < size - 2; i++) {
00425       int max = 0;
00426       if (k[j].card() == i+firstValue)
00427         max = k[j++].max();
00428       if ((sum[i] - sum[i - 1]) != max)
00429         return true;
00430     }
00431     return false;
00432   }
00433 
00434   template<class Card>
00435   inline bool
00436   PartialSum<Card>::check_update_min(ViewArray<Card>& k) {
00437     int j = 0;
00438     for (int i = 3; i < size - 2; i++) {
00439       int min = 0;
00440       if (k[j].card() == i+firstValue)
00441         min = k[j++].min();
00442       if ((sum[i] - sum[i - 1]) != min)
00443         return true;
00444     }
00445     return false;
00446   }
00447 
00448 
00460   class HallInfo {
00461   public:
00463     int bounds;
00469     int t;
00477     int d;
00486     int h;
00488     int s;
00490     int ps;
00497     int newBound;
00498   };
00499 
00500 
00509 
00510   forceinline void
00511   pathset_ps(HallInfo hall[], int start, int end, int to) {
00512     int k, l;
00513     for (l=start; (k=l) != end; hall[k].ps=to) {
00514       l = hall[k].ps;
00515     }
00516   }
00518   forceinline void
00519   pathset_s(HallInfo hall[], int start, int end, int to) {
00520     int k, l;
00521     for (l=start; (k=l) != end; hall[k].s=to) {
00522       l = hall[k].s;
00523     }
00524   }
00526   forceinline void
00527   pathset_t(HallInfo hall[], int start, int end, int to) {
00528     int k, l;
00529     for (l=start; (k=l) != end; hall[k].t=to) {
00530       l = hall[k].t;
00531     }
00532   }
00534   forceinline void
00535   pathset_h(HallInfo hall[], int start, int end, int to) {
00536     int k, l;
00537     for (l=start; (k=l) != end; hall[k].h=to) {
00538       l = hall[k].h;
00539       assert(l != k);
00540     }
00541   }
00543 
00551 
00552   forceinline int
00553   pathmin_h(const HallInfo hall[], int i) {
00554     while (hall[i].h < i)
00555       i = hall[i].h;
00556     return i;
00557   }
00559   forceinline int
00560   pathmin_t(const HallInfo hall[], int i) {
00561     while (hall[i].t < i)
00562       i = hall[i].t;
00563     return i;
00564   }
00566 
00574 
00575   forceinline int
00576   pathmax_h(const HallInfo hall[], int i) {
00577     while (hall[i].h > i)
00578       i = hall[i].h;
00579     return i;
00580   }
00582   forceinline int
00583   pathmax_t(const HallInfo hall[], int i) {
00584     while (hall[i].t > i) {
00585       i = hall[i].t;
00586     }
00587     return i;
00588   }
00590   forceinline int
00591   pathmax_s(const HallInfo hall[], int i) {
00592     while (hall[i].s > i)
00593       i = hall[i].s;
00594     return i;
00595   }
00597   forceinline int
00598   pathmax_ps(const HallInfo hall[], int i) {
00599     while (hall[i].ps > i)
00600       i = hall[i].ps;
00601     return i;
00602   }
00604 
00605 }}}
00606 
00607 // STATISTICS: int-prop
00608