#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;


int uniqid();

struct Variable{
	int id;

	Variable(int id);

	bool isOperator() const;
	bool isFixed() const;
	bool isTemp() const;

	bool operator==(Variable v) const;
	bool operator!=(Variable v) const;

	operator int() const;
};

ostream& operator<<(ostream &os,const Variable &v);

namespace std {
	template <>
	struct hash<Variable>{
		hash<int> inthasher;
		size_t operator()(Variable v) const;
	};
}

class Tree{
	struct Node;

	using Assign = unordered_map<Variable,Node>;

	struct Node{
		Variable v;
		Node *left,*right;

		explicit Node(Variable v);
		Node(Node *left,Node *right);
		Node(const Node &other);
		~Node();

		Node& operator=(const Node &other);

		Assign* match(const Node &pat,Assign *accum=nullptr) const;
		Node* apply(const Assign &as) const;
		void collectTemporaries(unordered_set<Variable> &accum) const;

		int nleaves() const;
		int height() const;

		int compare(const Node &other) const;
	};

	Node *root=nullptr;

	static Node* parseTerm(const string &expr,size_t &idx);
	static Node* parseNode(const string &expr,size_t &idx);

	void replace(Node *subj,const Tree &pat,const Tree &repl,vector<Tree> &accum);

	void refreshUnassigned(const Tree &repl,Assign &as) const;

public:
	Tree(); // Creates invalid tree
	Tree(const string &expr);
	Tree(const Tree &other);
	~Tree();

	Tree& operator=(const Tree &other);

	bool matches(const Tree &pat) const;
	vector<Tree> replace(const Tree &pat,const Tree &repl);
	unordered_set<Variable> collectTemporaries() const;

	int nleaves() const;
	int height() const;

	int compare(const Tree &other) const;

	friend ostream& operator<<(ostream &os,const Variable &v);
	friend ostream& operator<<(ostream &os,const Node &node);
	friend ostream& operator<<(ostream &os,const Tree &tree);
	friend bool operator==(const Node &a,const Node &b);
	friend bool operator!=(const Node &a,const Node &b);
};

struct TreeCompare{
	bool operator()(const Tree &a,const Tree &b) const;
};

ostream& operator<<(ostream &os,const Tree &tree);