JAL-2920 format/comment tidy
[jalview.git] / test / jalview / datamodel / features / NCListTest.java
1 package jalview.datamodel.features;
2 import static org.testng.Assert.assertEquals;
3 import static org.testng.Assert.assertFalse;
4 import static org.testng.Assert.assertSame;
5 import static org.testng.Assert.assertTrue;
6
7 import jalview.datamodel.ContiguousI;
8 import jalview.datamodel.Range;
9 import jalview.datamodel.SequenceFeature;
10
11 import java.util.ArrayList;
12 import java.util.Collections;
13 import java.util.Comparator;
14 import java.util.List;
15 import java.util.Random;
16
17 import junit.extensions.PA;
18
19 import org.testng.annotations.DataProvider;
20 import org.testng.annotations.Test;
21
22 public class NCListTest
23 {
24
25   private Random random = new Random(107);
26
27   private Comparator<ContiguousI> sorter = new RangeComparator(true);
28
29   /**
30    * A basic sanity test of the constructor
31    */
32   @Test(groups = "Functional")
33   public void testConstructor()
34   {
35     List<Range> ranges = new ArrayList<Range>();
36     ranges.add(new Range(20, 20));
37     ranges.add(new Range(10, 20));
38     ranges.add(new Range(15, 30));
39     ranges.add(new Range(10, 30));
40     ranges.add(new Range(11, 19));
41     ranges.add(new Range(10, 20));
42     ranges.add(new Range(1, 100));
43
44     NCList<Range> ncl = new NCList<Range>(ranges);
45     String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
46     assertEquals(ncl.toString(), expected);
47     assertTrue(ncl.isValid());
48
49     Collections.reverse(ranges);
50     ncl = new NCList<Range>(ranges);
51     assertEquals(ncl.toString(), expected);
52     assertTrue(ncl.isValid());
53   }
54
55   @Test(groups = "Functional")
56   public void testFindOverlaps()
57   {
58     List<Range> ranges = new ArrayList<Range>();
59     ranges.add(new Range(20, 50));
60     ranges.add(new Range(30, 70));
61     ranges.add(new Range(1, 100));
62     ranges.add(new Range(70, 120));
63   
64     NCList<Range> ncl = new NCList<Range>(ranges);
65
66     List<Range> overlaps = ncl.findOverlaps(121, 122);
67     assertEquals(overlaps.size(), 0);
68
69     overlaps = ncl.findOverlaps(21, 22);
70     assertEquals(overlaps.size(), 2);
71     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
72     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
73     assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
74     assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
75
76     overlaps = ncl.findOverlaps(110, 110);
77     assertEquals(overlaps.size(), 1);
78     assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
79     assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
80   }
81
82   @Test(groups = "Functional")
83   public void testAdd_onTheEnd()
84   {
85     List<Range> ranges = new ArrayList<Range>();
86     ranges.add(new Range(20, 50));
87     NCList<Range> ncl = new NCList<Range>(ranges);
88     assertEquals(ncl.toString(), "[20-50]");
89     assertTrue(ncl.isValid());
90
91     ncl.add(new Range(60, 70));
92     assertEquals(ncl.toString(), "[20-50, 60-70]");
93     assertTrue(ncl.isValid());
94   }
95
96   @Test(groups = "Functional")
97   public void testAdd_inside()
98   {
99     List<Range> ranges = new ArrayList<Range>();
100     ranges.add(new Range(20, 50));
101     NCList<Range> ncl = new NCList<Range>(ranges);
102     assertEquals(ncl.toString(), "[20-50]");
103     assertTrue(ncl.isValid());
104
105     ncl.add(new Range(30, 40));
106     assertEquals(ncl.toString(), "[20-50 [30-40]]");
107   }
108
109   @Test(groups = "Functional")
110   public void testAdd_onTheFront()
111   {
112     List<Range> ranges = new ArrayList<Range>();
113     ranges.add(new Range(20, 50));
114     NCList<Range> ncl = new NCList<Range>(ranges);
115     assertEquals(ncl.toString(), "[20-50]");
116     assertTrue(ncl.isValid());
117
118     ncl.add(new Range(5, 15));
119     assertEquals(ncl.toString(), "[5-15, 20-50]");
120     assertTrue(ncl.isValid());
121   }
122
123   @Test(groups = "Functional")
124   public void testAdd_enclosing()
125   {
126     List<Range> ranges = new ArrayList<Range>();
127     ranges.add(new Range(20, 50));
128     ranges.add(new Range(30, 60));
129     NCList<Range> ncl = new NCList<Range>(ranges);
130     assertEquals(ncl.toString(), "[20-50, 30-60]");
131     assertTrue(ncl.isValid());
132     assertEquals(ncl.getStart(), 20);
133
134     ncl.add(new Range(10, 70));
135     assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
136     assertTrue(ncl.isValid());
137   }
138
139   @Test(groups = "Functional")
140   public void testAdd_spanning()
141   {
142     List<Range> ranges = new ArrayList<Range>();
143     ranges.add(new Range(20, 40));
144     ranges.add(new Range(60, 70));
145     NCList<Range> ncl = new NCList<Range>(ranges);
146     assertEquals(ncl.toString(), "[20-40, 60-70]");
147     assertTrue(ncl.isValid());
148
149     ncl.add(new Range(30, 50));
150     assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
151     assertTrue(ncl.isValid());
152
153     ncl.add(new Range(40, 65));
154     assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
155     assertTrue(ncl.isValid());
156   }
157
158   /**
159    * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
160    * [0-scale] interval to be stored
161    * 
162    * @return
163    */
164   @DataProvider(name = "scalesOfLife")
165   public Object[][] getScales()
166   {
167     return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
168   }
169
170   /**
171    * Do a number of pseudo-random (reproducible) builds of an NCList, to
172    * exercise as many methods of the class as possible while generating the
173    * range of possible structure topologies
174    * <ul>
175    * <li>verify that add adds an entry and increments size</li>
176    * <li>...except where the entry is already contained (by equals test)</li>
177    * <li>verify that the structure is valid at all stages of construction</li>
178    * <li>generate, run and verify a range of overlap queries</li>
179    * <li>tear down the structure by deleting entries, verifying correctness at
180    * each stage</li>
181    * </ul>
182    */
183   @Test(groups = "Functional", dataProvider = "scalesOfLife")
184   public void test_pseudoRandom(Integer scale)
185   {
186     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
187     List<SequenceFeature> features = new ArrayList<SequenceFeature>(scale);
188     
189     testAdd_pseudoRandom(scale, ncl, features);
190
191     /*
192      * sort the list of added ranges - this doesn't affect the test,
193      * just makes it easier to inspect the data in the debugger
194      */
195     Collections.sort(features, sorter);
196
197     testFindOverlaps_pseudoRandom(ncl, scale, features);
198
199     testDelete_pseudoRandom(ncl, features);
200   }
201
202   /**
203    * Pick randomly selected entries to delete in turn, checking the NCList size
204    * and validity at each stage, until it is empty
205    * 
206    * @param ncl
207    * @param features
208    */
209   protected void testDelete_pseudoRandom(NCList<SequenceFeature> ncl,
210           List<SequenceFeature> features)
211   {
212     int deleted = 0;
213
214     while (!features.isEmpty())
215     {
216       assertEquals(ncl.size(), features.size());
217       int toDelete = random.nextInt(features.size());
218       SequenceFeature entry = features.get(toDelete);
219       assertTrue(ncl.contains(entry), String.format(
220               "NCList doesn't contain entry [%d] '%s'!", deleted,
221               entry.toString()));
222
223       ncl.delete(entry);
224       assertFalse(ncl.contains(entry), String.format(
225               "NCList still contains deleted entry [%d] '%s'!", deleted,
226               entry.toString()));
227       features.remove(toDelete);
228       deleted++;
229
230       assertTrue(ncl.isValid(), String.format(
231               "NCList invalid after %d deletions, last deleted was '%s'",
232               deleted, entry.toString()));
233
234       /*
235        * brute force check that deleting one entry didn't delete any others
236        */
237       for (int i = 0; i < features.size(); i++)
238       {
239         SequenceFeature sf = features.get(i);
240         assertTrue(ncl.contains(sf), String.format(
241                         "NCList doesn't contain entry [%d] %s after deleting '%s'!",
242                         i, sf.toString(), entry.toString()));
243       }
244     }
245     assertEquals(ncl.size(), 0); // all gone
246   }
247
248   /**
249    * Randomly generate entries and add them to the NCList, checking its validity
250    * and size at each stage. A few entries should be duplicates (by equals test)
251    * so not get added.
252    * 
253    * @param scale
254    * @param ncl
255    * @param features
256    */
257   protected void testAdd_pseudoRandom(Integer scale,
258           NCList<SequenceFeature> ncl,
259           List<SequenceFeature> features)
260   {
261     int count = 0;
262     final int size = 50;
263
264     for (int i = 0; i < size; i++)
265     {
266       int r1 = random.nextInt(scale + 1);
267       int r2 = random.nextInt(scale + 1);
268       int from = Math.min(r1, r2);
269       int to = Math.max(r1, r2);
270
271       /*
272        * choice of two feature values means that occasionally an identical
273        * feature may be generated, in which case it should not be added 
274        */
275       float value = (float) i % 2;
276       SequenceFeature feature = new SequenceFeature("Pfam", "", from, to,
277               value, "group");
278
279       /*
280        * add to NCList - with duplicate entries (by equals) disallowed
281        */
282       ncl.add(feature, false);
283       if (features.contains(feature))
284       {
285         System.out.println("Duplicate feature generated "
286                 + feature.toString());
287       }
288       else
289       {
290         features.add(feature);
291         count++;
292       }
293     
294       /*
295        * check list format is valid at each stage of its construction
296        */
297       assertTrue(ncl.isValid(),
298               String.format("Failed for scale = %d, i=%d", scale, i));
299       assertEquals(ncl.size(), count);
300     }
301     // System.out.println(ncl.prettyPrint());
302   }
303
304   /**
305    * A helper method that generates pseudo-random range queries and veries that
306    * findOverlaps returns the correct matches
307    * 
308    * @param ncl
309    *          the NCList to query
310    * @param scale
311    *          ncl maximal range is [0, scale]
312    * @param features
313    *          a list of the ranges stored in ncl
314    */
315   protected void testFindOverlaps_pseudoRandom(NCList<SequenceFeature> ncl,
316           int scale,
317           List<SequenceFeature> features)
318   {
319     int halfScale = scale / 2;
320     int minIterations = 20;
321
322     /*
323      * generates ranges in [-halfScale, scale+halfScale]
324      * - some should be internal to [0, scale] P = 1/4
325      * - some should lie before 0 P = 1/16
326      * - some should lie after scale P = 1/16
327      * - some should overlap left P = 1/4
328      * - some should overlap right P = 1/4
329      * - some should enclose P = 1/8
330      * 
331      * 50 iterations give a 96% probability of including the
332      * unlikeliest case; keep going until we have done all!
333      */
334     boolean inside = false;
335     boolean enclosing = false;
336     boolean before = false;
337     boolean after = false;
338     boolean overlapLeft = false;
339     boolean overlapRight = false;
340     boolean allCasesCovered = false;
341
342     int i = 0;
343     while (i < minIterations || !allCasesCovered)
344     {
345       i++;
346       int r1 = random.nextInt((scale + 1) * 2);
347       int r2 = random.nextInt((scale + 1) * 2);
348       int from = Math.min(r1, r2) - halfScale;
349       int to = Math.max(r1, r2) - halfScale;
350
351       /*
352        * ensure all cases of interest get covered
353        */
354       inside |= from >= 0 && to <= scale;
355       enclosing |= from <= 0 && to >= scale;
356       before |= to < 0;
357       after |= from > scale;
358       overlapLeft |= from < 0 && to >= 0 && to <= scale;
359       overlapRight |= from >= 0 && from <= scale && to > scale;
360       if (!allCasesCovered)
361       {
362         allCasesCovered |= inside && enclosing && before && after
363               && overlapLeft && overlapRight;
364         if (allCasesCovered)
365         {
366           System.out
367                   .println(String
368                           .format("Covered all findOverlaps cases after %d iterations for scale %d",
369                                   i, scale));
370         }
371       }
372
373       verifyFindOverlaps(ncl, from, to, features);
374     }
375   }
376
377   /**
378    * A helper method that verifies that overlaps found by interrogating an
379    * NCList correctly match those found by brute force search
380    * 
381    * @param ncl
382    * @param from
383    * @param to
384    * @param features
385    */
386   protected void verifyFindOverlaps(NCList<SequenceFeature> ncl, int from,
387           int to, List<SequenceFeature> features)
388   {
389     List<SequenceFeature> overlaps = ncl.findOverlaps(from, to);
390
391     /*
392      * check returned entries do indeed overlap from-to range
393      */
394     for (ContiguousI sf : overlaps)
395     {
396       int begin = sf.getBegin();
397       int end = sf.getEnd();
398       assertTrue(begin <= to && end >= from, String.format(
399               "[%d, %d] does not overlap query range [%d, %d]", begin, end,
400               from, to));
401     }
402
403     /*
404      * check overlapping ranges are included in the results
405      * (the test above already shows non-overlapping ranges are not)
406      */
407     for (ContiguousI sf : features)
408     {
409       int begin = sf.getBegin();
410       int end = sf.getEnd();
411       if (begin <= to && end >= from)
412       {
413         boolean found = overlaps.contains(sf);
414         assertTrue(found, String.format(
415                 "[%d, %d] missing in query range [%d, %d]", begin, end,
416                 from, to));
417       }
418     }
419   }
420
421   @Test(groups = "Functional")
422   public void testGetEntries()
423   {
424     List<Range> ranges = new ArrayList<Range>();
425     Range r1 = new Range(20, 20);
426     Range r2 = new Range(10, 20);
427     Range r3 = new Range(15, 30);
428     Range r4 = new Range(10, 30);
429     Range r5 = new Range(11, 19);
430     Range r6 = new Range(10, 20);
431     ranges.add(r1);
432     ranges.add(r2);
433     ranges.add(r3);
434     ranges.add(r4);
435     ranges.add(r5);
436     ranges.add(r6);
437   
438     NCList<Range> ncl = new NCList<Range>(ranges);
439     Range r7 = new Range(1, 100);
440     ncl.add(r7);
441
442     List<Range> contents = ncl.getEntries();
443     assertEquals(contents.size(), 7);
444     assertTrue(contents.contains(r1));
445     assertTrue(contents.contains(r2));
446     assertTrue(contents.contains(r3));
447     assertTrue(contents.contains(r4));
448     assertTrue(contents.contains(r5));
449     assertTrue(contents.contains(r6));
450     assertTrue(contents.contains(r7));
451
452     ncl = new NCList<Range>();
453     assertTrue(ncl.getEntries().isEmpty());
454   }
455
456   @Test(groups = "Functional")
457   public void testDelete()
458   {
459     List<Range> ranges = new ArrayList<Range>();
460     Range r1 = new Range(20, 30);
461     ranges.add(r1);
462     NCList<Range> ncl = new NCList<Range>(ranges);
463     assertTrue(ncl.getEntries().contains(r1));
464
465     Range r2 = new Range(20, 30);
466     assertFalse(ncl.delete(null)); // null argument
467     assertFalse(ncl.delete(r2)); // never added
468     assertTrue(ncl.delete(r1)); // success
469     assertTrue(ncl.getEntries().isEmpty());
470
471     /*
472      * tests where object.equals() == true
473      */
474     NCList<SequenceFeature> features = new NCList<SequenceFeature>();
475     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
476             "group");
477     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
478             "group");
479     features.add(sf1);
480     assertEquals(sf1, sf2); // sf1.equals(sf2)
481     assertFalse(features.delete(sf2)); // equality is not enough for deletion
482     assertTrue(features.getEntries().contains(sf1)); // still there!
483     assertTrue(features.delete(sf1));
484     assertTrue(features.getEntries().isEmpty()); // gone now
485
486     /*
487      * test with duplicate objects in NCList
488      */
489     features.add(sf1);
490     features.add(sf1);
491     assertEquals(features.getEntries().size(), 2);
492     assertSame(features.getEntries().get(0), sf1);
493     assertSame(features.getEntries().get(1), sf1);
494     assertTrue(features.delete(sf1)); // first match only is deleted
495     assertTrue(features.contains(sf1));
496     assertEquals(features.size(), 1);
497     assertTrue(features.delete(sf1));
498     assertTrue(features.getEntries().isEmpty());
499   }
500
501   @Test(groups = "Functional")
502   public void testAdd_overlapping()
503   {
504     List<Range> ranges = new ArrayList<Range>();
505     ranges.add(new Range(40, 50));
506     ranges.add(new Range(20, 30));
507     NCList<Range> ncl = new NCList<Range>(ranges);
508     assertEquals(ncl.toString(), "[20-30, 40-50]");
509     assertTrue(ncl.isValid());
510   
511     /*
512      * add range overlapping internally
513      */
514     ncl.add(new Range(25, 35));
515     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
516     assertTrue(ncl.isValid());
517
518     /*
519      * add range overlapping last range
520      */
521     ncl.add(new Range(45, 55));
522     assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
523     assertTrue(ncl.isValid());
524
525     /*
526      * add range overlapping first range
527      */
528     ncl.add(new Range(15, 25));
529     assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
530     assertTrue(ncl.isValid());
531   }
532
533   /**
534    * Test the contains method (which uses object equals test)
535    */
536   @Test(groups = "Functional")
537   public void testContains()
538   {
539     NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
540     SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
541             "group");
542     SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
543             "group");
544     SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
545             "anothergroup");
546     ncl.add(sf1);
547
548     assertTrue(ncl.contains(sf1));
549     assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
550     assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
551
552     /*
553      * make some deeper structure in the NCList
554      */
555     SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
556             "group");
557     ncl.add(sf4);
558     assertTrue(ncl.contains(sf4));
559     SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
560             "group");
561     SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
562             "group");
563     ncl.add(sf5);
564     ncl.add(sf6);
565     assertTrue(ncl.contains(sf5));
566     assertTrue(ncl.contains(sf6));
567   }
568
569   @Test(groups = "Functional")
570   public void testIsValid()
571   {
572     List<Range> ranges = new ArrayList<Range>();
573     Range r1 = new Range(40, 50);
574     ranges.add(r1);
575     NCList<Range> ncl = new NCList<Range>(ranges);
576     assertTrue(ncl.isValid());
577
578     Range r2 = new Range(42, 44);
579     ncl.add(r2);
580     assertTrue(ncl.isValid());
581     Range r3 = new Range(46, 48);
582     ncl.add(r3);
583     assertTrue(ncl.isValid());
584     Range r4 = new Range(43, 43);
585     ncl.add(r4);
586     assertTrue(ncl.isValid());
587
588     assertEquals(ncl.toString(), "[40-50 [42-44 [43-43], 46-48]]");
589     assertTrue(ncl.isValid());
590
591     PA.setValue(r1, "start", 43);
592     assertFalse(ncl.isValid()); // r2 not inside r1
593     PA.setValue(r1, "start", 40);
594     assertTrue(ncl.isValid());
595
596     PA.setValue(r3, "start", 41);
597     assertFalse(ncl.isValid()); // r3 should precede r2
598     PA.setValue(r3, "start", 46);
599     assertTrue(ncl.isValid());
600
601     PA.setValue(r4, "start", 41);
602     assertFalse(ncl.isValid()); // r4 not inside r2
603     PA.setValue(r4, "start", 43);
604     assertTrue(ncl.isValid());
605
606     PA.setValue(r4, "start", 44);
607     assertFalse(ncl.isValid()); // r4 has reverse range
608   }
609
610   @Test(groups = "Functional")
611   public void testPrettyPrint()
612   {
613     /*
614      * construct NCList from a list of ranges
615      * they are sorted then assembled into NCList subregions
616      * notice that 42-42 end up inside 41-46
617      */
618     List<Range> ranges = new ArrayList<Range>();
619     ranges.add(new Range(40, 50));
620     ranges.add(new Range(45, 55));
621     ranges.add(new Range(40, 45));
622     ranges.add(new Range(41, 46));
623     ranges.add(new Range(42, 42));
624     ranges.add(new Range(42, 42));
625     NCList<Range> ncl = new NCList<Range>(ranges);
626     assertTrue(ncl.isValid());
627     assertEquals(ncl.toString(),
628             "[40-50 [40-45], 41-46 [42-42 [42-42]], 45-55]");
629     String expected = "40-50\n  40-45\n41-46\n  42-42\n    42-42\n45-55\n";
630     assertEquals(ncl.prettyPrint(), expected);
631
632     /*
633      * repeat but now add ranges one at a time
634      * notice that 42-42 end up inside 40-50 so we get
635      * a different but equal valid NCList structure
636      */
637     ranges.clear();
638     ncl = new NCList<Range>(ranges);
639     ncl.add(new Range(40, 50));
640     ncl.add(new Range(45, 55));
641     ncl.add(new Range(40, 45));
642     ncl.add(new Range(41, 46));
643     ncl.add(new Range(42, 42));
644     ncl.add(new Range(42, 42));
645     assertTrue(ncl.isValid());
646     assertEquals(ncl.toString(),
647             "[40-50 [40-45 [42-42 [42-42]], 41-46], 45-55]");
648     expected = "40-50\n  40-45\n    42-42\n      42-42\n  41-46\n45-55\n";
649     assertEquals(ncl.prettyPrint(), expected);
650   }
651
652   /**
653    * A test that shows different valid trees can be constructed from the same
654    * set of ranges, depending on the order of construction
655    */
656   @Test(groups = "Functional")
657   public void testConstructor_alternativeTrees()
658   {
659     List<Range> ranges = new ArrayList<Range>();
660     ranges.add(new Range(10, 60));
661     ranges.add(new Range(20, 30));
662     ranges.add(new Range(40, 50));
663   
664     /*
665      * constructor with greedy traversal of sorted ranges to build nested
666      * containment lists results in 20-30 inside 10-60, 40-50 a sibling
667      */
668     NCList<Range> ncl = new NCList<Range>(ranges);
669     assertEquals(ncl.toString(), "[10-60 [20-30], 40-50]");
670     assertTrue(ncl.isValid());
671
672     /*
673      * adding ranges one at a time results in 40-50 
674      * a sibling of 20-30 inside 10-60
675      */
676     ncl = new NCList<Range>(new Range(10, 60));
677     ncl.add(new Range(20, 30));
678     ncl.add(new Range(40, 50));
679     assertEquals(ncl.toString(), "[10-60 [20-30, 40-50]]");
680     assertTrue(ncl.isValid());
681   }
682 }