1 package jalview.datamodel.features;
2 import static org.testng.Assert.assertEquals;
3 import static org.testng.Assert.assertTrue;
5 import java.util.ArrayList;
6 import java.util.Collections;
7 import java.util.Comparator;
9 import java.util.Random;
11 import org.testng.annotations.DataProvider;
12 import org.testng.annotations.Test;
14 public class NCListTest
17 private Random random = new Random(107);
19 private Comparator<ContiguousI> sorter = new RangeComparator(true);
22 * A basic sanity test of the constructor
24 @Test(groups = "Functional")
25 public void testConstructor()
27 List<Range> ranges = new ArrayList<Range>();
28 ranges.add(new Range(20, 20));
29 ranges.add(new Range(10, 20));
30 ranges.add(new Range(15, 30));
31 ranges.add(new Range(10, 30));
32 ranges.add(new Range(11, 19));
33 ranges.add(new Range(10, 20));
34 ranges.add(new Range(1, 100));
36 NCList<Range> ncl = new NCList<Range>(ranges);
37 String expected = "[1-100 [10-30 [10-20 [10-20 [11-19]]]], 15-30 [20-20]]";
38 assertEquals(ncl.toString(), expected);
39 assertTrue(ncl.isValid());
41 Collections.reverse(ranges);
42 ncl = new NCList<Range>(ranges);
43 assertEquals(ncl.toString(), expected);
44 assertTrue(ncl.isValid());
47 @Test(groups = "Functional")
48 public void testFindOverlaps()
50 List<Range> ranges = new ArrayList<Range>();
51 ranges.add(new Range(20, 50));
52 ranges.add(new Range(30, 70));
53 ranges.add(new Range(1, 100));
54 ranges.add(new Range(70, 120));
56 NCList<Range> ncl = new NCList<Range>(ranges);
58 List<Range> overlaps = ncl.findOverlaps(121, 122);
59 assertEquals(overlaps.size(), 0);
61 overlaps = ncl.findOverlaps(21, 22);
62 assertEquals(overlaps.size(), 2);
63 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 1);
64 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 100);
65 assertEquals(((ContiguousI) overlaps.get(1)).getBegin(), 20);
66 assertEquals(((ContiguousI) overlaps.get(1)).getEnd(), 50);
68 overlaps = ncl.findOverlaps(110, 110);
69 assertEquals(overlaps.size(), 1);
70 assertEquals(((ContiguousI) overlaps.get(0)).getBegin(), 70);
71 assertEquals(((ContiguousI) overlaps.get(0)).getEnd(), 120);
74 @Test(groups = "Functional")
75 public void testAdd_onTheEnd()
77 List<Range> ranges = new ArrayList<Range>();
78 ranges.add(new Range(20, 50));
79 NCList<Range> ncl = new NCList<Range>(ranges);
80 assertEquals(ncl.toString(), "[20-50]");
81 assertTrue(ncl.isValid());
83 ncl.add(new Range(60, 70));
84 assertEquals(ncl.toString(), "[20-50, 60-70]");
85 assertTrue(ncl.isValid());
88 @Test(groups = "Functional")
89 public void testAdd_inside()
91 List<Range> ranges = new ArrayList<Range>();
92 ranges.add(new Range(20, 50));
93 NCList<Range> ncl = new NCList<Range>(ranges);
94 assertEquals(ncl.toString(), "[20-50]");
95 assertTrue(ncl.isValid());
97 ncl.add(new Range(30, 40));
98 assertEquals(ncl.toString(), "[20-50 [30-40]]");
101 @Test(groups = "Functional")
102 public void testAdd_onTheFront()
104 List<Range> ranges = new ArrayList<Range>();
105 ranges.add(new Range(20, 50));
106 NCList<Range> ncl = new NCList<Range>(ranges);
107 assertEquals(ncl.toString(), "[20-50]");
108 assertTrue(ncl.isValid());
110 ncl.add(new Range(5, 15));
111 assertEquals(ncl.toString(), "[5-15, 20-50]");
112 assertTrue(ncl.isValid());
115 @Test(groups = "Functional")
116 public void testAdd_enclosing()
118 List<Range> ranges = new ArrayList<Range>();
119 ranges.add(new Range(20, 50));
120 ranges.add(new Range(30, 60));
121 NCList<Range> ncl = new NCList<Range>(ranges);
122 assertEquals(ncl.toString(), "[20-50, 30-60]");
123 assertTrue(ncl.isValid());
124 assertEquals(ncl.getStart(), 20);
126 ncl.add(new Range(10, 70));
127 assertEquals(ncl.toString(), "[10-70 [20-50, 30-60]]");
128 assertTrue(ncl.isValid());
131 @Test(groups = "Functional")
132 public void testAdd_spanning()
134 List<Range> ranges = new ArrayList<Range>();
135 ranges.add(new Range(20, 40));
136 ranges.add(new Range(60, 70));
137 NCList<Range> ncl = new NCList<Range>(ranges);
138 assertEquals(ncl.toString(), "[20-40, 60-70]");
139 assertTrue(ncl.isValid());
141 ncl.add(new Range(30, 50));
142 assertEquals(ncl.toString(), "[20-40, 30-50, 60-70]");
143 assertTrue(ncl.isValid());
145 ncl.add(new Range(40, 65));
146 assertEquals(ncl.toString(), "[20-40, 30-50, 40-65, 60-70]");
147 assertTrue(ncl.isValid());
151 * Provides the scales for pseudo-random NCLists i.e. the range of the maximal
152 * [0-scale] interval to be stored
156 @DataProvider(name = "scalesOfLife")
157 public Object[][] getScales()
159 return new Object[][] { new Integer[] { 10 }, new Integer[] { 100 } };
163 * Do a number of pseudo-random (reproducible) builds of an NCList, with
164 * checks for validity of the data structure, and searches for (pseudo-random)
165 * overlap ranges, for greater (but not perfect!) confidence that corner cases
166 * are being handled correctly.
168 @Test(groups = "Functional", dataProvider = "scalesOfLife")
169 public void testAdd_FindOverlaps_pseudoRandom(Integer scale)
171 NCList<Range> ncl = new NCList<Range>();
173 List<Range> ranges = new ArrayList<Range>(scale);
175 for (int i = 0; i < scale; i++)
177 int r1 = random.nextInt(scale + 1);
178 int r2 = random.nextInt(scale + 1);
179 int from = Math.min(r1, r2);
180 int to = Math.max(r1, r2);
181 Range range = new Range(from, to);
186 * check list format is valid at each stage of its construction
188 assertTrue(ncl.isValid(),
189 String.format("Failed for scale = %d, i=%d", scale, i));
191 assertEquals(ncl.getSize(), count);
193 // System.out.println(ncl.prettyPrint());
196 * sort the list of added ranges - this doesn't affect the test,
197 * just makes it easier to inspect the data in the debugger
199 Collections.sort(ranges, sorter);
201 testFindOverlaps(ncl, scale, ranges);
205 * A helper method that generates pseudo-random range queries and veries that
206 * findOverlaps returns the correct matches
209 * the NCList to query
211 * ncl maximal range is [0, scale]
213 * a list of the ranges stored in ncl
215 protected void testFindOverlaps(NCList<Range> ncl, int scale,
218 int halfScale = scale / 2;
219 int minIterations = 20;
222 * generates ranges in [-halfScale, scale+halfScale]
223 * - some should be internal to [0, scale] P = 1/4
224 * - some should lie before 0 P = 1/16
225 * - some should lie after scale P = 1/16
226 * - some should overlap left P = 1/4
227 * - some should overlap right P = 1/4
228 * - some should enclose P = 1/8
230 * 50 iterations give a 96% probability of including the
231 * unlikeliest case; keep going until we have done all!
233 boolean inside = false;
234 boolean enclosing = false;
235 boolean before = false;
236 boolean after = false;
237 boolean overlapLeft = false;
238 boolean overlapRight = false;
239 boolean allCasesCovered = false;
242 while (i < minIterations || !allCasesCovered)
245 int r1 = random.nextInt((scale + 1) * 2);
246 int r2 = random.nextInt((scale + 1) * 2);
247 int from = Math.min(r1, r2) - halfScale;
248 int to = Math.max(r1, r2) - halfScale;
251 * ensure all cases of interest get covered
253 inside |= from >= 0 && to <= scale;
254 enclosing |= from <= 0 && to >= scale;
256 after |= from > scale;
257 overlapLeft |= from < 0 && to >= 0 && to <= scale;
258 overlapRight |= from >= 0 && from <= scale && to > scale;
259 if (!allCasesCovered)
261 allCasesCovered |= inside && enclosing && before && after
262 && overlapLeft && overlapRight;
267 .format("Covered all findOverlaps cases after %d iterations for scale %d",
272 verifyFindOverlaps(ncl, from, to, ranges);
277 * A helper method that verifies that overlaps found by interrogating an
278 * NCList correctly match those found by brute force search
285 protected void verifyFindOverlaps(NCList<Range> ncl, int from, int to,
288 List<Range> overlaps = ncl.findOverlaps(from, to);
291 * check returned entries do indeed overlap from-to range
293 for (Range r : overlaps)
295 int begin = r.getBegin();
296 int end = r.getEnd();
297 assertTrue(begin <= to && end >= from, String.format(
298 "[%d, %d] does not overlap query range [%d, %d]", begin, end,
303 * check overlapping ranges are included in the results
304 * (the test above already shows non-overlapping ranges are not)
306 for (Range r : ranges)
308 int begin = r.getBegin();
309 int end = r.getEnd();
310 if (begin <= to && end >= from)
312 boolean found = overlaps.contains(r);
313 assertTrue(found, String.format(
314 "[%d, %d] missing in query range [%d, %d]", begin, end,
320 @Test(groups = "Functional")
321 public void testGetEntries()
323 List<Range> ranges = new ArrayList<Range>();
324 Range r1 = new Range(20, 20);
325 Range r2 = new Range(10, 20);
326 Range r3 = new Range(15, 30);
327 Range r4 = new Range(10, 30);
328 Range r5 = new Range(11, 19);
329 Range r6 = new Range(10, 20);
337 NCList<Range> ncl = new NCList<Range>(ranges);
338 Range r7 = new Range(1, 100);
341 List<Range> contents = ncl.getEntries();
342 assertEquals(contents.size(), 7);
343 assertTrue(contents.contains(r1));
344 assertTrue(contents.contains(r2));
345 assertTrue(contents.contains(r3));
346 assertTrue(contents.contains(r4));
347 assertTrue(contents.contains(r5));
348 assertTrue(contents.contains(r6));
349 assertTrue(contents.contains(r7));
351 ncl = new NCList<Range>();
352 assertTrue(ncl.getEntries().isEmpty());
355 @Test(groups = "Functional")
356 public void testDelete()
358 assertTrue(false, "todo");
361 @Test(groups = "Functional")
362 public void testAdd_overlapping()
364 List<Range> ranges = new ArrayList<Range>();
365 ranges.add(new Range(40, 50));
366 ranges.add(new Range(20, 30));
367 NCList<Range> ncl = new NCList<Range>(ranges);
368 assertEquals(ncl.toString(), "[20-30, 40-50]");
369 assertTrue(ncl.isValid());
372 * add range overlapping internally
374 ncl.add(new Range(25, 35));
375 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50]");
376 assertTrue(ncl.isValid());
379 * add range overlapping last range
381 ncl.add(new Range(45, 55));
382 assertEquals(ncl.toString(), "[20-30, 25-35, 40-50, 45-55]");
383 assertTrue(ncl.isValid());
386 * add range overlapping first range
388 ncl.add(new Range(15, 25));
389 assertEquals(ncl.toString(), "[15-25, 20-30, 25-35, 40-50, 45-55]");
390 assertTrue(ncl.isValid());