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

post.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2004/2005
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2009
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <gecode/int/linear.hh>
00041 #include <gecode/int/distinct.hh>
00042 
00043 namespace Gecode { namespace Int { namespace GCC {
00044 
00045   template<class Card>
00047   class CardLess : public Support::Less<Card> {
00048   public:
00049     bool operator ()(const Card& x, const Card& y) {
00050       return x.card() < y.card();
00051     }
00052   };
00053 
00058   template<class Card>
00059   ExecStatus
00060   postSideConstraints(Home home, ViewArray<IntView>& x, ViewArray<Card>& k) {
00061     CardLess<Card> cl;
00062     Support::quicksort(&k[0], k.size(), cl);
00063     Region r;
00064 
00065     {
00066       int smin = 0;
00067       int smax = 0;
00068       for (int i = k.size(); i--; ) {
00069         GECODE_ME_CHECK((k[i].gq(home, 0)));
00070         GECODE_ME_CHECK((k[i].lq(home, x.size())));
00071         smin += k[i].min();
00072         smax += k[i].max();
00073       }
00074 
00075       // not enough variables to satisfy min req
00076       if ((x.size() < smin) || (smax < x.size()))
00077         return ES_FAILED;
00078     }
00079 
00080     // Remove all values from the x that are not in v
00081     {
00082       int* v = r.alloc<int>(k.size());
00083       for (int i=k.size(); i--;)
00084         v[i]=k[i].card();
00085       Support::quicksort(v,k.size());
00086       for (int i=x.size(); i--; ) {
00087         Iter::Values::Array iv(v,k.size());
00088         GECODE_ME_CHECK(x[i].inter_v(home, iv, false));
00089       }
00090     }
00091 
00092     // Remove all values with 0 max occurrence
00093     // and remove corresponding occurrence variables from k
00094     {
00095       // The number of zeroes
00096       int n_z = 0;
00097       for (int i=k.size(); i--;)
00098         if (k[i].max() == 0)
00099           n_z++;
00100 
00101       if (n_z > 0) {
00102         int* z = r.alloc<int>(n_z);
00103         n_z = 0;
00104         int n_k = 0;
00105         for (int i=0; i<k.size(); i++)
00106           if (k[i].max() == 0) {
00107             z[n_z++] = k[i].card();
00108           } else {
00109             k[n_k++] = k[i];
00110           }
00111         k.size(n_k);
00112         Support::quicksort(z,n_z);
00113         for (int i=x.size(); i--;) {
00114           Iter::Values::Array zi(z,n_z);
00115           GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
00116         }
00117       }
00118     }
00119 
00120     if (Card::propagate) {
00121       Linear::Term<IntView>* t = r.alloc<Linear::Term<IntView> >(k.size());
00122       for (int i = k.size(); i--; ) {
00123         t[i].a=1; t[i].x=k[i].base();
00124       }
00125       Linear::post(home,t,k.size(),IRT_EQ,x.size(),IPL_BND);
00126     }
00127 
00128     return ES_OK;
00129   }
00130 
00131 
00136   template<class Card>
00137   inline bool
00138   isDistinct(ViewArray<IntView>& x, ViewArray<Card>& k) {
00139     if (Card::propagate) {
00140       Region r;
00141       ViewRanges<IntView>* xrange = r.alloc<ViewRanges<IntView> >(x.size());
00142       for (int i = x.size(); i--; ){
00143         ViewRanges<IntView> iter(x[i]);
00144         xrange[i] = iter;
00145       }
00146       Iter::Ranges::NaryUnion drl(r, &xrange[0], x.size());
00147       if (static_cast<unsigned int>(k.size()) == Iter::Ranges::size(drl)) {
00148         for (int i=k.size(); i--;)
00149           if (k[i].min() != 1 || k[i].max() != 1)
00150             return false;
00151         return true;
00152       } else {
00153         return false;
00154       }
00155     } else {
00156       for (int i=k.size(); i--;)
00157         if (k[i].min() != 0 || k[i].max() != 1)
00158           return false;
00159       return true;
00160     }
00161   }
00162 
00163 }}}
00164 
00165 // STATISTICS: int-prop