001 /**
002 * Copyright (c) 2010, SIB. All rights reserved.
003 *
004 * SIB (Swiss Institute of Bioinformatics) - http://www.isb-sib.ch Host -
005 * https://sourceforge.net/projects/javaprotlib/
006 *
007 * Redistribution and use in source and binary forms, with or without
008 * modification, are permitted provided that the following conditions are met:
009 * Redistributions of source code must retain the above copyright notice, this
010 * list of conditions and the following disclaimer. Redistributions in binary
011 * form must reproduce the above copyright notice, this list of conditions and
012 * the following disclaimer in the documentation and/or other materials provided
013 * with the distribution. Neither the name of the SIB/GENEBIO nor the names of
014 * its contributors may be used to endorse or promote products derived from this
015 * software without specific prior written permission.
016 *
017 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
018 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
019 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
020 * ARE DISCLAIMED. IN NO EVENT SHALL SIB/GENEBIO BE LIABLE FOR ANY DIRECT,
021 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
022 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
023 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
024 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
026 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027 */
028 package org.expasy.jpl.commons.base.cond;
029
030
031 import java.text.ParseException;
032 import java.util.HashMap;
033 import java.util.Map;
034 import java.util.regex.Matcher;
035 import java.util.regex.Pattern;
036 import org.expasy.jpl.commons.base.builder.Interpreter;
037 import org.expasy.jpl.commons.base.cond.ConditionImpl.ConditionRuntimeException;
038 import org.expasy.jpl.commons.base.cond.operator.OperatorManager;
039 import org.expasy.jpl.commons.base.cond.operator.OperatorManager.InvalidOperatorException;
040
041
042 /**
043 * {@code ConditionInterpreter} translates condition type expressions into
044 * {@code Condition}. It helps building complex {@code ConditionImpl}s.
045 *
046 * <p>
047 * Expressions are represented as an expression tree. [conditional] Expression
048 * trees represent code in a tree-like data structure, where each node is a
049 * expression over condition.
050 * </p>
051 *
052 * <p>
053 * A complex conditional expression is an expression of simple condition {@code
054 * operands} (defined internally as variable (CVAR)) and classic unary (OR) and
055 * binary {@code operators} (AND, OR). Here is the grammar below:
056 * </p>
057 *
058 * <p>
059 * EXPR := COND | NOT? EXPR<br/>
060 * COND := CVAR BOP COND<br/>
061 * CVAR := \w+<br/>
062 * BOP := AND | OR<br/>
063 * NOT := '!' <br/>
064 * AND := '&'<br/>
065 * OR := '|'<br/>
066 * </p>
067 *
068 * How to create a complex condition ?
069 * <ol>
070 * <li>register simple conditions in engine as variables (CVAR).</li>
071 * <li>compile engine with a given string expression of defined variables (CVAR)
072 * and logical operators (NOT, AND and OR).</li>
073 * <li>get and test the condition as a simple condition {@code Condition}.</li>
074 * </ol>
075 *
076 * Example:
077 *
078 * <pre>
079 * ConditionInterpreter<Double> interpreter =
080 * ConditionInterpreter.newInstance();
081 *
082 * engine.register("c1", new ConditionImpl.Builder<Double, Double>(0.)
083 * .operator(OperatorGreaterThan.newInstance()).build());<br/>
084 *
085 * engine.register("c2", new ConditionImpl.Builder<Double, Double>(10.)
086 * .operator(OperatorLowerThan.newInstance()).build());<br/>
087 *
088 * Condition<Double> condition = interpreter.translate("c1 & c2");
089 *
090 * Assert.assertTrue(condition.evaluate(4.));
091 * Assert.assertFalse(condition.evaluate(14.));
092 * </pre>
093 *
094 * @see ConditionImpl
095 *
096 * @author nikitin
097 *
098 * @version 1.0
099 *
100 */
101 public final class ConditionInterpreter<T> implements Interpreter<Condition<T>> {
102
103 private static final OperatorManager OPERATOR_MANAGER =
104 OperatorManager.getInstance();
105
106 /** the table with all condition variables */
107 private final Map<String, Condition<T>> conditions;
108
109 /** counter for condition naming */
110 private int counter;
111
112 private String currentConditionName;
113
114 /**
115 * <expression> ::= [ "not" ] <id> | "(" <expression> <operator>
116 * <expression> ")" <id> ::= <String> <operator> ::= "or" | "and"
117 */
118 private class Parser {
119
120 /** the expression to parse */
121 String expression;
122
123 /** current position on the expression */
124 int cursor = 0;
125
126 Parser(final String expression) {
127 this.expression = expression;
128 }
129
130 /**
131 * Create a new expression tree
132 *
133 * @return an expression
134 *
135 * @throws ParseException if invalid expression
136 */
137 Condition<T> parse() throws ParseException {
138 final Condition<T> tree = newAbstractSyntaxTree();
139 return tree;
140 }
141
142 /**
143 * Move cursor forward while blank character
144 */
145 private void skipBlanks() {
146 // Skip past any spaces and tabs on the current line of input.
147 // Stop at a non-blank character or end-of-line.
148 while ((cursor < expression.length())
149 && ((expression.charAt(cursor) == ' ') || (expression
150 .charAt(cursor) == '\t'))) {
151 cursor++;
152 }
153 }
154
155 /**
156 * @return the next identifier from current cursor position
157 */
158 private String getNextIdentifier() {
159 final Pattern pat = Pattern.compile("(\\w+).*");
160
161 final Matcher match = pat.matcher(expression.substring(cursor));
162
163 if (match.find()) {
164 cursor += match.end(1);
165
166 return match.group(1);
167 }
168
169 return null;
170 }
171
172 private Condition<T> newAbstractSyntaxTree() throws ParseException {
173 if (expression == null || expression.length() == 0) {
174 throw new ParseException("Cannot parse empty expression.", -1);
175 }
176
177 // Read an expression from the current line of input and
178 // return an expression tree representing the expression.
179 skipBlanks();
180 boolean not; // True if there is a leading minus sign.
181 not = false;
182
183 if (expression.charAt(cursor) == '!') {
184 cursor++;
185 not = true;
186 }
187
188 // The expression tree for the expression: start with the first
189 // term.
190 Condition<T> exp = expressionValue();
191
192 if (not) {
193 exp = new ConditionalUnaryNotOperator<T>(exp);
194 }
195 skipBlanks();
196
197 while ((cursor < expression.length())
198 && ((expression.charAt(cursor) == '&') || (expression
199 .charAt(cursor) == '|'))) {
200 // Read the next term and combine it with the
201 // previous terms into a bigger expression tree.
202 final char op = expression.charAt(cursor);
203 cursor++;
204 final Condition<T> nextTerm = newAbstractSyntaxTree();
205
206 exp = new ConditionalBinOperator<T>(op, exp, nextTerm);
207 skipBlanks();
208 }
209 return exp;
210 } // end newAbstractSyntaxTree()
211
212 private Condition<T> expressionValue() throws ParseException {
213
214 // Read an expression from the current line of input and
215 // return its value.
216 skipBlanks();
217
218 final char ch = expression.charAt(cursor);
219 if (Character.isJavaIdentifierPart(ch)) {
220 // The factor is a symbol. Return a ConstNode.
221 final String id = getNextIdentifier();
222 if (conditions.containsKey(id)) {
223 return conditions.get(id);
224 } else {
225 throw new ConditionRuntimeException(id
226 + " was not found in table of symbols");
227 }
228 } else if (ch == '(') {
229 // The factor is an expression in parentheses.
230 cursor++; // Read the "("
231 final Condition<T> exp = newAbstractSyntaxTree();
232 skipBlanks();
233 if (expression.charAt(cursor) != ')') {
234 throw new ParseException("Missing right parenthesis.",
235 cursor);
236 }
237 cursor++; // Read the ")"
238 return exp;
239 } else if (ch == '\n') {
240 throw new ParseException(
241 "End-of-line encountered in the middle of an expression.",
242 cursor);
243 } else if (ch == ')') {
244 throw new ParseException("Extra right parenthesis.", cursor);
245 } else if ((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/')) {
246 throw new ParseException("Misplaced operator.", cursor);
247 } else {
248 throw new ParseException("Unexpected character \"" + ch
249 + "\" encountered.", cursor);
250 }
251 }
252 }
253
254 /**
255 * Default constructor
256 */
257 private ConditionInterpreter() {
258 conditions = new HashMap<String, Condition<T>>();
259 }
260
261 public static <T> ConditionInterpreter<T> newInstance() {
262 return new ConditionInterpreter<T>();
263 }
264
265 /**
266 * Add a named condition in the condition table.
267 *
268 * @param conditionName the condition name.
269 * @param condition the condition instance.
270 */
271 public ConditionInterpreter<T> register(final String conditionName,
272 final Condition<T> condition) {
273
274 conditions.put(conditionName, condition);
275
276 return this;
277 }
278
279 /**
280 * Add anonymous condition instance in the condition table.
281 *
282 * <p>
283 * Do not forget to get
284 * </p>
285 *
286 * @param condition the condition instance.
287 */
288 public ConditionInterpreter<T> register(final Condition<T> condition) {
289
290 setNextConditionName(nextConditionName());
291
292 conditions.put(currentConditionName, condition);
293
294 return this;
295 }
296
297 /**
298 * @throws InvalidOperatorException
299 *
300 */
301 @SuppressWarnings("unchecked")
302 public ConditionInterpreter<T> register(final String conditionName,
303 final String condition) throws InvalidOperatorException {
304
305 String[] lvalOpRval = OPERATOR_MANAGER.getRvalueOpLvalue(condition);
306
307 conditions.put(conditionName, (Condition<T>) ConditionImpl.valueOf(
308 lvalOpRval[0], lvalOpRval[1], lvalOpRval[2]));
309
310 return this;
311 }
312
313 /**
314 * Add anonymous condition.
315 *
316 * @param condition the string format condition.
317 * @return the engine.
318 * @throws InvalidOperatorException
319 */
320 public ConditionInterpreter<T> register(final String condition)
321 throws InvalidOperatorException {
322
323 setNextConditionName(nextConditionName());
324
325 register(currentConditionName, condition);
326
327 return this;
328 }
329
330 /**
331 * @return the next generated condition name.
332 */
333 public String getNextConditionName() {
334 return currentConditionName;
335 }
336
337 /**
338 * Set the next condition name.
339 */
340 private void setNextConditionName(String name) {
341 currentConditionName = "_cond" + (counter++);
342 }
343
344 /**
345 * Generate and ..
346 *
347 * @return the next condition name.
348 */
349 private String nextConditionName() {
350 return "_cond" + (counter++);
351 }
352
353 /**
354 * Remove the condition.
355 *
356 * @param name the condition name.
357 * @return the removed condition.
358 */
359 public Condition<T> removeCondition(final String name) {
360
361 if (conditions.containsKey(name)) {
362 return conditions.remove(name);
363 }
364 return null;
365 }
366
367 /**
368 * Remove all conditions.
369 */
370 public void removeAllConditions() {
371 conditions.clear();
372 }
373
374 /**
375 * Get the condition given its name.
376 *
377 * @param name the condition name.
378 * @return the fetched condition.
379 */
380 public Condition<T> getCondition(final String name) {
381
382 if (conditions.containsKey(name)) {
383 return conditions.get(name);
384 }
385 return null;
386 }
387
388 /**
389 * @return the number of stored condition.
390 */
391 public int getNumOfCondition() {
392 return conditions.size();
393 }
394
395 /**
396 * Display the internal content of defined conditions variables.
397 */
398 public void traceInternalConditions() {
399 for (final String id : conditions.keySet()) {
400 System.out.println(id + ": " + conditions.get(id));
401 }
402 }
403
404 /**
405 * Parse expression and return a tree conditional expression.
406 *
407 * @param expression the expression to evaluate.
408 * @return a tree expression of conditions.
409 *
410 * @throws ParseException if invalid expression.
411 */
412 public Condition<T> translate(String expression) throws ParseException {
413
414 try {
415 expression = transform(expression);
416 } catch (InvalidOperatorException e) {
417 throw new ParseException(e.getMessage(), -1);
418 }
419
420 Parser parser = new Parser(expression);
421
422 return parser.parse();
423 }
424
425 private String transform(String expression) throws InvalidOperatorException {
426 StringBuilder sb = new StringBuilder();
427
428 // ex: !(x >= 0.6) | y > 0.8
429 // 1. locate ()!&|
430 // 2. add conditions
431 // addCondition("_cond0", "x>=0.6")
432 // addCondition("_cond1", "y>0.8")
433 // compile("!(_cond0) & _cond1");
434 Pattern pat = Pattern.compile("([&|)(!])");
435
436 Matcher matcher = pat.matcher(expression);
437
438 int nextStart = 0;
439
440 while (matcher.find()) {
441
442 String oper = matcher.group();
443
444 int beg = matcher.start();
445 int end = matcher.end();
446
447 String match = expression.substring(nextStart, beg).trim();
448
449 if (match.length() > 0) {
450 if (OPERATOR_MANAGER.isConditionContainsOperator(match)) {
451 register(match);
452 sb.append(currentConditionName);
453 } else {
454 sb.append(match);
455 }
456 }
457 sb.append(oper);
458
459 nextStart = end;
460 }
461
462 // get the right part expression
463 if (nextStart > 0) {
464 String match = expression.substring(nextStart).trim();
465
466 if (match.length() > 0) {
467 if (OPERATOR_MANAGER.isConditionContainsOperator(match)) {
468 register(match);
469 sb.append(currentConditionName);
470 } else {
471 sb.append(match);
472 }
473 }
474
475 return sb.toString();
476 } else if (OPERATOR_MANAGER.isConditionContainsOperator(expression)) {
477 // just a simple condition
478 register(expression);
479
480 return currentConditionName;
481 }
482 return expression;
483 }
484 }