#include <array>
#include <map>
#include <string>


#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/gist.hh>
#include <gecode/minimodel.hh>

using namespace std;
using namespace Gecode;

string S() {
  return "";
}

template<typename T, typename... Ts>
string S(T v, Ts... vs) {
  stringstream ss;
  ss << v << S(vs...);
  return ss.str();
}

struct Op {
  string inst;
  IntVar *v;
  int delay;
};

struct Demultiplexer : public Space {
  
  IntVarArray op_times;
  array<Op, 17> ops;
  uint opCount;

  Demultiplexer(vector<bool> bits) 
    : op_times(*this, 17, 0, 16)
  {
    /// post the problem (the instructions and their temporal
    /// dependencies)

    // only one op per time slice
    distinct(*this, op_times);

    // the final jump
    auto &jump = op(2, "  ijmp");
    at(jump, 15);

    // rising flanks
    for (uint i=0; i<bits.size(); i++) {
      auto &rise = op(1, S("  out %", i, ", 1"));
      auto &fall = op(1, S("  out %", i, ", 0"));
      if (bits[i]) { after(rise, fall, 4, 6 ); }
      else         { after(rise, fall, 8, 13); }
      after(fall, jump);
      at(rise, i);
    }

    // load next jump location
    after(op(2, "  ld %ZH, %[data_ptr]+"), jump);

    // add nops until we have enough instructions to fill the time
    // slice
    while (opCount < ops.size())
      op(1, "  nop");

    /// branching
    branch(*this, op_times, INT_VAR_SIZE_MIN, INT_VAL_MIN);
  }

  Op& op(int delay, string inst) {
    Op &o = ops[opCount];
    o.inst  = inst;
    o.v     = &(op_times[opCount]);
    o.delay = delay;
    opCount++;

    // add pseudo-op to encode instructions that take more than one
    // cycle
    if (delay > 1) {
      auto nextOp = op(delay - 1, "; 1 clock cycle delay");
      rel(*this, *(o.v) + 1 == *(nextOp.v));
    }
   
    return o;
  }

  /// helper for constraint formulation

  void after(Op& pre, Op& post, int delay_min=0, int delay_max=-1) {
    rel(*this, *(pre.v) + pre.delay + delay_min <= *(post.v));
    if (delay_max >= 0)
      rel(*this, *(pre.v) + pre.delay + delay_max >= *(post.v));
  }

  void at(Op& op, int time_min, int time_max=-1) {
    if (time_max == -1)
      time_max = time_min;
    rel(*this, *(op.v) >= time_min);
    rel(*this, *(op.v) <= time_max);
  }

  /// return resulting instruction stream

  string print() {
    stringstream ss;
    print(ss, false);
    return ss.str();
  }

  /// gecode boilerplate
  Demultiplexer(bool share, Demultiplexer &o)
    : Space(share, o),
      ops(o.ops),
      opCount(o.opCount)
  {
    op_times.update(*this, share, o.op_times);
  }

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

  void print(ostream &o, bool printTimes=true) const {
    multimap<int, int> timedOps;
    for (uint i=0; i<ops.size(); i++)
      timedOps.insert(make_pair(op_times[i].min(), i));
    for (auto i : timedOps) {
      auto &op = ops[i.second];
      o << op.inst;
      if (printTimes)
	o << "\t; " << *(op.v);
      o << endl;
    }
  }
};

int main(int argc, char **argv) {
  Demultiplexer *d = new Demultiplexer({0,1,0,1,0});

  // Gist::Print<Demultiplexer> gp("print solution");
  // Gist::Options go;
  // go.inspect.click(&gp);
  // Gist::dfs(d, go);

  DFS<Demultiplexer> e(d);
  delete d;
  d = e.next();
  if (d) {
    cout << d->print();
    delete d;
  }else{
    cerr << "no instruction sequence found";
  }
}