Generated on Fri Oct 19 11:25:10 2018 for Gecode by doxygen 1.6.3

int.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int.hh>
00035 
00036 namespace Gecode { namespace Int {
00037 
00038   forceinline bool
00039   IntVarImp::closer_min(int n) const {
00040     unsigned int l = static_cast<unsigned int>(n - dom.min());
00041     unsigned int r = static_cast<unsigned int>(dom.max() - n);
00042     return l < r;
00043   }
00044 
00045   int
00046   IntVarImp::med(void) const {
00047     // Computes the median
00048     if (fst() == NULL)
00049       return (dom.min()+dom.max())/2 - ((dom.min()+dom.max())%2 < 0 ? 1 : 0);
00050     unsigned int i = size() / 2;
00051     if (size() % 2 == 0)
00052       i--;
00053     const RangeList* p = NULL;
00054     const RangeList* c = fst();
00055     while (i >= c->width()) {
00056       i -= c->width();
00057       const RangeList* n=c->next(p); p=c; c=n;
00058     }
00059     return c->min() + static_cast<int>(i);
00060   }
00061 
00062   bool
00063   IntVarImp::in_full(int m) const {
00064     if (closer_min(m)) {
00065       const RangeList* p = NULL;
00066       const RangeList* c = fst();
00067       while (m > c->max()) {
00068         const RangeList* n=c->next(p); p=c; c=n;
00069       }
00070       return (m >= c->min());
00071     } else {
00072       const RangeList* n = NULL;
00073       const RangeList* c = lst();
00074       while (m < c->min()) {
00075         const RangeList* p=c->prev(n); n=c; c=p;
00076       }
00077       return (m <= c->max());
00078     }
00079   }
00080 
00081   /*
00082    * "Standard" tell operations
00083    *
00084    */
00085 
00086   ModEvent
00087   IntVarImp::lq_full(Space& home, int m) {
00088     assert((m >= dom.min()) && (m <= dom.max()));
00089     int old_max = dom.max();
00090     ModEvent me = ME_INT_BND;
00091     if (range()) { // Is already range...
00092       dom.max(m);
00093       if (assigned()) me = ME_INT_VAL;
00094     } else if (m < fst()->next(NULL)->min()) { // Becomes range...
00095       dom.max(std::min(m,fst()->max()));
00096       fst()->dispose(home,NULL,lst());
00097       fst(NULL); holes = 0;
00098       if (assigned()) me = ME_INT_VAL;
00099     } else { // Stays non-range...
00100       RangeList* n = NULL;
00101       RangeList* c = lst();
00102       unsigned int h = 0;
00103       while (m < c->min()) {
00104         RangeList* p = c->prev(n); c->fix(n);
00105         h += (c->min() - p->max() - 1);
00106         n=c; c=p;
00107       }
00108       holes -= h;
00109       int max_c = std::min(m,c->max());
00110       dom.max(max_c); c->max(max_c);
00111       if (c != lst()) {
00112         n->dispose(home,lst());
00113         c->next(n,NULL); lst(c);
00114       }
00115     }
00116     IntDelta d(dom.max()+1,old_max);
00117     return notify(home,me,d);
00118   }
00119 
00120   ModEvent
00121   IntVarImp::gq_full(Space& home, int m) {
00122     assert((m >= dom.min()) && (m <= dom.max()));
00123     int old_min = dom.min();
00124     ModEvent me = ME_INT_BND;
00125     if (range()) { // Is already range...
00126       dom.min(m);
00127       if (assigned()) me = ME_INT_VAL;
00128     } else if (m > lst()->prev(NULL)->max()) { // Becomes range...
00129       dom.min(std::max(m,lst()->min()));
00130       fst()->dispose(home,NULL,lst());
00131       fst(NULL); holes = 0;
00132       if (assigned()) me = ME_INT_VAL;
00133     } else { // Stays non-range...
00134       RangeList* p = NULL;
00135       RangeList* c = fst();
00136       unsigned int h = 0;
00137       while (m > c->max()) {
00138         RangeList* n = c->next(p); c->fix(n);
00139         h += (n->min() - c->max() - 1);
00140         p=c; c=n;
00141       }
00142       holes -= h;
00143       int min_c = std::max(m,c->min());
00144       dom.min(min_c); c->min(min_c);
00145       if (c != fst()) {
00146         fst()->dispose(home,p);
00147         c->prev(p,NULL); fst(c);
00148       }
00149     }
00150     IntDelta d(old_min,dom.min()-1);
00151     return notify(home,me,d);
00152   }
00153 
00154   ModEvent
00155   IntVarImp::eq_full(Space& home, int m) {
00156     dom.min(m); dom.max(m);
00157     if (!range()) {
00158       bool failed = false;
00159       RangeList* p = NULL;
00160       RangeList* c = fst();
00161       while (m > c->max()) {
00162         RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00163       }
00164       if (m < c->min())
00165         failed = true;
00166       while (c != NULL) {
00167         RangeList* n=c->next(p); c->fix(n); p=c; c=n;
00168       }
00169       assert(p == lst());
00170       fst()->dispose(home,p);
00171       fst(NULL); holes = 0;
00172       if (failed)
00173         return fail(home);
00174     }
00175     IntDelta d;
00176     return notify(home,ME_INT_VAL,d);
00177   }
00178 
00179   ModEvent
00180   IntVarImp::nq_full(Space& home, int m) {
00181     assert(!((m < dom.min()) || (m > dom.max())));
00182     ModEvent me = ME_INT_DOM;
00183     if (range()) {
00184       if ((m == dom.min()) && (m == dom.max()))
00185         return fail(home);
00186       if (m == dom.min()) {
00187         dom.min(m+1);
00188         me = assigned() ? ME_INT_VAL : ME_INT_BND;
00189       } else if (m == dom.max()) {
00190         dom.max(m-1);
00191         me = assigned() ? ME_INT_VAL : ME_INT_BND;
00192       } else {
00193         RangeList* f = new (home) RangeList(dom.min(),m-1);
00194         RangeList* l = new (home) RangeList(m+1,dom.max());
00195         f->prevnext(NULL,l);
00196         l->prevnext(f,NULL);
00197         fst(f); lst(l); holes = 1;
00198       }
00199     } else if (m < fst()->next(NULL)->min()) { // Concerns the first range...
00200       int f_max = fst()->max();
00201       if (m > f_max)
00202         return ME_INT_NONE;
00203       int f_min = dom.min();
00204       if ((m == f_min) && (m == f_max)) {
00205         RangeList* f_next = fst()->next(NULL);
00206         dom.min(f_next->min());
00207         if (f_next == lst()) { // Turns into range
00208           // Works as at the ends there are only NULL pointers
00209           fst()->dispose(home,f_next);
00210           fst(NULL); holes = 0;
00211           me = assigned() ? ME_INT_VAL : ME_INT_BND;
00212         } else { // Remains non-range
00213           f_next->prev(fst(),NULL);
00214           fst()->dispose(home); fst(f_next);
00215           holes -= dom.min() - f_min - 1;
00216           me = ME_INT_BND;
00217         }
00218       } else if (m == f_min) {
00219         dom.min(m+1); fst()->min(m+1);
00220         me = ME_INT_BND;
00221       } else if (m == f_max) {
00222         fst()->max(m-1); holes += 1;
00223       } else {
00224         // Create new hole
00225         RangeList* f = new (home) RangeList(f_min,m-1);
00226         f->prevnext(NULL,fst());
00227         fst()->min(m+1); fst()->prev(NULL,f);
00228         fst(f); holes += 1;
00229       }
00230     } else if (m > lst()->prev(NULL)->max()) { // Concerns the last range...
00231       int l_min = lst()->min();
00232       if (m < l_min)
00233         return ME_INT_NONE;
00234       int l_max = dom.max();
00235       if ((m == l_min) && (m == l_max)) {
00236         RangeList* l_prev = lst()->prev(NULL);
00237         dom.max(l_prev->max());
00238         if (l_prev == fst()) {
00239           // Turns into range
00240           l_prev->dispose(home,lst());
00241           fst(NULL); holes = 0;
00242           me = assigned() ? ME_INT_VAL : ME_INT_BND;
00243         } else { // Remains non-range
00244           l_prev->next(lst(),NULL);
00245           lst()->dispose(home); lst(l_prev);
00246           holes -= l_max - dom.max() - 1;
00247           me = ME_INT_BND;
00248         }
00249       } else if (m == l_max) {
00250         dom.max(m-1); lst()->max(m-1);
00251         me = ME_INT_BND;
00252       } else if (m == l_min) {
00253         lst()->min(m+1); holes += 1;
00254       } else { // Create new hole
00255         RangeList* l = new (home) RangeList(m+1,l_max);
00256         l->prevnext(lst(),NULL);
00257         lst()->max(m-1); lst()->next(NULL,l);
00258         lst(l); holes += 1;
00259       }
00260     } else { // Concerns element in the middle of the list of ranges
00261       RangeList* p;
00262       RangeList* c;
00263       RangeList* n;
00264       if (closer_min(m)) {
00265         assert(m > fst()->max());
00266         p = NULL;
00267         c = fst();
00268         do {
00269           n=c->next(p); p=c; c=n;
00270         } while (m > c->max());
00271         if (m < c->min())
00272           return ME_INT_NONE;
00273         n=c->next(p);
00274       } else {
00275         assert(m < lst()->min());
00276         n = NULL;
00277         c = lst();
00278         do {
00279           p=c->prev(n); n=c; c=p;
00280         } while (m < c->min());
00281         if (m > c->max())
00282           return ME_INT_NONE;
00283         p=c->prev(n);
00284       }
00285       assert((fst() != c) && (lst() != c));
00286       assert((m >= c->min()) && (m <= c->max()));
00287       holes += 1;
00288       int c_min = c->min();
00289       int c_max = c->max();
00290       if ((c_min == m) && (c_max == m)) {
00291         c->dispose(home);
00292         p->next(c,n); n->prev(c,p);
00293       } else if (c_min == m) {
00294         c->min(m+1);
00295       } else {
00296         c->max(m-1);
00297         if (c_max != m) {
00298           RangeList* l = new (home) RangeList(m+1,c_max);
00299           l->prevnext(c,n);
00300           c->next(n,l);
00301           n->prev(c,l);
00302         }
00303       }
00304     }
00305     IntDelta d(m,m);
00306     return notify(home,me,d);
00307   }
00308 
00309 
00310 
00311   /*
00312    * Copying variables
00313    *
00314    */
00315 
00316   forceinline
00317   IntVarImp::IntVarImp(Space& home, IntVarImp& x)
00318     : IntVarImpBase(home,x), dom(x.dom.min(),x.dom.max()) {
00319     holes = x.holes;
00320     if (holes) {
00321       int m = 1;
00322       // Compute length
00323       {
00324         RangeList* s_p = x.fst();
00325         RangeList* s_c = s_p->next(NULL);
00326         do {
00327           m++;
00328           RangeList* s_n = s_c->next(s_p); s_p=s_c; s_c=s_n;
00329         } while (s_c != NULL);
00330       }
00331       RangeList* d_c = home.alloc<RangeList>(m);
00332       fst(d_c); lst(d_c+m-1);
00333       d_c->min(x.fst()->min());
00334       d_c->max(x.fst()->max());
00335       d_c->prevnext(NULL,NULL);
00336       RangeList* s_p = x.fst();
00337       RangeList* s_c = s_p->next(NULL);
00338       do {
00339         RangeList* d_n = d_c + 1;
00340         d_c->next(NULL,d_n);
00341         d_n->prevnext(d_c,NULL);
00342         d_n->min(s_c->min()); d_n->max(s_c->max());
00343         d_c = d_n;
00344         RangeList* s_n=s_c->next(s_p); s_p=s_c; s_c=s_n;
00345       } while (s_c != NULL);
00346       d_c->next(NULL,NULL);
00347     } else {
00348       fst(NULL);
00349     }
00350   }
00351 
00352   IntVarImp*
00353   IntVarImp::perform_copy(Space& home) {
00354     return new (home) IntVarImp(home,*this);
00355   }
00356 
00357   /*
00358    * Dependencies
00359    *
00360    */
00361   void
00362   IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc,
00363                        bool schedule) {
00364     IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),schedule);
00365   }
00366 
00367   void
00368   IntVarImp::reschedule(Space& home, Propagator& p, PropCond pc) {
00369     IntVarImpBase::reschedule(home,p,pc,dom.min()==dom.max());
00370   }
00371 
00372   void
00373   IntVarImp::subscribe(Space& home, Advisor& a, bool fail) {
00374     IntVarImpBase::subscribe(home,a,dom.min()==dom.max(),fail);
00375   }
00376 
00377 }}
00378 
00379 // STATISTICS: int-var