1 files changed, 326 insertions, 0 deletions
diff --git a/tree.cpp b/tree.cpp
new file mode 100644
index 0000000..8d677db
--- /dev/null
+++ b/tree.cpp
@@ -0,0 +1,326 @@
+#include <cctype>
+#include <cassert>
+#include "tree.h"
+
+using namespace std;
+
+
+int uniqid(){
+	static int id=10;
+	return 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;
+}
+
+int Tree::Node::nleaves() const {
+	if(v.isOperator()){
+		return left->nleaves()+right->nleaves();
+	} 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::replace(Node *subj,const Tree &pat,const Tree &repl,vector<Tree> &accum){
+	Assign *as=subj->match(*pat.root);
+	if(as){
+		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;
+}
+
+int Tree::nleaves() const {
+	assert(root);
+	return root->nleaves();
+}
+
+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;
+}