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

man.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   ManProp<Box>::ManProp(Home home, Box* b, int n)
00039     : Base<Box>(home, b, n) {}
00040 
00041   template<class Box>
00042   inline ExecStatus
00043   ManProp<Box>::post(Home home, Box* b, int n) {
00044     if (n > 1)
00045       (void) new (home) ManProp<Box>(home,b,n);
00046     return ES_OK;
00047   }
00048 
00049   template<class Box>
00050   forceinline size_t
00051   ManProp<Box>::dispose(Space& home) {
00052     (void) Base<Box>::dispose(home);
00053     return sizeof(*this);
00054   }
00055 
00056 
00057   template<class Box>
00058   forceinline
00059   ManProp<Box>::ManProp(Space& home, ManProp<Box>& p)
00060     : Base<Box>(home, p, p.n) {}
00061 
00062   template<class Box>
00063   Actor*
00064   ManProp<Box>::copy(Space& home) {
00065     return new (home) ManProp<Box>(home,*this);
00066   }
00067 
00068   template<class Box>
00069   ExecStatus
00070   ManProp<Box>::propagate(Space& home, const ModEventDelta&) {
00071     Region r;
00072 
00073     // Number of disjoint boxes
00074     int* db = r.alloc<int>(n);
00075     for (int i=0; i<n; i++)
00076       db[i] = n-1;
00077 
00078     // Number of boxes to be eliminated
00079     int e = 0;
00080 
00081     for (int i=0; i<n; i++)
00082       for (int j=0; j<i; j++)
00083         if (b[i].nooverlap(b[j])) {
00084           assert(db[i] > 0); assert(db[j] > 0);
00085           if (--db[i] == 0) e++;
00086           if (--db[j] == 0) e++;
00087           continue;
00088         } else {
00089           GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
00090         }
00091 
00092     if (e == n)
00093       return home.ES_SUBSUMED(*this);
00094 
00095     {
00096       int i = n-1;
00097       while (e > 0) {
00098         // Eliminate boxes that do not overlap
00099         while (db[i] > 0)
00100           i--;
00101         b[i].cancel(home, *this);
00102         b[i] = b[--n];
00103         e--; i--;
00104       }
00105       if (n < 2)
00106         return home.ES_SUBSUMED(*this);
00107     }
00108 
00109     return ES_NOFIX;
00110   }
00111 
00112 }}}
00113 
00114 // STATISTICS: int-prop
00115