Generated on Wed Jan 4 17:49:10 2006 for Gecode by doxygen 1.4.6

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: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
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 
00023 namespace Gecode { namespace Int { namespace GCC {
00024 
00026 
00027 
00031   class Rank {
00032   public:
00037     int min;
00042     int max;
00043   };
00044 
00052   template <class View>
00053   class MaxInc {
00054   protected:
00055     ViewArray<View> x;
00056   public:
00057     MaxInc(const ViewArray<View>& x0) : x(x0) {}
00058     forceinline bool
00059     operator()(const int i, const int j) {
00060       return x[i].max() < x[j].max();
00061     }
00062   };
00063 
00071   template <class View>
00072   class MinInc {
00073   protected:
00074     ViewArray<View> x;
00075   public:
00076     MinInc(const ViewArray<View>& x0) : x(x0) {}
00077     forceinline bool
00078     operator()(const int i, const int j) {
00079       return x[i].min() < x[j].min();
00080     }
00081   };
00082 
00083 
00089   template <class Card>
00090   class PartialSum {
00091   private:
00093     char* mem;
00094     // sum[i] contains the partial sum from 0 to i
00095     int* sum;  
00100     int* ds;   
00102     int size;
00103   public:    
00105 
00106     PartialSum( int, int, Card& , bool);
00107     ~PartialSum(void);
00109 
00110 
00111     int firstValue;
00112     int lastValue;
00113     int sumup(int, int);
00114     int minValue(void);
00115     int maxValue(void);
00116     int skipNonNullElementsRight(int);
00117     int skipNonNullElementsLeft(int);
00118     void* operator new(size_t s);
00119     void operator delete(void* p);
00120     void print(void);
00121     bool check_update_max(Card& k);
00122     bool check_update_min(Card& k);
00123     int getsize(void);
00125   };
00126 
00127   template <class Card>
00128   forceinline 
00129   PartialSum<Card>::~PartialSum(void){
00130     assert(mem != NULL);
00131     Memory::free(mem);
00132   }
00133 
00134   template <class Card>
00135   forceinline void*
00136   PartialSum<Card>::operator new(size_t t){
00137     void* allocated = Memory::malloc(t);
00138     return allocated;
00139   }
00140   
00141   template <class Card>
00142   forceinline void
00143   PartialSum<Card>::operator delete(void* p){
00144       Memory::free(p);
00145   }
00146 
00156   template <class Card>
00157   forceinline 
00158   PartialSum<Card>::PartialSum(int first,
00159                                int count, 
00160                                Card& elements, 
00161                                bool up) {
00162     int i = 0;
00163     int j = 0;
00164     // for the partial sum we add 3 elements at the beginning
00165     // and two at the end
00166     size  = count + 5;
00167     // memory allocation
00168     size_t sum_size = (size) * sizeof(int);
00169     size_t ds_size  = (size) * sizeof(int);
00170     size_t total    = sum_size + ds_size;
00171 
00172     mem = reinterpret_cast<char*> (Memory::malloc(total));
00173     sum = reinterpret_cast<int*> (mem);
00174     ds  = reinterpret_cast<int*> (mem + sum_size);
00175 
00176     for (int z = 0; z < size; z++) {
00177       sum[z] = 0;
00178       ds[z]  = 0;
00179     }
00180 
00181     /* 
00182      * firstValue and lastValue are sentinels
00183      * indicating whether an end of the sum has been reached
00184      *
00185      */
00186     // we added three elements at the beginning
00187     firstValue = first - 3; 
00188     lastValue  = first + count + 1;
00189 
00190 
00191     // the first three elements
00192     for (i = 3; i--; ){
00193       sum[i] = i;
00194     }
00195 
00196     int shift  = count + 2;
00197     
00198     // copy the bounds into sum
00199     // optimization only those values being indeed variable bounds
00200     for (i = 2; i < shift; i++){
00201       if (up) {
00202         sum[i + 1] = sum[i] + elements[i - 2].max();
00203       } else {
00204         sum[i + 1] = sum[i] + elements[i - 2].min();
00205       }
00206     }
00207     sum[i + 1] = sum[i] + 1;
00208     sum[i + 2] = sum[i + 1] + 1;
00209 
00210     
00211     // check for doublets
00212     i = count + 3;
00213     j = i + 1;
00214     for ( ; i > 0; ){
00215       while(sum[i] == sum[i - 1]) {
00216         ds[i] = j;
00217         i--;
00218       }
00219       ds[j] = i;
00220       i--;
00221       j = ds[j];
00222     }
00223     ds[j] = 0;
00224     // just for the sake of having no seg fault
00225     ds[0] = 0;
00226   }
00227 
00231   template <class Card>
00232   forceinline int 
00233   PartialSum<Card>::sumup(int from, int to){
00234     int result = 0;
00235     if (from <= to) {
00236       result = sum[to - firstValue] - sum[from - firstValue - 1];
00237     }
00238     else {
00239       result = sum[to - firstValue - 1] - sum[from - firstValue];
00240     }
00241     return result;
00242   }
00243 
00249   template <class Card>
00250   forceinline int 
00251   PartialSum<Card>::minValue(void){
00252     return firstValue + 3;
00253   }
00254 
00261   template <class Card>
00262   forceinline int 
00263   PartialSum<Card>::maxValue(void){
00264     return lastValue - 2;
00265   }
00266 
00267 
00272   template <class Card>
00273   forceinline int 
00274   PartialSum<Card>::skipNonNullElementsRight(int value) {
00275     value -= firstValue;
00276     return (ds[value] < value ? value : ds[value]) + firstValue;
00277   }
00278 
00279   template <class Card>
00280   forceinline int 
00281   PartialSum<Card>::skipNonNullElementsLeft(int value) {
00282     value -= firstValue;
00283     return (ds[value] > value ? ds[ds[value]] : value) + firstValue;
00284   }
00285 
00287   template <class Card>
00288   forceinline void
00289   PartialSum<Card>::print(void){
00290     std::cout << "fsv: "<< firstValue <<" lsv: " << lastValue 
00291               << " size = "<< size << "\n";
00292     std::cout << "number of elements = "<< size - 5<<"\n";
00293     std::cout << "elements: ";
00294     for (int i = 3; i < size - 2; i++) {
00295       std::cout << sum[i] - sum[i-1] << " ";
00296     }
00297     std::cout <<"\n";
00298 
00299     std::cout << "sum: ";
00300     for (int i = 0; i < size; i++) {
00301       std::cout <<sum[i] << " ";
00302     }
00303     std::cout <<"\n";
00304     std::cout << "ds: ";
00305     for (int i = 0; i < size; i++) {
00306       std::cout <<sum[i] << " ";
00307     }
00308     std::cout <<"\n";
00309 
00310   }
00311 
00312   template <class Card>
00313   forceinline bool
00314   PartialSum<Card>::check_update_max(Card& k){
00315     if (k.size() <= size - 5) {
00316       return true; 
00317     } else {
00318       for (int i = 3; i < size - 2; i++) {
00319         if ((sum[i] - sum[i - 1]) != k[i - 3].max()) {
00320           return true;
00321         }
00322       }
00323       return false;
00324     }
00325   }
00326 
00327   template <class Card>
00328   forceinline bool
00329   PartialSum<Card>::check_update_min(Card& k){
00330     if (k.size() <= size - 5) {
00331       return true; 
00332     } else {
00333       for (int i = 3; i < size - 2; i++) {
00334         if ((sum[i] - sum[i - 1]) != k[i - 3].min()) {
00335           return true;
00336         }
00337       }
00338       return false;
00339     }
00340   }
00341   
00342   template <class Card>
00343   forceinline int
00344   PartialSum<Card>::getsize(void){
00345     return size;
00346   }
00347 
00348 
00359   class HallInfo {
00360   public:
00362     int bounds;   
00368     int t;
00376     int d;
00385     int h;
00390     int s;    
00395     int ps;
00402     int newBound; 
00403   };
00404 
00405 
00415 
00416   inline void
00417   pathset_ps(HallInfo hall[], int start, int end, int to) {
00418     int k = 0;
00419     int l = start;
00420     for ( ; (k = l) != end; hall[k].ps = to) {
00421       l = hall[k].ps;
00422 
00423     }
00424   }
00426   inline void
00427   pathset_s(HallInfo hall[], int start, int end, int to) {
00428     int k = 0;
00429     int l = start;
00430     for ( ; (k = l) != end; hall[k].s = to) {
00431       l = hall[k].s;
00432     }
00433   }
00434 
00436   inline void
00437   pathset_t(HallInfo hall[], int start, int end, int to) {
00438     int k = 0;
00439     int l = start;
00440     for ( ; (k = l) != end; hall[k].t = to) {
00441       l = hall[k].t;
00442     }
00443   }
00444 
00446   inline void
00447   pathset_h(HallInfo hall[], int start, int end, int to) {
00448     int k = 0;
00449     int l = start;
00450     for ( ; (k = l) != end; hall[k].h = to) {
00451       l = hall[k].h;
00452     }
00453   }
00455   
00463 
00464   forceinline int
00465   pathmin_h(const HallInfo hall[], int i) {
00466     while (hall[i].h < i)
00467       i = hall[i].h;
00468     return i;
00469   }
00471   forceinline int
00472   pathmin_t(const HallInfo hall[], int i) {
00473     while (hall[i].t < i)
00474       i = hall[i].t;
00475     return i;
00476   }
00478 
00485 
00486   forceinline int
00487   pathmax_h(const HallInfo hall[], int i) {
00488     while (hall[i].h > i)
00489       i = hall[i].h;
00490     return i;
00491   }
00492 
00493 
00495   forceinline int
00496   pathmax_t(const HallInfo hall[], int i) {
00497     while (hall[i].t > i)
00498       i = hall[i].t;
00499     return i;
00500   }
00501 
00503   forceinline int
00504   pathmax_s(const HallInfo hall[], int i) {
00505     while (hall[i].s > i)
00506       i = hall[i].s;
00507     return i;
00508   }
00509 
00511   forceinline int
00512   pathmax_ps(const HallInfo hall[], int i) {
00513     while (hall[i].ps > i)
00514       i = hall[i].ps;
00515     return i;
00516   }
00518 
00519 
00529   template <class Card>
00530   void reduce_card(int cmin, int cmax, Card& k) {
00531 
00532     if (cmin == cmax) {
00533       int idx = 0;
00534       while (k[idx].card() != cmax) {
00535         idx++;
00536       }
00537       k[0] = k[idx];
00538       k.size(1);
00539     } else {
00540 
00541       GECODE_AUTOARRAY(bool, zero, k.size());
00542       int ks = k.size();
00543       int zc = 0;
00544       for (int i = 0; i < ks; i++) {
00545         bool impossible  = ( (k[i].counter() == 0) &&
00546                              (k[i].card() < cmin ||
00547                               k[i].card() > cmax));
00548         
00549         if (impossible) {
00550           zero[i] = true;
00551           zc++;
00552         } else {
00553           zero[i] = false;
00554         }
00555       }      
00556 
00557       if (zero[ks - 1]) {
00558         int m = ks;
00559         while(zero[m - 1]) {
00560           m--;
00561           zc--;
00562         }
00563         k.size(m);
00564       }
00565 
00566       int start_size = k.size();
00567       if (zc > 0) {
00568         int ks = k.size();
00569         // if there are still zero entries left
00570         for (int i = 0; i < ks; i++) {
00571           assert(0 <= i && i < ks);
00572           if  (zero[i]) {
00573             if (i == ks - 1) {
00574               break;
00575             }
00576             // this cardinality does not occur
00577             // remove it
00578             // we need the next non-null entry
00579             int j = i + 1;
00580             assert(0 <= j && j < ks);
00581             if (j < ks) {
00582               while (zero[j]) {
00583                 j++;
00584               }
00585             }
00586             if (j > ks - 1) {
00587               break;
00588             }
00589             k[i] = k[j];
00590             zero[j] = true;
00591           }
00592         }
00593         k.size(ks - zc);
00594       }
00595 
00596 
00597       int end_size = k.size();
00598       assert(start_size == end_size + zc);
00599     }
00600     
00601     // validty check
00602 //     for (int i = 1; i < k.size(); i++) {
00603 //       assert(k[i].card() > k[i - 1].card());
00604 //     }
00605   }
00606 
00607 }}}
00608 
00609 // STATISTICS: int-prop
00610