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.biojava.nbio.genome.parsers.gff;
022
023
024/**
025 * A location on a sequence.
026 * A location is a contiguous range of indices, with a single start and end point.
027 * <br><br>
028 * Internally, location indices are stored in Java "half-open" format: the start is the (origin 0) index of
029 * the first symbol in the range; the end is the origin 0 index of the first symbol PAST the
030 * end of the range, so that end - start == length.
031 * <br><br>
032 * Location objects, once constructed, cannot be changed. Instead, all methods return a new
033 * location. This allows the use of "method chaining" to implement a particular calculation.
034 * For example, consider the chained statement "loc.prefix( 100 ).suffix( 10 )",
035 * which first applies the prefix method to
036 * the variable named loc, and then the suffix method to the result.
037 * Together, the chained operations create a new location object of length 10
038 * whose start is the index of the 90th symbol.
039 * Here's another example. This one returns a location object holding the coordinates of the intron between
040 * the first exon (location exon1) and
041 * the second exon (location exon2) on a sequence (seq): "seq.prefix( exon2 ).suffix( exon1 )"
042 * <br><br>
043 * About the negative (reverse) strand: The location object stores reverse strand locations as
044 * negative indices. For example, the positive strand location from index 12 to index 97 is
045 * on the opposite side as index -97 (start) to index -12 (end). Note that the larger index is
046 * always downstream from the smaller index, (i.e. start &lt;= end, regardless of strand).
047 * Obviously this representation makes it trivial
048 * to convert a location from one strand to the other.
049 * <br><br>
050 * Additional points regarding the use of locations on opposite strands:
051 *<br>
052 * (1) Opposite strand locations cannot be compared, eg isBefore() will
053 * throw an exception.<br>
054 * (2) Containment queries ( eg overlaps(), contains() ) also throw exceptions.
055 *<br>
056 * (3) The plus() method will map a location to its positive strand equivalent; use it on both args
057 * before calling, for example the intersection() method,
058 * if your code needs to be indifferent to strand.
059 *<br><br>
060 * Exceptions and how they are (typically) used:
061 *<br>
062 * IllegalArgumentException - the location given as a parameter is not on the same strand as the location.
063 *<br>
064 * IndexOutOfBoundsException - often means the operation caused the location to span the origin, ie
065 * be partially on positive and partially on negative strand.
066 *<br>
067 * @author Hanno Hinsch
068 */
069public class Location implements Iterable<Location>
070{
071
072        private int mStart;
073        private int mEnd;
074
075
076        /**
077         * Construct new location from coordinates.
078         * See package description of coordinate format.
079         * @param start Origin 0 index of first symbol.
080         * @param end Origin 0 index of last symbol + 1.
081         * @throws IllegalArgumentException End is not after start, or location spans the origin
082         */
083        public Location( int start, int end )
084        {
085                mStart= start;
086                mEnd= end;
087
088                if( !isHealthy() )
089                {
090                        throw new IllegalArgumentException( "Improper location parameters: (" + start + "," + end + ")" );
091                }
092
093        }
094
095        /**
096         * Clone other location.
097         * @param other The location to clone.
098         */
099        public Location( Location other )
100        {
101                mStart= other.mStart;
102                mEnd= other.mEnd;
103
104                assert isHealthy(): toString();
105        }
106
107                public int getBegin(){
108                        if(isNegative())
109                                return mEnd;
110                        else
111                                return mStart;
112                }
113
114                public int getEnd(){
115                        if(isNegative())
116                                return mStart;
117                        else
118                                return mEnd;
119                }
120
121
122        /**
123         * Create location from "biocoordinates", as in GFF file. In biocoordinates,
124         * the start index of a range is represented in origin 1 (ie the very first index is 1, not 0),
125         * and end= start + length - 1.
126         *
127         * @param start Origin 1 index of first symbol.
128         * @param end Origin 1 index of last symbol.
129         * @param strand '+' or '-' or '.' ('.' is interpreted as '+').
130         * @return Created location.
131         * @throws IllegalArgumentException strand must be '+', '-' or '.'
132         */
133        public static Location fromBio( int start, int end, char strand )
134        {
135                int s= start - 1;
136                int e= end;
137
138                if( !( strand == '-' || strand == '+' || strand == '.' ))
139                {
140                        throw new IllegalArgumentException( "Strand must be '+', '-', or '.'" );
141                }
142
143                if( strand == '-' )
144                {
145                        //negate
146                        s= - end;
147                        e= - ( start - 1);
148                }
149
150                return new Location( s, e );
151        }
152
153        /**
154         * Create a location from MAF file coordinates, which represent negative
155         * strand locations as the distance from the end of the sequence.
156         *
157         * @param start Origin 1 index of first symbol.
158         * @param length Number of symbols in range.
159         * @param strand '+' or '-' or '.' ('.' is interpreted as '+').
160         * @param totalLength Total number of symbols in sequence.
161         * @throws IllegalArgumentException Strand must be '+', '-', '.'
162         *
163         */
164         public static Location fromBioExt( int start, int length, char strand, int totalLength )
165         {
166                int s= start;
167                int e= s + length;
168
169                if( !( strand == '-' || strand == '+' || strand == '.' ))
170                {
171                        throw new IllegalArgumentException( "Strand must be '+', '-', or '.'" );
172                }
173
174                if( strand == '-' )
175                {
176                        s= s - totalLength;
177                        e= e - totalLength;
178                }
179
180                return new Location( s, e );
181         }
182
183        /**
184         * Get character representation of strand.
185         *
186         * @return '+' or '-'
187         */
188        public char bioStrand()
189        {
190                return ( isNegative() )?'-':'+';
191        }
192
193        /**
194         * Get start index, in biocoordinates.
195         *
196         * @return The origin 1 index of the first symbol in location.
197         */
198        public int bioStart()
199        {
200                return plus().start() + 1;
201        }
202
203        /**
204         * Get end index, in biocoordinates.
205         *
206         * @return The origin 1 index of the final symbol in location.
207         */
208        public int bioEnd()
209        {
210                return plus().end();
211        }
212
213
214
215        /**
216         * Return location that is in same position on plus strand. If location is already
217         * on plus strand, just return the location unchanged.
218         *
219         * @return Location on plus strand.
220         */
221        public Location plus()
222        {
223                if( isNegative() )
224                {
225                        return opposite();
226                }
227                else
228                {
229                        return this;
230                }
231        }
232
233        /**
234         * Return location that is in same position on negative strand. If location is already
235         * on negative strand, just return the location unchanged.
236         *
237         * @return Location on negative strand.
238         */
239        public Location minus()
240        {
241                if( isNegative() )
242                {
243                        return this;
244                }
245                else
246                {
247                        return opposite();
248                }
249        }
250
251
252        /**
253        *  Return the union.
254        * <br>
255        *
256         * @param other The location to join.
257         * @return The union is a range that starts at the lesser of the two starting indices and ends at the
258         * greater of the two ends.
259         * @throws IllegalArgumentException Locations are on opposite strands.
260        */
261        public Location union( Location other )
262        {
263
264                if( !isSameStrand( other ))
265                {
266                        throw new IllegalArgumentException( "Locations are on opposite strands." );
267                }
268                else
269                {
270                        int start= (other.mStart < mStart)? other.mStart: mStart;
271                        int end= (other.mEnd > mEnd)? other.mEnd: mEnd;
272
273                        return new Location( start, end );
274                }
275
276        }
277
278        /**
279         * Return the intersection, or null if no overlap.
280         *
281         * @param other
282         *            The location to intersect.
283         * @return The maximal location that is contained by both. Returns null if
284         *         no overlap!
285         * @throws IllegalArgumentException
286         *             Locations are on opposite strands.
287         */
288        public Location intersection(Location other) {
289                if (isSameStrand(other)) {
290                        return intersect(mStart, mEnd, other.mStart, other.mEnd);
291                } else {
292                        throw new IllegalArgumentException("Locations are on opposite strands.");
293                }
294        }
295
296        private Location intersect(int a1, int a2, int b1, int b2) {
297                if (a1 > b1) {
298                        return intersect(b1, b2, a1, a2);
299                }
300                // Safe to assume a1 <= b1
301                if (b1 >= a2) {
302                        // b starts after a ends
303                        return null;
304                } else if (b1 < a2 && b2 <= a2) {
305                        // b starts after a starts and ends before or at where a ends
306                        return new Location(b1, b2);
307                } else if (b1 >= a1 && a2 <= b2) {
308                        // b starts after a but extends after the end of a
309                        return new Location(b1, a2);
310                }
311                return null;
312        }
313
314
315        /**
316         * Get starting index (origin 0).
317         *
318         * @return The start index.
319         */
320        public int start()
321        {
322                return mStart;
323        }
324
325        /**
326         * Get the ending index.
327         *
328         * @return The index of last symbol + 1 (remember Java half-open coordinates).
329         */
330        public int end()
331        {
332                return mEnd;
333        }
334
335        /**
336         * Get length of range.
337         *
338         * @return The length of the range (end - start).
339         */
340        public int length()
341        {
342                return mEnd - mStart;
343        }
344
345
346        /**
347         * Enable a "sliding window" iteration over a location
348         * to use with Java's "for" loop construct.
349         * The returned helper object implements the Iterable interface; the windowSize and increment semantics are implemented
350         * by an underlying LocIterator.
351         * <br><br>
352         * For example, given a location variable "loc":
353         *<br>
354<pre>
355        //use window size of 3 and increment of +3
356        for( Location temp: loc.window( 3, 3 ))
357        {
358        //at each iteration, temp will be the location of the next 3 symbols
359        }
360</pre>
361         *
362         * @param windowSize The number of symbols to get on each iteration.
363         * @param increment The direction and number of symbols to advance at each iteration.
364         * @return An anonymous iterable object to use with Java's for( ... ) loop construct.
365         */
366        public Iterable<Location> window( final int windowSize, final int increment )
367        {
368                final Location loc= this;
369
370                //return iterable anonymous inner class
371                return new Iterable<Location> ()
372                        {
373                                @Override
374                                public LocIterator iterator()
375                                {
376                                        return new LocIterator( loc, windowSize, increment );
377                                }
378
379                        };
380        }
381
382        /**
383         * Create a location iterator over this location with a window size of 1 and
384         * an increment of +1 (successive symbols from start to end).
385         *
386         * @return An iterator over a Location (a LocIterator object).
387         */
388        @Override
389        public LocIterator iterator()
390        {
391                return new LocIterator( this, 1, 1 );
392        }
393
394        /**
395         * Create a location iterator over this location,
396         * using specified window size and increment.
397         *
398         * @param windowSize The number of symbols to get on each iteration.
399         * @param increment The direction and number of symbols to advance at each iteration.
400         * @return An iterator over a Location (a LocIterator object).
401         */
402        public LocIterator iterator( int windowSize, int increment )
403        {
404                return new LocIterator( this, windowSize, increment );
405        }
406
407
408        /**
409         * The part of this location before the specified position. If position is negative,
410         * count backwards from the end.
411         * <br><br>
412         * For position >= 0, return Location( start, start + position ).
413         * <br>
414         * For position < 0, return Location( start, end + position ).
415         * <br>
416         * @return New location from start of this location to directly before position.
417         * @param position Where the prefix ends.
418         * @throws IndexOutOfBoundsException Specified prefix is longer than location.
419         */
420        public Location prefix( int position )
421        {
422                int end;
423                if( position >= 0 )
424                {
425                        if( (mStart + position <= mEnd) )
426                        {
427                                end= mStart + position;
428                        }
429                        else
430                        {
431                                throw new IndexOutOfBoundsException( "Specified prefix longer than location." );
432                        }
433                }
434                else
435                {
436                        if( (mEnd + position > mStart))
437                        {
438                                end= mEnd + position;
439                        }
440                        else
441                        {
442                                throw new IndexOutOfBoundsException( "Specified prefix longer than location." );
443                        }
444                }
445
446                return new Location( mStart, end );
447        }
448
449
450        /**
451         * The part of this location after the specified position. If position is negative, count backwards
452         * from the end.
453         * <br><br>
454         * For position >= 0, return Location( start + position, end ).
455         * <br>
456         * For position < 0, return Location( end - position, end ).
457         * <br>
458         * @return New location from position to end of this location.
459         * @param position Where the suffix starts.
460         * @throws IndexOutOfBoundsException Specified suffix is longer than location.
461         */
462        public Location suffix( int position )
463        {
464                int start;
465                if( position >= 0 )
466                {
467                        if( mStart + position <= mEnd ) // Scooter willis when 60 + 60 = 120 no remainder
468                        {
469                                start= mStart + position;
470                        }
471                        else
472                        {
473                                throw new IndexOutOfBoundsException( "Specified suffix longer than location." );
474                        }
475                }
476                else
477                {
478                        if( mEnd + position >= mStart )
479                        {
480                                start= mEnd + position;
481                        }
482                        else
483                        {
484                                throw new IndexOutOfBoundsException( "Specified suffix longer than location." );
485                        }
486                }
487
488                return new Location( start, mEnd );
489        }
490
491        /**
492         * The part of this location before the other location (not inclusive).
493         *
494         * @param other The other location.
495         * @return The part of this location before the other location.
496         * @throws IllegalArgumentException Locations are on opposite strands.
497         * @throws IndexOutOfBoundsException This location does not contain other location.
498         */
499        public Location prefix( Location other )
500        {
501
502                if( isSameStrand( other ) )
503                {
504                        if( other.mStart >= mStart )
505                        {
506                                return new Location( mStart, (other.mStart < mEnd)? other.mStart: mEnd );
507                        }
508                        else
509                        {
510                                //other is out of bounds -- no prefix
511                                throw new IndexOutOfBoundsException( "Specified location not within this location." );
512                        }
513                }
514                else
515                {
516                        throw new IllegalArgumentException( "Locations are on opposite strands." );
517                }
518        }
519
520        /**
521         * The part of this location after the other location (not inclusive).
522         *
523         * @param other The other location.
524         * @return The part of this location after the other location.
525         * @throws IllegalArgumentException Locations are on opposite strands.
526         * @throws IndexOutOfBoundsException This location does not contain other location.
527         */
528        public Location suffix( Location other )
529        {
530                if( isSameStrand( other ))
531                {
532                        if( other.mEnd <= mEnd )
533                        {
534                                return new Location( (other.mEnd > mStart)? other.mEnd: mStart, mEnd );
535                        }
536                        else
537                        {
538                                //other is out of bounds -- no suffix
539                                throw new IndexOutOfBoundsException( "Specified location not within this location." );
540                        }
541                }
542                else
543                {
544                        throw new IllegalArgumentException( "Locations are on opposite strands." );
545                }
546
547        }
548
549        /**
550         * Return the adjacent location of specified length directly upstream of this location.
551         *
552         * @return Upstream location.
553         * @param length The length of the upstream location.
554         * @throws IndexOutOfBoundsException Specified length causes crossing of origin.
555         */
556        public Location upstream( int length )
557        {
558                if( length < 0 )
559                {
560                        throw new IllegalArgumentException( "Parameter must be >= 0; is=" + length );
561                }
562
563                if( Math.signum( mStart - length) == Math.signum( mStart ) || 0 == Math.signum( mStart - length ) )
564                {
565                        return new Location(mStart - length, mStart );
566                }
567                else
568                {
569                        throw new IndexOutOfBoundsException( "Specified length causes crossing of origin: " + length + "; " + toString() );
570                }
571        }
572
573        /**
574         * Return the adjacent location of specified length directly downstream of this location.
575         *
576         * @return The downstream location.
577         * @param length The length of the downstream location.
578         * @throws IndexOutOfBoundsException Specified length causes crossing of origin.
579         */
580        public Location downstream( int length )
581        {
582                if( length < 0 )
583                {
584                        throw new IllegalArgumentException( "Parameter must be >= 0; is=" + length );
585                }
586
587                if( Math.signum( mEnd + length) == Math.signum( mEnd ) || 0 == Math.signum( mEnd + length ) )
588                {
589                        return new Location( mEnd, mEnd + length );
590                }
591                else
592                {
593                        throw new IndexOutOfBoundsException( "Specified length causes crossing of origin: " + length + "; " + toString() );
594                }
595
596        }
597
598
599
600        /**
601        *   Return distance between this location and the other location.
602        *
603        *       Distance is defined only if both locations are on same strand.
604         *
605         * @param other The location to compare.
606         * @return The integer distance. Returns -1 if they overlap; 0 if directly adjacent.
607         * @throws IllegalArgumentException Locations are on opposite strands.
608         */
609        public int distance( Location other )
610        {
611                if( isSameStrand( other ))
612                {
613                        if( overlaps( other ))
614                        {
615                                return -1;
616                        }
617                        else
618                        {
619                                return ( mEnd <= other.mStart )? (other.mStart - mEnd) : (mStart - other.mEnd);
620                        }
621                }
622                else
623                {
624                        throw new IllegalArgumentException( "Locations are on opposite strands." );
625                }
626        }
627
628        /**
629         * Return percent overlap of two locations.
630         *
631         * @param other The location to compare.
632         * @return 100.0 * intersection(other).length() / this.length()
633         * @throws IllegalArgumentException Locations are on opposite strands.
634         */
635        public double percentOverlap( Location other )
636        {
637                if( length() > 0 && overlaps( other ))
638                {
639                        return 100.0 * (((double) intersection( other ).length()) / (double) length());
640                }
641                else
642                {
643                        return 0;
644                }
645        }
646
647        /**
648         * Check if this location and other location overlap.
649         *
650         * @param other The location to compare.
651         * @return True if they overlap.
652         * @throws IllegalArgumentException Locations are on opposite strands.
653         */
654        public boolean overlaps( Location other )
655        {
656                if( isSameStrand( other ))
657                {
658                        return !( mStart >= other.mEnd || mEnd <= other.mStart );
659                }
660                else
661                {
662                        throw new IllegalArgumentException( "Locations are on opposite strands." );
663                }
664        }
665
666        /**
667         * Check if this location contains the other.
668         *
669         * @param other The location to compare.
670         * @return True if other is entirely contained by this location.
671         * @throws IllegalArgumentException Locations are on opposite strands.
672         */
673        public boolean contains( Location other )
674        {
675                if( isSameStrand( other ))
676                {
677                        return ( mStart <= other.mStart && mEnd >= other.mEnd );
678                }
679                else
680                {
681                        throw new IllegalArgumentException( "Locations are on opposite strands." );
682                }
683        }
684
685
686        /**
687         * Check if this location starts after the other location starts.
688         * The locations may overlap.
689         *
690         * @param other The location to compare.
691         * @return True if this starts after other.
692         * @throws IllegalArgumentException Locations are on opposite strands.
693         */
694        public boolean startsAfter( Location other )
695        {
696                if( isSameStrand( other ))
697                {
698                        return mStart > other.mStart;
699                }
700                else
701                {
702                        throw new IllegalArgumentException( "Locations are on opposite strands." );
703                }
704        }
705
706        /**
707         * Check if this location starts before other location starts.
708         * The locations may overlap.
709         *
710         * @param other The location to compare.
711         * @return True if this starts before other.
712         * @throws IllegalArgumentException Locations are on opposite strands.
713         */
714        public boolean startsBefore( Location other )
715        {
716                if( isSameStrand( other ))
717                {
718                        return mStart < other.mStart;
719                }
720                else
721                {
722                        throw new IllegalArgumentException( "Locations are on opposite strands." );
723                }
724        }
725
726        /**
727         * Check if this location ends after other location ends.
728         * The locations may overlap.
729         *
730         * @param other The location to compare.
731         * @return True if location ends after other.
732         * @throws IllegalArgumentException Locations are on opposite strands.
733         */
734        public boolean endsAfter( Location other )
735        {
736                if( isSameStrand( other ) )
737                {
738                        return mEnd > other.mEnd;
739                }
740                else
741                {
742                        throw new IllegalArgumentException( "Locations are on opposite strands." );
743                }
744        }
745
746        /**
747         * Check if this location ends before other location ends.
748         * The locations may overlap.
749         *
750         * @param other The location to compare.
751         * @return True if this ends before other.
752         * @throws IllegalArgumentException Locations are on opposite strands.
753         */
754        public boolean endsBefore( Location other )
755        {
756                if( isSameStrand( other ) )
757                {
758                        return mEnd < other.mEnd;
759                }
760                else
761                {
762                        throw new IllegalArgumentException( "Locations are on opposite strands." );
763                }
764        }
765
766        /**
767         * Check if this location is entirely after the other location (no overlap).
768         *
769         * @param other The location to compare.
770         * @return True if this is after other.
771         * @throws IllegalArgumentException Locations are on opposite strands.
772         */
773        public boolean isAfter( Location other )
774        {
775                if( isSameStrand( other ) )
776                {
777                        return mStart >= other.mEnd;
778                }
779                else
780                {
781                        throw new IllegalArgumentException( "Locations are on opposite strands." );
782                }
783        }
784
785        /**
786         * Check if this location is entirely before other location (no overlap).
787         *
788         * @param other The location to compare.
789         * @return True if this is before other.
790         * @throws IllegalArgumentException Locations are on opposite strands.
791         */
792        public boolean isBefore( Location other )
793        {
794                if( isSameStrand( other ) )
795                {
796                        return mEnd <= other.mStart;
797                }
798                else
799                {
800                        throw new IllegalArgumentException( "Locations are on opposite strands." );
801                }
802        }
803
804        /**
805         * Check if location is on negative strand.
806         * Note that Location( 0, 0 ) is by construction defined to be on the
807         * positive strand.
808         *
809         * @return True if on negative (reverse) strand.
810         */
811        public boolean isNegative()
812        {
813                return ( mStart <= 0 && mEnd <= 0 );
814        }
815
816        /**
817         * Return location that is in same position on opposite strand.
818         *
819         * @return Location on opposite strand.
820         */
821        public Location opposite()
822        {
823                return new Location( - mEnd, - mStart );
824        }
825
826        /**
827         * Check if this location is on same strand as other location.
828         *
829         * @param other The location to compare.
830         * @return True if on same strand.
831         */
832        public boolean isSameStrand( Location other )
833        {
834                return ( isNegative() && other.isNegative() ) || ( !isNegative() && !other.isNegative() );
835        }
836
837
838        /**
839         * Return a string representation of location.
840         *
841         * @return Text string.
842         */
843        @Override
844        public String toString()
845        {
846                return new String( "[L=" + (mEnd - mStart) + "; S=" + mStart + "; E=" + mEnd +"]" );
847        }
848
849        /* (non-Javadoc)
850         * @see java.lang.Object#hashCode()
851         */
852        @Override
853        public int hashCode() {
854                final int prime = 31;
855                int result = 1;
856                result = prime * result + mEnd;
857                result = prime * result + mStart;
858                return result;
859        }
860
861        /* (non-Javadoc)
862         * @see java.lang.Object#equals(java.lang.Object)
863         */
864        @Override
865        public boolean equals(Object obj) {
866                if (this == obj)
867                        return true;
868                if (obj == null)
869                        return false;
870                if (getClass() != obj.getClass())
871                        return false;
872                Location other = (Location) obj;
873                if (mEnd != other.mEnd)
874                        return false;
875                if (mStart != other.mStart)
876                        return false;
877                return true;
878        }
879
880        /**
881         *
882         */
883        private boolean isHealthy()
884        {
885                return ( mStart <= mEnd ) && (( mStart <= 0 && mEnd <= 0 ) || (mStart >= 0 && mEnd >= 0));
886        }
887
888}