// Prog: xexpression.cpp
// defines a class for expression trees,
// using different types of nodes

#include<iostream>
#include<cassert>
#include<cmath>
namespace ifmp
{
  // (abstract) base class for any xexpression node
  // ---------------------------------------------
  struct xtree_node
  {
    // POST: evaluates the subtree with root *this
    virtual double eval () const = 0;

    // POST: the subtree with root *this is printed as
    //       fully parenthesized xexpression
    virtual void print (std::ostream& o) const = 0;

    // POST: returns the size (number of nodes) in the
    //       subtree with root *this
    virtual int size () const = 0;

    // POST: a copy of the subtree with root *this is made,
    //       and a pointer to its root node is returned
    virtual xtree_node* copy () const = 0;

    // POST: all nodes in the subtree with
    //       root *this are deleted
    virtual void clear () = 0;

    virtual ~xtree_node(){}; // needed just for technical reasons
  };

  // class for leaf nodes with numbers (no children)
  // -----------------------------------------------
  struct number_node: public xtree_node
  {
    double val;

    // constructor
    number_node (double v)
    : val (v)
    {}

    double eval () const
    {
      return val;
    }

    void print (std::ostream& o) const
    {
      o << val;
    }

    int size () const
    {
      return 1;
    }

    xtree_node* copy () const
    {
      return new number_node (val);
    }

    void clear ()
    {
      delete this;
    }
  };

  // class for leaf nodes with variables (no children)
  // -------------------------------------------------
  struct variable_node: public xtree_node
  {
    double* ptr;

    // constructor
    variable_node (double* p)
    : ptr (p)
    {}

    double eval () const
    {
      return *ptr;
    }

    void print (std::ostream& o) const
    {
      o << '[' << ptr << ']';
    }

    int size () const
    {
      return 1;
    }

    xtree_node* copy () const
    {
      return new variable_node (ptr);
    }
    
    void clear ()
    {
      delete this;
    }
  };


  // (abstract) class for unary nodes (only a right child)
  // -----------------------------------------------------
  struct unary_node: public xtree_node
  {
    xtree_node* right; // INV != 0

    // constructor
    unary_node (xtree_node* r)
    : right (r)
    {
      assert (right);
    }

    int size () const
    {
      return 1 + right->size();
    }

    virtual void clear ()
    {
      right->clear();
      delete this;
    }

    // eval, print, copy defined in subclasses
  };

  // class for unary minus node
  // --------------------------
  struct minus_node: public unary_node
  {
    // constructor
    minus_node (xtree_node* r)
    : unary_node (r)
    {}

    double eval () const
    {
      return -right->eval();
    }

    void print (std::ostream& o) const
    {
      o << "-(";
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new minus_node (right->copy());
    }
  };

  // (abstract) class for binary nodes (left and right child)
  // --------------------------------------------------------
  struct binary_node: public xtree_node
  {
    xtree_node* left; // INV != 0
    xtree_node* right; // INV != 0

    // constructor
    binary_node (xtree_node* l, xtree_node* r)
      : left (l), right (r)
    {
      assert (left);
      assert (right); 
    }

    int size () const
    {
      return 1 + left->size() + right->size();
    }

    virtual void clear ()
    {
      left->clear();
      right->clear();
      delete this;
    }

    // eval, print, copy defined in subclasses
  };

  // class for binary + nodes
  // ------------------------
  struct add_node : public binary_node
  {
    // constructor
    add_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() + right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '+';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new add_node (left->copy(), right->copy());
    }
  };

  // class for binary - nodes
  // ------------------------
  struct sub_node : public binary_node
  {
    // constructor
    sub_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() - right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '-';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new sub_node (left->copy(), right->copy());
    }
  };

  // class for binary * nodes
  // ------------------------
  struct mul_node : public binary_node
  {
    // constructor
    mul_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() * right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '*';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new mul_node (left->copy(), right->copy());
    }
  };

  // class for binary / nodes
  // ------------------------
  struct div_node : public binary_node
  {
    // constructor
    div_node (xtree_node* l, xtree_node* r)
      : binary_node (l, r)
    {}

    double eval () const
    {
      return left->eval() / right->eval();
    }

    void print (std::ostream& o) const
    {
      o << '(';
      left->print(o);
      o << '/';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new div_node (left->copy(), right->copy());
    }
  };

  // class for abs nodes
  // -------------------
  struct abs_node: public unary_node
  {
    // constructor
    abs_node (xtree_node* arg)
    : unary_node (arg)
    {}

    double eval () const
    {
      return std::abs (right->eval());
    }

    void print (std::ostream& o) const
    {
      // internal node
      o << "abs" << '(';
      right->print(o);
      o << ')';
    }

    xtree_node* copy () const
    {
      return new abs_node (right->copy());
    }
  };

  class xexpression
  {
  private:
    xtree_node* root;

  public:

    // POST: *this is an empty xexpression
    xexpression ()
      : root (0)
    {}

    // POST: *this has one node with value d
    xexpression (double d)
    : root (new number_node (d))
    {}

    // POST: *this has one node whose value is found
    //       at address ptr
    xexpression (double* ptr)
    : root (new variable_node (ptr))
    {}

    // copy constructor
    xexpression (const xexpression& v)
      : root (v.root ? v.root->copy() : 0)
    {}

    // assignment operator
    xexpression& operator= (const xexpression& v)
    {
       if (root != v.root) { 
        if (root) 
	  root->clear();
	root = v.root ? v.root->copy() : 0;
      }
      return *this;
    }

    // replaces *this with -(*this)
    xexpression& negate ()
    {
      root = new minus_node (root);
      return *this;
    }

    // += operator
    xexpression& operator+= (const xexpression& t)
    {
      assert(t.root);
      root = new add_node (root, t.root->copy());
      return *this;
    }

    // -= operator
    xexpression& operator-= (const xexpression& t)
    {
      assert(t.root);
      root = new sub_node (root, t.root->copy());
      return *this;
    }

    // *= operator
    xexpression& operator*= (const xexpression& t)
    {
      assert(t.root);
      root = new mul_node (root, t.root->copy());
      return *this;
    }

    // /= operator
    xexpression& operator/= (const xexpression& t)
    {
      assert(t.root);
      root = new div_node (root, t.root->copy());
      return *this;
    }

    // replaces *this with abs (*this)
    xexpression& abs()
    {
      root = new abs_node(root);
      return *this;
    }

    // destructor
    ~xexpression ()
    {
      if (root) {
	root->clear();
      }
    }

    // POST: evaluates *this
    double evaluate () const
    {
      if (root) return root->eval();
      return 0;
    }

    // POST: *this is printed as fully
    //       parenthesized xexpression
    void print (std::ostream& o) const
    {
      if (root) root->print (o);
    }

  };

  // POST: l + r is returned
  xexpression operator+ (const xexpression& l, const xexpression& r)
  {
    xexpression result = l;
    return result += r;
  }

  // POST: l - r is returned
  xexpression operator- (const xexpression& l, const xexpression& r)
  {
    xexpression result = l;
    return result -= r;
  }

  // POST: l * r is returned
  xexpression operator* (const xexpression& l, const xexpression& r)
  {
    xexpression result = l;
    return result *= r;
  }

  // POST: l / r is returned
  xexpression operator/ (const xexpression& l, const xexpression& r)
  {
    xexpression result = l;
    return result /= r;
  }

  // POST: -r is returned
  xexpression operator- (const xexpression &r)
  {
    xexpression result = r;
    return result.negate();
  }

  // POST: abs (r) is returned
  xexpression abs (const xexpression &r)
  {
    xexpression result = r;
    return result.abs();
  }

  // POST: *this is written to o
  std::ostream& operator<< (std::ostream& o, const xexpression& v)
  {
    v.print(o);
    return o;
  }

} // end namespace ifmp