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 */
021package org.biojavax.bio.seq;
022
023import java.util.ArrayList;
024import java.util.Collection;
025import java.util.Collections;
026import java.util.HashMap;
027import java.util.Iterator;
028import java.util.List;
029import java.util.Map;
030import java.util.Set;
031import java.util.TreeSet;
032
033import org.biojava.bio.Annotation;
034import org.biojava.bio.symbol.IllegalSymbolException;
035import org.biojava.bio.symbol.Location;
036import org.biojava.bio.symbol.SimpleSymbolList;
037import org.biojava.bio.symbol.SymbolList;
038import org.biojava.utils.ChangeVetoException;
039import org.biojavax.CrossReferenceResolver;
040import org.biojavax.RichAnnotation;
041import org.biojavax.RichObjectFactory;
042import org.biojavax.ontology.ComparableTerm;
043
044/**
045 * An implementation of RichLocation which covers multiple locations, 
046 * but on the same strand of the same (optionally circular) sequence.
047 * @author Richard Holland
048 * @author Mark Schreiber
049 * @since 1.5
050 */
051public class CompoundRichLocation extends SimpleRichLocation implements RichLocation {
052
053    protected List members;
054    protected int size = 0;
055
056    /**
057     * Getter for the "join" term
058     * @return the "join" term
059     */
060    public static ComparableTerm getJoinTerm() {
061        return RichObjectFactory.getDefaultOntology().getOrCreateTerm("join");
062    }
063
064    /**
065     * Getter for the "order" term
066     * @return the "order" term
067     */
068    public static ComparableTerm getOrderTerm() {
069        return RichObjectFactory.getDefaultOntology().getOrCreateTerm("order");
070    }
071
072    /**
073     * Constructs a CompoundRichLocation from the given set of members, with
074     * the default term of "join". Note that you really shouldn't use this if
075     * you are unsure if your members set contains overlapping members. Use
076     * RichLocation.Tools.construct() instead. The members collection
077     * must only contain Location instances. Any that are not RichLocations will
078     * be converted using RichLocation.Tools.enrich(). All members must come from
079     * the same strand of the same sequence with the same circular length.
080     * @param members the members to put into the compound location.
081     * @see RichLocation.Tools
082     */
083    public CompoundRichLocation(Collection members) {
084        this(getJoinTerm(), members);
085    }
086
087    /**
088     * Constructs a CompoundRichLocation from the given set of members.
089     * Note that you really shouldn't use this if
090     * you are unsure if your members set contains overlapping members. Use
091     * RichLocation.Tools.construct(members) instead. The members collection
092     * must only contain Location instances. Any that are not RichLocations will
093     * be converted using RichLocation.Tools.enrich().
094     * @param term the term to use when describing the group of members.
095     * @param members the members to put into the compound location.
096     * @see RichLocation.Tools
097     */
098    public CompoundRichLocation(ComparableTerm term, Collection members) {
099        if (term == null) {
100            throw new IllegalArgumentException("Term cannot be null");
101        }
102        if (members == null || members.size() < 2) {
103            throw new IllegalArgumentException("Must have at least two members");
104        }
105        if (RichLocation.Tools.isMultiSource(members)) {
106            throw new IllegalArgumentException("All members must be from the same source");
107        }
108        this.term = term;
109        this.members = new ArrayList();
110        for (Iterator i = members.iterator(); i.hasNext();) {
111            // Convert each member into a RichLocation
112            Object o = i.next();
113            if (!(o instanceof RichLocation)) {
114                o = RichLocation.Tools.enrich((Location) o);
115            }
116            // Convert
117            RichLocation rl = (RichLocation) o;
118            // Add in member
119            this.members.add(rl);
120            // Update our cross ref
121            this.setCrossRef(rl.getCrossRef());
122            // Update our circular length
123            this.circularLength = rl.getCircularLength();
124            // Update our strand
125            this.setStrand(rl.getStrand());
126            // Update our size and min/max
127            this.size += rl.getMax() - rl.getMin();
128            if (this.getMinPosition() == null) {
129                this.setMinPosition(rl.getMinPosition());
130            } else {
131                this.setMinPosition(this.posmin(this.getMinPosition(), rl.getMinPosition()));
132            }
133            if (this.getMaxPosition() == null) {
134                this.setMaxPosition(rl.getMaxPosition());
135            } else {
136                this.setMaxPosition(this.posmax(this.getMaxPosition(), rl.getMaxPosition()));
137            }
138        }
139    }
140
141    // for internal use only
142    protected CompoundRichLocation() {
143    }
144
145    /**
146     * {@inheritDoc} 
147     */
148    public void sort() {
149        Collections.sort(this.members);
150    }
151
152    /**
153     * {@inheritDoc} 
154     * Passes the call on to each of its members in turn.
155     */
156    public void setFeature(RichFeature feature) throws ChangeVetoException {
157        super.setFeature(feature);
158        for (Iterator i = this.members.iterator(); i.hasNext();) {
159            ((RichLocation) i.next()).setFeature(feature);
160        }
161    }
162
163    /**
164     * {@inheritDoc}
165     * ALWAYS RETURNS THE EMPTY ANNOTATION
166     */
167    public Annotation getAnnotation() {
168        return getRichAnnotation();
169    }
170
171    /**
172     * {@inheritDoc}
173     * ALWAYS RETURNS THE EMPTY ANNOTATION
174     */
175    public RichAnnotation getRichAnnotation() {
176        return RichAnnotation.EMPTY_ANNOTATION;
177    }
178    
179    /**
180     * {@inheritDoc}
181     * ALWAYS RETURNS THE EMPTY ANNOTATION NOTE SET
182     */
183    public Set getNoteSet() {
184        return RichAnnotation.EMPTY_ANNOTATION.getNoteSet();
185    }
186
187    /**
188     * {@inheritDoc}
189     * NOT IMPLEMENTED
190     * @throws ChangeVetoException ALWAYS
191     */
192    public void setNoteSet(Set notes) throws ChangeVetoException {
193        throw new ChangeVetoException("Cannot annotate compound locations.");
194    }
195
196    /**
197     * {@inheritDoc}
198     * RECURSIVELY APPLIES CALL TO ALL MEMBERS
199     */
200    public void setCircularLength(int sourceSeqLength) throws ChangeVetoException {
201        super.setCircularLength(sourceSeqLength);
202        for (Iterator i = this.members.iterator(); i.hasNext();) {
203            ((RichLocation) i.next()).setCircularLength(sourceSeqLength);
204        }
205    }
206
207    /**
208     * {@inheritDoc}
209     */
210    public Iterator blockIterator() {
211        final List sortedMembers = new ArrayList(this.members);
212        Collections.sort(sortedMembers);
213        return sortedMembers.iterator();
214    }
215
216    /**
217     * {@inheritDoc}
218     * ALWAYS RETURNS FALSE
219     */
220    public boolean isContiguous() {
221        return false;
222    }
223
224    /**
225     * {@inheritDoc}
226     * Recursively applies this call to all members.
227     */
228    public boolean contains(int p) {
229        for (Iterator i = this.members.iterator(); i.hasNext();) {
230            if (((RichLocation) i.next()).contains(p)) {
231                return true;
232            }
233        }
234        return false;
235    }
236
237    /**
238     * {@inheritDoc}
239     * ALWAYS RETURNS NULL
240     */
241    public Location getDecorator(Class decoratorClass) {
242        return null;
243    }
244
245    /**
246     * {@inheritDoc}
247     * ALWAYS RETURNS SELF
248     */
249    public Location newInstance(Location loc) {
250        return loc;
251    }
252
253    /**
254     * {@inheritDoc}
255     * Recursively translates all members of this location.
256     */
257    public Location translate(int dist) {
258        if (this.members.isEmpty()) {
259            return this;
260        }
261        List newmembers = new ArrayList();
262        for (Iterator i = this.members.iterator(); i.hasNext();) {
263            RichLocation rl = (RichLocation) i.next();
264            newmembers.add(rl.translate(dist));
265        }
266        return new CompoundRichLocation(this.getTerm(), newmembers);
267    }
268
269    /**
270     * {@inheritDoc}
271     * Recursively applies this call to all members. If passed a Location 
272     * which is not a RichLocation, it converts it first using 
273     * RichLocation.Tools.enrich().
274     * @see RichLocation.Tools
275     * @return true if an only if one of the members of this <code>Location</code>
276     * wholey contains <code>l</code>.
277     */
278    public boolean contains(Location l) {
279        if (!(l instanceof RichLocation)) {
280            l = RichLocation.Tools.enrich(l);
281        }
282        if (l instanceof EmptyRichLocation) {
283            return l.contains(this); // let them do the hard work!
284        } else {
285            RichLocation rl = (RichLocation) l;
286            if (rl instanceof CompoundRichLocation) {
287                CompoundRichLocation crl = (CompoundRichLocation) rl;
288                Map matches = new HashMap();
289                for (Iterator i = crl.members.iterator(); i.hasNext();) {
290                    matches.put(i.next(), Boolean.FALSE);
291                }
292                for (Iterator i = this.members.iterator(); i.hasNext();) {
293                    RichLocation member = (RichLocation) i.next();
294                    for (Iterator j = matches.entrySet().iterator(); j.hasNext();) {
295                        Map.Entry entry = (Map.Entry)j.next();
296                        if (entry.getValue().equals(Boolean.TRUE)) {
297                            continue;
298                        }
299                        RichLocation match = (RichLocation) entry.getKey();
300                        if (member.contains(match)) {
301                            entry.setValue(Boolean.TRUE);
302                        }
303                    }
304                }
305                for (Iterator i = matches.values().iterator(); i.hasNext(); ) {
306                    if (i.next().equals(Boolean.FALSE)) {
307                        return false;
308                    }
309                }
310                return true;
311            } else {
312                for (Iterator i = this.members.iterator(); i.hasNext();) {
313                    if (((RichLocation) i.next()).contains(rl)) {
314                        return true;
315                    }
316                }
317            }
318            return false;
319        }
320    }
321
322    /**
323     * {@inheritDoc}
324     * Recursively applies this call to all members.
325     * @return true if and only if at least on of the members overlaps <code>l</code>
326     */
327    public boolean overlaps(Location l) {
328        for (Iterator i = this.members.iterator(); i.hasNext();) {
329            RichLocation rl = (RichLocation) i.next();
330            if (rl.overlaps(l)) {
331                return true;
332            }
333        }
334        return false;
335    }
336
337    /**
338     * {@inheritDoc} 
339     * If passed a Location which is not a RichLocation, it converts it first 
340     * using RichLocation.Tools.enrich().
341     * The resulting location may or may not be a compound location. If it is
342     * a compound location, its contents will be a set of simple locations.
343     * Regions that overlap will be merged into a single location.
344     * @see RichLocation.Tools
345     * @return a <code>CompoundLocation</code> if the components of the union
346     * cannot be merged else a <code>SimpleRichLocation</code>
347     */
348    public Location union(Location l) {
349        if (!(l instanceof RichLocation)) {
350            l = RichLocation.Tools.enrich(l);
351        }
352        if (l instanceof EmptyRichLocation) {
353            return this;
354        } else {
355            // Easy - construct a new location based on the members of both
356            // ourselves and the location passed as a parameter
357            List members = new ArrayList();
358            members.addAll(RichLocation.Tools.flatten(this));
359            members.addAll(RichLocation.Tools.flatten((RichLocation) l));
360            return RichLocation.Tools.construct(RichLocation.Tools.merge(members));
361        }
362    }
363
364    /**
365     * {@inheritDoc}
366     * If passed a Location which is not a RichLocation, it converts it first 
367     * using RichLocation.Tools.enrich().
368     * The resulting location may or may not be a compound location. If it is
369     * a compound location, its contents will be a set of simple locations.
370     * @return a <code>CompoundLocation</code> if there is more than one region
371     * of intersection that cannot be merged. Else a <code>SimpleRichLocation</code>.
372     */
373    public Location intersection(Location l) {
374        if (!(l instanceof RichLocation)) {
375            l = RichLocation.Tools.enrich(l);
376        }
377        if (l instanceof EmptyRichLocation) {
378            return l;
379        } else if (l instanceof CompoundRichLocation) {
380            Collection theirMembers = RichLocation.Tools.flatten((RichLocation) l);
381            // For every member of the location passed as a parameter, intersect 
382            // with ourselves. Then construct a new location from the
383            // results of all the intersections.
384            Set results = new TreeSet();
385            for (Iterator i = theirMembers.iterator(); i.hasNext();) {
386                RichLocation member = (RichLocation) i.next();
387                results.add(this.intersection(member));
388            }
389            return RichLocation.Tools.construct(RichLocation.Tools.merge(results));
390        } else {
391            // Simple vs. ourselves
392            // For every member of ourselves, intersect with the location
393            // passed as a parameter. Then construct a new location from the
394            // results of all the intersections.
395            Set results = new TreeSet();
396            for (Iterator i = this.members.iterator(); i.hasNext();) {
397                RichLocation member = (RichLocation) i.next();
398                results.add(member.intersection(l));
399            }
400            return RichLocation.Tools.construct(RichLocation.Tools.merge(results));
401        }
402    }
403
404    /**
405     * {@inheritDoc}
406     * Recursively applies this call to all members.
407     */
408    public void setCrossRefResolver(CrossReferenceResolver r) {
409        for (Iterator i = this.members.iterator(); i.hasNext();) {
410            ((RichLocation) i.next()).setCrossRefResolver(r);
411        }
412    }
413
414    /**
415     * {@inheritDoc}
416     * This function concatenates the symbols of all its child locations.
417     * <p>
418     * The most obvious application of this method to a <code>CompoundRichLocation</code>
419     * is the contatenation of the components of a gene with multiple exons.
420     */
421    public SymbolList symbols(SymbolList seq) {
422        if (seq == null) {
423            throw new IllegalArgumentException("Sequence cannot be null");
424        }
425
426        List res = new ArrayList();
427        for (Iterator i = this.members.iterator(); i.hasNext();) {
428            RichLocation l = (RichLocation) i.next();
429            res.addAll(l.symbols(seq).toList());
430        }
431
432        try {
433            return new SimpleSymbolList(seq.getAlphabet(), res);
434        } catch (IllegalSymbolException ex) {
435            throw new RuntimeException("Could not build compound sequence string", ex);
436        }
437    }
438
439    /**
440     * {@inheritDoc}
441     */
442    public void setTerm(ComparableTerm term) throws ChangeVetoException {
443        if (term == null) {
444            throw new ChangeVetoException("Cannot set term to null");
445        }
446        super.setTerm(term);
447    }
448
449    /**
450     * {@inheritDoc}
451     */
452    public int hashCode() {
453        int code = 17;
454        code = 31 * code + this.getTerm().hashCode();
455        for (Iterator i = this.members.iterator(); i.hasNext();) {
456            code = 31 * i.next().hashCode();
457        }
458        return code;
459    }
460
461    /**
462     * {@inheritDoc}
463     * Compound locations are only equal to other Locations if all their
464     * components are equal.
465     */
466    public boolean equals(Object o) {
467        if (o == this) {
468            return true;
469        }
470        if (!(o instanceof Location)) {
471            return false;
472        }
473        Location them = (Location) o;
474
475        if (them.isContiguous()) {
476            return false;
477        } //because this is not!
478
479        // ok - both compound. The blocks returned from blockIterator should each be
480        // equivalent.
481        Iterator i1 = this.blockIterator();
482        Iterator i2 = them.blockIterator();
483
484        // while there are more pairs to check...
485        while (i1.hasNext() && i2.hasNext()) {
486            // check that this pair is equivalent
487            Location l1 = (Location) i1.next();
488            Location l2 = (Location) i2.next();
489
490            if (!(l1.equals(l2))) // not equivalent blocks so not equal
491            {
492                return false;
493            }
494        }
495        if (i1.hasNext() || i2.hasNext()) {
496            // One of the locations had more blocks than the other
497            return false;
498        }
499        // Same number of blocks, all equivalent. Must be equal.
500        return true;
501    }
502
503    /**
504     * {@inheritDoc}
505     * 
506     */
507    public int compareTo(Object o) {
508        Location fo = (Location) o;
509        if (this.equals(fo)) {
510            return 0;
511        } else {
512            return this.getMin() - fo.getMin();
513        }
514    }
515
516    /**
517     * {@inheritDoc}
518     * Form: "term:[location,location...]"
519     */
520    public String toString() {
521        StringBuffer sb = new StringBuffer();
522        sb.append(this.getTerm());
523        sb.append(":[");
524        for (Iterator i = this.blockIterator(); i.hasNext();) {
525            sb.append(i.next());
526            if (i.hasNext()) {
527                sb.append(",");
528            }
529        }
530        sb.append("]");
531        return sb.toString();
532    }
533}
534