// File:            map.cpp
// ---------------------------------------------------------------------
// Author:          Russell Lowke,  russ@mocaz.com
// TF:              Francis Crick
// Date:            7/26/2002
// Assignment:		Unit 6 Hard supplementary #6
// Version:         1
//
//


#include <iostream>
#include <iomanip>
#include <fstream>
#include "bitset.hpp"


// constants
const int MAXNAME = 16;
const int MAXSTATE = 50;

// the colors
enum      COLOR {red, black, green, blue};
const int NUM_COLORS = 4;

// structure for info about a state
struct stateinfo {
    char name[MAXNAME];
    bitset borders;
};

// global variables
bitset colored[NUM_COLORS];
stateinfo state[MAXSTATE + 1];


//
// init_map -- read in the map info from the specified ifstream
// and initialize the bitsets, returning the number of states
// in the reference parameter num_states
//
void init_map(ifstream& infile, int& num_states)
{
	char temp_name[MAXNAME];
	int num;

	num_states = 0;

	// Read in the map info and initialize the stateinfo structs 
	while (true) {
		// Check if there is more state info.
		infile >> temp_name;
		if (infile.eof())
			break;

		// If so, initialize the next entry of the state array.
		num_states++;
		strcpy(state[num_states].name, temp_name);
		state[num_states].borders.set_size(MAXSTATE + 1);

		//
		// Read in the border info, displaying it
		// and building the bitset of borders.
		//
		cout << "\t" << num_states << " " << temp_name;
		cout << " is bordered by ";
		do {
			infile >> num;
			cout << num << " ";

			state[num_states].borders.include(num);
		} while (infile.peek() != '\n');

		cout << '\n';
	}

	// Initialize the colored sets.
	for (COLOR color = red; color <= blue; color = (COLOR)((int)color + 1))
		colored[color].set_size(MAXSTATE + 1);
}

//
// legal_color -- determines if the specified state can be legally
// colored with the specified color, returning true or false as
// appropriate.
//
bool legal_color(COLOR color, int state_num)
{
	for(int i = 0; i < MAXSTATE; i++) {
		if ( state[state_num].borders.member(i) ) {
			if ( colored[color].member(i) ) {
				return false;
			}
		}
	}
	
	return true;
}

//
// add_color - color the specified state with the specified color
//
void add_color(COLOR color, int state_num)
{
	colored[color].include(state_num);
}

//
// remove_color - remove the specified color from the specified state
//
void remove_color(COLOR color, int state_num)
{
	colored[color].exclude(state_num);
}

//
// print_solution - print out the list of states and their colors
//
void print_solution(int num_states)
{		
	cout << "\nHere's the solution:\n";
	for (int state_num = 1; state_num <= num_states; state_num++) {
		for (COLOR color = red; color <= blue;
				color = (COLOR)((int)color + 1)) {
			if (colored[color].member(state_num)) {
				cout << "\t" << state_num << " ";
				cout << state[state_num].name << "\t";
				cout << (color == red ? "red" :
						color == black ? "black" :
						color == green ? "green" :
						"blue");
				cout << "\n";
				break;
			}
		}
    }
}

		
//
// search_for_coloring - generates solutions to the map-coloring
// problem using recursive backtracking.
//
// This function should return true if a solution has been found,
// or false if backtracking is needed.  You should *not* use exit().
//
bool search_for_coloring(int state_num, int num_states)
{
	for (COLOR color = red; color <= blue; color = (COLOR)((int)color + 1)) {
		if ( legal_color(color, state_num) ) {
			add_color(color, state_num);
			
			if ( state_num == num_states ) {		// base case
				return true;
			} else {
				if ( search_for_coloring(state_num + 1, num_states) ) {
					return true;
				}
			}
			
			// if we make it here, solution failed
			remove_color(color, state_num);
		}
	}

	return false;
}


int main()
{
	char filename[128];
	int num_states;
	bool success;

	cout << "Name of map file? ";
	cin >> filename;
	ifstream infile(filename);

	init_map(infile, num_states);
	
	// first call to search
	search_for_coloring(0, num_states);
	
	print_solution(num_states);
	exit(success);
}
