/*
 * File:   branch.cc
 * Author: Filip Niksic, fniksic@gmail.com
 *
 * Created on 2008. sijecanj 31, 15:35
 */

#include <vector>
#include <utility>
#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <iostream>
#include <iterator>

#include "globals.h"
#include "graph.h"
#include "branch.h"
#include "partition.h"

using namespace std;

Branch::Branch(const Graph& _g) :
    size(_g.numVertices()), g(_g), constraints(size, vector<EdgeConstraint_T>(size, ALLOWED)),
            lowerBound(0.0), numRequired(size), numAllowed(size, size), tourFound(false),
            contradiction(false), p(size) {
    setInitialConstraints();
//    cout << "Branch::Branch() (nakon setInitialConstraints)" << endl;
//    printConstraints();
//    printNums();
    computeLowerBound();

}

void Branch::setInitialConstraints() {
    for (Vertex_ID i = 0; i != constraints.size(); ++i)
        for (Vertex_ID j = i; j != constraints.size(); ++j)
            if (!g.existsEdge(i, j))
                setConstraint(make_pair(i, j), DISALLOWED);
//    cout << "Branch::setInitialConstraints()" << endl;
    setImpliedConstraints();
}

Branch::Edge_ID Branch::nextAllowedEdge(Branch::Edge_ID e) const {
    if (e.first < 0 || e.first >= constraints.size() || e.second < 0 || e.second >= constraints.size())
        throw out_of_range("Branch::nextAllowedEdge : Nepostojeci brid.");
    // Ocekujem Edge_ID u gornjem trokutu
    if (e.first > e.second)
        swap(e.first, e.second);
    for (Vertex_ID i = e.first; i != constraints.size(); ++i)
        for (Vertex_ID j = (i == e.first ? e.second : i); j != constraints.size(); ++j)
            if (constraints[i][j] == ALLOWED)
                return make_pair(i, j);
    return Graph::nullEdge;
}

void Branch::disallowEdge(Edge_ID e) {
    if (e.first < 0 || e.first >= constraints.size() || e.second < 0 || e.second >= constraints.size())
        throw out_of_range("Branch::addEdge : Nepostojeci brid.");
    if (constraints[e.first][e.second] != ALLOWED)
        throw logic_error("Branch::addEdge : Samo bridovi koji su ALLOWED smiju mijenjati constraint.");
    setConstraint(e, DISALLOWED);
    setImpliedConstraints();
    computeLowerBound();
}

void Branch::requireEdge(Edge_ID e) {
    if (e.first < 0 || e.first >= constraints.size() || e.second < 0 || e.second >= constraints.size())
        throw out_of_range("Branch::requireEdge : Nepostojeci brid.");
    if (constraints[e.first][e.second] != ALLOWED)
        throw logic_error("Branch::requireEdge : Samo bridovi koji su ALLOWED smiju mijenjati constraint.");
    setConstraint(e, REQUIRED);
    p.merge(e.first, e.second);
    setImpliedConstraints();
    computeLowerBound();
}

// setImpliedConstraints() po svom izlasku garantira da svaki brid koji je ALLOWED
// moze biti postavljen na REQUIRED ili DISALLOWED.
// TODO: Treba jos napraviti double-check uvjeta.
void Branch::setImpliedConstraints() {
    bool done = false;
    while (!done) {
        done = true;
        Edge_ID e(nextAllowedEdge(Edge_ID(0, 0)));
        while (e != Graph::nullEdge) {
            bool mustRequire(false), mustDisallow(false);
            if (closesCycle(e)) {
                // Kriterij za Hamiltonov ciklus:
                // 1. svi vrhovi se nalaze u istom skupu u particiji
                // 2. zatvaramo ciklus upravo spajajuci vrhove kojima fali jos jedan brid
                if (p.numSets() == 1 && numRequired[e.first] == 1 && numRequired[e.second] == 1) {
                    mustRequire = true;
                    tourFound = true;
                }
                else
                    mustDisallow = true;
            }
            if (numRequired[e.first] >= 2 || numRequired[e.second] >= 2)
                mustDisallow = true;
            if (numRequired[e.first] + numAllowed[e.first] <= 2 || numRequired[e.second] + numAllowed[e.second] <= 2)
                mustRequire = true;
            contradiction = (mustRequire && mustDisallow) || contradiction;
            if (mustRequire && !contradiction) {
                setConstraint(e, REQUIRED);
                p.merge(e.first, e.second);
                done = false;
            }
            if (mustDisallow && !contradiction) {
                setConstraint(e, DISALLOWED);
                done = false;
            }
            ++e.second;
            if (e.second == constraints.size()) {
                ++e.first;
                e.second = e.first;
            }
            if (e.first == constraints.size())
                break;
            e = nextAllowedEdge(e);
        }
    }
//    cout << "Branch::setImpliedConstraints() --- current constraints:" << endl;
//    printConstraints();
//    printNums();
}

// Racunam ustvari dvostruki lowerBound.
void Branch::computeLowerBound() {
    lowerBound = 0.0;
    for (Vertex_ID i = 0; i != constraints.size(); ++i) {
        Real_T smallest(Inf), nextSmallest(Inf);
        for (Vertex_ID j = 0; j != constraints.size(); ++j) {
            if (constraints[i][j] == ALLOWED) {
                if (g.getEdge(i, j) < nextSmallest) {
                    nextSmallest = g.getEdge(i, j);
                    if (nextSmallest < smallest)
                        swap(smallest, nextSmallest);
                }
            }
            else if (constraints[i][j] == REQUIRED)
                lowerBound += g.getEdge(i, j);
        }
        if (numRequired[i] <= 1)
            lowerBound += smallest;
        if (numRequired[i] == 0)
            lowerBound += nextSmallest;
    }
//    cout << "lowerBound computed: " << lowerBound << endl;
}

vector<Branch::Vertex_ID> Branch::getTour() const {
    if (!tourFound)
        throw logic_error("Branch::getTour : Tour not found!");
//    cout << "Branch::getTour()" << endl;
//    printConstraints();
//    printNums();
    Vertex_ID from(0), to(0);
    vector<Vertex_ID> tour(constraints.size());
    do {
        for (Vertex_ID next = 0; next != constraints.size(); ++next) {
            if (next != from && constraints[to][next] == REQUIRED) {
                tour[to] = next;
                from = to;
                to = next;
                break;
            }
        }
    } while (to != 0);
    return tour;
}

void Branch::printConstraints() const {
    for (Vertex_ID i = 0; i != constraints.size(); ++i) {
        for (Vertex_ID j = 0; j != constraints[i].size(); ++j) {
            if (constraints[i][j] == ALLOWED)
                cout << "A ";
            else if (constraints[i][j] == REQUIRED)
                cout << "R ";
            else
                cout << "D ";
        }
        cout << endl;
    }
}

void Branch::printNums() const {
    ostream_iterator<size_t> out(cout, " ");
    cout << "Allowed:   ";
    copy(numAllowed.begin(), numAllowed.end(), out);
    cout << endl << "Required:  ";
    copy(numRequired.begin(), numRequired.end(), out);
    cout << endl;
}