X-Git-Url: http://source.jalview.org/gitweb/?p=jalview.git;a=blobdiff_plain;f=src%2Fjalview%2Futil%2FMappingUtils.java;h=6294ca132ae9ba1b8135bb08b206043e07a81ac1;hp=11597ebafc4ab5ca05db48d784e1cf69611a7664;hb=c17981672620e0b780a2338bd0c74e55cf9ddec2;hpb=a23ea387c12b87e15490f4a7f9afbdf34c232cf1 diff --git a/src/jalview/util/MappingUtils.java b/src/jalview/util/MappingUtils.java index 11597eb..6294ca1 100644 --- a/src/jalview/util/MappingUtils.java +++ b/src/jalview/util/MappingUtils.java @@ -20,31 +20,34 @@ */ package jalview.util; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map; + import jalview.analysis.AlignmentSorter; import jalview.api.AlignViewportI; +import jalview.bin.Cache; import jalview.commands.CommandI; import jalview.commands.EditCommand; import jalview.commands.EditCommand.Action; import jalview.commands.EditCommand.Edit; import jalview.commands.OrderCommand; import jalview.datamodel.AlignedCodonFrame; +import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping; import jalview.datamodel.AlignmentI; import jalview.datamodel.AlignmentOrder; import jalview.datamodel.ColumnSelection; +import jalview.datamodel.HiddenColumns; +import jalview.datamodel.SearchResultMatchI; import jalview.datamodel.SearchResults; -import jalview.datamodel.SearchResults.Match; +import jalview.datamodel.SearchResultsI; import jalview.datamodel.Sequence; import jalview.datamodel.SequenceGroup; import jalview.datamodel.SequenceI; -import java.util.ArrayList; -import java.util.Collections; -import java.util.HashMap; -import java.util.Iterator; -import java.util.List; -import java.util.Map; -import java.util.Set; - /** * Helper methods for manipulations involving sequence mappings. * @@ -69,7 +72,7 @@ public final class MappingUtils */ protected static void mapCutOrPaste(Edit edit, boolean undo, List targetSeqs, EditCommand result, - Set mappings) + List mappings) { Action action = edit.getAction(); if (undo) @@ -77,7 +80,7 @@ public final class MappingUtils action = action.getUndoAction(); } // TODO write this - System.err.println("MappingUtils.mapCutOrPaste not yet implemented"); + Cache.log.error("MappingUtils.mapCutOrPaste not yet implemented"); } /** @@ -93,7 +96,7 @@ public final class MappingUtils */ public static EditCommand mapEditCommand(EditCommand command, boolean undo, final AlignmentI mapTo, char gapChar, - Set mappings) + List mappings) { /* * For now, only support mapping from protein edits to cDna @@ -107,7 +110,7 @@ public final class MappingUtils * Cache a copy of the target sequences so we can mimic successive edits on * them. This lets us compute mappings for all edits in the set. */ - Map targetCopies = new HashMap(); + Map targetCopies = new HashMap<>(); for (SequenceI seq : mapTo.getSequences()) { SequenceI ds = seq.getDatasetSequence(); @@ -165,7 +168,7 @@ public final class MappingUtils Map originalSequences, final List targetSeqs, Map targetCopies, char gapChar, - EditCommand result, Set mappings) + EditCommand result, List mappings) { Action action = edit.getAction(); @@ -195,7 +198,7 @@ public final class MappingUtils /* * Determine all mappings from this position to mapped sequences. */ - SearchResults sr = buildSearchResults(seq, seqpos, mappings); + SearchResultsI sr = buildSearchResults(seq, seqpos, mappings); if (!sr.isEmpty()) { @@ -218,8 +221,9 @@ public final class MappingUtils * Shift Delete start position left, as it acts on positions to its * right. */ - int mappedEditPos = action == Action.DELETE_GAP ? match[0] - - mappedCount : match[0]; + int mappedEditPos = action == Action.DELETE_GAP + ? match[0] - mappedCount + : match[0]; Edit e = result.new Edit(action, new SequenceI[] { targetSeq }, mappedEditPos, mappedCount, gapChar); result.addEdit(e); @@ -229,15 +233,15 @@ public final class MappingUtils */ if (action == Action.INSERT_GAP) { - copyTarget.setSequence(new String(StringUtils.insertCharAt( - copyTarget.getSequence(), mappedEditPos, mappedCount, - gapChar))); + copyTarget.setSequence(new String( + StringUtils.insertCharAt(copyTarget.getSequence(), + mappedEditPos, mappedCount, gapChar))); } else if (action == Action.DELETE_GAP) { - copyTarget.setSequence(new String(StringUtils.deleteChars( - copyTarget.getSequence(), mappedEditPos, - mappedEditPos + mappedCount))); + copyTarget.setSequence(new String( + StringUtils.deleteChars(copyTarget.getSequence(), + mappedEditPos, mappedEditPos + mappedCount))); } } } @@ -267,10 +271,10 @@ public final class MappingUtils * @param seqmappings * @return */ - public static SearchResults buildSearchResults(SequenceI seq, int index, - Set seqmappings) + public static SearchResultsI buildSearchResults(SequenceI seq, int index, + List seqmappings) { - SearchResults results = new SearchResults(); + SearchResultsI results = new SearchResults(); addSearchResults(results, seq, index, seqmappings); return results; } @@ -284,8 +288,8 @@ public final class MappingUtils * @param index * @param seqmappings */ - public static void addSearchResults(SearchResults results, SequenceI seq, - int index, Set seqmappings) + public static void addSearchResults(SearchResultsI results, SequenceI seq, + int index, List seqmappings) { if (index >= seq.getStart() && index <= seq.getEnd()) { @@ -314,13 +318,13 @@ public final class MappingUtils */ boolean targetIsNucleotide = mapTo.isNucleotide(); AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo; - Set codonFrames = protein.getAlignment() + List codonFrames = protein.getAlignment() .getCodonFrames(); /* * Copy group name, colours etc, but not sequences or sequence colour scheme */ SequenceGroup mappedGroup = new SequenceGroup(sg); - mappedGroup.cs = mapTo.getGlobalColourScheme(); + mappedGroup.setColourScheme(mapTo.getGlobalColourScheme()); mappedGroup.clear(); int minStartCol = -1; @@ -362,49 +366,45 @@ public final class MappingUtils for (AlignedCodonFrame acf : codonFrames) { - SequenceI mappedSequence = targetIsNucleotide ? acf - .getDnaForAaSeq(selected) : acf.getAaForDnaSeq(selected); - if (mappedSequence != null) + for (SequenceI seq : mapTo.getAlignment().getSequences()) { - for (SequenceI seq : mapTo.getAlignment().getSequences()) + SequenceI peptide = targetIsNucleotide ? selected : seq; + SequenceI cds = targetIsNucleotide ? seq : selected; + SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds, + peptide); + if (s2s == null) { - int mappedStartResidue = 0; - int mappedEndResidue = 0; - if (seq.getDatasetSequence() == mappedSequence) - { - /* - * Found a sequence mapping. Locate the start/end mapped residues. - */ - SearchResults sr = buildSearchResults(selected, - startResiduePos, Collections.singleton(acf)); - for (Match m : sr.getResults()) - { - mappedStartResidue = m.getStart(); - mappedEndResidue = m.getEnd(); - } - sr = buildSearchResults(selected, endResiduePos, - Collections.singleton(acf)); - for (Match m : sr.getResults()) - { - mappedStartResidue = Math.min(mappedStartResidue, - m.getStart()); - mappedEndResidue = Math.max(mappedEndResidue, m.getEnd()); - } - - /* - * Find the mapped aligned columns, save the range. Note findIndex - * returns a base 1 position, SequenceGroup uses base 0 - */ - int mappedStartCol = seq.findIndex(mappedStartResidue) - 1; - minStartCol = minStartCol == -1 ? mappedStartCol : Math.min( - minStartCol, mappedStartCol); - int mappedEndCol = seq.findIndex(mappedEndResidue) - 1; - maxEndCol = maxEndCol == -1 ? mappedEndCol : Math.max( - maxEndCol, mappedEndCol); - mappedGroup.addSequence(seq, false); - break; - } + continue; } + int mappedStartResidue = 0; + int mappedEndResidue = 0; + List mapping = Arrays.asList(acf); + SearchResultsI sr = buildSearchResults(selected, startResiduePos, + mapping); + for (SearchResultMatchI m : sr.getResults()) + { + mappedStartResidue = m.getStart(); + mappedEndResidue = m.getEnd(); + } + sr = buildSearchResults(selected, endResiduePos, mapping); + for (SearchResultMatchI m : sr.getResults()) + { + mappedStartResidue = Math.min(mappedStartResidue, m.getStart()); + mappedEndResidue = Math.max(mappedEndResidue, m.getEnd()); + } + + /* + * Find the mapped aligned columns, save the range. Note findIndex + * returns a base 1 position, SequenceGroup uses base 0 + */ + int mappedStartCol = seq.findIndex(mappedStartResidue) - 1; + minStartCol = minStartCol == -1 ? mappedStartCol + : Math.min(minStartCol, mappedStartCol); + int mappedEndCol = seq.findIndex(mappedEndResidue) - 1; + maxEndCol = maxEndCol == -1 ? mappedEndCol + : Math.max(maxEndCol, mappedEndCol); + mappedGroup.addSequence(seq, false); + break; } } } @@ -427,11 +427,11 @@ public final class MappingUtils * the mappings available * @return */ - public static CommandI mapOrderCommand(OrderCommand command, - boolean undo, AlignmentI mapTo, Set mappings) + public static CommandI mapOrderCommand(OrderCommand command, boolean undo, + AlignmentI mapTo, List mappings) { SequenceI[] sortOrder = command.getSequenceOrder(undo); - List mappedOrder = new ArrayList(); + List mappedOrder = new ArrayList<>(); int j = 0; /* @@ -444,20 +444,23 @@ public final class MappingUtils { for (AlignedCodonFrame acf : mappings) { - SequenceI mappedSeq = mappingToNucleotide ? acf.getDnaForAaSeq(seq) - : acf.getAaForDnaSeq(seq); - if (mappedSeq != null) - { for (SequenceI seq2 : mapTo.getSequences()) { - if (seq2.getDatasetSequence() == mappedSeq) + /* + * the corresponding peptide / CDS is the one for which there is + * a complete ('covering') mapping to 'seq' + */ + SequenceI peptide = mappingToNucleotide ? seq2 : seq; + SequenceI cds = mappingToNucleotide ? seq : seq2; + SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds, + peptide); + if (s2s != null) { mappedOrder.add(seq2); j++; break; } } - } } } @@ -507,95 +510,181 @@ public final class MappingUtils * @param mapTo * @return */ - public static ColumnSelection mapColumnSelection(ColumnSelection colsel, - AlignViewportI mapFrom, AlignViewportI mapTo) + public static void mapColumnSelection(ColumnSelection colsel, + HiddenColumns hiddencols, AlignViewportI mapFrom, + AlignViewportI mapTo, ColumnSelection newColSel, + HiddenColumns newHidden) { boolean targetIsNucleotide = mapTo.isNucleotide(); AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo; - Set codonFrames = protein.getAlignment() + List codonFrames = protein.getAlignment() .getCodonFrames(); - ColumnSelection mappedColumns = new ColumnSelection(); if (colsel == null) { - return mappedColumns; + return; } char fromGapChar = mapFrom.getAlignment().getGapCharacter(); - // FIXME allow for hidden columns - /* * For each mapped column, find the range of columns that residues in that * column map to. */ - for (Object obj : colsel.getSelected()) + List fromSequences = mapFrom.getAlignment().getSequences(); + List toSequences = mapTo.getAlignment().getSequences(); + + for (Integer sel : colsel.getSelected()) { - int col = ((Integer) obj).intValue(); - int mappedToMin = Integer.MAX_VALUE; - int mappedToMax = Integer.MIN_VALUE; + mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences, + toSequences, fromGapChar); + } + + Iterator regions = hiddencols.iterator(); + while (regions.hasNext()) + { + mapHiddenColumns(regions.next(), codonFrames, newHidden, + fromSequences, toSequences, fromGapChar); + } + return; + } + + /** + * Helper method that maps a [start, end] hidden column range to its mapped + * equivalent + * + * @param hidden + * @param mappings + * @param mappedColumns + * @param fromSequences + * @param toSequences + * @param fromGapChar + */ + protected static void mapHiddenColumns(int[] hidden, + List mappings, HiddenColumns mappedColumns, + List fromSequences, List toSequences, + char fromGapChar) + { + for (int col = hidden[0]; col <= hidden[1]; col++) + { + int[] mappedTo = findMappedColumns(col, mappings, fromSequences, + toSequences, fromGapChar); /* - * For each sequence in the 'from' alignment + * Add the range of hidden columns to the mapped selection (converting + * base 1 to base 0). */ - for (SequenceI fromSeq : mapFrom.getAlignment().getSequences()) + if (mappedTo != null) { - /* - * Ignore gaps (unmapped anyway) - */ - if (fromSeq.getCharAt(col) == fromGapChar) - { - continue; - } + mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1); + } + } + } + + /** + * Helper method to map one column selection + * + * @param col + * the column number (base 0) + * @param mappings + * the sequence mappings + * @param mappedColumns + * the mapped column selections to add to + * @param fromSequences + * @param toSequences + * @param fromGapChar + */ + protected static void mapColumn(int col, List mappings, + ColumnSelection mappedColumns, List fromSequences, + List toSequences, char fromGapChar) + { + int[] mappedTo = findMappedColumns(col, mappings, fromSequences, + toSequences, fromGapChar); + + /* + * Add the range of mapped columns to the mapped selection (converting + * base 1 to base 0). Note that this may include intron-only regions which + * lie between the start and end ranges of the selection. + */ + if (mappedTo != null) + { + for (int i = mappedTo[0]; i <= mappedTo[1]; i++) + { + mappedColumns.addElement(i - 1); + } + } + } + + /** + * Helper method to find the range of columns mapped to from one column. + * Returns the maximal range of columns mapped to from all sequences in the + * source column, or null if no mappings were found. + * + * @param col + * @param mappings + * @param fromSequences + * @param toSequences + * @param fromGapChar + * @return + */ + protected static int[] findMappedColumns(int col, + List mappings, List fromSequences, + List toSequences, char fromGapChar) + { + int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE }; + boolean found = false; + + /* + * For each sequence in the 'from' alignment + */ + for (SequenceI fromSeq : fromSequences) + { + /* + * Ignore gaps (unmapped anyway) + */ + if (fromSeq.getCharAt(col) == fromGapChar) + { + continue; + } + + /* + * Get the residue position and find the mapped position. + */ + int residuePos = fromSeq.findPosition(col); + SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings); + for (SearchResultMatchI m : sr.getResults()) + { + int mappedStartResidue = m.getStart(); + int mappedEndResidue = m.getEnd(); + SequenceI mappedSeq = m.getSequence(); /* - * Get the residue position and find the mapped position. + * Locate the aligned sequence whose dataset is mappedSeq. TODO a + * datamodel that can do this efficiently. */ - int residuePos = fromSeq.findPosition(col); - SearchResults sr = buildSearchResults(fromSeq, residuePos, - codonFrames); - for (Match m : sr.getResults()) + for (SequenceI toSeq : toSequences) { - int mappedStartResidue = m.getStart(); - int mappedEndResidue = m.getEnd(); - SequenceI mappedSeq = m.getSequence(); - - /* - * Locate the aligned sequence whose dataset is mappedSeq. TODO a - * datamodel that can do this efficiently. - */ - for (SequenceI toSeq : mapTo.getAlignment().getSequences()) + if (toSeq.getDatasetSequence() == mappedSeq + && mappedStartResidue >= toSeq.getStart() + && mappedEndResidue <= toSeq.getEnd()) { - if (toSeq.getDatasetSequence() == mappedSeq) - { - int mappedStartCol = toSeq.findIndex(mappedStartResidue); - int mappedEndCol = toSeq.findIndex(mappedEndResidue); - mappedToMin = Math.min(mappedToMin, mappedStartCol); - mappedToMax = Math.max(mappedToMax, mappedEndCol); - // System.out.println(fromSeq.getName() + " mapped to cols " - // + mappedStartCol + ":" + mappedEndCol); - break; - // note: remove break if we ever want to map one to many sequences - } + int mappedStartCol = toSeq.findIndex(mappedStartResidue); + int mappedEndCol = toSeq.findIndex(mappedEndResidue); + mappedTo[0] = Math.min(mappedTo[0], mappedStartCol); + mappedTo[1] = Math.max(mappedTo[1], mappedEndCol); + found = true; + break; + // note: remove break if we ever want to map one to many sequences } } } - /* - * Add the range of mapped columns to the mapped selection (converting - * base 1 to base 0). Note that this may include intron-only regions which - * lie between the start and end ranges of the selection. - */ - for (int i = mappedToMin; i <= mappedToMax; i++) - { - mappedColumns.addElement(i - 1); - } } - return mappedColumns; + return found ? mappedTo : null; } /** - * Returns the mapped codon for a given aligned sequence column position (base - * 0). + * Returns the mapped codon or codons for a given aligned sequence column + * position (base 0). * * @param seq * an aligned peptide sequence @@ -603,21 +692,27 @@ public final class MappingUtils * an aligned column position (base 0) * @param mappings * a set of codon mappings - * @return the bases of the mapped codon in the cDNA dataset sequence, or null - * if not found + * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s), + * or an empty list if none found */ - public static char[] findCodonFor(SequenceI seq, int col, - Set mappings) + public static List findCodonsFor(SequenceI seq, int col, + List mappings) { + List result = new ArrayList<>(); int dsPos = seq.findPosition(col); for (AlignedCodonFrame mapping : mappings) { if (mapping.involvesSequence(seq)) { - return mapping.getMappedCodon(seq.getDatasetSequence(), dsPos); + List codons = mapping + .getMappedCodons(seq.getDatasetSequence(), dsPos); + if (codons != null) + { + result.addAll(codons); + } } } - return null; + return result; } /** @@ -663,9 +758,26 @@ public final class MappingUtils * @return */ public static List findMappingsForSequence( - SequenceI sequence, Set mappings) + SequenceI sequence, List mappings) + { + return findMappingsForSequenceAndOthers(sequence, mappings, null); + } + + /** + * Returns a list of any mappings that are from or to the given (aligned or + * dataset) sequence, optionally limited to mappings involving one of a given + * list of sequences. + * + * @param sequence + * @param mappings + * @param filterList + * @return + */ + public static List findMappingsForSequenceAndOthers( + SequenceI sequence, List mappings, + List filterList) { - List result = new ArrayList(); + List result = new ArrayList<>(); if (sequence == null || mappings == null) { return result; @@ -674,9 +786,317 @@ public final class MappingUtils { if (mapping.involvesSequence(sequence)) { - result.add(mapping); + if (filterList != null) + { + for (SequenceI otherseq : filterList) + { + SequenceI otherDataset = otherseq.getDatasetSequence(); + if (otherseq == sequence + || otherseq == sequence.getDatasetSequence() + || (otherDataset != null && (otherDataset == sequence + || otherDataset == sequence + .getDatasetSequence()))) + { + // skip sequences in subset which directly relate to sequence + continue; + } + if (mapping.involvesSequence(otherseq)) + { + // selected a mapping contained in subselect alignment + result.add(mapping); + break; + } + } + } + else + { + result.add(mapping); + } } } return result; } + + /** + * Returns the total length of the supplied ranges, which may be as single + * [start, end] or multiple [start, end, start, end ...] + * + * @param ranges + * @return + */ + public static int getLength(List ranges) + { + if (ranges == null) + { + return 0; + } + int length = 0; + for (int[] range : ranges) + { + if (range.length % 2 != 0) + { + Cache.log.error( + "Error unbalance start/end ranges: " + ranges.toString()); + return 0; + } + for (int i = 0; i < range.length - 1; i += 2) + { + length += Math.abs(range[i + 1] - range[i]) + 1; + } + } + return length; + } + + /** + * Answers true if any range includes the given value + * + * @param ranges + * @param value + * @return + */ + public static boolean contains(List ranges, int value) + { + if (ranges == null) + { + return false; + } + for (int[] range : ranges) + { + if (range[1] >= range[0] && value >= range[0] && value <= range[1]) + { + /* + * value within ascending range + */ + return true; + } + if (range[1] < range[0] && value <= range[0] && value >= range[1]) + { + /* + * value within descending range + */ + return true; + } + } + return false; + } + + /** + * Removes a specified number of positions from the start of a ranges list. + * For example, could be used to adjust cds ranges to allow for an incomplete + * start codon. Subranges are removed completely, or their start positions + * adjusted, until the required number of positions has been removed from the + * range. Reverse strand ranges are supported. The input array is not + * modified. + * + * @param removeCount + * @param ranges + * an array of [start, end, start, end...] positions + * @return a new array with the first removeCount positions removed + */ + public static int[] removeStartPositions(int removeCount, + final int[] ranges) + { + if (removeCount <= 0) + { + return ranges; + } + + int[] copy = Arrays.copyOf(ranges, ranges.length); + int sxpos = -1; + int cdspos = 0; + for (int x = 0; x < copy.length && sxpos == -1; x += 2) + { + cdspos += Math.abs(copy[x + 1] - copy[x]) + 1; + if (removeCount < cdspos) + { + /* + * we have removed enough, time to finish + */ + sxpos = x; + + /* + * increment start of first exon, or decrement if reverse strand + */ + if (copy[x] <= copy[x + 1]) + { + copy[x] = copy[x + 1] - cdspos + removeCount + 1; + } + else + { + copy[x] = copy[x + 1] + cdspos - removeCount - 1; + } + break; + } + } + + if (sxpos > 0) + { + /* + * we dropped at least one entire sub-range - compact the array + */ + int[] nxon = new int[copy.length - sxpos]; + System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos); + return nxon; + } + return copy; + } + + /** + * Answers true if range's start-end positions include those of queryRange, + * where either range might be in reverse direction, else false + * + * @param range + * a start-end range + * @param queryRange + * a candidate subrange of range (start2-end2) + * @return + */ + public static boolean rangeContains(int[] range, int[] queryRange) + { + if (range == null || queryRange == null || range.length != 2 + || queryRange.length != 2) + { + /* + * invalid arguments + */ + return false; + } + + int min = Math.min(range[0], range[1]); + int max = Math.max(range[0], range[1]); + + return (min <= queryRange[0] && max >= queryRange[0] + && min <= queryRange[1] && max >= queryRange[1]); + } + + /** + * Removes the specified number of positions from the given ranges. Provided + * to allow a stop codon to be stripped from a CDS sequence so that it matches + * the peptide translation length. + * + * @param positions + * @param ranges + * a list of (single) [start, end] ranges + * @return + */ + public static void removeEndPositions(int positions, List ranges) + { + int toRemove = positions; + Iterator it = new ReverseListIterator<>(ranges); + while (toRemove > 0) + { + int[] endRange = it.next(); + if (endRange.length != 2) + { + /* + * not coded for [start1, end1, start2, end2, ...] + */ + Cache.log.error( + "MappingUtils.removeEndPositions doesn't handle multiple ranges"); + return; + } + + int length = endRange[1] - endRange[0] + 1; + if (length <= 0) + { + /* + * not coded for a reverse strand range (end < start) + */ + Cache.log.error( + "MappingUtils.removeEndPositions doesn't handle reverse strand"); + return; + } + if (length > toRemove) + { + endRange[1] -= toRemove; + toRemove = 0; + } + else + { + toRemove -= length; + it.remove(); + } + } + } + + /** + * Converts a list of [start, end] ranges to a single array of [start, end, + * start, end ...] + * + * @param ranges + * @return + */ + public static int[] listToArray(List ranges) + { + int[] result = new int[ranges.size() * 2]; + int i = 0; + for (int[] range : ranges) + { + result[i++] = range[0]; + result[i++] = range[1]; + } + return result; + } + + /** + * Returns the maximal start-end positions in the given (ordered) list of + * ranges which is overlapped by the given begin-end range, or null if there + * is no overlap. + * + * 
+   * Examples:
+   *   if ranges is {[4, 8], [10, 12], [16, 19]}
+   * then
+   *   findOverlap(ranges, 1, 20) == [4, 19]
+   *   findOverlap(ranges, 6, 11) == [6, 11]
+   *   findOverlap(ranges, 9, 15) == [10, 12]
+   *   findOverlap(ranges, 13, 15) == null
+   *
+ * + * @param ranges + * @param begin + * @param end + * @return + */ + protected static int[] findOverlap(List ranges, final int begin, + final int end) + { + boolean foundStart = false; + int from = 0; + int to = 0; + + /* + * traverse the ranges to find the first position (if any) >= begin, + * and the last position (if any) <= end + */ + for (int[] range : ranges) + { + if (!foundStart) + { + if (range[0] >= begin) + { + /* + * first range that starts with, or follows, begin + */ + foundStart = true; + from = Math.max(range[0], begin); + } + else if (range[1] >= begin) + { + /* + * first range that contains begin + */ + foundStart = true; + from = begin; + } + } + + if (range[0] <= end) + { + to = Math.min(end, range[1]); + } + } + + return foundStart && to >= from ? new int[] { from, to } : null; + } }