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;
7 import jalview.datamodel.SequenceFeature;
9 import java.util.ArrayList;
10 import java.util.Collections;
11 import java.util.Comparator;
12 import java.util.List;
13 import java.util.Random;
15 import org.testng.annotations.DataProvider;
16 import org.testng.annotations.Test;
18 public class NCListTest
21 private Random random = new Random(107);
23 private Comparator<ContiguousI> sorter = new RangeComparator(true);
26 * A basic sanity test of the constructor
28 @Test(groups = "Functional")
29 public void testConstructor()
31 List<Range> ranges = new ArrayList<Range>();
32 ranges.add(new Range(20, 20));
33 ranges.add(new Range(10, 20));
34 ranges.add(new Range(15, 30));
35 ranges.add(new Range(10, 30));
36 ranges.add(new Range(11, 19));
37 ranges.add(new Range(10, 20));
38 ranges.add(new Range(1, 100));
40 NCList<Range> ncl = new NCList<Range>(ranges);
41 String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
42 assertEquals(ncl.toString(), expected);
43 assertTrue(ncl.isValid());
45 Collections.reverse(ranges);
46 ncl = new NCList<Range>(ranges);
47 assertEquals(ncl.toString(), expected);
48 assertTrue(ncl.isValid());
51 @Test(groups = "Functional")
52 public void testFindOverlaps()
54 List<Range> ranges = new ArrayList<Range>();
55 ranges.add(new Range(20, 50));
56 ranges.add(new Range(30, 70));
57 ranges.add(new Range(1, 100));
58 ranges.add(new Range(70, 120));
60 NCList<Range> ncl = new NCList<Range>(ranges);
62 List<Range> overlaps = ncl.findOverlaps(121, 122);
63 assertEquals(overlaps.size(), 0);
65 overlaps = ncl.findOverlaps(21, 22);
66 assertEquals(overlaps.size(), 2);
67 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
68 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
69 assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
70 assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
72 overlaps = ncl.findOverlaps(110, 110);
73 assertEquals(overlaps.size(), 1);
74 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
75 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
78 @Test(groups = "Functional")
79 public void testAdd_onTheEnd()
81 List<Range> ranges = new ArrayList<Range>();
82 ranges.add(new Range(20, 50));
83 NCList<Range> ncl = new NCList<Range>(ranges);
84 assertEquals(ncl.toString(), "[20-50]");
85 assertTrue(ncl.isValid());
87 ncl.add(new Range(60, 70));
88 assertEquals(ncl.toString(), "[20-50, 60-70]");
89 assertTrue(ncl.isValid());
92 @Test(groups = "Functional")
93 public void testAdd_inside()
95 List<Range> ranges = new ArrayList<Range>();
96 ranges.add(new Range(20, 50));
97 NCList<Range> ncl = new NCList<Range>(ranges);
98 assertEquals(ncl.toString(), "[20-50]");
99 assertTrue(ncl.isValid());
101 ncl.add(new Range(30, 40));
102 assertEquals(ncl.toString(), "[20-50 [30-40]]");
105 @Test(groups = "Functional")
106 public void testAdd_onTheFront()
108 List<Range> ranges = new ArrayList<Range>();
109 ranges.add(new Range(20, 50));
110 NCList<Range> ncl = new NCList<Range>(ranges);
111 assertEquals(ncl.toString(), "[20-50]");
112 assertTrue(ncl.isValid());
114 ncl.add(new Range(5, 15));
115 assertEquals(ncl.toString(), "[5-15, 20-50]");
116 assertTrue(ncl.isValid());
119 @Test(groups = "Functional")
120 public void testAdd_enclosing()
122 List<Range> ranges = new ArrayList<Range>();
123 ranges.add(new Range(20, 50));
124 ranges.add(new Range(30, 60));
125 NCList<Range> ncl = new NCList<Range>(ranges);
126 assertEquals(ncl.toString(), "[20-50, 30-60]");
127 assertTrue(ncl.isValid());
128 assertEquals(ncl.getStart(), 20);
130 ncl.add(new Range(10, 70));
131 assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
132 assertTrue(ncl.isValid());
135 @Test(groups = "Functional")
136 public void testAdd_spanning()
138 List<Range> ranges = new ArrayList<Range>();
139 ranges.add(new Range(20, 40));
140 ranges.add(new Range(60, 70));
141 NCList<Range> ncl = new NCList<Range>(ranges);
142 assertEquals(ncl.toString(), "[20-40, 60-70]");
143 assertTrue(ncl.isValid());
145 ncl.add(new Range(30, 50));
146 assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
147 assertTrue(ncl.isValid());
149 ncl.add(new Range(40, 65));
150 assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
151 assertTrue(ncl.isValid());
155 * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
156 * [0-scale] interval to be stored
160 @DataProvider(name = "scalesOfLife")
161 public Object[][] getScales()
163 return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
167 * Do a number of pseudo-random (reproducible) builds of an NCList, with
168 * checks for validity of the data structure, and searches for (pseudo-random)
169 * overlap ranges, for greater (but not perfect!) confidence that corner cases
170 * are being handled correctly.
172 @Test(groups = "Functional", dataProvider = "scalesOfLife")
173 public void testAdd_FindOverlaps_pseudoRandom(Integer scale)
175 NCList<Range> ncl = new NCList<Range>();
177 List<Range> ranges = new ArrayList<Range>(scale);
179 for (int i = 0; i < scale; i++)
181 int r1 = random.nextInt(scale + 1);
182 int r2 = random.nextInt(scale + 1);
183 int from = Math.min(r1, r2);
184 int to = Math.max(r1, r2);
185 Range range = new Range(from, to);
190 * check list format is valid at each stage of its construction
192 assertTrue(ncl.isValid(),
193 String.format("Failed for scale = %d, i=%d", scale, i));
195 assertEquals(ncl.getSize(), count);
197 // System.out.println(ncl.prettyPrint());
200 * sort the list of added ranges - this doesn't affect the test,
201 * just makes it easier to inspect the data in the debugger
203 Collections.sort(ranges, sorter);
205 testFindOverlaps(ncl, scale, ranges);
209 * A helper method that generates pseudo-random range queries and veries that
210 * findOverlaps returns the correct matches
213 * the NCList to query
215 * ncl maximal range is [0, scale]
217 * a list of the ranges stored in ncl
219 protected void testFindOverlaps(NCList<Range> ncl, int scale,
222 int halfScale = scale / 2;
223 int minIterations = 20;
226 * generates ranges in [-halfScale, scale+halfScale]
227 * - some should be internal to [0, scale] P = 1/4
228 * - some should lie before 0 P = 1/16
229 * - some should lie after scale P = 1/16
230 * - some should overlap left P = 1/4
231 * - some should overlap right P = 1/4
232 * - some should enclose P = 1/8
234 * 50 iterations give a 96% probability of including the
235 * unlikeliest case; keep going until we have done all!
237 boolean inside = false;
238 boolean enclosing = false;
239 boolean before = false;
240 boolean after = false;
241 boolean overlapLeft = false;
242 boolean overlapRight = false;
243 boolean allCasesCovered = false;
246 while (i < minIterations || !allCasesCovered)
249 int r1 = random.nextInt((scale + 1) * 2);
250 int r2 = random.nextInt((scale + 1) * 2);
251 int from = Math.min(r1, r2) - halfScale;
252 int to = Math.max(r1, r2) - halfScale;
255 * ensure all cases of interest get covered
257 inside |= from >= 0 && to <= scale;
258 enclosing |= from <= 0 && to >= scale;
260 after |= from > scale;
261 overlapLeft |= from < 0 && to >= 0 && to <= scale;
262 overlapRight |= from >= 0 && from <= scale && to > scale;
263 if (!allCasesCovered)
265 allCasesCovered |= inside && enclosing && before && after
266 && overlapLeft && overlapRight;
271 .format("Covered all findOverlaps cases after %d iterations for scale %d",
276 verifyFindOverlaps(ncl, from, to, ranges);
281 * A helper method that verifies that overlaps found by interrogating an
282 * NCList correctly match those found by brute force search
289 protected void verifyFindOverlaps(NCList<Range> ncl, int from, int to,
292 List<Range> overlaps = ncl.findOverlaps(from, to);
295 * check returned entries do indeed overlap from-to range
297 for (Range r : overlaps)
299 int begin = r.getBegin();
300 int end = r.getEnd();
301 assertTrue(begin <= to && end >= from, String.format(
302 "[%d, %d] does not overlap query range [%d, %d]", begin, end,
307 * check overlapping ranges are included in the results
308 * (the test above already shows non-overlapping ranges are not)
310 for (Range r : ranges)
312 int begin = r.getBegin();
313 int end = r.getEnd();
314 if (begin <= to && end >= from)
316 boolean found = overlaps.contains(r);
317 assertTrue(found, String.format(
318 "[%d, %d] missing in query range [%d, %d]", begin, end,
324 @Test(groups = "Functional")
325 public void testGetEntries()
327 List<Range> ranges = new ArrayList<Range>();
328 Range r1 = new Range(20, 20);
329 Range r2 = new Range(10, 20);
330 Range r3 = new Range(15, 30);
331 Range r4 = new Range(10, 30);
332 Range r5 = new Range(11, 19);
333 Range r6 = new Range(10, 20);
341 NCList<Range> ncl = new NCList<Range>(ranges);
342 Range r7 = new Range(1, 100);
345 List<Range> contents = ncl.getEntries();
346 assertEquals(contents.size(), 7);
347 assertTrue(contents.contains(r1));
348 assertTrue(contents.contains(r2));
349 assertTrue(contents.contains(r3));
350 assertTrue(contents.contains(r4));
351 assertTrue(contents.contains(r5));
352 assertTrue(contents.contains(r6));
353 assertTrue(contents.contains(r7));
355 ncl = new NCList<Range>();
356 assertTrue(ncl.getEntries().isEmpty());
359 @Test(groups = "Functional")
360 public void testDelete()
362 List<Range> ranges = new ArrayList<Range>();
363 Range r1 = new Range(20, 30);
365 NCList<Range> ncl = new NCList<Range>(ranges);
366 assertTrue(ncl.getEntries().contains(r1));
368 Range r2 = new Range(20, 30);
369 assertFalse(ncl.delete(null)); // null argument
370 assertFalse(ncl.delete(r2)); // never added
371 assertTrue(ncl.delete(r1)); // success
372 assertTrue(ncl.getEntries().isEmpty());
375 * tests where object.equals() == true
377 NCList<SequenceFeature> features = new NCList<SequenceFeature>();
378 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
380 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
383 assertEquals(sf1, sf2); // sf1.equals(sf2)
384 assertFalse(features.delete(sf2)); // equality is not enough for deletion
385 assertTrue(features.getEntries().contains(sf1)); // still there!
386 assertTrue(features.delete(sf1));
387 assertTrue(features.getEntries().isEmpty()); // gone now
390 * test with duplicate objects in NCList
394 assertEquals(features.getEntries().size(), 2);
395 assertSame(features.getEntries().get(0), sf1);
396 assertSame(features.getEntries().get(1), sf1);
397 assertTrue(features.delete(sf1)); // first match only is deleted
398 assertTrue(features.contains(sf1));
399 assertEquals(features.getSize(), 1);
400 assertTrue(features.delete(sf1));
401 assertTrue(features.getEntries().isEmpty());
404 @Test(groups = "Functional")
405 public void testAdd_overlapping()
407 List<Range> ranges = new ArrayList<Range>();
408 ranges.add(new Range(40, 50));
409 ranges.add(new Range(20, 30));
410 NCList<Range> ncl = new NCList<Range>(ranges);
411 assertEquals(ncl.toString(), "[20-30, 40-50]");
412 assertTrue(ncl.isValid());
415 * add range overlapping internally
417 ncl.add(new Range(25, 35));
418 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
419 assertTrue(ncl.isValid());
422 * add range overlapping last range
424 ncl.add(new Range(45, 55));
425 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
426 assertTrue(ncl.isValid());
429 * add range overlapping first range
431 ncl.add(new Range(15, 25));
432 assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
433 assertTrue(ncl.isValid());
437 * Test the contains method (which uses object equals test)
439 @Test(groups = "Functional")
440 public void testContains()
442 NCList<SequenceFeature> ncl = new NCList<SequenceFeature>();
443 SequenceFeature sf1 = new SequenceFeature("type", "desc", 1, 10, 2f,
445 SequenceFeature sf2 = new SequenceFeature("type", "desc", 1, 10, 2f,
447 SequenceFeature sf3 = new SequenceFeature("type", "desc", 1, 10, 2f,
451 assertTrue(ncl.contains(sf1));
452 assertTrue(ncl.contains(sf2)); // sf1.equals(sf2)
453 assertFalse(ncl.contains(sf3)); // !sf1.equals(sf3)
456 * make some deeper structure in the NCList
458 SequenceFeature sf4 = new SequenceFeature("type", "desc", 2, 9, 2f,
461 assertTrue(ncl.contains(sf4));
462 SequenceFeature sf5 = new SequenceFeature("type", "desc", 4, 5, 2f,
464 SequenceFeature sf6 = new SequenceFeature("type", "desc", 6, 8, 2f,
468 assertTrue(ncl.contains(sf5));
469 assertTrue(ncl.contains(sf6));