/*
	This file is part of ct.

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with ct. If not, see <https://www.gnu.org/licenses/>.
*/

#include "actions.h"

// ===================================================================
// Helper method declarations
// ===================================================================

#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))

#define CLR_STONE NUM_MASK

static inline void
lq_append(action_lq_t *lq, const enum A_TYPE type,
           const int8_t loc, const uint8_t data0,
           const uint8_t data1);

static inline void
lq_prepend(action_lq_t *lq, const enum A_TYPE type,
            const int8_t loc, const uint8_t data0,
            const uint8_t data1);

static inline void
inline_next_ply(void);

static inline void
inline_prev_ply(void);

// ===================================================================
// Exported method implementations
// ===================================================================

int action_move_to_front(const action_t action, action_lq_t *lq) {
	for (int k=lq->i_f; k<lq->i_b; k++) {
		if (lq->actions[k] == action) {
			for (int j=k; j>lq->i_f; j--) {
				lq->actions[j] = lq->actions[j-1];
			}
			lq->actions[lq->i_f] = action;
			return EXIT_SUCCESS;
		}
	}
	return EXIT_FAILURE;
}

action_lq_t *action_lq_copy_with_mtf(action_lq_t *lq, action_t front) {
	// Normalise, empty list ---> null
	if (lq == NULL || lq->length == 0) return NULL;
	action_lq_t *copy = malloc(sizeof(action_lq_t));

	copy->length = lq->length;
	copy->i_b = lq->i_b;
	copy->i_f = lq->i_f;

	for (int source=lq->i_f, dest=copy->i_f+1;
	     source < lq->i_b; source++, dest++) {
		if (lq->actions[source] == front) {
			source++;
			if (source >= lq->i_b) break;
		}
		copy->actions[dest] = lq->actions[source];
	}

	copy->actions[copy->i_f] = front;

	return copy;
}

void action_lq_free(action_lq_t *lq) {
	free(lq);
}

// Keep track of move offsets
int8_t move_deltas[4];

void action_lq_init(void) {
	move_deltas[0] = +board_size;
	move_deltas[1] = -board_size;
	move_deltas[2] = -1;
	move_deltas[3] = +1;
}

// We bias place over move by prepending place actions and appending
// move actions to the generated list
action_lq_t *action_lq_generate(void) {
	action_lq_t *lq = malloc(sizeof(action_lq_t));

	// TODO: trap errno
	lq->length = 0;
	lq->i_f = ACTION_AR_LEN;
	lq->i_b = ACTION_AR_LEN;

	/*
	 * The check for whether it's a black piece to be played is actually
	 *     black = (ply < 2) ? (ply==1) : (ply & 1),
	 * but material will always be sufficient in ply < 2 so we might as
	 * well save on the conditional.
	 */

	const uint8_t material = (ply & 1) ? black_count : white_count,
		flat = material & 0x7F,
		cap = ((ply >= 2) && (material & 0x80)),
		standing = ((ply >= 2) && flat);

	// Step across the board
	for (int row = 0; row < board_size; row++) {
		for (int col = 0; col < board_size; col++) {
			// We'll need these at various points: the location of this
			// square and the maximum number of stones we could pick up
			const int loc = THE_COORDS(col, row);
			const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size);

			// Only try moves after CPS and if the colour is correct
			if (count) {
				if (ply >= 2 && ((colours[loc] & 1) == current_colour)) {

					// Pre-compute end-stops and crushes
					uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};

					// These are upper bounds, not counting walls and such.
					// UP DOWN LEFT RIGHT
					end_stops[0] = DANGER_MIN(board_size - row - 1, count);
					end_stops[1] = DANGER_MIN(row, count);
					end_stops[2] = DANGER_MIN(col, count);
					end_stops[3] = DANGER_MIN(board_size - col - 1, count);

					// Now we check for caps and walls
					const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
					for (int d = 0; d < 4; d++){
						const int delta = move_deltas[d];
						const int stop = end_stops[d];
						end_stops[d] = 0;
						for (int k = 1; k <= stop; k++) {
							const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
							if (stone == STONE_STANDING) {
								if (cap_top) {
									crushes[d] = 0xFF;
									end_stops[d]++;
								}
								break;
							} else if (stone == STONE_CAPSTONE) {
								break;
							}
							end_stops[d]++;
						}
					}
					/*
					 * For each direction, generate all possible ordered integer
					 * partitions of 1 ≤ num ≤ count whose number of summands is
					 * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we
					 * write summands as steps.
					 *
					 * We exploit the `gaps' bijection here and elsewhere
					 * between ordered {integer partitions of n with s summands}
					 * and {binary strings of length n-1 with s-1 set bits}.
					 */
					for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) {
						for (uint8_t num = 1; num <= count; num++) {
							for (uint8_t steps = 1;
									 steps <= end_stops[dir] && steps <= num;
									 steps++) {
								uint8_t gaps =
									((1<<(board_size - 2)) - 1) >> (board_size-steps-1);
								// For 5x5 this givess 0b0000[0XXX] where steps-1 of
								// those X's are 1s (starting with LSB) because 4-1=3
								// and 5-1=4
								do  {
									/*
									 * We skip the partition if it calls for multiple
									 * stones at the end with a crush.
									 */
									const uint8_t last_drop_check =
										(num > 1) ? (gaps & (1 << (num - 2))) : 1;
									if (crushes[dir] == 0 || last_drop_check) {
										// We have to record a crush!
										const uint8_t crush =
											(steps == end_stops[dir]) && crushes[dir];
										// Store the move

										lq_append(lq, A_MOVE, loc,
										           (crush << 7) | gaps,
										           (dir<<4) | num);
									}
									/*
									 * With thanks to
									 * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
									 * we have the following magic to generate the next
									 * permutation of steps-many set bits
									 */
									uint8_t t = (gaps | (gaps - 1));
									gaps = (t + 1)
										| (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
								} while (gaps && (gaps + 1 <= (1 << (num - 1))));
							}
						}
					}
				}
			} // end of if (count) { ... }
			else if (material) {
				// Empty square, generate placements
				if (flat) {
					lq_prepend(lq, A_PLACE, loc, STONE_FLAT, 0);
					if (standing)
						lq_prepend(lq, A_PLACE, loc, STONE_STANDING,0);
				}
				if (cap)
					lq_prepend(lq, A_PLACE, loc, STONE_CAPSTONE, 0);
			}
		}
	}
	return lq;
}

void action_take(const action_t action) {
	const int8_t loc = A_GET_LOC(action);
	if (A_GET_TYPE(action) == A_PLACE) {
		const uint8_t black = (current_colour == C_BLACK);
		switch (A_GET_DATA0(action)) {
			case STONE_FLAT: {
				if (black) black_count--;
				else white_count--;
				colours[loc] = current_colour;
				celldat[loc] = NUM_INC | STONE_FLAT;
				break;
			}
			case STONE_STANDING:  {
				if (black) black_count--;
				else white_count--;
				colours[loc] = current_colour;
				celldat[loc] = NUM_INC | STONE_STANDING;
				break;
			}
			default: {
				if (black) black_count &= 0x7F;
				else white_count &= 0x7F;
				colours[loc] = current_colour;
				celldat[loc] = NUM_INC | STONE_CAPSTONE;
				break;
			}
		}
	} else {
		/*
		 * See the discussion around line 135 for an explanation of the
		 * encoding. Here we are not interested in whether we crushed, it
		 * will work out by anyway because we overwrite the top stone
		 * type. See (*) later for when we do need to know.
		 */
		const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
			num = A_GET_DATA1(action) & 0x0F, // unpack
			dir = A_GET_DATA1(action) >> 4;
		int8_t delta = move_deltas[dir];

		// Use the Kernighan method to count the set bits
		int8_t steps = 1;
		for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1;

		// Move top stone type to destination
		celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing
		celldat[loc+steps*delta] |= STONE_AT(loc);
		celldat[loc] &= CLR_STONE;
		celldat[loc] |= STONE_FLAT; // should be optimised out

		uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important
																								 // what negative
																								 // shifts do here, we
																								 // don't use gap_bit
																								 // if num < 2
		// move stuff starting at destination
		for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) {
			// We took a step, move everything over so far
			if (gaps & gap_bit) {
				colours[loc+steps*delta] <<= total;
				colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1);
				colours[loc] >>= total;
				celldat[loc+steps*delta] += total*NUM_INC;
				celldat[loc] -= total*NUM_INC;
				// Reset for next step
				total = 0;
				steps--;
			}
		}
		// Move what remains (steps == 1 here always, so we simplify)
		colours[loc+delta] <<= total;
		colours[loc+delta] |= colours[loc] & ((1 << total) - 1);
		colours[loc] >>= total;
		celldat[loc+delta] += total*NUM_INC;
		celldat[loc] -= total*NUM_INC;
	}
	// Next ply
	inline_next_ply();
}

void action_undo(const action_t action) {
	// Previous ply
	inline_prev_ply();

	const int8_t loc = A_GET_LOC(action);
	if (A_GET_TYPE(action) == A_PLACE) {
		const uint8_t black = (current_colour == C_BLACK);
		celldat[loc] = 0;
		if (A_GET_DATA0(action) == STONE_CAPSTONE) {
			if (black) black_count |= 0x80;
			else white_count |= 0x80;
		} else {
			if (black) black_count++;
			else white_count++;
		}
	} else {
		// See action_take for comments, this is the time reversal, but
		// there is one caveat -- undoing a crush! (*)
		const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
			crush = A_GET_DATA0(action) & 0x80,
			num = A_GET_DATA1(action) & 0x0F,
			dir = A_GET_DATA1(action) >> 4;
		const int8_t delta = move_deltas[dir];

		int8_t steps = 1;
		uint8_t gap_bit = 1, total = 1;
		for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
			if (gaps & gap_bit) {
				colours[loc] <<= total;
				colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
				colours[loc+steps*delta] >>= total;
				celldat[loc] += total*NUM_INC;
				celldat[loc+steps*delta] -= total*NUM_INC;
				total = 0;
				steps++;
			}
		}
		colours[loc] <<= total;
		colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
		colours[loc+steps*delta] >>= total;

		celldat[loc] += total*NUM_INC;
		// celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
		celldat[loc] |= STONE_AT(loc+steps*delta);
		celldat[loc+steps*delta] -= total*NUM_INC;
		celldat[loc+steps*delta] &= CLR_STONE;
		if (crush) {
			celldat[loc+steps*delta] |= STONE_STANDING;
		} else {
			celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
		}
	}
}

void action_to_ptn(const action_t action, char* out_ptn) {
	const int8_t loc = A_GET_LOC(action);
	if (A_GET_TYPE(action) == A_PLACE) {
		generate_place(loc, A_GET_DATA0(action), out_ptn);
	} else {
		const uint8_t gaps = A_GET_DATA0(action) & 0x7F,
			num = A_GET_DATA1(action) & 0x0F, // unpack
			dir = A_GET_DATA1(action) >> 4;

		uint8_t drops[board_size]; // we only ever need board_size-1 in
															 // drops actually, the last spot is to
															 // skip a bounds check at (**)
		uint8_t mask = 1, steps = 0;
		// Translate to a drop sequence
		drops[0] = 1; mask = 1;
		for (uint8_t d = 1; d < num; d++) {
			if (gaps & mask) {
				steps++;
				drops[steps] = 1; // (**) no bounds check
			} else {
				drops[steps] += 1;
			}
			mask <<= 1;
		}
		generate_move(loc, dir, steps+1, drops, out_ptn);
	}
}

// ===================================================================
// Helper method implementations
// ===================================================================

static inline void
lq_append(action_lq_t *lq, const enum A_TYPE type,
           const int8_t loc, const uint8_t data0,
           const uint8_t data1) {
	lq->actions[lq->i_b++] = A_BUILD(type, loc, data0, data1);
	lq->length++;
}

static inline void
lq_prepend(action_lq_t *lq, const enum A_TYPE type,
            const int8_t loc, const uint8_t data0,
            const uint8_t data1) {
	lq->actions[--lq->i_f] = A_BUILD(type, loc, data0, data1);
	lq->length++;
}

static inline void
inline_next_ply(void) {
	ply++;
	if (ply == 2) {
		current_colour = C_WHITE;
	} else {
		if (current_colour == C_BLACK) current_colour = C_WHITE;
		else current_colour = C_BLACK;
	}
}

static inline void
inline_prev_ply(void) {
	if (ply>0) ply--;
	if (ply == 1) {
		current_colour = C_WHITE;
	} else {
		if (current_colour == C_BLACK) current_colour = C_WHITE;
		else current_colour = C_BLACK;
	}
}