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.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.SearchResultMatchI;
45 import jalview.datamodel.SearchResults;
46 import jalview.datamodel.SearchResultsI;
47 import jalview.datamodel.Sequence;
48 import jalview.datamodel.SequenceGroup;
49 import jalview.datamodel.SequenceI;
52 * Helper methods for manipulations involving sequence mappings.
57 public final class MappingUtils
61 * Helper method to map a CUT or PASTE command.
64 * the original command
66 * if true, the command is to be undone
68 * the mapped sequences to apply the mapped command to
70 * the mapped EditCommand to add to
73 protected static void mapCutOrPaste(Edit edit, boolean undo,
74 List<SequenceI> targetSeqs, EditCommand result,
75 List<AlignedCodonFrame> mappings)
77 Action action = edit.getAction();
80 action = action.getUndoAction();
83 Cache.log.error("MappingUtils.mapCutOrPaste not yet implemented");
87 * Returns a new EditCommand representing the given command as mapped to the
88 * given sequences. If there is no mapping, returns null.
97 public static EditCommand mapEditCommand(EditCommand command,
98 boolean undo, final AlignmentI mapTo, char gapChar,
99 List<AlignedCodonFrame> mappings)
102 * For now, only support mapping from protein edits to cDna
104 if (!mapTo.isNucleotide())
110 * Cache a copy of the target sequences so we can mimic successive edits on
111 * them. This lets us compute mappings for all edits in the set.
113 Map<SequenceI, SequenceI> targetCopies = new HashMap<>();
114 for (SequenceI seq : mapTo.getSequences())
116 SequenceI ds = seq.getDatasetSequence();
119 final SequenceI copy = new Sequence(seq);
120 copy.setDatasetSequence(ds);
121 targetCopies.put(ds, copy);
126 * Compute 'source' sequences as they were before applying edits:
128 Map<SequenceI, SequenceI> originalSequences = command.priorState(undo);
130 EditCommand result = new EditCommand();
131 Iterator<Edit> edits = command.getEditIterator(!undo);
132 while (edits.hasNext())
134 Edit edit = edits.next();
135 if (edit.getAction() == Action.CUT
136 || edit.getAction() == Action.PASTE)
138 mapCutOrPaste(edit, undo, mapTo.getSequences(), result, mappings);
140 else if (edit.getAction() == Action.INSERT_GAP
141 || edit.getAction() == Action.DELETE_GAP)
143 mapInsertOrDelete(edit, undo, originalSequences,
144 mapTo.getSequences(), targetCopies, gapChar, result,
148 return result.getSize() > 0 ? result : null;
152 * Helper method to map an edit command to insert or delete gaps.
155 * the original command
157 * if true, the action is to undo the command
158 * @param originalSequences
159 * the sequences the command acted on
161 * @param targetCopies
164 * the new EditCommand to add mapped commands to
167 protected static void mapInsertOrDelete(Edit edit, boolean undo,
168 Map<SequenceI, SequenceI> originalSequences,
169 final List<SequenceI> targetSeqs,
170 Map<SequenceI, SequenceI> targetCopies, char gapChar,
171 EditCommand result, List<AlignedCodonFrame> mappings)
173 Action action = edit.getAction();
176 * Invert sense of action if an Undo.
180 action = action.getUndoAction();
182 final int count = edit.getNumber();
183 final int editPos = edit.getPosition();
184 for (SequenceI seq : edit.getSequences())
187 * Get residue position at (or to right of) edit location. Note we use our
188 * 'copy' of the sequence before editing for this.
190 SequenceI ds = seq.getDatasetSequence();
195 final SequenceI actedOn = originalSequences.get(ds);
196 final int seqpos = actedOn.findPosition(editPos);
199 * Determine all mappings from this position to mapped sequences.
201 SearchResultsI sr = buildSearchResults(seq, seqpos, mappings);
205 for (SequenceI targetSeq : targetSeqs)
207 ds = targetSeq.getDatasetSequence();
212 SequenceI copyTarget = targetCopies.get(ds);
213 final int[] match = sr.getResults(copyTarget, 0,
214 copyTarget.getLength());
217 final int ratio = 3; // TODO: compute this - how?
218 final int mappedCount = count * ratio;
221 * Shift Delete start position left, as it acts on positions to its
224 int mappedEditPos = action == Action.DELETE_GAP
225 ? match[0] - mappedCount
227 Edit e = result.new Edit(action, new SequenceI[] { targetSeq },
228 mappedEditPos, mappedCount, gapChar);
232 * and 'apply' the edit to our copy of its target sequence
234 if (action == Action.INSERT_GAP)
236 copyTarget.setSequence(new String(
237 StringUtils.insertCharAt(copyTarget.getSequence(),
238 mappedEditPos, mappedCount, gapChar)));
240 else if (action == Action.DELETE_GAP)
242 copyTarget.setSequence(new String(
243 StringUtils.deleteChars(copyTarget.getSequence(),
244 mappedEditPos, mappedEditPos + mappedCount)));
250 * and 'apply' the edit to our copy of its source sequence
252 if (action == Action.INSERT_GAP)
254 actedOn.setSequence(new String(StringUtils.insertCharAt(
255 actedOn.getSequence(), editPos, count, gapChar)));
257 else if (action == Action.DELETE_GAP)
259 actedOn.setSequence(new String(StringUtils.deleteChars(
260 actedOn.getSequence(), editPos, editPos + count)));
266 * Returns a SearchResults object describing the mapped region corresponding
267 * to the specified sequence position.
274 public static SearchResultsI buildSearchResults(SequenceI seq, int index,
275 List<AlignedCodonFrame> seqmappings)
277 SearchResultsI results = new SearchResults();
278 addSearchResults(results, seq, index, seqmappings);
283 * Adds entries to a SearchResults object describing the mapped region
284 * corresponding to the specified sequence position.
291 public static void addSearchResults(SearchResultsI results, SequenceI seq,
292 int index, List<AlignedCodonFrame> seqmappings)
294 if (index >= seq.getStart() && index <= seq.getEnd())
296 for (AlignedCodonFrame acf : seqmappings)
298 acf.markMappedRegion(seq, index, results);
304 * Returns a (possibly empty) SequenceGroup containing any sequences in the
305 * mapped viewport corresponding to the given group in the source viewport.
312 public static SequenceGroup mapSequenceGroup(final SequenceGroup sg,
313 final AlignViewportI mapFrom, final AlignViewportI mapTo)
316 * Note the SequenceGroup holds aligned sequences, the mappings hold dataset
319 boolean targetIsNucleotide = mapTo.isNucleotide();
320 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
321 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
324 * Copy group name, colours etc, but not sequences or sequence colour scheme
326 SequenceGroup mappedGroup = new SequenceGroup(sg);
327 mappedGroup.setColourScheme(mapTo.getGlobalColourScheme());
330 int minStartCol = -1;
332 final int selectionStartRes = sg.getStartRes();
333 final int selectionEndRes = sg.getEndRes();
334 for (SequenceI selected : sg.getSequences())
337 * Find the widest range of non-gapped positions in the selection range
339 int firstUngappedPos = selectionStartRes;
340 while (firstUngappedPos <= selectionEndRes
341 && Comparison.isGap(selected.getCharAt(firstUngappedPos)))
346 boolean allGapped = (firstUngappedPos > selectionEndRes);
348 int lastUngappedPos = selectionEndRes;
351 while (lastUngappedPos >= selectionStartRes
352 && Comparison.isGap(selected.getCharAt(lastUngappedPos)))
359 * Find the selected start/end residue positions in sequence
361 int startResiduePos = allGapped ? 0 : selected.findPosition(firstUngappedPos);
362 int endResiduePos = allGapped ? 0 : selected.findPosition(lastUngappedPos);
364 for (AlignedCodonFrame acf : codonFrames)
366 for (SequenceI seq : mapTo.getAlignment().getSequences())
368 SequenceI peptide = targetIsNucleotide ? selected : seq;
369 SequenceI cds = targetIsNucleotide ? seq : selected;
370 SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds,
376 mappedGroup.addSequence(seq, false);
380 * sequence is mapped but includes no mapped residues
384 int mappedStartResidue = 0;
385 int mappedEndResidue = 0;
386 List<AlignedCodonFrame> mapping = Arrays.asList(acf);
387 SearchResultsI sr = buildSearchResults(selected, startResiduePos,
389 for (SearchResultMatchI m : sr.getResults())
391 mappedStartResidue = m.getStart();
392 mappedEndResidue = m.getEnd();
394 sr = buildSearchResults(selected, endResiduePos, mapping);
395 for (SearchResultMatchI m : sr.getResults())
397 mappedStartResidue = Math.min(mappedStartResidue, m.getStart());
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);
414 mappedGroup.setStartRes(minStartCol < 0 ? 0 : minStartCol);
415 mappedGroup.setEndRes(maxEndCol < 0 ? 0 : maxEndCol);
420 * Returns an OrderCommand equivalent to the given one, but acting on mapped
421 * sequences as described by the mappings, or null if no mapping can be made.
424 * the original order command
426 * if true, the action is to undo the sort
428 * the alignment we are mapping to
430 * the mappings available
433 public static CommandI mapOrderCommand(OrderCommand command, boolean undo,
434 AlignmentI mapTo, List<AlignedCodonFrame> mappings)
436 SequenceI[] sortOrder = command.getSequenceOrder(undo);
437 List<SequenceI> mappedOrder = new ArrayList<>();
441 * Assumption: we are only interested in a cDNA/protein mapping; refactor in
442 * future if we want to support sorting (c)dna as (c)dna or protein as
445 boolean mappingToNucleotide = mapTo.isNucleotide();
446 for (SequenceI seq : sortOrder)
448 for (AlignedCodonFrame acf : mappings)
450 for (SequenceI seq2 : mapTo.getSequences())
453 * the corresponding peptide / CDS is the one for which there is
454 * a complete ('covering') mapping to 'seq'
456 SequenceI peptide = mappingToNucleotide ? seq2 : seq;
457 SequenceI cds = mappingToNucleotide ? seq : seq2;
458 SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds,
462 mappedOrder.add(seq2);
471 * Return null if no mappings made.
479 * Add any unmapped sequences on the end of the sort in their original
482 if (j < mapTo.getHeight())
484 for (SequenceI seq : mapTo.getSequences())
486 if (!mappedOrder.contains(seq))
488 mappedOrder.add(seq);
494 * Have to sort the sequences before constructing the OrderCommand - which
495 * then resorts them?!?
497 final SequenceI[] mappedOrderArray = mappedOrder
498 .toArray(new SequenceI[mappedOrder.size()]);
499 SequenceI[] oldOrder = mapTo.getSequencesArray();
500 AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
501 final OrderCommand result = new OrderCommand(command.getDescription(),
507 * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
508 * given selection in the 'mapFrom' view. We assume one is nucleotide, the
509 * other is protein (and holds the mappings from codons to protein residues).
516 public static void mapColumnSelection(ColumnSelection colsel,
517 HiddenColumns hiddencols, AlignViewportI mapFrom,
518 AlignViewportI mapTo, ColumnSelection newColSel,
519 HiddenColumns newHidden)
521 boolean targetIsNucleotide = mapTo.isNucleotide();
522 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
523 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
531 char fromGapChar = mapFrom.getAlignment().getGapCharacter();
534 * For each mapped column, find the range of columns that residues in that
537 List<SequenceI> fromSequences = mapFrom.getAlignment().getSequences();
538 List<SequenceI> toSequences = mapTo.getAlignment().getSequences();
540 for (Integer sel : colsel.getSelected())
542 mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences,
543 toSequences, fromGapChar);
546 Iterator<int[]> regions = hiddencols.iterator();
547 while (regions.hasNext())
549 mapHiddenColumns(regions.next(), codonFrames, newHidden,
550 fromSequences, toSequences, fromGapChar);
556 * Helper method that maps a [start, end] hidden column range to its mapped
561 * @param mappedColumns
562 * @param fromSequences
566 protected static void mapHiddenColumns(int[] hidden,
567 List<AlignedCodonFrame> mappings, HiddenColumns mappedColumns,
568 List<SequenceI> fromSequences, List<SequenceI> toSequences,
571 for (int col = hidden[0]; col <= hidden[1]; col++)
573 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
574 toSequences, fromGapChar);
577 * Add the range of hidden columns to the mapped selection (converting
580 if (mappedTo != null)
582 mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1);
588 * Helper method to map one column selection
591 * the column number (base 0)
593 * the sequence mappings
594 * @param mappedColumns
595 * the mapped column selections to add to
596 * @param fromSequences
600 protected static void mapColumn(int col, List<AlignedCodonFrame> mappings,
601 ColumnSelection mappedColumns, List<SequenceI> fromSequences,
602 List<SequenceI> toSequences, char fromGapChar)
604 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
605 toSequences, fromGapChar);
608 * Add the range of mapped columns to the mapped selection (converting
609 * base 1 to base 0). Note that this may include intron-only regions which
610 * lie between the start and end ranges of the selection.
612 if (mappedTo != null)
614 for (int i = mappedTo[0]; i <= mappedTo[1]; i++)
616 mappedColumns.addElement(i - 1);
622 * Helper method to find the range of columns mapped to from one column.
623 * Returns the maximal range of columns mapped to from all sequences in the
624 * source column, or null if no mappings were found.
628 * @param fromSequences
633 protected static int[] findMappedColumns(int col,
634 List<AlignedCodonFrame> mappings, List<SequenceI> fromSequences,
635 List<SequenceI> toSequences, char fromGapChar)
637 int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
638 boolean found = false;
641 * For each sequence in the 'from' alignment
643 for (SequenceI fromSeq : fromSequences)
646 * Ignore gaps (unmapped anyway)
648 if (fromSeq.getCharAt(col) == fromGapChar)
654 * Get the residue position and find the mapped position.
656 int residuePos = fromSeq.findPosition(col);
657 SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings);
658 for (SearchResultMatchI m : sr.getResults())
660 int mappedStartResidue = m.getStart();
661 int mappedEndResidue = m.getEnd();
662 SequenceI mappedSeq = m.getSequence();
665 * Locate the aligned sequence whose dataset is mappedSeq. TODO a
666 * datamodel that can do this efficiently.
668 for (SequenceI toSeq : toSequences)
670 if (toSeq.getDatasetSequence() == mappedSeq
671 && mappedStartResidue >= toSeq.getStart()
672 && mappedEndResidue <= toSeq.getEnd())
674 int mappedStartCol = toSeq.findIndex(mappedStartResidue);
675 int mappedEndCol = toSeq.findIndex(mappedEndResidue);
676 mappedTo[0] = Math.min(mappedTo[0], mappedStartCol);
677 mappedTo[1] = Math.max(mappedTo[1], mappedEndCol);
680 // note: remove break if we ever want to map one to many sequences
685 return found ? mappedTo : null;
689 * Returns the mapped codon or codons for a given aligned sequence column
693 * an aligned peptide sequence
695 * an aligned column position (base 0)
697 * a set of codon mappings
698 * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s),
699 * or an empty list if none found
701 public static List<char[]> findCodonsFor(SequenceI seq, int col,
702 List<AlignedCodonFrame> mappings)
704 List<char[]> result = new ArrayList<>();
705 int dsPos = seq.findPosition(col);
706 for (AlignedCodonFrame mapping : mappings)
708 if (mapping.involvesSequence(seq))
710 List<char[]> codons = mapping
711 .getMappedCodons(seq.getDatasetSequence(), dsPos);
714 result.addAll(codons);
722 * Converts a series of [start, end] range pairs into an array of individual
723 * positions. This also caters for 'reverse strand' (start > end) cases.
728 public static int[] flattenRanges(int[] ranges)
731 * Count how many positions altogether
734 for (int i = 0; i < ranges.length - 1; i += 2)
736 count += Math.abs(ranges[i + 1] - ranges[i]) + 1;
739 int[] result = new int[count];
741 for (int i = 0; i < ranges.length - 1; i += 2)
743 int from = ranges[i];
744 final int to = ranges[i + 1];
745 int step = from <= to ? 1 : -1;
750 } while (from != to + step);
756 * Returns a list of any mappings that are from or to the given (aligned or
763 public static List<AlignedCodonFrame> findMappingsForSequence(
764 SequenceI sequence, List<AlignedCodonFrame> mappings)
766 return findMappingsForSequenceAndOthers(sequence, mappings, null);
770 * Returns a list of any mappings that are from or to the given (aligned or
771 * dataset) sequence, optionally limited to mappings involving one of a given
779 public static List<AlignedCodonFrame> findMappingsForSequenceAndOthers(
780 SequenceI sequence, List<AlignedCodonFrame> mappings,
781 List<SequenceI> filterList)
783 List<AlignedCodonFrame> result = new ArrayList<>();
784 if (sequence == null || mappings == null)
788 for (AlignedCodonFrame mapping : mappings)
790 if (mapping.involvesSequence(sequence))
792 if (filterList != null)
794 for (SequenceI otherseq : filterList)
796 SequenceI otherDataset = otherseq.getDatasetSequence();
797 if (otherseq == sequence
798 || otherseq == sequence.getDatasetSequence()
799 || (otherDataset != null && (otherDataset == sequence
800 || otherDataset == sequence
801 .getDatasetSequence())))
803 // skip sequences in subset which directly relate to sequence
806 if (mapping.involvesSequence(otherseq))
808 // selected a mapping contained in subselect alignment
824 * Returns the total length of the supplied ranges, which may be as single
825 * [start, end] or multiple [start, end, start, end ...]
830 public static int getLength(List<int[]> ranges)
837 for (int[] range : ranges)
839 if (range.length % 2 != 0)
842 "Error unbalance start/end ranges: " + ranges.toString());
845 for (int i = 0; i < range.length - 1; i += 2)
847 length += Math.abs(range[i + 1] - range[i]) + 1;
854 * Answers true if any range includes the given value
860 public static boolean contains(List<int[]> ranges, int value)
866 for (int[] range : ranges)
868 if (range[1] >= range[0] && value >= range[0] && value <= range[1])
871 * value within ascending range
875 if (range[1] < range[0] && value <= range[0] && value >= range[1])
878 * value within descending range
887 * Removes a specified number of positions from the start of a ranges list.
888 * For example, could be used to adjust cds ranges to allow for an incomplete
889 * start codon. Subranges are removed completely, or their start positions
890 * adjusted, until the required number of positions has been removed from the
891 * range. Reverse strand ranges are supported. The input array is not
896 * an array of [start, end, start, end...] positions
897 * @return a new array with the first removeCount positions removed
899 public static int[] removeStartPositions(int removeCount,
902 if (removeCount <= 0)
907 int[] copy = Arrays.copyOf(ranges, ranges.length);
910 for (int x = 0; x < copy.length && sxpos == -1; x += 2)
912 cdspos += Math.abs(copy[x + 1] - copy[x]) + 1;
913 if (removeCount < cdspos)
916 * we have removed enough, time to finish
921 * increment start of first exon, or decrement if reverse strand
923 if (copy[x] <= copy[x + 1])
925 copy[x] = copy[x + 1] - cdspos + removeCount + 1;
929 copy[x] = copy[x + 1] + cdspos - removeCount - 1;
938 * we dropped at least one entire sub-range - compact the array
940 int[] nxon = new int[copy.length - sxpos];
941 System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos);
948 * Answers true if range's start-end positions include those of queryRange,
949 * where either range might be in reverse direction, else false
954 * a candidate subrange of range (start2-end2)
957 public static boolean rangeContains(int[] range, int[] queryRange)
959 if (range == null || queryRange == null || range.length != 2
960 || queryRange.length != 2)
968 int min = Math.min(range[0], range[1]);
969 int max = Math.max(range[0], range[1]);
971 return (min <= queryRange[0] && max >= queryRange[0]
972 && min <= queryRange[1] && max >= queryRange[1]);
976 * Removes the specified number of positions from the given ranges. Provided
977 * to allow a stop codon to be stripped from a CDS sequence so that it matches
978 * the peptide translation length.
982 * a list of (single) [start, end] ranges
985 public static void removeEndPositions(int positions, List<int[]> ranges)
987 int toRemove = positions;
988 Iterator<int[]> it = new ReverseListIterator<>(ranges);
991 int[] endRange = it.next();
992 if (endRange.length != 2)
995 * not coded for [start1, end1, start2, end2, ...]
998 "MappingUtils.removeEndPositions doesn't handle multiple ranges");
1002 int length = endRange[1] - endRange[0] + 1;
1006 * not coded for a reverse strand range (end < start)
1009 "MappingUtils.removeEndPositions doesn't handle reverse strand");
1012 if (length > toRemove)
1014 endRange[1] -= toRemove;
1026 * Converts a list of [start, end] ranges to a single array of [start, end,
1032 public static int[] listToArray(List<int[]> ranges)
1034 int[] result = new int[ranges.size() * 2];
1036 for (int[] range : ranges)
1038 result[i++] = range[0];
1039 result[i++] = range[1];
1045 * Returns the maximal start-end positions in the given (ordered) list of
1046 * ranges which is overlapped by the given begin-end range, or null if there
1051 * if ranges is {[4, 8], [10, 12], [16, 19]}
1053 * findOverlap(ranges, 1, 20) == [4, 19]
1054 * findOverlap(ranges, 6, 11) == [6, 11]
1055 * findOverlap(ranges, 9, 15) == [10, 12]
1056 * findOverlap(ranges, 13, 15) == null
1064 protected static int[] findOverlap(List<int[]> ranges, final int begin,
1067 boolean foundStart = false;
1072 * traverse the ranges to find the first position (if any) >= begin,
1073 * and the last position (if any) <= end
1075 for (int[] range : ranges)
1079 if (range[0] >= begin)
1082 * first range that starts with, or follows, begin
1085 from = Math.max(range[0], begin);
1087 else if (range[1] >= begin)
1090 * first range that contains begin
1097 if (range[0] <= end)
1099 to = Math.min(end, range[1]);
1103 return foundStart && to >= from ? new int[] { from, to } : null;