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

opt.hpp

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, 2011
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 namespace Gecode { namespace Int { namespace NoOverlap {
00035 
00036   template<class Box>
00037   forceinline
00038   OptProp<Box>::OptProp(Home home, Box* b, int n, int m0)
00039     : Base<Box>(home,b,n), m(m0) {
00040     for (int i=0; i<m; i++)
00041       b[n+i].subscribe(home, *this);
00042   }
00043 
00044   template<class Box>
00045   ExecStatus
00046   OptProp<Box>::post(Home home, Box* b, int n) {
00047     // Partition into mandatory and optional boxes
00048     if (n > 1) {
00049       int p = Base<Box>::partition(b, 0, n);
00050       (void) new (home) OptProp<Box>(home,b,p,n-p);
00051     }
00052     return ES_OK;
00053   }
00054 
00055   template<class Box>
00056   forceinline size_t
00057   OptProp<Box>::dispose(Space& home) {
00058     for (int i=0; i<m; i++)
00059       b[n+i].cancel(home, *this);
00060     (void) Base<Box>::dispose(home);
00061     return sizeof(*this);
00062   }
00063 
00064 
00065   template<class Box>
00066   forceinline
00067   OptProp<Box>::OptProp(Space& home, OptProp<Box>& p)
00068     : Base<Box>(home, p, p.n + p.m), m(p.m) {}
00069 
00070   template<class Box>
00071   Actor*
00072   OptProp<Box>::copy(Space& home) {
00073     return new (home) OptProp<Box>(home,*this);
00074   }
00075 
00076   template<class Box>
00077   ExecStatus
00078   OptProp<Box>::propagate(Space& home, const ModEventDelta& med) {
00079     Region r;
00080 
00081     if (BoolView::me(med) == ME_BOOL_VAL) {
00082       // Eliminate excluded boxes
00083       for (int i=m; i--; )
00084         if (b[n+i].excluded()) {
00085           b[n+i].cancel(home,*this);
00086           b[n+i] = b[n+(--m)];
00087         }
00088       // Reconsider optional boxes
00089       if (m > 0) {
00090         int p = Base<Box>::partition(b+n, 0, m);
00091         n += p; m -= p;
00092       }
00093     }
00094 
00095     // Number of disjoint boxes
00096     int* db = r.alloc<int>(n);
00097     for (int i=0; i<n; i++)
00098       db[i] = n-1;
00099 
00100     // Number of boxes to be eliminated
00101     int e = 0;
00102     for (int i=0; i<n; i++) {
00103       assert(b[i].mandatory());
00104       for (int j=0; j<i; j++)
00105         if (b[i].nooverlap(b[j])) {
00106           assert(db[i] > 0); assert(db[j] > 0);
00107           if (--db[i] == 0) e++;
00108           if (--db[j] == 0) e++;
00109           continue;
00110         } else {
00111           GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
00112         }
00113     }
00114 
00115     if (m == 0) {
00116       if (e == n)
00117         return home.ES_SUBSUMED(*this);
00118       int i = n-1;
00119       while (e > 0) {
00120         // Eliminate boxes that do not overlap
00121         while (db[i] > 0)
00122           i--;
00123         b[i].cancel(home, *this);
00124         b[i] = b[--n]; b[n] = b[n+m];
00125         e--; i--;
00126       }
00127       if (n < 2)
00128         return home.ES_SUBSUMED(*this);
00129     }
00130 
00131     // Check whether some optional boxes must be excluded
00132     for (int i=m; i--; ) {
00133       if (b[n+i].optional()) {
00134         for (int j=n; j--; )
00135           if (b[n+i].overlap(b[j])) {
00136             GECODE_ES_CHECK(b[n+i].exclude(home));
00137             b[n+i].cancel(home,*this);
00138             b[n+i] = b[n+(--m)];
00139             break;
00140           }
00141       } else {
00142         // This might be the case if the same Boolean view occurs
00143         // several times and has already been excluded
00144         assert(b[n+i].excluded());
00145         b[n+i].cancel(home,*this);
00146         b[n+i] = b[n+(--m)];
00147       }
00148     }
00149 
00150     return ES_NOFIX;
00151   }
00152 
00153 }}}
00154 
00155 // STATISTICS: int-prop
00156