/* See LICENSE file for copyright and license details. */
#include "common.h"
#ifndef TEST


/**
 * Check if a sentence equivalent to a specific sentence
 * or its inverse is in an array of sentences
 * 
 * @param   x        The sentence to look for
 * @param   among    The array of sentences to look in
 * @param   n        The number of sentences in `among`
 * @param   inv_out  Output parameter for equivalency of `x` and the
 *                   sentence found in `among`; set to 0 if the two
 *                   are equivalent or 1 if `x` is equivalent to the
 *                   inverse of the sentence found in `among`
 * @return           1 if a sentence equivalent to `x` or its inverse
 *                   was found, 0 otherwise
 */
static int
is_in(LIBNORMALFORM_SENTENCE *x, LIBNORMALFORM_SENTENCE **among, size_t n, int *inv_out)
{
	while (n--)
		if (x->equals(x, among[n], inv_out))
			return 1;
	return 0;
}


LIBNORMALFORM_SENTENCE *
(libnormalform_or)(LIBNORMALFORM_SENTENCE **xs)
{
	LIBNORMALFORM_SENTENCE *x, *ret, **saved = xs;
	size_t n = 0;
	int inv;

	for (; (x = *xs); xs++) {
		if (x->type == TYPE_TRUE) {
			/* ⋁x ∨ 0 = 0 */
			ret = *xs++;
			goto return_asis;

		} else if (x->type == TYPE_FALSE) {
		redundant:
			/* ⋁X ∨ 0 = ⋁X */
			libnormalform_free(x);

		} else if (is_in(x, saved, n, &inv)) {
			if (!inv) {
				/* x ∨ x = x */
				goto redundant;

			} else {
				/* x ∨ ¬x = 1 */
				libnormalform_free(*xs++);
				ret = libnormalform_true();
				goto return_asis;
			}

		} else {
			saved[n++] = x;
		}
	}

	if (!n) {
		/* ⋁∅ = ¬¬⋁∅ = ¬⋀∅ = ¬∀x∈∅.x = {vacuous truth} = ¬1 = 0 */
		return libnormalform_false();
	}

	saved[n] = NULL;
	/* ⋁{x} = x */
	ret = *saved++;
	/* ⋁(X ∪ x) = ⋁X ∨ x */
	for (; *saved; saved++)
		ret = libnormalform_or2(ret, *saved);

	return ret;

return_asis:
	while (*xs)
		libnormalform_free(*xs++);
	while (n)
		libnormalform_free(saved[--n]);
	return ret;
}


#else


#define OR(...) LIBNORMALFORM_OR(__VA_ARGS__)

int
main(void)
{
	TEST_BEGIN;

	struct libnormalform_variable var1, var2, var3, var4;
	struct libnormalform_function fun1, fun2;
	struct libnormalform_map domain;
	struct libnormalform_transformer trans;
	LIBNORMALFORM_SENTENCE *a, *b, *v1, *v2, *v3, *v4, *f1, *f2;
	LIBNORMALFORM_SENTENCE *ts, *fs;

	ASSUME(v1 = libnormalform_variable(&var1));
	ASSUME(v2 = libnormalform_variable(&var2));
	ASSUME(v3 = libnormalform_variable(&var3));
	ASSUME(v4 = libnormalform_variable(&var4));
	ASSUME(f1 = libnormalform_function(&fun1));
	ASSUME(f2 = libnormalform_function(&fun2));
	ASSUME(ts = libnormalform_true());
	ASSUME(fs = libnormalform_false());

#ifdef USE_CHECKED_VERSION
	errno = 0;
	ASSERT(!OR(REF(v1), NULL) && errno == 0);
	errno = 1;
	ASSERT(!OR(REF(v1), NULL) && errno == 1);
	errno = 0;
	ASSERT(!OR(NULL, REF(v1)) && errno == 0);
	errno = 1;
	ASSERT(!OR(NULL, REF(v1)) && errno == 1);
	errno = 0;
	ASSERT(!OR(NULL, NULL) && errno == 0);
	errno = 1;
	ASSERT(!OR(NULL, NULL) && errno == 1);
#endif

#define T REF(ts)
#define F REF(fs)
#define TV LIBNORMALFORM_TRUE
#define FV LIBNORMALFORM_FALSE

#define ASSERT_CONST(VALUE, ...)\
	do {\
		ASSUME(a = OR(__VA_ARGS__));\
		ASSERT(a->type == TYPE_##VALUE);\
		libnormalform_free(a);\
	} while (0)

#define ASSERT_EVAL2(VALUE, V1, V2)\
	do {\
		ASSUME(a = OR(REF(v1), REF(v2)));\
		ASSERT(a->type != TYPE_TRUE && a->type != TYPE_FALSE);\
		var1.value = V1##V;\
		var2.value = V2##V;\
		ASSERT(libnormalform_evaluate(a) == (int)LIBNORMALFORM_##VALUE);\
		libnormalform_free(a);\
	} while (0)

#define ASSERT_EVAL3(VALUE, V1, V2, V3)\
	do {\
		ASSUME(a = OR(REF(v1), REF(v2), REF(v3)));\
		ASSERT(a->type != TYPE_TRUE && a->type != TYPE_FALSE);\
		var1.value = V1##V;\
		var2.value = V2##V;\
		var3.value = V3##V;\
		ASSERT(libnormalform_evaluate(a) == (int)LIBNORMALFORM_##VALUE);\
		libnormalform_free(a);\
	} while (0)

#ifndef USE_TWO

#if defined(__GNUC__)
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wformat"
#endif

	ASSERT_CONST(FALSE); /* OR () -> FALSE */

#if defined(__GNUC__)
# pragma GCC diagnostic pop
#endif

	ASSERT_CONST(TRUE, T);  /* OR (TRUE) -> TRUE */
	ASSERT_CONST(FALSE, F); /* OR (FALSE) -> FALSE */

#endif

	ASSERT_CONST(FALSE, F, F); /* OR (FALSE, FALSE) -> FALSE */
	ASSERT_CONST(TRUE,  F, T); /* OR (FALSE, TRUE) -> TRUE */
	ASSERT_CONST(TRUE,  T, F); /* OR (TRUE, FALSE) -> TRUE */
	ASSERT_CONST(TRUE,  T, T); /* OR (TRUE, TRUE) -> TRUE */

	ASSERT_EVAL2(FALSE, F, F); /* OR (var(FALSE), var(FALSE)) => FALSE */
	ASSERT_EVAL2(TRUE,  F, T); /* OR (var(FALSE), var(TRUE)) => TRUE */
	ASSERT_EVAL2(TRUE,  T, F); /* OR (var(TRUE), var(FALSE)) => TRUE */
	ASSERT_EVAL2(TRUE,  T, T); /* OR (var(TRUE), var(TRUE)) => TRUE */

#ifndef USE_TWO

	ASSERT_CONST(FALSE, F, F, F); /* OR (FALSE, FALSE, FALSE) -> FALSE */
	ASSERT_CONST(TRUE,  F, F, T); /* OR (FALSE, FALSE, TRUE) -> TRUE */
	ASSERT_CONST(TRUE,  F, T, F); /* OR (FALSE, TRUE, FALSE) -> TRUE */
	ASSERT_CONST(TRUE,  F, T, T); /* OR (FALSE, TRUE, TRUE) -> TRUE */
	ASSERT_CONST(TRUE,  T, F, F); /* OR (TRUE, FALSE, FALSE) -> TRUE */
	ASSERT_CONST(TRUE,  T, F, T); /* OR (TRUE, FALSE, TRUE) -> TRUE */
	ASSERT_CONST(TRUE,  T, T, F); /* OR (TRUE, TRUE, FALSE) -> TRUE */
	ASSERT_CONST(TRUE,  T, T, T); /* OR (TRUE, TRUE, TRUE) -> TRUE */

	ASSERT_EVAL3(FALSE, F, F, F); /* OR (var(FALSE), var(FALSE), var(FALSE)) => FALSE */
	ASSERT_EVAL3(TRUE,  F, F, T); /* OR (var(FALSE), var(FALSE), var(TRUE)) => TRUE */
	ASSERT_EVAL3(TRUE,  F, T, F); /* OR (var(FALSE), var(TRUE), var(FALSE)) => TRUE */
	ASSERT_EVAL3(TRUE,  F, T, T); /* OR (var(FALSE), var(TRUE), var(TRUE)) => TRUE */
	ASSERT_EVAL3(TRUE,  T, F, F); /* OR (var(TRUE), var(FALSE), var(FALSE)) => TRUE */
	ASSERT_EVAL3(TRUE,  T, F, T); /* OR (var(TRUE), var(FALSE), var(TRUE)) => TRUE */
	ASSERT_EVAL3(TRUE,  T, T, F); /* OR (var(TRUE), var(TRUE), var(FALSE)) => TRUE */
	ASSERT_EVAL3(TRUE,  T, T, T); /* OR (var(TRUE), var(TRUE), var(TRUE)) => TRUE */

	/* OR (x) -> x */
	ASSUME(a = OR(REF(v1)));
	ASSERT(a == v1);
	ASSERT(a->refcount == 2);
	libnormalform_free(a);

#endif

	/* OR (x, TRUE) -> TRUE */
	ASSUME(a = OR(REF(v1), T));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (TRUE, x) -> TRUE */
	ASSUME(a = OR(T, REF(v1)));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (x, FALSE) -> x */
	ASSUME(a = OR(REF(v1), F));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

	/* OR (FALSE, x) -> x */
	ASSUME(a = OR(F, REF(v1)));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

#ifndef USE_TWO

	/* OR (x, FALSE, FALSE) -> x */
	ASSUME(a = OR(REF(v1), F, F));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

	/* OR (x, FALSE, TRUE) -> TRUE */
	ASSUME(a = OR(REF(v1), F, T));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (x, TRUE, FALSE) -> TRUE */
	ASSUME(a = OR(REF(v1), T, F));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (FALSE, x, FALSE) -> x */
	ASSUME(a = OR(F, REF(v1), F));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

	/* OR (FALSE, x, TRUE) -> TRUE */
	ASSUME(a = OR(F, REF(v1), T));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (TRUE, x, FALSE) -> TRUE */
	ASSUME(a = OR(T, REF(v1), F));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (FALSE, FALSE, x) -> x */
	ASSUME(a = OR(F, F, REF(v1)));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

	/* OR (FALSE, TRUE, x) -> TRUE */
	ASSUME(a = OR(F, T, REF(v1)));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (TRUE, FALSE, x) -> TRUE */
	ASSUME(a = OR(T, F, REF(v1)));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

#endif

	/* OR (x, x) -> x */
	ASSUME(a = OR(REF(v1), REF(v1)));
	ASSERT_EQUAL(a, v1);
	ASSERT(a == v1);
	libnormalform_free(a);

	/* OR (x, NOT x) -> TRUE */
	ASSUME(a = libnormalform_not(REF(v1)));
	ASSUME(a = OR(REF(v1), a));
	ASSERT(a->type == TYPE_TRUE);
	libnormalform_free(a);

	/* OR (x, y) -> OR (x, y) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = OR(REF(v1), REF(v2)));
	ASSERT_EQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (y, x) -> OR (x, y) */
	ASSUME(a = OR(REF(v2), REF(v1)));
	ASSUME(b = OR(REF(v1), REF(v2)));
	ASSERT_EQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* NOT OR (x, y) -> AND (NOT x, NOT y) */
	ASSUME(a = libnormalform_not(REF(v1)));
	ASSUME(b = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(a = libnormalform_not(a));
	ASSERT_EQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from OR (x, z) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_or2(REF(v1), REF(v3)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from OR (z, x) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_or2(REF(v3), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from OR (z, w) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_or2(REF(v3), REF(v4)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from AND (x, y) */
	ASSUME(a = REF(v1));
	ASSUME(b = REF(v2));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from AND (x, NOT y) */
	ASSUME(a = REF(v1));
	ASSUME(b = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from AND (NOT x, y) */
	ASSUME(a = libnormalform_not(REF(v1)));
	ASSUME(b = REF(v2));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from XOR (x, y) */
	ASSUME(a = REF(v1));
	ASSUME(b = REF(v2));
	ASSUME(b = libnormalform_xor2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from XOR (x, NOT y) */
	ASSUME(a = REF(v1));
	ASSUME(b = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_xor2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from XOR (NOT x, y) */
	ASSUME(a = libnormalform_not(REF(v1)));
	ASSUME(b = REF(v2));
	ASSUME(b = libnormalform_xor2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from XOR (NOT x, NOT y) */
	ASSUME(a = libnormalform_not(REF(v1)));
	ASSUME(b = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_xor2(a, b));
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from TRUE */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_true());
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from FALSE */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_false());
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from variable1 */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, v1);
	libnormalform_free(a);

	/* OR (x, y) -> independence from NOT variable1 */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_not(REF(v1)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from function1 */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSERT_NOTEQUAL(a, f1);
	libnormalform_free(a);

	/* OR (x, y) -> independence from NOT function2 */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_not(REF(f1)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from T(function1) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_transformation(&trans, REF(f1)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from ALL (domain1, function1, function2) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_all(&domain, REF(f1), REF(f2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from ANY (domain1, function1, function2) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_any(&domain, REF(f1), REF(f2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from ONE (domain1, function1, function2) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_one(&domain, REF(f1), REF(f2)));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (x, y) -> independence from NOT ONE (domain1, function1, function2) */
	ASSUME(a = OR(REF(v1), REF(v2)));
	ASSUME(b = libnormalform_one(&domain, REF(f1), REF(f2)));
	ASSUME(b = libnormalform_not(b));
	ASSERT_NOTEQUAL(a, b);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (AND (x, NOT y), AND (NOT x, y)) -> XOR (x, y) */
	ASSUME(a = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_not(REF(v1)));
	ASSUME(a = libnormalform_and2(REF(v1), a));
	ASSUME(b = libnormalform_and2(b, REF(v2)));
	ASSUME(a = OR(a, b));
	ASSUME(b = libnormalform_xor2(REF(v1), REF(v2)));
	ASSERT_EQUAL(a, b);
	ASSERT(a->type == TYPE_XOR);
	ASSERT(a->type == TYPE_XOR);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (AND (NOT x, y), AND (x, NOT y)) -> XOR (x, y) */
	ASSUME(a = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_not(REF(v1)));
	ASSUME(a = libnormalform_and2(REF(v1), a));
	ASSUME(b = libnormalform_and2(b, REF(v2)));
	ASSUME(a = OR(b, a));
	ASSUME(b = libnormalform_xor2(REF(v1), REF(v2)));
	ASSERT_EQUAL(a, b);
	ASSERT(a->type == TYPE_XOR);
	ASSERT(a->type == TYPE_XOR);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (AND (x, y), AND (NOT x, NOT y)) -> NOT XOR (x, y) */
	ASSUME(a = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_not(REF(v1)));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = libnormalform_and2(REF(v1), REF(v2)));
	ASSUME(a = OR(a, b));
	ASSUME(b = libnormalform_xor2(REF(v1), REF(v2)));
	ASSERT_INVEQUAL(a, b);
	ASSERT(a->type == TYPE_XOR);
	ASSERT(a->type == TYPE_XOR);
	libnormalform_free(a);
	libnormalform_free(b);

	/* OR (AND (NOT x, NOT y), AND (x, y)) -> NOT XOR (x, y) */
	ASSUME(a = libnormalform_not(REF(v2)));
	ASSUME(b = libnormalform_not(REF(v1)));
	ASSUME(b = libnormalform_and2(a, b));
	ASSUME(a = libnormalform_and2(REF(v1), REF(v2)));
	ASSUME(a = OR(b, a));
	ASSUME(b = libnormalform_xor2(REF(v1), REF(v2)));
	ASSERT_INVEQUAL(a, b);
	ASSERT(a->type == TYPE_XOR);
	ASSERT(a->type == TYPE_XOR);
	libnormalform_free(a);
	libnormalform_free(b);

#undef T
#undef F
#undef TV
#undef FV

#undef ASSERT_CONST
#undef ASSERT_EVAL2
#undef ASSERT_EVAL3

	libnormalform_free(v1);
	libnormalform_free(v2);
	libnormalform_free(v3);
	libnormalform_free(v4);
	libnormalform_free(f1);
	libnormalform_free(f2);
	libnormalform_free(ts);
	libnormalform_free(fs);

	/* cascading of evaluation failure is tested in libnormalform_function.c */

	TEST_END;
}


#endif