Generated on Wed Jan 4 17:49:11 2006 for Gecode by doxygen 1.4.6

sortedness.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-02 18:22:34 +0100 (Fri, 02 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2691 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 #include "int/sortedness.hh"
00023 namespace Gecode {
00024 
00025   using namespace Int;
00026   void sortedness(Space* home, 
00027                   const IntVarArgs& x, 
00028                   const IntVarArgs& y, 
00029                   IntConLevel) {
00030     int n = x.size();
00031     if (n != y.size()) {
00032 
00033       throw ArgumentSizeMismatch("Int::sortedness");
00034     }
00035     if (home->failed()) {
00036       return;
00037     }
00038 
00039     ViewArray<IntView> y0(home, y);
00040     ViewArray<IntView> x_check_shared(home, x);
00041 
00042     ViewArray<ViewTuple<IntView,1> > x0(home, n);
00043 
00044     for (int i = n; i--; ) {
00045       x0[i][0] = x[i];
00046     }
00047 
00048     if (x_check_shared.shared() ||
00049         y0.shared()) {
00050       GECODE_ES_FAIL(home, 
00051                      (Sortedness::
00052                       Sortedness<IntView, ViewTuple<IntView,1>, false, true>::
00053                       post(home, x0, y0)));
00054 
00055     } else {
00056       GECODE_ES_FAIL(home, 
00057                      (Sortedness::
00058                       Sortedness<IntView, ViewTuple<IntView,1>, false, false >::
00059                       post(home, x0, y0)));
00060     }
00061   }
00062 
00063   void sortedness(Space* home, 
00064                   const IntVarArgs& x, 
00065                   const IntVarArgs& y, 
00066                   const IntVarArgs& z, 
00067                   IntConLevel) {
00068     int n = x.size();
00069     if ((n != y.size()) || (n != z.size())) {
00070       throw ArgumentSizeMismatch("Int::sortedness");
00071     }
00072     if (home->failed()) {
00073       return;
00074     }
00075 
00076     ViewArray<IntView> x_check_shared(home, x);
00077     ViewArray<IntView> z_check_shared(home, z);
00078     // permutation variables have to be all different
00079     if (z_check_shared.shared() && z.size() > 1) {
00080       home->fail();
00081     }
00082 
00083     ViewArray<IntView> y0(home, y);
00084     ViewArray<ViewTuple<IntView, 2> > xz0(home, n);
00085 
00086     // assert that permutation variables encode a permutation
00087     ViewArray<IntView> pz0(home, n);
00088     for (int i = n; i--; ) {
00089       xz0[i][0] = x[i];
00090       xz0[i][1] = z[i];
00091       pz0[i]    = z[i];
00092       // Constrain z_i to a valid index
00093       GECODE_ME_FAIL(home,xz0[i][1].gq(home,0));
00094       GECODE_ME_FAIL(home,xz0[i][1].lq(home,n - 1));
00095     }
00096     // assert permutation
00097     GECODE_ES_FAIL(home, Distinct::Bnd<IntView>::post(home, pz0));
00098 
00099     if (x_check_shared.shared() ||
00100         y0.shared()) {
00101       GECODE_ES_FAIL(home, 
00102                      (Sortedness::
00103                       Sortedness<IntView, ViewTuple<IntView,2>, true, true >::
00104                       post(home, xz0, y0)));
00105     } else {
00106       GECODE_ES_FAIL(home, 
00107                      (Sortedness::
00108                       Sortedness<IntView, ViewTuple<IntView,2>, true, false >::
00109                       post(home, xz0, y0)));
00110     }
00111   }
00112 }
00113 
00114 // STATISTICS: int-post