#include <gecode/driver.hh>

#include <algorithm>
#include <fstream>
#include <iterator>
#include <iostream>
#include <vector>

#include "ldsb.hh"
#include "siglex.hh"

#include "cputimer.hh"

using namespace Gecode;
using namespace std;

class ConcertInstance {
public:
    int n;
    vector<int> start;
    vector<int> end;
    vector<int> price;

    ConcertInstance() { }
    ConcertInstance(string filename) {
        ifstream i(filename.c_str());
        i >> n;
        for (int j = 0 ; j < n ; j++) {
            int s, e, p;
            i >> s >> e >> p;
            start.push_back(s);
            end.push_back(e);
            price.push_back(p);
            //            cerr << start[j] << " " << end[j] << " " << price[j] << "\n";
        }
    }
    
    friend ostream& operator<< (ostream& o, const ConcertInstance& g);
};

ostream&
operator<< (ostream& o, const ConcertInstance& g) {
    o << "n: " << g.n << "\n";
    o << "start: ";
    copy(g.start.begin(), g.start.end(), ostream_iterator<int>(o, " "));
    o << "\n";
    o << "end: ";
    copy(g.end.begin(), g.end.end(), ostream_iterator<int>(o, " "));
    o << "\n";
    o << "price: ";
    copy(g.price.begin(), g.price.end(), ostream_iterator<int>(o, " "));
    o << "\n";
    return o;
}

// Is x in the interval [l..r]?
bool between(int x, int l, int r) {
    return l <= x && x <= r;
}

class ConcertOptions : public Options {
public:
    ConcertInstance inst;
    int halls;
    ConcertOptions(const char *s) : Options(s) {}
    void parse(int& argc, char **argv) {
        Options::parse(argc, argv);
        inst = ConcertInstance(argv[1]);
        halls = atoi(argv[2]);
    }
};

int end(IntArgs p, int i, int n) {
    if (i == p.size()-1)
        return n;
    return p[i+1];
}

class Concert : public MaximizeScript {
protected:
    IntVarArray x;
    IntVar profit;
public:
    enum {
        SYMMETRY_NONE, 
        SYMMETRY_PRECEDE,
        SYMMETRY_SIGLEX,
        SYMMETRY_SIGLEXDEC,
        SYMMETRY_LDSB,
        SYMMETRY_NAIVE
    };

    enum {
        BRANCH_NONE,
        BRANCH_SIZE_CON,
        BRANCH_SIZE_MIN
    };

    enum {
        MODEL_VARVAL,
        MODEL_VAL
    };

    Concert(const ConcertOptions& opt)
        : x(*this, opt.inst.n, 1, opt.halls+1) {
        int n = opt.inst.n;
        int dummy = opt.halls+1;

        // Work out the upper bound on profit.
        int max_profit = 0;
        for (int i = 0 ; i < n ; i++)
            max_profit += opt.inst.price[i];
        // Initialise profit variable.
        profit = IntVar(*this, 0, max_profit);

        // std::cerr << opt.inst << "\n";

        // Compute number of variable partitions.
        int n_partitions = 1;
        for (int i = 1 ; i < n ; i++) {
            bool same_as_before;
            same_as_before =
                opt.inst.start[i] == opt.inst.start[i-1]
                && opt.inst.end[i] == opt.inst.end[i-1]
                && opt.inst.price[i] == opt.inst.price[i-1];
            if (!same_as_before)
                n_partitions++;
        }
        IntArgs p(n_partitions);
        // Now go through again and record where the partitions
        // start.
        {
            p[0] = 0;
            int j = 1;
            for (int i = 1 ; i < n ; i++) {
                bool same_as_before;
                same_as_before =
                    opt.inst.start[i] == opt.inst.start[i-1]
                    && opt.inst.end[i] == opt.inst.end[i-1]
                    && opt.inst.price[i] == opt.inst.price[i-1];
                if (!same_as_before) {
                    p[j] = i;
                    j++;
                }
            }
        }
        // cerr << p << "\n";

        for (int i = 0 ; i < n ; i++) {
            for (int j = i+1 ; j < n ; j++) {
                bool overlap = between(opt.inst.start[i], opt.inst.start[j], opt.inst.end[j])
                    || between(opt.inst.start[j], opt.inst.start[i], opt.inst.end[i]);
                if (overlap) {
                    // x_i != dummy OR x_j != dummy OR x_i != x_j
                    // This doesn't seem to give enough propagation.
                    // 
                    // // Offers i and j overlap, so they must not be in
                    // // the same hall.
                    // BoolVar i_unassigned = expr(*this, x[i] == dummy);
                    // BoolVar j_unassigned = expr(*this, x[j] == dummy);
                    // BoolVar different = expr(*this, x[i] != x[j]);
                    // // At least one of the above must be true.
                    // BoolVarArgs b(3);
                    // b[0] = i_unassigned;
                    // b[1] = j_unassigned;
                    // b[2] = different;
                    // rel(*this, BOT_OR, b, 1, ICL_DOM);

                    // x_i != dummy -> x_i != x_j AND
                    // x_j != dummy -> x_i != x_j
                    BoolVar i_assigned(*this, 0, 1);
                    BoolVar j_assigned(*this, 0, 1);
                    rel(*this, x[i], IRT_NQ, dummy, i_assigned);
                    rel(*this, x[j], IRT_NQ, dummy, j_assigned);
                    rel(*this, i_assigned >> (x[i] != x[j]));
                    rel(*this, j_assigned >> (x[i] != x[j]));
                }
            }
        }

        // Calculate profit.
        BoolVarArray used(*this, n, 0, 1);
        IntArgs coefficients(n);
        for (int i = 0 ; i < n ; i++) {
            used[i] = expr(*this, x[i] != dummy);
            coefficients[i] = opt.inst.price[i];
        }
        linear(*this, coefficients, used, IRT_EQ, profit);

        // Discard variable symmetries?
        if (opt.model() == MODEL_VAL) {
            p = IntArgs(n);
            for (int i = 0 ; i < n ; i++)
                p[i] = i;
        }
                
        if (opt.symmetry() == SYMMETRY_LDSB) {
            Symmetries<IntView> s(p.size()+1);

            IntArgs a(opt.halls);
            for (int i = 0 ; i < opt.halls ; i++)
                a[i] = i+1;
            s[0] = ValueSymmetry<IntView>(*this, a);

            for (int i = 0 ; i < p.size() ; i++) {
                int ps = end(p,i,n) - p[i];
                IntArgs indices(ps);
                for (int j = 0 ; j < ps ; j++)
                    indices[j] = p[i]+j;
                // cerr << indices << "\n";
                s[i+1] = VariableSymmetry<IntView>(*this, indices);
            }
            switch (opt.branching()) {
            case BRANCH_NONE: branch(*this, x, INT_VAR_NONE, INT_VAL_MIN, s); break;
            case BRANCH_SIZE_MIN: branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN, s); break;
            case BRANCH_SIZE_CON: branch(*this, x, tiebreak(INT_VAR_SIZE_MIN, INT_VAR_DEGREE_MAX), INT_VAL_MIN, s); break;
            }
        } else {
            if (opt.symmetry() == SYMMETRY_PRECEDE) {
                int minval = 1;
                int maxval = opt.halls;
                for (int i = minval ; i < maxval ; i++) {
                    precede(*this, x, i, i+1);
                }
                for (int i = 0 ; i < p.size() ; i++) {
                    for (int j = p[i] ; j != end(p,i,n)-1 ; j++)
                        rel(*this, x[j] <= x[j+1]);
                }
            } else if (opt.symmetry() == SYMMETRY_SIGLEX) {
                int minval = 1;
                int maxval = opt.halls;
                for (int i = minval ; i < maxval ; i++) {
                    SigLex::siglex(*this, i, p, x);
                }
            } else if (opt.symmetry() == SYMMETRY_SIGLEXDEC) {
                int minval = 1;
                int maxval = opt.halls;
                for (int i = minval ; i < maxval ; i++) {
                    SigLex::siglexdec(*this, i, p, x);
                }
            } else if (opt.symmetry() == SYMMETRY_NAIVE) {
                // Order variables in partitions.
                for (int i = 0 ; i < p.size() ; i++)
                    for (int j = p[i] ; j != end(p,i,n)-1 ; j++)
                        rel(*this, x[j] <= x[j+1]);
                // Channel to boolean matrix, and lex-order its
                // columns.
                BoolVarArray b(*this, n*(opt.halls+1), 0, 1);
                Matrix<BoolVarArray> m(b, opt.halls+1, n);
                for (int i = 0 ; i < n ; i++)
                    channel(*this, m.row(i), x[i], 1, ICL_DEF);
                // Note: don't lex order value opt.halls and
                // opt.halls+1: the latter is NOT symmetric with the
                // other values.
                //
                // Note also that we order with >=, not <=, so that
                // smaller values appear earlier.  This makes it
                // consistent with the variable symmetry on x.
                for (int j = 0 ; j < opt.halls-1 ; j++)
                    lex(*this, m.col(j), IRT_GQ, m.col(j+1), ICL_DOM);
            }
            switch (opt.branching()) {
            case BRANCH_NONE: branch(*this, x, INT_VAR_NONE, INT_VAL_MIN); break;
            case BRANCH_SIZE_MIN: branch(*this, x, INT_VAR_SIZE_MIN, INT_VAL_MIN); break;
            case BRANCH_SIZE_CON: branch(*this, x, tiebreak(INT_VAR_SIZE_MIN, INT_VAR_DEGREE_MAX), INT_VAL_MIN); break;
            }
        }
    }
    virtual Space* copy(bool share) {
        return new Concert(share, *this);
    }
    Concert(bool share, Concert& e)
        : MaximizeScript(share, e) {
        x.update(*this, share, e.x);
        profit.update(*this, share, e.profit);
    }
    IntVar cost(void) const {
        return profit;
    }

    virtual void print(std::ostream& o) const {
        o << "profit: " << profit << '\n';
        o << x << '\n';
    }
};

int
main(int argc, char **argv) {
    ConcertOptions opt("concert hall scheduling");
    opt.solutions(0);
    opt.symmetry(Concert::SYMMETRY_NONE);
    opt.symmetry(Concert::SYMMETRY_NONE, "none", "no symmetry breaking");
    opt.symmetry(Concert::SYMMETRY_PRECEDE, "precede", "use value precedence constraints");
    opt.symmetry(Concert::SYMMETRY_SIGLEX, "siglex", "use SigLex constraints");
    opt.symmetry(Concert::SYMMETRY_SIGLEXDEC, "siglexdec", "use SigLex constraints with decreasing partition ordering");
    opt.symmetry(Concert::SYMMETRY_LDSB, "ldsb", "use LDSB");
    opt.symmetry(Concert::SYMMETRY_NAIVE, "naive", "use naive symmetry breaking");
    opt.branching(Concert::BRANCH_SIZE_MIN);
    opt.branching(Concert::BRANCH_NONE, "none", "naive branching");
    opt.branching(Concert::BRANCH_SIZE_MIN, "size", "smallest domain size");
    opt.branching(Concert::BRANCH_SIZE_CON, "sizecon", "smallest domain, break ties by constrainedness");
    opt.model(Concert::MODEL_VARVAL);
    opt.model(Concert::MODEL_VARVAL, "varval", "consider variable and value symmetries");
    opt.model(Concert::MODEL_VAL, "val", "consider only value symmetries");
    opt.parse(argc, argv);
    // std::cerr << *(opt.graph);
    CPUTimer t;
    MinimizeScript::run<Concert,BAB,ConcertOptions>(opt);
    cout << "\tCPUTimer: ";
    t.stop();
    cout << "\n";
}
