SubQueryParser.java
001 /*
002  *  SubQueryParser.java
003  *
004  *  Niraj Aswani, 19/March/07
005  *
006  *  $Id: SubQueryParser.html,v 1.0 2007/03/19 16:22:01 niraj Exp $
007  */
008 package gate.creole.annic.lucene;
009 
010 import java.io.*;
011 import java.util.*;
012 
013 import gate.creole.ir.SearchException;
014 
015 /**
016  * This class behaves as a helper class to the QueryParser and provides
017  * various methods which are called from various methods of QueryParser.
018  
019  @author niraj
020  */
021 public class SubQueryParser {
022 
023   public static void main(String[] args) {
024     try {
025 
026       BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
027       while(true) {
028         System.out.print("Query: ");
029         String line = in.readLine();
030 
031         if(line.length() == -1break;
032 
033         List<String> queries = parseQuery(line);
034         for(int i = 0; i < queries.size(); i++) {
035           System.out.println("=>" + queries.get(i));
036         }
037       }
038     }
039     catch(Exception e) {
040       e.printStackTrace();
041     }
042 
043   }
044 
045   /**
046    * Method retrieves wild card characters after the closing bracket.
047    */
048   private static String findWildCardString(int brClPos, String query) {
049     String wcs = "";
050     if(brClPos + < query.length()) {
051       if(query.charAt(brClPos + 1== '*' || query.charAt(brClPos + 1== '+' || query.charAt(brClPos + 1== '?') {
052         wcs = query.charAt(brClPos + 1"";
053         // ok so lets fetch the number
054         for(int i = brClPos + 2; i < query.length(); i++) {
055           if(Character.isDigit(query.charAt(i))) {
056             wcs += query.charAt(i);
057           }
058           else {
059             break;
060           }
061         }
062       }
063     }
064     return wcs;
065   }
066 
067   /**
068    * This method, interprets the wild cards and convert query
069    * accordingly. For example: (A)+3 is converted into ((A) | ((A)(A)) |
070    * ((A)(A)(A)))
071    */
072   private static String extractWildcards(String querythrows SearchException {
073     outer: while(true) {
074       char ch = ' ', pre = ' ';
075       for(int i = 0; i < query.length(); i++) {
076         pre = ch;
077         ch = query.charAt(i);
078 
079         // check if it is an open bracket
080         // it is if it doesn't follow the '\' escape sequence
081         if(isOpenBracket(ch, pre)) {
082 
083           // so find out where it gets closed
084           int brClPos = findBracketClosingPosition(i + 1, query);
085           if(brClPos == -1) {
086             throw new SearchException("unbalanced brackets",
087               "a closing bracket ()) is missing for this opening bracket", query, i);
088           }
089 
090           String wildCardString = findWildCardString(brClPos, query);
091           int wcsLen = 0;
092           boolean atLeastOne = false;
093 
094           // at least once
095           int repeatClause = 1;
096 
097           if(wildCardString.length() != 0) {
098             if(wildCardString.length() == 1) {
099               // if there is only wildcard char sign
100               // we consider it as 1
101               wcsLen = 1;
102             }
103             else {
104               atLeastOne = (wildCardString.charAt(0== '*' || wildCardString.charAt(0== '?'false true;
105               // now find out the number of Times we need to
106               // duplicate the bracketClause
107               repeatClause = Integer.parseInt(wildCardString.substring(1,
108                       wildCardString.length()));
109               wcsLen = wildCardString.length();
110             }
111 
112             String previous = query.substring(0, i);
113             String after = query
114                     .substring(brClPos + wcsLen + 1, query.length());
115             String sToRepeat = query.substring(i, brClPos + 1);
116 
117             String newString = "(";
118             for(int k = 1; k <= repeatClause; k++) {
119               newString += "(";
120               for(int subK = 0; subK < k; subK++) {
121                 newString += sToRepeat;
122               }
123               newString += ")";
124               if(k + <= repeatClause) {
125                 newString += " | ";
126               }
127             }
128 
129             if(!atLeastOne) {
130               newString += "| {__o__}";
131             }
132 
133             newString += ")";
134             query = previous + newString + after;
135             continue outer;
136           }
137         }
138       }
139 
140       // if we are here
141       // that means no whildcard left
142       return query;
143     }
144   }
145 
146   /**
147    * this method parses the query and returns the different queries
148    * converted into the OR normalized form 
149    * for e.g. ({A}|{B}){C} 
150    * this will be converted into ({A}{C}) | ({B}{C}) 
151    * and the arrayList consists of 
152    * 1. {A}{C} 
153    * 2. {B}{C}
154    */
155   public static List<String> parseQuery(String q1throws SearchException {
156 
157     // arraylist to return - will contain all the OR normalized queries
158     List<String> queries = new ArrayList<String>();
159 
160     // remove all extra spaces from the query
161     q1 = q1.trim();
162 
163     // we add opening and closing brackets explicitly
164     q1 = "( " + q1 + " )";
165 
166     q1 = extractWildcards(q1);
167     // add the main Query in the arraylist
168     queries.add(q1);
169 
170     for(int index = 0; index < queries.size(); index++) {
171       // get the query to be parsed
172       String query = queries.get(index);
173 
174       // current character and the previous character
175       char ch = ' ', pre = ' ';
176 
177       // if query is ORed
178       // we need duplication
179       // for example: {A}({B}|{C})
180       // the normalized form will be
181       // {A}{B}
182       // {A}{C}
183       // here we need {A} to be duplicated two times
184       boolean duplicated = false;
185       int dupliSize = 0;
186       String data = "";
187 
188       // we need to look into one query at a time and parse it
189       for(int i = 0; i < query.length(); i++) {
190         pre = ch;
191         ch = query.charAt(i);
192 
193         // check if it is an open bracket
194         // it is if it doesn't follow the '\' escape sequence
195         if(isOpenBracket(ch, pre)) {
196 
197           // so find out where it gets closed
198           int brClPos = findBracketClosingPosition(i + 1, query);
199           if(brClPos == -1) {
200             throw new SearchException("unbalanced brackets",
201               "a closing bracket ()) is missing for this opening bracket", query, i);
202           }
203 
204           // see if there are any OR operators in it
205           ArrayList<String> orTokens = findOrTokens(query.substring(i + 1, brClPos));
206 
207           // orTokens will have
208           // for eg. {A} | ({B}{C})
209           // then {A}
210           // and ({B}{C})
211           // so basically findOrTokens find out all the tokens around
212           // | operator
213           if(orTokens.size() 1) {
214             String text = "";
215 
216             // data contains all the buffered character before the
217             // current positions
218             // for example "ABC" ({B} | {C})
219             // here "ABC" will be in data
220             // and {B} and {C} in orTokens
221             if(!duplicated && data.length() 0) {
222               text = data;
223               data = "";
224             }
225             else {
226               if(index == queries.size() 1) {
227                 // this is the case where we would select the
228                 // text as ""
229                 text = "";
230               }
231               else {
232                 text = queries.get(queries.size() 1);
233               }
234             }
235 
236             // so we need to duplicate the text orTokens.size()
237             // times
238             // for example "ABC" ({B} | {C})
239             // text = "ABC"
240             // orTokens {B} {C}
241             // so two queries will be added
242             // 1. "ABC"
243             // 2. "ABC"
244 
245             queries = duplicate(queries, text, dupliSize, orTokens.size());
246             // and tokens will be added
247             // 1. "ABC" {B}
248             // 2. "ABC" {C}
249             queries = writeTokens(orTokens, queries, dupliSize);
250 
251             // text is duplicated so make it true
252             duplicated = true;
253 
254             // and how many times it was duplicated
255             if(dupliSize == 0dupliSize = 1;
256             dupliSize *= orTokens.size();
257           }
258           else {
259             // what if the there is only one element between ( and )
260             // it is not an 'OR' query
261 
262             // check how many times we have duplicated the text
263             if(dupliSize == 0) {
264               // if zero and the text buffered is ""
265               // we simply add "" as a separate Query
266               // otherwise add the buffered data as a separate
267               // Query
268               if(data.length() == 0)
269                 queries.add("");
270               else queries.add(data);
271 
272               // because we simply needs to add it only once
273               // but still we have copied it as a separate query
274               // so say duplicated = true
275               duplicated = true;
276               data = "";
277               // and ofcourse the size of the duplication will be
278               // only 1
279               dupliSize = 1;
280             }
281             // and we need to add all the contents between two
282             // brackets in the last duplicated
283             // queries
284             queries = writeStringInAll(query.substring(i + 1, brClPos),
285                     dupliSize, queries);
286           }
287           i = brClPos;
288         }
289         else if(isClosingBracket(ch, pre)) {
290           throw new SearchException("unbalanced brackets",
291             "a opening bracket (() is missing for this closing bracket", query, i);
292         }
293         else {
294           if(duplicated) {
295             queries = writeCharInAll(ch, dupliSize, queries);
296           }
297           else {
298             data += "" + ch;
299           }
300         }
301       }
302 
303       boolean scan = scanQueryForOrOrBracket(query);
304       if(scan) {
305         queries.remove(index);
306         index--;
307       }
308     }
309 
310     ArrayList<String> queriesToReturn = new ArrayList<String>();
311     for(int i = 0; i < queries.size(); i++) {
312       String q = queries.get(i);
313       if(q.trim().length() == 0) {
314         continue;
315       }
316       else if(queriesToReturn.contains(q.trim())) {
317         continue;
318       }
319       else {
320         queriesToReturn.add(q.trim());
321       }
322     }
323     return queriesToReturn;
324   }
325 
326   /**
327    * This method checks if query has either | or ( in it.
328    */
329   public static boolean scanQueryForOrOrBracket(String query) {
330     int index = 0;
331     int index1 = 0;
332     do {
333       index = query.indexOf('|', index);
334       if(index == 0) {
335         return true;
336       }
337       else if(index > 0) {
338         // we have found it but we need to check if it is an escape
339         // sequence
340         if(query.charAt(index - 1== '\\') {
341           // yes it is an escape sequence
342           // lets search for the next one
343         }
344         else {
345           return true;
346         }
347       }
348 
349       // if we are here that means it was not found
350       index1 = query.indexOf('(', index1);
351       if(index1 == 0) {
352         return true;
353       }
354       else if(index1 > 0) {
355         // we have found it
356         if(query.charAt(index1 - 1== '\\') {
357           // yes it is an escape sequence
358           continue;
359         }
360         else {
361           return true;
362         }
363       }
364 
365     while(index >= && index1 >= 0);
366 
367     return false;
368   }
369 
370   /**
371    * This is a helper method that helps in duplicating the provided tokens.
372    */
373   private static List<String> writeTokens(List<String> tokens, List<String> queries,
374           int dupliSize) {
375     if(dupliSize == 0dupliSize = 1;
376 
377     ArrayList<String> qToRemove = new ArrayList<String>();
378     for(int j = 0; j < dupliSize; j++) {
379       for(int i = 1; i <= tokens.size(); i++) {
380         String token = tokens.get(i - 1);
381         if(token.trim().equals("{__o__}")) {
382           token = " ";
383         }
384         String s = queries
385                 .get(queries.size() (j * tokens.size() + i));
386         qToRemove.add(s);
387         s += token;
388         queries.set(queries.size() (j * tokens.size() + i), s);
389       }
390     }
391 
392     // and now remove
393     for(int i = 0; i < qToRemove.size(); i++) {
394       queries.remove(qToRemove.get(i));
395     }
396 
397     return queries;
398   }
399 
400   /**
401    * This is a helper method that helps in duplicating the provided tokens.
402    */
403   private static List<String> duplicate(List<String> queries, String s, int dupliSize,
404           int no) {
405     if(s == nulls = "";
406 
407     List<String> strings = new ArrayList<String>();
408     if(dupliSize == 0) {
409       strings.add(s);
410     }
411     else {
412       for(int i = 0; i < dupliSize; i++) {
413         strings.add(queries.get(queries.size() (i + 1)));
414       }
415     }
416 
417     for(int i = 0; i < strings.size(); i++) {
418       for(int j = 0; j < no; j++) {
419         queries.add(strings.get(i));
420       }
421     }
422 
423     return queries;
424   }
425 
426   /**
427    * This method given a query identifies the OR Tokens
428    * for eg. {A} | ({B}{C})
429    * then {A}
430    * and ({B}{C})
431    * so basically findOrTokens find out all the tokens around
432    * | operator
433    */
434   public static ArrayList<String> findOrTokens(String query) {
435     int balance = 0;
436     char pre = ' ';
437     char ch = ' ';
438     ArrayList<String> ors = new ArrayList<String>();
439 
440     String s = "";
441     for(int i = 0; i < query.length(); i++) {
442       pre = ch;
443       ch = query.charAt(i);
444       if(isOpenBracket(ch, pre)) {
445         balance++;
446         s += "" + ch;
447         continue;
448       }
449 
450       if(isClosingBracket(ch, pre&& balance > 0) {
451         balance--;
452         s += "" + ch;
453         continue;
454       }
455 
456       if(isOrSym(ch, pre)) {
457         if(balance > 0) {
458           s += "" + ch;
459           continue;
460         }
461         else {
462           ors.add(s);
463           s = "";
464           continue;
465         }
466       }
467 
468       s += "" + ch;
469     }
470 
471     if(s.length() 0ors.add(s);
472 
473     return ors;
474   }
475 
476   /**
477    * Returns the position of a closing bracket.
478    */
479   private static int findBracketClosingPosition(int startFrom, String query) {
480     int balance = 0;
481     char pre = ' ';
482     char ch = ' ';
483     for(int i = startFrom; i < query.length(); i++) {
484       pre = ch;
485       ch = query.charAt(i);
486       if(isOpenBracket(ch, pre)) {
487         balance++;
488         continue;
489       }
490 
491       if(isClosingBracket(ch, pre)) {
492         if(balance > 0) {
493           balance--;
494         }
495         else {
496           return i;
497         }
498       }
499     }
500     return -1;
501   }
502 
503   /**
504    * Helps in duplicating a character in the provided queries
505    */
506   private static List<String> writeCharInAll(char c, int no, List<String> queries) {
507     for(int i = 0; i < no; i++) {
508       String s = queries.get(queries.size() (i + 1));
509       s += "" + c;
510       queries.set(queries.size() (i + 1), s);
511     }
512     return queries;
513   }
514 
515   /**
516    * Helps in duplicating a string in the provided queries
517    */
518   private static List<String> writeStringInAll(String c, int no, List<String> queries) {
519     for(int i = 0; i < no; i++) {
520       String s = queries.get(queries.size() (i + 1));
521       s += "" + c;
522       queries.set(queries.size() (i + 1), s);
523     }
524     return queries;
525   }
526 
527   /**
528    * Returns if the character is bracket used to mark boundary of a token or an escape character.
529    */
530   private static boolean isOpenBracket(char ch, char pre) {
531     if(ch == '(' && pre != '\\')
532       return true;
533     else return false;
534   }
535 
536   /**
537    * Returns if the character is bracket used to mark boundary of a token or an escape character.
538    */
539   private static boolean isClosingBracket(char ch, char pre) {
540     if(ch == ')' && pre != '\\')
541       return true;
542     else return false;
543   }
544 
545   /**
546    * Returns if the character is an OR symbol used as a logical operator or an escape character.
547    */
548   private static boolean isOrSym(char ch, char pre) {
549     if(ch == '|' && pre != '\\')
550       return true;
551     else return false;
552   }
553 
554 }