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