1 files changed, 94 insertions, 0 deletions
diff --git a/tree.h b/tree.h
new file mode 100644
index 0000000..7d8cf15
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,94 @@
+#pragma once
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <unordered_map>
+
+using namespace std;
+
+
+int uniqid();
+
+struct Variable{
+	int id;
+
+	Variable(int id):id(id){}
+
+	bool isOperator() const;
+	bool isFixed() const;
+	bool isTemp() const;
+
+	bool operator==(Variable v) const;
+	bool operator!=(Variable v) const;
+
+	operator int() const;
+};
+
+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;
+
+		int nleaves() 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);
+
+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);
+
+	int nleaves() 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);