main page modules namespaces classes files
Gecode home

search for 

hamming.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2004
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-03 13:51:17 +0200 (Thu, 03 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3506 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "gecode/set.hh"
#include "examples/support.hh"
#include "gecode/minimodel.hh"

class Hamming : public Example {
public:
  SetVarArray xs;

  static const int bits = 20;
  static const int dist = 3;

  Hamming(const Options& o) :
    xs(this,o.size,IntSet::empty,1,bits) {
    SetVarArray cxs(this,xs.size());
    for (int i=0; i<xs.size(); i++)
      rel(this, xs[i], SRT_CMPL, cxs[i]);

    for (int i=0; i<xs.size(); i++) {
      SetVar y = xs[i];
      SetVar cy = cxs[i];
      for (int j=i+1; j<xs.size(); j++) {
        SetVar x = xs[j];
        SetVar cx = cxs[j];

        SetVar xIntCy(this);
        SetVar yIntCx(this);

        rel(this, x, SOT_INTER, cy, SRT_EQ, xIntCy);
        rel(this, y, SOT_INTER, cx, SRT_EQ, yIntCx);
        IntVar diff1(this,0,1024);
        IntVar diff2(this,0,1204);
        cardinality(this, xIntCy,diff1);
        cardinality(this, yIntCx,diff2);
        post(this, diff1+diff2 >= dist);

      }
    }

    branch(this, xs, SETBVAR_NONE, SETBVAL_MIN);
  }

  Hamming(bool share, Hamming& s) : Example(share,s) {
    xs.update(this, share, s.xs);
  }

  virtual Space*
  copy(bool share) {
    return new Hamming(share,*this);
  }

  virtual void
  print(void) {
    for (int i=0; i<xs.size(); i++) {
      std::cout << "\t[" << i << "]" << xs[i] << std::endl;
    }
  }
};


int
main(int argc, char** argv) {
  Options o("Hamming");
  o.size = 32;
  o.parse(argc,argv);
  Example::run<Hamming,DFS>(o);
  return 0;
}


// STATISTICS: example-any