Basic Polynomial Algebra Subprograms (BPAS)  v. 1.791
ExprTreeNode.hpp
1 
2 #ifndef _EXPR_TREE_NODE_
3 #define _EXPR_TREE_NODE_
4 
5 #include <string>
6 #include <gmpxx.h>
7 
8 //foward declaration.
9 class Symbol;
10 
11 /**
12  * The ExprTreeType enum indentifies the type of an ExprTreeNode.
13  * It is a way to differentiate between data-types and operators and so on.
14  *
15  * The special value EXPR_NONE is a default value to indicate that the ExprTreeNode
16  * is of no type and holds no value or meaning. Generally, this default value will
17  * occur during the building of an expression tree and is not meant to be used in
18  * a completed tree.
19  *
20  * EXPR_ARRAY indicates that the subtree rooted at this ExprTreeNode encodes an array.
21  * The structure of this sub-tree is left-leaning such that all right children are
22  * sub-trees encoding array elements and left children are again EXPR_ARRAY nodes.
23  * The array encoding continues until one EXPR_ARRAY node has a NULL left node,
24  * indicating that the array ends. The first element of the array is the one at
25  * the lowest level of the tree. The last element of the array is right-child of
26  * the second-top-most ELEM_ARRAY. The top-most ELEM_ARRAY node has a NULL right-child
27  * to indicate the end of the array.
28  */
29 enum ExprTreeType {
30  EXPR_NONE = 0x0,
31  EXPR_VAR,
32  EXPR_INT,
33  EXPR_MPZ,
34  EXPR_MPQ,
35  EXPR_ADD,
36  EXPR_SUB,
37  EXPR_MULT,
38  EXPR_DIV,
39  EXPR_EXP,
40  EXPR_NEG,
41  EXPR_SYM,
42  EXPR_ARRAY,
43  EXPR_DATA
44 };
45 
46 /**
47  * ExprTreeVal is the data element of a ExprTreeNode.
48  * the active union member is determined by the ExprTreeNode's type.
49  * The data elements here have a one-to-one correspondence to values int he
50  * ExprTreeType enum.
51  * For example EXPR_VAR <-> var, EXPR_INT <-> i, EXPR_MPZ <-> z.
52  *
53  * The final element void* genericData is meant to be 1) a default NULL value
54  * when the ExprTreeNode does not need any data itself (as is the case with an operator)
55  * or in the future when some flexible, generic data needs to be stored.
56  */
57 union ExprTreeVal {
58  std::string* var;
59  long int i;
60  mpz_class* z;
61  mpq_class* q;
62  Symbol* sym;
63  void* genericData;
64 };
65 
66 /**
67  * ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
68  * Nodes have a recursive structure, where each node is the root of a sub-tree
69  * with edges connecting *this node to the left and right sub-trees.
70  *
71  * Each tree has a type and a val. The type is used to specify how the val should
72  * interpreted.
73  *
74  * See Also, The enum ExprTreeType, and the union ExprTreeVal.
75  */
76 struct ExprTreeNode {
77  ExprTreeNode* left;
78  ExprTreeNode* right;
79  ExprTreeType type;
80  ExprTreeVal val;
81 
82  /**
83  * Construct a default, empty ExprTreeNode.
84  */
85  ExprTreeNode();
86 
87  /**
88  * Construct an ExprTreeNode given its type, value, and left and right children.
89  * Value and children can be NULL.
90  */
91  ExprTreeNode(ExprTreeType type, ExprTreeVal* val, ExprTreeNode* lNode, ExprTreeNode* rNode);
92 
93  /**
94  * Construct an ExprTreeNode of type EXPR_VAR with a copy of s as data.
95  */
96  ExprTreeNode(const std::string& s);
97 
98  /**
99  * Construct an ExprTreeNode of type EXPR_INT with i as data.
100  */
101  ExprTreeNode(long int i);
102 
103  /**
104  * Construct an ExprTreeNode of type EXPR_MPZ with a copy of z as data.
105  */
106  ExprTreeNode(const mpz_class& z);
107 
108  /**
109  * Construct an ExprTreeNode of type EXPR_MPQ with a copy of q as data.
110  */
111  ExprTreeNode(const mpq_class& q);
112 
113  /**
114  * Construct an ExpeTreeNode of type EXPR_SYM with a copy of s as data.
115  */
116  ExprTreeNode(const Symbol& s);
117 
118  /**
119  * ExprTreeNode destructor.
120  */
121  ~ExprTreeNode();
122 
123  /**
124  * Determine if *this or any of it's children is of type searchType.
125  *
126  * returns true iff searchType found.
127  */
128  bool findChildType(ExprTreeType searchType);
129 
130  /**
131  * Covnert *this to a string, depending on it's type and data.
132  * Only convert this particular node, not it's children. This allows
133  * for different tree traversals.
134  */
135  std::string toString() const;
136 
137 
138  /**
139  * Check to see if the expression rooted at *this encodes a variable
140  * or a variable to a power.
141  */
142  bool isVar() const;
143 
144  /**
145  * Check to see if the expression rooted at *this encodes a constant.
146  * That is, an integer, a rational number, etc.
147  */
148  bool isConstant() const;
149 
150  /**
151  * Check to see if the expression rooted at *this encodes a monomial.
152  *
153  * returns true iff *this encodes a monomial.
154  */
155  bool isPolynomialTerm() const;
156 
157  /**
158  * Get a deep copy of the tree rooted at root.
159  *
160  * Node that if the node or any its children hold data
161  * as a void* then that data will NOT be deeply copied.
162  *
163  * returns the new root
164  */
165  ExprTreeNode* deepCopy() const;
166 
167  ///////////////////
168  // Static Helpers
169  ///////////////////
170 
171  /**
172  * Creates a new ExprTreeNode and combines two sub-trees (lNode and rNode)
173  * by adjoining them to the newly created node as their root.
174  * The newly created node has type tType and val vVal (if vVal is not NULL).
175  */
176  static ExprTreeNode* combineExprTreeNodes(ExprTreeNode* lNode, ExprTreeNode* rNode, ExprTreeType tType, ExprTreeVal* vVal = NULL);
177 };
178 
179 #endif
ExprTreeVal is the data element of a ExprTreeNode.
Definition: ExprTreeNode.hpp:57
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
Definition: ExprTreeNode.hpp:76