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 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037 #include <gecode/set.hh>
00038
00039 using namespace Gecode;
00040
00046 class HammingOptions : public Options {
00047 private:
00049 Driver::UnsignedIntOption _bits;
00051 Driver::UnsignedIntOption _distance;
00053 Driver::UnsignedIntOption _size;
00054
00055 public:
00057 HammingOptions(const char* s, unsigned int bits0,
00058 unsigned int distance0, unsigned int size0)
00059 : Options(s),
00060 _bits("bits","word size in bits",bits0),
00061 _distance("distance","minimum distance",distance0),
00062 _size("size","number of symbols",size0) {
00063 add(_bits); add(_distance); add(_size);
00064 }
00065
00067 unsigned int bits(void) const { return _bits.value(); }
00069 unsigned int distance(void) const { return _distance.value(); }
00071 unsigned int size(void) const { return _size.value(); }
00072
00073 };
00074
00086 class Hamming : public Script {
00087 private:
00089 SetVarArray x;
00090 public:
00092 Hamming(const HammingOptions& opt) :
00093 Script(opt),
00094 x(*this,opt.size(),IntSet::empty,1,opt.bits()) {
00095
00096 if (opt.trace() != 0)
00097 trace(*this, x, opt.trace());
00098
00099 SetVarArgs cx(x.size());
00100
00101 for (int i=x.size(); i--;)
00102 cx[i] = expr(*this, -x[i]);
00103
00104 for (int i=0; i<x.size(); i++)
00105 for (int j=i+1; j<x.size(); j++)
00106 rel(*this,
00107 cardinality(x[j] & cx[i]) +
00108 cardinality(x[i] & cx[j]) >= opt.distance());
00109
00110 branch(*this, x, SET_VAR_NONE(), SET_VAL_MIN_INC());
00111 }
00112
00114 virtual void
00115 print(std::ostream& os) const {
00116 for (int i=0; i<x.size(); i++) {
00117 os << "\t[" << i << "] = " << x[i] << std::endl;
00118 }
00119 }
00120
00122 Hamming(Hamming& s) : Script(s) {
00123 x.update(*this, s.x);
00124 }
00126 virtual Space*
00127 copy(void) {
00128 return new Hamming(*this);
00129 }
00130
00131 };
00132
00136 int
00137 main(int argc, char* argv[]) {
00138 HammingOptions opt("Hamming",20,3,32);
00139 opt.parse(argc,argv);
00140 Script::run<Hamming,DFS,HammingOptions>(opt);
00141 return 0;
00142 }
00143
00144
00145
00146