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.Mapping;
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)))
347 * If this sequence is only gaps in the selected range, skip it
349 if (firstUngappedPos > selectionEndRes)
354 int lastUngappedPos = selectionEndRes;
355 while (lastUngappedPos >= selectionStartRes
356 && Comparison.isGap(selected.getCharAt(lastUngappedPos)))
362 * Find the selected start/end residue positions in sequence
364 int startResiduePos = selected.findPosition(firstUngappedPos);
365 int endResiduePos = selected.findPosition(lastUngappedPos);
366 for (SequenceI seq : mapTo.getAlignment().getSequences())
368 int mappedStartResidue = 0;
369 int mappedEndResidue = 0;
371 for (AlignedCodonFrame acf : codonFrames)
373 Mapping map = acf.getMappingBetween(seq, selected);
377 * Found a sequence mapping. Locate the start/end mapped residues.
379 List<AlignedCodonFrame> mapping = Arrays
380 .asList(new AlignedCodonFrame[]
382 SearchResultsI sr = buildSearchResults(selected,
383 startResiduePos, mapping);
384 for (SearchResultMatchI m : sr.getResults())
386 mappedStartResidue = m.getStart();
387 mappedEndResidue = m.getEnd();
389 sr = buildSearchResults(selected, endResiduePos, mapping);
390 for (SearchResultMatchI m : sr.getResults())
392 mappedStartResidue = Math.min(mappedStartResidue,
394 mappedEndResidue = Math.max(mappedEndResidue, m.getEnd());
398 * Find the mapped aligned columns, save the range. Note findIndex
399 * returns a base 1 position, SequenceGroup uses base 0
401 int mappedStartCol = seq.findIndex(mappedStartResidue) - 1;
402 minStartCol = minStartCol == -1 ? mappedStartCol
403 : Math.min(minStartCol, mappedStartCol);
404 int mappedEndCol = seq.findIndex(mappedEndResidue) - 1;
405 maxEndCol = maxEndCol == -1 ? mappedEndCol
406 : Math.max(maxEndCol, mappedEndCol);
407 mappedGroup.addSequence(seq, false);
413 mappedGroup.setStartRes(minStartCol < 0 ? 0 : minStartCol);
414 mappedGroup.setEndRes(maxEndCol < 0 ? 0 : maxEndCol);
419 * Returns an OrderCommand equivalent to the given one, but acting on mapped
420 * sequences as described by the mappings, or null if no mapping can be made.
423 * the original order command
425 * if true, the action is to undo the sort
427 * the alignment we are mapping to
429 * the mappings available
432 public static CommandI mapOrderCommand(OrderCommand command, boolean undo,
433 AlignmentI mapTo, List<AlignedCodonFrame> mappings)
435 SequenceI[] sortOrder = command.getSequenceOrder(undo);
436 List<SequenceI> mappedOrder = new ArrayList<>();
440 * Assumption: we are only interested in a cDNA/protein mapping; refactor in
441 * future if we want to support sorting (c)dna as (c)dna or protein as
444 boolean mappingToNucleotide = mapTo.isNucleotide();
445 for (SequenceI seq : sortOrder)
447 for (AlignedCodonFrame acf : mappings)
449 SequenceI mappedSeq = mappingToNucleotide ? acf.getDnaForAaSeq(seq)
450 : acf.getAaForDnaSeq(seq);
451 if (mappedSeq != null)
453 for (SequenceI seq2 : mapTo.getSequences())
455 if (seq2.getDatasetSequence() == mappedSeq)
457 mappedOrder.add(seq2);
467 * Return null if no mappings made.
475 * Add any unmapped sequences on the end of the sort in their original
478 if (j < mapTo.getHeight())
480 for (SequenceI seq : mapTo.getSequences())
482 if (!mappedOrder.contains(seq))
484 mappedOrder.add(seq);
490 * Have to sort the sequences before constructing the OrderCommand - which
491 * then resorts them?!?
493 final SequenceI[] mappedOrderArray = mappedOrder
494 .toArray(new SequenceI[mappedOrder.size()]);
495 SequenceI[] oldOrder = mapTo.getSequencesArray();
496 AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
497 final OrderCommand result = new OrderCommand(command.getDescription(),
503 * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
504 * given selection in the 'mapFrom' view. We assume one is nucleotide, the
505 * other is protein (and holds the mappings from codons to protein residues).
512 public static void mapColumnSelection(ColumnSelection colsel,
513 HiddenColumns hiddencols, AlignViewportI mapFrom,
514 AlignViewportI mapTo, ColumnSelection newColSel,
515 HiddenColumns newHidden)
517 boolean targetIsNucleotide = mapTo.isNucleotide();
518 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
519 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
524 return; // mappedColumns;
527 char fromGapChar = mapFrom.getAlignment().getGapCharacter();
530 * For each mapped column, find the range of columns that residues in that
533 List<SequenceI> fromSequences = mapFrom.getAlignment().getSequences();
534 List<SequenceI> toSequences = mapTo.getAlignment().getSequences();
536 for (Integer sel : colsel.getSelected())
538 mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences,
539 toSequences, fromGapChar);
542 Iterator<int[]> regions = hiddencols.iterator();
543 while (regions.hasNext())
545 mapHiddenColumns(regions.next(), codonFrames, newHidden,
546 fromSequences, toSequences, fromGapChar);
548 return; // mappedColumns;
552 * Helper method that maps a [start, end] hidden column range to its mapped
557 * @param mappedColumns
558 * @param fromSequences
562 protected static void mapHiddenColumns(int[] hidden,
563 List<AlignedCodonFrame> mappings, HiddenColumns mappedColumns,
564 List<SequenceI> fromSequences, List<SequenceI> toSequences,
567 for (int col = hidden[0]; col <= hidden[1]; col++)
569 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
570 toSequences, fromGapChar);
573 * Add the range of hidden columns to the mapped selection (converting
576 if (mappedTo != null)
578 mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1);
584 * Helper method to map one column selection
587 * the column number (base 0)
589 * the sequence mappings
590 * @param mappedColumns
591 * the mapped column selections to add to
592 * @param fromSequences
596 protected static void mapColumn(int col, List<AlignedCodonFrame> mappings,
597 ColumnSelection mappedColumns, List<SequenceI> fromSequences,
598 List<SequenceI> toSequences, char fromGapChar)
600 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
601 toSequences, fromGapChar);
604 * Add the range of mapped columns to the mapped selection (converting
605 * base 1 to base 0). Note that this may include intron-only regions which
606 * lie between the start and end ranges of the selection.
608 if (mappedTo != null)
610 for (int i = mappedTo[0]; i <= mappedTo[1]; i++)
612 mappedColumns.addElement(i - 1);
618 * Helper method to find the range of columns mapped to from one column.
619 * Returns the maximal range of columns mapped to from all sequences in the
620 * source column, or null if no mappings were found.
624 * @param fromSequences
629 protected static int[] findMappedColumns(int col,
630 List<AlignedCodonFrame> mappings, List<SequenceI> fromSequences,
631 List<SequenceI> toSequences, char fromGapChar)
633 int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
634 boolean found = false;
637 * For each sequence in the 'from' alignment
639 for (SequenceI fromSeq : fromSequences)
642 * Ignore gaps (unmapped anyway)
644 if (fromSeq.getCharAt(col) == fromGapChar)
650 * Get the residue position and find the mapped position.
652 int residuePos = fromSeq.findPosition(col);
653 SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings);
654 for (SearchResultMatchI m : sr.getResults())
656 int mappedStartResidue = m.getStart();
657 int mappedEndResidue = m.getEnd();
658 SequenceI mappedSeq = m.getSequence();
661 * Locate the aligned sequence whose dataset is mappedSeq. TODO a
662 * datamodel that can do this efficiently.
664 for (SequenceI toSeq : toSequences)
666 if (toSeq.getDatasetSequence() == mappedSeq)
668 int mappedStartCol = toSeq.findIndex(mappedStartResidue);
669 int mappedEndCol = toSeq.findIndex(mappedEndResidue);
670 mappedTo[0] = Math.min(mappedTo[0], mappedStartCol);
671 mappedTo[1] = Math.max(mappedTo[1], mappedEndCol);
674 // note: remove break if we ever want to map one to many sequences
679 return found ? mappedTo : null;
683 * Returns the mapped codon or codons for a given aligned sequence column
687 * an aligned peptide sequence
689 * an aligned column position (base 0)
691 * a set of codon mappings
692 * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s),
693 * or an empty list if none found
695 public static List<char[]> findCodonsFor(SequenceI seq, int col,
696 List<AlignedCodonFrame> mappings)
698 List<char[]> result = new ArrayList<>();
699 int dsPos = seq.findPosition(col);
700 for (AlignedCodonFrame mapping : mappings)
702 if (mapping.involvesSequence(seq))
704 List<char[]> codons = mapping
705 .getMappedCodons(seq.getDatasetSequence(), dsPos);
708 result.addAll(codons);
716 * Converts a series of [start, end] range pairs into an array of individual
717 * positions. This also caters for 'reverse strand' (start > end) cases.
722 public static int[] flattenRanges(int[] ranges)
725 * Count how many positions altogether
728 for (int i = 0; i < ranges.length - 1; i += 2)
730 count += Math.abs(ranges[i + 1] - ranges[i]) + 1;
733 int[] result = new int[count];
735 for (int i = 0; i < ranges.length - 1; i += 2)
737 int from = ranges[i];
738 final int to = ranges[i + 1];
739 int step = from <= to ? 1 : -1;
744 } while (from != to + step);
750 * Returns a list of any mappings that are from or to the given (aligned or
757 public static List<AlignedCodonFrame> findMappingsForSequence(
758 SequenceI sequence, List<AlignedCodonFrame> mappings)
760 return findMappingsForSequenceAndOthers(sequence, mappings, null);
764 * Returns a list of any mappings that are from or to the given (aligned or
765 * dataset) sequence, optionally limited to mappings involving one of a given
773 public static List<AlignedCodonFrame> findMappingsForSequenceAndOthers(
774 SequenceI sequence, List<AlignedCodonFrame> mappings,
775 List<SequenceI> filterList)
777 List<AlignedCodonFrame> result = new ArrayList<>();
778 if (sequence == null || mappings == null)
782 for (AlignedCodonFrame mapping : mappings)
784 if (mapping.involvesSequence(sequence))
786 if (filterList != null)
788 for (SequenceI otherseq : filterList)
790 SequenceI otherDataset = otherseq.getDatasetSequence();
791 if (otherseq == sequence
792 || otherseq == sequence.getDatasetSequence()
793 || (otherDataset != null && (otherDataset == sequence
794 || otherDataset == sequence
795 .getDatasetSequence())))
797 // skip sequences in subset which directly relate to sequence
800 if (mapping.involvesSequence(otherseq))
802 // selected a mapping contained in subselect alignment
818 * Returns the total length of the supplied ranges, which may be as single
819 * [start, end] or multiple [start, end, start, end ...]
824 public static int getLength(List<int[]> ranges)
831 for (int[] range : ranges)
833 if (range.length % 2 != 0)
836 "Error unbalance start/end ranges: " + ranges.toString());
839 for (int i = 0; i < range.length - 1; i += 2)
841 length += Math.abs(range[i + 1] - range[i]) + 1;
848 * Answers true if any range includes the given value
854 public static boolean contains(List<int[]> ranges, int value)
860 for (int[] range : ranges)
862 if (range[1] >= range[0] && value >= range[0] && value <= range[1])
865 * value within ascending range
869 if (range[1] < range[0] && value <= range[0] && value >= range[1])
872 * value within descending range
881 * Removes a specified number of positions from the start of a ranges list.
882 * For example, could be used to adjust cds ranges to allow for an incomplete
883 * start codon. Subranges are removed completely, or their start positions
884 * adjusted, until the required number of positions has been removed from the
885 * range. Reverse strand ranges are supported. The input array is not
890 * an array of [start, end, start, end...] positions
891 * @return a new array with the first removeCount positions removed
893 public static int[] removeStartPositions(int removeCount,
896 if (removeCount <= 0)
901 int[] copy = Arrays.copyOf(ranges, ranges.length);
904 for (int x = 0; x < copy.length && sxpos == -1; x += 2)
906 cdspos += Math.abs(copy[x + 1] - copy[x]) + 1;
907 if (removeCount < cdspos)
910 * we have removed enough, time to finish
915 * increment start of first exon, or decrement if reverse strand
917 if (copy[x] <= copy[x + 1])
919 copy[x] = copy[x + 1] - cdspos + removeCount + 1;
923 copy[x] = copy[x + 1] + cdspos - removeCount - 1;
932 * we dropped at least one entire sub-range - compact the array
934 int[] nxon = new int[copy.length - sxpos];
935 System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos);
942 * Answers true if range's start-end positions include those of queryRange,
943 * where either range might be in reverse direction, else false
948 * a candidate subrange of range (start2-end2)
951 public static boolean rangeContains(int[] range, int[] queryRange)
953 if (range == null || queryRange == null || range.length != 2
954 || queryRange.length != 2)
962 int min = Math.min(range[0], range[1]);
963 int max = Math.max(range[0], range[1]);
965 return (min <= queryRange[0] && max >= queryRange[0]
966 && min <= queryRange[1] && max >= queryRange[1]);
970 * Removes the specified number of positions from the given ranges. Provided
971 * to allow a stop codon to be stripped from a CDS sequence so that it matches
972 * the peptide translation length.
976 * a list of (single) [start, end] ranges
979 public static void removeEndPositions(int positions, List<int[]> ranges)
981 int toRemove = positions;
982 Iterator<int[]> it = new ReverseListIterator<>(ranges);
985 int[] endRange = it.next();
986 if (endRange.length != 2)
989 * not coded for [start1, end1, start2, end2, ...]
992 "MappingUtils.removeEndPositions doesn't handle multiple ranges");
996 int length = endRange[1] - endRange[0] + 1;
1000 * not coded for a reverse strand range (end < start)
1003 "MappingUtils.removeEndPositions doesn't handle reverse strand");
1006 if (length > toRemove)
1008 endRange[1] -= toRemove;
1020 * Converts a list of {@code start-end} ranges to a single array of
1021 * {@code start1, end1, start2, ... } ranges
1026 public static int[] rangeListToArray(List<int[]> ranges)
1028 int rangeCount = ranges.size();
1029 int[] result = new int[rangeCount * 2];
1031 for (int i = 0; i < rangeCount; i++)
1033 int[] range = ranges.get(i);
1034 result[j++] = range[0];
1035 result[j++] = range[1];
1041 * Returns the maximal start-end positions in the given (ordered) list of
1042 * ranges which is overlapped by the given begin-end range, or null if there
1047 * if ranges is {[4, 8], [10, 12], [16, 19]}
1049 * findOverlap(ranges, 1, 20) == [4, 19]
1050 * findOverlap(ranges, 6, 11) == [6, 11]
1051 * findOverlap(ranges, 9, 15) == [10, 12]
1052 * findOverlap(ranges, 13, 15) == null
1060 protected static int[] findOverlap(List<int[]> ranges, final int begin,
1063 boolean foundStart = false;
1068 * traverse the ranges to find the first position (if any) >= begin,
1069 * and the last position (if any) <= end
1071 for (int[] range : ranges)
1075 if (range[0] >= begin)
1078 * first range that starts with, or follows, begin
1081 from = Math.max(range[0], begin);
1083 else if (range[1] >= begin)
1086 * first range that contains begin
1093 if (range[0] <= end)
1095 to = Math.min(end, range[1]);
1099 return foundStart && to >= from ? new int[] { from, to } : null;