Generated on Thu Jul 6 07:06:44 2006 for Gecode by doxygen 1.4.7

gccbndsup.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-06-13 15:32:47 +0200 (Tue, 13 Jun 2006) $ by $Author: tack $
00010  *     $Revision: 3289 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #ifdef NDEBUG
00023 #define START_SIZE
00024 #define END_SIZE
00025 #else
00026 #define START_SIZE  int start_size = k.size();
00027 #define END_SIZE    int end_size = k.size();
00028 #endif
00029 
00030 
00031 
00032 namespace Gecode { namespace Int { namespace GCC {
00033 
00035 
00036 
00042   class UnReachable {
00043   public:
00044     unsigned int minb;
00045     unsigned int maxb;
00046     unsigned int eq;
00047     unsigned int le;
00048     unsigned int gr;
00049   };
00050 
00055   template <class View, class Card, bool shared>
00056   forceinline ExecStatus 
00057   prop_card(Space* home, ViewArray<View>& x, ViewArray<Card>& k, bool& mod) {
00058     int n = x.size();
00059     int m = k.size();
00060     GECODE_AUTOARRAY(UnReachable, rv, m);
00061     for(int i = m; i--; ) {
00062       rv[i].minb    = 0;
00063       rv[i].maxb    = 0;
00064       rv[i].le = 0;
00065       rv[i].gr = 0;
00066       rv[i].eq = 0;
00067     }
00068 
00069     for (int i = n; i--; ) {
00070       int b = x[i].assigned();
00071       int min_idx = 0;
00072       int max_idx = 0;
00073       min_idx = lookupValue(k,x[i].min());
00074       if (min_idx == -1) {
00075         return ES_FAILED;
00076       }
00077       if (b) {
00078         rv[min_idx].minb++;
00079         rv[min_idx].maxb++;
00080         rv[min_idx].eq++;
00081       } else {
00082         max_idx = lookupValue(k,x[i].max());
00083         if (max_idx == -1) {
00084           return ES_FAILED;
00085         }
00086         // count the number of variables 
00087         // with lower bound k[min_idx].card()
00088         rv[min_idx].minb++;
00089 
00090         // count the number of variables 
00091         // with upper bound k[max_idx].card()
00092         rv[max_idx].maxb++;
00093       }      
00094     }
00095     
00096     rv[0].le = 0;
00097     int c_min = 0;
00098     for (int i = 1; i < m; i++) {
00099       rv[i].le = c_min + rv[i - 1].maxb;
00100       c_min += rv[i - 1].maxb;
00101     }
00102 
00103     rv[m-1].gr = 0;
00104     int c_max = 0;
00105     for (int i = m-1; i--; ) {
00106       rv[i].gr = c_max + rv[i + 1].minb;
00107       c_max += rv[i + 1].minb;
00108     }
00109     
00110     for (int i = m; i--; ) {
00111       int reachable = (int) (x.size() - rv[i].le - rv[i].gr);
00112       if (!k[i].assigned()) {
00113         ModEvent me = k[i].lq(home, reachable);
00114         if (me_failed(me)) {
00115           return ES_FAILED;
00116         }
00117         mod |= (k[i].modified() && (k[i].max() != reachable));
00118         mod |= shared && k[i].modified();
00119           
00120         if (rv[i].eq > 0) {
00121           ModEvent me = k[i].gq(home, (int) rv[i].eq);
00122           if (me_failed(me)) {
00123             return ES_FAILED;
00124           }
00125           mod |= (k[i].modified() && (k[i].min() != (int) rv[i].eq));
00126           mod |= shared && k[i].modified();
00127         }
00128       } else {
00129         // check validity of the cardinality value
00130         int v = k[i].max();
00131         if ( !( (int) rv[i].eq <= v && v <= reachable) ) {
00132           return ES_FAILED;
00133         }
00134       }
00135     }
00136 
00137     return ES_OK;
00138   }
00139 
00140 
00144   template <class View, class Card>
00145   inline bool
00146   card_consistent(int& smin, int& smax, ViewArray<View>& x,
00147                   ViewArray<Card>& k, bool& all) {
00148     
00149     int m = k.size();
00150     int n = x.size();
00151     for (int i = m; i--; ) {
00152       smax += k[i].max();
00153       smin += k[i].min();
00154     }
00155 
00156     // not enough variables to satifsy cardinality requirements
00157     if (n < smin) {
00158       return false;
00159     } 
00160 
00161     // if we use all variables
00162     // not all variables can be assigned
00163     if (all && smax < n) {
00164       return false;
00165     }
00166         
00167     return true;
00168   }
00169 
00173   class Rank {
00174   public:
00179     int min;
00184     int max;
00185   };
00186 
00194   template <class View>
00195   class MaxInc {
00196   protected:
00197     ViewArray<View> x;
00198   public:
00199     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00200     forceinline bool
00201     operator()(const int i, const int j) {
00202       return x[i].max() < x[j].max();
00203     }
00204   };
00205 
00213   template <class View>
00214   class MinInc {
00215   protected:
00216     ViewArray<View> x;
00217   public:
00218     MinInc(const ViewArray<View>& x0) : x(x0) {}
00219     forceinline bool
00220     operator()(const int i, const int j) {
00221       return x[i].min() < x[j].min();
00222     }
00223   };
00224 
00225 
00231   template <class Card>
00232   class PartialSum {
00233   private:
00235     char* mem;
00237     int* sum;  
00242     int* ds;   
00244     int size;
00245   public:    
00247 
00248     PartialSum( int, int, ViewArray<Card>& , bool);
00249     ~PartialSum(void);
00251 
00252 
00253     int firstValue;
00254     int lastValue;
00255     int sumup(int, int);
00256     int minValue(void);
00257     int maxValue(void);
00258     int skipNonNullElementsRight(int);
00259     int skipNonNullElementsLeft(int);
00260     void* operator new(size_t s);
00261     void operator delete(void* p);
00262     void print(void);
00263     bool check_update_max(ViewArray<Card>& k);
00264     bool check_update_min(ViewArray<Card>& k);
00265     int getsize(void);
00267   };
00268 
00270   template <class Card>
00271   forceinline 
00272   PartialSum<Card>::~PartialSum(void){
00273     assert(mem != NULL);
00274     Memory::free(mem);
00275   }
00276 
00278   template <class Card>
00279   forceinline void*
00280   PartialSum<Card>::operator new(size_t t){
00281     void* allocated = Memory::malloc(t);
00282     return allocated;
00283   }
00284   
00286   template <class Card>
00287   forceinline void
00288   PartialSum<Card>::operator delete(void* p){
00289       Memory::free(p);
00290   }
00291 
00304   template <class Card>
00305   inline 
00306   PartialSum<Card>::PartialSum(int first,
00307                                int count, 
00308                                ViewArray<Card>& elements, 
00309                                bool up) {
00310     int i = 0;
00311     int j = 0;
00312     // we add three elements at the beginning and two at the end
00313     size  = count + 5;
00314     // memory allocation
00315     size_t sum_size = (size) * sizeof(int);
00316     size_t ds_size  = (size) * sizeof(int);
00317     size_t total    = sum_size + ds_size;
00318 
00319     mem = reinterpret_cast<char*> (Memory::malloc(total));
00320     sum = reinterpret_cast<int*> (mem);
00321     ds  = reinterpret_cast<int*> (mem + sum_size);
00322 
00323     for (int z = 0; z < size; z++) {
00324       sum[z] = 0;
00325       ds[z]  = 0;
00326     }
00327 
00328     /* 
00329      * firstValue and lastValue are sentinels
00330      * indicating whether an end of the sum has been reached
00331      *
00332      */
00333     firstValue = first - 3; 
00334     lastValue  = first + count + 1;
00335 
00336 
00337     // the first three elements
00338     for (i = 3; i--; ){
00339       sum[i] = i;
00340     }
00341 
00342     int shift  = count + 2;
00343     
00344     /*
00345      * copy the bounds into sum
00346      * optimization only those values being indeed 
00347      * variable bounds
00348      */
00349     for (i = 2; i < shift; i++){
00350       if (up) {
00351         sum[i + 1] = sum[i] + elements[i - 2].max();
00352       } else {
00353         sum[i + 1] = sum[i] + elements[i - 2].min();
00354       }
00355     }
00356     sum[i + 1] = sum[i] + 1;
00357     sum[i + 2] = sum[i + 1] + 1;
00358 
00359     
00360     // check for doublets
00361     i = count + 3;
00362     j = i + 1;
00363     for ( ; i > 0; ){
00364       while(sum[i] == sum[i - 1]) {
00365         ds[i] = j;
00366         i--;
00367       }
00368       ds[j] = i;
00369       i--;
00370       j = ds[j];
00371     }
00372     ds[j] = 0;
00373     // for the sake of having no seg fault
00374     ds[0] = 0;
00375   }
00376 
00380   template <class Card>
00381   forceinline int 
00382   PartialSum<Card>::sumup(int from, int to){
00383     if (from <= to) {
00384       return sum[to - firstValue] - sum[from - firstValue - 1];
00385     } else {
00386       return sum[to - firstValue - 1] - sum[from - firstValue];
00387     }
00388   }
00389 
00394   template <class Card>
00395   forceinline int 
00396   PartialSum<Card>::minValue(void){
00397     return firstValue + 3;
00398   }
00399 
00405   template <class Card>
00406   forceinline int 
00407   PartialSum<Card>::maxValue(void){
00408     return lastValue - 2;
00409   }
00410 
00411 
00417   template <class Card>
00418   forceinline int 
00419   PartialSum<Card>::skipNonNullElementsRight(int value) {
00420     value -= firstValue;
00421     return (ds[value] < value ? value : ds[value]) + firstValue;
00422   }
00423 
00429   template <class Card>
00430   forceinline int 
00431   PartialSum<Card>::skipNonNullElementsLeft(int value) {
00432     value -= firstValue;
00433     return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00434   }
00435 
00437   template <class Card>
00438   void
00439   PartialSum<Card>::print(void){
00440     std::cout << "----------\n";
00441     std::cout << "smallest elem = "<< minValue() << " - "
00442               << "largest  elem = "<< maxValue() << "\n";
00443     std::cout << "fsv: "<< firstValue <<" lsv: " << lastValue 
00444               << " size = "<< size << "\n";
00445     std::cout << "number of elements = "<< size - 5<<"\n";
00446     std::cout << "elements: ";
00447     for (int i = 3; i < size - 2; i++) {
00448       std::cout << sum[i] - sum[i-1] << " ";
00449     }
00450     std::cout <<"\n";
00451 
00452     std::cout << "sum: ";
00453     for (int i = 0; i < size; i++) {
00454       std::cout <<sum[i] << " ";
00455     }
00456     std::cout <<"\n";
00457     std::cout << "ds: ";
00458     for (int i = 0; i < size; i++) {
00459       std::cout <<sum[i] << " ";
00460     }
00461     std::cout <<"\n";
00462 
00463   }
00464 
00473   template <class Card>
00474   inline bool
00475   PartialSum<Card>::check_update_max(ViewArray<Card>& k){
00476     if (k.size() <= size - 5) {
00477       return true; 
00478     } else {
00479       for (int i = 3; i < size - 2; i++) {
00480         if ((sum[i] - sum[i - 1]) != k[i - 3].max()) {
00481           return true;
00482         }
00483       }
00484       return false;
00485     }
00486   }
00487 
00496   template <class Card>
00497   inline bool
00498   PartialSum<Card>::check_update_min(ViewArray<Card>& k){
00499     if (k.size() <= size - 5) {
00500       return true; 
00501     } else {
00502       for (int i = 3; i < size - 2; i++) {
00503         if ((sum[i] - sum[i - 1]) != k[i - 3].min()) {
00504           return true;
00505         }
00506       }
00507       return false;
00508     }
00509   }
00510   
00512   template <class Card>
00513   forceinline int
00514   PartialSum<Card>::getsize(void){
00515     return size;
00516   }
00517 
00518 
00529   class HallInfo {
00530   public:
00532     int bounds;   
00538     int t;
00546     int d;
00555     int h;
00560     int s;    
00565     int ps;
00572     int newBound; 
00573   };
00574 
00575 
00585 
00586   inline void
00587   pathset_ps(HallInfo hall[], int start, int end, int to) {
00588     int k, l;
00589     for (l=start; (k=l) != end; hall[k].ps=to) {
00590       l = hall[k].ps;
00591     }
00592   }
00593 
00595   inline void
00596   pathset_s(HallInfo hall[], int start, int end, int to) {
00597     int k, l;
00598     for (l=start; (k=l) != end; hall[k].s=to) {
00599       l = hall[k].s;
00600     }
00601   }
00602 
00604   inline void
00605   pathset_t(HallInfo hall[], int start, int end, int to) {
00606     int k, l;
00607     for (l=start; (k=l) != end; hall[k].t=to) {
00608       l = hall[k].t;
00609     }
00610   }
00611 
00613   inline void
00614   pathset_h(HallInfo hall[], int start, int end, int to) {
00615     int k, l;
00616     for (l=start; (k=l) != end; hall[k].h=to) {
00617       l = hall[k].h;
00618     }
00619   }
00621   
00629 
00630   forceinline int
00631   pathmin_h(const HallInfo hall[], int i) {
00632     while (hall[i].h < i)
00633       i = hall[i].h;
00634     return i;
00635   }
00637   forceinline int
00638   pathmin_t(const HallInfo hall[], int i) {
00639     while (hall[i].t < i)
00640       i = hall[i].t;
00641     return i;
00642   }
00644 
00651 
00652   forceinline int
00653   pathmax_h(const HallInfo hall[], int i) {
00654     while (hall[i].h > i)
00655       i = hall[i].h;
00656     return i;
00657   }
00658 
00659 
00661   forceinline int
00662   pathmax_t(const HallInfo hall[], int i) {
00663     while (hall[i].t > i) {
00664       i = hall[i].t;
00665     }
00666     return i;
00667   }
00668 
00670   forceinline int
00671   pathmax_s(const HallInfo hall[], int i) {
00672     while (hall[i].s > i)
00673       i = hall[i].s;
00674     return i;
00675   }
00676 
00678   forceinline int
00679   pathmax_ps(const HallInfo hall[], int i) {
00680     while (hall[i].ps > i)
00681       i = hall[i].ps;
00682     return i;
00683   }
00685 
00686 
00696   template <class Card>
00697   void 
00698   reduce_card(int cmin, int cmax, ViewArray<Card>& k) {
00699     if (cmin == cmax) {
00700       int idx = 0;
00701       while (k[idx].card() != cmax) {
00702         idx++;
00703       }
00704       k[0] = k[idx];
00705       k.size(1);
00706     } else {
00707 
00708       GECODE_AUTOARRAY(bool, zero, k.size());
00709       int ks = k.size();
00710       int zc = 0;
00711       for (int i = 0; i < ks; i++) {
00712         bool impossible  = ( (k[i].counter() == 0) &&
00713                              (k[i].card() < cmin ||
00714                               k[i].card() > cmax));
00715         
00716         if (impossible) {
00717           zero[i] = true;
00718           zc++;
00719         } else {
00720           zero[i] = false;
00721         }
00722       } 
00723 
00724       
00725       if (zero[ks - 1]) {
00726         int m = ks;
00727         while(zero[m - 1]) {
00728           m--;
00729           zc--;
00730         }
00731         k.size(m);
00732       }
00733 
00734       START_SIZE
00735       if (zc > 0) {
00736         int ks = k.size();
00737         // if there are still zero entries left
00738         for (int i = 0; i < ks; i++) {
00739           assert(0 <= i && i < ks);
00740           if  (zero[i]) {
00741             if (i == ks - 1) {
00742               break;
00743             }
00744             // this cardinality does not occur
00745             // remove it
00746             // we need the next non-null entry
00747             int j = i + 1;
00748             assert(0 <= j && j < ks);
00749             if (j < ks) {
00750               while (zero[j]) {
00751                 j++;
00752               }
00753             }
00754             if (j > ks - 1) {
00755               break;
00756             }
00757             k[i] = k[j];
00758             zero[j] = true;
00759           }
00760         }
00761         k.size(ks - zc);
00762       }
00763 
00764       END_SIZE
00765       assert(start_size == end_size + zc);
00766     }
00767     
00768     // validty check
00769     // for (int i = 1; i < k.size(); i++) {
00770 //       assert(k[i].card() > k[i - 1].card());
00771 //     }
00772   }
00773 
00774 }}}
00775 
00776 // STATISTICS: int-prop
00777