1 package org.broadinstitute.hellbender.tools.spark.utils;
2 
3 import org.broadinstitute.hellbender.tools.spark.sv.utils.SVUtils;
4 import org.broadinstitute.hellbender.tools.spark.utils.HopscotchMapTest.IntPair;
5 import org.broadinstitute.hellbender.GATKBaseTest;
6 import org.testng.Assert;
7 import org.testng.annotations.Test;
8 
9 import java.util.Arrays;
10 import java.util.List;
11 import java.util.stream.Collectors;
12 
13 public final class HopscotchMultiMapTest extends GATKBaseTest {
14 
15     // a HopscotchMultiMap is just like a HopscotchCollection, which is separately tested,
16     //    except that retrieval is by key rather than by entry.
17     // so we'll just test that new behavior here.
18 
19     private static final List<IntPair> testVals = Arrays.asList(
20             new IntPair(1,2), new IntPair(1,2), // repeated entries are legal in a multimap
21             new IntPair(1,3), // as are repeated keys
22             new IntPair(3,4), new IntPair(5,6));
23     private static final IntPair notInTestVals = new IntPair(7,8);
24 
25     @Test
addTest()26     void addTest() {
27         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>();
28         for ( final IntPair entry : testVals ) {
29             Assert.assertTrue(hopscotchMultiMap.add(entry));
30         }
31         Assert.assertEquals(hopscotchMultiMap.size(), testVals.size());
32     }
33 
34     @Test
containsTest()35     void containsTest() {
36         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>(testVals);
37         Assert.assertEquals(hopscotchMultiMap.size(), testVals.size());
38         for ( final IntPair entry : testVals ) {
39             Assert.assertTrue(hopscotchMultiMap.contains(entry.getKey()));
40         }
41         Assert.assertFalse(hopscotchMultiMap.contains(notInTestVals));
42     }
43 
44     @Test
findTest()45     void findTest() {
46         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>(testVals);
47         for ( final IntPair entry : testVals ) {
48             Assert.assertEquals(hopscotchMultiMap.find(entry.getKey()).getKey(), entry.getKey());
49         }
50         Assert.assertNull(hopscotchMultiMap.find(notInTestVals));
51     }
52 
53     @Test
findEachTest()54     void findEachTest() {
55         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>(testVals);
56         for ( final Integer key : testVals.stream().map(IntPair::getKey).collect(Collectors.toSet()) ) {
57             Assert.assertEquals(SVUtils.iteratorSize(hopscotchMultiMap.findEach(key)),
58                     testVals.stream().filter(intPair -> intPair.getKey().equals(key)).count());
59         }
60         Assert.assertEquals(SVUtils.iteratorSize(hopscotchMultiMap.findEach(notInTestVals)), 0);
61     }
62 
63     @Test
removeTest()64     void removeTest() {
65         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>(testVals);
66         for ( final IntPair entry : testVals ) {
67             Assert.assertTrue(hopscotchMultiMap.remove(entry.getKey()));
68         }
69         Assert.assertEquals(hopscotchMultiMap.size(), 0);
70     }
71 
72     @Test
removeEachTest()73     void removeEachTest() {
74         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>(testVals);
75         for ( final Integer key : testVals.stream().map(IntPair::getKey).collect(Collectors.toSet()) ) {
76             Assert.assertTrue(hopscotchMultiMap.removeEach(key));
77             Assert.assertFalse(hopscotchMultiMap.removeEach(key));
78         }
79         Assert.assertEquals(hopscotchMultiMap.size(), 0);
80     }
81 
82     // found a bug in removeEach when multiple keys hash to the same bucket
83     // (non-equivalent keys were getting deleted)
84     // this test demonstrates the fix
85     @Test
removeEachBugTest()86     void removeEachBugTest() {
87         final HopscotchMultiMap<Integer, Integer, IntPair> hopscotchMultiMap = new HopscotchMultiMap<>();
88         final int capacity = hopscotchMultiMap.capacity();
89         hopscotchMultiMap.add(new IntPair(1, 1));
90         hopscotchMultiMap.add(new IntPair(capacity+1, 1));
91         hopscotchMultiMap.add(new IntPair(1, 2));
92         hopscotchMultiMap.add(new IntPair(capacity+1, 2));
93         hopscotchMultiMap.add(new IntPair(1, 3));
94         Assert.assertTrue(hopscotchMultiMap.removeEach(1));
95         Assert.assertEquals(hopscotchMultiMap.size(),2);
96     }
97 }
98