// Copyrights by Kenneth Lee, 2022. All Rights Reserved
#include "value.hpp"

ValComp::ValComp(int sz): size(sz), op(INV_OP), left(NULL),
	                  right(NULL), parent(NULL) {
	vals = new Val[size];
	ids = new int[size];
	for (int i = 0; i < size; i++) {
		ids[i] = -1;
	}
}

ValComp::ValComp() {
	*this = ValComp(1);
}

// construct by substract sub from src
ValComp::ValComp(ValComp *src, ValComp *sub) {
	*this = ValComp(src->size - sub->size);
	int j = 0;
	for (int i = 0; i < src->size; i++)
		if (!sub->contain_id(i))
			vals[j++] = src->vals[i];
	assert(j == size);
}

// construct by command line
ValComp::ValComp(int argc, char *argv[]) {
	*this = ValComp(argc - 2);
	for (int i = 0; i < size; i++)
		vals[i] = argv[i+2];
}

ValComp * ValComp::clone() const {
	ValComp *v = new ValComp(*this);
	if (debug_level > 1)
		cout << "clone " << this << " to " << v << *v << endl;
	if (v->left) {
		v->left = v->left->clone();
		v->left->parent = v;
	}
	if (v->right) {
		v->right = v->right->clone();
		v->right->parent = v;
	}

	return v;
}

// clone parent with new node n. don't touch "this".
void ValComp::clone_parent(ValComp *n) {
	n->parent = new ValComp(*parent); // create new parent node for n
	if (parent->left == this) {
		n->parent->left = n; //redirect to the new node

		assert(parent->right); //there is a left, it should be a right
		n->parent->right = parent->right->clone(); // clone right tree
		n->parent->right->parent = n->parent;

	} else {
		assert(parent->right == this); //parent is not left, it should right
		n->parent->right = n;

		assert(parent->left); //there is a right, there is a left
		n->parent->left = parent->left->clone(); // clone its old tree
		n->parent->left->parent = n->parent;
	}
	if (n->parent->parent) // recur to its parent
		parent->clone_parent(n->parent);
}

ValComp * ValComp::clone_tree() {
	ValComp *v = clone();
	if (parent)
		clone_parent(v);
	return v;
}

ostream & show(ostream & os, const ValComp & vg, int i) {
	os << vg.vals[i];

	if (vg.show_id)
		os << "(" << vg.ids[i] << ")";

	return os;
}

ostream & operator<<(ostream & os, const ValComp & vc) {
	os << "{";
	for (int i = 0; i < vc.size-1; i++) {
		show(cout, vc, i);
		cout << ", ";
	}

	if (vc.size > 0)
		show(cout, vc, vc.size-1);

	cout << "}";
	return os;
}

bool ValComp::contain_id(int id) {
	for (int i = 0; i < size; i++) {
		if (ids[i] == id)
			return true;
	}
	return false;
}

bool ValComp::is_right_most() {
	ValComp *p = this;
	while (p->parent) {
		if (debug_level > 1)
			cout << *(p->parent);

		if (p->parent->right != p) {
			if (debug_level > 1)
				cout << "not right:" << p << " " << p->parent << " "
				     << p->parent->left << " " << p->parent->right<< endl;
			return false;
		}
		p = p->parent;
	}
	return true;
}

void ValComp::copy_by_id(ValComp *vc, int tgt_id, int src_id) {
	vals[tgt_id] = vc->vals[src_id];
	ids[tgt_id] = src_id; // the src may not be set with id, we MUST use the id itself but the one saved in vc->ids
}

void ValComp::merge_op(ValComp *l, ValComp *r, OPS o) {
	if (debug_level > 1)
		cout << "merge: " << this << " " << l << " " << r << endl;
	left = l;
	right = r;
	op = o;
	l->parent = r->parent = this;
}

ValComp * ValComp::find_root() {
	ValComp *r = this;
	while (r->parent)
		r = r->parent;
	return r;
}

void ValComp::show_expr(void) {
	if (!left) {
		assert(!right);
		cout << ret;
	} else {
		assert(right);
		cout << "(";
		left->show_expr();
		cout << op;
		right->show_expr();
		cout << ")";
	}
}

void ValComp::evaluate(void) {
	switch(op) {
	case ADD:
		ret = left->ret + right->ret;
		break;
	case SUB:
		ret = left->ret - right->ret;
		break;
	case MUL:
		ret = left->ret * right->ret;
		break;
	case DIV:
		ret = left->ret / right->ret;
		break;
	default:
		assert(false);
	}
}

void free_tree(ValComp *root) {
	assert(root);

	if (root->left)
		free_tree(root->left);

	if (root->right)
		free_tree(root->right);

	free(root);
}

ValComp *find_unsolved_leaf(ValComp *r) {
	if (!r)
		return NULL;

	if (r->left == NULL && r->size > 1)
		return r;
	else {
		ValComp *p;

		p = find_unsolved_leaf(r->left);
		if (p)
			return p;

		p = find_unsolved_leaf(r->right);
		return p;
	}

	return NULL;
}

ostream & operator<<(ostream & os, const ValComp::OPS & op) {
	static const char * ops_str[] = { "+", "-", "*", "/", "<Invalide_op>"};

	os << ops_str[op];
	return os;
}