Generated on Thu Mar 22 10:39:40 2012 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  *  Last modified:
00010  *     $Date: 2011-07-13 16:42:33 +0200 (Wed, 13 Jul 2011) $ by $Author: schulte $
00011  *     $Revision: 12191 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Int { namespace NoOverlap {
00039 
00040   template<class Dim, int d>
00041   forceinline
00042   OptProp<Dim,d>::OptProp(Home home, OptBox<Dim,d>* b, int n, int m0)
00043     : Base<OptBox<Dim,d> >(home,b,n), m(m0) {
00044     for (int i=m; i--; )
00045       b[n+i].subscribe(home, *this);
00046   }
00047 
00048   template<class Dim, int d>
00049   ExecStatus
00050   OptProp<Dim,d>::post(Home home, OptBox<Dim,d>* b, int n) {
00051     // Partition into mandatory and optional boxes
00052     if (n > 1) {
00053       int p = Base<OptBox<Dim,d> >::partition(b, 0, n);
00054       (void) new (home) OptProp<Dim,d>(home,b,p,n-p);
00055     }
00056     return ES_OK;
00057   }
00058 
00059   template<class Dim, int d>
00060   forceinline size_t 
00061   OptProp<Dim,d>::dispose(Space& home) {
00062     for (int i=m; i--; )
00063       b[n+i].cancel(home, *this);
00064     (void) Base<OptBox<Dim,d> >::dispose(home);
00065     return sizeof(*this);
00066   }
00067 
00068 
00069   template<class Dim, int d>
00070   forceinline
00071   OptProp<Dim,d>::OptProp(Space& home, bool shared, OptProp<Dim,d>& p) 
00072     : Base<OptBox<Dim,d> >(home, shared, p, p.n + p.m), m(p.m) {}
00073 
00074   template<class Dim, int d>
00075   Actor* 
00076   OptProp<Dim,d>::copy(Space& home, bool share) {
00077     return new (home) OptProp<Dim,d>(home,share,*this);
00078   }
00079 
00080   template<class Dim, int d>
00081   ExecStatus 
00082   OptProp<Dim,d>::propagate(Space& home, const ModEventDelta& med) {
00083     Region r(home);
00084 
00085     if (BoolView::me(med) == ME_BOOL_VAL) {
00086       // Eliminate excluded boxes
00087       for (int i=m; i--; )
00088         if (b[n+i].excluded()) {
00089           b[n+i].cancel(home,*this);
00090           b[n+i] = b[n+(--m)];
00091         }
00092       // Reconsider optional boxes
00093       if (m > 0) {
00094         int p = Base<OptBox<Dim,d> >::partition(b+n, 0, m);
00095         n += p; m -= p;
00096       }
00097     }
00098 
00099     // Number of disjoint boxes
00100     int* db = r.alloc<int>(n);
00101     for (int i=n; i--; )
00102       db[i] = n-1;
00103 
00104     // Number of boxes to be eliminated
00105     int e = 0;
00106     for (int i=n; i--; ) {
00107       assert(b[i].mandatory());
00108       for (int j=i; j--; ) 
00109         if (b[i].nooverlap(b[j])) {
00110           assert(db[i] > 0); assert(db[j] > 0);
00111           if (--db[i] == 0) e++;
00112           if (--db[j] == 0) e++;
00113           continue;
00114         } else {
00115           GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
00116         }
00117     }
00118 
00119     if (m == 0) {
00120       if (e == n)
00121         return home.ES_SUBSUMED(*this);
00122       int i = n-1;
00123       while (e > 0) {
00124         // Eliminate boxes that do not overlap
00125         while (db[i] > 0)
00126           i--;
00127         b[i].cancel(home, *this);
00128         b[i] = b[--n]; b[n] = b[n+m];
00129         e--; i--;
00130       }
00131       if (n < 2)
00132         return home.ES_SUBSUMED(*this);
00133     }
00134 
00135     // Check whether some optional boxes must be excluded
00136     for (int i=m; i--; ) {
00137       assert(b[n+i].optional());
00138       for (int j=n; j--; )
00139         if (b[n+i].overlap(b[j])) {
00140           GECODE_ES_CHECK(b[n+i].exclude(home));
00141           b[n+i].cancel(home,*this);
00142           b[n+i] = b[n+(--m)];
00143           break;
00144         }
00145     }
00146 
00147     return ES_NOFIX;
00148   }
00149 
00150 }}}
00151 
00152 // STATISTICS: int-prop
00153