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}