Generated on Tue Apr 18 10:22:09 2017 for Gecode by doxygen 1.6.3

nogoods.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, 2013
00008  *
00009  *  Last modified:
00010  *     $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
00011  *     $Revision: 15137 $
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 #include <gecode/search/meta/nogoods.hh>
00039 
00040 namespace Gecode { namespace Search { namespace Meta {
00041 
00043   forceinline NGL*
00044   disposenext(NGL* ngl, Space& home, Propagator& p, bool c) {
00045     NGL* n = ngl->next();
00046     if (c)
00047       ngl->cancel(home,p);
00048     home.rfree(ngl,ngl->dispose(home));
00049     return n;
00050   }
00051 
00052   void
00053   NoNGL::subscribe(Space&, Propagator&) {
00054     GECODE_NEVER;
00055   }
00056   void
00057   NoNGL::cancel(Space&, Propagator&) {
00058     GECODE_NEVER;
00059   }
00060   void
00061   NoNGL::reschedule(Space&, Propagator&) {
00062     GECODE_NEVER;
00063   }
00064   NGL::Status
00065   NoNGL::status(const Space&) const {
00066     GECODE_NEVER;
00067     return NGL::NONE;
00068   }
00069   ExecStatus
00070   NoNGL::prune(Space&) {
00071     GECODE_NEVER;
00072     return ES_OK;
00073   }
00074   NGL*
00075   NoNGL::copy(Space&, bool) {
00076     GECODE_NEVER;
00077     return NULL;
00078   }
00079 
00080   Actor*
00081   NoGoodsProp::copy(Space& home, bool share) {
00082     return new (home) NoGoodsProp(home,share,*this);
00083   }
00084 
00085   PropCost
00086   NoGoodsProp::cost(const Space&, const ModEventDelta&) const {
00087     return PropCost::linear(PropCost::LO,n);
00088   }
00089 
00090   void
00091   NoGoodsProp::reschedule(Space& home) {
00092     root->reschedule(home,*this);
00093     NGL* l = root->next();
00094     while ((l != NULL) && l->leaf()) {
00095       l->reschedule(home,*this);
00096       l = l->next();
00097     }
00098     if (l != NULL)
00099       l->reschedule(home,*this);
00100   }
00101 
00102 
00103   ExecStatus
00104   NoGoodsProp::propagate(Space& home, const ModEventDelta&) {
00105   restart:
00106     // Start with checking the first literal
00107     switch (root->status(home)) {
00108     case NGL::FAILED:
00109       // All no-goods are dead, let dispose() clean up
00110       return home.ES_SUBSUMED(*this);
00111     case NGL::SUBSUMED:
00112       {
00113         NGL* l = disposenext(root,home,*this,true); n--;
00114         // Prune leaf-literals
00115         while ((l != NULL) && l->leaf()) {
00116           l->cancel(home,*this); n--;
00117           GECODE_ES_CHECK(l->prune(home));
00118           l = disposenext(l,home,*this,false);
00119         }
00120         root = l;
00121         // Is there anything left?
00122         if (l == NULL)
00123           return home.ES_SUBSUMED(*this);
00124         // Skip literal that already has a subscription
00125         l = l->next();
00126         // Create subscriptions for leafs
00127         while ((l != NULL) && l->leaf()) {
00128           l->subscribe(home,*this); n++;
00129           l = l->next();
00130         }
00131         // Create subscription for possible non-leaf literal
00132         if (l != NULL) {
00133           l->subscribe(home,*this); n++;
00134         }
00135         goto restart;
00136       }
00137     case NGL::NONE:
00138       break;
00139     default: GECODE_NEVER;
00140     }
00141 
00142     {
00143       NGL* p = root;
00144       NGL* l = p->next();
00145 
00146       // Check the leaves
00147       while ((l != NULL) && l->leaf()) {
00148         switch (l->status(home)) {
00149         case NGL::SUBSUMED:
00150           l = disposenext(l,home,*this,true); n--;
00151           p->next(l);
00152           GECODE_ES_CHECK(root->prune(home));
00153           if (root->status(home) == NGL::FAILED)
00154             return home.ES_SUBSUMED(*this);
00155           break;
00156         case NGL::FAILED:
00157           l = disposenext(l,home,*this,true); n--;
00158           p->next(l);
00159           break;
00160         case NGL::NONE:
00161           p = l; l = l->next();
00162           break;
00163         default: GECODE_NEVER;
00164         }
00165       }
00166 
00167       // Check the next subtree
00168       if (l != NULL) {
00169         switch (l->status(home)) {
00170         case NGL::FAILED:
00171           (void) disposenext(l,home,*this,true); n--;
00172           // Prune entire subtree
00173           p->next(NULL);
00174           break;
00175         case NGL::SUBSUMED:
00176           {
00177             // Unlink node
00178             l = disposenext(l,home,*this,true); n--;
00179             p->next(l);
00180             // Create subscriptions
00181             while ((l != NULL) && l->leaf()) {
00182               l->subscribe(home,*this); n++;
00183               l = l->next();
00184             }
00185             if (l != NULL) {
00186               l->subscribe(home,*this); n++;
00187             }
00188           }
00189           break;
00190         case NGL::NONE:
00191           break;
00192         default: GECODE_NEVER;
00193         }
00194       }
00195     }
00196     return ES_NOFIX;
00197   }
00198 
00199   size_t
00200   NoGoodsProp::dispose(Space& home) {
00201     if (home.failed()) {
00202       // This will be executed when one ngl returned true for notice()
00203       NGL* l = root;
00204       while (l != NULL) {
00205         NGL* t = l->next();
00206         (void) l->dispose(home);
00207         l = t;
00208       }
00209     } else if (root != NULL) {
00210       // This will be executed for subsumption
00211       NGL* l = disposenext(root,home,*this,true);
00212       while ((l != NULL) && l->leaf())
00213         l = disposenext(l,home,*this,true);
00214       if (l != NULL)
00215         l = disposenext(l,home,*this,true);
00216       while (l != NULL)
00217         l = disposenext(l,home,*this,false);
00218     }
00219     home.ignore(*this,AP_DISPOSE,true);
00220     (void) Propagator::dispose(home);
00221     return sizeof(*this);
00222   }
00223 
00224 }}}
00225 
00226 // STATISTICS: search-meta