### Question:
DoubleLinkedCountingSet { public void increment(int key) { int index = sparse[key]; if (index < elementsCount && dense[index] == key) { counts[index]++; } else { index = elementsCount++; sparse[key] = index; dense[index] = key; counts[index] = 1; } } DoubleLinkedCountingSet(int maxValue, int maxValues); void increment(int key); void clear(); final int[] sparse; final int[] dense; final int[] counts; public int elementsCount; }### Answer:
@Test public void testSimple() { DoubleLinkedCountingSet s = new DoubleLinkedCountingSet(10, 5); assertEquals(0, s.elementsCount); s.increment(3); assertEquals(1, s.elementsCount); assertEquals(1, s.counts[0]); assertEquals(3, s.dense[0]); s.increment(10); assertEquals(2, s.elementsCount); assertEquals(1, s.counts[1]); assertEquals(10, s.dense[1]); s.increment(3); assertEquals(2, s.elementsCount); assertEquals(2, s.counts[0]); }
@Test @Repeat(iterations = 20) public void testRandomized() { int maxValue = randomIntBetween(0, 1000); int maxValues = randomIntBetween(0, maxValue); int [] values = new int [maxValues]; for (int i = 0; i < values.length; i++) { values[i] = randomIntBetween(0, maxValue); } DoubleLinkedCountingSet s = new DoubleLinkedCountingSet(maxValue, maxValues); IntIntOpenHashMap ref = IntIntOpenHashMap.newInstance(); for (int i = 0; i < maxValues * 10; i++) { int r = values[randomIntBetween(0, values.length - 1)]; ref.addTo(r, 1); s.increment(r); } IntIntOpenHashMap result = IntIntOpenHashMap.newInstance(); for (int i = 0; i < s.elementsCount; i++) { int k = s.dense[i]; int v = s.counts[i]; assertTrue(!result.containsKey(k)); result.put(k, v); } assertEquals(ref, result); }