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

argmax.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, 2015
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/rel.hh>
00035 
00036 namespace Gecode { namespace Int { namespace Arithmetic {
00037 
00038   template<class VA, class VB, bool tiebreak>
00039   forceinline
00040   ArgMax<VA,VB,tiebreak>::ArgMax(Home home, IdxViewArray<VA>& x0, VB y0)
00041     : Propagator(home), x(x0), y(y0) {
00042     x.subscribe(home,*this,PC_INT_BND);
00043     y.subscribe(home,*this,PC_INT_DOM);
00044   }
00045 
00046   template<class VA, class VB, bool tiebreak>
00047   ExecStatus
00048   ArgMax<VA,VB,tiebreak>::post(Home home, IdxViewArray<VA>& x, VB y) {
00049     assert(x.size() > 0);
00050     if (x.size() == 1) {
00051       GECODE_ME_CHECK(y.eq(home,x[0].idx));
00052     } else if (y.assigned()) {
00053       int max=0;
00054       while (x[max].idx < y.val())
00055         max++;
00056       assert(x[max].idx == y.val());
00057       if (tiebreak)
00058         for (int i=0; i<max; i++)
00059           GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home,
00060                                                 x[i].view,x[max].view)));
00061       else
00062         for (int i=0; i<max; i++)
00063           GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
00064                                                 x[i].view,x[max].view)));
00065       for (int i=max+1; i<x.size(); i++)
00066         GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
00067                                               x[i].view,x[max].view)));
00068     } else {
00069       (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
00070     }
00071     return ES_OK;
00072   }
00073 
00074   template<class VA, class VB, bool tiebreak>
00075   forceinline
00076   ArgMax<VA,VB,tiebreak>::ArgMax(Space& home, ArgMax<VA,VB,tiebreak>& p)
00077     : Propagator(home,p) {
00078     x.update(home,p.x);
00079     y.update(home,p.y);
00080   }
00081 
00082   template<class VA, class VB, bool tiebreak>
00083   Actor*
00084   ArgMax<VA,VB,tiebreak>::copy(Space& home) {
00085     return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
00086   }
00087 
00088   template<class VA, class VB, bool tiebreak>
00089   PropCost
00090   ArgMax<VA,VB,tiebreak>::cost(const Space&, const ModEventDelta&) const {
00091     return PropCost::linear(PropCost::LO,x.size()+1);
00092   }
00093 
00094   template<class VA, class VB, bool tiebreak>
00095   void
00096   ArgMax<VA,VB,tiebreak>::reschedule(Space& home) {
00097     x.reschedule(home,*this,PC_INT_BND);
00098     y.reschedule(home,*this,PC_INT_DOM);
00099   }
00100 
00101   template<class VA, class VB, bool tiebreak>
00102   ExecStatus
00103   ArgMax<VA,VB,tiebreak>::propagate(Space& home, const ModEventDelta&) {
00104     /*
00105      * A key invariant is as follows: for each value i in the domain
00106      * of y there is an index-value pair with index i in x.
00107      */
00108 
00109     // Compute lower and upper bounds for the maximum and its first position.
00110     int p = x[0].idx;
00111     int l = x[0].view.min();
00112     int u = x[0].view.max();
00113     for (int i=1; i<x.size(); i++) {
00114       if (l < x[i].view.min()) {
00115         p = x[i].idx; l = x[i].view.min();
00116       }
00117       if (u < x[i].view.max())
00118         u = x[i].view.max();
00119     }
00120 
00121     // Eliminate elements from x and y that are too small
00122     {
00123       Region r;
00124 
00125       // Values to delete from y
00126       int* d=r.alloc<int>(y.size());
00127       // Number of values to delete
00128       int  n = 0;
00129 
00130       int i=0, j=0;
00131       ViewValues<VB> iy(y);
00132 
00133       while ((i < x.size()) && iy()) {
00134         if (x[i].idx == iy.val()) {
00135           if (x[i].view.max() < l) {
00136             x[i].view.cancel(home,*this,PC_INT_BND);
00137             d[n++]=x[i].idx;
00138           } else {
00139             x[j++]=x[i];
00140           }
00141           ++iy;
00142         } else {
00143           assert(x[i].idx < iy.val());
00144           if (x[i].view.max() < l) {
00145             x[i].view.cancel(home,*this,PC_INT_BND);
00146           } else {
00147             x[j++]=x[i];
00148           }
00149         }
00150         i++;
00151       }
00152       while (i < x.size())
00153         if (x[i].view.max() < l) {
00154           x[i].view.cancel(home,*this,PC_INT_BND); i++;
00155         } else {
00156           x[j++]=x[i++];
00157         }
00158       x.size(j);
00159 
00160       if (static_cast<unsigned int>(n) == y.size())
00161         return ES_FAILED;
00162       Iter::Values::Array id(d,n);
00163       GECODE_ME_CHECK(y.minus_v(home,id,false));
00164     }
00165 
00166     /*
00167      * Now the following invariant holds:
00168      * - for all q in y: u >= x(q).max() >= l
00169      * - if l==u, then exists q in y: x(q).max = u
00170      */
00171 
00172     if (tiebreak && (l == u))
00173       GECODE_ME_CHECK(y.lq(home,p));
00174 
00175     if (y.assigned()) {
00176       int max=0;
00177       while (x[max].idx < y.val())
00178         max++;
00179       assert(x[max].idx == y.val());
00180       if (tiebreak)
00181         for (int i=0; i<max; i++)
00182           GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home(*this),
00183                                                 x[i].view,x[max].view)));
00184       else
00185         for (int i=0; i<max; i++)
00186           GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
00187                                                x[i].view,x[max].view)));
00188       for (int i=max+1; i<x.size(); i++)
00189         GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
00190                                               x[i].view,x[max].view)));
00191       return home.ES_SUBSUMED(*this);
00192     }
00193 
00194     // Recompute the upper bound for elements in y
00195     {
00196       ViewValues<VB> iy(y);
00197       int i=0;
00198       // Skip smaller elements
00199       while (x[i].idx < y.min())
00200         i++;
00201       u=x[i].view.max();
00202       // Skip the minimal element
00203       i++; ++iy;
00204       while (iy()) {
00205         if (x[i].idx == iy.val()) {
00206           u = std::max(u,x[i].view.max());
00207           ++iy;
00208         } else {
00209           assert(x[i].idx < iy.val());
00210         }
00211         i++;
00212       }
00213     }
00214 
00215     // Constrain elements in x but not in y
00216     {
00217       int i = 0;
00218       // Elements which must be smaller (for tiebreaking)
00219       if (tiebreak)
00220         while ((i < x.size()) && (x[i].idx < y.min())) {
00221           GECODE_ME_CHECK(x[i].view.le(home,u));
00222           i++;
00223         }
00224       else
00225         while ((i < x.size()) && (x[i].idx < y.min())) {
00226           GECODE_ME_CHECK(x[i].view.lq(home,u));
00227           i++;
00228         }
00229       assert(x[i].idx == y.min());
00230 
00231       // Elements which cannot be larger
00232       ViewValues<VB> iy(y);
00233       // Skip the minimal element
00234       i++; ++iy;
00235       while ((i < x.size()) && iy()) {
00236         if (x[i].idx == iy.val()) {
00237           ++iy;
00238         } else {
00239           assert(x[i].idx < iy.val());
00240           GECODE_ME_CHECK(x[i].view.lq(home,u));
00241         }
00242         i++;
00243       }
00244       while (i < x.size()) {
00245         assert(x[i].idx > y.max());
00246         GECODE_ME_CHECK(x[i].view.lq(home,u));
00247         i++;
00248       }
00249     }
00250     return tiebreak ? ES_NOFIX : ES_FIX;
00251   }
00252 
00253   template<class VA, class VB, bool tiebreak>
00254   forceinline size_t
00255   ArgMax<VA,VB,tiebreak>::dispose(Space& home) {
00256     x.cancel(home,*this,PC_INT_BND);
00257     y.cancel(home,*this,PC_INT_DOM);
00258     (void) Propagator::dispose(home);
00259     return sizeof(*this);
00260   }
00261 
00262 }}}
00263 
00264 // STATISTICS: int-prop
00265