#include <cctype>
#include <cassert>
#include "tree.h"

using namespace std;


int uniqid(){
	static int id=10;
	return id++;
}


Variable::Variable(int id):id(id){}

bool Variable::isOperator() const {
	return id==0;
}

bool Variable::isFixed() const {
	return id<0;
}

bool Variable::isTemp() const {
	return id>0;
}

bool Variable::operator==(Variable v) const {
	return id==v.id;
}

bool Variable::operator!=(Variable v) const {
	return id!=v.id;
}

Variable::operator int() const {
	return id;
}

namespace std {
	size_t hash<Variable>::operator()(Variable v) const {
		return inthasher(v.id);
	}
}

ostream& operator<<(ostream &os,const Variable &v){
	assert(!v.isOperator());
	if(v.isFixed())return os<<-v.id;
	else return os<<'['<<v.id<<']';
}


Tree::Node::Node(Variable v):v(v),left(nullptr),right(nullptr){}

Tree::Node::Node(Node *left,Node *right):v(0),left(left),right(right){
	assert(left&&right);
}

Tree::Node::Node(const Node &other):v(other.v){
	if(v.isOperator()){
		assert(other.left&&other.right);
		left=new Node(*other.left);
		right=new Node(*other.right);
	} else {
		assert(!other.left&&!other.right);
		left=right=nullptr;
	}
}

Tree::Node::~Node(){
	if(left){
		assert(right);
		delete left;
		delete right;
	} else {
		assert(!right);
	}
}

Tree::Node& Tree::Node::operator=(const Node &other){
	v=other.v;
	if(left){
		assert(right);
		delete left;
		delete right;
	} else {
		assert(!right);
	}
	if(other.left){
		assert(other.right);
		left=new Node(*other.left);
		right=new Node(*other.right);
	} else {
		assert(!other.right);
		left=right=nullptr;
	}
	return *this;
}

Tree::Assign* Tree::Node::match(const Node &pat,Assign *accum) const {
	//cerr<<"Matching "<<*this<<" and "<<pat<<endl;
	if(pat.v.isOperator()&&!v.isOperator()){
		if(v.isTemp()){
			//cerr<<"  -> ok, L="<<__LINE__<<endl;
			return accum;
		}
		//cerr<<"  -> null, L="<<__LINE__<<endl;
		if(accum)delete accum;
		return nullptr;
	}
	if(pat.v.isOperator()){
		assert(v.isOperator());
		assert(left&&right&&pat.left&&pat.right);
		Assign *as=left->match(*pat.left,accum);
		if(!as){
			//cerr<<"  -> null, L="<<__LINE__<<endl;
			return nullptr;
		}
		Assign *right_res=right->match(*pat.right,as);
		if(!right_res){
			//cerr<<"  -> null, L="<<__LINE__<<endl;
			return nullptr;
		}
		return as;
	}
	assert(!pat.left&&!pat.right);
	if(pat.v.isFixed()){
		if(v.isOperator()||(v.isFixed()&&pat.v!=v)){
			//cerr<<"  -> null, L="<<__LINE__<<endl;
			if(accum)delete accum;
			return nullptr;
		}
		//cerr<<"  -> ok, L="<<__LINE__<<endl;
		if(accum)return accum;
		else return new Assign();
	}
	if(!accum){
		accum=new Assign();
		accum->emplace(pat.v,*this);
		//cerr<<"  -> ok, L="<<__LINE__<<endl;
		return accum;
	}
	auto it=accum->find(pat.v);
	if(it==accum->end()){
		accum->emplace(pat.v,*this);
		//cerr<<"  -> ok, L="<<__LINE__<<endl;
		return accum;
	}
	if(it->second==*this){
		//cerr<<"  -> ok, L="<<__LINE__<<endl;
		return accum;
	} else {
		//cerr<<"  -> null, L="<<__LINE__<<endl;
		delete accum;
		return nullptr;
	}
}

Tree::Node* Tree::Node::apply(const Assign &as) const {
	Node *n=new Node(v);
	if(v.isOperator()){
		n->left=left->apply(as);
		n->right=right->apply(as);
	} else {
		auto it=as.find(v);
		if(it==as.end())n->v=v;
		else *n=it->second;
	}
	return n;
}

void Tree::Node::collectTemporaries(unordered_set<Variable> &accum) const {
	if(v.isOperator()){
		left->collectTemporaries(accum);
		right->collectTemporaries(accum);
	} else {
		accum.insert(v);
	}
}

int Tree::Node::nleaves() const {
	if(v.isOperator()){
		return left->nleaves()+right->nleaves();
	} else {
		return 1;
	}
}

int Tree::Node::height() const {
	if(v.isOperator())return max(left->height(),right->height());
	else return 1;
}

int Tree::Node::compare(const Node &other) const {
	if(v.isTemp()&&other.v.isTemp())return 0;
	if(v<other.v)return -1;
	if(v>other.v)return 1;
	if(!v.isOperator())return 0;
	int c=left->compare(*other.left);
	if(c!=0)return c;
	return right->compare(*other.right);
}

bool operator==(const Tree::Node &a,const Tree::Node &b){
	if(a.v.isTemp()&&b.v.isTemp())return true;
	if(a.v!=b.v)return false;
	if(!a.v.isOperator())return true;
	return *a.left==*b.left&&*a.right==*b.right;
}

bool operator!=(const Tree::Node &a,const Tree::Node &b){
	return !(a==b);
}

ostream& operator<<(ostream &os,const Tree::Node &node){
	if(node.v.isOperator()){
		return os<<'('<<*node.left<<'*'<<*node.right<<')';
	} else {
		return os<<node.v;
	}
}

Tree::Node* Tree::parseTerm(const string &expr,size_t &idx){
	if(expr[idx]=='('){
		idx++;
		Node *node=parseNode(expr,idx);
		assert(expr[idx]==')');
		idx++;
		return node;
	} else if(expr[idx]=='['){
		idx++;
		char *endp;
		const char *data=expr.data();
		assert(isdigit(data[idx]));
		Variable v=strtol(data+idx,&endp,10);
		assert(endp-(data+idx)>0);
		idx=endp-data;
		assert(data[idx]==']');
		idx++;
		assert(!v.isOperator());
		return new Node(v);
	} else {
		char *endp;
		const char *data=expr.data();
		assert(isdigit(data[idx]));
		Variable v=-strtol(data+idx,&endp,10);
		assert(endp-(data+idx)>0);
		idx=endp-data;
		assert(!v.isOperator());
		return new Node(v);
	}
}

Tree::Node* Tree::parseNode(const string &expr,size_t &idx){
	Node *l=parseTerm(expr,idx);
	if(idx==expr.size())return l;
	assert(expr[idx]=='*');
	idx++;
	Node *r=parseTerm(expr,idx);
	assert(idx==expr.size()||expr[idx]==')');
	return new Node(l,r);
}

Tree::Tree():root(nullptr){}

Tree::Tree(const string &expr){
	size_t idx=0;
	root=parseNode(expr,idx);
}

Tree::Tree(const Tree &other){
	if(root)delete root;
	if(other.root){
		root=new Node(*other.root);
	} else {
		root=nullptr;
	}
}

Tree::~Tree(){
	if(root)delete root;
}

Tree& Tree::operator=(const Tree &other){
	assert(other.root);
	if(root)delete root;
	root=new Node(*other.root);
	return *this;
}

bool Tree::matches(const Tree &pat) const {
	assert(root&&pat.root);
	Assign *as=root->match(*pat.root);
	if(as){
		delete as;
		return true;
	} else {
		return false;
	}
}

void Tree::refreshUnassigned(const Tree &repl,Assign &as) const {
	unordered_set<Variable> temps=repl.collectTemporaries();
	// cerr<<"rU:"<<endl;
	for(Variable v : temps){
		// cerr<<"  v = "<<v<<endl;
		if(v.isTemp()&&as.find(v)==as.end()){
			int id=uniqid();
			as.emplace(v,Node(id));
			// cerr<<"  emplace("<<v<<","<<Node(id)<<")"<<endl;
		}
	}
}

void Tree::replace(Node *subj,const Tree &pat,const Tree &repl,vector<Tree> &accum){
	Assign *as=subj->match(*pat.root);
	if(as){
		refreshUnassigned(repl,*as);
		// cerr<<"replace("<<*subj<<","<<pat<<","<<repl<<"); as:"<<endl;
		// for(const pair<Variable,Node> &p : *as){
		// 	cerr<<"  "<<p.first<<" -> "<<p.second<<endl;
		// }
		Node *res=repl.root->apply(*as);
		Node backup=*subj;
		*subj=*res;
		accum.push_back(*this);
		*subj=backup;
		delete res;
		delete as;
	}
	if(subj->left){
		replace(subj->left,pat,repl,accum);
		replace(subj->right,pat,repl,accum);
	}
}

vector<Tree> Tree::replace(const Tree &pat,const Tree &repl){
	assert(root&&pat.root);
	vector<Tree> res;
	replace(root,pat,repl,res);
	return res;
}

unordered_set<Variable> Tree::collectTemporaries() const {
	assert(root);
	unordered_set<Variable> temps;
	root->collectTemporaries(temps);
	return temps;
}

int Tree::nleaves() const {
	assert(root);
	return root->nleaves();
}

int Tree::height() const {
	assert(root);
	return root->height();
}

int Tree::compare(const Tree &other) const {
	assert(root&&other.root);
	return root->compare(*other.root);
}

bool TreeCompare::operator()(const Tree &a,const Tree &b) const {
	return a.compare(b)<0;
}

ostream& operator<<(ostream &os,const Tree &tree){
	return os<<*tree.root;
}