2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
7 * Jalview is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation, either version 3
10 * of the License, or (at your option) any later version.
12 * Jalview is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty
14 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19 * The Jalview Authors are detailed in the 'AUTHORS' file.
23 import java.util.ArrayList;
24 import java.util.Arrays;
25 import java.util.HashMap;
26 import java.util.Iterator;
27 import java.util.List;
30 import jalview.analysis.AlignmentSorter;
31 import jalview.api.AlignViewportI;
32 import jalview.bin.Console;
33 import jalview.commands.CommandI;
34 import jalview.commands.EditCommand;
35 import jalview.commands.EditCommand.Action;
36 import jalview.commands.EditCommand.Edit;
37 import jalview.commands.OrderCommand;
38 import jalview.datamodel.AlignedCodonFrame;
39 import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping;
40 import jalview.datamodel.AlignmentI;
41 import jalview.datamodel.AlignmentOrder;
42 import jalview.datamodel.ColumnSelection;
43 import jalview.datamodel.HiddenColumns;
44 import jalview.datamodel.Mapping;
45 import jalview.datamodel.SearchResultMatchI;
46 import jalview.datamodel.SearchResults;
47 import jalview.datamodel.SearchResultsI;
48 import jalview.datamodel.Sequence;
49 import jalview.datamodel.SequenceGroup;
50 import jalview.datamodel.SequenceI;
53 * Helper methods for manipulations involving sequence mappings.
58 public final class MappingUtils
62 * Helper method to map a CUT or PASTE command.
65 * the original command
67 * if true, the command is to be undone
69 * the mapped sequences to apply the mapped command to
71 * the mapped EditCommand to add to
74 protected static void mapCutOrPaste(Edit edit, boolean undo,
75 List<SequenceI> targetSeqs, EditCommand result,
76 List<AlignedCodonFrame> mappings)
78 Action action = edit.getAction();
81 action = action.getUndoAction();
84 Console.error("MappingUtils.mapCutOrPaste not yet implemented");
88 * Returns a new EditCommand representing the given command as mapped to the
89 * given sequences. If there is no mapping, returns null.
98 public static EditCommand mapEditCommand(EditCommand command,
99 boolean undo, final AlignmentI mapTo, char gapChar,
100 List<AlignedCodonFrame> mappings)
103 * For now, only support mapping from protein edits to cDna
105 if (!mapTo.isNucleotide())
111 * Cache a copy of the target sequences so we can mimic successive edits on
112 * them. This lets us compute mappings for all edits in the set.
114 Map<SequenceI, SequenceI> targetCopies = new HashMap<>();
115 for (SequenceI seq : mapTo.getSequences())
117 SequenceI ds = seq.getDatasetSequence();
120 final SequenceI copy = new Sequence(seq);
121 copy.setDatasetSequence(ds);
122 targetCopies.put(ds, copy);
127 * Compute 'source' sequences as they were before applying edits:
129 Map<SequenceI, SequenceI> originalSequences = command.priorState(undo);
131 EditCommand result = new EditCommand();
132 Iterator<Edit> edits = command.getEditIterator(!undo);
133 while (edits.hasNext())
135 Edit edit = edits.next();
136 if (edit.getAction() == Action.CUT
137 || edit.getAction() == Action.PASTE)
139 mapCutOrPaste(edit, undo, mapTo.getSequences(), result, mappings);
141 else if (edit.getAction() == Action.INSERT_GAP
142 || edit.getAction() == Action.DELETE_GAP)
144 mapInsertOrDelete(edit, undo, originalSequences,
145 mapTo.getSequences(), targetCopies, gapChar, result,
149 return result.getSize() > 0 ? result : null;
153 * Helper method to map an edit command to insert or delete gaps.
156 * the original command
158 * if true, the action is to undo the command
159 * @param originalSequences
160 * the sequences the command acted on
162 * @param targetCopies
165 * the new EditCommand to add mapped commands to
168 protected static void mapInsertOrDelete(Edit edit, boolean undo,
169 Map<SequenceI, SequenceI> originalSequences,
170 final List<SequenceI> targetSeqs,
171 Map<SequenceI, SequenceI> targetCopies, char gapChar,
172 EditCommand result, List<AlignedCodonFrame> mappings)
174 Action action = edit.getAction();
177 * Invert sense of action if an Undo.
181 action = action.getUndoAction();
183 final int count = edit.getNumber();
184 final int editPos = edit.getPosition();
185 for (SequenceI seq : edit.getSequences())
188 * Get residue position at (or to right of) edit location. Note we use our
189 * 'copy' of the sequence before editing for this.
191 SequenceI ds = seq.getDatasetSequence();
196 final SequenceI actedOn = originalSequences.get(ds);
197 final int seqpos = actedOn.findPosition(editPos);
200 * Determine all mappings from this position to mapped sequences.
202 SearchResultsI sr = buildSearchResults(seq, seqpos, mappings);
206 for (SequenceI targetSeq : targetSeqs)
208 ds = targetSeq.getDatasetSequence();
213 SequenceI copyTarget = targetCopies.get(ds);
214 final int[] match = sr.getResults(copyTarget, 0,
215 copyTarget.getLength());
218 final int ratio = 3; // TODO: compute this - how?
219 final int mappedCount = count * ratio;
222 * Shift Delete start position left, as it acts on positions to its
225 int mappedEditPos = action == Action.DELETE_GAP
226 ? match[0] - mappedCount
228 Edit e = result.new Edit(action, new SequenceI[] { targetSeq },
229 mappedEditPos, mappedCount, gapChar);
233 * and 'apply' the edit to our copy of its target sequence
235 if (action == Action.INSERT_GAP)
237 copyTarget.setSequence(new String(
238 StringUtils.insertCharAt(copyTarget.getSequence(),
239 mappedEditPos, mappedCount, gapChar)));
241 else if (action == Action.DELETE_GAP)
243 copyTarget.setSequence(new String(
244 StringUtils.deleteChars(copyTarget.getSequence(),
245 mappedEditPos, mappedEditPos + mappedCount)));
251 * and 'apply' the edit to our copy of its source sequence
253 if (action == Action.INSERT_GAP)
255 actedOn.setSequence(new String(StringUtils.insertCharAt(
256 actedOn.getSequence(), editPos, count, gapChar)));
258 else if (action == Action.DELETE_GAP)
260 actedOn.setSequence(new String(StringUtils.deleteChars(
261 actedOn.getSequence(), editPos, editPos + count)));
267 * Returns a SearchResults object describing the mapped region corresponding
268 * to the specified sequence position.
275 public static SearchResultsI buildSearchResults(SequenceI seq, int index,
276 List<AlignedCodonFrame> seqmappings)
278 SearchResultsI results = new SearchResults();
279 addSearchResults(results, seq, index, seqmappings);
284 * Adds entries to a SearchResults object describing the mapped region
285 * corresponding to the specified sequence position.
292 public static void addSearchResults(SearchResultsI results, SequenceI seq,
293 int index, List<AlignedCodonFrame> seqmappings)
295 if (index >= seq.getStart() && index <= seq.getEnd())
297 for (AlignedCodonFrame acf : seqmappings)
299 acf.markMappedRegion(seq, index, results);
305 * Returns a (possibly empty) SequenceGroup containing any sequences in the
306 * mapped viewport corresponding to the given group in the source viewport.
313 public static SequenceGroup mapSequenceGroup(final SequenceGroup sg,
314 final AlignViewportI mapFrom, final AlignViewportI mapTo)
317 * Note the SequenceGroup holds aligned sequences, the mappings hold dataset
320 boolean targetIsNucleotide = mapTo.isNucleotide();
321 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
322 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
325 * Copy group name, colours etc, but not sequences or sequence colour scheme
327 SequenceGroup mappedGroup = new SequenceGroup(sg);
328 mappedGroup.setColourScheme(mapTo.getGlobalColourScheme());
331 int minStartCol = -1;
333 final int selectionStartRes = sg.getStartRes();
334 final int selectionEndRes = sg.getEndRes();
335 for (SequenceI selected : sg.getSequences())
338 * Find the widest range of non-gapped positions in the selection range
340 int firstUngappedPos = selectionStartRes;
341 while (firstUngappedPos <= selectionEndRes
342 && Comparison.isGap(selected.getCharAt(firstUngappedPos)))
348 * If this sequence is only gaps in the selected range, skip it
350 if (firstUngappedPos > selectionEndRes)
355 int lastUngappedPos = selectionEndRes;
356 while (lastUngappedPos >= selectionStartRes
357 && Comparison.isGap(selected.getCharAt(lastUngappedPos)))
363 * Find the selected start/end residue positions in sequence
365 int startResiduePos = selected.findPosition(firstUngappedPos);
366 int endResiduePos = selected.findPosition(lastUngappedPos);
367 for (SequenceI seq : mapTo.getAlignment().getSequences())
369 int mappedStartResidue = 0;
370 int mappedEndResidue = 0;
371 for (AlignedCodonFrame acf : codonFrames)
373 // rather than use acf.getCoveringMapping() we iterate through all
374 // mappings to make sure all CDS are selected for a protein
375 for (SequenceToSequenceMapping map: acf.getMappings())
377 if (map.covers(selected) && map.covers(seq))
380 * Found a sequence mapping. Locate the start/end mapped residues.
382 List<AlignedCodonFrame> mapping = Arrays
383 .asList(new AlignedCodonFrame[]
386 SearchResultsI sr = buildSearchResults(selected,
387 startResiduePos, mapping);
388 for (SearchResultMatchI m : sr.getResults())
390 mappedStartResidue = m.getStart();
391 mappedEndResidue = m.getEnd();
393 // locate end - allowing for adjustment of start range
394 sr = buildSearchResults(selected, endResiduePos, mapping);
395 for (SearchResultMatchI m : sr.getResults())
397 mappedStartResidue = Math.min(mappedStartResidue,
399 mappedEndResidue = Math.max(mappedEndResidue, m.getEnd());
403 * Find the mapped aligned columns, save the range. Note findIndex
404 * returns a base 1 position, SequenceGroup uses base 0
406 int mappedStartCol = seq.findIndex(mappedStartResidue) - 1;
407 minStartCol = minStartCol == -1 ? mappedStartCol
408 : Math.min(minStartCol, mappedStartCol);
409 int mappedEndCol = seq.findIndex(mappedEndResidue) - 1;
410 maxEndCol = maxEndCol == -1 ? mappedEndCol
411 : Math.max(maxEndCol, mappedEndCol);
412 mappedGroup.addSequence(seq, false);
418 mappedGroup.setStartRes(minStartCol < 0 ? 0 : minStartCol);
419 mappedGroup.setEndRes(maxEndCol < 0 ? 0 : maxEndCol);
424 * Returns an OrderCommand equivalent to the given one, but acting on mapped
425 * sequences as described by the mappings, or null if no mapping can be made.
428 * the original order command
430 * if true, the action is to undo the sort
432 * the alignment we are mapping to
434 * the mappings available
437 public static CommandI mapOrderCommand(OrderCommand command, boolean undo,
438 AlignmentI mapTo, List<AlignedCodonFrame> mappings)
440 SequenceI[] sortOrder = command.getSequenceOrder(undo);
441 List<SequenceI> mappedOrder = new ArrayList<>();
445 * Assumption: we are only interested in a cDNA/protein mapping; refactor in
446 * future if we want to support sorting (c)dna as (c)dna or protein as
449 boolean mappingToNucleotide = mapTo.isNucleotide();
450 for (SequenceI seq : sortOrder)
452 for (AlignedCodonFrame acf : mappings)
454 for (SequenceI seq2 : mapTo.getSequences())
457 * the corresponding peptide / CDS is the one for which there is
458 * a complete ('covering') mapping to 'seq'
460 SequenceI peptide = mappingToNucleotide ? seq2 : seq;
461 SequenceI cds = mappingToNucleotide ? seq : seq2;
462 SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds,
466 mappedOrder.add(seq2);
475 * Return null if no mappings made.
483 * Add any unmapped sequences on the end of the sort in their original
486 if (j < mapTo.getHeight())
488 for (SequenceI seq : mapTo.getSequences())
490 if (!mappedOrder.contains(seq))
492 mappedOrder.add(seq);
498 * Have to sort the sequences before constructing the OrderCommand - which
499 * then resorts them?!?
501 final SequenceI[] mappedOrderArray = mappedOrder
502 .toArray(new SequenceI[mappedOrder.size()]);
503 SequenceI[] oldOrder = mapTo.getSequencesArray();
504 AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
505 final OrderCommand result = new OrderCommand(command.getDescription(),
511 * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
512 * given selection in the 'mapFrom' view. We assume one is nucleotide, the
513 * other is protein (and holds the mappings from codons to protein residues).
520 public static void mapColumnSelection(ColumnSelection colsel,
521 HiddenColumns hiddencols, AlignViewportI mapFrom,
522 AlignViewportI mapTo, ColumnSelection newColSel,
523 HiddenColumns newHidden)
525 boolean targetIsNucleotide = mapTo.isNucleotide();
526 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
527 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
535 char fromGapChar = mapFrom.getAlignment().getGapCharacter();
538 * For each mapped column, find the range of columns that residues in that
541 List<SequenceI> fromSequences = mapFrom.getAlignment().getSequences();
542 List<SequenceI> toSequences = mapTo.getAlignment().getSequences();
544 for (Integer sel : colsel.getSelected())
546 mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences,
547 toSequences, fromGapChar);
550 Iterator<int[]> regions = hiddencols.iterator();
551 while (regions.hasNext())
553 mapHiddenColumns(regions.next(), codonFrames, newHidden,
554 fromSequences, toSequences, fromGapChar);
560 * Helper method that maps a [start, end] hidden column range to its mapped
565 * @param mappedColumns
566 * @param fromSequences
570 protected static void mapHiddenColumns(int[] hidden,
571 List<AlignedCodonFrame> mappings, HiddenColumns mappedColumns,
572 List<SequenceI> fromSequences, List<SequenceI> toSequences,
575 for (int col = hidden[0]; col <= hidden[1]; col++)
577 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
578 toSequences, fromGapChar);
581 * Add the range of hidden columns to the mapped selection (converting
584 if (mappedTo != null)
586 mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1);
592 * Helper method to map one column selection
595 * the column number (base 0)
597 * the sequence mappings
598 * @param mappedColumns
599 * the mapped column selections to add to
600 * @param fromSequences
604 protected static void mapColumn(int col, List<AlignedCodonFrame> mappings,
605 ColumnSelection mappedColumns, List<SequenceI> fromSequences,
606 List<SequenceI> toSequences, char fromGapChar)
608 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
609 toSequences, fromGapChar);
612 * Add the range of mapped columns to the mapped selection (converting
613 * base 1 to base 0). Note that this may include intron-only regions which
614 * lie between the start and end ranges of the selection.
616 if (mappedTo != null)
618 for (int i = mappedTo[0]; i <= mappedTo[1]; i++)
620 mappedColumns.addElement(i - 1);
626 * Helper method to find the range of columns mapped to from one column.
627 * Returns the maximal range of columns mapped to from all sequences in the
628 * source column, or null if no mappings were found.
632 * @param fromSequences
637 protected static int[] findMappedColumns(int col,
638 List<AlignedCodonFrame> mappings, List<SequenceI> fromSequences,
639 List<SequenceI> toSequences, char fromGapChar)
641 int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
642 boolean found = false;
645 * For each sequence in the 'from' alignment
647 for (SequenceI fromSeq : fromSequences)
650 * Ignore gaps (unmapped anyway)
652 if (fromSeq.getCharAt(col) == fromGapChar)
658 * Get the residue position and find the mapped position.
660 int residuePos = fromSeq.findPosition(col);
661 SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings);
662 for (SearchResultMatchI m : sr.getResults())
664 int mappedStartResidue = m.getStart();
665 int mappedEndResidue = m.getEnd();
666 SequenceI mappedSeq = m.getSequence();
669 * Locate the aligned sequence whose dataset is mappedSeq. TODO a
670 * datamodel that can do this efficiently.
672 for (SequenceI toSeq : toSequences)
674 if (toSeq.getDatasetSequence() == mappedSeq
675 && mappedStartResidue >= toSeq.getStart()
676 && mappedEndResidue <= toSeq.getEnd())
678 int mappedStartCol = toSeq.findIndex(mappedStartResidue);
679 int mappedEndCol = toSeq.findIndex(mappedEndResidue);
680 mappedTo[0] = Math.min(mappedTo[0], mappedStartCol);
681 mappedTo[1] = Math.max(mappedTo[1], mappedEndCol);
684 // note: remove break if we ever want to map one to many sequences
689 return found ? mappedTo : null;
693 * Returns the mapped codon or codons for a given aligned sequence column
697 * an aligned peptide sequence
699 * an aligned column position (base 0)
701 * a set of codon mappings
702 * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s),
703 * or an empty list if none found
705 public static List<char[]> findCodonsFor(SequenceI seq, int col,
706 List<AlignedCodonFrame> mappings)
708 List<char[]> result = new ArrayList<>();
709 int dsPos = seq.findPosition(col);
710 for (AlignedCodonFrame mapping : mappings)
712 if (mapping.involvesSequence(seq))
714 List<char[]> codons = mapping
715 .getMappedCodons(seq.getDatasetSequence(), dsPos);
718 result.addAll(codons);
726 * Converts a series of [start, end] range pairs into an array of individual
727 * positions. This also caters for 'reverse strand' (start > end) cases.
732 public static int[] flattenRanges(int[] ranges)
735 * Count how many positions altogether
738 for (int i = 0; i < ranges.length - 1; i += 2)
740 count += Math.abs(ranges[i + 1] - ranges[i]) + 1;
743 int[] result = new int[count];
745 for (int i = 0; i < ranges.length - 1; i += 2)
747 int from = ranges[i];
748 final int to = ranges[i + 1];
749 int step = from <= to ? 1 : -1;
754 } while (from != to + step);
760 * Returns a list of any mappings that are from or to the given (aligned or
767 public static List<AlignedCodonFrame> findMappingsForSequence(
768 SequenceI sequence, List<AlignedCodonFrame> mappings)
770 return findMappingsForSequenceAndOthers(sequence, mappings, null);
774 * Returns a list of any mappings that are from or to the given (aligned or
775 * dataset) sequence, optionally limited to mappings involving one of a given
783 public static List<AlignedCodonFrame> findMappingsForSequenceAndOthers(
784 SequenceI sequence, List<AlignedCodonFrame> mappings,
785 List<SequenceI> filterList)
787 List<AlignedCodonFrame> result = new ArrayList<>();
788 if (sequence == null || mappings == null)
792 for (AlignedCodonFrame mapping : mappings)
794 if (mapping.involvesSequence(sequence))
796 if (filterList != null)
798 for (SequenceI otherseq : filterList)
800 SequenceI otherDataset = otherseq.getDatasetSequence();
801 if (otherseq == sequence
802 || otherseq == sequence.getDatasetSequence()
803 || (otherDataset != null && (otherDataset == sequence
804 || otherDataset == sequence
805 .getDatasetSequence())))
807 // skip sequences in subset which directly relate to sequence
810 if (mapping.involvesSequence(otherseq))
812 // selected a mapping contained in subselect alignment
828 * Returns the total length of the supplied ranges, which may be as single
829 * [start, end] or multiple [start, end, start, end ...]
834 public static int getLength(List<int[]> ranges)
841 for (int[] range : ranges)
843 if (range.length % 2 != 0)
846 "Error unbalance start/end ranges: " + ranges.toString());
849 for (int i = 0; i < range.length - 1; i += 2)
851 length += Math.abs(range[i + 1] - range[i]) + 1;
858 * Answers true if any range includes the given value
864 public static boolean contains(List<int[]> ranges, int value)
870 for (int[] range : ranges)
872 if (range[1] >= range[0] && value >= range[0] && value <= range[1])
875 * value within ascending range
879 if (range[1] < range[0] && value <= range[0] && value >= range[1])
882 * value within descending range
891 * Removes a specified number of positions from the start of a ranges list.
892 * For example, could be used to adjust cds ranges to allow for an incomplete
893 * start codon. Subranges are removed completely, or their start positions
894 * adjusted, until the required number of positions has been removed from the
895 * range. Reverse strand ranges are supported. The input array is not
900 * an array of [start, end, start, end...] positions
901 * @return a new array with the first removeCount positions removed
903 public static int[] removeStartPositions(int removeCount,
906 if (removeCount <= 0)
911 int[] copy = Arrays.copyOf(ranges, ranges.length);
914 for (int x = 0; x < copy.length && sxpos == -1; x += 2)
916 cdspos += Math.abs(copy[x + 1] - copy[x]) + 1;
917 if (removeCount < cdspos)
920 * we have removed enough, time to finish
925 * increment start of first exon, or decrement if reverse strand
927 if (copy[x] <= copy[x + 1])
929 copy[x] = copy[x + 1] - cdspos + removeCount + 1;
933 copy[x] = copy[x + 1] + cdspos - removeCount - 1;
942 * we dropped at least one entire sub-range - compact the array
944 int[] nxon = new int[copy.length - sxpos];
945 System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos);
952 * Answers true if range's start-end positions include those of queryRange,
953 * where either range might be in reverse direction, else false
958 * a candidate subrange of range (start2-end2)
961 public static boolean rangeContains(int[] range, int[] queryRange)
963 if (range == null || queryRange == null || range.length != 2
964 || queryRange.length != 2)
972 int min = Math.min(range[0], range[1]);
973 int max = Math.max(range[0], range[1]);
975 return (min <= queryRange[0] && max >= queryRange[0]
976 && min <= queryRange[1] && max >= queryRange[1]);
980 * Removes the specified number of positions from the given ranges. Provided
981 * to allow a stop codon to be stripped from a CDS sequence so that it matches
982 * the peptide translation length.
986 * a list of (single) [start, end] ranges
989 public static void removeEndPositions(int positions, List<int[]> ranges)
991 int toRemove = positions;
992 Iterator<int[]> it = new ReverseListIterator<>(ranges);
995 int[] endRange = it.next();
996 if (endRange.length != 2)
999 * not coded for [start1, end1, start2, end2, ...]
1002 "MappingUtils.removeEndPositions doesn't handle multiple ranges");
1006 int length = endRange[1] - endRange[0] + 1;
1010 * not coded for a reverse strand range (end < start)
1013 "MappingUtils.removeEndPositions doesn't handle reverse strand");
1016 if (length > toRemove)
1018 endRange[1] -= toRemove;
1030 * Converts a list of {@code start-end} ranges to a single array of
1031 * {@code start1, end1, start2, ... } ranges
1036 public static int[] rangeListToArray(List<int[]> ranges)
1038 int rangeCount = ranges.size();
1039 int[] result = new int[rangeCount * 2];
1041 for (int i = 0; i < rangeCount; i++)
1043 int[] range = ranges.get(i);
1044 result[j++] = range[0];
1045 result[j++] = range[1];
1051 * Returns the maximal start-end positions in the given (ordered) list of
1052 * ranges which is overlapped by the given begin-end range, or null if there
1057 * if ranges is {[4, 8], [10, 12], [16, 19]}
1059 * findOverlap(ranges, 1, 20) == [4, 19]
1060 * findOverlap(ranges, 6, 11) == [6, 11]
1061 * findOverlap(ranges, 9, 15) == [10, 12]
1062 * findOverlap(ranges, 13, 15) == null
1070 protected static int[] findOverlap(List<int[]> ranges, final int begin,
1073 boolean foundStart = false;
1078 * traverse the ranges to find the first position (if any) >= begin,
1079 * and the last position (if any) <= end
1081 for (int[] range : ranges)
1085 if (range[0] >= begin)
1088 * first range that starts with, or follows, begin
1091 from = Math.max(range[0], begin);
1093 else if (range[1] >= begin)
1096 * first range that contains begin
1103 if (range[0] <= end)
1105 to = Math.min(end, range[1]);
1109 return foundStart && to >= from ? new int[] { from, to } : null;