/*
* BioJava development code
*
* This code may be freely distributed and modified under the
* terms of the GNU Lesser General Public Licence. This should
* be distributed with the code. If you do not have a copy,
* see:
*
* http://www.gnu.org/copyleft/lesser.html
*
* Copyright for this code is held jointly by the individual
* authors. These should be listed in @author doc comments.
*
* For more information on the BioJava project and its aims,
* or to join the biojava-l mailing list, visit the home page
* at:
*
* http://www.biojava.org/
*
*/
package org.biojava.bio.symbol;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import org.biojava.bio.BioError;
import org.biojava.bio.BioException;
/**
* Tools class containing a number of operators for working with Location
objects.
*
*
* Most of the methods in this class are simple set-wise binary operators: for example, * calculate the intersection of two locations. *
* * This class provides helpful methods for set-wise manipulation of Location objects. * * @author Matthew Pocock * @author Greg Cox * @author Thomas Down * @author Mark Schreiber * @author Francois Pepin * @since 1.2 */ final public class LocationTools { /** * Nobody needs one of these. */ private LocationTools() { } /** * Return the union of two locations. * ** The union will be a Location instance that contains every index contained * by either locA or locB. *
* * @param locA the first Location * @param locB the second Location * @return a Location that is the union of locA and locB */ public static Location union(Location locA, Location locB) { if(isDecorated(locA) || isDecorated(locB)) { handleDecorations(locA, locB); if(locA instanceof CircularLocation && locB instanceof CircularLocation){ return CircularLocationTools.union((CircularLocation)locA,(CircularLocation)locB); } if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB))) { return BetweenLocationTools.union(locA, locB); } } if( locA.isContiguous() && locB.isContiguous() && locA.overlaps(locB) ) { // the simple case Location mloc = null; try { mloc = MergeLocation.mergeLocations(locA, locB); } catch (BioException ex) { //this shouldn't happen as conditions have been checked above throw new BioError("Assertion Error, cannot build MergeLocation",ex); } return mloc; } else { // either may be compound. They may not overlap. We must build the // complete list of blocks, merge overlapping blocks and then create the // appropriate implementation of Location for the resulting list. // list of all blocks List locList = new ArrayList(); // add all blocks in locA for(Iterator i = locA.blockIterator(); i.hasNext(); ) { locList.add(i.next()); } // add all blocks in locB for(Iterator i = locB.blockIterator(); i.hasNext(); ) { locList.add(i.next()); } return _union(locList); } } /** * Return the intersection of two locations. ** The intersection will be a Location instance that contains every index * contained by both locA and locB. *
* * @param locA the first Location * @param locB the second Location * @return a Location that is the intersection of locA and locB */ public static Location intersection(Location locA, Location locB) { if(isDecorated(locA) || isDecorated(locB)) { handleDecorations(locA, locB); if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB))) { return BetweenLocationTools.intersection(locA, locB); } if (CircularLocationTools.isCircular(locA) || CircularLocationTools.isCircular(locB)) { return CircularLocationTools.intersection(locA, locB); } } if(locA.isContiguous() && locB.isContiguous()) { // handle easy case of solid locations // Ought to make this bit more efficient --THOMASD if (LocationTools.contains(locA, locB)) { return locB; } else if (LocationTools.contains(locB, locA)) { return locA; } if(LocationTools.overlaps(locA, locB)) { int min = Math.max(locA.getMin(), locB.getMin()); int max = Math.min(locA.getMax(), locB.getMax()); return makeLocation(min, max); } else { return Location.empty; } } else { // One or other of the locations is compound. Build a list of all // locations created by finding intersection of all pairwise combinations // of blocks in locA and locB. Ignore all Location.empty. Create the // appropriate Location instance. List locList = new ArrayList(); List blA = getBlockList(locA); { int minBlock = blockContainingOrFollowingPoint(blA, locB.getMin()); int maxBlock = blockContainingOrPreceedingPoint(blA, locB.getMax()); if (minBlock == -1 || maxBlock == -1) { return Location.empty; } blA = blA.subList(minBlock, maxBlock + 1); } List blB = getBlockList(locB); { int minBlock = blockContainingOrFollowingPoint(blB, locA.getMin()); int maxBlock = blockContainingOrPreceedingPoint(blB, locA.getMax()); if (minBlock == -1 || maxBlock == -1) { return Location.empty; } blB = blB.subList(minBlock, maxBlock + 1); } if (blA.size() > blB.size()) { List temp = blA; blA = blB; blB = temp; } for (Iterator i = blA.iterator(); i.hasNext(); ) { Location blocA = (Location) i.next(); int minHitIndex = blockContainingOrFollowingPoint(blB, blocA.getMin()); int maxHitIndex = blockContainingOrPreceedingPoint(blB, blocA.getMax()); for (int hitIndex = minHitIndex; hitIndex <= maxHitIndex; ++hitIndex) { Location blocB = (Location) blB.get(hitIndex); locList.add(LocationTools.intersection(blocA, blocB)); } } return buildLoc(locList); } } /** * Return an ordered list of non-overlapping blocks of a location * (singleton list for contiguous locations, empty list for empty locations) * * Note that from this point of view, contiguous circular locations * aren't necessarily contiguous :-(. * * @param l theLocation
to get the blocks from
* @return and ordered List
of Locations
*/
private static List getBlockList(Location l) {
if (l == Location.empty) {
return Collections.EMPTY_LIST;
} else if (l instanceof CompoundLocation) {
return ((CompoundLocation )l).getBlockList();
} else if (l.isContiguous() && !CircularLocationTools.isCircular(l)) {
return Collections.nCopies(1, l);
} else {
List bl = new ArrayList();
for (Iterator bi = l.blockIterator(); bi.hasNext(); ) {
bl.add(bi.next());
}
Collections.sort(bl, Location.naturalOrder);
return bl;
}
}
/**
* Return the index into bl
of a block containing
* point
, or -1 if it is not found.
*/
private static int blockContainingPoint(List bl, int point) {
int start = 0;
int end = bl.size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
Location block = (Location) bl.get(mid);
if (block.contains(point)) {
return mid;
} else if (point < block.getMin()) {
end = mid - 1;
} else if (point > block.getMax()) {
start = mid + 1;
} else {
throw new BioError("Assertion failed: overrun in binary search");
}
}
return -1;
}
/**
* Return the index of the block containing point
, if it exists,
* or the block preceeding it.
*/
private static int blockContainingOrPreceedingPoint(List bl, int point) {
// System.err.println("COPP");
int start = 0;
int length = bl.size();
int end = length - 1;
while (start <= end) {
int mid = (start + end) / 2;
// System.err.println("Start=" + start + " mid=" + mid + " end=" + end);
Location block = (Location) bl.get(mid);
if (block.contains(point)) {
return mid;
} else if (point < block.getMin()) {
end = mid - 1;
} else if (point > block.getMax()) {
start = mid + 1;
} else {
throw new BioError("Assertion failed: overrun in binary search");
}
}
if (end < length) {
return end;
} else {
return -1;
}
}
/**
* Return the index of the block containing point
, if it exists,
* or the block preceeding it.
*/
private static int blockContainingOrFollowingPoint(List bl, int point) {
// System.err.println("COFP");
int start = 0;
int length = bl.size();
int end = length - 1;
while (start <= end) {
int mid = (start + end) / 2;
// System.err.println("Start=" + start + " mid=" + mid + " end=" + end);
Location block = (Location) bl.get(mid);
if (block.contains(point)) {
return mid;
} else if (point < block.getMin()) {
end = mid - 1;
} else if (point > block.getMax()) {
start = mid + 1;
} else {
throw new BioError("Assertion failed: overrun in binary search");
}
}
if (start >= 0) {
return start;
} else {
return -1;
}
}
/**
* Determines whether the locations are touching or not (if they could be
* merged in a single Location.
* * Two locations can merge if they contain at least one index of one * beside one index of the other. *
* * @param locA the first Location * @param locB the second Location * @returntrue
if they can merge, false
otherwise
*/
public static boolean canMerge(Location locA, Location locB){
if (overlaps(locA, locB)||
overlaps(locA.translate(1), locB)||
overlaps(locA.translate(-1),locB))
return true;
return false;
}
/**
* Determines whether the locations overlap or not.
* * Two locations overlap if they contain at least one index in common. *
* * @param locA the first Location * @param locB the second Location * @returntrue
if they overlap, false
otherwise
*/
public static boolean overlaps(Location locA, Location locB) {
if(isDecorated(locA) || isDecorated(locB))
{
handleDecorations(locA, locB);
if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
{
return BetweenLocationTools.overlaps(locA, locB);
}
}
if(locA.isContiguous() && locB.isContiguous()) {
// if they are both solid, return whether the extents overlap
return !(
(locA.getMax() < locB.getMin()) ||
(locA.getMin() > locB.getMax())
);
} else {
// System.err.println("Doing complex overlap stuff");
List blA = getBlockList(locA);
{
// System.err.println("In A restriction");
int minBlock = blockContainingOrFollowingPoint(blA, locB.getMin());
int maxBlock = blockContainingOrPreceedingPoint(blA, locB.getMax());
if (minBlock == -1 || maxBlock == -1) {
// System.err.println("blA empty: minBlock=" + minBlock +", maxBlock=" + maxBlock);
return false;
}
blA = blA.subList(minBlock, maxBlock + 1);
}
List blB = getBlockList(locB);
{
// System.err.println("In B restriction");
int minBlock = blockContainingOrFollowingPoint(blB, locA.getMin());
int maxBlock = blockContainingOrPreceedingPoint(blB, locA.getMax());
if (minBlock == -1 || maxBlock == -1) {
// System.err.println("blB empty: minBlock=" + minBlock +", maxBlock=" + maxBlock);
return false;
}
blB = blB.subList(minBlock, maxBlock + 1);
}
// System.err.println("Restricted lists");
for(Iterator aI = blA.iterator(); aI.hasNext(); ) {
Location a = (Location) aI.next();
for(Iterator bI = blB.iterator(); bI.hasNext(); ) {
Location b = (Location) bI.next();
if(LocationTools.overlaps(a, b)) {
return true;
}
}
}
return false;
}
}
/**
* Return true
iff all indices in locB
are also contained
* by locA
.
*
* @param locA The containing location
* @param locB The contained location
* @return true
is locA contains locB
*/
public static boolean contains(Location locA, Location locB) {
if(isDecorated(locA) || isDecorated(locB))
{
handleDecorations(locA, locB);
if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
{
return BetweenLocationTools.contains(locA, locB);
}
}
if (locA.getMin() <= locB.getMin() && locA.getMax() >= locB.getMax()) {
if (locA.isContiguous()) {
return true;
} else {
List blA = getBlockList(locA);
for (Iterator biB = locB.blockIterator(); biB.hasNext(); ) {
Location bloc = (Location) biB.next();
int hitIndex = blockContainingPoint(blA, bloc.getMin());
if (hitIndex < 0) {
return false;
} else {
Location hitBloc = (Location) blA.get(hitIndex);
if (bloc.getMax() > hitBloc.getMax()) {
return false;
}
}
}
return true;
}
} else {
return false;
}
}
/**
* Return whether two locations are equal.
* * They are equal if both a contains b and b contains a. Equivalently, they * are equal if for every point p, locA.contains(p) == locB.contains(p). *
* * @param locA the first Location * @param locB the second Location * @return true if they are equivalent, false otherwise */ public static boolean areEqual(Location locA, Location locB) { if(isDecorated(locA) || isDecorated(locB)) { handleDecorations(locA, locB); if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB))) { return BetweenLocationTools.areEqual(locA, locB); } } // simple check - if one is broken and the other isn't, they aren't equal. if(locA.isContiguous() != locB.isContiguous()) { return false; } // both contiguous if one is - check extent only if(locA.isContiguous()) { return (locA.getMin() == locB.getMin()) && (locA.getMax() == locB.getMax()); } // ok - both compound. The blocks returned from blockIterator should each be // equivalent. Iterator i1 = locA.blockIterator(); Iterator i2 = locB.blockIterator(); // while there are more pairs to check... while(i1.hasNext() && i2.hasNext()) { // check that this pair is equivalent Location l1 = (Location) i1.next(); Location l2 = (Location) i2.next(); if( (l1.getMin() != l2.getMin()) || (l1.getMax() != l2.getMax()) ) { // not equivalent blocks so not equal return false; } } // One of the locations had more blocks than the other if(i1.hasNext() || i2.hasNext()) { return false; } // Same number of blocks, all equivalent. Must be equal. return true; } /** * Create a Location instance from the list of contiguous locations in * locList. *
* If the list is empty then Location.empty will be produced. If it is just
* one element long, then this will be returned as-is. If there are multiple
* locations then they will be sorted and then used to construct a
* CompoundLocation.
*
* @param locList a List
* If the list is empty then Location.empty will be produced. If it is just
* one element long, then this will be returned as-is. If there are multiple
* locations then they will be sorted and then used to construct a
* CompoundLocation.
*
* @param locList a List
* If min == max then a PointLocation will be made, otherwise, a RangeLocation
* will be returned.
*
* @param min the Location min value
* @param max the Location max value
* @return a new Location from min to max
*/
public static Location makeLocation(int min, int max) {
if(min == max) {
return new PointLocation(min);
} else {
return new RangeLocation(min, max);
}
}
/**
* A simple method to generate a RangeLocation wrapped
* in a CircularLocation. The method will cope with situtations
* where the min is greater than the max. Either of min or max can
* be negative, or greater than the underlying sequence length. If min and
* max are equal a wrapped point location will be made.
*
* @param min the "left" end of the location
* @param max the "right" end of the location
* @param seqLength the lenght of the sequence that the location will
* be applied to (for purposes of determining origin).
* @return the new It is very common in biological sequences to represent locations on a sequence and then reverse that
* sequence. This method allows locations in the original coordinate space to be transformed int
* locations in the reverse one.locs
*
* @param locs A collection of locations.
* @return A union location
* @throws ClassCastException if the collection contains non-Location objects.
*/
public static Location union(Collection locs) {
boolean circular = false;
List locList = new ArrayList();
for (Iterator li = locs.iterator(); li.hasNext(); ) {
Location loc = (Location) li.next();
if((loc instanceof CircularLocation)){
circular = true;
locList.add(loc);
}else{
for (Iterator bi = loc.blockIterator(); bi.hasNext(); ) {
locList.add(bi.next());
}
}
}
if(circular){
//need to add these one at a time
ListIterator li = locList.listIterator();
CircularLocation loc = (CircularLocation)li.next();
while(li.hasNext()){
loc = (CircularLocation)union(loc, (Location)li.next());
}
return loc;
}else{
return _union(locList);
}
}
static Location _union(List locList) {
// sort these blocks
Collections.sort(locList, Location.naturalOrder);
// merge into this list...
List joinList = new ArrayList();
// start iterating over sorted list.
// last is used as loop variable. We must be careful about zero lengthed
// lists and also careful to merge overlaps before adding to joinList.
Iterator i = locList.iterator();
Location last = Location.empty;
// prime last
if(i.hasNext()) {
last = (Location) i.next();
}
// merge or add last with next location
while(i.hasNext()) {
Location cur = (Location) i.next();
if(canMerge(last,cur)) {
try {
last = MergeLocation.mergeLocations(last,cur);
}
catch (BioException ex) {
throw new BioError("Cannot make MergeLocation",ex);
}
} else {
joinList.add(last);
last = cur;
}
}
// handle the end of the loop
if(last == Location.empty) {
return Location.empty;
} else {
joinList.add(last);
}
// now make the appropriate Location instance
return buildLocSorted(joinList);
}
/**
* Return a contiguous Location from min to max.
* CircularLocation
*/
public static CircularLocation makeCircularLocation(int min, int max, int seqLength){
return CircularLocationTools.makeCircLoc(min,max,seqLength);
}
/**
* Checks if the location has a decorator.
*
* @param theLocation The location to test for decorators
* @return True if the location has a decorator and false otherwise
*/
static boolean isDecorated(Location theLocation)
{
return (theLocation instanceof AbstractLocationDecorator);
}
/**
* Currently CircularLocations are handled if and only if
* CircularLocationTools.safeOperation returns true. For this to be true
* the locations must have the same sequence length.
*
* BetweenLocations are handled in all cases. Overlap cases, such as
* between, circular locations have indeterminate behavior.
*
* The default behavior is to not handle decorators. Any new decorators
* will have to re-visit this method
*/
private static void handleDecorations(Location locA, Location locB){
if(CircularLocationTools.isCircular(locA)|| CircularLocationTools.isCircular(locB)){
if(CircularLocationTools.safeOperation(locA, locB) == false){
throw new UnsupportedOperationException(
"Binary operations between Circular and"+
" Non-Circular locations, or CircularLocations"+
" from sequences of differing length are currently unsupported.");
}
}
else if(BetweenLocationTools.isBetween(locA) || (BetweenLocationTools.isBetween(locB)))
{
// Intentionally blank
}
else{
throw new ClassCastException("Decorated locations are not handled in this version: " + locA.getClass().getName() + ", " + locB.getClass().getName());
}
}
/**
* Flips a location relative to a length.
*
* keep
but not in
* remove
.
*
* @param keep A location
* @param remove A location
* @return a location containing all points which are in x but not y
* @since 1.3
*/
public static Location subtract(Location keep, Location remove) {
// fixme: documentation hack - I should re-factor this method
Location x = keep;
Location y = remove;
if (isDecorated(x) || isDecorated(y)) {
handleDecorations(x, y);
}
List spans = new ArrayList();
for (Iterator i = x.blockIterator(); i.hasNext(); ) {
Location xb = (Location) i.next();
Location yb = LocationTools.intersection(xb, y);
int pos = xb.getMin();
for (Iterator j = yb.blockIterator(); j.hasNext(); ) {
Location sb = (Location) j.next();
if (sb.getMin() > pos) {
spans.add(new RangeLocation(pos, sb.getMin() - 1));
}
pos = sb.getMax() + 1;
}
if (pos <= xb.getMax()) {
spans.add(new RangeLocation(pos, xb.getMax()));
}
}
return LocationTools.union(spans);
}
/**
* Return the number of positions which are covered by a Location
*
* @param loc A location
* @return the number of distinct points contained by that location
* @since 1.4
*/
public static int coverage(Location loc) {
int cov = 0;
for (Iterator i = loc.blockIterator(); i.hasNext(); ) {
Location bloc = (Location) i.next();
cov += (bloc.getMax() - bloc.getMin() + 1);
}
return cov;
}
/**
* Return a contiguous location running from the minimum to the maximum points of
* the specified location.
*
* @param loc a location
* @return a corresponding contiguous location
*/
public static Location shadow(Location loc) {
if (loc.isContiguous()) {
return loc;
} else {
return new RangeLocation(loc.getMin(), loc.getMax());
}
}
/**
* Return the number of contiguous blocks in a location.
*
* @param loc a location
* @return the number of blocks
* @since 1.4
*/
public static int blockCount(Location loc) {
if (loc.isContiguous()) {
if (loc instanceof EmptyLocation) {
return 0;
} else {
return 1;
}
} else {
int cnt = 0;
for (Iterator bi = loc.blockIterator(); bi.hasNext(); ) {
bi.next(); ++cnt;
}
return cnt;
}
}
}