JAL-3725 helper methods for computing mapped feature range overlap

[jalview.git] / src / jalview / util / MappingUtils.java

diff --git a/src/jalview/util/MappingUtils.java b/src/jalview/util/MappingUtils.java
index 9c5c109..33decb4 100644 (file)
--- a/src/jalview/util/MappingUtils.java
+++ b/src/jalview/util/MappingUtils.java
@@ -20,8 +20,16 @@
  */
 package jalview.util;
 
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
 import jalview.analysis.AlignmentSorter;
 import jalview.api.AlignViewportI;
+import jalview.bin.Cache;
 import jalview.commands.CommandI;
 import jalview.commands.EditCommand;
 import jalview.commands.EditCommand.Action;
@@ -39,13 +47,6 @@ import jalview.datamodel.Sequence;
 import jalview.datamodel.SequenceGroup;
 import jalview.datamodel.SequenceI;
 
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-
 /**
  * Helper methods for manipulations involving sequence mappings.
  * 
@@ -78,7 +79,7 @@ public final class MappingUtils
       action = action.getUndoAction();
     }
     // TODO write this
-    System.err.println("MappingUtils.mapCutOrPaste not yet implemented");
+    Cache.log.error("MappingUtils.mapCutOrPaste not yet implemented");
   }
 
   /**
@@ -542,10 +543,11 @@ public final class MappingUtils
               toSequences, fromGapChar);
     }
 
-    for (int[] hidden : hiddencols.getHiddenColumnsCopy())
+    Iterator<int[]> regions = hiddencols.iterator();
+    while (regions.hasNext())
     {
-      mapHiddenColumns(hidden, codonFrames, newHidden, fromSequences,
-              toSequences, fromGapChar);
+      mapHiddenColumns(regions.next(), codonFrames, newHidden,
+              fromSequences, toSequences, fromGapChar);
     }
     return; // mappedColumns;
   }
@@ -834,7 +836,7 @@ public final class MappingUtils
     {
       if (range.length % 2 != 0)
       {
-        System.err.println(
+        Cache.log.error(
                 "Error unbalance start/end ranges: " + ranges.toString());
         return 0;
       }
@@ -941,6 +943,34 @@ public final class MappingUtils
   }
 
   /**
+   * Answers true if range's start-end positions include those of queryRange,
+   * where either range might be in reverse direction, else false
+   * 
+   * @param range
+   *          a start-end range
+   * @param queryRange
+   *          a candidate subrange of range (start2-end2)
+   * @return
+   */
+  public static boolean rangeContains(int[] range, int[] queryRange)
+  {
+    if (range == null || queryRange == null || range.length != 2
+            || queryRange.length != 2)
+    {
+      /*
+       * invalid arguments
+       */
+      return false;
+    }
+
+    int min = Math.min(range[0], range[1]);
+    int max = Math.max(range[0], range[1]);
+
+    return (min <= queryRange[0] && max >= queryRange[0]
+            && min <= queryRange[1] && max >= queryRange[1]);
+  }
+
+  /**
    * Removes the specified number of positions from the given ranges. Provided
    * to allow a stop codon to be stripped from a CDS sequence so that it matches
    * the peptide translation length.
@@ -950,8 +980,7 @@ public final class MappingUtils
    *          a list of (single) [start, end] ranges
    * @return
    */
-  public static void removeEndPositions(int positions,
-          List<int[]> ranges)
+  public static void removeEndPositions(int positions, List<int[]> ranges)
   {
     int toRemove = positions;
     Iterator<int[]> it = new ReverseListIterator<>(ranges);
@@ -963,8 +992,8 @@ public final class MappingUtils
         /*
          * not coded for [start1, end1, start2, end2, ...]
          */
-        System.err
-                .println("MappingUtils.removeEndPositions doesn't handle multiple  ranges");
+        Cache.log.error(
+                "MappingUtils.removeEndPositions doesn't handle multiple  ranges");
         return;
       }
 
@@ -974,8 +1003,8 @@ public final class MappingUtils
         /*
          * not coded for a reverse strand range (end < start)
          */
-        System.err
-                .println("MappingUtils.removeEndPositions doesn't handle reverse strand");
+        Cache.log.error(
+                "MappingUtils.removeEndPositions doesn't handle reverse strand");
         return;
       }
       if (length > toRemove)
@@ -990,4 +1019,87 @@ public final class MappingUtils
       }
     }
   }
+
+  /**
+   * Converts a list of {@code start-end} ranges to a single array of
+   * {@code start1, end1, start2, ... } ranges
+   * 
+   * @param ranges
+   * @return
+   */
+  public static int[] rangeListToArray(List<int[]> ranges)
+  {
+    int rangeCount = ranges.size();
+    int[] result = new int[rangeCount * 2];
+    int j = 0;
+    for (int i = 0; i < rangeCount; i++)
+    {
+      int[] range = ranges.get(i);
+      result[j++] = range[0];
+      result[j++] = range[1];
+    }
+    return result;
+  }
+
+  /*
+   * Returns the maximal start-end positions in the given (ordered) list of
+   * ranges which is overlapped by the given begin-end range, or null if there
+   * is no overlap.
+   * 
+   * <pre>
+   * Examples:
+   *   if ranges is {[4, 8], [10, 12], [16, 19]}
+   * then
+   *   findOverlap(ranges, 1, 20) == [4, 19]
+   *   findOverlap(ranges, 6, 11) == [6, 11]
+   *   findOverlap(ranges, 9, 15) == [10, 12]
+   *   findOverlap(ranges, 13, 15) == null
+   * </pre>
+   * 
+   * @param ranges
+   * @param begin
+   * @param end
+   * @return
+   */
+  protected static int[] findOverlap(List<int[]> ranges, final int begin,
+          final int end)
+  {
+    boolean foundStart = false;
+    int from = 0;
+    int to = 0;
+
+    /*
+     * traverse the ranges to find the first position (if any) >= begin,
+     * and the last position (if any) <= end
+     */
+    for (int[] range : ranges)
+    {
+      if (!foundStart)
+      {
+        if (range[0] >= begin)
+        {
+          /*
+           * first range that starts with, or follows, begin
+           */
+          foundStart = true;
+          from = Math.max(range[0], begin);
+        }
+        else if (range[1] >= begin)
+        {
+          /*
+           * first range that contains begin
+           */
+          foundStart = true;
+          from = begin;
+        }
+      }
+
+      if (range[0] <= end)
+      {
+        to = Math.min(end, range[1]);
+      }
+    }
+
+    return foundStart && to >= from ? new int[] { from, to } : null;
+  }
 }