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

[Martin Mann]

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/