001: package org.drools.rule;
002:
003: /*
004: * Copyright 2005 JBoss Inc
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: */
018:
019: import java.util.ArrayList;
020: import java.util.HashMap;
021: import java.util.Iterator;
022: import java.util.List;
023: import java.util.ListIterator;
024: import java.util.Map;
025:
026: /**
027: * LogicTransformation is reponsible for removing redundant nodes and move Or
028: * nodes upwards.
029: *
030: * This class does not turn Exists into two Nots at this stage, that role is
031: * delegated to the Builder.
032: *
033: * @author mproctor
034: *
035: */
036: class LogicTransformer {
037: private final Map orTransformations = new HashMap();
038:
039: private static LogicTransformer INSTANCE = null;
040:
041: static LogicTransformer getInstance() {
042: if (LogicTransformer.INSTANCE == null) {
043: LogicTransformer.INSTANCE = new LogicTransformer();
044: }
045:
046: return LogicTransformer.INSTANCE;
047: }
048:
049: LogicTransformer() {
050: initialize();
051: }
052:
053: /**
054: * sets up the parent->child transformations map
055: *
056: */
057: private void initialize() {
058: // these pairs will be transformed
059: addTransformationPair(GroupElement.NOT,
060: new NotOrTransformation());
061: addTransformationPair(GroupElement.EXISTS,
062: new ExistOrTransformation());
063: addTransformationPair(GroupElement.AND,
064: new AndOrTransformation());
065: }
066:
067: private void addTransformationPair(final GroupElement.Type parent,
068: final Transformation method) {
069: this .orTransformations.put(parent, method);
070: }
071:
072: public GroupElement[] transform(final GroupElement and)
073: throws InvalidPatternException {
074: final GroupElement cloned = (GroupElement) and.clone();
075:
076: processTree(cloned);
077: cloned.pack();
078:
079: GroupElement[] ands = null;
080: // is top element an AND?
081: if (cloned.isAnd()) {
082: // Yes, so just return it
083: ands = new GroupElement[] { cloned };
084: } else if (cloned.isOr()) {
085: // it is an OR, so each child is an AND branch
086: ands = new GroupElement[cloned.getChildren().size()];
087: int i = 0;
088: for (final Iterator it = cloned.getChildren().iterator(); it
089: .hasNext();) {
090: final RuleConditionElement branch = (RuleConditionElement) it
091: .next();
092: if ((branch instanceof GroupElement)
093: && (((GroupElement) branch).isAnd())) {
094: ands[i++] = (GroupElement) branch;
095: } else {
096: ands[i] = GroupElementFactory.newAndInstance();
097: ands[i].addChild(branch);
098: i++;
099: }
100: }
101: } else {
102: // no, so just wrap into an AND
103: final GroupElement wrapper = GroupElementFactory
104: .newAndInstance();
105: wrapper.addChild(cloned);
106: ands = new GroupElement[] { wrapper };
107: }
108: return ands;
109: }
110:
111: /**
112: * Traverses a Tree, during the process it transforms Or nodes moving the
113: * upwards and it removes duplicate logic statement, this does not include
114: * Not nodes.
115: *
116: * Traversal involves three levels the graph for each iteration. The first
117: * level is the current node, this node will not be transformed, instead
118: * what we are interested in are the children of the current node (called
119: * the parent nodes) and the children of those parents (call the child
120: * nodes).
121: *
122: * @param ce
123: */
124: void processTree(final GroupElement ce)
125: throws InvalidPatternException {
126:
127: boolean hasChildOr = false;
128:
129: // first we eliminicate any redundancy
130: ce.pack();
131:
132: for (final ListIterator it = ce.getChildren().listIterator(); it
133: .hasNext();) {
134: final Object object = it.next();
135: if (object instanceof GroupElement) {
136: final GroupElement child = (GroupElement) object;
137:
138: processTree(child);
139:
140: if (child.isOr()) {
141: hasChildOr = true;
142: }
143: }
144: }
145: if (hasChildOr) {
146: applyOrTransformation(ce);
147: }
148: }
149:
150: void applyOrTransformation(final GroupElement parent)
151: throws InvalidPatternException {
152: final Transformation transformation = (Transformation) this .orTransformations
153: .get(parent.getType());
154:
155: if (transformation == null) {
156: throw new RuntimeException(
157: "applyOrTransformation could not find transformation for parent '"
158: + parent.getType() + "' and child 'OR'");
159: }
160: transformation.transform(parent);
161: }
162:
163: interface Transformation {
164: void transform(GroupElement element)
165: throws InvalidPatternException;
166: }
167:
168: /**
169: * Takes any And that has an Or as a child and rewrites it to move the Or
170: * upwards
171: *
172: * (a||b)&&c
173: *
174: * <pre>
175: * and
176: * / \
177: * or c
178: * / \
179: * a b
180: * </pre>
181: *
182: * Should become (a&&c)||(b&&c)
183: *
184: * <pre>
185: *
186: * or
187: * / \
188: * / \
189: * / \
190: * and and
191: * / \ / \
192: * a c b c
193: * </pre>
194: */
195: class AndOrTransformation implements Transformation {
196:
197: public void transform(final GroupElement parent)
198: throws InvalidPatternException {
199: final List orsList = new ArrayList();
200: // must keep order, so, using array
201: final Object[] others = new Object[parent.getChildren()
202: .size()];
203:
204: // first we split children as OR or not OR
205: int permutations = 1;
206: int index = 0;
207: for (final Iterator it = parent.getChildren().iterator(); it
208: .hasNext();) {
209: final Object child = it.next();
210: if ((child instanceof GroupElement)
211: && ((GroupElement) child).isOr()) {
212: permutations *= ((GroupElement) child)
213: .getChildren().size();
214: orsList.add(child);
215: } else {
216: others[index] = child;
217: }
218: index++;
219: }
220:
221: // transform parent into an OR
222: parent.setType(GroupElement.OR);
223: parent.getChildren().clear();
224:
225: // prepare arrays and indexes to calculate permutation
226: final GroupElement[] ors = (GroupElement[]) orsList
227: .toArray(new GroupElement[orsList.size()]);
228: final int[] indexes = new int[ors.length];
229:
230: // now we know how many permutations we will have, so create it
231: for (int i = 1; i <= permutations; i++) {
232: final GroupElement and = GroupElementFactory
233: .newAndInstance();
234:
235: // create the actual permutations
236: int mod = 1;
237: for (int j = ors.length - 1; j >= 0; j--) {
238: // we must insert at the beggining to keep the order
239: and.getChildren().add(0,
240: ors[j].getChildren().get(indexes[j]));
241: if ((i % mod) == 0) {
242: indexes[j] = (indexes[j] + 1)
243: % ors[j].getChildren().size();
244: }
245: mod *= ors[j].getChildren().size();
246: }
247:
248: // elements originally outside OR will be in every permutation, so add them
249: // in their original position
250: for (int j = 0; j < others.length; j++) {
251: if (others[j] != null) {
252: // always add clone of them to avoid offset conflicts in declarations
253: and.getChildren().add(
254: j,
255: ((RuleConditionElement) others[j])
256: .clone());
257: }
258: }
259: parent.addChild(and);
260: }
261:
262: // remove duplications
263: parent.pack();
264: }
265: }
266:
267: /**
268: * (Exist (OR (A B)
269: *
270: * <pre>
271: * Exist
272: * |
273: * or
274: * / \
275: * a b
276: * </pre>
277: *
278: * (Exist ( Not (a) Not (b)) )
279: *
280: * <pre>
281: * Or
282: * / \
283: * Exists Exists
284: * | |
285: * a b
286: * </pre>
287: */
288: class ExistOrTransformation implements Transformation {
289:
290: public void transform(final GroupElement parent)
291: throws InvalidPatternException {
292: if ((!(parent.getChildren().get(0) instanceof GroupElement))
293: && (((GroupElement) parent.getChildren().get(0))
294: .isExists())) {
295: throw new RuntimeException(
296: "ExistOrTransformation expected 'OR' but instead found '"
297: + parent.getChildren().get(0)
298: .getClass().getName() + "'");
299: }
300:
301: /*
302: * we know an Exists only ever has one child, and the previous algorithm
303: * has confirmed the child is an OR
304: */
305: final GroupElement or = (GroupElement) parent.getChildren()
306: .get(0);
307: parent.setType(GroupElement.OR);
308: parent.getChildren().clear();
309: for (final Iterator it = or.getChildren().iterator(); it
310: .hasNext();) {
311: final GroupElement newExists = GroupElementFactory
312: .newExistsInstance();
313: newExists.addChild((RuleConditionElement) it.next());
314: parent.addChild(newExists);
315: }
316: parent.pack();
317: }
318: }
319:
320: /**
321: * (Not (OR (A B)
322: *
323: * <pre>
324: * Not
325: * |
326: * or
327: * / \
328: * a b
329: * </pre>
330: *
331: * (And ( Not (a) Exist (b)) )
332: *
333: * <pre>
334: * And
335: * / \
336: * Not Not
337: * | |
338: * a b
339: * </pre>
340: */
341: public class NotOrTransformation implements Transformation {
342:
343: public void transform(final GroupElement parent)
344: throws InvalidPatternException {
345:
346: if ((!(parent.getChildren().get(0) instanceof GroupElement))
347: && (((GroupElement) parent.getChildren().get(0))
348: .isOr())) {
349: throw new RuntimeException(
350: "NotOrTransformation expected 'OR' but instead found '"
351: + parent.getChildren().get(0)
352: .getClass().getName() + "'");
353: }
354:
355: /*
356: * we know a Not only ever has one child, and the previous algorithm
357: * has confirmed the child is an OR
358: */
359: final GroupElement or = (GroupElement) parent.getChildren()
360: .get(0);
361: parent.setType(GroupElement.AND);
362: parent.getChildren().clear();
363: for (final Iterator it = or.getChildren().iterator(); it
364: .hasNext();) {
365: final GroupElement newNot = GroupElementFactory
366: .newNotInstance();
367: newNot.addChild((RuleConditionElement) it.next());
368: parent.addChild(newNot);
369: }
370: parent.pack();
371: }
372: }
373:
374: //@todo for 3.1
375: // public class NotAndTransformation
376: // implements
377: // Transformation {
378: //
379: // public GroupElement transform(GroupElement not) throws InvalidPatternException {
380: // if ( !(not.getChildren().get( 0 ) instanceof And) ) {
381: // throw new RuntimeException( "NotAndTransformation expected '" + And.class.getName() + "' but instead found '" + not.getChildren().get( 0 ).getClass().getName() + "'" );
382: // }
383: //
384: // /*
385: // * we know a Not only ever has one child, and the previous algorithm
386: // * has confirmed the child is an And
387: // */
388: // And and = (And) not.getChildren().get( 0 );
389: // for ( Iterator it = and.getChildren().iterator(); it.hasNext(); ) {
390: // Object object1 = it.next();
391: //
392: // for ( Iterator it2 = and.getChildren().iterator(); it.hasNext(); ) {
393: // Object object2 = it.next();
394: // if ( object2 != object1 ) {
395: //
396: // }
397: // }
398: //
399: // Not newNot = new Not();
400: // newNot.addChild( it.next() );
401: // and.addChild( newNot );
402: // }
403: //
404: // return and;
405: // }
406: // }
407: }
|