[gecode-users] a missed "atleast/atmost/exactly" for arrays - solution source included

[Christian Schulte]

Martin, that's a good one! I'll add it for Gecode 2.0.

Christian

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Martin Mann
Sent: Thursday, March 08, 2007 4:49 PM
To: gecode user list
Subject: [gecode-users] a missed "atleast/atmost/exactly" for arrays -
solution source included


Hi,

I was searching for an 'atmost' constraint to express

#( X_i == Y_i ) <= z

whereby X = IntVarArray, Y = IntArgs (array of integers) and z is the 
integer bound for the number of matches.
Currently 'atmost' supports only the match against one single value or 
an IntVar.

Below I attached my code (derived from 'count' and the mechanisms used 
for 'distinct'), maybe this is something usefull for others too. Think 
this could be interesting for further versions of Gecode if you like it.

Have a nice weekend,

Martin

=====================================================================


#include "gecode/int/count.hh"

namespace Gecode {

   void
   count(Space* home, const IntVarArgs& xa, const IntArgs& ya,
	IntRelType r, int z, IntConLevel icl) {
     using namespace Int;
     if (home->failed()) return;
     ViewArray<OffsetView> x(home,xa.size());
     for (int i = ya.size(); i--; )
       if ((-ya[i] < Limits::Int::int_min) || (-ya[i] > 
Limits::Int::int_max))
         throw NumericalOverflow("Int::count");
       else
         x[i].init(xa[i],-ya[i]);
     ConstIntView yv(0);
     switch (r) {
     case IRT_EQ:
       GECODE_ES_FAIL(home,(Count::EqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z)));
       break;
     case IRT_NQ:
       GECODE_ES_FAIL(home,(Count::NqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z)));
       break;
     case IRT_LE:
       GECODE_ES_FAIL(home,(Count::LqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z-1)));
       break;
     case IRT_LQ:
       GECODE_ES_FAIL(home,(Count::LqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z)));
       break;
     case IRT_GR:
       GECODE_ES_FAIL(home,(Count::GqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z+1)));
       break;
     case IRT_GQ:
       GECODE_ES_FAIL(home,(Count::GqInt<OffsetView,ConstIntView>
       			   ::post(home,x,yv,z)));
       break;
     default:
       throw UnknownRelation("Int::count");
     }
   }

   void
   atmost(Space* home, const IntVarArgs& x, const IntArgs& ya, int m,
     IntConLevel icl=ICL_DEF)
   {
     count(home,x,ya,IRT_LQ,m,icl);
   }

   void
   atleast(Space* home, const IntVarArgs& x, const IntArgs& ya, int m,
     IntConLevel icl=ICL_DEF)
   {
     count(home,x,ya,IRT_GQ,m,icl);
   }

   void
   exactly(Space* home, const IntVarArgs& x, const IntArgs& ya, int m,
     IntConLevel icl=ICL_DEF)
   {
     count(home,x,ya,IRT_EQ,m,icl);
   }

} // namespace Gecode

=====================================================================

-- 
Martin Mann, Dipl. Bioinf.
Bioinformatics - Inst. of Computer Science Albert-Ludwigs-University
Freiburg
Tel: ++49-761-203-8259
Fax: ++49-761-203-7462 http://www.bioinf.uni-freiburg.de/~mmann/

_______________________________________________
Gecode users mailing list
users at gecode.org https://www.gecode.org/mailman/listinfo/gecode-users