hamming.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 #include <gecode/set.hh>
00042
00043 using namespace Gecode;
00044
00050 class HammingOptions : public Options {
00051 private:
00053 Driver::UnsignedIntOption _bits;
00055 Driver::UnsignedIntOption _distance;
00057 Driver::UnsignedIntOption _size;
00058
00059 public:
00061 HammingOptions(const char* s, unsigned int bits0,
00062 unsigned int distance0, unsigned int size0)
00063 : Options(s),
00064 _bits("-bits","word size in bits",bits0),
00065 _distance("-distance","minimum distance",distance0),
00066 _size("-size","number of symbols",size0) {
00067 add(_bits); add(_distance); add(_size);
00068 }
00069
00071 unsigned int bits(void) const { return _bits.value(); }
00073 unsigned int distance(void) const { return _distance.value(); }
00075 unsigned int size(void) const { return _size.value(); }
00076
00077 };
00078
00090 class Hamming : public Script {
00091 private:
00093 SetVarArray x;
00094 public:
00096 Hamming(const HammingOptions& opt) :
00097 Script(opt),
00098 x(*this,opt.size(),IntSet::empty,1,opt.bits()) {
00099 SetVarArgs cx(x.size());
00100 for (int i=x.size(); i--;)
00101 cx[i] = expr(*this, -x[i]);
00102
00103 for (int i=0; i<x.size(); i++)
00104 for (int j=i+1; j<x.size(); j++)
00105 rel(*this,
00106 cardinality(x[j] & cx[i]) +
00107 cardinality(x[i] & cx[j]) >= opt.distance());
00108
00109 branch(*this, x, SET_VAR_NONE(), SET_VAL_MIN_INC());
00110 }
00111
00113 virtual void
00114 print(std::ostream& os) const {
00115 for (int i=0; i<x.size(); i++) {
00116 os << "\t[" << i << "] = " << x[i] << std::endl;
00117 }
00118 }
00119
00121 Hamming(bool share, Hamming& s) : Script(share,s) {
00122 x.update(*this, share, s.x);
00123 }
00125 virtual Space*
00126 copy(bool share) {
00127 return new Hamming(share,*this);
00128 }
00129
00130 };
00131
00135 int
00136 main(int argc, char* argv[]) {
00137 HammingOptions opt("Hamming",20,3,32);
00138 opt.parse(argc,argv);
00139 Script::run<Hamming,DFS,HammingOptions>(opt);
00140 return 0;
00141 }
00142
00143
00144
00145