// Copyrights by Kenneth Lee, 2022. All Rights Reserved
#include <iostream>
#include <assert.h>
#include "value.hpp"

using namespace std;

static Val target;
static void enumerate_all_splites(ValComp * set);

static void evaluate(ValComp * set) {
	assert(set && set->size > 0);

	assert(set->ret.state == ValIf::ST_NON); // don't give evaluated node

	if (set->size == 1) {
		set->ret = set->vals[0];
	} else {
		if (set->left)
			evaluate(set->left);
		if (set->right)
			evaluate(set->right);
		set->evaluate();
	}
}

void cal(ValComp *set, ValComp *set1, ValComp *set2, ValComp::OPS op) {
	if (debug_level > 0)
		cout << "cal: " << *set1 << op << *set2 << endl;

	set->merge_op(set1, set2, op);

	ValComp *unsolved = find_unsolved_leaf(set->find_root());
	if (unsolved)
		enumerate_all_splites(unsolved);
	else {
		// now the tree is solved
		ValComp *root = set->find_root();
		evaluate(root);
		if (debug_level > 0) {
			cout << "evaluate" << *root << ": ";
			root->show_expr();
			cout << " = " << root->ret << endl;
		} else if (root->ret == target) {
			root->show_expr();
			cout << " = " << root->ret << endl;
		}

		free_tree(root);
	}
}

//enumerate all combination of operations
void cal_all(ValComp *set, ValComp *set1, ValComp *set2) {
	if (debug_level > 0)
		cout << "cal_all " << *set1 << *set2 << endl;
	for (int op = ValComp::ADD; op<ValComp::INV_OP; op++)
		cal(set->clone_tree(), set1->clone(), set2->clone(), (ValComp::OPS)op);
	cal(set->clone_tree(), set2->clone(), set1->clone(), ValComp::SUB);
	cal(set->clone_tree(), set2->clone(), set1->clone(), ValComp::DIV);

	free_tree(set);
	free_tree(set1);
	free_tree(set2);
}

// cur: to where set1 have be initialized
static void enumerate_n(ValComp * set, ValComp *set1, int cur) {
	if (debug_level > 0)
		cout << "enumerate_n(" << *set << ", " << *set1 << ", " << cur << ")" <<endl;

	if (set1->size == cur) {
		// now we finish set1, we create set2
		ValComp *set2 = new ValComp(set, set1);
		cal_all(set, set1, set2);
	} else {
		for (int i = set1->ids[cur-1] + 1; i < set->size; i++) {
			// expand the enumeration, we need clone to both set and set1
			ValComp * new_set1 = set1->clone();
			new_set1->copy_by_id(set, cur, i);
			enumerate_n(set->clone_tree(), new_set1, cur+1);
		}

		// new enumerated set and set1 were cloned, the input ones are not needed
		free(set);
		free(set1);
	}
}

// enumerate the input set into to disjoin set: set1 & set2, compose them with
// an operator.
static void enumerate_all_splites(ValComp * set) {
	assert(set->size > 0);

	if (debug_level > 0)
		cout << "enumerate_all_splites " << *set << endl;

	// loop with power of set1, from 1 to half of its power. but for even
	// size of set, the last one is exclusive
	for (int i = 0; i < (set->size - 1) / 2; i++) {
		for (int j = 0; j < set->size; j++) {
			ValComp *set1 = new ValComp(i+1);
			set1->copy_by_id(set, 0, j);
			enumerate_n(set->clone_tree(), set1, 1);
		}
	}

	// if the set is even power, we enumerate only first column to avoid
	// redundancy
	if (!(set->size % 2)) {
		ValComp *set1 = new ValComp(set->size/2);
		set1->copy_by_id(set, 0, 0);
		enumerate_n(set->clone_tree(), set1, 1);
	}

	// todo: size == 1 is senselss, we can still add this logic later

	free_tree(set);
}

int main(int argc, char *argv[]) {
	if (argc < 2)
		return -1;

	target = argv[1];
	enumerate_all_splites(new ValComp(argc, argv));
	return 0;
}