1 /* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15 package com.google.common.collect; 16 17 import static com.google.common.truth.Truth.assertThat; 18 19 import com.google.common.collect.testing.MapTestSuiteBuilder; 20 import com.google.common.collect.testing.TestStringMapGenerator; 21 import com.google.common.collect.testing.features.CollectionFeature; 22 import com.google.common.collect.testing.features.CollectionSize; 23 import com.google.common.collect.testing.features.MapFeature; 24 import java.util.List; 25 import java.util.Map; 26 import java.util.Map.Entry; 27 import junit.framework.Test; 28 import junit.framework.TestCase; 29 import junit.framework.TestSuite; 30 31 /** 32 * Tests for {@code CompactLinkedHashMap}. 33 * 34 * @author Louis Wasserman 35 */ 36 public class CompactLinkedHashMapTest extends TestCase { suite()37 public static Test suite() { 38 TestSuite suite = new TestSuite(); 39 suite.addTest( 40 MapTestSuiteBuilder.using( 41 new TestStringMapGenerator() { 42 @Override 43 protected Map<String, String> create(Entry<String, String>[] entries) { 44 Map<String, String> map = CompactLinkedHashMap.create(); 45 for (Entry<String, String> entry : entries) { 46 map.put(entry.getKey(), entry.getValue()); 47 } 48 return map; 49 } 50 }) 51 .named("CompactLinkedHashMap") 52 .withFeatures( 53 CollectionSize.ANY, 54 CollectionFeature.SUPPORTS_ITERATOR_REMOVE, 55 MapFeature.GENERAL_PURPOSE, 56 MapFeature.ALLOWS_NULL_KEYS, 57 MapFeature.ALLOWS_NULL_VALUES, 58 CollectionFeature.SERIALIZABLE, 59 CollectionFeature.KNOWN_ORDER) 60 .createTestSuite()); 61 suite.addTest( 62 MapTestSuiteBuilder.using( 63 new TestStringMapGenerator() { 64 @Override 65 protected Map<String, String> create(Entry<String, String>[] entries) { 66 CompactLinkedHashMap<String, String> map = CompactLinkedHashMap.create(); 67 map.convertToHashFloodingResistantImplementation(); 68 for (Entry<String, String> entry : entries) { 69 map.put(entry.getKey(), entry.getValue()); 70 } 71 return map; 72 } 73 }) 74 .named("CompactLinkedHashMap with flooding resistance") 75 .withFeatures( 76 CollectionSize.ANY, 77 CollectionFeature.SUPPORTS_ITERATOR_REMOVE, 78 MapFeature.GENERAL_PURPOSE, 79 MapFeature.ALLOWS_NULL_KEYS, 80 MapFeature.ALLOWS_NULL_VALUES, 81 CollectionFeature.SERIALIZABLE, 82 CollectionFeature.KNOWN_ORDER) 83 .createTestSuite()); 84 suite.addTestSuite(CompactLinkedHashMapTest.class); 85 suite.addTestSuite(FloodingTest.class); 86 return suite; 87 } 88 testInsertionOrder()89 public void testInsertionOrder() { 90 Map<Integer, String> map = CompactLinkedHashMap.create(); 91 map.put(1, "a"); 92 map.put(4, "b"); 93 map.put(3, "d"); 94 map.put(2, "c"); 95 testHasMapEntriesInOrder(map, 1, "a", 4, "b", 3, "d", 2, "c"); 96 } 97 testInsertionOrderAfterPutKeyTwice()98 public void testInsertionOrderAfterPutKeyTwice() { 99 Map<Integer, String> map = CompactLinkedHashMap.create(); 100 map.put(1, "a"); 101 map.put(4, "b"); 102 map.put(3, "d"); 103 map.put(2, "c"); 104 map.put(1, "e"); 105 testHasMapEntriesInOrder(map, 1, "e", 4, "b", 3, "d", 2, "c"); 106 } 107 testInsertionOrderAfterRemoveFirstEntry()108 public void testInsertionOrderAfterRemoveFirstEntry() { 109 Map<Integer, String> map = CompactLinkedHashMap.create(); 110 map.put(1, "a"); 111 map.put(4, "b"); 112 map.put(3, "d"); 113 map.put(2, "c"); 114 map.remove(1); 115 testHasMapEntriesInOrder(map, 4, "b", 3, "d", 2, "c"); 116 } 117 testInsertionOrderAfterRemoveMiddleEntry()118 public void testInsertionOrderAfterRemoveMiddleEntry() { 119 Map<Integer, String> map = CompactLinkedHashMap.create(); 120 map.put(1, "a"); 121 map.put(4, "b"); 122 map.put(3, "d"); 123 map.put(2, "c"); 124 map.remove(4); 125 testHasMapEntriesInOrder(map, 1, "a", 3, "d", 2, "c"); 126 } 127 testInsertionOrderAfterRemoveLastEntry()128 public void testInsertionOrderAfterRemoveLastEntry() { 129 Map<Integer, String> map = CompactLinkedHashMap.create(); 130 map.put(1, "a"); 131 map.put(4, "b"); 132 map.put(3, "d"); 133 map.put(2, "c"); 134 map.remove(2); 135 testHasMapEntriesInOrder(map, 1, "a", 4, "b", 3, "d"); 136 } 137 testTrimToSize()138 public void testTrimToSize() { 139 CompactLinkedHashMap<Integer, String> map = CompactLinkedHashMap.createWithExpectedSize(100); 140 map.put(1, "a"); 141 map.put(4, "b"); 142 map.put(3, "d"); 143 map.put(2, "c"); 144 map.trimToSize(); 145 assertThat(map.entries).hasLength(4); 146 assertThat(map.keys).hasLength(4); 147 assertThat(map.values).hasLength(4); 148 assertThat(map.links).hasLength(4); 149 assertEquals(4, map.size()); 150 testHasMapEntriesInOrder(map, 1, "a", 4, "b", 3, "d", 2, "c"); 151 } 152 testHasMapEntriesInOrder(Map<?, ?> map, Object... alternatingKeysAndValues)153 private void testHasMapEntriesInOrder(Map<?, ?> map, Object... alternatingKeysAndValues) { 154 List<? extends Entry<?, ?>> entries = Lists.newArrayList(map.entrySet()); 155 List<Object> keys = Lists.newArrayList(map.keySet()); 156 List<Object> values = Lists.newArrayList(map.values()); 157 assertEquals(2 * entries.size(), alternatingKeysAndValues.length); 158 assertEquals(2 * keys.size(), alternatingKeysAndValues.length); 159 assertEquals(2 * values.size(), alternatingKeysAndValues.length); 160 for (int i = 0; i < map.size(); i++) { 161 Object expectedKey = alternatingKeysAndValues[2 * i]; 162 Object expectedValue = alternatingKeysAndValues[2 * i + 1]; 163 Entry<Object, Object> expectedEntry = Maps.immutableEntry(expectedKey, expectedValue); 164 assertEquals(expectedEntry, entries.get(i)); 165 assertEquals(expectedKey, keys.get(i)); 166 assertEquals(expectedValue, values.get(i)); 167 } 168 } 169 testAllocArraysDefault()170 public void testAllocArraysDefault() { 171 CompactLinkedHashMap<Integer, String> map = CompactLinkedHashMap.create(); 172 assertThat(map.needsAllocArrays()).isTrue(); 173 assertThat(map.entries).isNull(); 174 assertThat(map.keys).isNull(); 175 assertThat(map.values).isNull(); 176 assertThat(map.links).isNull(); 177 178 map.put(1, Integer.toString(1)); 179 assertThat(map.needsAllocArrays()).isFalse(); 180 assertThat(map.entries).hasLength(CompactHashing.DEFAULT_SIZE); 181 assertThat(map.keys).hasLength(CompactHashing.DEFAULT_SIZE); 182 assertThat(map.values).hasLength(CompactHashing.DEFAULT_SIZE); 183 assertThat(map.links).hasLength(CompactHashing.DEFAULT_SIZE); 184 } 185 testAllocArraysExpectedSize()186 public void testAllocArraysExpectedSize() { 187 for (int i = 0; i <= CompactHashing.DEFAULT_SIZE; i++) { 188 CompactLinkedHashMap<Integer, String> map = CompactLinkedHashMap.createWithExpectedSize(i); 189 assertThat(map.needsAllocArrays()).isTrue(); 190 assertThat(map.entries).isNull(); 191 assertThat(map.keys).isNull(); 192 assertThat(map.values).isNull(); 193 assertThat(map.links).isNull(); 194 195 map.put(1, Integer.toString(1)); 196 assertThat(map.needsAllocArrays()).isFalse(); 197 int expectedSize = Math.max(1, i); 198 assertThat(map.entries).hasLength(expectedSize); 199 assertThat(map.keys).hasLength(expectedSize); 200 assertThat(map.values).hasLength(expectedSize); 201 assertThat(map.links).hasLength(expectedSize); 202 } 203 } 204 205 public static class FloodingTest extends AbstractHashFloodingTest<Map<Object, Object>> { FloodingTest()206 public FloodingTest() { 207 super( 208 ImmutableList.of(Construction.mapFromKeys(CompactLinkedHashMap::create)), 209 n -> n * Math.log(n), 210 ImmutableList.of(QueryOp.MAP_GET)); 211 } 212 } 213 } 214