/*
 * at_most_one.c
 *
 *  Created on: 26/03/2017
 *      Author: pedro
 */

#ifndef __OPENCL_VERSION__

#include <stddef.h>
#include <stdio.h>

#include "at_most_one.h"

#include "../bitmaps.h"
#include "../config.h"
#include "../variables.h"

#endif

#include "../kernels/cl_aux_functions.h"
#if CL_D_TYPE == CL_BITMAP
#include "../kernels/cl_bitmaps.h"
#elif CL_D_TYPE == CL_INTERVAL
#include  "../kernels/cl_intervals.h"
#endif
#include "../kernels/cl_constraints.h"
#include "../kernels/cl_variables.h"
#include "../kernels/cl_ttl.h"

#ifndef __OPENCL_VERSION__

/*
 * Creates a new constraint of the at_most_one type and return the constraint ID
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|≤1
 * S_ids - vector with the ID of the variables of all the sets, ordered by set
 * N_vs - number of variables on each set, per set order (c)
 * n_sets - number of sets
 */
unsigned int c_at_most_one(unsigned int* S_ids, int* N_vs, unsigned int n_sets) {
	unsigned int n_vs, i;

	// set to include in kernel compilation
	USE_CS[AT_MOST_ONE] = 1;
	USE_NON_CS_REIFI[AT_MOST_ONE] = 1;

	n_vs = 0;
	for (i = 0; i < n_sets; i++) {
		n_vs += (unsigned int)N_vs[i];
	}

	unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));

	for (i = 0; i < n_vs; i++) {
		c_vs[i] = S_ids[i];
	}

	// creates a new generic constraint
	unsigned int c_id = c_new(c_vs, n_vs, N_vs, n_sets, -1);

	// pointers to this type of constraint functions
	CS[c_id].kind = AT_MOST_ONE;
	CS[c_id].check_sol_f = &at_most_one_check;
	CS[c_id].constant_val = (int)n_sets;

	free(c_vs);

	return c_id;
}

/*
 * Creates a new reified constraint of the at_most_one type and return the constraint ID
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|≤1
 * S_ids - vector with the ID of the variables of all the sets, ordered by set
 * N_vs - number of variables on each set, per set order (c)
 * n_sets - number of sets
 * reif_v_id - ID of the reification variable
 */
unsigned int c_at_most_one_reif(unsigned int* S_ids, int* N_vs, unsigned int n_sets, int reif_v_id) {
	unsigned int n_vs, i;

	if (VS[reif_v_id].max > 1) {
		v_del_gt(&VS[reif_v_id], 1);

		if (VS[reif_v_id].n_vals == 0) {
			fprintf(stderr, "\nError: Constraint AT_MOST_ONE_REIF makes model inconsistent at creation:\n");
			exit(-1);
		}
	}

	// set to include in kernel compilation
	USE_CS[AT_MOST_ONE] = 1;
	USE_CS_REIFI[AT_MOST_ONE] = 1;

	n_vs = 0;
	for (i = 0; i < n_sets; i++) {
		n_vs += (unsigned int)N_vs[i];
	}

	unsigned int* c_vs = malloc(n_vs * sizeof(unsigned int));

	for (i = 0; i < n_vs; i++) {
		c_vs[i] = S_ids[i];
	}

	// creates a new generic constraint
	unsigned int c_id = c_new(c_vs, n_vs, N_vs, n_sets, reif_v_id);

	// pointers to this type of constraint functions
	CS[c_id].kind = AT_MOST_ONE;
	CS[c_id].check_sol_f = &at_most_one_check;
	CS[c_id].constant_val = (int)n_sets;

	free(c_vs);

	return c_id;
}

/*
 * Return true if the at_most_one constraint is respected or false if not
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|≤1
 * c - constraint to check if is respected
 * explored - if the CSP was already explored, which mean that all the variables must already be singletons
 * */
bool at_most_one_check(constr* c, bool explored) {
	int* cards = c->c_consts;
	var** sets = c->c_vs;
	int n_sets = c->constant_val;
	unsigned int v_iter1;
	unsigned int v_iter2;
	unsigned int vals_eq;
	int i, j, k, l;

	// if any variable have more than one value
#if CHECK_SOL_N_VALS
	for (i = 0; i < c->n_c_vs; i++) {
		if (sets[i]->to_label && sets[i]->n_vals != 1) {

			if (explored) {
				fprintf(stderr, "\nError: Constraint LINEAR_VAR (%d) not respected:\n", c->c_id);

				for (i = 0; i < c->n_c_vs; i++) {
					fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id, b_get_min_val(&c->c_vs[i]->domain_b),
							b_get_max_val(&c->c_vs[i]->domain_b),
							b_cnt_vals(&c->c_vs[i]->domain_b));
				}
			}
			return false;
		}
	}
#endif

	// if any two sets share more than one value
	v_iter1 = 0;
	v_iter2 = (unsigned int)cards[0];
	for (i = 0; i < n_sets; i++) {
		for (j = 0; j < cards[i]; j++) {
			for (k = i + 1; k < n_sets; k++) {
				vals_eq = 0;
				for (l = 0; l < cards[k]; l++) {

					if (sets[v_iter1]->min == sets[v_iter2]->min) {
						vals_eq++;

						if (vals_eq > 1) {

							if (explored) {
								fprintf(stderr, "\nError: Constraint AT_MOST_ONE (%d) not respected:\n", c->c_id);

								for (i = 0; i < c->n_c_vs; i++) {
									fprintf(stderr, "Variable ID=%u -> minimum=%u, maximum=%u, number of values=%u\n\n", c->c_vs[i]->v_id,
											b_get_min_val(&c->c_vs[i]->domain_b), b_get_max_val(&c->c_vs[i]->domain_b),	b_cnt_vals(&c->c_vs[i]->domain_b));
								}
							}
							return false;
						}
					}
					v_iter2++;
				}
				v_iter2 -= (unsigned int)cards[k];
			}
			v_iter2 += (unsigned int)cards[k];
			v_iter1++;
		}
	}
	return true;
}

#endif

#if CS_AT_MOST_ONE == 1
/*
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_most_one constraint
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|≤1
 * prop_ok will be set to 1 if success or to 0 if any domain became empty
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * prop_v_id - variable ID to propagate
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_most_one_prop(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, unsigned int prop_v_id, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok TTL_CTR) {

	CL_INTS_MEM int* cards = c_consts;
	int n_sets = current_cs->constant_val;
	int set_to_prop_idx;	// set with the variables to propagate
	int set_to_prun_idx;	// Iterator for the other sets to prune
	int set_to_prop_n = -1;
	int v_to_prop_id;
	int v_to_prun_id;
	int v_iter = 0;
	int val;
	int vals_repeat_ctr;
	bool changed = 0;
	int i, j, k;

	// if the variable to propagate is singleton, propagate all the variables already singleton on that set to all the other sets
	if (V_N_VALS(vs_prop_[prop_v_id]) == 1) {

		// get the number of the set where the variable to propagate belong and initialize set_to_prop
		v_iter = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 43)
			set_to_prop_idx = v_iter;
			for (j = 0; j < cards[i]; j++) {
				CHECK_TTL(ttl_ctr, 44)
				if (prop_v_id == (unsigned int)vs_per_c_idx[v_iter]) {
					set_to_prop_n = i;
					break;
				}
				v_iter++;
			}
			if (set_to_prop_n != -1) {
				break;
			}
		}

		// iterate over all the sets
		set_to_prun_idx = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 45)
			if (i > 0) {
				set_to_prun_idx += cards[i - 1];
			}
			// if this set is not the one being propagated
			if (i != set_to_prop_n) {

				// iterate all the variables on the set to propagate and propagate all the singleton variables on that set
				vals_repeat_ctr = 0;
				for (j = 0; j < cards[set_to_prop_n]; j++) {
					CHECK_TTL(ttl_ctr, 46)

					v_to_prop_id = vs_per_c_idx[set_to_prop_idx + j];
					if (V_N_VALS(vs_prop_[v_to_prop_id]) == 1) {
						val = V_MIN(vs_prop_[v_to_prop_id]);

						for (k = 0; k < cards[i]; k++) {
							CHECK_TTL(ttl_ctr, 47)
							v_to_prun_id = vs_per_c_idx[set_to_prun_idx + k];
							// count number of singleton variable values repeated on both sets
							if (V_N_VALS(vs_prop_[v_to_prun_id]) == 1 && V_MIN(vs_prop_[v_to_prun_id]) == val) {
								vals_repeat_ctr++;

								if (vals_repeat_ctr > 1) {
									*prop_ok = 0;
									return;
								}
							}
							// if only one singleton variable value is repeated on both sets remove that value from the other variables
							if (vals_repeat_ctr == 1 && V_N_VALS(vs_prop_[v_to_prun_id]) > 1) {

								cl_v_del_val_m(&changed, &vs_prop_[v_to_prun_id], val TTL_CTR_V);
								if (changed) {
									if (V_N_VALS(vs_prop_[v_to_prun_id]) == 0) {
										*prop_ok = 0;
										return;
									}
									v_add_to_prop(vs_id_to_prop_, vs_prop_, v_to_prun_id);
								}
							}
						}
					}
				}
			}
		}
	}
}

#if CS_R_AT_MOST_ONE == 1
/*
 * Validate at_most_one constraint to be normally propagated, when reified
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|≤1
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_most_one_reif( CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, unsigned int prop_v_id, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_ TTL_CTR) {

	CL_INTS_MEM int* cards = c_consts;
	int n_sets = current_cs->constant_val;
	int set_to_prop_idx;	// set with the variables to propagate
	int set_to_prun_idx;	// Iterator for the other sets to prune
	int set_to_prop_n = -1;
	int v_to_prop_id;
	VARS_PROP v_to_prun;
	int v_iter = 0;
	int val;
	int vals_repeat_ctr;
	bool changed = 0;
	int i, j, k;

	// if the variable to propagate is singleton, propagate all the variables already singleton on that set to all the other sets
	if (V_N_VALS(vs_prop_[prop_v_id]) == 1) {

		// get the number of the set where the variable to propagate belong and initialize set_to_prop
		v_iter = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 48)
			set_to_prop_idx = v_iter;
			for (j = 0; j < cards[i]; j++) {
				CHECK_TTL(ttl_ctr, 49)
				if (prop_v_id == (unsigned int)vs_per_c_idx[v_iter]) {
					set_to_prop_n = i;
					break;
				}
				v_iter++;
			}
			if (set_to_prop_n != -1) {
				break;
			}
		}

		// iterate over all the sets
		set_to_prun_idx = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 50)
			if (i > 0) {
				set_to_prun_idx += cards[i - 1];
			}
			// if this set is not the one being propagated
			if (i != set_to_prop_n) {

				// iterate all the variables on the set to propagate and propagate all the singleton variables on that set
				vals_repeat_ctr = 0;
				for (j = 0; j < cards[set_to_prop_n]; j++) {
					CHECK_TTL(ttl_ctr, 51)

					v_to_prop_id = vs_per_c_idx[set_to_prop_idx + j];
					if (V_N_VALS(vs_prop_[v_to_prop_id]) == 1) {
						val = V_MIN(vs_prop_[v_to_prop_id]);

						for (k = 0; k < cards[i]; k++) {
							CHECK_TTL(ttl_ctr, 52)

							cl_v_copy_pm(&v_to_prun, &vs_prop_[vs_per_c_idx[set_to_prun_idx + k]] TTL_CTR_V);

							// count number of singleton variable values repeated on both sets
							if (V_N_VALS(v_to_prun) == 1 && V_MIN(v_to_prun) == val) {
								vals_repeat_ctr++;

								if (vals_repeat_ctr > 1) {
									cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V);

									v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));
									return;
								}
							}
							// if only one singleton variable value is repeated on both sets remove that value from the other variables
							if (vals_repeat_ctr == 1 && V_N_VALS(v_to_prun) > 1) {

								cl_v_del_val_n(&changed, &v_to_prun, val TTL_CTR_V);
								if (V_N_VALS(v_to_prun) == 0) {
									cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 1 TTL_CTR_V);
									v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));
									return;
								}
							}
						}
					}
				}
			}
		}

		// check if constraint is already fixed
		v_iter = 0;
		for (i = 0; i < current_cs->n_c_vs; i++) {
			CHECK_TTL(ttl_ctr, 187)

			if (V_N_VALS(vs_prop_[vs_per_c_idx[v_iter]]) != 1) {
				return;
			}
		}
		cl_v_bool_del_val_m(&vs_prop_[current_cs->reif_var_id], 0 TTL_CTR_V);
		v_add_to_prop(vs_id_to_prop_, vs_prop_, convert_int(current_cs->reif_var_id));
	}
}

/*
 * Propagate the domain of the variable with the ID prop_v_id through all the other variables on the same c_numb ID at_most_one opposite constraint
 * ∀i∈[1,n]:|si|=ci ; ∀i,j∈[1,n](i<j):∣si⋂sj|>1
 * vs_per_c_idx - vector with all constrained variables ID per constraint, per constraint ID order
 * c_consts - vector with all constrained constants per constraint, per constraint ID order
 * vs_prop_ - all CSP variables with current step values
 * prop_v_id - variable ID to propagate
 * current_cs - constraint that should be propagated for the variable with prop_v_id ID
 * vs_id_to_prop_ - circular vector with the ids of the variables to propagate
 */
CUDA_FUNC void at_most_one_prop_opposite(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, unsigned int prop_v_id
		, CL_CS_MEM cl_constr* current_cs TTL_CTR) {

	CL_INTS_MEM int* cards = c_consts;
	int n_sets = current_cs->constant_val;
	int set_to_prop_idx;	// set with the variables to propagate
	int set_to_prun_idx;	// Iterator for the other sets to prune
	int set_to_prop_n = -1;
	int v_to_prop_id;
	int v_to_prun_id;
	int v_iter = 0;
	int val;
	int vals_repeat_ctr;
	bool contains;
	int i, j, k;

	// if the variable to propagate is singleton, propagate all the variables already singleton on that set to all the other sets
	if (V_N_VALS(vs_prop_[prop_v_id]) == 1) {

		// get the number of the set where the variable to propagate belong and initialize set_to_prop
		v_iter = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 200)
			set_to_prop_idx = v_iter;
			for (j = 0; j < cards[i]; j++) {
				CHECK_TTL(ttl_ctr, 201)
				if (prop_v_id == (unsigned int)vs_per_c_idx[v_iter]) {
					set_to_prop_n = i;
					break;
				}
				v_iter++;
			}
			if (set_to_prop_n != -1) {
				break;
			}
		}

		// iterate over all the sets
		set_to_prun_idx = 0;
		for (i = 0; i < n_sets; i++) {
			CHECK_TTL(ttl_ctr, 202)
			if (i > 0) {
				set_to_prun_idx += cards[i - 1];
			}
			// if this set is not the one being propagated
			if (i != set_to_prop_n) {

				// iterate all the variables on the set to propagate and propagate all the singleton variables on that set
				vals_repeat_ctr = 0;
				for (j = 0; j < cards[set_to_prop_n]; j++) {
					CHECK_TTL(ttl_ctr, 203)

					v_to_prop_id = vs_per_c_idx[set_to_prop_idx + j];
					if (V_N_VALS(vs_prop_[v_to_prop_id]) == 1) {
						val = V_MIN(vs_prop_[v_to_prop_id]);

						for (k = 0; k < cards[i]; k++) {
							CHECK_TTL(ttl_ctr, 204)
							v_to_prun_id = vs_per_c_idx[set_to_prun_idx + k];

							// count number of variable values repeated on both sets
							cl_v_contains_val_m(&contains, &vs_prop_[v_to_prun_id], val TTL_CTR_V);
							if (contains) {

								if (++vals_repeat_ctr > 1) {
									return;
								}
							}
						}
					}
				}
			}
		}
	}
}

#endif

CUDA_FUNC void at_most_one_propagate(CL_INTS_MEM int* vs_per_c_idx, CL_INTS_MEM int* c_consts, CL_MEMORY VARS_PROP* vs_prop_, unsigned int prop_v_id, CL_CS_MEM cl_constr* current_cs,
		CL_MEMORY unsigned short* vs_id_to_prop_, bool* prop_ok PROPAGATED_FUNC TTL_CTR) {

#if CS_R_AT_MOST_ONE == 0
	at_most_one_prop(vs_per_c_idx, c_consts, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok TTL_CTR_V);
#if CL_STATS == 1
	*propagated = true;
#endif
#elif CS_R_AT_MOST_ONE == 1
	if (current_cs->reified == 1) {
		if (prop_v_id != current_cs->reif_var_id) {
			if (V_N_VALS(vs_prop_[current_cs->reif_var_id]) > 1) {
				at_most_one_reif(vs_per_c_idx, c_consts, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_ TTL_CTR_V);

			} else {
				if (V_MIN(vs_prop_[current_cs->reif_var_id]) == 1) {
					at_most_one_prop(vs_per_c_idx, c_consts, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok TTL_CTR_V);
				} else {
					at_most_one_prop_opposite(vs_per_c_idx, c_consts, vs_prop_, prop_v_id, current_cs TTL_CTR_V);
				}
#if CL_STATS == 1
				*propagated = true;
#endif
			}
		}
	} else {
		at_most_one_prop(vs_per_c_idx, c_consts, vs_prop_, prop_v_id, current_cs, vs_id_to_prop_, prop_ok TTL_CTR_V);
#if CL_STATS == 1
		*propagated = true;
#endif
	}
#endif
}

#endif