001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021
022package org.biojava.bio.seq;
023
024import java.util.ArrayList;
025import java.util.HashSet;
026import java.util.List;
027
028import org.biojava.bio.AnnotationTools;
029import org.biojava.bio.AnnotationType;
030import org.biojava.bio.BioException;
031import org.biojava.bio.CardinalityConstraint;
032import org.biojava.bio.PropertyConstraint;
033import org.biojava.bio.symbol.Location;
034import org.biojava.bio.symbol.LocationTools;
035import org.biojava.utils.walker.Visitor;
036import org.biojava.utils.walker.Walker;
037import org.biojava.utils.walker.WalkerFactory;
038
039/**
040 * A set of FeatureFilter algebraic operations.
041 *
042 * @since 1.2
043 * @author Matthew Pocock
044 * @author Thomas Down
045 */
046
047public class FilterUtils {
048  
049    //that block avoids problems in WalkerFactory.generateWalker(Class visitorClass),
050    //if none of these filters are instanciated before invoking that method.
051    static {
052      new FeatureFilter.And(null,null);
053      new FeatureFilter.Or(null,null);
054      new FeatureFilter.Not(null);
055    } 
056  
057    private FilterUtils() {
058    }
059    
060    /**
061     * Determines if the set of features matched by sub can be <code>proven</code> to be a
062     * proper subset of the features matched by sup.
063     * <p>
064     * If the filter sub matches only features that are matched by sup, then it is
065     * a proper subset. It is still a proper subset if it does not match every
066     * feature in sup, as long as no feature matches sub that is rejected by sup.
067     * </p>
068     *
069     * @param sub the subset filter
070     * @param sup the superset filter
071     * @return <code>true</code> if <code>sub</code> is a proper subset of <code>sup</code>
072     */
073
074    public static boolean areProperSubset(FeatureFilter sub, FeatureFilter sup) {
075      // Preconditions
076
077      if (sub == null) {
078        throw new NullPointerException("Null FeatureFilter: sub");
079      }
080      if (sup == null) {
081        throw new NullPointerException("Null FeatureFilter: sup");
082      }
083
084      // Body
085
086      if(sub.equals(sup)) {
087        return true;
088      } else if (sup == all()) {
089        return true;
090      } else if (sub == none()) {
091        return true;
092      } else if (sup instanceof FeatureFilter.And) {
093        FeatureFilter.And and_sup = (FeatureFilter.And) sup;
094        return areProperSubset(sub, and_sup.getChild1()) && areProperSubset(sub, and_sup.getChild2());
095      } else if (sub instanceof FeatureFilter.And) {
096        FeatureFilter.And and_sub = (FeatureFilter.And) sub;
097        return areProperSubset(and_sub.getChild1(), sup) || areProperSubset(and_sub.getChild2(), sup);
098      } else if (sub instanceof FeatureFilter.Or) {
099        FeatureFilter.Or or_sub = (FeatureFilter.Or) sub;
100        return areProperSubset(or_sub.getChild1(), sup) && areProperSubset(or_sub.getChild2(), sup);
101      } else if (sup instanceof FeatureFilter.Or) {
102        FeatureFilter.Or or_sup = (FeatureFilter.Or) sup;
103        return areProperSubset(sub, or_sup.getChild1()) || areProperSubset(sub, or_sup.getChild2());
104      } else if (sup instanceof FeatureFilter.Not) {
105        FeatureFilter not_sup = ((FeatureFilter.Not) sup).getChild();
106        return areDisjoint(sub, not_sup);
107      } else if (sub instanceof FeatureFilter.Not) {
108        // How do we prove this one?
109        return false;  // return false for now
110      } else if (sub instanceof OptimizableFilter) {
111          // The works okay for ByFeature, too.
112        return ((OptimizableFilter) sub).isProperSubset(sup);
113      } else if(sup.equals(sub)) {
114        return true;
115      } else {
116        return false;
117      }
118    }
119
120    /**
121     * Determines if two queries can be proven to be disjoint.
122     * <p>
123     * They are disjoint if there is no element that is matched by both filters
124     * - that is, they have an empty intersection.  Order of arguments to this
125     * method is not significant.
126     * </p>
127     *
128     * @param a   the first FeatureFilter
129     * @param b   the second FeatureFilter
130     * @return <code>true</code> if they are proved to be disjoint, <code>false</code> otherwise
131     */
132
133    public static boolean areDisjoint(FeatureFilter a, FeatureFilter b) {
134        // System.err.println("Disjunction test of " + a + " | " + b);
135
136      // Preconditions
137
138      if (a == null) {
139        throw new NullPointerException("Null FeatureFilter: a");
140      }
141      if (b == null) {
142        throw new NullPointerException("Null FeatureFilter: b");
143      }
144
145      // Body
146
147      if(a.equals(b)) {
148        return false;
149      }
150
151      if(a == none() || b == none()) {
152        return true;
153      }
154
155      if (a == all()) {
156        return areProperSubset(b, FeatureFilter.none);
157      } else if(b == all()) {
158        return areProperSubset(a, FeatureFilter.none);
159      } else if (a == none() || b == none()) {
160        return true;
161      } if (a instanceof FeatureFilter.And) {
162        FeatureFilter.And and_a = (FeatureFilter.And) a;
163        return areDisjoint(and_a.getChild1(), b) || areDisjoint(and_a.getChild2(), b);
164      } else if (b instanceof FeatureFilter.And) {
165        FeatureFilter.And and_b = (FeatureFilter.And) b;
166        return areDisjoint(a, and_b.getChild1()) || areDisjoint(a, and_b.getChild2());
167      } else if (a instanceof FeatureFilter.Or) {
168        FeatureFilter.Or or_a = (FeatureFilter.Or) a;
169        return areDisjoint(or_a.getChild1(), b) && areDisjoint(or_a.getChild2(), b);
170      } else if (b instanceof FeatureFilter.Or) {
171        FeatureFilter.Or or_b = (FeatureFilter.Or) b;
172        return areDisjoint(a, or_b.getChild1()) && areDisjoint(a, or_b.getChild2());
173      } else if (a instanceof FeatureFilter.Not) {
174        FeatureFilter not_a = ((FeatureFilter.Not) a).getChild();
175        return areProperSubset(b, not_a);
176      } else if (b instanceof FeatureFilter.Not) {
177        FeatureFilter not_b = ((FeatureFilter.Not) b).getChild();
178        return areProperSubset(a, not_b);
179      } else if (a instanceof FeatureFilter.ByFeature) {
180          return ((FeatureFilter.ByFeature) a).isDisjoint(b);
181      } else if (b instanceof FeatureFilter.ByFeature) {
182          return ((FeatureFilter.ByFeature) b).isDisjoint(a);
183      } else if (a instanceof FeatureFilter.ByAncestor) {
184        return ((OptimizableFilter) a).isDisjoint(b);
185      } else if (b instanceof FeatureFilter.ByAncestor) {
186        return ((OptimizableFilter) b).isDisjoint(a);
187      } else if (a instanceof FeatureFilter.ByParent) {
188        return ((OptimizableFilter) a).isDisjoint(b);
189      } else if (b instanceof FeatureFilter.ByParent) {
190        return ((OptimizableFilter) b).isDisjoint(a);
191      } else if (a instanceof OptimizableFilter) {
192        return ((OptimizableFilter) a).isDisjoint(b);
193      } else if (b instanceof OptimizableFilter) {
194        return ((OptimizableFilter) b).isDisjoint(a);
195      }
196
197      // *SIGH* we don't have a proof here...
198
199      return false;
200    }
201
202    /**
203     * Try to determine the minimal location which all features matching a given
204     * filter must overlap.
205     *
206     * @param ff A feature filter
207     * @return the minimal location which any features matching <code>ff</code>
208     *          must overlap, or <code>null</code> if no proof is possible
209     *          (normally indicates that the filter has nothing to do with
210     *          location).
211     * @since 1.2
212     */
213
214    public static Location extractOverlappingLocation(FeatureFilter ff) {
215        if (ff instanceof FeatureFilter.OverlapsLocation) {
216            return ((FeatureFilter.OverlapsLocation) ff).getLocation();
217        } else if (ff instanceof FeatureFilter.ContainedByLocation) {
218            return ((FeatureFilter.ContainedByLocation) ff).getLocation();
219        } else if (ff instanceof FeatureFilter.And) {
220            FeatureFilter.And ffa = (FeatureFilter.And) ff;
221            Location l1 = extractOverlappingLocation(ffa.getChild1());
222            Location l2 = extractOverlappingLocation(ffa.getChild2());
223
224            if (l1 != null) {
225                if (l2 != null) {
226                    return l1.intersection(l2);
227                } else {
228                    return l1;
229                }
230            } else {
231                if (l2 != null) {
232                    return l2;
233                } else {
234                    return null;
235                }
236            }
237        } else if (ff instanceof FeatureFilter.Or) {
238            FeatureFilter.Or ffo = (FeatureFilter.Or) ff;
239            Location l1 = extractOverlappingLocation(ffo.getChild1());
240            Location l2 = extractOverlappingLocation(ffo.getChild2());
241
242            if (l1 != null && l2 != null) {
243                return LocationTools.union(l1, l2);
244            }
245        }
246
247        return null;
248    }
249
250  /**
251   * Decide if two feature filters accept exactly the same set of features.
252   *
253   * <p>
254   * Two feature filters are equal if it can be proven that
255   * <code>f1.accept(feature) == f2.accept(feature)</code> for all values of
256   * <code>feature</code>. If areEqual returns false, this may indicate that
257   * they accept clearly different sets of features. It may also, howerver,
258   * indicate that the method was unable to prove that they were equal.
259   * </p>
260   *
261   * <p>
262   * Note that given a finite set of features, f1 and f2 may match the same
263   * sub-set of those features even if they are not equal.
264   * </p>
265   *
266   * @param f1  the first filter
267   * @param f2  the second filter
268   * @return true if they can be proven to be equivalent
269   */
270  public final static boolean areEqual(FeatureFilter f1, FeatureFilter f2) {
271    if(f1 instanceof FeatureFilter.And && f2 instanceof FeatureFilter.And) {
272      List f1f = new ArrayList();
273      List f2f = new ArrayList();
274
275      expandAnd(f1, f1f);
276      expandAnd(f2, f2f);
277
278      return new HashSet(f1f).equals(new HashSet(f2f));
279    } else if(f1 instanceof FeatureFilter.And || f2 instanceof FeatureFilter.And) {
280      return false;
281    } else if(f1 instanceof FeatureFilter.Or && f2 instanceof FeatureFilter.Or) {
282      List f1f = new ArrayList();
283      List f2f = new ArrayList();
284
285      expandOr(f1, f1f);
286      expandOr(f2, f2f);
287
288      return new HashSet(f1f).equals(new HashSet(f2f));
289    } else if(f1 instanceof FeatureFilter.Or || f2 instanceof FeatureFilter.Or) {
290      return false;
291    } else {
292      return f1.equals(f2);
293    }
294  }
295
296  /**
297   * Construct a filter which matches features with a specific <code>type</code>
298   * value.
299   */
300  
301  public final static FeatureFilter byType(String type) {
302    return new FeatureFilter.ByType(type);
303  }
304
305  /**
306   * Construct a filter which matches features with a specific <code>source</code>
307   * value.
308   */
309  
310  public final static FeatureFilter bySource(String source) {
311    return new FeatureFilter.BySource(source);
312  }
313
314  /**
315   * Construct a filter which matches features which are assignable to the
316   * specified class or interface.
317   */
318  
319  public final static FeatureFilter byClass(Class clazz)
320  throws ClassCastException {
321    return new FeatureFilter.ByClass(clazz);
322  }
323
324  /** 
325   * Construct a filter which matches features with locations wholly contained
326   * by the specified <code>Location</code>.
327   */
328  
329  public final static FeatureFilter containedByLocation(Location loc) {
330    return new FeatureFilter.ContainedByLocation(loc);
331  }
332
333  /** 
334   * Construct a filter which matches features with locations contained by or
335   * overlapping the specified <code>Location</code>.
336   */
337  
338  public final static FeatureFilter overlapsLocation(Location loc) {
339    return new FeatureFilter.OverlapsLocation(loc);
340  }
341
342  /** 
343   * Construct a filter which matches features with locations where the interval
344   * between the <code>min</code> and <code>max</code> positions are contained by or
345   * overlap the specified <code>Location</code>.
346   */
347  
348  public final static FeatureFilter shadowOverlapsLocation(Location loc) {
349      return new FeatureFilter.ShadowOverlapsLocation(loc);
350  }
351  
352  /** 
353   * Construct a filter which matches features with locations where the interval
354   * between the <code>min</code> and <code>max</code> positions are contained by 
355   * the specified <code>Location</code>.
356   */
357  
358  public final static FeatureFilter shadowContainedByLocation(Location loc) {
359      return new FeatureFilter.ShadowContainedByLocation(loc);
360  }
361
362  /**
363   * Match features attached to sequences with a specified name.
364   */
365  
366  public final static FeatureFilter bySequenceName(String name) {
367    return new FeatureFilter.BySequenceName(name);
368  }
369
370  /**
371   * Construct a new filter which is the negation of <code>filter</code>.
372   */
373  
374  public final static FeatureFilter not(FeatureFilter filter) {
375    return new FeatureFilter.Not(filter);
376  }
377
378  /**
379   * Construct a new filter which matches the intersection of two other
380   * filters.
381   */
382  
383  public final static FeatureFilter and(FeatureFilter c1, FeatureFilter c2) {
384    return new FeatureFilter.And(c1, c2);
385  }
386
387  /**
388   * Constructs a new filter which matches the intersection of a set of filters.
389   */
390  
391  public final static FeatureFilter and(FeatureFilter[] filters) {
392    if(filters.length == 0) {
393      return all();
394    } else if(filters.length == 1) {
395      return filters[0];
396    } else {
397      FeatureFilter f = and(filters[0], filters[1]);
398      for(int i = 2; i < filters.length; i++) {
399        f = and(f, filters[i]);
400      }
401      return f;
402    }
403  }
404
405  /**
406   * Construct a new filter which matches the union of two filters.
407   */
408  
409  public final static FeatureFilter or(FeatureFilter c1, FeatureFilter c2) {
410    return new FeatureFilter.Or(c1, c2);
411  }
412
413  /**
414   * Construct a new filter which matches the intersection of two filters.
415   */
416  
417  public final static FeatureFilter or(FeatureFilter[] filters) {
418    if(filters.length == 0) {
419      return none();
420    } else if(filters.length == 1) {
421      return filters[0];
422    } else {
423      FeatureFilter f = or(filters[0], filters[1]);
424      for(int i = 2; i < filters.length; i++) {
425        f = or(f, filters[i]);
426      }
427      return f;
428    }
429  }
430
431  /**
432   * Match features with annotations matching the specified <code>AnnotationType</code>
433   */
434  
435  public final static FeatureFilter byAnnotationType(AnnotationType type) {
436    return new FeatureFilter.ByAnnotationType(type);
437  }
438
439  /**
440   * Match features where the annotation property named <code>key</code> is
441   * equal to <code>value</code>.
442   */
443  
444  public final static FeatureFilter byAnnotation(Object key, Object value) {
445    return new FeatureFilter.ByAnnotation(key, value);
446  }
447
448  /**
449   * Match features where the annotation property named <code>key</code> is
450   * an instance of <code>valClass</code>.
451   */
452  
453  public final static FeatureFilter byAnnotationType(Object key, Class valClass) {
454    AnnotationType type = new AnnotationType.Impl();
455    type.setConstraints(key, new PropertyConstraint.ByClass(valClass), CardinalityConstraint.ANY);
456    return byAnnotationType(type);
457  }
458
459  /**
460   * Match features where the property <code>key</code> has been defined as having
461   * some value, regardless of the exact value.
462   */
463  
464  public final static FeatureFilter hasAnnotation(Object key) {
465    return new FeatureFilter.HasAnnotation(key);
466  }
467
468  /**
469   * Match StrandedFeatures on the specified strand.
470   */
471  
472  public final static FeatureFilter byStrand(StrandedFeature.Strand strand) {
473    return new FeatureFilter.StrandFilter(strand);
474  }
475
476  /**
477   * Match features where the parent feature matches the specified filter.
478   * This cannot match top-level features.
479   */
480  
481  public final static FeatureFilter byParent(FeatureFilter parentFilter) {
482    return new FeatureFilter.ByParent(parentFilter);
483  }
484
485  /**
486   * Match features where at least one of the ancestors matches the specified
487   * filter.  This cannot match top-level features.
488   */
489  
490  public final static FeatureFilter byAncestor(FeatureFilter ancestorFilter) {
491    return new FeatureFilter.ByAncestor(ancestorFilter);
492  }
493
494  /**
495   * Match features where at least one child feature matches the supplied filter.
496   * This does not match leafFeatures.
497   */
498  
499  public final static FeatureFilter byChild(FeatureFilter childFilter) {
500    return new FeatureFilter.ByChild(childFilter);
501  }
502
503  /**
504   * Match features where at least one decendant feature -- possibly but not necessarily an
505   * immediate child -- matches the specified filter.
506   */
507  
508  public final static FeatureFilter byDescendant(FeatureFilter descFilter) {
509    return new FeatureFilter.ByDescendant(descFilter);
510  }
511
512  /**
513   * Construct a filter which matches features whose children all match the
514   * specified filter.  This filter always matches leaf features.
515   */
516  
517  public final static FeatureFilter onlyChildren(FeatureFilter child) {
518    return new FeatureFilter.OnlyChildren(child);
519  }
520
521  /**
522   * Construct a filter which matches features whose decendants all match the
523   * specified filter.  This filter always matches leaf features.
524   */
525  
526  public final static FeatureFilter onlyDescendants(FeatureFilter desc) {
527    return new FeatureFilter.OnlyDescendants(desc);
528  }
529
530  /**
531   * Construct a filter which matches FramedFeatures with the specified reading
532   * frame.
533   */
534  
535  public final static FeatureFilter byFrame(FramedFeature.ReadingFrame frame) {
536    return new FeatureFilter.FrameFilter(frame);
537  }
538
539  /**
540   * Match SeqSimilaritiy features with scores in the specified range.
541   */
542  
543  public final static FeatureFilter byPairwiseScore(double minScore, double maxScore) {
544    return new FeatureFilter.ByPairwiseScore(minScore, maxScore);
545  }
546
547  /**
548   * Construct a filter which matches all features which implement the
549   * <code>ComponentFeature</code> interface and have a <code>componentName</code>
550   * property equal to the specified value
551   */
552  
553  public final static FeatureFilter byComponentName(String compName) {
554    return new FeatureFilter.ByComponentName(compName);
555  }
556
557  /**
558   * Return a filter which matches all top-level features.  These are features
559   * which are direct children of a <code>Sequence</code> rather than another
560   * <code>Feature</code>.
561   */
562  
563  public final static FeatureFilter topLevel() {
564    return FeatureFilter.top_level;
565  }
566
567  /**
568   * Return a filter which matches features with zero children.
569   */
570  
571  public final static FeatureFilter leaf() {
572    return FeatureFilter.leaf;
573  }
574
575  /**
576   * Return a filter which matches all features.
577   */
578  
579  public final static FeatureFilter all() {
580    return FeatureFilter.all;
581  }
582
583  /**
584   * Return a filter which matches no features.
585   */
586  
587  public final static FeatureFilter none() {
588    return FeatureFilter.none;
589  }
590
591  /**
592   * Attempts to reduce a FeatureFilter to an equivalent FeatureFilter with
593   * fewer terms.
594   *
595   * <p>
596   * This will attempt to push all leaf constraints as far from the root of the
597   * filter expression as possible, in an attept to prove an empty or universal
598   * set. It will then propogate these through the logical operators in an
599   * attempt to reduce the entire expression to the empty or universal set. If
600   * filters can be combined (for example, overlapping constraints), then this
601   * will happen on the way.
602   * </p>
603   *
604   * <p>
605   * The resulting filter is guaranteed to accept exactly the same set of\
606   * features that is accepted by the argument. In particular,
607   * <code>areEqual(filter, optimize(filter))</code> is always true.
608   * </p>
609   *
610   * @param filter  the FeatureFilter to optimize
611   * @return an optimized version
612   */
613  public final static FeatureFilter optimize(FeatureFilter filter) {
614    //depth++;
615    //System.out.println(depth + ":" + "Optimizing " + filter);
616    try {
617    if(filter instanceof FeatureFilter.And) {
618      //System.out.println(depth + ":" + "is AND");
619
620      List filters = new ArrayList();
621      expandAnd(filter, filters);
622      //System.out.println(depth + ":" + "as list: " + filters);
623
624      // get all children of this AND, and of all AND children
625      for(int i = 0; i < filters.size(); i++) {
626        filters.set(i, optimize((FeatureFilter) filters.get(i)));
627      }
628
629      // now scan this list for all OR children
630      List ors = new ArrayList();
631      for(int i = 0; i < filters.size(); i++) {
632        FeatureFilter f = (FeatureFilter) filters.get(i);
633        if(f instanceof FeatureFilter.Or) {
634          filters.remove(i);
635          ors.add(f);
636          i--;
637        }
638      }
639
640      // optimize all simple filters
641      for(int i = 1; i < filters.size(); i++) {
642        //System.out.println(depth + ":" + "i: " + i);
643        FeatureFilter a = (FeatureFilter) filters.get(i);
644        for(int j = 0; j < i; j++) {
645          //System.out.println(depth + ":" + "j: " + j);
646          FeatureFilter b = (FeatureFilter) filters.get(j);
647
648          //System.out.println(depth + ":" + "Comparing " + a + ", " + b + " of " + filters);
649
650          if(areDisjoint(a, b)) {
651            // a n b = E
652            //System.out.println(depth + ":" + "Disjoint. Returning none()");
653            return none();
654          } else if(areProperSubset(a, b)) {
655            //System.out.println(depth + ":" + "a < b. Removing b");
656            // if a < b then a n b = a
657            filters.remove(j);
658            j--; i--;
659          } else if(areProperSubset(b, a)) {
660            //System.out.println(depth + ":" + "a > b. Removing a");
661            // if a > b then a n b = b
662            filters.remove(i);
663            i--;
664            break;
665          } else {
666            //System.out.println(depth + ":" + "Attempting to calculate intersection");
667            FeatureFilter intersect = intersection(a, b);
668            if(intersect != null) {
669              //System.out.println(depth + ":" + "got intersection: " + intersect);
670              filters.set(i, intersect);
671              filters.remove(j);
672              j--; i-=2;
673            } else {
674              //System.out.println(depth + ":" + "no luck - moving on");
675            }
676          }
677        }
678      }
679      //System.out.println(depth + ":" + "Reduced to: " + filters);
680
681      if(filters.isEmpty()) {
682        if(ors.isEmpty()) {
683          //System.out.println("All empty. Returning none()");
684          return none();
685        } else {
686          FeatureFilter andedOrs = FilterUtils.and((FeatureFilter[]) filters.toArray(new FeatureFilter[] {}));
687          //System.out.println("No filters, some ors, returning: " + andedOrs);
688          return andedOrs;
689        }
690      } else {
691        FeatureFilter ands = and((FeatureFilter[]) filters.toArray(new FeatureFilter[] {}));
692        if(ors.isEmpty()) {
693          //System.out.println(depth + ":" + "No ors, just returning anded values: " + ands);
694          return ands;
695        } else {
696          //System.out.println(depth + ":" + "Mixing in ors: " + ors);
697          //System.out.println(depth + ":" + "to: " + ands);
698          List combs = new ArrayList();
699          combs.add(ands);
700          for(int i = 0; i < ors.size(); i++) {
701            List newCombs = new ArrayList();
702            FeatureFilter.Or or = (FeatureFilter.Or) ors.get(i);
703            for(int j = 0; j < combs.size(); j++) {
704              FeatureFilter f = (FeatureFilter) combs.get(j);
705              newCombs.add(and(f, or.getChild1()));
706              newCombs.add(and(f, or.getChild2()));
707            }
708            combs = newCombs;
709            //System.out.println("Expanded To: " + combs);
710          }
711          FeatureFilter res = optimize(or((FeatureFilter[]) combs.toArray(new FeatureFilter[] {})));
712          //System.out.println(depth + ":" + "Returning optimized or: " + res);
713          return res;
714        }
715      }
716    } else if(filter instanceof FeatureFilter.Or) {
717      //System.out.println(depth + ":" + "is OR");
718
719      List filters = new ArrayList();
720      expandOr(filter, filters);
721
722      //System.out.println(depth + ":" + "as list: " + filters);
723
724      for(int i = 0; i < filters.size(); i++) {
725        filters.set(i, optimize((FeatureFilter) filters.get(i)));
726      }
727
728      // now scan this list for all OR children
729      List ands = new ArrayList();
730      for(int i = 0; i < filters.size(); i++) {
731        FeatureFilter f = (FeatureFilter) filters.get(i);
732        if(f instanceof FeatureFilter.And) {
733          filters.remove(i);
734          ands.add(f);
735          i--;
736        }
737      }
738      //System.out.println(depth + ":" + "filters: " + filters);
739      //System.out.println(depth + ":" + "ands: " + ands);
740
741      for(int i = 1; i < filters.size(); i++) {
742        //System.out.println(depth + ":" + "i: " + i);
743        FeatureFilter a = (FeatureFilter) filters.get(i);
744        for(int j = 0; j < i; j++) {
745          //System.out.println(depth + ":" + "j: " + j);
746          FeatureFilter b = (FeatureFilter) filters.get(j);
747
748          //System.out.println(depth + ":" + "Comparing " + a + ", " + b + " of " + filters);
749
750          if(a == all() || b == all()) {
751            //System.out.println(depth + ":" + "Found an all. Returning all()");
752            return all();
753          } else if(areProperSubset(a, b)) {
754            //System.out.println(depth + ":" + "a < b. Removing a");
755            filters.remove(i);
756            i--;
757            break;
758          } else if(areProperSubset(b, a)) {
759            //System.out.println(depth + ":" + "a > b. Removing b");
760            filters.remove(j);
761            j--; i-=2;
762          } else {
763            //System.out.println(depth + ":" + "Trying to calculate union");
764            FeatureFilter union = union(a, b);
765            if(union != null) {
766              //System.out.println(depth + ":" + "Got union: " + union);
767              filters.set(i, union);
768              filters.remove(j);
769              j--; i--;
770            } else {
771              //System.out.println(depth + ":" + "no luck - moving on");
772            }
773          }
774        }
775      }
776      //System.out.println(depth + ":" + "Reduced to: " + filters);
777
778      if(filters.isEmpty()) {
779        if(ands.isEmpty()) {
780          //System.out.println("All empty. Returning none()");
781          return none();
782        } else {
783          FeatureFilter oredAnds = or((FeatureFilter[]) ands.toArray(new FeatureFilter[] {}));
784          //System.out.println("No filters, some ands. returning: " + oredAnds);
785          return oredAnds;
786        }
787      } else {
788        FeatureFilter ors = or((FeatureFilter[]) filters.toArray(new FeatureFilter[] {}));
789        if(ands.isEmpty()) {
790          //System.out.println(depth + ":" + "no ands, returning ors: " + ors);
791          return ors;
792        } else {
793          //System.out.println(depth + ":" + "Mixing in ands: " + ands);
794          //System.out.println(depth + ":" + "to: " + ors);
795          List combs = new ArrayList();
796          combs.add(ors);
797          for(int i = 0; i < ands.size(); i++) {
798            List newCombs = new ArrayList();
799            FeatureFilter.And and = (FeatureFilter.And) ands.get(i);
800            for(int j = 0; j < combs.size(); j++) {
801              FeatureFilter f = (FeatureFilter) combs.get(j);
802              newCombs.add(or(f, and.getChild1()));
803              newCombs.add(or(f, and.getChild2()));
804            }
805            combs = newCombs;
806          }
807          FeatureFilter val = optimize(and((FeatureFilter[]) combs.toArray(new FeatureFilter[] {})));
808          //System.out.println(depth + ":" + "returning anded values: " + val);
809          return val;
810        }
811      }
812    } else if(filter instanceof FeatureFilter.Not) {
813      FeatureFilter.Not not = (FeatureFilter.Not) filter;
814      return not(optimize(not.getChild()));
815    } else {
816      return filter;
817    }
818    } finally {
819      // depth--;
820    }
821  }
822
823  private static FeatureFilter intersection(FeatureFilter f1, FeatureFilter f2) {
824    if(
825      f1 instanceof FeatureFilter.ContainedByLocation &&
826      f2 instanceof FeatureFilter.ContainedByLocation
827    ) {
828      Location loc = LocationTools.intersection(
829        ((FeatureFilter.ContainedByLocation) f1).getLocation(),
830        ((FeatureFilter.ContainedByLocation) f2).getLocation()
831      );
832      if(loc == Location.empty) {
833        return none();
834      } else {
835        return containedByLocation(loc);
836      }
837    } else if(
838      f1 instanceof FeatureFilter.OverlapsLocation &&
839      f2 instanceof FeatureFilter.OverlapsLocation
840    ) {
841      // can't do much here
842    } else if(
843      f1 instanceof FeatureFilter.ByAnnotationType &&
844      f2 instanceof FeatureFilter.ByAnnotationType
845    ) {
846      FeatureFilter.ByAnnotationType f1t = (FeatureFilter.ByAnnotationType) f1;
847      FeatureFilter.ByAnnotationType f2t = (FeatureFilter.ByAnnotationType) f2;
848
849      AnnotationType intersect = AnnotationTools.intersection(
850        f1t.getType(),
851        f2t.getType()
852      );
853
854      if(intersect == AnnotationType.NONE) {
855        return none();
856      } else {
857        return byAnnotationType(intersect);
858      }
859    } else if(
860      f1 instanceof ByHierarchy &&
861      f2 instanceof ByHierarchy
862    ) {
863      ByHierarchy f1h = (ByHierarchy) f1;
864      ByHierarchy f2h = (ByHierarchy) f2;
865
866      if(f1 instanceof Up && f2 instanceof Up) {
867        FeatureFilter filt = optimize(or(f1h.getFilter(), f2h.getFilter()));
868        if(filt == none()) {
869          return none();
870        }
871
872        if(
873          f1h instanceof FeatureFilter.ByParent ||
874          f2h instanceof FeatureFilter.ByParent
875        ) {
876          return byParent(filt);
877        } else {
878          return byAncestor(filt);
879        }
880      } else if(f1 instanceof Down && f2 instanceof Down) {
881        FeatureFilter filt = optimize(or(f1h.getFilter(), f2h.getFilter()));
882        if(filt == none()) {
883          return none();
884        }
885
886        if(
887          f1h instanceof FeatureFilter.ByChild ||
888          f2h instanceof FeatureFilter.ByChild
889        ) {
890          return byChild(filt);
891        } else {
892          return byDescendant(filt);
893        }
894      } else {
895        return none();
896      }
897    }
898
899    return null;
900  }
901
902  private static FeatureFilter union(FeatureFilter f1, FeatureFilter f2) {
903    if(
904      f1 instanceof FeatureFilter.ContainedByLocation &&
905      f2 instanceof FeatureFilter.ContainedByLocation
906    ) {
907      return containedByLocation(LocationTools.union(
908        ((FeatureFilter.ContainedByLocation) f1).getLocation(),
909        ((FeatureFilter.ContainedByLocation) f2).getLocation()
910      ));
911    } else if(
912      f1 instanceof FeatureFilter.OverlapsLocation &&
913      f2 instanceof FeatureFilter.OverlapsLocation
914    ) {
915      return overlapsLocation(LocationTools.intersection(
916        ((FeatureFilter.OverlapsLocation) f1).getLocation(),
917        ((FeatureFilter.OverlapsLocation) f2).getLocation()
918      ));
919    } else if(
920      f1 instanceof FeatureFilter.ByAnnotationType &&
921      f2 instanceof FeatureFilter.ByAnnotationType
922    ) {
923      FeatureFilter.ByAnnotationType f1t = (FeatureFilter.ByAnnotationType) f1;
924      FeatureFilter.ByAnnotationType f2t = (FeatureFilter.ByAnnotationType) f2;
925
926      AnnotationType union = AnnotationTools.union(
927        f1t.getType(),
928        f2t.getType()
929      );
930
931      return byAnnotationType(union);
932    } else if(
933      f1 instanceof ByHierarchy &&
934      f2 instanceof ByHierarchy
935    ) {
936      ByHierarchy f1h = (ByHierarchy) f1;
937      ByHierarchy f2h = (ByHierarchy) f2;
938
939      if(f1 instanceof Up && f2 instanceof Up) {
940        FeatureFilter filt = optimize(or(f1h.getFilter(), f2h.getFilter()));
941        if(filt == none()) {
942          return none();
943        }
944
945        if(
946          f1h instanceof FeatureFilter.ByAncestor ||
947          f2h instanceof FeatureFilter.ByAncestor
948        ) {
949          return byAncestor(filt);
950        } else {
951          return byParent(filt);
952        }
953      } else if(f1 instanceof Down && f2 instanceof Down) {
954        FeatureFilter filt = optimize(or(f1h.getFilter(), f2h.getFilter()));
955        if(filt == none()) {
956          return none();
957        }
958
959        if(
960          f1h instanceof FeatureFilter.ByDescendant ||
961          f2h instanceof FeatureFilter.ByDescendant
962        ) {
963          return byDescendant(filt);
964        } else {
965          return byChild(filt);
966        }
967      } else {
968        return none();
969      }
970    }
971
972    return null;
973  }
974
975  private static void expandAnd(FeatureFilter filt, List filters) {
976    if(filt instanceof FeatureFilter.And) {
977      FeatureFilter.And and = (FeatureFilter.And) filt;
978      expandAnd(and.getChild1(), filters);
979      expandAnd(and.getChild2(), filters);
980    } else {
981      filters.add(filt);
982    }
983  }
984
985  private static void expandOr(FeatureFilter filt, List filters) {
986    if(filt instanceof FeatureFilter.Or) {
987      FeatureFilter.Or or = (FeatureFilter.Or) filt;
988      expandOr(or.getChild1(), filters);
989      expandOr(or.getChild2(), filters);
990    } else {
991      filters.add(filt);
992    }
993  }
994
995  /**
996   * <p>This is a general framework method for transforming one filter into another.
997   * This method will handle the logical elements of a query (and, or, not) and delegate
998   * all the domain-specific munging to a FilterTransformer object.</p>
999   *
1000   * <p>The transformer could flip strands and locations of elements of a filter, add or
1001   * remove attributes required in annotations, or systematically alter feature types
1002   * or sources.</p>
1003   *
1004   * @param ff  the FeatureFilter to transform
1005   * @param trans  a FilterTransformer encapsulating rules about how to transform filters
1006   */
1007  public static FeatureFilter transformFilter(FeatureFilter ff, FilterTransformer trans) {
1008    if(ff == null) {
1009      throw new NullPointerException("Can't transform null filters");
1010    }
1011
1012    if(ff instanceof FeatureFilter.And) {
1013      FeatureFilter.And and = (FeatureFilter.And) ff;
1014      return and(
1015        transformFilter(and.getChild1(), trans),
1016        transformFilter(and.getChild2(), trans)
1017      );
1018    } else if(ff instanceof FeatureFilter.Or) {
1019      FeatureFilter.Or or = (FeatureFilter.Or) ff;
1020      return or(
1021        transformFilter(or.getChild1(), trans),
1022        transformFilter(or.getChild2(), trans)
1023      );
1024    } else if(ff instanceof FeatureFilter.Not) {
1025      return not(
1026        transformFilter(((FeatureFilter.Not) ff).getChild(), trans)
1027      );
1028    } else {
1029      FeatureFilter tf = trans.transform(ff);
1030      if(tf != null) {
1031        return tf;
1032      } else {
1033        return ff;
1034      }
1035    }
1036  }
1037
1038  /**
1039   * An object able to transform some FeatureFilter instances sytematically into others.
1040   *
1041   * @author Matthew Pocock
1042   */
1043  public interface FilterTransformer {
1044    /**
1045     * Transform a filter, or return null if it can not be transformed.
1046     *
1047     * @param filter  the FeatureFilter to attempt to transform
1048     * @return a transformed filter, or null
1049     */
1050    public FeatureFilter transform(FeatureFilter filter);
1051  }
1052
1053  /**
1054   * An implementation of FilterTransformer that attempts to transform by one transformer,
1055   * and if that fails, by another.
1056   *
1057   * @author Matthew Pocock
1058   */
1059  public class DelegatingTransformer
1060  implements FilterTransformer {
1061    FilterTransformer t1;
1062    FilterTransformer t2;
1063
1064    /**
1065     * Create a new DelegatingTransformer that will apply t1 and then t2 if t1 fails.
1066     *
1067     * @param t1 the first FilterTransformer to try
1068     * @param t2 the seccond FilterTransformer to try
1069     */
1070    public DelegatingTransformer(FilterTransformer t1, FilterTransformer t2) {
1071      this.t1 = t1;
1072      this.t2 = t2;
1073    }
1074
1075    public FeatureFilter transform(FeatureFilter ff) {
1076      FeatureFilter res = t1.transform(ff);
1077      if(res == null) {
1078        res = t2.transform(ff);
1079      }
1080      return res;
1081    }
1082  }
1083
1084    static FeatureFilter getOnlyDescendantsFilter(FeatureFilter ff) {
1085        if (ff instanceof FeatureFilter.OnlyDescendants) {
1086            return ((FeatureFilter.OnlyDescendants) ff).getFilter();
1087        } else if (ff instanceof FeatureFilter.And) {
1088            FeatureFilter.And ffa = (FeatureFilter.And) ff;
1089            FeatureFilter ocf1 = getOnlyDescendantsFilter(ffa.getChild1());
1090            FeatureFilter ocf2 = getOnlyDescendantsFilter(ffa.getChild2());
1091            if (ocf1 == null) {
1092                return ocf2;
1093            } else if (ocf2 == null) {
1094                return ocf1;
1095            } else {
1096                return new FeatureFilter.And(ocf1, ocf2);
1097            }
1098        } else if (ff instanceof FeatureFilter.Or) {
1099            FeatureFilter.Or ffa = (FeatureFilter.Or) ff;
1100            FeatureFilter ocf1 = getOnlyDescendantsFilter(ffa.getChild1());
1101            FeatureFilter ocf2 = getOnlyDescendantsFilter(ffa.getChild2());
1102            if (ocf1 == null) {
1103                return ocf2;
1104            } else if (ocf2 == null) {
1105                return ocf1;
1106            } else {
1107                return new FeatureFilter.Or(ocf1, ocf2);
1108            }
1109        } else {
1110            return null;
1111        }
1112    }
1113
1114    static FeatureFilter getOnlyChildrenFilter(FeatureFilter ff) {
1115        // System.err.println("In getOnlyChildrenFilter: " + ff.toString());
1116
1117        if (ff instanceof FeatureFilter.OnlyChildren) {
1118            return ((FeatureFilter.OnlyChildren) ff).getFilter();
1119        } else if (ff instanceof FeatureFilter.OnlyDescendants) {
1120            return ((FeatureFilter.OnlyDescendants) ff).getFilter();
1121        } else if (ff instanceof FeatureFilter.And) {
1122            FeatureFilter.And ffa = (FeatureFilter.And) ff;
1123            FeatureFilter ocf1 = getOnlyChildrenFilter(ffa.getChild1());
1124            FeatureFilter ocf2 = getOnlyChildrenFilter(ffa.getChild2());
1125            if (ocf1 == null) {
1126                return ocf2;
1127            } else if (ocf2 == null) {
1128                return ocf1;
1129            } else {
1130                return new FeatureFilter.And(ocf1, ocf2);
1131            }
1132        } else if (ff instanceof FeatureFilter.Or) {
1133            FeatureFilter.Or ffa = (FeatureFilter.Or) ff;
1134            FeatureFilter ocf1 = getOnlyChildrenFilter(ffa.getChild1());
1135            FeatureFilter ocf2 = getOnlyChildrenFilter(ffa.getChild2());
1136            if (ocf1 == null) {
1137                return ocf2;
1138            } else if (ocf2 == null) {
1139                return ocf1;
1140            } else {
1141                return new FeatureFilter.Or(ocf1, ocf2);
1142            }
1143        } else {
1144            return null;
1145        }
1146    }
1147
1148  /**
1149   * Applies a visitor to a filter, and returns the visitor's result or null.
1150   *
1151   * @param filter  the filter to scan
1152   * @param visitor the visitor to scan with
1153   * @return  the result of the visitor or null
1154   * @throws BioException   if the required walker could not be created
1155   */
1156  public static Object visitFilter(FeatureFilter filter, Visitor visitor)
1157  throws BioException {
1158    Walker walker = WalkerFactory.getInstance().getWalker(visitor);
1159    walker.walk(filter, visitor);
1160    return walker.getValue();
1161  }
1162}