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.
24 import jalview.analysis.AlignmentSorter;
25 import jalview.api.AlignViewportI;
26 import jalview.bin.Console;
27 import jalview.commands.CommandI;
28 import jalview.commands.EditCommand;
29 import jalview.commands.EditCommand.Action;
30 import jalview.commands.EditCommand.Edit;
31 import jalview.commands.OrderCommand;
32 import jalview.datamodel.AlignedCodonFrame;
33 import jalview.datamodel.AlignedCodonFrame.SequenceToSequenceMapping;
34 import jalview.datamodel.AlignmentI;
35 import jalview.datamodel.AlignmentOrder;
36 import jalview.datamodel.ColumnSelection;
37 import jalview.datamodel.HiddenColumns;
38 import jalview.datamodel.Mapping;
39 import jalview.datamodel.SearchResultMatchI;
40 import jalview.datamodel.SearchResults;
41 import jalview.datamodel.SearchResultsI;
42 import jalview.datamodel.Sequence;
43 import jalview.datamodel.SequenceGroup;
44 import jalview.datamodel.SequenceI;
46 import java.util.ArrayList;
47 import java.util.Arrays;
48 import java.util.HashMap;
49 import java.util.Iterator;
50 import java.util.List;
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);
368 for (SequenceI seq : mapTo.getAlignment().getSequences())
370 int mappedStartResidue = 0;
371 int mappedEndResidue = 0;
372 for (AlignedCodonFrame acf : codonFrames)
374 // rather than use acf.getCoveringMapping() we iterate through all
375 // mappings to make sure all CDS are selected for a protein
376 for (SequenceToSequenceMapping map : acf.getMappings())
378 if (map.covers(selected) && map.covers(seq))
381 * Found a sequence mapping. Locate the start/end mapped residues.
383 List<AlignedCodonFrame> mapping = Arrays
384 .asList(new AlignedCodonFrame[]
387 SearchResultsI sr = buildSearchResults(selected,
388 startResiduePos, mapping);
389 for (SearchResultMatchI m : sr.getResults())
391 mappedStartResidue = m.getStart();
392 mappedEndResidue = m.getEnd();
394 // locate end - allowing for adjustment of start range
395 sr = buildSearchResults(selected, endResiduePos, mapping);
396 for (SearchResultMatchI m : sr.getResults())
398 mappedStartResidue = Math.min(mappedStartResidue,
400 mappedEndResidue = Math.max(mappedEndResidue, m.getEnd());
404 * Find the mapped aligned columns, save the range. Note findIndex
405 * returns a base 1 position, SequenceGroup uses base 0
407 int mappedStartCol = seq.findIndex(mappedStartResidue) - 1;
408 minStartCol = minStartCol == -1 ? mappedStartCol
409 : Math.min(minStartCol, mappedStartCol);
410 int mappedEndCol = seq.findIndex(mappedEndResidue) - 1;
411 maxEndCol = maxEndCol == -1 ? mappedEndCol
412 : Math.max(maxEndCol, mappedEndCol);
413 mappedGroup.addSequence(seq, false);
420 mappedGroup.setStartRes(minStartCol < 0 ? 0 : minStartCol);
421 mappedGroup.setEndRes(maxEndCol < 0 ? 0 : maxEndCol);
426 * Returns an OrderCommand equivalent to the given one, but acting on mapped
427 * sequences as described by the mappings, or null if no mapping can be made.
430 * the original order command
432 * if true, the action is to undo the sort
434 * the alignment we are mapping to
436 * the mappings available
439 public static CommandI mapOrderCommand(OrderCommand command, boolean undo,
440 AlignmentI mapTo, List<AlignedCodonFrame> mappings)
442 SequenceI[] sortOrder = command.getSequenceOrder(undo);
443 List<SequenceI> mappedOrder = new ArrayList<>();
447 * Assumption: we are only interested in a cDNA/protein mapping; refactor in
448 * future if we want to support sorting (c)dna as (c)dna or protein as
451 boolean mappingToNucleotide = mapTo.isNucleotide();
452 for (SequenceI seq : sortOrder)
454 for (AlignedCodonFrame acf : mappings)
456 for (SequenceI seq2 : mapTo.getSequences())
459 * the corresponding peptide / CDS is the one for which there is
460 * a complete ('covering') mapping to 'seq'
462 SequenceI peptide = mappingToNucleotide ? seq2 : seq;
463 SequenceI cds = mappingToNucleotide ? seq : seq2;
464 SequenceToSequenceMapping s2s = acf.getCoveringMapping(cds,
468 mappedOrder.add(seq2);
477 * Return null if no mappings made.
485 * Add any unmapped sequences on the end of the sort in their original
488 if (j < mapTo.getHeight())
490 for (SequenceI seq : mapTo.getSequences())
492 if (!mappedOrder.contains(seq))
494 mappedOrder.add(seq);
500 * Have to sort the sequences before constructing the OrderCommand - which
501 * then resorts them?!?
503 final SequenceI[] mappedOrderArray = mappedOrder
504 .toArray(new SequenceI[mappedOrder.size()]);
505 SequenceI[] oldOrder = mapTo.getSequencesArray();
506 AlignmentSorter.sortBy(mapTo, new AlignmentOrder(mappedOrderArray));
507 final OrderCommand result = new OrderCommand(command.getDescription(),
513 * Returns a ColumnSelection in the 'mapTo' view which corresponds to the
514 * given selection in the 'mapFrom' view. We assume one is nucleotide, the
515 * other is protein (and holds the mappings from codons to protein residues).
522 public static void mapColumnSelection(ColumnSelection colsel,
523 HiddenColumns hiddencols, AlignViewportI mapFrom,
524 AlignViewportI mapTo, ColumnSelection newColSel,
525 HiddenColumns newHidden)
527 boolean targetIsNucleotide = mapTo.isNucleotide();
528 AlignViewportI protein = targetIsNucleotide ? mapFrom : mapTo;
529 List<AlignedCodonFrame> codonFrames = protein.getAlignment()
534 return; // mappedColumns;
537 char fromGapChar = mapFrom.getAlignment().getGapCharacter();
540 * For each mapped column, find the range of columns that residues in that
543 List<SequenceI> fromSequences = mapFrom.getAlignment().getSequences();
544 List<SequenceI> toSequences = mapTo.getAlignment().getSequences();
546 for (Integer sel : colsel.getSelected())
548 mapColumn(sel.intValue(), codonFrames, newColSel, fromSequences,
549 toSequences, fromGapChar);
552 Iterator<int[]> regions = hiddencols.iterator();
553 while (regions.hasNext())
555 mapHiddenColumns(regions.next(), codonFrames, newHidden,
557 toSequences, fromGapChar);
559 return; // mappedColumns;
563 * Helper method that maps a [start, end] hidden column range to its mapped
568 * @param mappedColumns
569 * @param fromSequences
573 protected static void mapHiddenColumns(int[] hidden,
574 List<AlignedCodonFrame> mappings, HiddenColumns mappedColumns,
575 List<SequenceI> fromSequences, List<SequenceI> toSequences,
578 for (int col = hidden[0]; col <= hidden[1]; col++)
580 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
581 toSequences, fromGapChar);
584 * Add the range of hidden columns to the mapped selection (converting
587 if (mappedTo != null)
589 mappedColumns.hideColumns(mappedTo[0] - 1, mappedTo[1] - 1);
595 * Helper method to map one column selection
598 * the column number (base 0)
600 * the sequence mappings
601 * @param mappedColumns
602 * the mapped column selections to add to
603 * @param fromSequences
607 protected static void mapColumn(int col, List<AlignedCodonFrame> mappings,
608 ColumnSelection mappedColumns, List<SequenceI> fromSequences,
609 List<SequenceI> toSequences, char fromGapChar)
611 int[] mappedTo = findMappedColumns(col, mappings, fromSequences,
612 toSequences, fromGapChar);
615 * Add the range of mapped columns to the mapped selection (converting
616 * base 1 to base 0). Note that this may include intron-only regions which
617 * lie between the start and end ranges of the selection.
619 if (mappedTo != null)
621 for (int i = mappedTo[0]; i <= mappedTo[1]; i++)
623 mappedColumns.addElement(i - 1);
629 * Helper method to find the range of columns mapped to from one column.
630 * Returns the maximal range of columns mapped to from all sequences in the
631 * source column, or null if no mappings were found.
635 * @param fromSequences
640 protected static int[] findMappedColumns(int col,
641 List<AlignedCodonFrame> mappings, List<SequenceI> fromSequences,
642 List<SequenceI> toSequences, char fromGapChar)
644 int[] mappedTo = new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
645 boolean found = false;
648 * For each sequence in the 'from' alignment
650 for (SequenceI fromSeq : fromSequences)
653 * Ignore gaps (unmapped anyway)
655 if (fromSeq.getCharAt(col) == fromGapChar)
661 * Get the residue position and find the mapped position.
663 int residuePos = fromSeq.findPosition(col);
664 SearchResultsI sr = buildSearchResults(fromSeq, residuePos, mappings);
665 for (SearchResultMatchI m : sr.getResults())
667 int mappedStartResidue = m.getStart();
668 int mappedEndResidue = m.getEnd();
669 SequenceI mappedSeq = m.getSequence();
672 * Locate the aligned sequence whose dataset is mappedSeq. TODO a
673 * datamodel that can do this efficiently.
675 for (SequenceI toSeq : toSequences)
677 if (toSeq.getDatasetSequence() == mappedSeq
678 && mappedStartResidue >= toSeq.getStart()
679 && mappedEndResidue <= toSeq.getEnd())
681 int mappedStartCol = toSeq.findIndex(mappedStartResidue);
682 int mappedEndCol = toSeq.findIndex(mappedEndResidue);
683 mappedTo[0] = Math.min(mappedTo[0], mappedStartCol);
684 mappedTo[1] = Math.max(mappedTo[1], mappedEndCol);
687 // note: remove break if we ever want to map one to many sequences
692 return found ? mappedTo : null;
696 * Returns the mapped codon or codons for a given aligned sequence column
700 * an aligned peptide sequence
702 * an aligned column position (base 0)
704 * a set of codon mappings
705 * @return the bases of the mapped codon(s) in the cDNA dataset sequence(s),
706 * or an empty list if none found
708 public static List<char[]> findCodonsFor(SequenceI seq, int col,
709 List<AlignedCodonFrame> mappings)
711 List<char[]> result = new ArrayList<>();
712 int dsPos = seq.findPosition(col);
713 for (AlignedCodonFrame mapping : mappings)
715 if (mapping.involvesSequence(seq))
717 List<char[]> codons = mapping
718 .getMappedCodons(seq.getDatasetSequence(), dsPos);
721 result.addAll(codons);
729 * Converts a series of [start, end] range pairs into an array of individual
730 * positions. This also caters for 'reverse strand' (start > end) cases.
735 public static int[] flattenRanges(int[] ranges)
738 * Count how many positions altogether
741 for (int i = 0; i < ranges.length - 1; i += 2)
743 count += Math.abs(ranges[i + 1] - ranges[i]) + 1;
746 int[] result = new int[count];
748 for (int i = 0; i < ranges.length - 1; i += 2)
750 int from = ranges[i];
751 final int to = ranges[i + 1];
752 int step = from <= to ? 1 : -1;
757 } while (from != to + step);
763 * Returns a list of any mappings that are from or to the given (aligned or
770 public static List<AlignedCodonFrame> findMappingsForSequence(
771 SequenceI sequence, List<AlignedCodonFrame> mappings)
773 return findMappingsForSequenceAndOthers(sequence, mappings, null);
777 * Returns a list of any mappings that are from or to the given (aligned or
778 * dataset) sequence, optionally limited to mappings involving one of a given
786 public static List<AlignedCodonFrame> findMappingsForSequenceAndOthers(
787 SequenceI sequence, List<AlignedCodonFrame> mappings,
788 List<SequenceI> filterList)
790 List<AlignedCodonFrame> result = new ArrayList<>();
791 if (sequence == null || mappings == null)
795 for (AlignedCodonFrame mapping : mappings)
797 if (mapping.involvesSequence(sequence))
799 if (filterList != null)
801 for (SequenceI otherseq : filterList)
803 SequenceI otherDataset = otherseq.getDatasetSequence();
804 if (otherseq == sequence
805 || otherseq == sequence.getDatasetSequence()
806 || (otherDataset != null && (otherDataset == sequence
807 || otherDataset == sequence
808 .getDatasetSequence())))
810 // skip sequences in subset which directly relate to sequence
813 if (mapping.involvesSequence(otherseq))
815 // selected a mapping contained in subselect alignment
831 * Returns the total length of the supplied ranges, which may be as single
832 * [start, end] or multiple [start, end, start, end ...]
837 public static int getLength(List<int[]> ranges)
844 for (int[] range : ranges)
846 if (range.length % 2 != 0)
849 "Error unbalance start/end ranges: " + ranges.toString());
852 for (int i = 0; i < range.length - 1; i += 2)
854 length += Math.abs(range[i + 1] - range[i]) + 1;
861 * Answers true if any range includes the given value
867 public static boolean contains(List<int[]> ranges, int value)
873 for (int[] range : ranges)
875 if (range[1] >= range[0] && value >= range[0] && value <= range[1])
878 * value within ascending range
882 if (range[1] < range[0] && value <= range[0] && value >= range[1])
885 * value within descending range
894 * Removes a specified number of positions from the start of a ranges list.
895 * For example, could be used to adjust cds ranges to allow for an incomplete
896 * start codon. Subranges are removed completely, or their start positions
897 * adjusted, until the required number of positions has been removed from the
898 * range. Reverse strand ranges are supported. The input array is not
903 * an array of [start, end, start, end...] positions
904 * @return a new array with the first removeCount positions removed
906 public static int[] removeStartPositions(int removeCount,
909 if (removeCount <= 0)
914 int[] copy = Arrays.copyOf(ranges, ranges.length);
917 for (int x = 0; x < copy.length && sxpos == -1; x += 2)
919 cdspos += Math.abs(copy[x + 1] - copy[x]) + 1;
920 if (removeCount < cdspos)
923 * we have removed enough, time to finish
928 * increment start of first exon, or decrement if reverse strand
930 if (copy[x] <= copy[x + 1])
932 copy[x] = copy[x + 1] - cdspos + removeCount + 1;
936 copy[x] = copy[x + 1] + cdspos - removeCount - 1;
945 * we dropped at least one entire sub-range - compact the array
947 int[] nxon = new int[copy.length - sxpos];
948 System.arraycopy(copy, sxpos, nxon, 0, copy.length - sxpos);
955 * Answers true if range's start-end positions include those of queryRange,
956 * where either range might be in reverse direction, else false
961 * a candidate subrange of range (start2-end2)
964 public static boolean rangeContains(int[] range, int[] queryRange)
966 if (range == null || queryRange == null || range.length != 2
967 || queryRange.length != 2)
975 int min = Math.min(range[0], range[1]);
976 int max = Math.max(range[0], range[1]);
978 return (min <= queryRange[0] && max >= queryRange[0]
979 && min <= queryRange[1] && max >= queryRange[1]);
983 * Removes the specified number of positions from the given ranges. Provided
984 * to allow a stop codon to be stripped from a CDS sequence so that it matches
985 * the peptide translation length.
989 * a list of (single) [start, end] ranges
992 public static void removeEndPositions(int positions, List<int[]> ranges)
994 int toRemove = positions;
995 Iterator<int[]> it = new ReverseListIterator<>(ranges);
998 int[] endRange = it.next();
999 if (endRange.length != 2)
1002 * not coded for [start1, end1, start2, end2, ...]
1005 "MappingUtils.removeEndPositions doesn't handle multiple ranges");
1009 int length = endRange[1] - endRange[0] + 1;
1013 * not coded for a reverse strand range (end < start)
1016 "MappingUtils.removeEndPositions doesn't handle reverse strand");
1019 if (length > toRemove)
1021 endRange[1] -= toRemove;
1032 * Adds the given range to a list of ranges. If the new range just extends
1033 * existing ranges, the current endpoint is updated instead.
1038 public static void addRange(int[] range, List<int[]> addTo)
1041 * list is empty - add to it!
1043 if (addTo.size() == 0)
1049 int[] last = addTo.get(addTo.size() - 1);
1050 boolean lastForward = last[1] >= last[0];
1051 boolean newForward = range[1] >= range[0];
1054 * contiguous range in the same direction - just update endpoint
1056 if (lastForward == newForward && last[1] == range[0])
1063 * next range starts at +1 in forward sense - update endpoint
1065 if (lastForward && newForward && range[0] == last[1] + 1)
1072 * next range starts at -1 in reverse sense - update endpoint
1074 if (!lastForward && !newForward && range[0] == last[1] - 1)
1081 * just add the new range
1087 * Converts a list of {@code start-end} ranges to a single array of
1088 * {@code start1, end1, start2, ... } ranges
1093 public static int[] rangeListToArray(List<int[]> ranges)
1095 int rangeCount = ranges.size();
1096 int[] result = new int[rangeCount * 2];
1098 for (int i = 0; i < rangeCount; i++)
1100 int[] range = ranges.get(i);
1101 result[j++] = range[0];
1102 result[j++] = range[1];
1108 * Returns the maximal start-end positions in the given (ordered) list of
1109 * ranges which is overlapped by the given begin-end range, or null if there
1114 * if ranges is {[4, 8], [10, 12], [16, 19]}
1116 * findOverlap(ranges, 1, 20) == [4, 19]
1117 * findOverlap(ranges, 6, 11) == [6, 11]
1118 * findOverlap(ranges, 9, 15) == [10, 12]
1119 * findOverlap(ranges, 13, 15) == null
1127 protected static int[] findOverlap(List<int[]> ranges, final int begin,
1130 boolean foundStart = false;
1135 * traverse the ranges to find the first position (if any) >= begin,
1136 * and the last position (if any) <= end
1138 for (int[] range : ranges)
1142 if (range[0] >= begin)
1145 * first range that starts with, or follows, begin
1148 from = Math.max(range[0], begin);
1150 else if (range[1] >= begin)
1153 * first range that contains begin
1160 if (range[0] <= end)
1162 to = Math.min(end, range[1]);
1166 return foundStart && to >= from ? new int[] { from, to } : null;