tree.h

// Copyright (C) 2005-2011, Ondra Kamenik

#ifndef OGP_TREE_H
#define OGP_TREE_H

#include <vector>
#include <set>
#include <map>
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
#include <cstdio>

namespace ogp {

	using boost::unordered_set;
	using boost::unordered_map;
	using std::vector;
	using std::set;
	using std::map;

	/** Enumerator representing nulary, unary and binary operation
	 * codes. For nulary, 'none' is used. When one is adding a new
	 * codes, he should update the code of #OperationTree::add_unary,
	 * #OperationTree::add_binary, and of course
	 * #OperationTree::add_derivative. */
	enum code_t {NONE, UMINUS, LOG, EXP, SIN, COS, TAN, SQRT, ERF,
				 ERFC, PLUS, MINUS, TIMES, DIVIDE, POWER};

	/** Class representing a nulary, unary, or binary operation. */
	class Operation {
	protected:
		/** Code of the operation. */
		code_t code;
		/** First operand. If none, then it is -1. */
		int op1;
		/** Second operand. If none, then it is -1. */
		int op2;

	public:
		/** Constructs a binary operation. */
		Operation(code_t cd, int oper1, int oper2)
			: code(cd), op1(oper1), op2(oper2) {}
		/** Constructs a unary operation. */
		Operation(code_t cd, int oper1)
			: code(cd), op1(oper1), op2(-1) {}
		/** Constructs a nulary operation. */
		Operation()
			: code(NONE), op1(-1), op2(-1) {}
		/** A copy constructor. */
		Operation(const Operation& op)
			: code(op.code), op1(op.op1), op2(op.op2) {}

		/** Operator =. */
		const Operation& operator=(const Operation& op)
			{
				code = op.code;
				op1 = op.op1;
				op2 = op.op2;
				return *this;
			}
		/** Operator ==. */
		bool operator==(const Operation& op) const
			{
				return code == op.code && op1 == op.op1 && op2 == op.op2;
			}
		/** Operator < implementing lexicographic ordering. */
		bool operator<(const Operation& op) const
			{
				return (code < op.code ||
						code == op.code &&