Source code

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.symbol;
023
024import java.util.ArrayList;
025import java.util.Collection;
026import java.util.Collections;
027import java.util.Iterator;
028import java.util.List;
029import java.util.ListIterator;
030
031import org.biojava.bio.BioError;
032import org.biojava.bio.BioException;
033
034/**
035 * Tools class containing a number of operators for working with <code>Location</code> objects.
036 *
037 * <p>
038 * Most of the methods in this class are simple set-wise binary operators: for example,
039 * calculate the intersection of two locations.
040 * </p>
041 *
042 * This class provides helpful methods for set-wise manipulation of Location objects.
043 *
044 * @author Matthew Pocock
045 * @author Greg Cox
046 * @author Thomas Down
047 * @author Mark Schreiber
048 * @author Francois Pepin
049 * @since 1.2
050 */
051final public class LocationTools {
052    /**
053     * Nobody needs one of these.
054     */
055
056    private LocationTools() {
057    }
058
059  /**
060   * Return the union of two locations.
061   *
062   * <p>
063   * The union will be a Location instance that contains every index contained
064   * by either locA or locB.
065   * </p>
066   *
067   * @param locA  the first Location
068   * @param locB  the second Location
069   * @return a Location that is the union of locA and locB
070   */
071  public static Location union(Location locA, Location locB) {
072        if(isDecorated(locA) || isDecorated(locB))
073        {
074          handleDecorations(locA, locB);
075          if(locA instanceof CircularLocation && locB instanceof CircularLocation){
076            return CircularLocationTools.union((CircularLocation)locA,(CircularLocation)locB);
077          }
078          if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
079            {
080               return BetweenLocationTools.union(locA, locB);
081            }
082        }
083
084    if(
085      locA.isContiguous() &&
086      locB.isContiguous() &&
087      locA.overlaps(locB)
088    ) {
089      // the simple case
090      Location mloc = null;
091      try {
092        mloc = MergeLocation.mergeLocations(locA, locB);
093      }
094      catch (BioException ex) {
095        //this shouldn't happen as conditions have been checked above
096        throw new BioError("Assertion Error, cannot build MergeLocation",ex);
097      }
098      return mloc;
099
100    } else {
101      // either may be compound. They may not overlap. We must build the
102      // complete list of blocks, merge overlapping blocks and then create the
103      // appropriate implementation of Location for the resulting list.
104
105      // list of all blocks
106      List locList = new ArrayList();
107
108      // add all blocks in locA
109      for(Iterator i = locA.blockIterator(); i.hasNext(); ) {
110        locList.add(i.next());
111      }
112
113      // add all blocks in locB
114      for(Iterator i = locB.blockIterator(); i.hasNext(); ) {
115        locList.add(i.next());
116      }
117
118      return _union(locList);
119    }
120  }
121
122  /**
123   * Return the intersection of two locations.
124   * <p>
125   * The intersection will be a Location instance that contains every index
126   * contained by both locA and locB.
127   * </p>
128   *
129   * @param locA  the first Location
130   * @param locB  the second Location
131   * @return a Location that is the intersection of locA and locB
132   */
133  public static Location intersection(Location locA, Location locB) {
134
135    if(isDecorated(locA) || isDecorated(locB))
136    {
137        handleDecorations(locA, locB);
138        if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
139            {
140                return BetweenLocationTools.intersection(locA, locB);
141            }
142        if (CircularLocationTools.isCircular(locA) || CircularLocationTools.isCircular(locB)) {
143            return CircularLocationTools.intersection(locA, locB);
144        }
145    }
146
147    if(locA.isContiguous() && locB.isContiguous()) {
148        // handle easy case of solid locations
149        // Ought to make this bit more efficient --THOMASD
150        if (LocationTools.contains(locA, locB)) {
151            return locB;
152        } else if (LocationTools.contains(locB, locA)) {
153            return locA;
154        } if(LocationTools.overlaps(locA, locB)) {
155            int min = Math.max(locA.getMin(), locB.getMin());
156            int max = Math.min(locA.getMax(), locB.getMax());
157            return makeLocation(min, max);
158        } else {
159            return Location.empty;
160        }
161    } else {
162        // One or other of the locations is compound. Build a list of all
163        // locations created by finding intersection of all pairwise combinations
164        // of blocks in locA and locB. Ignore all Location.empty. Create the
165        // appropriate Location instance.
166        List locList = new ArrayList();
167
168        List blA = getBlockList(locA);
169        {
170            int minBlock = blockContainingOrFollowingPoint(blA, locB.getMin());
171            int maxBlock = blockContainingOrPreceedingPoint(blA, locB.getMax());
172            if (minBlock == -1 || maxBlock == -1) {
173                return Location.empty;
174            }
175            blA = blA.subList(minBlock, maxBlock + 1);
176        }
177        List blB = getBlockList(locB);
178        {
179            int minBlock = blockContainingOrFollowingPoint(blB, locA.getMin());
180            int maxBlock = blockContainingOrPreceedingPoint(blB, locA.getMax());
181            if (minBlock == -1 || maxBlock == -1) {
182                return Location.empty;
183            }
184            blB = blB.subList(minBlock, maxBlock + 1);
185        }
186
187        if (blA.size() > blB.size()) {
188            List temp = blA;
189            blA = blB;
190            blB = temp;
191        }
192
193        for (Iterator i = blA.iterator(); i.hasNext(); ) {
194            Location blocA = (Location) i.next();
195            int minHitIndex = blockContainingOrFollowingPoint(blB, blocA.getMin());
196            int maxHitIndex = blockContainingOrPreceedingPoint(blB, blocA.getMax());
197            for (int hitIndex = minHitIndex; hitIndex <= maxHitIndex; ++hitIndex) {
198                Location blocB = (Location) blB.get(hitIndex);
199                locList.add(LocationTools.intersection(blocA, blocB));
200            }
201        }
202
203        return buildLoc(locList);
204    }
205  }
206
207    /**
208     * Return an ordered list of non-overlapping blocks of a location
209     * (singleton list for contiguous locations, empty list for empty locations)
210     *
211     * Note that from this point of view, contiguous circular locations
212     * aren't necessarily contiguous :-(.
213     *
214     * @param l the <code>Location</code> to get the blocks from
215     * @return and ordered <code>List</code> of <code>Locations</code>
216     */
217
218    private static List getBlockList(Location l) {
219        if (l == Location.empty) {
220            return Collections.EMPTY_LIST;
221        } else if (l instanceof CompoundLocation) {
222            return ((CompoundLocation )l).getBlockList();
223        } else if (l.isContiguous() && !CircularLocationTools.isCircular(l)) {
224            return Collections.nCopies(1, l);
225        } else {
226            List bl = new ArrayList();
227            for (Iterator bi = l.blockIterator(); bi.hasNext(); ) {
228                bl.add(bi.next());
229            }
230            Collections.sort(bl, Location.naturalOrder);
231            return bl;
232        }
233    }
234
235    /**
236     * Return the index into <code>bl</code> of a block containing
237     * <code>point</code>, or -1 if it is not found.
238     */
239
240    private static int blockContainingPoint(List bl, int point) {
241        int start = 0;
242        int end = bl.size() - 1;
243
244        while (start <= end) {
245            int mid = (start + end) / 2;
246            Location block = (Location) bl.get(mid);
247            if (block.contains(point)) {
248                return mid;
249            } else if (point < block.getMin()) {
250                end = mid - 1;
251            } else if (point > block.getMax()) {
252                start = mid + 1;
253            } else {
254                throw new BioError("Assertion failed: overrun in binary search");
255            }
256        }
257        return -1;
258    }
259
260    /**
261     * Return the index of the block containing <code>point</code>, if it exists,
262     * or the block preceeding it.
263     */
264
265    private static int blockContainingOrPreceedingPoint(List bl, int point) {
266        // System.err.println("COPP");
267        int start = 0;
268        int length = bl.size();
269        int end = length - 1;
270
271        while (start <= end) {
272            int mid = (start + end) / 2;
273            // System.err.println("Start=" + start + " mid=" + mid + " end=" + end);
274            Location block = (Location) bl.get(mid);
275            if (block.contains(point)) {
276                return mid;
277            } else if (point < block.getMin()) {
278                end = mid - 1;
279            } else if (point > block.getMax()) {
280                start = mid + 1;
281            } else {
282                throw new BioError("Assertion failed: overrun in binary search");
283            }
284        }
285
286        if (end < length) {
287            return end;
288        } else {
289            return -1;
290        }
291    }
292
293    /**
294     * Return the index of the block containing <code>point</code>, if it exists,
295     * or the block preceeding it.
296     */
297
298    private static int blockContainingOrFollowingPoint(List bl, int point) {
299        // System.err.println("COFP");
300        int start = 0;
301        int length = bl.size();
302        int end = length - 1;
303
304        while (start <= end) {
305            int mid = (start + end) / 2;
306            // System.err.println("Start=" + start + " mid=" + mid + " end=" + end);
307            Location block = (Location) bl.get(mid);
308            if (block.contains(point)) {
309                return mid;
310            } else if (point < block.getMin()) {
311                end = mid - 1;
312            } else if (point > block.getMax()) {
313                start = mid + 1;
314            } else {
315                throw new BioError("Assertion failed: overrun in binary search");
316            }
317        }
318        if (start >= 0) {
319            return start;
320        } else {
321            return -1;
322        }
323    }
324
325    /**
326     * Determines whether the locations are touching or not (if they could be
327     * merged in a single Location.
328     * <p>
329     * Two locations can merge if they contain at least one index of one
330     * beside one index of the other.
331     * </p>
332     *
333     * @param locA  the first Location
334     * @param locB  the second Location
335     * @return <code>true</code> if they can merge, <code>false</code> otherwise
336     */
337  public static boolean canMerge(Location locA, Location locB){
338    if (overlaps(locA, locB)||
339        overlaps(locA.translate(1), locB)||
340        overlaps(locA.translate(-1),locB))
341      return true;
342    return false;
343  }
344  
345
346  
347    /**
348     * Determines whether the locations overlap or not.
349     * <p>
350     * Two locations overlap if they contain at least one index in common.
351     * </p>
352     *
353     * @param locA  the first Location
354     * @param locB  the second Location
355     * @return <code>true</code> if they overlap, <code>false</code> otherwise
356     */
357
358    public static boolean overlaps(Location locA, Location locB) {
359        if(isDecorated(locA) || isDecorated(locB))
360        {
361            handleDecorations(locA, locB);
362            if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
363                {
364                    return BetweenLocationTools.overlaps(locA, locB);
365                }
366        }
367
368        if(locA.isContiguous() && locB.isContiguous()) {
369            // if they are both solid, return whether the extents overlap
370            return !(
371                     (locA.getMax() < locB.getMin()) ||
372                     (locA.getMin() > locB.getMax())
373                     );
374        } else {
375            // System.err.println("Doing complex overlap stuff");
376
377            List blA = getBlockList(locA);
378            {
379                // System.err.println("In A restriction");
380                int minBlock = blockContainingOrFollowingPoint(blA, locB.getMin());
381                int maxBlock = blockContainingOrPreceedingPoint(blA, locB.getMax());
382                if (minBlock == -1 || maxBlock == -1) {
383                    // System.err.println("blA empty: minBlock=" + minBlock +", maxBlock=" + maxBlock);
384                    return false;
385                }
386                blA = blA.subList(minBlock, maxBlock + 1);
387            }
388            List blB = getBlockList(locB);
389            {
390                // System.err.println("In B restriction");
391                int minBlock = blockContainingOrFollowingPoint(blB, locA.getMin());
392                int maxBlock = blockContainingOrPreceedingPoint(blB, locA.getMax());
393                if (minBlock == -1 || maxBlock == -1) {
394                    // System.err.println("blB empty: minBlock=" + minBlock +", maxBlock=" + maxBlock);
395                    return false;
396                }
397                blB = blB.subList(minBlock, maxBlock + 1);
398            }
399
400            // System.err.println("Restricted lists");
401
402            for(Iterator aI = blA.iterator(); aI.hasNext(); ) {
403                Location a = (Location) aI.next();
404                for(Iterator bI = blB.iterator(); bI.hasNext(); ) {
405                    Location b = (Location) bI.next();
406                    if(LocationTools.overlaps(a, b)) {
407                        return true;
408                    }
409                }
410            }
411
412            return false;
413        }
414    }
415
416    /**
417     * Return <code>true</code> iff all indices in <code>locB</code> are also contained
418     * by <code>locA</code>.
419     *
420     * @param locA The containing location
421     * @param locB The contained location
422     * @return <code>true</code> is locA contains locB
423     */
424
425    public static boolean contains(Location locA, Location locB) {
426        if(isDecorated(locA) || isDecorated(locB))
427        {
428            handleDecorations(locA, locB);
429            if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
430                {
431                    return BetweenLocationTools.contains(locA, locB);
432                }
433        }
434
435        if (locA.getMin() <= locB.getMin() && locA.getMax() >= locB.getMax()) {
436            if (locA.isContiguous()) {
437                return true;
438            } else {
439                List blA = getBlockList(locA);
440                for (Iterator biB = locB.blockIterator(); biB.hasNext(); ) {
441                    Location bloc = (Location) biB.next();
442                    int hitIndex = blockContainingPoint(blA, bloc.getMin());
443                    if (hitIndex < 0) {
444                        return false;
445                    } else {
446                        Location hitBloc = (Location) blA.get(hitIndex);
447                        if (bloc.getMax() > hitBloc.getMax()) {
448                            return false;
449                        }
450                    }
451                }
452                return true;
453            }
454        } else {
455            return false;
456        }
457    }
458
459  /**
460   * Return whether two locations are equal.
461   * <p>
462   * They are equal if both a contains b and b contains a. Equivalently, they
463   * are equal if for every point p, locA.contains(p) == locB.contains(p).
464   * </p>
465   *
466   * @param locA the first Location
467   * @param locB the second Location
468   * @return true if they are equivalent, false otherwise
469   */
470  public static boolean areEqual(Location locA, Location locB) {
471        if(isDecorated(locA) || isDecorated(locB))
472        {
473                handleDecorations(locA, locB);
474                if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
475                {
476                        return BetweenLocationTools.areEqual(locA, locB);
477                }
478        }
479    // simple check - if one is broken and the other isn't, they aren't equal.
480    if(locA.isContiguous() != locB.isContiguous()) {
481      return false;
482    }
483
484    // both contiguous if one is - check extent only
485    if(locA.isContiguous()) {
486      return
487        (locA.getMin() == locB.getMin()) &&
488        (locA.getMax() == locB.getMax());
489    }
490
491    // ok - both compound. The blocks returned from blockIterator should each be
492    // equivalent.
493    Iterator i1 = locA.blockIterator();
494    Iterator i2 = locB.blockIterator();
495
496    // while there are more pairs to check...
497    while(i1.hasNext() && i2.hasNext()) {
498      // check that this pair is equivalent
499      Location l1 = (Location) i1.next();
500      Location l2 = (Location) i2.next();
501
502      if(
503        (l1.getMin() != l2.getMin()) ||
504        (l1.getMax() != l2.getMax())
505      ) {
506        // not equivalent blocks so not equal
507        return false;
508      }
509    }
510
511    // One of the locations had more blocks than the other
512    if(i1.hasNext() || i2.hasNext()) {
513      return false;
514    }
515
516    // Same number of blocks, all equivalent. Must be equal.
517    return true;
518  }
519
520  /**
521   * Create a Location instance from the list of contiguous locations in
522   * locList.
523   * <p>
524   * If the list is empty then Location.empty will be produced. If it is just
525   * one element long, then this will be returned as-is. If there are multiple
526   * locations then they will be sorted and then used to construct a
527   * CompoundLocation.
528   *
529   * @param locList a List<Location>, where each element is a contiguous location.
530   * @return a new Location instance
531   */
532  static Location buildLoc(List locList) {
533    if(locList.size() == 0) {
534      return Location.empty;
535    } else if(locList.size() == 1) {
536      return (Location) locList.get(0);
537    } else {
538      Collections.sort(locList, Location.naturalOrder);
539      return new CompoundLocation(locList);
540    }
541  }
542  
543  /**
544   * Create a Location instance from the sorted list of contiguous locations in
545   * locList.
546   * <p>
547   * If the list is empty then Location.empty will be produced. If it is just
548   * one element long, then this will be returned as-is. If there are multiple
549   * locations then they will be sorted and then used to construct a
550   * CompoundLocation.
551   *
552   * @param locList a List<Location>, where each element is a contiguous location.
553   * @return a new Location instance
554   */
555  
556  static Location buildLocSorted(List locList) {
557      if(locList.size() == 0) {
558        return Location.empty;
559      } else if(locList.size() == 1) {
560        return (Location) locList.get(0);
561      } else {
562        return new CompoundLocation(locList);
563      }
564    }
565
566    /**
567     * The n-way union of a Collection of locations.  Returns a Location
568     * which covers every point covered by at least one of the locations
569     * in <code>locs</code>
570     *
571     * @param locs A collection of locations.
572     * @return A union location
573     * @throws ClassCastException if the collection contains non-Location objects.
574     */
575
576    public static Location union(Collection locs) {
577        boolean circular = false;
578        List locList = new ArrayList();
579        for (Iterator li = locs.iterator(); li.hasNext(); ) {
580            Location loc = (Location) li.next();
581            if((loc instanceof CircularLocation)){
582              circular = true;
583              locList.add(loc);
584            }else{
585              for (Iterator bi = loc.blockIterator(); bi.hasNext(); ) {
586                locList.add(bi.next());
587              }
588            }
589        }
590        if(circular){
591          //need to add these one at a time
592          ListIterator li = locList.listIterator();
593          CircularLocation loc = (CircularLocation)li.next();
594          while(li.hasNext()){
595            loc = (CircularLocation)union(loc, (Location)li.next());
596          }
597          return loc;
598        }else{
599          return _union(locList);
600        }
601    }
602
603
604    static Location _union(List locList) {
605      // sort these blocks
606      Collections.sort(locList, Location.naturalOrder);
607
608      // merge into this list...
609      List joinList = new ArrayList();
610
611      // start iterating over sorted list.
612      // last is used as loop variable. We must be careful about zero lengthed
613      // lists and also careful to merge overlaps before adding to joinList.
614      Iterator i = locList.iterator();
615      Location last = Location.empty;
616
617
618      // prime last
619      if(i.hasNext()) {
620        last = (Location) i.next();
621      }
622
623      // merge or add last with next location
624      while(i.hasNext()) {
625        Location cur = (Location) i.next();
626        if(canMerge(last,cur)) {
627          try {
628            last = MergeLocation.mergeLocations(last,cur);
629          }
630          catch (BioException ex) {
631            throw new BioError("Cannot make MergeLocation",ex);
632          }
633        } else {
634          joinList.add(last);
635          last = cur;
636        }
637      }
638
639      // handle the end of the loop
640      if(last == Location.empty) {
641        return Location.empty;
642      } else {
643        joinList.add(last);
644      }
645
646      // now make the appropriate Location instance
647      return buildLocSorted(joinList);
648    }
649
650  /**
651   * Return a contiguous Location from min to max.
652   * <p>
653   * If min == max then a PointLocation will be made, otherwise, a RangeLocation
654   * will be returned.
655   *
656   * @param min  the Location min value
657   * @param max  the Location max value
658   * @return a new Location from min to max
659   */
660  public static Location makeLocation(int min, int max) {
661    if(min == max) {
662      return new PointLocation(min);
663    } else {
664      return new RangeLocation(min, max);
665    }
666  }
667
668    /**
669     * A simple method to generate a RangeLocation wrapped
670     * in a CircularLocation. The method will cope with situtations
671     * where the min is greater than the max. Either of min or max can
672     * be negative, or greater than the underlying sequence length. If min and
673     * max are equal a wrapped point location will be made.
674     *
675     * @param min the "left" end of the location
676     * @param max the "right" end of the location
677     * @param seqLength the lenght of the sequence that the location will
678     * be applied to (for purposes of determining origin).
679     * @return the new <code>CircularLocation</code>
680     */
681    public static CircularLocation makeCircularLocation(int min, int max, int seqLength){
682        return CircularLocationTools.makeCircLoc(min,max,seqLength);
683    }
684
685  /**
686   * Checks if the location has a decorator.
687   *
688   * @param theLocation The location to test for decorators
689   * @return True if the location has a decorator and false otherwise
690   */
691  static boolean isDecorated(Location theLocation)
692  {
693        return (theLocation instanceof AbstractLocationDecorator);
694  }
695
696  /**
697   * Currently CircularLocations are handled if and only if
698   * CircularLocationTools.safeOperation returns true. For this to be true
699   * the locations must have the same sequence length.
700   *
701   * BetweenLocations are handled in all cases.  Overlap cases, such as
702   * between, circular locations have indeterminate behavior.
703   *
704   * The default behavior is to not handle decorators.  Any new decorators
705   * will have to re-visit this method
706   */
707  private static void handleDecorations(Location locA, Location locB){
708    if(CircularLocationTools.isCircular(locA)|| CircularLocationTools.isCircular(locB)){
709        if(CircularLocationTools.safeOperation(locA, locB) == false){
710              throw new UnsupportedOperationException(
711                "Binary operations between Circular and"+
712                " Non-Circular locations, or CircularLocations"+
713                " from sequences of differing length are currently unsupported.");
714        }
715      }
716    else if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
717    {
718        // Intentionally blank
719    }
720    else{
721        throw new ClassCastException("Decorated locations are not handled in this version: " + locA.getClass().getName() + ", " + locB.getClass().getName());
722      }
723  }
724
725  /**
726   * Flips a location relative to a length.
727   *
728   * <p>It is very common in biological sequences to represent locations on a sequence and then reverse that
729   * sequence. This method allows locations in the original coordinate space to be transformed int
730   * locations in the reverse one.</p>
731   *
732   * @param loc  the Location to flip
733   * @param len  the length of the region to flip within
734   * @return  a flipped view of the location
735   */
736  public static Location flip(Location loc, int len) {
737      if(loc instanceof PointLocation) {
738          return new PointLocation(len - loc.getMin() + 1);
739      } else if(loc instanceof RangeLocation) {
740          return new RangeLocation(
741            len - loc.getMax() + 1,
742            len - loc.getMin() + 1
743          );
744      } else {
745          Iterator bi = loc.blockIterator();
746          Location res = (Location) bi.next();
747          while(bi.hasNext()) {
748              res = LocationTools.union(res, (Location) bi.next());
749          }
750          return res;
751      }
752  }
753
754    /**
755     * Subtract one location from another.  This methods calculates the set of
756     * points which are contains in location <code>keep</code> but not in
757     * <code>remove</code>.
758     *
759     * @param keep A location
760     * @param remove A location
761     * @return a location containing all points which are in x but not y
762     * @since 1.3
763     */
764
765    public static Location subtract(Location keep, Location remove) {
766        // fixme: documentation hack - I should re-factor this method
767        Location x = keep;
768        Location y = remove;
769        
770        if (isDecorated(x) || isDecorated(y)) {
771            handleDecorations(x, y);
772        }
773
774        List spans = new ArrayList();
775        for (Iterator i = x.blockIterator(); i.hasNext(); ) {
776            Location xb = (Location) i.next();
777            Location yb = LocationTools.intersection(xb, y);
778            int pos = xb.getMin();
779            for (Iterator j = yb.blockIterator(); j.hasNext(); ) {
780                Location sb = (Location) j.next();
781                if (sb.getMin() > pos) {
782                    spans.add(new RangeLocation(pos, sb.getMin() - 1));
783                }
784                pos = sb.getMax() + 1;
785            }
786            if (pos <= xb.getMax()) {
787                spans.add(new RangeLocation(pos, xb.getMax()));
788            }
789        }
790        return LocationTools.union(spans);
791    }
792    
793    /**
794     * Return the number of positions which are covered by a <code>Location</code>
795     *
796     * @param loc A location
797     * @return the number of distinct points contained by that location
798     * @since 1.4
799     */
800    
801    public static int coverage(Location loc) {
802        int cov = 0;
803        for (Iterator i = loc.blockIterator(); i.hasNext(); ) {
804            Location bloc = (Location) i.next();
805            cov += (bloc.getMax() - bloc.getMin() + 1);
806        }
807        return cov;
808    }
809    
810    /**
811     * Return a contiguous location running from the minimum to the maximum points of
812     * the specified location.
813     * 
814     * @param loc a location
815     * @return a corresponding contiguous location
816     */
817    
818    public static Location shadow(Location loc) {
819        if (loc.isContiguous()) {
820            return loc;
821        } else {
822            return new RangeLocation(loc.getMin(), loc.getMax());
823        }
824    }
825    
826    /**
827     * Return the number of contiguous blocks in a location.
828     * 
829     * @param loc a location
830     * @return the number of blocks
831     * @since 1.4
832     */
833    
834    public static int blockCount(Location loc) {
835        if (loc.isContiguous()) {
836            if (loc instanceof EmptyLocation) {
837                return 0;
838            } else {
839                return 1;
840            }
841        } else {
842            int cnt = 0;
843            for (Iterator bi = loc.blockIterator(); bi.hasNext(); ) {
844                bi.next(); ++cnt;
845            }
846            return cnt;
847        }
848    }
849}