#include <cassert>
#include <iostream>

#include <gp-bnb/bnb.hpp>

static constexpr bool verbose = false;

namespace gp_bnb {

// --------------------------------------------------------------------------------------
// trail_state implementation.
// --------------------------------------------------------------------------------------

void trail_state::push_node(node_id node, subgraph alt) {
	stack_.push_back({node, alt});
}

void trail_state::pop() {
	stack_.pop_back();
}

// --------------------------------------------------------------------------------------
// solver implementation.
// --------------------------------------------------------------------------------------

solver::solver(graph& g) : graph_(g), partition_(partition{g}) {
}

void solver::solve() {
	//anfangs lower bound?
	best_objective_ = graph_.num_nodes();


	while(true) {
		//falls current sol schlechter als bisher beste lösung: 
		//zähle schritte bis zur nächsten alternative und
		
		if(partition_.current_objective() >= best_objective_) {
			int i = trail_.length() - 1;
			while(true) {
				if(i < 0)
					return;
				// Only backtrack to assignments that have an alternative.
				if(trail_.alternative_at(i) != subgraph::none)
					break;
				i--;
			}

			auto node = trail_.node_at(i);
			auto alt = trail_.alternative_at(i);
			//backtracke soviele schritte und
			while((int)trail_.length() > i){
				backtrack();
			}
			//wende dann die entsprechende alternative an
			expand(node, alt);
		}else if(trail_.length() == graph_.num_nodes()) {
			//falls wir an einem blatt im suchbaum sind
			// Memorize the new solution.
			best_solution_.resize(graph_.num_nodes());
			for(node_id node = 0; node < graph_.num_nodes(); node++){
				best_solution_[node] = partition_.assigned_subgraph_of(node+1);
			}
			best_objective_ = partition_.current_objective();
			std::cerr << "Solution improved to k = " << best_objective_ << std::endl;
		}else{
			//sonst expandiere suchbaum weiter
			int node = trail_.length() +1;
			expand(node, next_possible_subgraph(node, subgraph::sg_a));
		}
	}
}

void solver::expand(node_id node, subgraph sg) {
	assert(sg == subgraph::sg_a || sg == subgraph::sg_b);
	// Search for an alternative BEFORE assigning the node.
	// Because the node is not assigned, this calculation is easy.
	subgraph alt;
	if(partition_.num_nodes_of(subgraph::sg_a) == 0 && partition_.num_nodes_of(subgraph::sg_b)){
		alt = subgraph::none;
	}else{
		alt = next_possible_subgraph(node, static_cast<subgraph>(sg +2));
	}
	if(verbose) {
		std::cerr << "Assign node " << node << " to subgraph " << sg << std::endl;
		std::cerr << "    Alternative " << alt << std::endl;
	}
	
	partition_.assign_node(node, sg);
	trail_.push_node(node, alt);
}

void solver::backtrack() {
	assert(trail_.length());

	auto node = trail_.node_at(trail_.length() - 1);
	if(verbose)
		std::cout << "Unassign node " << node << std::endl;

	trail_.pop();
	partition_.unassign_node(node);
}

// Finds the next partition in which the given node can be placed.
subgraph solver::next_possible_subgraph(node_id node, subgraph m) {
	// This function is only correct if the node is not assigned yet.
	assert(partition_.assigned_subgraph_of(node) == subgraph::none);

	subgraph sg = m;
	
	while(sg <= 1){
		if((partition_.num_nodes_of(sg) * 2) < graph_.num_nodes())
			return sg;
		else
		{
			sg = static_cast<subgraph>(sg+2);
		}
	}

	return subgraph::none;
}

} // namespace gp_bnb