Generated on Mon Nov 30 23:53:27 2009 for Gecode by doxygen 1.6.1

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  *  Last modified:
00016  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00017  *     $Revision: 9878 $
00018  *
00019  *  This file is part of Gecode, the generic constraint
00020  *  development environment:
00021  *     http://www.gecode.org
00022  *
00023  *  Permission is hereby granted, free of charge, to any person obtaining
00024  *  a copy of this software and associated documentation files (the
00025  *  "Software"), to deal in the Software without restriction, including
00026  *  without limitation the rights to use, copy, modify, merge, publish,
00027  *  distribute, sublicense, and/or sell copies of the Software, and to
00028  *  permit persons to whom the Software is furnished to do so, subject to
00029  *  the following conditions:
00030  *
00031  *  The above copyright notice and this permission notice shall be
00032  *  included in all copies or substantial portions of the Software.
00033  *
00034  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00035  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00036  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00037  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00038  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00039  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00040  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00041  *
00042  */
00043 
00044 #include <gecode/int/linear.hh>
00045 #include <gecode/int/distinct.hh>
00046 
00047 namespace Gecode { namespace Int { namespace GCC {
00048 
00049 
00054   template<class Card>
00055   ExecStatus
00056   postSideConstraints(Home home, ViewArray<IntView>& x, ViewArray<Card>& k) {
00057     Region r(home);
00058 
00059     {
00060       int smin = 0;
00061       int smax = 0;
00062       for (int i = k.size(); i--; ) {
00063         GECODE_ME_CHECK((k[i].gq(home, 0)));
00064         GECODE_ME_CHECK((k[i].lq(home, x.size())));
00065         smin += k[i].min();
00066         smax += k[i].max();
00067       }
00068 
00069       // not enough variables to satisfy min req
00070       if ((x.size() < smin) || (smax < x.size()))
00071         return ES_FAILED;
00072     }
00073 
00074     // Remove all values from the x that are not in v
00075     {
00076       int* v = r.alloc<int>(k.size());
00077       for (int i=k.size(); i--;)
00078         v[i]=k[i].card();
00079       Support::quicksort(v,k.size());
00080       for (int i=x.size(); i--; ) {
00081         Iter::Values::Array iv(v,k.size());
00082         GECODE_ME_CHECK(x[i].inter_v(home, iv, false));
00083       }
00084     }
00085 
00086     // Remove all values with 0 max occurrence
00087     // and remove corresponding occurrence variables from k
00088     {
00089       // The number of zeroes
00090       int n_z = 0;
00091       for (int i=k.size(); i--;)
00092         if (k[i].max() == 0)
00093           n_z++;
00094 
00095       if (n_z > 0) {
00096         int* z = r.alloc<int>(n_z);
00097         n_z = 0;
00098         int n_k = 0;
00099         for (int i=0; i<k.size(); i++)
00100           if (k[i].max() == 0) {
00101             z[n_z++] = k[i].card();            
00102           } else {
00103             k[n_k++] = k[i];
00104           }
00105         k.size(n_k);
00106         Support::quicksort(z,n_z);
00107         for (int i=x.size(); i--;) {
00108           Iter::Values::Array zi(z,n_z);
00109           GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
00110         }
00111       }
00112     }
00113 
00114     if (Card::propagate) {
00115       Linear::Term<IntView>* t = r.alloc<Linear::Term<IntView> >(k.size());
00116       for (int i = k.size(); i--; ) {
00117         t[i].a=1; t[i].x=k[i].base();
00118       }
00119       Linear::post(home,t,k.size(),IRT_EQ,x.size(),ICL_BND);
00120     }
00121 
00122     return ES_OK;
00123   }
00124 
00125 
00130   template<class Card>
00131   inline bool
00132   isDistinct(Home home, ViewArray<IntView>& x, ViewArray<Card>& k) {
00133     if (Card::propagate) {
00134       Region r(home);
00135       ViewRanges<IntView>* xrange = r.alloc<ViewRanges<IntView> >(x.size());
00136       for (int i = x.size(); i--; ){
00137         ViewRanges<IntView> iter(x[i]);
00138         xrange[i] = iter;
00139       }
00140       Iter::Ranges::NaryUnion<ViewRanges<IntView> > drl(&xrange[0], x.size());
00141       if (static_cast<unsigned int>(k.size()) == Iter::Ranges::size(drl)) {
00142         for (int i=k.size(); i--;)
00143           if (k[i].min() != 1 || k[i].max() != 1)
00144             return false;
00145         return true;
00146       } else {
00147         return false;
00148       }
00149     } else {
00150       for (int i=k.size(); i--;)
00151         if (k[i].min() != 0 || k[i].max() != 1)
00152           return false;
00153       return true;
00154     }
00155   }
00156 
00157 }}}
00158 
00159 // STATISTICS: int-prop