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