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
00100 if (opt.trace() != 0)
00101 trace(*this, x, opt.trace());
00102
00103 SetVarArgs cx(x.size());
00104
00105 for (int i=x.size(); i--;)
00106 cx[i] = expr(*this, -x[i]);
00107
00108 for (int i=0; i<x.size(); i++)
00109 for (int j=i+1; j<x.size(); j++)
00110 rel(*this,
00111 cardinality(x[j] & cx[i]) +
00112 cardinality(x[i] & cx[j]) >= opt.distance());
00113
00114 branch(*this, x, SET_VAR_NONE(), SET_VAL_MIN_INC());
00115 }
00116
00118 virtual void
00119 print(std::ostream& os) const {
00120 for (int i=0; i<x.size(); i++) {
00121 os << "\t[" << i << "] = " << x[i] << std::endl;
00122 }
00123 }
00124
00126 Hamming(bool share, Hamming& s) : Script(share,s) {
00127 x.update(*this, share, s.x);
00128 }
00130 virtual Space*
00131 copy(bool share) {
00132 return new Hamming(share,*this);
00133 }
00134
00135 };
00136
00140 int
00141 main(int argc, char* argv[]) {
00142 HammingOptions opt("Hamming",20,3,32);
00143 opt.parse(argc,argv);
00144 Script::run<Hamming,DFS,HammingOptions>(opt);
00145 return 0;
00146 }
00147
00148
00149
00150