1 karl 1.9 //%2006////////////////////////////////////////////////////////////////////////
|
2 chuck 1.2 //
|
3 karl 1.8 // Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
4 // Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
|
6 chuck 1.2 // IBM Corp.; EMC Corporation, The Open Group.
|
7 karl 1.8 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
9 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
|
11 karl 1.9 // Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.;
12 // EMC Corporation; Symantec Corporation; The Open Group.
|
13 chuck 1.2 //
14 // Permission is hereby granted, free of charge, to any person obtaining a copy
15 // of this software and associated documentation files (the "Software"), to
16 // deal in the Software without restriction, including without limitation the
17 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
18 // sell copies of the Software, and to permit persons to whom the Software is
19 // furnished to do so, subject to the following conditions:
|
20 karl 1.8 //
|
21 chuck 1.2 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
22 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
23 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
24 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
25 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
26 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
27 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 //
|
30 karl 1.8 //==============================================================================
|
31 chuck 1.2 //
32 // Author: Humberto Rivero (hurivero@us.ibm.com)
33 //
34 //
35 //%/////////////////////////////////////////////////////////////////////////////
36
37 #ifndef Cql2Dnf_h
38 #define Cql2Dnf_h
39
40 #include <Pegasus/Common/Stack.h>
41 //#include <Pegasus/WQL/WQLOperation.h>
42 //#include <Pegasus/WQL/WQLOperand.h>
43 #include <Pegasus/CQL/CQLSelectStatement.h>
44 #include <Pegasus/CQL/CQLSimplePredicate.h>
45 #include <Pegasus/CQL/CQLPredicate.h>
46 #include <Pegasus/CQL/CQLExpression.h>
47
48 PEGASUS_NAMESPACE_BEGIN
49
50 #undef PEGASUS_COMMON_LINKAGE
51 #define PEGASUS_COMMON_LINKAGE
52 chuck 1.2
53 #include <Pegasus/Common/Linkage.h>
54
|
55 humberto 1.6 enum OperationType { CQL_LT, CQL_GT, CQL_EQ, CQL_LE, CQL_GE, CQL_NE, CQL_IS_NULL, CQL_IS_NOT_NULL, CQL_AND, CQL_OR, CQL_NOT, CQL_NOOP, CQL_ISA, CQL_LIKE};
|
56 chuck 1.2
57 class term_el
58 {
59 public:
|
60 humberto 1.6 term_el(){}
|
61 chuck 1.2 term_el(Boolean m, CQLSimplePredicate simplePredicate) :
|
62 humberto 1.7 mark(m), _simplePredicate(simplePredicate), NOT(false){}
|
63 chuck 1.2 Boolean mark;
64 CQLSimplePredicate _simplePredicate;
|
65 humberto 1.6 Boolean NOT;
|
66 chuck 1.2 void negate();
67 //int toStrings(CMPIType &typ, CMPIPredOp &opr, String &o1, String &o2) const;
68 };
69
70 class stack_el
71 {
72 public:
73 stack_el() {}
74 stack_el(int o, Boolean i) : opn(o), is_terminal(i) {}
75 int opn; // either to terminals or eval_heap
76 Boolean is_terminal;
77 };
78
79
80 class eval_el
81 {
82 public:
83 eval_el() {}
84 eval_el(Boolean m, OperationType o, int op1, Boolean i1, int op2, Boolean i2) :
85 mark(m), op(o), opn1(op1), is_terminal1(i1), opn2(op2), is_terminal2(i2) {}
86 Boolean mark;
87 chuck 1.2 OperationType op;
88 int opn1;
89 Boolean is_terminal1; // if yes, look in terminal Array
90 int opn2;
91 Boolean is_terminal2; // if no, look in eval heap
92
93 stack_el getFirst();
94
95 stack_el getSecond();
96
97 void setFirst(const stack_el s);
98
99 void setSecond(const stack_el s);
100
101 void assign_unary_to_first(const eval_el & assignee);
102
103 void assign_unary_to_second(const eval_el & assignee);
104
105 // Ordering operators, so that op1 > op2 for all non-terminals
106 // and terminals appear in the second operand first
107 void order(void);
108 chuck 1.2 };
109
110 #define PEGASUS_ARRAY_T term_el
111 # include <Pegasus/Common/ArrayInter.h>
112 #undef PEGASUS_ARRAY_T
113
114 #define PEGASUS_ARRAY_T eval_el
115 # include <Pegasus/Common/ArrayInter.h>
116 #undef PEGASUS_ARRAY_T
117
118 #define PEGASUS_ARRAY_T stack_el
119 # include <Pegasus/Common/ArrayInter.h>
120 #undef PEGASUS_ARRAY_T
121
122 #undef PEGASUS_COMMON_LINKAGE
123
124
125 class Cql2Dnf
126 {
127 public:
|
128 humberto 1.5 /*
|
129 chuck 1.2 Cql2Dnf();
130
131 Cql2Dnf(CQLSelectStatement& cqs);
132
133 Cql2Dnf(CQLSelectStatement * cqs);
|
134 humberto 1.5 */
135
136 /**
137 Contructs Cql2Dnf object. The predicate passed in is converted to DNF.
138
139 @param - topLevel. CQLPredicate to convert to DNF.
140 @return - None.
141 @throw - None.
142 <I><B>Experimental Interface</B></I><BR>
143 */
|
144 chuck 1.2
145 Cql2Dnf(CQLPredicate& topLevel);
146
|
147 humberto 1.5 /**
148 Destructs the Cql2Dnf object.
149
150 @param - None.
151 @return - None.
152 @throw - None.
153 <I><B>Experimental Interface</B></I><BR>
154 */
|
155 chuck 1.2 ~Cql2Dnf();
|
156 humberto 1.5 /*
157 void compile (CQLSelectStatement * cqs);
158 */
|
159 chuck 1.2
160 void compile (CQLPredicate& topLevel);
|
161 humberto 1.5 /*
|
162 chuck 1.2 void print();
|
163 humberto 1.5 */
164 /**
165 Gets the DNF converted CQLPredicate.
166
167 @param - None.
168 @return - The CQLPredicate in DNF.
169 @throw - None.
170 <I><B>Experimental Interface</B></I><BR>
171 */
|
172 chuck 1.2 CQLPredicate getDnfPredicate();
173
174 protected:
|
175 humberto 1.5
176 /**
177 Preps the DNF algorithm. Fills the _operations and _operands objects for later processing.
178
179 @param - None.
180 @return - None.
181 @throw - None.
182 <I><B>Experimental Interface</B></I><BR>
183 */
|
184 chuck 1.2 void _buildEvalHeap();
185
186 void _pushNOTDown(void);
187
188 void _factoring(void);
189
|
190 humberto 1.5 /**
191
192 This function takes a CQLSelectStatement and does a depth first search looking for the operations and operands.
193 The operations are appended to the _operations array and the operands appended to the _operands array
194 When finished, we will have two arrays, representing the statement tree, from which we can start the process
195 to put the statement into DNF.
196
197 Example: a=b^(!c=d v e=f)
198 _operations array will look like:
199 [=][=][!][=][v][^]
200 _operands array will look like:
201 [a][b][c][d][e][f]
202
203 @param - topLevel. CQLPredicate to extract operations and operands from
204 @return - None.
205 @throw - None.
206
207 */
|
208 chuck 1.2
209 void _strip_ops_operands(CQLPredicate& topLevel);
210
211 void _destruct(CQLPredicate& _p);
212
|
213 humberto 1.5 /**
|
214 chuck 1.2 //
215 // _construct()
216 //
217 // Each eval_el on the eval heap contains all the information needed to make a CQLPredicate.
218 // We will build a CQLPredicate for every element in the eval heap. So there is a 1 to 1 correspondence
219 // between elements in the eval heap and elements in the CQLPredicate array used below.
220 // The first eval_el on the eval heap will always contain at least one terminal if the operation is a NOT
221 // or two terminals if the operation is AND or OR. We are guaranteed to build a CQLPredicate from the first
222 // position in the eval_heap array.
223 //
224 // The key to the algorithm is the isterminalX flag. When set to true, we go to the
225 // term_heap and get the CQLSimplePredicate. When set to false, we go to the _preds array below
226 // and get the CQLPredicate. Since there is a 1 - 1 correspondence, as explained above, the index
227 // referred to by eval.opn1 or eval.opn2 is valid into the _preds array.
228 //
229 // For ANDs and ORs, we need two operands, as explained above, we get those operands
230 // from either the term_heap or the _preds array. For NOTs, we need only 1 operand, and that
231 // comes from either the term_heap or the _preds array.
232 //
233 // When finished, the last element in the _preds array contains the top level CQLPredicate (the rebuilt tree)
234 //
235 chuck 1.2 // Example: a=b^(!c=d v e=f)
236 // If the current eval_heap looks like:
237 // 0,NOT,1,True,-1,True [index = 0]
238 // 0,OR,2,True,0,False [index = 1]
239 // 0,AND,1,False,0,True [index = 2]
240 //
241 // And the current term_heap looks like:
242 // CQLSimplePredicate(a=b) [index = 0]
243 // CQLSimplePredicate(c=d) [index = 1]
244 // CQLSimplePredicate(e=f) [index = 0]
245 //
246 // The _preds array at the end would look like:
247 // CQLPredicate(!c==d) [index = 0]
248 // CQLPredicate(e==f v !c==d) [index = 1]
249 // CQLPredicate((e==f v !c==d) ^ a==b) [index = 2] (the rebuilt tree)
250 //
|
251 humberto 1.5
252 @param - None.
253 @return - None.
254 @throw - None.
255
256 */
257
|
258 chuck 1.2 void _construct();
259
|
260 humberto 1.5 /**
261 this is to prevent appending complex predicates to the top level predicate
262 the final DNFed predicate must only have simple predicates inside its predicate array
263
264 example:
265 say P = A AND B
266 say P1 = C AND D
267 say we need to OR them together
268 we cant call P.appendPredicate(P1,OR) because this creates one more complex predicate layer
269 instead we would:
270 -> get P1s predicates (which should all be simple)
271 -> append its first predicate to P along with the operator passed into us
272 -> so conceptually at this point we have P = A AND B OR C
273 -> then go through P1s remaining predicates and append them and P1s operators to P
274 -> when done we have P = A AND B OR C AND D INSTEAD of having P = A AND B OR P1 where P1 is a complex predicate
275
276
277 @param topLevel, CQLPredicate that will contain CQLPredicate p
278 @param op, The operation AND / OR
279 @param p, CQLPredicate to add to topLevel.
280 @return - None.
281 humberto 1.5 @throw - None.
282 */
|
283 humberto 1.3 CQLPredicate _flattenANDappend(CQLPredicate& topLevel, BooleanOpType op, CQLPredicate& p);
284
|
285 chuck 1.2 OperationType _convertOpType(ExpressionOpType op);
|
286 humberto 1.3
|
287 chuck 1.2 ExpressionOpType _convertOpType(OperationType op);
288
289 private:
290
291 //
292 // The eval_heap structure contains an ordered tree of non-terminal
293 // expressions, the term_heap structure the corresponding terminal
294 // expressions
295 //
296
297 Stack<term_el> terminal_heap;
298
299 Array<eval_el> eval_heap;
300
|
301 humberto 1.3 Array<CQLExpression> _operands; // contains all the operands from the original top level predicate
302
303 Array<OperationType> _operations; // contains all the operations from the original top level predicate
304
305 CQLPredicate _dnfPredicate; // the final DNFed predicate
|
306 chuck 1.2 };
307
308
309 PEGASUS_NAMESPACE_END
310
311 #endif /* Cql2Dnf_h */
|