Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
hamming.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2004
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/driver.hh>
35 #include <gecode/int.hh>
36 #include <gecode/minimodel.hh>
37 #include <gecode/set.hh>
38 
39 using namespace Gecode;
40 
46 class HammingOptions : public Options {
47 private:
51  Driver::UnsignedIntOption _distance;
54 
55 public:
57  HammingOptions(const char* s, unsigned int bits0,
58  unsigned int distance0, unsigned int size0)
59  : Options(s),
60  _bits("bits","word size in bits",bits0),
61  _distance("distance","minimum distance",distance0),
62  _size("size","number of symbols",size0) {
63  add(_bits); add(_distance); add(_size);
64  }
65 
67  unsigned int bits(void) const { return _bits.value(); }
69  unsigned int distance(void) const { return _distance.value(); }
71  unsigned int size(void) const { return _size.value(); }
72 
73 };
74 
86 class Hamming : public Script {
87 private:
89  SetVarArray x;
90 public:
93  Script(opt),
94  x(*this,opt.size(),IntSet::empty,1,opt.bits()) {
95 
96  if (opt.trace() != 0)
97  trace(*this, x, opt.trace());
98 
99  SetVarArgs cx(x.size());
100 
101  for (int i=x.size(); i--;)
102  cx[i] = expr(*this, -x[i]);
103 
104  for (int i=0; i<x.size(); i++)
105  for (int j=i+1; j<x.size(); j++)
106  rel(*this,
107  cardinality(x[j] & cx[i]) +
108  cardinality(x[i] & cx[j]) >= opt.distance());
109 
110  branch(*this, x, SET_VAR_NONE(), SET_VAL_MIN_INC());
111  }
112 
114  virtual void
115  print(std::ostream& os) const {
116  for (int i=0; i<x.size(); i++) {
117  os << "\t[" << i << "] = " << x[i] << std::endl;
118  }
119  }
120 
122  Hamming(Hamming& s) : Script(s) {
123  x.update(*this, s.x);
124  }
126  virtual Space*
127  copy(void) {
128  return new Hamming(*this);
129  }
130 
131 };
132 
136 int
137 main(int argc, char* argv[]) {
138  HammingOptions opt("Hamming",20,3,32);
139  opt.parse(argc,argv);
140  Script::run<Hamming,DFS,HammingOptions>(opt);
141  return 0;
142 }
143 
144 
145 // STATISTICS: example-any
146 
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:629
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
Parametric base-class for scripts.
Definition: driver.hh:729
Unsigned integer option.
Definition: driver.hh:229
void value(unsigned int v)
Set default value to v.
Definition: options.hpp:91
Integer sets.
Definition: int.hh:174
Options for scripts
Definition: driver.hh:366
Passing set variables.
Definition: set.hh:488
Set variable array
Definition: set.hh:570
Computation spaces.
Definition: core.hpp:1742
Options for Hamming problems
Definition: hamming.cpp:46
unsigned int bits(void) const
Return number of bits.
Definition: hamming.cpp:67
unsigned int size(void) const
Return number of symbols.
Definition: hamming.cpp:71
unsigned int distance(void) const
Return minimum distance.
Definition: hamming.cpp:69
HammingOptions(const char *s, unsigned int bits0, unsigned int distance0, unsigned int size0)
Initialize options for example with name s.
Definition: hamming.cpp:57
Example: Generating Hamming codes
Definition: hamming.cpp:86
virtual void print(std::ostream &os) const
Print solution.
Definition: hamming.cpp:115
int main(int argc, char *argv[])
Main-function.
Definition: hamming.cpp:137
Hamming(Hamming &s)
Constructor for copying s.
Definition: hamming.cpp:122
virtual Space * copy(void)
Copy during cloning.
Definition: hamming.cpp:127
Hamming(const HammingOptions &opt)
Actual model.
Definition: hamming.cpp:92
void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te, FloatTracer &t)
Create a tracer for float variables.
Definition: trace.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})
Options opt
The options.
Definition: test.cpp:97
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:817
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96