#include "io.hpp"

void read_problem(short int *W, short int *H, short int *blocks, short int *line_num, short int block_info[][5][3], short int line_info[][2][5]) {
	
	for(int i = 0; i < MAX_BLOCKS+1; i++) {
		for(int j = 0; j < 5; j++) {
			for(int k = 0; k < 3; k++) {
				block_info[i][j][k] = -1;
			}
		}
	}
	for(int i = 0; i < MAX_LINES+1; i++) {
		for(int j = 0; j < 2; j++) {
			for(int k = 0; k < 5; k++) {
				line_info[i][j][k] = -1;
			}
		}
	}
	*line_num = 0;
	
	int now_block = 0, count;
	short int size_x = -1, size_y = -1, now_x, now_y, num;
	while(1) {
		string line, tmp;
		string::size_type pos;
		
		if(!getline(cin,line)) break; // stdin
		if(line.find("\n") != string::npos || line.find("\r") != string::npos) {
			line.replace(line.length()-1, 1, ""); // Remove '\n' or '\r'
		}
		
		int len = line.length();
		if(len == 0) continue;
		
		if(line.find("SIZE") != string::npos) {
			replace(line.begin(), line.end(), 'X', ' ');
			istringstream iss(line);
			iss >> tmp >> *W >> *H;
			continue;
		}
		else if(line.find("BLOCK_NUM") != string::npos) {
			istringstream iss(line);
			iss >> tmp >> *blocks;
			continue;
		}
		else if(line.find("BLOCK") != string::npos) {
			now_block++;
			replace(line.begin(), line.end(), 'X', ' ');
			istringstream iss(line);
			iss >> tmp >> size_x >> size_y;
			now_y = 0;
			count = 1;
			block_info[now_block][0][0] = size_x;
			block_info[now_block][0][1] = size_y;
			continue;
		}
		
		// Replace ' ' -> ""
		pos = 0;
		while((pos = line.find(' ', pos)) != string::npos) {
			line.replace(pos, 1, "");
		}
		// Replace '+' -> "-1"
		pos = 0;
		while((pos = line.find('+', pos)) != string::npos) {
			line.replace(pos, 1, "-1");
		}
		// Replace ',' -> " "
		pos = 0;
		while((pos = line.find(',', pos)) != string::npos) {
			line.replace(pos, 1, " ");
		}
		
		istringstream iss(line);
		for(now_x = 0; now_x < size_x; now_x++) {
			iss >> num;
			if(num > 0) {
				block_info[now_block][count][0] = now_x;
				block_info[now_block][count][1] = now_y;
				block_info[now_block][count][2] = num;
				if(line_info[num][0][0] == -1) { line_info[num][0][0] = now_block; }
				else if(line_info[num][1][0] == -1) { line_info[num][1][0] = now_block; }
				else { cout << "Error(RE0): Line#" << num << endl; exit(1); }
				if(num > *line_num) { *line_num = num; }
				count++;
			}
			else if(num < 0) {
				block_info[now_block][count][0] = now_x;
				block_info[now_block][count][1] = now_y;
				block_info[now_block][count][2] = 0;
				count++;
			}
		}
		now_y++;
	}
	cout << "W: " << *W << ", H: " << *H << endl;
	
	/// Print block information ///
	cout << "== Block information ==" << endl;
	cout << "#Blocks = " << *blocks << endl;
	for(int i = 1; i <= *blocks; i++) {
		short int sx = block_info[i][0][0];
		short int sy = block_info[i][0][1];
		cout << "Block#" << i << ": (" << sx << ", " << sy << ")" << endl;
		
		if(sx == 1 && sy == 1) { // monomino
			short int tx = block_info[i][1][0];
			short int ty = block_info[i][1][1];
			short int tn = block_info[i][1][2];
			cout << "- (" << tx << ", " << ty << ") " << tn << endl;
		}
		else {
			for(int it = 1; it < 5; it++) {
				short int tx = block_info[i][it][0];
				short int ty = block_info[i][it][1];
				short int tn = block_info[i][it][2];
				cout << "- (" << tx << ", " << ty << ") " << tn << endl;
			}
		}
	}
	/// Print block information ///
}

void extract_line_info(short int line_num, short int blocks, short int block_info[][5][3], short int line_info[][2][5]) {
	
	short int lines_x[4], lines_y[4]; // # of nums in a block for X- & Y- axes
	for(int i = 1; i <= blocks; i++) {
		short int sx = block_info[i][0][0];
		short int sy = block_info[i][0][1];
		
		if(sx == 1 && sy == 1) { // monomino
			short int tx = block_info[i][1][0];
			short int ty = block_info[i][1][1];
			short int tn = block_info[i][1][2];
			
			if(tn == 0) continue;
			
			short int n_idx = 0;
			while(line_info[tn][n_idx][1] != -1) {
				n_idx++;
				if(n_idx >= 2) { cout << "Error(EL0): Line#" << tn << endl; exit(1); }
			}
			line_info[tn][n_idx][LE] = 2;
			line_info[tn][n_idx][TO] = 2;
			line_info[tn][n_idx][RI] = 2;
			line_info[tn][n_idx][BO] = 2;
			
			continue;
		}
		
		for(short int p = 0; p < 4; p++) lines_x[p] = 0;
		for(short int q = 0; q < 4; q++) lines_y[q] = 0;
		
		for(int it = 1; it < 5; it++) {
			short int tx = block_info[i][it][0];
			short int ty = block_info[i][it][1];
			short int tn = block_info[i][it][2];
			if(tn > 0) {
				lines_x[tx] += 1;
				lines_y[ty] += 1;
			}
		}
		
		for(int it = 1; it < 5; it++) {
			short int tx = block_info[i][it][0];
			short int ty = block_info[i][it][1];
			short int tn = block_info[i][it][2];
			
			if(tn == 0) continue;
			
			short int n_idx = 0;
			while(line_info[tn][n_idx][1] != -1) {
				n_idx++;
				if(n_idx >= 2) { cout << "Error(EL1): Line#" << tn << endl; exit(1); }
			}
			
			short int compe_cost, wall_cost;
			// Map to left
			compe_cost = 2;
			compe_cost += lines_x[tx] - 1;
			for(short int p = tx - 1; p >= 0; p--) { compe_cost += lines_x[p] * 2; }
			wall_cost = 1;
			for(int it2 = 1; it2 < 5; it2++) {
				short int cx = block_info[i][it2][0];
				short int cy = block_info[i][it2][1];
				if(cx == tx && cy == ty) continue;
				if(cy == ty && cx < tx) {
					if(sx == 2 && sy == 3 && ty == 1) {
						wall_cost = 4;
					}
					else {
						wall_cost = 2;
					}
				}
			}
			line_info[tn][n_idx][LE] = compe_cost * wall_cost;
			
			// Map to top
			compe_cost = 2;
			compe_cost += lines_y[ty] - 1;
			for(short int q = ty - 1; q >= 0; q--) { compe_cost += lines_y[q] * 2; }
			wall_cost = 1;
			for(int it2 = 1; it2 < 5; it2++) {
				short int cx = block_info[i][it2][0];
				short int cy = block_info[i][it2][1];
				if(cx == tx && cy == ty) continue;
				if(cx == tx && cy < ty) {
					if(sx == 3 && sy == 2 && tx == 1) {
						wall_cost = 4;
					}
					else {
						wall_cost = 2;
					}
				}
			}
			line_info[tn][n_idx][TO] = compe_cost * wall_cost;
			
			// Map to right
			compe_cost = 2;
			compe_cost += lines_x[tx] - 1;
			for(short int p = tx + 1; p < sx; p++) { compe_cost += lines_x[p] * 2; }
			wall_cost = 1;
			for(int it2 = 1; it2 < 5; it2++) {
				short int cx = block_info[i][it2][0];
				short int cy = block_info[i][it2][1];
				if(cx == tx && cy == ty) continue;
				if(cy == ty && cx > tx) {
					if(sx == 2 && sy == 3 && ty == 1) {
						wall_cost = 4;
					}
					else {
						wall_cost = 2;
					}
				}
			}
			line_info[tn][n_idx][RI] = compe_cost * wall_cost;
			
			// Map to bottom
			compe_cost = 2;
			compe_cost += lines_y[ty] - 1;
			for(short int q = ty + 1; q < sy; q++) { compe_cost += lines_y[q] * 2; }
			wall_cost = 1;
			for(int it2 = 1; it2 < 5; it2++) {
				short int cx = block_info[i][it2][0];
				short int cy = block_info[i][it2][1];
				if(cx == tx && cy == ty) continue;
				if(cx == tx && cy > ty) {
					if(sx == 3 && sy == 2 && tx == 1) {
						wall_cost = 4;
					}
					else {
						wall_cost = 2;
					}
				}
			}
			line_info[tn][n_idx][BO] = compe_cost * wall_cost;
		}
	}
	
	/// Print line information ///
	cout << "== Line information ==" << endl;
	cout << "#Lines = " << line_num << endl;
	for(int l = 1; l <= line_num; l++) {
		short int block1 = line_info[l][0][0];
		short int block2 = line_info[l][1][0];
		cout << "Line#" << l << ": ";
		cout << "Block#" << block1 << "(";
		for(int i = 1; i < 5; i++) {
			cout << (float)line_info[l][0][i] / 2;
			if(i != 4) { cout << ", "; }
		}
		cout << "), ";
		cout << "Block#" << block2 << "(";
		for(int i = 1; i < 5; i++) {
			cout << (float)line_info[l][1][i] / 2;
			if(i != 4) { cout << ", "; }
		}
		cout << ")" << endl;
	}
	/// Print line information ///
}

static unsigned int lfsr, lfsr_x, lfsr_y;

static void lfsr_random_init(unsigned int seed, unsigned int seed_x, unsigned int seed_y) {
	lfsr = seed;
	lfsr_x = seed_x;
	lfsr_y = seed_y;
}

static unsigned int lfsr_random() {
	bool b_32 = false, b_22 = false, b_2 = false, b_1 = false;
	if((lfsr >>  0) % 2 == 1) b_32 = true;
	if((lfsr >> 10) % 2 == 1) b_22 = true;
	if((lfsr >> 30) % 2 == 1) b_2 = true;
	if((lfsr >> 31) % 2 == 1) b_1 = true;
	bool new_bit = b_32 ^ b_22 ^ b_2 ^ b_1;
	lfsr >>= 1;
	if(new_bit) lfsr |= 0x80000000;
	return lfsr;
}
static unsigned int lfsr_x_random() {
	bool b_32 = false, b_22 = false, b_2 = false, b_1 = false;
	if((lfsr_x >>  0) % 2 == 1) b_32 = true;
	if((lfsr_x >> 10) % 2 == 1) b_22 = true;
	if((lfsr_x >> 30) % 2 == 1) b_2 = true;
	if((lfsr_x >> 31) % 2 == 1) b_1 = true;
	bool new_bit = b_32 ^ b_22 ^ b_2 ^ b_1;
	lfsr_x >>= 1;
	if(new_bit) lfsr_x |= 0x80000000;
	return lfsr_x;
}
static unsigned int lfsr_y_random() {
	bool b_32 = false, b_22 = false, b_2 = false, b_1 = false;
	if((lfsr_y >>  0) % 2 == 1) b_32 = true;
	if((lfsr_y >> 10) % 2 == 1) b_22 = true;
	if((lfsr_y >> 30) % 2 == 1) b_2 = true;
	if((lfsr_y >> 31) % 2 == 1) b_1 = true;
	bool new_bit = b_32 ^ b_22 ^ b_2 ^ b_1;
	lfsr_y >>= 1;
	if(new_bit) lfsr_y |= 0x80000000;
	return lfsr_y;
}

float calcPlaceCost(short int line_num, short int line_info[MAX_LINES+1][2][5], short int block_place_global[MAX_BLOCKS+1][2]) {

	short int block1, block2; // block idx
	short int x1, y1; // 1st block
	short int x2, y2; // 2nd block
	short int delta_x, delta_y;
	// delta_x > 0: 1st block is located in the East of 2nd block
	// delta_x < 0: 1st block is located in the West of 2nd block
	// delta_y > 0: 1st block is located in the South of 2nd block
	// delta_y < 0: 1st block is located in the North of 2nd block
	short int dist_x, dist_y; // distance between 2 blocks
	short int dir_x1, dir_x2; // X-direction from 1st block to 2nd block and ...
	short int dir_y1, dir_y2; // Y-direction from 1st block to 2nd block and ...

	int cost = 0;
	for(int l = 1; l <= line_num; l++) {
		block1 = line_info[l][0][0]; // 1st block including line#L
		block2 = line_info[l][1][0]; // 2nd block including line#L
		x1 = block_place_global[block1][0];
		y1 = block_place_global[block1][1];
		x2 = block_place_global[block2][0];
		y2 = block_place_global[block2][1];
		delta_x = x1 - x2;
		delta_y = y1 - y2;
		//dist_x = abs(delta_x);
		//dist_y = abs(delta_y);

		dir_x1 = 0;
		dir_x2 = 0;
		dist_x = 0;
		if(delta_x > 0) {
			dist_x = delta_x;
			dir_x1 = line_info[l][0][1];
			dir_x2 = line_info[l][1][3];
		}
		else if(delta_x < 0) {
			dist_x = delta_x * (-1);
			dir_x1 = line_info[l][0][3];
			dir_x2 = line_info[l][1][1];
		}
		dir_y1 = 0;
		dir_y2 = 0;
		dist_y = 0;
		if(delta_y > 0) {
			dist_y = delta_y;
			dir_y1 = line_info[l][0][2];
			dir_y2 = line_info[l][1][4];
		}
		else if(delta_y < 0) {
			dist_y = delta_y * (-1);
			dir_y1 = line_info[l][0][4];
			dir_y2 = line_info[l][1][2];
		}
		cost += (dist_x * dir_x1 * dir_x2 + dist_y * dir_y1 * dir_y2);
	}

	return (float)cost / 4;
}

void global_placement(unsigned int seed[3], short int W, short int H, short int line_num, short int blocks, short int block_info[MAX_BLOCKS+1][5][3], short int line_info[MAX_LINES+1][2][5], short int block_place_global[MAX_BLOCKS+1][2]) {

	lfsr_random_init(seed[0], seed[1], seed[2]);

	cout << "== Global placement ==" << endl;
	short int sx_sum = 0, sy_sum = 0;
	for(int i = 1; i <= blocks; i++) {
		sx_sum += block_info[i][0][0]; // block size (x)
		sy_sum += block_info[i][0][1]; // block size (y)
	}
	// define #slots
	short int max_x = W * blocks / sx_sum - 1;
	short int max_y = H * blocks / sy_sum - 1;
	while(((max_x + 1) * (max_y + 1)) < blocks) {
		max_x += 1;
		max_y += 1;
	}
	cout << "#Slots for X-axis: " << max_x + 1 << endl;
	cout << "#Slots for Y-axis: " << max_y + 1 << endl;

	// init. placement on global slot
	short int global_slot[SLOT_MAX_SIZE][SLOT_MAX_SIZE];
	short int i = 1;
	for(short int q = 0; q <= max_y; q++) {
		for(short int p = 0; p <= max_x; p++) {
			if(i <= blocks) {
				block_place_global[i][0] = p;
				block_place_global[i][1] = q;
				global_slot[q][p] = i;
				i++;
			}
			else {
				global_slot[q][p] = 0;
			}
		}
	}

	short int line_info_buf[MAX_LINES+1][2][5];
	for(int l = 1; l <= line_num; l++) {
		line_info_buf[l][0][0] = line_info[l][0][0];
		line_info_buf[l][0][1] = line_info[l][0][1];
		line_info_buf[l][0][2] = line_info[l][0][2];
		line_info_buf[l][0][3] = line_info[l][0][3];
		line_info_buf[l][0][4] = line_info[l][0][4];
		line_info_buf[l][1][0] = line_info[l][1][0];
		line_info_buf[l][1][1] = line_info[l][1][1];
		line_info_buf[l][1][2] = line_info[l][1][2];
		line_info_buf[l][1][3] = line_info[l][1][3];
		line_info_buf[l][1][4] = line_info[l][1][4];
	}

	// cost calculation (may be inefficient)
	float cost = calcPlaceCost(line_num, line_info_buf, block_place_global);
	float init_cost = cost;
	cout << "Cost = " << cost << " -> ";

	// SA setup
	float temperature = TEMP_S;
	float delta = powf(((float)(TEMP_E)/(float)(TEMP_S)), (1./(float)(SA_O)));

	// SA
	for(int counter = 0; counter < SA_O; counter++) {
		temperature *= delta; // Update temperature

		// trgt_i, trgt_j: moved block idx (trgt_j == 0, no block is placed on slot(j_x,j_y))
		// i_x, i_y, j_x, j_y
		for(int counter_in = 0; counter_in < SA_I; counter_in++) {
			short int trgt_i = lfsr_random() % blocks + 1;
			short int i_x = block_place_global[trgt_i][0];
			short int i_y = block_place_global[trgt_i][1];
			short int j_x = lfsr_x_random() % SLOT_MAX_SIZE;
			short int j_y = lfsr_y_random() % SLOT_MAX_SIZE;
			if(j_x > max_x || j_y > max_y) continue;
			short int trgt_j = global_slot[j_y][j_x]; // slot -> block

			block_place_global[trgt_i][0] = j_x;
			block_place_global[trgt_i][1] = j_y;
			global_slot[j_y][j_x] = trgt_i;
			block_place_global[trgt_j][0] = i_x;
			block_place_global[trgt_j][1] = i_y;
			global_slot[i_y][i_x] = trgt_j;

			float new_cost = calcPlaceCost(line_num, line_info_buf, block_place_global);

			if(new_cost > cost && (float)lfsr_random()/LFSR_RAND_MAX > expf(-(new_cost-cost)/temperature)) {
				block_place_global[trgt_i][0] = i_x;
				block_place_global[trgt_i][1] = i_y;
				global_slot[i_y][i_x] = trgt_i;
				block_place_global[trgt_j][0] = j_x;
				block_place_global[trgt_j][1] = j_y;
				global_slot[j_y][j_x] = trgt_j;
			}
			else if(new_cost != cost) { cost = new_cost; }
		}
	}

	cout << cost << endl;

	seed[0] = lfsr;
	seed[1] = lfsr_x;
	seed[2] = lfsr_y;
}