/*
	Author:	James Pate Williams (c) 2000

	Branch and bound search algorithm from _Foundations
	of Constraint Satisfaction by E. P. K. Tsang. Section
	10.2.3 page 301. See Figure 10.1 page 304.
*/

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <vector>
using namespace std;

int BOUND = - 2000000000;

class Domain {
private:
	vector<int> data[5];
public:
	Domain(void) {
	}
	bool empty(int i) {
		return data[i].empty();
	}
	int getElement(int i, int j) {
		return data[i][j];
	}
	int getSize(int i) {
		return data[i].size();
	}
	void erase(int i, vector<int>::iterator vIterator) {
		data[i].erase(vIterator);
	}
	void push_back(int i, int x) {
		data[i].push_back(x);
	}
	vector<int>::iterator first(int i) {
		return data[i].begin();
	}
	vector<int>::iterator last(int i) {
		return data[i].end();
	}
};

int constraintsViolated(vector<int> compoundLabel) {
	int c = 0;

	if (compoundLabel[1] != - 1 && compoundLabel[0] != - 1)
		if (compoundLabel[1] == compoundLabel[0]) c++;
	if (compoundLabel[2] != - 1 && compoundLabel[1] != - 1)
		if (compoundLabel[2] != compoundLabel[1]) c++;
	if (compoundLabel[3] != - 1 && compoundLabel[2] != - 1)
		if (compoundLabel[3] >= compoundLabel[2]) c++;
	if (compoundLabel[4] != - 1 && compoundLabel[3] != - 1) 
		if (compoundLabel[4] == compoundLabel[3]) c++;
	return c;
}

int f(vector<int> compoundLabel) {
	int fValue = 0, i;

	for (i = 0; i < compoundLabel.size(); i++)
		fValue += compoundLabel[i];
	return fValue;
}

int h(vector<int> compoundLabel, Domain &D) {
	int hValue = 0, i, j, max;

	for (i = 0; i < compoundLabel.size(); i++)
		if (compoundLabel[i] != - 1)	
			hValue += compoundLabel[i];
	for (i = 0; i < 5; i++) {
		if (compoundLabel[i] == - 1) {
			if (D.getSize(i) != 0) {
				max = D.getElement(i, 0);
				for (j = 1; j < D.getSize(i); j++)
					if (D.getElement(i, j) > max)
						max = D.getElement(i, j);
				hValue += max;
			}
		}
	}
	return hValue;
}

void BNB(vector<int> unlabelled, vector<int> compoundLabel, Domain D,
	vector<int> &bestSoFar) {
	int fcl, v, x;

	//cout << "h(CL) = " << h(compoundLabel, D) << endl;
	//cout << "BOUND = " << BOUND << endl;
	if (unlabelled.empty()) {
		fcl = f(compoundLabel);
		cout << "f(compound label) = " << fcl << endl;
		for (int i = 0; i < compoundLabel.size(); i++)
			cout << compoundLabel[i] << ' ';
		cout << endl;
		if (fcl > BOUND) {
			BOUND = fcl;
			copy(compoundLabel.begin(), compoundLabel.end(), bestSoFar.begin());
		}
	}
	else if (h(compoundLabel, D) > BOUND) {
		x = unlabelled[rand() % unlabelled.size()];
		do {
			if (D.getSize(x) == 0) {
				cout << "domain is empty" << endl;
				exit(1);
			}	
			v = D.getElement(x, rand() % D.getSize(x));
			vector<int>::iterator vIterator = find(D.first(x), D.last(x), v);
			D.erase(x, vIterator);
			compoundLabel[x] = v;
			if (constraintsViolated(compoundLabel) == 0) {
				vIterator = find(unlabelled.begin(), unlabelled.end(), x);
				unlabelled.erase(vIterator);
				BNB(unlabelled, compoundLabel, D, bestSoFar);
				unlabelled.push_back(x);
			}
			else 
				compoundLabel[x] = - 1;
		} while (!D.empty(x));
	}
}

void BranchAndBound(vector<int> &bestSoFar, Domain D) {
	vector<int> compoundLabel(5, - 1), unlabelled;

	for (int i = 0; i < 5; i++)
		unlabelled.push_back(i);
	BNB(unlabelled, compoundLabel, D, bestSoFar); 
}

int main(void) {
	Domain D;
	vector<int> bestSoFar(5, - 1);

	srand(time(NULL));
	D.push_back(0, 4);
	D.push_back(0, 5);
	D.push_back(1, 3);
	D.push_back(1, 5);
	D.push_back(2, 3);
	D.push_back(2, 5);
	D.push_back(3, 2);
	D.push_back(3, 3);
	D.push_back(4, 1);
	D.push_back(4, 3);
	BranchAndBound(bestSoFar, D);
	cout << "f(best so far) = " << f(bestSoFar) << endl;
	for (int i = 0; i < bestSoFar.size(); i++)
		cout << bestSoFar[i] << ' ';
	cout << endl;
	return 0;
}