JAL-3751 only merge strictly contiguous ranges of mappings
authorgmungoc <g.m.carstairs@dundee.ac.uk>
Thu, 24 Sep 2020 10:55:20 +0000 (11:55 +0100)
committerJim Procter <jprocter@issues.jalview.org>
Thu, 22 Oct 2020 14:43:32 +0000 (15:43 +0100)
src/jalview/util/MapList.java
test/jalview/util/MapListTest.java
test/jalview/util/MappingUtilsTest.java

index 731e976..36fb450 100644 (file)
@@ -209,8 +209,7 @@ public class MapList
 
   /**
    * Constructor given from and to ranges as [start1, end1, start2, end2,...].
-   * If any end is equal to the next start, the ranges will be merged. There is
-   * no validation check that the ranges do not overlap each other.
+   * There is no validation check that the ranges do not overlap each other.
    * 
    * @param from
    *          contiguous regions as [start1, end1, start2, end2, ...]
@@ -228,7 +227,6 @@ public class MapList
     this.toRatio = toRatio;
     fromLowest = Integer.MAX_VALUE;
     fromHighest = Integer.MIN_VALUE;
-    int added = 0;
 
     for (int i = 0; i < from.length; i += 2)
     {
@@ -238,36 +236,16 @@ public class MapList
        */
       fromLowest = Math.min(fromLowest, Math.min(from[i], from[i + 1]));
       fromHighest = Math.max(fromHighest, Math.max(from[i], from[i + 1]));
-      if (added > 0 && from[i] == fromShifts.get(added - 1)[1])
-      {
-        /*
-         * this range starts where the last ended - just extend it
-         */
-        fromShifts.get(added - 1)[1] = from[i + 1];
-      }
-      else
-      {
-        fromShifts.add(new int[] { from[i], from[i + 1] });
-        added++;
-      }
+      fromShifts.add(new int[] { from[i], from[i + 1] });
     }
 
     toLowest = Integer.MAX_VALUE;
     toHighest = Integer.MIN_VALUE;
-    added = 0;
     for (int i = 0; i < to.length; i += 2)
     {
       toLowest = Math.min(toLowest, Math.min(to[i], to[i + 1]));
       toHighest = Math.max(toHighest, Math.max(to[i], to[i + 1]));
-      if (added > 0 && to[i] == toShifts.get(added - 1)[1])
-      {
-        toShifts.get(added - 1)[1] = to[i + 1];
-      }
-      else
-      {
-        toShifts.add(new int[] { to[i], to[i + 1] });
-        added++;
-      }
+      toShifts.add(new int[] { to[i], to[i + 1] });
     }
   }
 
@@ -330,9 +308,8 @@ public class MapList
       if (range.length != 2)
       {
         // throw new IllegalArgumentException(range);
-        System.err.println(
-                "Invalid format for fromRange " + Arrays.toString(range)
-                + " may cause errors");
+        System.err.println("Invalid format for fromRange "
+                + Arrays.toString(range) + " may cause errors");
       }
       fromLowest = Math.min(fromLowest, Math.min(range[0], range[1]));
       fromHighest = Math.max(fromHighest, Math.max(range[0], range[1]));
@@ -346,8 +323,7 @@ public class MapList
       {
         // throw new IllegalArgumentException(range);
         System.err.println("Invalid format for toRange "
-                + Arrays.toString(range)
-                + " may cause errors");
+                + Arrays.toString(range) + " may cause errors");
       }
       toLowest = Math.min(toLowest, Math.min(range[0], range[1]));
       toHighest = Math.max(toHighest, Math.max(range[0], range[1]));
@@ -357,6 +333,16 @@ public class MapList
   /**
    * Consolidates a list of ranges so that any contiguous ranges are merged.
    * This assumes the ranges are already in start order (does not sort them).
+   * <p>
+   * The main use case for this method is when mapping cDNA sequence to its
+   * protein product, based on CDS feature ranges which derive from spliced
+   * exons, but are contiguous on the cDNA sequence. For example 
+   * <pre>
+   *   CDS 1-20  // from exon1
+   *   CDS 21-35 // from exon2
+   *   CDS 36-71 // from exon3
+   * 'coalesce' to range 1-71
+   * </pre>
    * 
    * @param ranges
    * @return the same list (if unchanged), else a new merged list, leaving the
@@ -384,27 +370,6 @@ public class MapList
         first = false;
         continue;
       }
-      if (range[0] == lastRange[0] && range[1] == lastRange[1])
-      {
-        // drop duplicate range
-        changed = true;
-        continue;
-      }
-
-      /*
-       * drop this range if it lies within the last range
-       */
-      if ((lastDirection == 1 && range[0] >= lastRange[0]
-              && range[0] <= lastRange[1] && range[1] >= lastRange[0]
-              && range[1] <= lastRange[1])
-              || (lastDirection == -1 && range[0] <= lastRange[0]
-                      && range[0] >= lastRange[1]
-                      && range[1] <= lastRange[0]
-                      && range[1] >= lastRange[1]))
-      {
-        changed = true;
-        continue;
-      }
 
       int direction = range[1] >= range[0] ? 1 : -1;
 
@@ -415,11 +380,7 @@ public class MapList
       boolean sameDirection = range[1] == range[0]
               || direction == lastDirection;
       boolean extending = range[0] == lastRange[1] + lastDirection;
-      boolean overlapping = (lastDirection == 1 && range[0] >= lastRange[0]
-              && range[0] <= lastRange[1])
-              || (lastDirection == -1 && range[0] <= lastRange[0]
-                      && range[0] >= lastRange[1]);
-      if (sameDirection && (overlapping || extending))
+      if (sameDirection && extending)
       {
         lastRange[1] = range[1];
         changed = true;
@@ -1134,8 +1095,8 @@ public class MapList
   }
 
   /**
-   * A helper method that returns true unless at least one range has start > end.
-   * Behaviour is undefined for a mixture of forward and reverse ranges.
+   * A helper method that returns true unless at least one range has start >
+   * end. Behaviour is undefined for a mixture of forward and reverse ranges.
    * 
    * @param ranges
    * @return
index 86dcc39..71fbdfd 100644 (file)
@@ -27,8 +27,6 @@ import static org.testng.AssertJUnit.assertSame;
 import static org.testng.AssertJUnit.assertTrue;
 import static org.testng.internal.junit.ArrayAsserts.assertArrayEquals;
 
-import jalview.gui.JvOptionPane;
-
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
@@ -36,9 +34,17 @@ import java.util.List;
 import org.testng.annotations.BeforeClass;
 import org.testng.annotations.Test;
 
+import jalview.bin.Cache;
+import jalview.gui.JvOptionPane;
+
 public class MapListTest
 {
-
+  @BeforeClass(alwaysRun = true)
+  public void setUp()
+  {
+    Cache.initLogger();
+  }
+  
   @BeforeClass(alwaysRun = true)
   public void setUpJvOptionPane()
   {
@@ -49,17 +55,20 @@ public class MapListTest
   @Test(groups = { "Functional" })
   public void testSomething()
   {
-    MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, new int[] {
-        51, 1 }, 1, 3);
+    MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 },
+            new int[]
+            { 51, 1 }, 1, 3);
     MapList ml1 = new MapList(new int[] { 1, 3, 17, 4 },
-            new int[] { 51, 1 }, 1, 3);
+            new int[]
+            { 51, 1 }, 1, 3);
     MapList ml2 = new MapList(new int[] { 1, 60 }, new int[] { 1, 20 }, 3,
             1);
     // test internal consistency
     int to[] = new int[51];
     testMap(ml, 1, 60);
-    MapList mldna = new MapList(new int[] { 2, 2, 6, 8, 12, 16 }, new int[]
-    { 1, 3 }, 3, 1);
+    MapList mldna = new MapList(new int[] { 2, 2, 6, 8, 12, 16 },
+            new int[]
+            { 1, 3 }, 3, 1);
     int[] frm = mldna.locateInFrom(1, 1);
     testLocateFrom(mldna, 1, 1, new int[] { 2, 2, 6, 7 });
     testMap(mldna, 1, 3);
@@ -431,7 +440,8 @@ public class MapListTest
     List<int[]> ranges = new ArrayList<>();
     ranges.add(new int[] { 2, 3 });
     ranges.add(new int[] { 5, 6 });
-    assertEquals("[2, 3, 5, 6]", Arrays.toString(MapList.getRanges(ranges)));
+    assertEquals("[2, 3, 5, 6]",
+            Arrays.toString(MapList.getRanges(ranges)));
   }
 
   /**
@@ -463,7 +473,8 @@ public class MapListTest
     assertEquals(6, ml2.getToHighest());
     assertEquals("{[2, 3], [5, 7], [9, 10], [12, 12], [14, 14], [16, 18]}",
             prettyPrint(ml2.getFromRanges()));
-    assertEquals("{[1, 1], [3, 4], [6, 6]}", prettyPrint(ml2.getToRanges()));
+    assertEquals("{[1, 1], [3, 4], [6, 6]}",
+            prettyPrint(ml2.getToRanges()));
 
     /*
      * reverse direction
@@ -478,22 +489,23 @@ public class MapListTest
   }
 
   /**
-   * Test constructor can merge consecutive ranges
+   * Test constructor used to merge consecutive ranges but now just leaves them
+   * as supplied (JAL-3751)
    */
   @Test(groups = { "Functional" })
   public void testConstructor_mergeRanges()
   {
-    int[] codons = { 2, 3, 3, 7, 9, 10, 12, 12, 14, 14, 16, 17 };
-    int[] protein = { 1, 1, 1, 3, 6, 6 };
+    int[] codons = { 2, 3, 3, 7, 9, 10, 12, 12, 13, 14, 16, 17 };
+    int[] protein = { 1, 1, 2, 3, 6, 6 };
     MapList ml = new MapList(codons, protein, 3, 1);
     assertEquals(3, ml.getFromRatio());
     assertEquals(2, ml.getFromLowest());
     assertEquals(17, ml.getFromHighest());
     assertEquals(1, ml.getToLowest());
     assertEquals(6, ml.getToHighest());
-    assertEquals("{[2, 7], [9, 10], [12, 12], [14, 14], [16, 17]}",
+    assertEquals("{[2, 3], [3, 7], [9, 10], [12, 12], [13, 14], [16, 17]}",
             prettyPrint(ml.getFromRanges()));
-    assertEquals("{[1, 3], [6, 6]}", prettyPrint(ml.getToRanges()));
+    assertEquals("{[1, 1], [2, 3], [6, 6]}", prettyPrint(ml.getToRanges()));
   }
 
   /**
@@ -544,8 +556,9 @@ public class MapListTest
   @Test(groups = { "Functional" })
   public void testToString()
   {
-    MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 }, new int[] {
-        51, 1 }, 1, 3);
+    MapList ml = new MapList(new int[] { 1, 5, 10, 15, 25, 20 },
+            new int[]
+            { 51, 1 }, 1, 3);
     String s = ml.toString();
     assertEquals("[ [1, 5] [10, 15] [25, 20] ] 1:3 to [ [51, 1] ]", s);
   }
@@ -554,14 +567,16 @@ public class MapListTest
   public void testAddMapList()
   {
     MapList ml = new MapList(new int[] { 11, 15, 20, 25, 35, 30 },
-            new int[] { 72, 22 }, 1, 3);
+            new int[]
+            { 72, 22 }, 1, 3);
     assertEquals(11, ml.getFromLowest());
     assertEquals(35, ml.getFromHighest());
     assertEquals(22, ml.getToLowest());
     assertEquals(72, ml.getToHighest());
 
-    MapList ml2 = new MapList(new int[] { 2, 4, 37, 40 }, new int[] { 12,
-        17, 78, 83, 88, 96 }, 1, 3);
+    MapList ml2 = new MapList(new int[] { 2, 4, 37, 40 },
+            new int[]
+            { 12, 17, 78, 83, 88, 96 }, 1, 3);
     ml.addMapList(ml2);
     assertEquals(2, ml.getFromLowest());
     assertEquals(40, ml.getFromHighest());
@@ -595,8 +610,8 @@ public class MapListTest
     MapList ml = new MapList(new int[] { 11, 15 }, new int[] { 72, 58 }, 1,
             3);
 
-    MapList ml2 = new MapList(new int[] { 15, 16 }, new int[] { 58, 53 },
-            1, 3);
+    MapList ml2 = new MapList(new int[] { 15, 16 }, new int[] { 58, 53 }, 1,
+            3);
     ml.addMapList(ml2);
     assertEquals("[ [11, 16] ] 1:3 to [ [72, 53] ]", ml.toString());
   }
@@ -682,13 +697,15 @@ public class MapListTest
   public void testIsFromForwardStrand()
   {
     // [3-9] declares forward strand
-    MapList ml = new MapList(new int[] { 2, 2, 3, 9, 12, 11 }, new int[] {
-        20, 11 }, 1, 1);
+    MapList ml = new MapList(new int[] { 2, 2, 3, 9, 12, 11 },
+            new int[]
+            { 20, 11 }, 1, 1);
     assertTrue(ml.isFromForwardStrand());
 
     // [11-5] declares reverse strand ([13-14] is ignored)
     ml = new MapList(new int[] { 2, 2, 11, 5, 13, 14 },
-            new int[] { 20, 11 }, 1, 1);
+            new int[]
+            { 20, 11 }, 1, 1);
     assertFalse(ml.isFromForwardStrand());
 
     // all single position ranges - defaults to forward strand
@@ -698,7 +715,7 @@ public class MapListTest
   }
 
   /**
-   * Test the method that merges a list of ranges where possible
+   * Test the method that merges contiguous ranges
    */
   @Test(groups = { "Functional" })
   public void testCoalesceRanges()
@@ -720,101 +737,57 @@ public class MapListTest
     // merging in forward direction:
     ranges.clear();
     ranges.add(new int[] { 1, 3 });
-    ranges.add(new int[] { 4, 5 });
-    ranges.add(new int[] { 5, 5 });
-    ranges.add(new int[] { 5, 7 });
+    ranges.add(new int[] { 4, 5 }); // contiguous
+    ranges.add(new int[] { 5, 5 }); // overlap!
+    ranges.add(new int[] { 6, 7 }); // contiguous
     List<int[]> merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 1, 7 }, merged.get(0));
+    assertEquals(2, merged.size());
+    assertArrayEquals(new int[] { 1, 5 }, merged.get(0));
+    assertArrayEquals(new int[] { 5, 7 }, merged.get(1));
     // verify input list is unchanged
     assertEquals(4, ranges.size());
     assertArrayEquals(new int[] { 1, 3 }, ranges.get(0));
     assertArrayEquals(new int[] { 4, 5 }, ranges.get(1));
     assertArrayEquals(new int[] { 5, 5 }, ranges.get(2));
-    assertArrayEquals(new int[] { 5, 7 }, ranges.get(3));
+    assertArrayEquals(new int[] { 6, 7 }, ranges.get(3));
 
     // merging in reverse direction:
     ranges.clear();
     ranges.add(new int[] { 7, 5 });
-    ranges.add(new int[] { 5, 4 });
-    ranges.add(new int[] { 4, 4 });
-    ranges.add(new int[] { 3, 1 });
+    ranges.add(new int[] { 5, 4 }); // overlap
+    ranges.add(new int[] { 4, 4 }); // overlap
+    ranges.add(new int[] { 3, 1 }); // contiguous
     merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 7, 1 }, merged.get(0));
+    assertEquals(3, merged.size());
+    assertArrayEquals(new int[] { 7, 5 }, merged.get(0));
+    assertArrayEquals(new int[] { 5, 4 }, merged.get(1));
+    assertArrayEquals(new int[] { 4, 1 }, merged.get(2));
 
     // merging with switches of direction:
     ranges.clear();
     ranges.add(new int[] { 1, 3 });
-    ranges.add(new int[] { 4, 5 });
-    ranges.add(new int[] { 5, 5 });
-    ranges.add(new int[] { 6, 6 });
+    ranges.add(new int[] { 4, 5 }); // contiguous
+    ranges.add(new int[] { 5, 5 }); // overlap
+    ranges.add(new int[] { 6, 6 }); // contiguous
     ranges.add(new int[] { 12, 10 });
-    ranges.add(new int[] { 9, 8 });
-    ranges.add(new int[] { 8, 8 });
-    ranges.add(new int[] { 7, 7 });
+    ranges.add(new int[] { 9, 8 }); // contiguous
+    ranges.add(new int[] { 8, 8 }); // overlap
+    ranges.add(new int[] { 7, 7 }); // contiguous
     merged = MapList.coalesceRanges(ranges);
-    assertEquals(2, merged.size());
-    assertArrayEquals(new int[] { 1, 6 }, merged.get(0));
-    assertArrayEquals(new int[] { 12, 7 }, merged.get(1));
-  }
-
-  /**
-   * Test the method that merges a list of ranges where possible
-   */
-  @Test(groups = { "Functional" })
-  public void testCoalesceRanges_withOverlap()
-  {
-    List<int[]> ranges = new ArrayList<>();
-    ranges.add(new int[] { 1, 3 });
-    ranges.add(new int[] { 2, 5 });
-
-    /*
-     * [2, 5] should extend [1, 3]
-     */
-    List<int[]> merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
+    assertEquals(4, merged.size());
     assertArrayEquals(new int[] { 1, 5 }, merged.get(0));
-
-    /*
-     * a subsumed interval should be dropped
-     */
-    ranges.clear();
-    ranges.add(new int[] { 1, 6 });
-    ranges.add(new int[] { 2, 4 });
-    merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 1, 6 }, merged.get(0));
-
+    assertArrayEquals(new int[] { 5, 6 }, merged.get(1));
+    assertArrayEquals(new int[] { 12, 8 }, merged.get(2));
+    assertArrayEquals(new int[] { 8, 7 }, merged.get(3));
+    
+    // 'subsumed' ranges are preserved
     ranges.clear();
-    ranges.add(new int[] { 1, 5 });
-    ranges.add(new int[] { 1, 6 });
+    ranges.add(new int[] { 10, 30 });
+    ranges.add(new int[] { 15, 25 }); 
     merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 1, 6 }, merged.get(0));
-
-    /*
-     * merge duplicate ranges
-     */
-    ranges.clear();
-    ranges.add(new int[] { 1, 3 });
-    ranges.add(new int[] { 1, 3 });
-    merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 1, 3 }, merged.get(0));
-
-    /*
-     * reverse direction
-     */
-    ranges.clear();
-    ranges.add(new int[] { 9, 5 });
-    ranges.add(new int[] { 9, 4 });
-    ranges.add(new int[] { 8, 3 });
-    ranges.add(new int[] { 3, 2 });
-    ranges.add(new int[] { 1, 0 });
-    merged = MapList.coalesceRanges(ranges);
-    assertEquals(1, merged.size());
-    assertArrayEquals(new int[] { 9, 0 }, merged.get(0));
+    assertEquals(2, merged.size());
+    assertArrayEquals(new int[] { 10, 30 }, merged.get(0));
+    assertArrayEquals(new int[] { 15, 25 }, merged.get(1));
   }
 
   /**
@@ -826,13 +799,15 @@ public class MapListTest
     /*
      * simple 1:1 plus 1:1 forwards
      */
-    MapList ml1 = new MapList(new int[] { 3, 4, 8, 12 }, new int[] { 5, 8,
-        11, 13 }, 1, 1);
+    MapList ml1 = new MapList(new int[] { 3, 4, 8, 12 },
+            new int[]
+            { 5, 8, 11, 13 }, 1, 1);
     assertEquals("{[3, 4], [8, 12]}", prettyPrint(ml1.getFromRanges()));
     assertEquals("{[5, 8], [11, 13]}", prettyPrint(ml1.getToRanges()));
 
-    MapList ml2 = new MapList(new int[] { 1, 50 }, new int[] { 40, 45, 70,
-        75, 90, 127 }, 1, 1);
+    MapList ml2 = new MapList(new int[] { 1, 50 },
+            new int[]
+            { 40, 45, 70, 75, 90, 127 }, 1, 1);
     assertEquals("{[1, 50]}", prettyPrint(ml2.getFromRanges()));
     assertEquals("{[40, 45], [70, 75], [90, 127]}",
             prettyPrint(ml2.getToRanges()));
@@ -859,7 +834,8 @@ public class MapListTest
      */
     ml1 = new MapList(new int[] { 1, 50 }, new int[] { 70, 119 }, 1, 1);
     ml2 = new MapList(new int[] { 1, 500 },
-            new int[] { 1000, 901, 600, 201 }, 1, 1);
+            new int[]
+            { 1000, 901, 600, 201 }, 1, 1);
     compound = ml1.traverse(ml2);
 
     assertEquals(1, compound.getFromRatio());
@@ -876,8 +852,8 @@ public class MapListTest
      * 1:1 plus 1:3 should result in 1:3
      */
     ml1 = new MapList(new int[] { 1, 30 }, new int[] { 11, 40 }, 1, 1);
-    ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 50, 91, 340 },
-            1, 3);
+    ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 50, 91, 340 }, 1,
+            3);
     compound = ml1.traverse(ml2);
 
     assertEquals(1, compound.getFromRatio());
@@ -895,8 +871,8 @@ public class MapListTest
      * 3:1 plus 1:1 should result in 3:1
      */
     ml1 = new MapList(new int[] { 1, 30 }, new int[] { 11, 20 }, 3, 1);
-    ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 15, 91, 175 },
-            1, 1);
+    ml2 = new MapList(new int[] { 1, 100 }, new int[] { 1, 15, 91, 175 }, 1,
+            1);
     compound = ml1.traverse(ml2);
 
     assertEquals(3, compound.getFromRatio());
@@ -958,8 +934,8 @@ public class MapListTest
   }
 
   /**
-   * Test that method that inspects for the (first) forward or reverse 'to' range.
-   * Single position ranges are ignored.
+   * Test that method that inspects for the (first) forward or reverse 'to'
+   * range. Single position ranges are ignored.
    */
   @Test(groups = { "Functional" })
   public void testIsToForwardsStrand()
index d4df8c7..d0269d8 100644 (file)
@@ -37,6 +37,7 @@ import org.testng.annotations.BeforeClass;
 import org.testng.annotations.Test;
 
 import jalview.api.AlignViewportI;
+import jalview.bin.Cache;
 import jalview.commands.EditCommand;
 import jalview.commands.EditCommand.Action;
 import jalview.commands.EditCommand.Edit;
@@ -59,6 +60,12 @@ import jalview.io.FormatAdapter;
 
 public class MappingUtilsTest
 {
+  @BeforeClass(alwaysRun = true)
+  public void setUp()
+  {
+    Cache.initLogger();
+  }
+  
 
   @BeforeClass(alwaysRun = true)
   public void setUpJvOptionPane()