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.Cache;
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.AlignmentI;
40 import jalview.datamodel.AlignmentOrder;
41 import jalview.datamodel.ColumnSelection;
42 import jalview.datamodel.HiddenColumns;
43 import jalview.datamodel.SearchResultMatchI;
44 import jalview.datamodel.SearchResults;
45 import jalview.datamodel.SearchResultsI;
46 import jalview.datamodel.Sequence;
47 import jalview.datamodel.SequenceGroup;
48 import jalview.datamodel.SequenceI;
51 * Helper methods for manipulations involving sequence mappings.
56 public final class MappingUtils
60 * Helper method to map a CUT or PASTE command.
63 * the original command
65 * if true, the command is to be undone
67 * the mapped sequences to apply the mapped command to
69 * the mapped EditCommand to add to
72 protected static void mapCutOrPaste(Edit edit, boolean undo,
73 List<SequenceI> targetSeqs, EditCommand result,
74 List<AlignedCodonFrame> mappings)
76 Action action = edit.getAction();
79 action = action.getUndoAction();
82 Cache.log.error("MappingUtils.mapCutOrPaste not yet implemented");
86 * Returns a new EditCommand representing the given command as mapped to the
87 * given sequences. If there is no mapping, returns null.
96 public static EditCommand mapEditCommand(EditCommand command,
97 boolean undo, final AlignmentI mapTo, char gapChar,
98 List<AlignedCodonFrame> mappings)
101 * For now, only support mapping from protein edits to cDna
103 if (!mapTo.isNucleotide())
109 * Cache a copy of the target sequences so we can mimic successive edits on
110 * them. This lets us compute mappings for all edits in the set.
112 Map<SequenceI, SequenceI> targetCopies = new HashMap<>();
113 for (SequenceI seq : mapTo.getSequences())
115 SequenceI ds = seq.getDatasetSequence();
118 final SequenceI copy = new Sequence(seq);
119 copy.setDatasetSequence(ds);
120 targetCopies.put(ds, copy);
125 * Compute 'source' sequences as they were before applying edits:
127 Map<SequenceI, SequenceI> originalSequences = command.priorState(undo);
129 EditCommand result = new EditCommand();
130 Iterator<Edit> edits = command.getEditIterator(!undo);
131 while (edits.hasNext())
133 Edit edit = edits.next();
134 if (edit.getAction() == Action.CUT
135 || edit.getAction() == Action.PASTE)
137 mapCutOrPaste(edit, undo, mapTo.getSequences(), result, mappings);
139 else if (edit.getAction() == Action.INSERT_GAP
140 || edit.getAction() == Action.DELETE_GAP)
142 mapInsertOrDelete(edit, undo, originalSequences,
143 mapTo.getSequences(), targetCopies, gapChar, result,
147 return result.getSize() > 0 ? result : null;
151 * Helper method to map an edit command to insert or delete gaps.
154 * the original command
156 * if true, the action is to undo the command
157 * @param originalSequences
158 * the sequences the command acted on
160 * @param targetCopies
163 * the new EditCommand to add mapped commands to
166 protected static void mapInsertOrDelete(Edit edit, boolean undo,
167 Map<SequenceI, SequenceI> originalSequences,
168 final List<SequenceI> targetSeqs,
169 Map<SequenceI, SequenceI> targetCopies, char gapChar,
170 EditCommand result, List<AlignedCodonFrame> mappings)
172 Action action = edit.getAction();
175 * Invert sense of action if an Undo.
179 action = action.getUndoAction();
181 final int count = edit.getNumber();
182 final int editPos = edit.getPosition();
183 for (SequenceI seq : edit.getSequences())
186 * Get residue position at (or to right of) edit location. Note we use our
187 * 'copy' of the sequence before editing for this.
189 SequenceI ds = seq.getDatasetSequence();
194 final SequenceI actedOn = originalSequences.get(ds);
195 final int seqpos = actedOn.findPosition(editPos);
198 * Determine all mappings from this position to mapped sequences.
200 SearchResultsI sr = buildSearchResults(seq, seqpos, mappings);
204 for (SequenceI targetSeq : targetSeqs)
206 ds = targetSeq.getDatasetSequence();
211 SequenceI copyTarget = targetCopies.get(ds);
212 final int[] match = sr.getResults(copyTarget, 0,
213 copyTarget.getLength());
216 final int ratio = 3; // TODO: compute this - how?
217 final int mappedCount = count * ratio;
220 * Shift Delete start position left, as it acts on positions to its
223 int mappedEditPos = action == Action.DELETE_GAP
224 ? match[0] - mappedCount
226 Edit e = result.new Edit(action, new SequenceI[] { targetSeq },
227 mappedEditPos, mappedCount, gapChar);
231 * and 'apply' the edit to our copy of its target sequence
233 if (action == Action.INSERT_GAP)
235 copyTarget.setSequence(new String(
236 StringUtils.insertCharAt(copyTarget.getSequence(),
237 mappedEditPos, mappedCount, gapChar)));
239 else if (action == Action.DELETE_GAP)
241 copyTarget.setSequence(new String(
242 StringUtils.deleteChars(copyTarget.getSequence(),
243 mappedEditPos, mappedEditPos + mappedCount)));
249 * and 'apply' the edit to our copy of its source sequence
251 if (action == Action.INSERT_GAP)
253 actedOn.setSequence(new String(StringUtils.insertCharAt(
254 actedOn.getSequence(), editPos, count, gapChar)));
256 else if (action == Action.DELETE_GAP)
258 actedOn.setSequence(new String(StringUtils.deleteChars(
259 actedOn.getSequence(), editPos, editPos + count)));
265 * Returns a SearchResults object describing the mapped region corresponding
266 * to the specified sequence position.
273 public static SearchResultsI buildSearchResults(SequenceI seq, int index,
274 List<AlignedCodonFrame> seqmappings)
276 SearchResultsI results = new SearchResults();
277 addSearchResults(results, seq, index, seqmappings);
282 * Adds entries to a SearchResults object describing the mapped region
283 * corresponding to the specified sequence position.
290 public static void addSearchResults(SearchResultsI results, SequenceI seq,
291 int index, List<AlignedCodonFrame> seqmappings)
293 if (index >= seq.getStart() && index <= seq.getEnd())
295 for (AlignedCodonFrame acf : seqmappings)
297 acf.markMappedRegion(seq, index, results);
303 * Returns a (possibly empty) SequenceGroup containing any sequences in the
304 * mapped viewport corresponding to the given group in the source viewport.
311 public static SequenceGroup mapSequenceGroup(final SequenceGroup sg,
312 final AlignViewportI mapFrom, final AlignViewportI mapTo)
315 * Note the SequenceGroup holds aligned sequences, the mappings hold dataset
318 boolean targetIsNucleotide = mapTo.isNucleotide();
319 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
320 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
323 * Copy group name, colours etc, but not sequences or sequence colour scheme
325 SequenceGroup mappedGroup = new SequenceGroup(sg);
326 mappedGroup.setColourScheme(mapTo.getGlobalColourScheme());
329 int minStartCol = -1;
331 final int selectionStartRes = sg.getStartRes();
332 final int selectionEndRes = sg.getEndRes();
333 for (SequenceI selected : sg.getSequences())
336 * Find the widest range of non-gapped positions in the selection range
338 int firstUngappedPos = selectionStartRes;
339 while (firstUngappedPos <= selectionEndRes
340 && Comparison.isGap(selected.getCharAt(firstUngappedPos)))
346 * If this sequence is only gaps in the selected range, skip it
348 if (firstUngappedPos > selectionEndRes)
353 int lastUngappedPos = selectionEndRes;
354 while (lastUngappedPos >= selectionStartRes
355 && Comparison.isGap(selected.getCharAt(lastUngappedPos)))
361 * Find the selected start/end residue positions in sequence
363 int startResiduePos = selected.findPosition(firstUngappedPos);
364 int endResiduePos = selected.findPosition(lastUngappedPos);
366 for (AlignedCodonFrame acf : codonFrames)
368 // TODO: handle multiple mappings
369 SequenceI mappedSequence = targetIsNucleotide
370 ? acf.getDnaForAaSeq(selected)
371 : acf.getAaForDnaSeq(selected);
372 if (mappedSequence != null)
374 for (SequenceI seq : mapTo.getAlignment().getSequences())
376 int mappedStartResidue = 0;
377 int mappedEndResidue = 0;
378 if (seq.getDatasetSequence() == mappedSequence)
381 * Found a sequence mapping. Locate the start/end mapped residues.
383 List<AlignedCodonFrame> mapping = Arrays
384 .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 sr = buildSearchResults(selected, endResiduePos, mapping);
394 for (SearchResultMatchI m : sr.getResults())
396 mappedStartResidue = Math.min(mappedStartResidue,
398 mappedEndResidue = Math.max(mappedEndResidue, m.getEnd());
402 * Find the mapped aligned columns, save the range. Note findIndex
403 * returns a base 1 position, SequenceGroup uses base 0
405 int mappedStartCol = seq.findIndex(mappedStartResidue) - 1;
406 minStartCol = minStartCol == -1 ? mappedStartCol
407 : Math.min(minStartCol, mappedStartCol);
408 int mappedEndCol = seq.findIndex(mappedEndResidue) - 1;
409 maxEndCol = maxEndCol == -1 ? mappedEndCol
410 : Math.max(maxEndCol, mappedEndCol);
411 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 SequenceI mappedSeq = mappingToNucleotide ? acf.getDnaForAaSeq(seq)
455 : acf.getAaForDnaSeq(seq);
456 if (mappedSeq != null)
458 for (SequenceI seq2 : mapTo.getSequences())
460 if (seq2.getDatasetSequence() == mappedSeq)
462 mappedOrder.add(seq2);
472 * Return null if no mappings made.
480 * Add any unmapped sequences on the end of the sort in their original
483 if (j < mapTo.getHeight())
485 for (SequenceI seq : mapTo.getSequences())
487 if (!mappedOrder.contains(seq))
489 mappedOrder.add(seq);
495 * Have to sort the sequences before constructing the OrderCommand - which
496 * then resorts them?!?
498 final SequenceI[] mappedOrderArray = mappedOrder
499 .toArray(new SequenceI[mappedOrder.size()]);
500 SequenceI[] oldOrder = mapTo.getSequencesArray();
501 AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
502 final OrderCommand result = new OrderCommand(command.getDescription(),
508 * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
509 * given selection in the 'mapFrom' view. We assume one is nucleotide, the
510 * other is protein (and holds the mappings from codons to protein residues).
517 public static void mapColumnSelection(ColumnSelection colsel,
518 HiddenColumns hiddencols, AlignViewportI mapFrom,
519 AlignViewportI mapTo, ColumnSelection newColSel,
520 HiddenColumns newHidden)
522 boolean targetIsNucleotide = mapTo.isNucleotide();
523 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
524 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
529 return; // mappedColumns;
532 char fromGapChar = mapFrom.getAlignment().getGapCharacter();
535 * For each mapped column, find the range of columns that residues in that
538 List<SequenceI> fromSequences = mapFrom.getAlignment().getSequences();
539 List<SequenceI> toSequences = mapTo.getAlignment().getSequences();
541 for (Integer sel : colsel.getSelected())
543 mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences,
544 toSequences, fromGapChar);
547 Iterator<int[]> regions = hiddencols.iterator();
548 while (regions.hasNext())
550 mapHiddenColumns(regions.next(), codonFrames, newHidden,
551 fromSequences, toSequences, fromGapChar);
553 return; // mappedColumns;
557 * Helper method that maps a [start, end] hidden column range to its mapped
562 * @param mappedColumns
563 * @param fromSequences
567 protected static void mapHiddenColumns(int[] hidden,
568 List<AlignedCodonFrame> mappings, HiddenColumns mappedColumns,
569 List<SequenceI> fromSequences, List<SequenceI> toSequences,
572 for (int col = hidden[0]; col <= hidden[1]; col++)
574 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
575 toSequences, fromGapChar);
578 * Add the range of hidden columns to the mapped selection (converting
581 if (mappedTo != null)
583 mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1);
589 * Helper method to map one column selection
592 * the column number (base 0)
594 * the sequence mappings
595 * @param mappedColumns
596 * the mapped column selections to add to
597 * @param fromSequences
601 protected static void mapColumn(int col, List<AlignedCodonFrame> mappings,
602 ColumnSelection mappedColumns, List<SequenceI> fromSequences,
603 List<SequenceI> toSequences, char fromGapChar)
605 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
606 toSequences, fromGapChar);
609 * Add the range of mapped columns to the mapped selection (converting
610 * base 1 to base 0). Note that this may include intron-only regions which
611 * lie between the start and end ranges of the selection.
613 if (mappedTo != null)
615 for (int i = mappedTo[0]; i <= mappedTo[1]; i++)
617 mappedColumns.addElement(i - 1);
623 * Helper method to find the range of columns mapped to from one column.
624 * Returns the maximal range of columns mapped to from all sequences in the
625 * source column, or null if no mappings were found.
629 * @param fromSequences
634 protected static int[] findMappedColumns(int col,
635 List<AlignedCodonFrame> mappings, List<SequenceI> fromSequences,
636 List<SequenceI> toSequences, char fromGapChar)
638 int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
639 boolean found = false;
642 * For each sequence in the 'from' alignment
644 for (SequenceI fromSeq : fromSequences)
647 * Ignore gaps (unmapped anyway)
649 if (fromSeq.getCharAt(col) == fromGapChar)
655 * Get the residue position and find the mapped position.
657 int residuePos = fromSeq.findPosition(col);
658 SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings);
659 for (SearchResultMatchI m : sr.getResults())
661 int mappedStartResidue = m.getStart();
662 int mappedEndResidue = m.getEnd();
663 SequenceI mappedSeq = m.getSequence();
666 * Locate the aligned sequence whose dataset is mappedSeq. TODO a
667 * datamodel that can do this efficiently.
669 for (SequenceI toSeq : toSequences)
671 if (toSeq.getDatasetSequence() == mappedSeq)
673 int mappedStartCol = toSeq.findIndex(mappedStartResidue);
674 int mappedEndCol = toSeq.findIndex(mappedEndResidue);
675 mappedTo[0] = Math.min(mappedTo[0], mappedStartCol);
676 mappedTo[1] = Math.max(mappedTo[1], mappedEndCol);
679 // note: remove break if we ever want to map one to many sequences
684 return found ? mappedTo : null;
688 * Returns the mapped codon or codons for a given aligned sequence column
692 * an aligned peptide sequence
694 * an aligned column position (base 0)
696 * a set of codon mappings
697 * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s),
698 * or an empty list if none found
700 public static List<char[]> findCodonsFor(SequenceI seq, int col,
701 List<AlignedCodonFrame> mappings)
703 List<char[]> result = new ArrayList<>();
704 int dsPos = seq.findPosition(col);
705 for (AlignedCodonFrame mapping : mappings)
707 if (mapping.involvesSequence(seq))
709 List<char[]> codons = mapping
710 .getMappedCodons(seq.getDatasetSequence(), dsPos);
713 result.addAll(codons);
721 * Converts a series of [start, end] range pairs into an array of individual
722 * positions. This also caters for 'reverse strand' (start > end) cases.
727 public static int[] flattenRanges(int[] ranges)
730 * Count how many positions altogether
733 for (int i = 0; i < ranges.length - 1; i += 2)
735 count += Math.abs(ranges[i + 1] - ranges[i]) + 1;
738 int[] result = new int[count];
740 for (int i = 0; i < ranges.length - 1; i += 2)
742 int from = ranges[i];
743 final int to = ranges[i + 1];
744 int step = from <= to ? 1 : -1;
749 } while (from != to + step);
755 * Returns a list of any mappings that are from or to the given (aligned or
762 public static List<AlignedCodonFrame> findMappingsForSequence(
763 SequenceI sequence, List<AlignedCodonFrame> mappings)
765 return findMappingsForSequenceAndOthers(sequence, mappings, null);
769 * Returns a list of any mappings that are from or to the given (aligned or
770 * dataset) sequence, optionally limited to mappings involving one of a given
778 public static List<AlignedCodonFrame> findMappingsForSequenceAndOthers(
779 SequenceI sequence, List<AlignedCodonFrame> mappings,
780 List<SequenceI> filterList)
782 List<AlignedCodonFrame> result = new ArrayList<>();
783 if (sequence == null || mappings == null)
787 for (AlignedCodonFrame mapping : mappings)
789 if (mapping.involvesSequence(sequence))
791 if (filterList != null)
793 for (SequenceI otherseq : filterList)
795 SequenceI otherDataset = otherseq.getDatasetSequence();
796 if (otherseq == sequence
797 || otherseq == sequence.getDatasetSequence()
798 || (otherDataset != null && (otherDataset == sequence
799 || otherDataset == sequence
800 .getDatasetSequence())))
802 // skip sequences in subset which directly relate to sequence
805 if (mapping.involvesSequence(otherseq))
807 // selected a mapping contained in subselect alignment
823 * Returns the total length of the supplied ranges, which may be as single
824 * [start, end] or multiple [start, end, start, end ...]
829 public static int getLength(List<int[]> ranges)
836 for (int[] range : ranges)
838 if (range.length % 2 != 0)
841 "Error unbalance start/end ranges: " + ranges.toString());
844 for (int i = 0; i < range.length - 1; i += 2)
846 length += Math.abs(range[i + 1] - range[i]) + 1;
853 * Answers true if any range includes the given value
859 public static boolean contains(List<int[]> ranges, int value)
865 for (int[] range : ranges)
867 if (range[1] >= range[0] && value >= range[0] && value <= range[1])
870 * value within ascending range
874 if (range[1] < range[0] && value <= range[0] && value >= range[1])
877 * value within descending range
886 * Removes a specified number of positions from the start of a ranges list.
887 * For example, could be used to adjust cds ranges to allow for an incomplete
888 * start codon. Subranges are removed completely, or their start positions
889 * adjusted, until the required number of positions has been removed from the
890 * range. Reverse strand ranges are supported. The input array is not
895 * an array of [start, end, start, end...] positions
896 * @return a new array with the first removeCount positions removed
898 public static int[] removeStartPositions(int removeCount,
901 if (removeCount <= 0)
906 int[] copy = Arrays.copyOf(ranges, ranges.length);
909 for (int x = 0; x < copy.length && sxpos == -1; x += 2)
911 cdspos += Math.abs(copy[x + 1] - copy[x]) + 1;
912 if (removeCount < cdspos)
915 * we have removed enough, time to finish
920 * increment start of first exon, or decrement if reverse strand
922 if (copy[x] <= copy[x + 1])
924 copy[x] = copy[x + 1] - cdspos + removeCount + 1;
928 copy[x] = copy[x + 1] + cdspos - removeCount - 1;
937 * we dropped at least one entire sub-range - compact the array
939 int[] nxon = new int[copy.length - sxpos];
940 System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos);
947 * Answers true if range's start-end positions include those of queryRange,
948 * where either range might be in reverse direction, else false
953 * a candidate subrange of range (start2-end2)
956 public static boolean rangeContains(int[] range, int[] queryRange)
958 if (range == null || queryRange == null || range.length != 2
959 || queryRange.length != 2)
967 int min = Math.min(range[0], range[1]);
968 int max = Math.max(range[0], range[1]);
970 return (min <= queryRange[0] && max >= queryRange[0]
971 && min <= queryRange[1] && max >= queryRange[1]);
975 * Removes the specified number of positions from the given ranges. Provided
976 * to allow a stop codon to be stripped from a CDS sequence so that it matches
977 * the peptide translation length.
981 * a list of (single) [start, end] ranges
984 public static void removeEndPositions(int positions, List<int[]> ranges)
986 int toRemove = positions;
987 Iterator<int[]> it = new ReverseListIterator<>(ranges);
990 int[] endRange = it.next();
991 if (endRange.length != 2)
994 * not coded for [start1, end1, start2, end2, ...]
997 "MappingUtils.removeEndPositions doesn't handle multiple ranges");
1001 int length = endRange[1] - endRange[0] + 1;
1005 * not coded for a reverse strand range (end < start)
1008 "MappingUtils.removeEndPositions doesn't handle reverse strand");
1011 if (length > toRemove)
1013 endRange[1] -= toRemove;
1025 * Converts a list of {@code start-end} ranges to a single array of
1026 * {@code start1, end1, start2, ... } ranges
1031 public static int[] rangeListToArray(List<int[]> ranges)
1033 int rangeCount = ranges.size();
1034 int[] result = new int[rangeCount * 2];
1036 for (int i = 0; i < rangeCount; i++)
1038 int[] range = ranges.get(i);
1039 result[j++] = range[0];
1040 result[j++] = range[1];
1046 * Returns the maximal start-end positions in the given (ordered) list of
1047 * ranges which is overlapped by the given begin-end range, or null if there
1052 * if ranges is {[4, 8], [10, 12], [16, 19]}
1054 * findOverlap(ranges, 1, 20) == [4, 19]
1055 * findOverlap(ranges, 6, 11) == [6, 11]
1056 * findOverlap(ranges, 9, 15) == [10, 12]
1057 * findOverlap(ranges, 13, 15) == null
1065 protected static int[] findOverlap(List<int[]> ranges, final int begin,
1068 boolean foundStart = false;
1073 * traverse the ranges to find the first position (if any) >= begin,
1074 * and the last position (if any) <= end
1076 for (int[] range : ranges)
1080 if (range[0] >= begin)
1083 * first range that starts with, or follows, begin
1086 from = Math.max(range[0], begin);
1088 else if (range[1] >= begin)
1091 * first range that contains begin
1098 if (range[0] <= end)
1100 to = Math.min(end, range[1]);
1104 return foundStart && to >= from ? new int[] { from, to } : null;