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;
023
024import java.util.Collection;
025import java.util.HashSet;
026import java.util.Iterator;
027import java.util.Set;
028
029import org.biojava.bio.symbol.Location;
030import org.biojava.bio.symbol.LocationTools;
031import org.biojava.utils.ChangeVetoException;
032
033/**
034 * <p><code>AnnotationTools</code> is a set of static utility methods for
035 * manipulating <code>Annotation</code>s and <code>AnnotationType</code>s.</p>
036 *
037 * <p>The methods allIn() and allOut() let you compare an Annotation to an
038 * AnnotationType and produce a new Annotation with only those properties
039 * explicitly constrained by or not constrained by the type. This could be
040 * of use when using an Annotation as a template for some object. You could use
041 * allOut to make an Annotation that has all the properties that do not fit into
042 * normal constructor properties, and pass that in as the Annotation bundle.</p>
043 *
044 * <p>intersection(AnnotationType) and union(AnnotationType) return new
045 * AnnotationType instances that will accept every Annotation instance that is
046 * accepted by both or either respectively. It is particularly informative to
047 * compare the result of this to the AnnotationType.NONE to see if the two types
048 * are mutualy disjoint.</p>
049 *
050 * <p>intersection(PropertyConstraint) and union(PropertyConstraint) return new
051 * PropertyConstraint instances that will accept every Object that is accepted
052 * by both or either one respectively.</p>
053 * 
054 * FilterTools uses these methods
055 * when comparing filters on features by their Annotation bundles.
056 * 
057 * @since 1.3
058 * @author Matthew Pocock
059 * @author <a href="mailto:kdj@sanger.ac.uk">Keith James</a> (docs)
060 * @author Thomas Down
061 *
062 */
063public final class AnnotationTools {
064    /**
065     * <p>
066     * Destructive down-cast an annotation to a type.
067     * </p>
068     *
069     * <p>
070     * <code>allIn</code> returns a new <code>Annotation</code>
071     * containing only those values in the <code>Annotation</code>
072     * argument which are of a type specified by the
073     * <code>AnnotationType</code>.
074     * </p>
075     *
076     * @param annotation an <code>Annotation</code> to scan.
077     * @param annType an <code>AnnotationType</code>.
078     *
079     * @return an <code>Annotation</code>.
080     */
081    public static Annotation allIn(Annotation annotation, AnnotationType annType) {
082        Annotation res;
083        if (annotation instanceof SmallAnnotation) {
084            res = new SmallAnnotation();
085        } else {
086            res = new SimpleAnnotation();
087        }
088
089        for (Iterator i = annType.getProperties().iterator(); i.hasNext();) {
090            Object tag = i.next();
091            try {
092                res.setProperty(tag, annotation.getProperty(tag));
093            } catch (ChangeVetoException cve) {
094                throw new BioError("Assertion Failure: Can't alter an annotation", cve);
095            }
096        }
097
098        return res;
099    }
100
101    /**
102     * <code>allOut</code> returns a new <code>Annotation</code>
103     * containing only those values in the <code>Annotation</code>
104     * argument which are <strong>not</strong> of a type specified by
105     * the <code>AnnotationType</code>.
106     *
107     * @param annotation an <code>Annotation</code>.
108     * @param annType an <code>AnnotationType</code>.
109     *
110     * @return an <code>Annotation</code> value.
111     */
112    public static Annotation allOut(Annotation annotation, AnnotationType annType) {
113        Annotation res;
114        if (annotation instanceof SmallAnnotation) {
115            res = new SmallAnnotation();
116        } else {
117            res = new SimpleAnnotation();
118        }
119
120        Set props = annType.getProperties();
121        for (Iterator i = annotation.keys().iterator(); i.hasNext();) {
122            Object tag = i.next();
123            if (! props.contains(tag)) {
124                try {
125                    res.setProperty(tag, annotation.getProperty(tag));
126                } catch (ChangeVetoException cve) {
127                    throw new BioError("Assertion Failure: Can't alter an annotation", cve);
128                }
129            }
130        }
131
132        return res;
133    }
134
135    /**
136     * <p>
137     * Scans an Annotation with an AnnotationType and returns all Annotation
138     * instances matching a Type.
139     * </p>
140     *
141     * <p>This differs from AnnotationType.instanceOf()
142     * as it will descend into properties of an Annotation if that property is
143     * itself an Annotation. This allows you to scan a tree of Annotations for
144     * nodes in the tree of a particular shape.
145     * </p>
146     *
147     * @param ann  the Annotation to scan
148     * @param query  the AnnotationType to match against all nodes in the tree
149     * @return the set of all annotations matching the query
150     */
151    public static Set searchAnnotation(Annotation ann, AnnotationType query) {
152      Set hits = new HashSet();
153      searchAnnotation(ann, query, hits);
154      return hits;
155    }
156
157    private static void searchAnnotation(Annotation ann, AnnotationType query, Set hits) {
158      if(query.instanceOf(ann)) {
159        hits.add(ann);
160      }
161
162      for(Iterator i = ann.keys().iterator(); i.hasNext(); ) {
163        Object prop = i.next();
164        Object val = ann.getProperty(prop);
165        if(val instanceof Annotation) {
166          searchAnnotation((Annotation) val, query, hits);
167        } else if(prop instanceof Collection) {
168          for(Iterator vi = ((Collection) val).iterator(); vi.hasNext(); ) {
169            Object v = vi.next();
170            if(v instanceof Annotation) {
171              searchAnnotation((Annotation) v, query, hits);
172            }
173          }
174        }
175      }
176    }
177
178    /**
179     * Calculate an AnnotationType that matches all Annotation instances matched
180     * by both types. Usually you will either use this value blind or compare it to
181     * AnnotationType.NONE.
182     *
183     * @param ann1  the first AnnotationType
184     * @param ann2  the seccond AnnotationType
185     * @return the intersection AnnotationType
186     */
187    public static AnnotationType intersection(
188      AnnotationType ann1,
189      AnnotationType ann2
190    ) {
191      if(ann1.subTypeOf(ann2)) {
192        return ann2;
193      } else if(ann2.subTypeOf(ann1)) {
194        return ann1;
195      } else {
196        Set props = new HashSet();
197        props.addAll(ann1.getProperties());
198        props.addAll(ann2.getProperties());
199
200        AnnotationType.Impl intersect = new AnnotationType.Impl();
201        for(Iterator i = props.iterator(); i.hasNext(); ) {
202          Object key = i.next();
203
204          CollectionConstraint pc1 = ann1.getConstraint(key);
205          CollectionConstraint pc2 = ann2.getConstraint(key);
206          CollectionConstraint pc = intersection(pc1, pc2);
207          if (pc == CollectionConstraint.NONE) {
208            return AnnotationType.NONE;
209          }
210
211          intersect.setConstraint(key, pc);
212        }
213
214        intersect.setDefaultConstraint(
215          intersection(ann1.getDefaultConstraint(), ann2.getDefaultConstraint())
216        );
217
218        return intersect;
219      }
220    }
221
222    /**
223     * Calculate the intersection of two PropertyConstraint instances. This method is realy only interesting when comparing each property in an
224     * AnnotationType in turn. Usually the return value is either compared to
225     * PropertyConstraint.NONE or is used blindly.
226     *
227     * @param pc1 the first PropertyConstraint
228     * @param pc2 the seccond PropertyConstraint
229     * @return the intersection PropertyConstraint
230     *
231     */
232    public static PropertyConstraint intersection(
233      PropertyConstraint pc1,
234      PropertyConstraint pc2
235    ) {
236      if(pc1.subConstraintOf(pc2)) {
237        return pc2;
238      } else if(pc2.subConstraintOf(pc1)) {
239        return pc1;
240      } else if(
241        pc1 instanceof PropertyConstraint.ByClass &&
242        pc2 instanceof PropertyConstraint.ByClass
243      ) {
244        PropertyConstraint.ByClass pc1c = (PropertyConstraint.ByClass) pc1;
245        PropertyConstraint.ByClass pc2c = (PropertyConstraint.ByClass) pc2;
246        Class c1 = pc1c.getPropertyClass();
247        Class c2 = pc2c.getPropertyClass();
248
249        if(!c1.isInterface() && !c2.isInterface()) {
250          return new PropertyConstraint.And(pc1c, pc2c);
251        } else {
252          return PropertyConstraint.NONE;
253        }
254      } else if(pc2 instanceof PropertyConstraint.ByClass) {
255        return intersection(pc2, pc1);
256      } else if(pc1 instanceof PropertyConstraint.ByClass) {
257        PropertyConstraint.ByClass pc1c = (PropertyConstraint.ByClass) pc1;
258
259        if(pc2 instanceof PropertyConstraint.Enumeration) {
260          PropertyConstraint.Enumeration pc2e = (PropertyConstraint.Enumeration) pc2;
261          Set values = new HashSet();
262          for(Iterator i = pc2e.getValues().iterator(); i.hasNext(); ) {
263            Object val = i.next();
264            if(pc1c.accept(val)) {
265              values.add(val);
266            }
267          }
268          if(values.isEmpty()) {
269            return PropertyConstraint.NONE;
270          } else if(values.size() == 1) {
271            return new PropertyConstraint.ExactValue(values.iterator().next());
272          } else {
273            return new PropertyConstraint.Enumeration(values);
274          }
275        }
276
277        if(pc2 instanceof PropertyConstraint.ExactValue) {
278          // we've already checked for containment - we know this value is of
279          // the wrong class
280          return PropertyConstraint.NONE;
281        }
282      } else if(
283        (pc1 instanceof PropertyConstraint.Enumeration ||
284         pc1 instanceof PropertyConstraint.ExactValue) &&
285        (pc2 instanceof PropertyConstraint.Enumeration ||
286         pc2 instanceof PropertyConstraint.ExactValue)
287      ) {
288        if (pc1 instanceof PropertyConstraint.Enumeration && pc2 instanceof PropertyConstraint.Enumeration) {
289            Set intersection = new HashSet(((PropertyConstraint.Enumeration) pc1).getValues());
290            intersection.retainAll(((PropertyConstraint.Enumeration) pc2).getValues());
291            if (intersection.size() == 0) {
292                return PropertyConstraint.NONE;
293            } else if (intersection.size() == 1) {
294                return new PropertyConstraint.ExactValue(intersection.iterator().next());
295            } else {
296                return new PropertyConstraint.Enumeration(intersection);
297            }
298        } else {
299            // This case already handled by subset/superset logic
300            return PropertyConstraint.NONE;
301        }
302      } else if(
303        (pc1 instanceof PropertyConstraint.ByAnnotationType &&
304         !(pc2 instanceof PropertyConstraint.ByAnnotationType)) ||
305        (pc2 instanceof PropertyConstraint.ByAnnotationType &&
306         !(pc1 instanceof PropertyConstraint.ByAnnotationType))
307      ) {
308        return PropertyConstraint.NONE;
309      } else if(
310        pc1 instanceof PropertyConstraint.ByAnnotationType &&
311        pc2 instanceof PropertyConstraint.ByAnnotationType
312      ) {
313        PropertyConstraint.ByAnnotationType pc1a = (PropertyConstraint.ByAnnotationType) pc1;
314        PropertyConstraint.ByAnnotationType pc2a = (PropertyConstraint.ByAnnotationType) pc2;
315
316        AnnotationType intersect = intersection(
317          pc1a.getAnnotationType(),
318          pc2a.getAnnotationType()
319        );
320        if(intersect == AnnotationType.NONE) {
321          return PropertyConstraint.NONE;
322        } else {
323          return new PropertyConstraint.ByAnnotationType(intersect);
324        }
325      }
326
327      return new PropertyConstraint.And(pc1, pc2);
328    }
329
330    /**
331     * Create an AnnotationType that matches all Anntotations that are accepted
332     * by two others. This method is realy not very usefull in most cases. You may wish to
333     * compare the result of this to AnnotationType.ANY, or use it blindly.
334     *
335     * @param ann1  the first AnnotationType
336     * @param ann2  the seccond AnnotationType
337     * @return an AnnotationType that represents their unions
338     *
339     */
340    public static AnnotationType union(
341      AnnotationType ann1,
342      AnnotationType ann2
343    ) {
344      if(ann1.subTypeOf(ann2)) {
345        return ann1;
346      } else if(ann2.subTypeOf(ann1)) {
347        return ann2;
348      } else {
349        Set props = new HashSet();
350        props.addAll(ann1.getProperties());
351        props.addAll(ann2.getProperties());
352
353        AnnotationType.Impl union = new AnnotationType.Impl();
354        for(Iterator i = props.iterator(); i.hasNext(); ) {
355          Object key = i.next();
356
357          CollectionConstraint pc1 = ann1.getConstraint(key);
358          CollectionConstraint pc2 = ann2.getConstraint(key);
359          CollectionConstraint pc = union(pc1, pc2);
360
361          union.setConstraint(key, pc);
362        }
363
364        return union;
365      }
366    }
367
368    /**
369     * Create a PropertyConstraint that matches all Objects that are accepted
370     * by two others. In the general case, there is no clean way to represent the union of two
371     * PropertyConstraint instances. You may get back a PropertyConstraint.Or
372     * instance, or perhaps PropertyConstraint.ANY. Alternatively, there may be
373     * some comparrison possible. It is a thankless task introspecting this in
374     * code. You have been warned.
375     *
376     * @param pc1 the first PropertyConstraint
377     * @param pc2 the second PropertyConstraint
378     * @return the union PropertyConstraint
379     */
380    public static PropertyConstraint union(
381      PropertyConstraint pc1,
382      PropertyConstraint pc2
383    ) {
384      if(pc1.subConstraintOf(pc2)) {
385        return pc1;
386      } else if(pc2.subConstraintOf(pc1)) {
387        return pc2;
388      } else if(
389        pc1 instanceof PropertyConstraint.ByClass &&
390        pc2 instanceof PropertyConstraint.ByClass
391      ) {
392        return new PropertyConstraint.Or(pc1, pc2);
393      } else if(pc2 instanceof PropertyConstraint.ByClass) {
394        return intersection(pc2, pc1);
395      } else if(pc1 instanceof PropertyConstraint.ByClass) {
396        PropertyConstraint.ByClass pc1c = (PropertyConstraint.ByClass) pc1;
397
398        if(pc2 instanceof PropertyConstraint.Enumeration) {
399          PropertyConstraint.Enumeration pc2e = (PropertyConstraint.Enumeration) pc2;
400          Set values = new HashSet();
401          for(Iterator i = pc2e.getValues().iterator(); i.hasNext(); ) {
402            Object val = i.next();
403            if(!pc1c.accept(val)) {
404              values.add(val);
405            }
406          }
407          if(values.isEmpty()) {
408            return pc1;
409          } else if(values.size() == 1) {
410            return new PropertyConstraint.Or(
411              pc1,
412              new PropertyConstraint.ExactValue(values.iterator().next())
413            );
414          } else {
415            return new PropertyConstraint.Or(
416              pc1,
417              new PropertyConstraint.Enumeration(values)
418            );
419          }
420        }
421
422        if(pc2 instanceof PropertyConstraint.ExactValue) {
423          // we've already checked for containment - we know this value is of
424          // the wrong class
425          return new PropertyConstraint.Or(pc1, pc2);
426        }
427      } else if(
428        pc1 instanceof PropertyConstraint.ByAnnotationType &&
429        pc2 instanceof PropertyConstraint.ByAnnotationType
430      ) {
431        PropertyConstraint.ByAnnotationType pc1a = (PropertyConstraint.ByAnnotationType) pc1;
432        PropertyConstraint.ByAnnotationType pc2a = (PropertyConstraint.ByAnnotationType) pc2;
433
434        return new PropertyConstraint.ByAnnotationType(union(
435          pc1a.getAnnotationType(),
436          pc2a.getAnnotationType()
437        ));
438      }
439
440      return new PropertyConstraint.Or(pc1, pc2);
441    }
442
443    /**
444     * Return the CollectionConstraint which accept only collections accepted by
445     * both of those specified.
446     *
447     * @param cc1 the first CollectionConstraint
448     * @param cc2 the seccond CollectionConstrant
449     * @return a CollectionConstraint representing the intersection of the other
450     *    two
451     */
452
453    public static CollectionConstraint intersection(CollectionConstraint cc1, CollectionConstraint cc2) {
454        if (cc1.subConstraintOf(cc2)) {
455            return cc2;
456        } else if (cc2.subConstraintOf(cc1)) {
457            return cc1;
458        } else if (cc1 instanceof CollectionConstraint.AllValuesIn &&
459                   cc2 instanceof CollectionConstraint.AllValuesIn)
460        {
461            PropertyConstraint pc1 = ((CollectionConstraint.AllValuesIn) cc1).getPropertyConstraint();
462            PropertyConstraint pc2 = ((CollectionConstraint.AllValuesIn) cc2).getPropertyConstraint();
463            Location card1 = ((CollectionConstraint.AllValuesIn) cc1).getCardinalityConstraint();
464            Location card2 = ((CollectionConstraint.AllValuesIn) cc2).getCardinalityConstraint();
465            Location card = LocationTools.intersection(card1, card2);
466            if (card == Location.empty) {
467                return CollectionConstraint.NONE;
468            }
469            PropertyConstraint pc = intersection(pc1, pc2);
470            if (pc == PropertyConstraint.NONE && !card.contains(0)) {
471                return CollectionConstraint.NONE;
472            } else {
473                return new CollectionConstraint.AllValuesIn(pc, card);
474            }
475        } else if (cc1 instanceof CollectionConstraint.Contains &&
476                   cc2 instanceof CollectionConstraint.Contains)
477        {
478            PropertyConstraint pc1 = ((CollectionConstraint.Contains) cc1).getPropertyConstraint();
479            PropertyConstraint pc2 = ((CollectionConstraint.Contains) cc2).getPropertyConstraint();
480            Location card1 = ((CollectionConstraint.Contains) cc1).getCardinalityConstraint();
481            Location card2 = ((CollectionConstraint.Contains) cc2).getCardinalityConstraint();
482            Location card = LocationTools.intersection(card1, card2);
483            if (card == Location.empty) {
484                return CollectionConstraint.NONE;
485            }
486            PropertyConstraint pc = intersection(pc1, pc2);
487            if (pc == PropertyConstraint.NONE && !card.contains(0)) {
488                return CollectionConstraint.NONE;
489            } else {
490                return new CollectionConstraint.Contains(pc, card);
491            }
492        } else if (cc1 instanceof CollectionConstraint.Contains &&
493                   cc2 instanceof CollectionConstraint.AllValuesIn)
494        {
495            PropertyConstraint pc1 = ((CollectionConstraint.Contains) cc1).getPropertyConstraint();
496            PropertyConstraint pc2 = ((CollectionConstraint.AllValuesIn) cc2).getPropertyConstraint();
497            Location card1 = ((CollectionConstraint.Contains) cc1).getCardinalityConstraint();
498            Location card2 = ((CollectionConstraint.AllValuesIn) cc2).getCardinalityConstraint();
499            if (card1.getMin() > card2.getMax()) {
500                // Requires too many values.
501                return CollectionConstraint.NONE;
502            }
503            PropertyConstraint pc = intersection(pc1, pc2);
504            if (pc == PropertyConstraint.NONE && !card1.contains(0)) {
505                return CollectionConstraint.NONE;
506            } else {
507                return new CollectionConstraint.Contains(pc, card1);
508            }
509        } else if (cc1 instanceof CollectionConstraint.AllValuesIn &&
510                   cc2 instanceof CollectionConstraint.Contains)
511        {
512            return intersection(cc2, cc1);
513        } else {
514            return new CollectionConstraint.And(cc1, cc2);
515        }
516    }
517
518  /**
519   * Calculate a CollectionConstaint that will accept all items accepted by
520   * either constraint.
521   *
522   * @param cc1   the first CollectionConstraint
523   * @param cc2   the seccond collectionConstraint
524   * @return      a CollectionConstraint representing the union of the other two
525   */
526    public static CollectionConstraint union(CollectionConstraint cc1, CollectionConstraint cc2) {
527        if (cc1.subConstraintOf(cc2)) {
528            return cc1;
529        } else if (cc2.subConstraintOf(cc1)) {
530            return cc2;
531        } else {
532            return new CollectionConstraint.Or(cc1, cc2);
533        }
534    }
535}