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

imp.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2002
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00010  *     $Revision: 3188 $
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 #include "gecode/int.hh"
00023 
00024 #include "gecode/limits.hh"
00025 
00026 namespace Gecode { namespace Int {
00027 
00028   forceinline bool
00029   IntVarImp::closer_min(int n) const {
00030     unsigned int l = n - dom.min();
00031     unsigned int r = dom.max() - n;
00032     return l < r;
00033   }
00034 
00035   int
00036   IntVarImp::med(void) const {
00037     // Computes the median
00038     if (fst() == NULL)
00039       return (dom.min()+dom.max())/2;
00040     unsigned int i = size() / 2;
00041     const RangeList* p = NULL;
00042     const RangeList* c = fst();
00043     while (i >= c->width()) {
00044       i -= c->width(); 
00045       const RangeList* n=c->next(p); p=c; c=n;
00046     }
00047     return c->min() + static_cast<int>(i);
00048   }
00049 
00050   bool
00051   IntVarImp::in_full(int m) const {
00052     if (closer_min(m)) {
00053       const RangeList* p = NULL;
00054       const RangeList* c = fst();
00055       while (m > c->max()) {
00056         const RangeList* n=c->next(p); p=c; c=n;
00057       }
00058       return (m >= c->min());
00059     } else {
00060       const RangeList* n = NULL;
00061       const RangeList* c = lst();
00062       while (m < c->min()) {
00063         const RangeList* p=c->prev(n); n=c; c=p;
00064       }
00065       return (m <= c->max());
00066     }
00067   }
00068 
00069   /*
00070    * "Standard" tell operations
00071    *
00072    */
00073 
00074   void
00075   IntVarImp::lq_full(Space* home, int m) {
00076     assert((m >= dom.min()) && (m <= dom.max()));
00077     if (range()) { // Is already range...
00078       dom.max(m);
00079       if (assigned()) goto notify_val;
00080     } else if (m < fst()->next(NULL)->min()) { // Becomes range...
00081       dom.max(std::min(m,fst()->max()));
00082       fst()->dispose(home,NULL,lst());
00083       fst(NULL); holes = 0;
00084       if (assigned()) goto notify_val;
00085     } else { // Stays non-range...
00086       RangeList* n = NULL;  
00087       RangeList* c = lst();
00088       unsigned int h = 0;
00089       while (m < c->min()) {
00090         RangeList* p = c->prev(n); c->fix(n);
00091         h += (c->min() - p->max() - 1); 
00092         n=c; c=p;
00093       }
00094       holes -= h;
00095       int max_c = std::min(m,c->max());
00096       dom.max(max_c); c->max(max_c);
00097       if (c != lst()) {
00098         lst()->dispose(home,n);
00099         c->next(n,NULL); lst(c);
00100       }
00101     }
00102     notify(home,ME_INT_BND);
00103     return;
00104   notify_val:
00105     notify(home,ME_INT_VAL);
00106   }
00107 
00108   void
00109   IntVarImp::gq_full(Space* home, int m) {
00110     assert((m >= dom.min()) && (m <= dom.max()));
00111     if (range()) { // Is already range...
00112       dom.min(m);
00113       if (assigned()) goto notify_val;
00114     } else if (m > lst()->prev(NULL)->max()) { // Becomes range...
00115       dom.min(std::max(m,lst()->min()));
00116       fst()->dispose(home,NULL,lst());
00117       fst(NULL); holes = 0;
00118       if (assigned()) goto notify_val;
00119     } else { // Stays non-range...
00120       RangeList* p = NULL;
00121       RangeList* c = fst();
00122       unsigned int h = 0;
00123       while (m > c->max()) {
00124         RangeList* n = c->next(p); c->fix(n);
00125         h += (n->min() - c->max() - 1); 
00126         p=c; c=n;
00127       }
00128       holes -= h;
00129       int min_c = std::max(m,c->min());
00130       dom.min(min_c); c->min(min_c);
00131       if (c != fst()) {
00132         fst()->dispose(home,p);
00133         c->prev(p,NULL); fst(c);
00134       }
00135     }
00136     notify(home,ME_INT_BND);
00137     return;
00138   notify_val:
00139     notify(home,ME_INT_VAL);
00140   }
00141 
00142   void
00143   IntVarImp::eq_full(Space* home, int m) {
00144     if (!range()) {
00145       RangeList* p = NULL;
00146       RangeList* c = fst();
00147       while (m > c->max()) {
00148         RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00149       }
00150       if (m < c->min()) {
00151         dom.min(Limits::Int::int_max+1);
00152         return;
00153       }
00154       while (c != NULL) {
00155         RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00156       }
00157       assert(p == lst());
00158       fst()->dispose(home,p);
00159       fst(NULL); holes = 0;
00160     }
00161     dom.min(m); dom.max(m);
00162     notify(home,ME_INT_VAL);
00163   }
00164 
00165   ModEvent
00166   IntVarImp::nq_full(Space* home, int m) {
00167     assert(!((m < dom.min()) || (m > dom.max())));
00168     if (range()) {
00169       if ((m == dom.min()) && (m == dom.max()))
00170         return ME_INT_FAILED;
00171       if (m == dom.min()) {
00172         dom.min(m+1); goto notify_bnd_or_val;
00173       }
00174       if (m == dom.max()) {
00175         dom.max(m-1); goto notify_bnd_or_val;
00176       }
00177       RangeList* f = new (home) RangeList(dom.min(),m-1);
00178       RangeList* l = new (home) RangeList(m+1,dom.max());
00179       f->prevnext(NULL,l);
00180       l->prevnext(f,NULL);
00181       fst(f); lst(l); holes = 1;
00182     } else if (m < fst()->next(NULL)->min()) { // Concerns the first range...
00183       int f_max = fst()->max();
00184       if (m > f_max)
00185         return ME_INT_NONE;
00186       int f_min = dom.min();
00187       if ((m == f_min) && (m == f_max)) {
00188         RangeList* f_next = fst()->next(NULL);
00189         dom.min(f_next->min());
00190         if (f_next == lst()) { // Turns into range
00191           // Works as at the ends there are only NULL pointers
00192           fst()->dispose(home,f_next);
00193           fst(NULL); holes = 0;
00194           goto notify_bnd_or_val;
00195         } else { // Remains non-range
00196           f_next->prev(fst(),NULL);
00197           fst()->dispose(home); fst(f_next);
00198           holes -= dom.min() - f_min - 1;
00199           goto notify_bnd;
00200         }
00201       } else if (m == f_min) {
00202         dom.min(m+1); fst()->min(m+1);
00203         goto notify_bnd;
00204       } else if (m == f_max) {
00205         fst()->max(m-1); holes += 1;
00206       } else {
00207         // Create new hole
00208         RangeList* f = new (home) RangeList(f_min,m-1);
00209         f->prevnext(NULL,fst());
00210         fst()->min(m+1); fst()->prev(NULL,f);
00211         fst(f); holes += 1;
00212       }
00213     } else if (m > lst()->prev(NULL)->max()) { // Concerns the last range...
00214       int l_min = lst()->min();
00215       if (m < l_min)
00216         return ME_INT_NONE;
00217       int l_max = dom.max();
00218       if ((m == l_min) && (m == l_max)) {
00219         RangeList* l_prev = lst()->prev(NULL);
00220         dom.max(l_prev->max());
00221         if (l_prev == fst()) {
00222           // Turns into range
00223           l_prev->dispose(home,lst());
00224           fst(NULL); holes = 0;
00225           goto notify_bnd_or_val;
00226         } else { // Remains non-range
00227           l_prev->next(lst(),NULL);
00228           lst()->dispose(home); lst(l_prev);
00229           holes -= l_max - dom.max() - 1;
00230           goto notify_bnd;
00231         }
00232       } else if (m == l_max) {
00233         dom.max(m-1); lst()->max(m-1);
00234         goto notify_bnd;
00235       } else if (m == l_min) {
00236         lst()->min(m+1); holes += 1;
00237       } else { // Create new hole
00238         RangeList* l = new (home) RangeList(m+1,l_max);
00239         l->prevnext(lst(),NULL);
00240         lst()->max(m-1); lst()->next(NULL,l);
00241         lst(l); holes += 1;
00242       }
00243     } else { // Concerns element in the middle of the list of ranges
00244       RangeList* p;
00245       RangeList* c;
00246       RangeList* n;
00247       if (closer_min(m)) {
00248         assert(m > fst()->max());
00249         p = NULL;
00250         c = fst();
00251         do { 
00252           n=c->next(p); p=c; c=n;
00253         } while (m > c->max());
00254         if (m < c->min())
00255           return ME_INT_NONE;
00256         n=c->next(p);
00257       } else {
00258         assert(m < lst()->min());
00259         n = NULL;
00260         c = lst();
00261         do { 
00262           p=c->prev(n); n=c; c=p;
00263         } while (m < c->min());
00264         if (m > c->max())
00265           return ME_INT_NONE;
00266         p=c->prev(n);
00267       }
00268       assert((fst() != c) && (lst() != c));
00269       assert((m >= c->min()) && (m <= c->max()));
00270       holes += 1;
00271       int c_min = c->min();
00272       int c_max = c->max();
00273       if ((c_min == m) && (c_max == m)) {
00274         c->dispose(home);
00275         p->next(c,n); n->prev(c,p);
00276       } else if (c_min == m) {
00277         c->min(m+1);
00278       } else {
00279         c->max(m-1);
00280         if (c_max != m) {
00281           RangeList* l = new (home) RangeList(m+1,c_max);
00282           l->prevnext(c,n);
00283           c->next(n,l);
00284           n->prev(c,l);
00285         }
00286       }
00287     }
00288     notify(home,ME_INT_DOM);
00289     return ME_INT_DOM;
00290   notify_bnd_or_val:
00291     if (assigned()) {
00292       notify(home,ME_INT_VAL);
00293       return ME_INT_VAL;
00294     }
00295   notify_bnd:
00296     notify(home,ME_INT_BND);
00297     return ME_INT_BND;
00298   }
00299 
00300 
00301 
00302   /*
00303    * Copying variables
00304    *
00305    */
00306 
00307   forceinline
00308   IntVarImp::IntVarImp(Space* home, bool share, IntVarImp& x)
00309     : Variable<VTI_INT,PC_INT_DOM>(home,share,x),
00310       dom(x.dom.min(),x.dom.max()), holes(x.holes) {
00311     if (holes) {
00312       int m = 1;
00313       // Compute length
00314       {
00315         RangeList* s_p = x.fst();
00316         RangeList* s_c = s_p->next(NULL);
00317         do {
00318           m++;
00319           RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n;
00320         } while (s_c != NULL);
00321       }
00322       RangeList* d_c =
00323         reinterpret_cast<RangeList*>(home->alloc(m*sizeof(RangeList)));
00324       fst(d_c); lst(d_c+m-1);
00325       d_c->min(x.fst()->min()); 
00326       d_c->max(x.fst()->max());
00327       d_c->prevnext(NULL,NULL);
00328       RangeList* s_p = x.fst();
00329       RangeList* s_c = s_p->next(NULL);
00330       do {
00331         RangeList* d_n = d_c + 1;
00332         d_c->next(NULL,d_n); 
00333         d_n->prevnext(d_c,NULL);
00334         d_n->min(s_c->min()); d_n->max(s_c->max());
00335         d_c = d_n;
00336         RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n;
00337       } while (s_c != NULL);
00338       d_c->next(NULL,NULL);
00339     } else {
00340       fst(NULL);
00341     }
00342   }
00343 
00344   IntVarImp*
00345   IntVarImp::perform_copy(Space* home, bool share) {
00346     return new (home) IntVarImp(home,share,*this);
00347   }
00348 
00349 
00350 
00351 
00352   /*
00353    * Integer variable modification board
00354    *
00355    */
00356 
00357   forceinline
00358   IntVarImp::Processor::Processor(void) {
00359     // Combination of modification events
00360     mec(ME_INT_BND,  ME_INT_DOM,  ME_INT_BND);
00361     // Mapping between modification events and propagation conditions
00362     mepc(ME_INT_BND, PC_INT_BND);
00363     mepc(ME_INT_BND, PC_INT_DOM);
00364     mepc(ME_INT_DOM, PC_INT_DOM);
00365     // Transfer to kernel
00366     enter();
00367   }
00368 
00369   IntVarImp::Processor IntVarImp::ivp;
00370 
00371 
00372 
00373   /*
00374    * Subscribing to variables
00375    *
00376    */
00377 
00378   void
00379   IntVarImp::subscribe(Space* home, Propagator* p, PropCond pc) {
00380     Variable<VTI_INT,PC_INT_DOM>::subscribe(home,p,pc,
00381                                             dom.min()==dom.max(), ME_INT_BND);
00382   }
00383 
00384 }}
00385 
00386 
00387 
00388 
00389 
00390 // STATISTICS: int-var
00391