Package: CompactHashSetTest

CompactHashSetTest

nameinstructionbranchcomplexitylinemethod
CompactHashSetTest()
M: 3 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
createSet()
M: 4 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
createSet(Collection)
M: 5 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
createSet(int)
M: 5 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
createSet(int, float)
M: 6 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
getInternalArray(Set)
M: 68 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 17 C: 0
0%
M: 1 C: 0
0%
getInternalCapacity(Set)
M: 7 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 2 C: 0
0%
M: 1 C: 0
0%
getInternalLoadFactor(Set)
M: 77 C: 0
0%
M: 16 C: 0
0%
M: 9 C: 0
0%
M: 18 C: 0
0%
M: 1 C: 0
0%
getNextPowerOfTwo(int)
M: 36 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
getRandomInteger()
M: 7 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
getRandomString()
M: 4 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
randomIntegerListNotIn(int, Collection)
M: 33 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
randomStringDequeNotIn(int, Collection)
M: 33 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
randomStringListNotIn(int, Collection)
M: 33 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
randomStringSetNotIn(int, Collection)
M: 33 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
static {...}
M: 8 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
testAdd()
M: 256 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 53 C: 0
0%
M: 1 C: 0
0%
testAddAll()
M: 693 C: 0
0%
M: 50 C: 0
0%
M: 26 C: 0
0%
M: 118 C: 0
0%
M: 1 C: 0
0%
testClear()
M: 590 C: 0
0%
M: 50 C: 0
0%
M: 26 C: 0
0%
M: 104 C: 0
0%
M: 1 C: 0
0%
testContains()
M: 677 C: 0
0%
M: 74 C: 0
0%
M: 38 C: 0
0%
M: 107 C: 0
0%
M: 1 C: 0
0%
testContainsAll()
M: 254 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testEquals()
M: 312 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 80 C: 0
0%
M: 1 C: 0
0%
testHashCode()
M: 562 C: 0
0%
M: 104 C: 0
0%
M: 53 C: 0
0%
M: 80 C: 0
0%
M: 1 C: 0
0%
testInstantiationCopy()
M: 256 C: 0
0%
M: 10 C: 0
0%
M: 6 C: 0
0%
M: 45 C: 0
0%
M: 1 C: 0
0%
testInstantiationEmpty()
M: 27 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 6 C: 0
0%
M: 1 C: 0
0%
testInstantiationLoadFactor()
M: 277 C: 0
0%
M: 24 C: 0
0%
M: 13 C: 0
0%
M: 34 C: 0
0%
M: 1 C: 0
0%
testInstantiationSize()
M: 151 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 32 C: 0
0%
M: 1 C: 0
0%
testIsEmpty()
M: 84 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 21 C: 0
0%
M: 1 C: 0
0%
testIterator()
M: 196 C: 0
0%
M: 18 C: 0
0%
M: 10 C: 0
0%
M: 55 C: 0
0%
M: 1 C: 0
0%
testIteratorRemove()
M: 129 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 36 C: 0
0%
M: 1 C: 0
0%
testRehashing()
M: 171 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 29 C: 0
0%
M: 1 C: 0
0%
testRemove()
M: 99 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 21 C: 0
0%
M: 1 C: 0
0%

Coverage

1: /*******************************************************************************
2: * Copyright (c) 2011, 2012 Obeo.
3: * All rights reserved. This program and the accompanying materials
4: * are made available under the terms of the Eclipse Public License v1.0
5: * which accompanies this distribution, and is available at
6: * http://www.eclipse.org/legal/epl-v10.html
7: *
8: * Contributors:
9: * Obeo - initial API and implementation
10: *******************************************************************************/
11: package org.eclipse.acceleo.common.tests.unit.utils;
12:
13: import static org.junit.Assert.assertEquals;
14: import static org.junit.Assert.assertFalse;
15: import static org.junit.Assert.assertNotNull;
16: import static org.junit.Assert.assertNull;
17: import static org.junit.Assert.assertSame;
18: import static org.junit.Assert.assertTrue;
19: import static org.junit.Assert.fail;
20:
21: import java.lang.reflect.Field;
22: import java.util.ArrayList;
23: import java.util.Collection;
24: import java.util.Collections;
25: import java.util.ConcurrentModificationException;
26: import java.util.HashSet;
27: import java.util.Iterator;
28: import java.util.List;
29: import java.util.NoSuchElementException;
30: import java.util.Set;
31:
32: import org.eclipse.acceleo.common.utils.CircularArrayDeque;
33: import org.eclipse.acceleo.common.utils.CompactHashSet;
34: import org.eclipse.acceleo.common.utils.Deque;
35: import org.junit.Test;
36:
37: /**
38: * Tests for the {@link CompactHashSet} behavior.
39: *
40: * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
41: */
42:•public class CompactHashSetTest {
43:         /**
44:          * This will test the behavior of {@link CompactHashSet#add(Object)} with random elements.
45:          */
46:         @Test
47:         public void testAdd() {
48:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
49:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
50:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
51:                 Collection<Object> duplicatesList = new ArrayList<Object>();
52:•                for (int i = 0; i < 40; i++) {
53:                         // our random integers and strings are values from 0-100000.
54:                         // Make sure we cannot have a conflict
55:                         int dupe = ((i / 2) + 1) * 100001;
56:                         duplicatesList.add(Integer.valueOf(dupe));
57:                         duplicatesList.add(String.valueOf(dupe));
58:                 }
59:                 duplicatesList.add(null);
60:                 duplicatesList.add(null);
61:
62:                 Set<Object> set = createSet();
63:
64:                 int size = 0;
65:•                for (Integer integer : listInt10) {
66:                         boolean modified = set.add(integer);
67:                         assertTrue(modified);
68:                         assertTrue(set.contains(integer));
69:                         assertEquals(++size, set.size());
70:                 }
71:                 assertTrue(set.containsAll(listInt10));
72:                 assertFalse(set.contains(null));
73:
74:•                for (String string : setString20) {
75:                         boolean modified = set.add(string);
76:                         assertTrue(modified);
77:                         assertTrue(set.contains(string));
78:                         assertEquals(++size, set.size());
79:                 }
80:                 assertTrue(set.containsAll(setString20));
81:                 assertFalse(set.contains(null));
82:
83:•                for (String string : dequeString40) {
84:                         boolean modified = set.add(string);
85:                         assertTrue(modified);
86:                         assertTrue(set.contains(string));
87:                         assertEquals(++size, set.size());
88:                 }
89:                 assertTrue(set.containsAll(dequeString40));
90:                 assertFalse(set.contains(null));
91:
92:•                for (Object o : duplicatesList) {
93:•                        if (set.contains(o)) {
94:                                 boolean modified = set.add(o);
95:                                 assertFalse(modified);
96:                                 assertTrue(set.contains(o));
97:                                 assertEquals(size, set.size());
98:                         } else {
99:                                 boolean modified = set.add(o);
100:                                 assertTrue(modified);
101:                                 assertTrue(set.contains(o));
102:                                 assertEquals(++size, set.size());
103:                         }
104:                 }
105:                 assertTrue(set.containsAll(duplicatesList));
106:                 assertTrue(set.contains(null));
107:
108:                 assertTrue(set.containsAll(listInt10));
109:                 assertTrue(set.containsAll(setString20));
110:                 assertTrue(set.containsAll(dequeString40));
111:                 assertTrue(set.containsAll(duplicatesList));
112:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size()
113:                                 + (duplicatesList.size() / 2), set.size());
114:         }
115:
116:         /**
117:          * This will test the behavior of {@link CompactHashSet#addAll(Collection)} with random elements.
118:          */
119:         @Test
120:         public void testAddAll() {
121:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
122:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
123:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
124:                 Collection<Object> duplicatesList = new ArrayList<Object>();
125:•                for (int i = 0; i < 40; i++) {
126:                         // our random integers and strings are values from 0-100000.
127:                         // Make sure we cannot have a conflict
128:                         int dupe = ((i / 2) + 1) * 100001;
129:                         duplicatesList.add(Integer.valueOf(dupe));
130:                         duplicatesList.add(String.valueOf(dupe));
131:                 }
132:                 duplicatesList.add(null);
133:                 duplicatesList.add(null);
134:
135:                 Set<Object> set = createSet();
136:
137:                 boolean modified = set.addAll(listInt10);
138:                 int expectedCapacity = 16;
139:                 assertTrue(modified);
140:                 assertEquals(listInt10.size(), set.size());
141:                 assertTrue(set.containsAll(listInt10));
142:                 assertFalse(set.containsAll(setString20));
143:                 assertFalse(set.containsAll(dequeString40));
144:                 assertFalse(set.containsAll(duplicatesList));
145:                 assertEquals(expectedCapacity, getInternalCapacity(set));
146:•                for (Integer integer : listInt10) {
147:                         assertTrue(set.contains(integer));
148:                 }
149:•                for (String string : setString20) {
150:                         assertFalse(set.contains(string));
151:                 }
152:•                for (String string : dequeString40) {
153:                         assertFalse(set.contains(string));
154:                 }
155:•                for (Object o : duplicatesList) {
156:                         assertFalse(set.contains(o));
157:                 }
158:                 assertFalse(set.contains(null));
159:
160:                 modified = set.addAll(setString20);
161:                 expectedCapacity = 64;
162:                 assertTrue(modified);
163:                 assertEquals(listInt10.size() + setString20.size(), set.size());
164:                 assertTrue(set.containsAll(listInt10));
165:                 assertTrue(set.containsAll(setString20));
166:                 assertFalse(set.containsAll(dequeString40));
167:                 assertFalse(set.containsAll(duplicatesList));
168:                 assertEquals(expectedCapacity, getInternalCapacity(set));
169:•                for (Integer integer : listInt10) {
170:                         assertTrue(set.contains(integer));
171:                 }
172:•                for (String string : setString20) {
173:                         assertTrue(set.contains(string));
174:                 }
175:•                for (String string : dequeString40) {
176:                         assertFalse(set.contains(string));
177:                 }
178:•                for (Object o : duplicatesList) {
179:                         assertFalse(set.contains(o));
180:                 }
181:                 assertFalse(set.contains(null));
182:
183:                 modified = set.addAll(dequeString40);
184:                 expectedCapacity = 128;
185:                 assertTrue(modified);
186:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), set.size());
187:                 assertTrue(set.containsAll(listInt10));
188:                 assertTrue(set.containsAll(setString20));
189:                 assertTrue(set.containsAll(dequeString40));
190:                 assertFalse(set.containsAll(duplicatesList));
191:                 assertEquals(expectedCapacity, getInternalCapacity(set));
192:•                for (Integer integer : listInt10) {
193:                         assertTrue(set.contains(integer));
194:                 }
195:•                for (String string : setString20) {
196:                         assertTrue(set.contains(string));
197:                 }
198:•                for (String string : dequeString40) {
199:                         assertTrue(set.contains(string));
200:                 }
201:•                for (Object o : duplicatesList) {
202:                         assertFalse(set.contains(o));
203:                 }
204:                 assertFalse(set.contains(null));
205:
206:                 modified = set.addAll(duplicatesList);
207:                 expectedCapacity = 256;
208:                 assertTrue(modified);
209:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size()
210:                                 + (duplicatesList.size() / 2), set.size());
211:                 assertTrue(set.containsAll(listInt10));
212:                 assertTrue(set.containsAll(setString20));
213:                 assertTrue(set.containsAll(dequeString40));
214:                 assertTrue(set.containsAll(duplicatesList));
215:                 assertEquals(expectedCapacity, getInternalCapacity(set));
216:•                for (Integer integer : listInt10) {
217:                         assertTrue(set.contains(integer));
218:                 }
219:•                for (String string : setString20) {
220:                         assertTrue(set.contains(string));
221:                 }
222:•                for (String string : dequeString40) {
223:                         assertTrue(set.contains(string));
224:                 }
225:•                for (Object o : duplicatesList) {
226:                         assertTrue(set.contains(o));
227:                 }
228:                 assertTrue(set.contains(null));
229:
230:                 set.removeAll(setString20);
231:                 assertEquals(listInt10.size() + dequeString40.size() + (duplicatesList.size() / 2), set.size());
232:                 assertTrue(set.containsAll(listInt10));
233:                 assertFalse(set.containsAll(setString20));
234:                 assertTrue(set.containsAll(dequeString40));
235:                 assertTrue(set.containsAll(duplicatesList));
236:                 assertEquals(expectedCapacity, getInternalCapacity(set));
237:•                for (Integer integer : listInt10) {
238:                         assertTrue(set.contains(integer));
239:                 }
240:•                for (String string : setString20) {
241:                         assertFalse(set.contains(string));
242:                 }
243:•                for (String string : dequeString40) {
244:                         assertTrue(set.contains(string));
245:                 }
246:•                for (Object o : duplicatesList) {
247:                         assertTrue(set.contains(o));
248:                 }
249:                 assertTrue(set.contains(null));
250:
251:                 set.addAll(setString20);
252:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size()
253:                                 + (duplicatesList.size() / 2), set.size());
254:                 assertTrue(set.containsAll(listInt10));
255:                 assertTrue(set.containsAll(setString20));
256:                 assertTrue(set.containsAll(dequeString40));
257:                 assertTrue(set.containsAll(duplicatesList));
258:                 assertEquals(expectedCapacity, getInternalCapacity(set));
259:•                for (Integer integer : listInt10) {
260:                         assertTrue(set.contains(integer));
261:                 }
262:•                for (String string : setString20) {
263:                         assertTrue(set.contains(string));
264:                 }
265:•                for (String string : dequeString40) {
266:                         assertTrue(set.contains(string));
267:                 }
268:•                for (Object o : duplicatesList) {
269:                         assertTrue(set.contains(o));
270:                 }
271:                 assertTrue(set.contains(null));
272:         }
273:
274:         /**
275:          * This will test the behavior of {@link CompactHashSet#clear()} with random elements.
276:          */
277:         @Test
278:         public void testClear() {
279:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
280:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
281:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
282:                 Collection<Object> duplicatesList = new ArrayList<Object>();
283:•                for (int i = 0; i < 40; i++) {
284:                         // our random integers and strings are values from 0-100000.
285:                         // Make sure we cannot have a conflict
286:                         int dupe = ((i / 2) + 1) * 100001;
287:                         duplicatesList.add(Integer.valueOf(dupe));
288:                         duplicatesList.add(String.valueOf(dupe));
289:                 }
290:                 duplicatesList.add(null);
291:                 duplicatesList.add(null);
292:
293:                 Set<Object> set = createSet();
294:
295:                 int expectedCapacity = 16;
296:                 set.clear();
297:                 assertTrue(set.isEmpty());
298:                 assertSame(0, set.size());
299:                 assertEquals(expectedCapacity, getInternalCapacity(set));
300:•                for (Integer integer : listInt10) {
301:                         assertFalse(set.contains(integer));
302:                 }
303:•                for (String string : setString20) {
304:                         assertFalse(set.contains(string));
305:                 }
306:•                for (String string : dequeString40) {
307:                         assertFalse(set.contains(string));
308:                 }
309:•                for (Object o : duplicatesList) {
310:                         assertFalse(set.contains(o));
311:                 }
312:                 assertFalse(set.contains(null));
313:
314:                 set.addAll(listInt10);
315:                 set.clear();
316:                 assertTrue(set.isEmpty());
317:                 assertSame(0, set.size());
318:                 assertEquals(expectedCapacity, getInternalCapacity(set));
319:•                for (Integer integer : listInt10) {
320:                         assertFalse(set.contains(integer));
321:                 }
322:•                for (String string : setString20) {
323:                         assertFalse(set.contains(string));
324:                 }
325:•                for (String string : dequeString40) {
326:                         assertFalse(set.contains(string));
327:                 }
328:•                for (Object o : duplicatesList) {
329:                         assertFalse(set.contains(o));
330:                 }
331:                 assertFalse(set.contains(null));
332:
333:                 set.addAll(listInt10);
334:                 set.addAll(setString20);
335:                 expectedCapacity = 64;
336:                 set.clear();
337:                 assertTrue(set.isEmpty());
338:                 assertSame(0, set.size());
339:                 assertEquals(expectedCapacity, getInternalCapacity(set));
340:•                for (Integer integer : listInt10) {
341:                         assertFalse(set.contains(integer));
342:                 }
343:•                for (String string : setString20) {
344:                         assertFalse(set.contains(string));
345:                 }
346:•                for (String string : dequeString40) {
347:                         assertFalse(set.contains(string));
348:                 }
349:•                for (Object o : duplicatesList) {
350:                         assertFalse(set.contains(o));
351:                 }
352:                 assertFalse(set.contains(null));
353:
354:                 set.addAll(listInt10);
355:                 set.addAll(setString20);
356:                 set.addAll(dequeString40);
357:                 expectedCapacity = 128;
358:                 set.clear();
359:                 assertTrue(set.isEmpty());
360:                 assertSame(0, set.size());
361:                 assertEquals(expectedCapacity, getInternalCapacity(set));
362:•                for (Integer integer : listInt10) {
363:                         assertFalse(set.contains(integer));
364:                 }
365:•                for (String string : setString20) {
366:                         assertFalse(set.contains(string));
367:                 }
368:•                for (String string : dequeString40) {
369:                         assertFalse(set.contains(string));
370:                 }
371:•                for (Object o : duplicatesList) {
372:                         assertFalse(set.contains(o));
373:                 }
374:                 assertFalse(set.contains(null));
375:
376:                 set.addAll(listInt10);
377:                 set.addAll(setString20);
378:                 set.addAll(dequeString40);
379:                 set.addAll(duplicatesList);
380:                 expectedCapacity = 256;
381:                 set.clear();
382:                 assertTrue(set.isEmpty());
383:                 assertSame(0, set.size());
384:                 assertEquals(expectedCapacity, getInternalCapacity(set));
385:•                for (Integer integer : listInt10) {
386:                         assertFalse(set.contains(integer));
387:                 }
388:•                for (String string : setString20) {
389:                         assertFalse(set.contains(string));
390:                 }
391:•                for (String string : dequeString40) {
392:                         assertFalse(set.contains(string));
393:                 }
394:•                for (Object o : duplicatesList) {
395:                         assertFalse(set.contains(o));
396:                 }
397:                 assertFalse(set.contains(null));
398:
399:                 set.clear();
400:                 assertTrue(set.isEmpty());
401:                 assertSame(0, set.size());
402:                 assertEquals(expectedCapacity, getInternalCapacity(set));
403:•                for (Integer integer : listInt10) {
404:                         assertFalse(set.contains(integer));
405:                 }
406:•                for (String string : setString20) {
407:                         assertFalse(set.contains(string));
408:                 }
409:•                for (String string : dequeString40) {
410:                         assertFalse(set.contains(string));
411:                 }
412:•                for (Object o : duplicatesList) {
413:                         assertFalse(set.contains(o));
414:                 }
415:                 assertFalse(set.contains(null));
416:         }
417:
418:         /**
419:          * This will test the behavior of {@link CompactHashSet#contains(Object)} with random elements.
420:          */
421:         @Test
422:         public void testContains() {
423:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
424:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
425:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
426:                 Collection<Object> duplicatesList = new ArrayList<Object>();
427:•                for (int i = 0; i < 40; i++) {
428:                         // our random integers and strings are values from 0-100000.
429:                         // Make sure we cannot have a conflict
430:                         int dupe = ((i / 2) + 1) * 100001;
431:                         duplicatesList.add(Integer.valueOf(dupe));
432:                         duplicatesList.add(String.valueOf(dupe));
433:                 }
434:                 duplicatesList.add(null);
435:                 duplicatesList.add(null);
436:
437:                 Set<Object> set = createSet();
438:
439:•                for (Integer integer : listInt10) {
440:                         assertFalse(set.contains(integer));
441:                 }
442:•                for (String string : setString20) {
443:                         assertFalse(set.contains(string));
444:                 }
445:•                for (String string : dequeString40) {
446:                         assertFalse(set.contains(string));
447:                 }
448:•                for (Object o : duplicatesList) {
449:                         assertFalse(set.contains(o));
450:                 }
451:                 assertFalse(set.contains(null));
452:
453:                 set.addAll(listInt10);
454:•                for (Integer integer : listInt10) {
455:                         assertTrue(set.contains(integer));
456:                 }
457:•                for (String string : setString20) {
458:                         assertFalse(set.contains(string));
459:                 }
460:•                for (String string : dequeString40) {
461:                         assertFalse(set.contains(string));
462:                 }
463:•                for (Object o : duplicatesList) {
464:                         assertFalse(set.contains(o));
465:                 }
466:                 assertFalse(set.contains(null));
467:
468:                 set.addAll(setString20);
469:•                for (Integer integer : listInt10) {
470:                         assertTrue(set.contains(integer));
471:                 }
472:•                for (String string : setString20) {
473:                         assertTrue(set.contains(string));
474:                 }
475:•                for (String string : dequeString40) {
476:                         assertFalse(set.contains(string));
477:                 }
478:•                for (Object o : duplicatesList) {
479:                         assertFalse(set.contains(o));
480:                 }
481:                 assertFalse(set.contains(null));
482:
483:                 set.addAll(dequeString40);
484:•                for (Integer integer : listInt10) {
485:                         assertTrue(set.contains(integer));
486:                 }
487:•                for (String string : setString20) {
488:                         assertTrue(set.contains(string));
489:                 }
490:•                for (String string : dequeString40) {
491:                         assertTrue(set.contains(string));
492:                 }
493:•                for (Object o : duplicatesList) {
494:                         assertFalse(set.contains(o));
495:                 }
496:                 assertFalse(set.contains(null));
497:
498:                 set.addAll(duplicatesList);
499:•                for (Integer integer : listInt10) {
500:                         assertTrue(set.contains(integer));
501:                 }
502:•                for (String string : setString20) {
503:                         assertTrue(set.contains(string));
504:                 }
505:•                for (String string : dequeString40) {
506:                         assertTrue(set.contains(string));
507:                 }
508:•                for (Object o : duplicatesList) {
509:                         assertTrue(set.contains(o));
510:                 }
511:                 assertTrue(set.contains(null));
512:
513:                 set.removeAll(setString20);
514:•                for (Integer integer : listInt10) {
515:                         assertTrue(set.contains(integer));
516:                 }
517:•                for (String string : setString20) {
518:                         assertFalse(set.contains(string));
519:                 }
520:•                for (String string : dequeString40) {
521:                         assertTrue(set.contains(string));
522:                 }
523:•                for (Object o : duplicatesList) {
524:                         assertTrue(set.contains(o));
525:                 }
526:                 assertTrue(set.contains(null));
527:
528:                 set.clear();
529:•                for (Integer integer : listInt10) {
530:                         assertFalse(set.contains(integer));
531:                 }
532:•                for (String string : setString20) {
533:                         assertFalse(set.contains(string));
534:                 }
535:•                for (String string : dequeString40) {
536:                         assertFalse(set.contains(string));
537:                 }
538:•                for (Object o : duplicatesList) {
539:                         assertFalse(set.contains(o));
540:                 }
541:                 assertFalse(set.contains(null));
542:
543:                 set.addAll(listInt10);
544:                 set.addAll(setString20);
545:                 set.addAll(dequeString40);
546:                 set.addAll(duplicatesList);
547:•                for (Integer integer : listInt10) {
548:                         assertTrue(set.contains(integer));
549:                 }
550:•                for (String string : setString20) {
551:                         assertTrue(set.contains(string));
552:                 }
553:•                for (String string : dequeString40) {
554:                         assertTrue(set.contains(string));
555:                 }
556:•                for (Object o : duplicatesList) {
557:                         assertTrue(set.contains(o));
558:                 }
559:                 assertTrue(set.contains(null));
560:
561:                 set.removeAll(listInt10);
562:                 set.removeAll(setString20);
563:                 set.removeAll(dequeString40);
564:                 set.removeAll(duplicatesList);
565:•                for (Integer integer : listInt10) {
566:                         assertFalse(set.contains(integer));
567:                 }
568:•                for (String string : setString20) {
569:                         assertFalse(set.contains(string));
570:                 }
571:•                for (String string : dequeString40) {
572:                         assertFalse(set.contains(string));
573:                 }
574:•                for (Object o : duplicatesList) {
575:                         assertFalse(set.contains(o));
576:                 }
577:                 assertFalse(set.contains(null));
578:         }
579:
580:         /**
581:          * This will test the behavior of {@link CompactHashSet#containsAll(Object)} with random elements.
582:          */
583:         @Test
584:         public void testContainsAll() {
585:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
586:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
587:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
588:                 Collection<Object> duplicatesList = new ArrayList<Object>();
589:•                for (int i = 0; i < 40; i++) {
590:                         // our random integers and strings are values from 0-100000.
591:                         // Make sure we cannot have a conflict
592:                         int dupe = ((i / 2) + 1) * 100001;
593:                         duplicatesList.add(Integer.valueOf(dupe));
594:                         duplicatesList.add(String.valueOf(dupe));
595:                 }
596:                 duplicatesList.add(null);
597:                 duplicatesList.add(null);
598:
599:                 Set<Object> set = createSet();
600:
601:                 assertFalse(set.containsAll(listInt10));
602:                 assertFalse(set.containsAll(setString20));
603:                 assertFalse(set.containsAll(dequeString40));
604:                 assertFalse(set.containsAll(duplicatesList));
605:
606:                 set.addAll(listInt10);
607:                 assertTrue(set.containsAll(listInt10));
608:                 assertFalse(set.containsAll(setString20));
609:                 assertFalse(set.containsAll(dequeString40));
610:                 assertFalse(set.containsAll(duplicatesList));
611:
612:                 set.addAll(setString20);
613:                 assertTrue(set.containsAll(listInt10));
614:                 assertTrue(set.containsAll(setString20));
615:                 assertFalse(set.containsAll(dequeString40));
616:                 assertFalse(set.containsAll(duplicatesList));
617:
618:                 set.addAll(dequeString40);
619:                 assertTrue(set.containsAll(listInt10));
620:                 assertTrue(set.containsAll(setString20));
621:                 assertTrue(set.containsAll(dequeString40));
622:                 assertFalse(set.containsAll(duplicatesList));
623:
624:                 set.addAll(duplicatesList);
625:                 assertTrue(set.containsAll(listInt10));
626:                 assertTrue(set.containsAll(setString20));
627:                 assertTrue(set.containsAll(dequeString40));
628:                 assertTrue(set.containsAll(duplicatesList));
629:
630:                 set.removeAll(setString20);
631:                 assertTrue(set.containsAll(listInt10));
632:                 assertFalse(set.containsAll(setString20));
633:                 assertTrue(set.containsAll(dequeString40));
634:                 assertTrue(set.containsAll(duplicatesList));
635:
636:                 set.clear();
637:                 assertFalse(set.containsAll(listInt10));
638:                 assertFalse(set.containsAll(setString20));
639:                 assertFalse(set.containsAll(dequeString40));
640:                 assertFalse(set.containsAll(duplicatesList));
641:
642:                 set.addAll(listInt10);
643:                 set.addAll(setString20);
644:                 set.addAll(dequeString40);
645:                 set.addAll(duplicatesList);
646:                 assertTrue(set.containsAll(listInt10));
647:                 assertTrue(set.containsAll(setString20));
648:                 assertTrue(set.containsAll(dequeString40));
649:                 assertTrue(set.containsAll(duplicatesList));
650:
651:                 set.removeAll(listInt10);
652:                 set.removeAll(setString20);
653:                 set.removeAll(dequeString40);
654:                 set.removeAll(duplicatesList);
655:                 assertFalse(set.containsAll(listInt10));
656:                 assertFalse(set.containsAll(setString20));
657:                 assertFalse(set.containsAll(dequeString40));
658:                 assertFalse(set.containsAll(duplicatesList));
659:         }
660:
661:         /**
662:          * Tests the behavior of {@link CompactHashSet#equals(Object)} with random elements.
663:          */
664:         @Test
665:         public void testEquals() {
666:                 Set<Object> set1 = createSet();
667:                 Set<Object> set2 = createSet();
668:
669:                 Collection<Object> objects1 = new ArrayList<Object>();
670:                 objects1.add(null);
671:                 objects1.addAll(randomStringDequeNotIn(40, Collections.<String> emptySet()));
672:                 objects1.add(null);
673:                 assertSame(42, objects1.size());
674:
675:                 assertTrue(set1.equals(set2));
676:                 assertTrue(set2.equals(set1));
677:
678:                 set1.addAll(objects1);
679:                 set2.addAll(objects1);
680:
681:                 Set<Object> set3 = createSet(set1);
682:
683:                 assertTrue(set1.equals(set2));
684:                 assertTrue(set1.equals(set3));
685:                 assertTrue(set2.equals(set1));
686:                 assertTrue(set2.equals(set3));
687:                 assertTrue(set3.equals(set1));
688:                 assertTrue(set3.equals(set2));
689:
690:•                for (int i = 0; i < 100; i++) {
691:                         String rand = getRandomString();
692:•                        while (set1.contains(rand)) {
693:                                 rand = getRandomString();
694:                         }
695:                         set1.add(rand);
696:                         set2.add(rand);
697:                 }
698:                 set1.add(null);
699:                 set2.add(null);
700:                 assertTrue(set1.equals(set2));
701:                 assertFalse(set1.equals(set3));
702:                 assertTrue(set2.equals(set1));
703:                 assertFalse(set2.equals(set3));
704:                 assertFalse(set3.equals(set1));
705:                 assertFalse(set3.equals(set2));
706:
707:                 set1.remove(null);
708:                 assertFalse(set1.equals(set2));
709:                 assertFalse(set1.equals(set3));
710:                 assertFalse(set2.equals(set1));
711:                 assertFalse(set2.equals(set3));
712:                 assertFalse(set3.equals(set1));
713:                 assertFalse(set3.equals(set2));
714:
715:                 set1.add(null);
716:                 assertTrue(set1.equals(set2));
717:                 assertFalse(set1.equals(set3));
718:                 assertTrue(set2.equals(set1));
719:                 assertFalse(set2.equals(set3));
720:                 assertFalse(set3.equals(set1));
721:                 assertFalse(set3.equals(set2));
722:
723:                 set1.remove(null);
724:                 set2.remove(null);
725:                 assertTrue(set1.equals(set2));
726:                 assertFalse(set1.equals(set3));
727:                 assertTrue(set2.equals(set1));
728:                 assertFalse(set2.equals(set3));
729:                 assertFalse(set3.equals(set1));
730:                 assertFalse(set3.equals(set2));
731:
732:                 set1.clear();
733:                 set2.clear();
734:                 assertTrue(set1.equals(set2));
735:                 assertFalse(set1.equals(set3));
736:                 assertTrue(set2.equals(set1));
737:                 assertFalse(set2.equals(set3));
738:                 assertFalse(set3.equals(set1));
739:                 assertFalse(set3.equals(set2));
740:
741:                 set1.addAll(objects1);
742:                 set2.addAll(objects1);
743:                 assertTrue(set1.equals(set2));
744:                 assertTrue(set1.equals(set3));
745:                 assertTrue(set2.equals(set1));
746:                 assertTrue(set2.equals(set3));
747:                 assertTrue(set3.equals(set1));
748:                 assertTrue(set3.equals(set2));
749:
750:                 set1.clear();
751:                 set2.clear();
752:                 set3.clear();
753:                 assertTrue(set1.equals(set2));
754:                 assertTrue(set1.equals(set3));
755:                 assertTrue(set2.equals(set1));
756:                 assertTrue(set2.equals(set3));
757:                 assertTrue(set3.equals(set1));
758:                 assertTrue(set3.equals(set2));
759:         }
760:
761:         /**
762:          * Tests the behavior of {@link CompactHashSet#hashCode()} with random elements.
763:          */
764:         @Test
765:         public void testHashCode() {
766:                 Set<Object> set1 = createSet();
767:                 Set<Object> set2 = createSet();
768:
769:                 Collection<Object> objects1 = new ArrayList<Object>();
770:                 objects1.add(null);
771:                 objects1.addAll(randomStringDequeNotIn(40, Collections.<String> emptySet()));
772:                 objects1.add(null);
773:                 assertSame(42, objects1.size());
774:
775:•                assertTrue(set1.hashCode() == set2.hashCode());
776:•                assertTrue(set2.hashCode() == set1.hashCode());
777:
778:                 set1.addAll(objects1);
779:                 set2.addAll(objects1);
780:
781:                 Set<Object> set3 = createSet(set1);
782:
783:•                assertTrue(set1.hashCode() == set2.hashCode());
784:•                assertTrue(set1.hashCode() == set3.hashCode());
785:•                assertTrue(set2.hashCode() == set1.hashCode());
786:•                assertTrue(set2.hashCode() == set3.hashCode());
787:•                assertTrue(set3.hashCode() == set1.hashCode());
788:•                assertTrue(set3.hashCode() == set2.hashCode());
789:
790:•                for (int i = 0; i < 100; i++) {
791:                         String rand = getRandomString();
792:•                        while (set1.contains(rand)) {
793:                                 rand = getRandomString();
794:                         }
795:                         set1.add(rand);
796:                         set2.add(rand);
797:                 }
798:                 set1.add(null);
799:                 set2.add(null);
800:•                assertTrue(set1.hashCode() == set2.hashCode());
801:•                assertFalse(set1.hashCode() == set3.hashCode());
802:•                assertTrue(set2.hashCode() == set1.hashCode());
803:•                assertFalse(set2.hashCode() == set3.hashCode());
804:•                assertFalse(set3.hashCode() == set1.hashCode());
805:•                assertFalse(set3.hashCode() == set2.hashCode());
806:
807:                 set1.remove(null);
808:•                assertTrue(set1.hashCode() == set2.hashCode());
809:•                assertFalse(set1.hashCode() == set3.hashCode());
810:•                assertTrue(set2.hashCode() == set1.hashCode());
811:•                assertFalse(set2.hashCode() == set3.hashCode());
812:•                assertFalse(set3.hashCode() == set1.hashCode());
813:•                assertFalse(set3.hashCode() == set2.hashCode());
814:
815:                 set1.add(null);
816:•                assertTrue(set1.hashCode() == set2.hashCode());
817:•                assertFalse(set1.hashCode() == set3.hashCode());
818:•                assertTrue(set2.hashCode() == set1.hashCode());
819:•                assertFalse(set2.hashCode() == set3.hashCode());
820:•                assertFalse(set3.hashCode() == set1.hashCode());
821:•                assertFalse(set3.hashCode() == set2.hashCode());
822:
823:                 set1.remove(null);
824:                 set2.remove(null);
825:•                assertTrue(set1.hashCode() == set2.hashCode());
826:•                assertFalse(set1.hashCode() == set3.hashCode());
827:•                assertTrue(set2.hashCode() == set1.hashCode());
828:•                assertFalse(set2.hashCode() == set3.hashCode());
829:•                assertFalse(set3.hashCode() == set1.hashCode());
830:•                assertFalse(set3.hashCode() == set2.hashCode());
831:
832:                 set1.clear();
833:                 set2.clear();
834:•                assertTrue(set1.hashCode() == set2.hashCode());
835:•                assertFalse(set1.hashCode() == set3.hashCode());
836:•                assertTrue(set2.hashCode() == set1.hashCode());
837:•                assertFalse(set2.hashCode() == set3.hashCode());
838:•                assertFalse(set3.hashCode() == set1.hashCode());
839:•                assertFalse(set3.hashCode() == set2.hashCode());
840:
841:                 set1.addAll(objects1);
842:                 set2.addAll(objects1);
843:•                assertTrue(set1.hashCode() == set2.hashCode());
844:•                assertTrue(set1.hashCode() == set3.hashCode());
845:•                assertTrue(set2.hashCode() == set1.hashCode());
846:•                assertTrue(set2.hashCode() == set3.hashCode());
847:•                assertTrue(set3.hashCode() == set1.hashCode());
848:•                assertTrue(set3.hashCode() == set2.hashCode());
849:
850:                 set1.clear();
851:                 set2.clear();
852:                 set3.clear();
853:•                assertTrue(set1.hashCode() == set2.hashCode());
854:•                assertTrue(set1.hashCode() == set3.hashCode());
855:•                assertTrue(set2.hashCode() == set1.hashCode());
856:•                assertTrue(set2.hashCode() == set3.hashCode());
857:•                assertTrue(set3.hashCode() == set1.hashCode());
858:•                assertTrue(set3.hashCode() == set2.hashCode());
859:         }
860:
861:         /**
862:          * Tests the copy constructor of our set.
863:          */
864:         @Test
865:         public void testInstantiationCopy() {
866:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
867:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
868:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
869:                 Collection<Object> duplicatesList = new ArrayList<Object>();
870:•                for (int i = 0; i < 40; i++) {
871:                         int dupe = i / 2;
872:                         duplicatesList.add(Integer.valueOf(dupe));
873:                         duplicatesList.add(String.valueOf(dupe));
874:                 }
875:                 duplicatesList.add(null);
876:                 duplicatesList.add(null);
877:
878:                 Set<Object> set = createSet(listInt10);
879:                 assertFalse(set.isEmpty());
880:                 assertSame(listInt10.size(), set.size());
881:                 assertSame(getNextPowerOfTwo(listInt10.size()), getInternalCapacity(set));
882:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
883:                 assertTrue(set.containsAll(listInt10));
884:•                for (Integer integer : listInt10) {
885:                         assertTrue(set.contains(integer));
886:                 }
887:
888:                 set = createSet(setString20);
889:                 assertFalse(set.isEmpty());
890:                 assertSame(setString20.size(), set.size());
891:                 assertSame(getNextPowerOfTwo(setString20.size()), getInternalCapacity(set));
892:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
893:                 assertTrue(set.containsAll(setString20));
894:•                for (String string : setString20) {
895:                         assertTrue(set.contains(string));
896:                 }
897:
898:                 set = createSet(dequeString40);
899:                 assertFalse(set.isEmpty());
900:                 assertSame(dequeString40.size(), set.size());
901:                 assertSame(getNextPowerOfTwo(dequeString40.size()), getInternalCapacity(set));
902:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
903:                 assertTrue(set.containsAll(dequeString40));
904:•                for (String string : dequeString40) {
905:                         assertTrue(set.contains(string));
906:                 }
907:
908:                 set = createSet(duplicatesList);
909:                 final int expectedSize = duplicatesList.size() / 2;
910:                 assertFalse(set.isEmpty());
911:                 assertSame(expectedSize, set.size());
912:                 assertEquals(getNextPowerOfTwo(duplicatesList.size()), getInternalCapacity(set));
913:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
914:                 assertTrue(set.containsAll(duplicatesList));
915:•                for (Object o : duplicatesList) {
916:                         assertTrue(set.contains(o));
917:                 }
918:                 assertTrue(set.contains(null));
919:         }
920:
921:         /**
922:          * Tests the empty set constructor.
923:          */
924:         @Test
925:         public void testInstantiationEmpty() {
926:                 Set<Object> set = createSet();
927:                 assertTrue(set.isEmpty());
928:                 assertSame(0, set.size());
929:                 assertSame(16, getInternalCapacity(set));
930:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
931:         }
932:
933:         /**
934:          * Tests the {@link CompactHashSet#CompactHashSet(int, float)} constructor of our set.
935:          */
936:         @Test
937:         public void testInstantiationLoadFactor() {
938:                 int[] validCapacities = new int[] {10, 0, (1 << 10) - 1, 1 << 31, -10 };
939:                 float[] validLoadFactors = new float[] {0.000001f, 0.5f, 0.75f, 1f, Float.MIN_VALUE };
940:                 int[] invalidCapacities = new int[] {Integer.MAX_VALUE, (1 << 30) + 1 };
941:                 float[] invalidLoadFactors = new float[] {0f, -1f, 1.000001f, 5f, Float.NEGATIVE_INFINITY,
942:                                 Float.POSITIVE_INFINITY, Float.NaN, Float.MAX_VALUE };
943:
944:•                for (int capacity : validCapacities) {
945:•                        for (float loadFactor : validLoadFactors) {
946:                                 Set<Object> set = createSet(capacity, loadFactor);
947:                                 assertTrue(set.isEmpty());
948:                                 assertSame(0, set.size());
949:                                 assertEquals(Math.max(4, getNextPowerOfTwo(capacity)), getInternalCapacity(set));
950:                                 assertEquals(loadFactor, getInternalLoadFactor(set), 0.001);
951:                         }
952:•                        for (float loadFactor : invalidLoadFactors) {
953:                                 try {
954:                                         createSet(capacity, loadFactor);
955:•                                        if (loadFactor <= 0f || loadFactor > 1f || Float.isNaN(loadFactor)) {
956:                                                 fail("Expected IllegalArgumentException hasn't been thrown"); //$NON-NLS-1$
957:                                         } else {
958:                                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
959:                                         }
960:                                 } catch (IndexOutOfBoundsException e) {
961:                                         // Expected
962:                                 } catch (IllegalArgumentException e) {
963:                                         // Expected
964:                                 }
965:                         }
966:                 }
967:
968:•                for (int capacity : invalidCapacities) {
969:•                        for (float loadFactor : validLoadFactors) {
970:                                 try {
971:                                         createSet(capacity, loadFactor);
972:                                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
973:                                 } catch (IndexOutOfBoundsException e) {
974:                                         // Expected
975:                                 }
976:                         }
977:•                        for (float loadFactor : invalidLoadFactors) {
978:                                 try {
979:                                         createSet(capacity, loadFactor);
980:•                                        if (loadFactor <= 0f || loadFactor > 1f || Float.isNaN(loadFactor)) {
981:                                                 fail("Expected IllegalArgumentException hasn't been thrown"); //$NON-NLS-1$
982:                                         } else {
983:                                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
984:                                         }
985:                                 } catch (IndexOutOfBoundsException e) {
986:                                         // Expected
987:                                 } catch (IllegalArgumentException e) {
988:                                         // Expected
989:                                 }
990:                         }
991:                 }
992:         }
993:
994:         /**
995:          * Tests the {@link CompactHashSet#CompactHashSet(int)} constructor of our set.
996:          */
997:         @Test
998:         public void testInstantiationSize() {
999:                 Set<Object> set = createSet(10);
1000:                 assertTrue(set.isEmpty());
1001:                 assertSame(0, set.size());
1002:                 assertSame(16, getInternalCapacity(set));
1003:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
1004:
1005:                 set = createSet(0);
1006:                 assertTrue(set.isEmpty());
1007:                 assertSame(0, set.size());
1008:                 assertSame(4, getInternalCapacity(set));
1009:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
1010:
1011:                 set = createSet((1 << 10) - 1);
1012:                 assertTrue(set.isEmpty());
1013:                 assertSame(0, set.size());
1014:                 assertEquals(1 << 10, getInternalCapacity(set));
1015:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
1016:
1017:                 set = createSet(1 << 31);
1018:                 assertTrue(set.isEmpty());
1019:                 assertSame(0, set.size());
1020:                 assertSame(4, getInternalCapacity(set));
1021:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
1022:
1023:                 set = createSet(-10);
1024:                 assertTrue(set.isEmpty());
1025:                 assertSame(0, set.size());
1026:                 assertSame(4, getInternalCapacity(set));
1027:                 assertEquals(0.75f, getInternalLoadFactor(set), 0.001);
1028:
1029:                 try {
1030:                         set = createSet(Integer.MAX_VALUE);
1031:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1032:                 } catch (IndexOutOfBoundsException e) {
1033:                         // Expected
1034:                 }
1035:                 try {
1036:                         /*
1037:                          * The last possible size for our internal array is 2^30, trying to hold that much elements will
1038:                          * yield a size of -1, which is invalid.
1039:                          */
1040:                         set = createSet((1 << 30) + 1);
1041:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1042:                 } catch (IndexOutOfBoundsException e) {
1043:                         // Expected
1044:                 }
1045:         }
1046:
1047:         /**
1048:          * Tests the behavior of {@link CompactHashSet#isEmpty()} with random elements.
1049:          */
1050:         @Test
1051:         public void testIsEmpty() {
1052:                 Set<Object> set = createSet();
1053:
1054:                 assertTrue(set.isEmpty());
1055:
1056:                 set.add(null);
1057:                 assertFalse(set.isEmpty());
1058:
1059:                 Collection<String> elements = new ArrayList<String>();
1060:•                for (int i = 0; i < 100; i++) {
1061:                         String rand = getRandomString();
1062:                         elements.add(rand);
1063:                         set.add(rand);
1064:                         assertFalse(set.isEmpty());
1065:                 }
1066:•                for (String rand : elements) {
1067:                         set.remove(rand);
1068:                         assertFalse(set.isEmpty());
1069:                 }
1070:
1071:                 set.remove(null);
1072:                 assertTrue(set.isEmpty());
1073:
1074:•                for (int i = 0; i < 100; i++) {
1075:                         set.add(getRandomString());
1076:                         assertFalse(set.isEmpty());
1077:                 }
1078:
1079:                 set.clear();
1080:                 assertTrue(set.isEmpty());
1081:         }
1082:
1083:         /**
1084:          * Tests the behavior of {@link CompactHashSet#iterator()} with random elements.
1085:          */
1086:         @Test
1087:         public void testIterator() {
1088:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
1089:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
1090:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1091:
1092:                 Set<Object> set = createSet();
1093:
1094:                 Iterator<Object> emptyIterator = set.iterator();
1095:                 assertFalse(emptyIterator.hasNext());
1096:                 try {
1097:                         emptyIterator.next();
1098:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1099:                 } catch (NoSuchElementException e) {
1100:                         // expected
1101:                 }
1102:                 try {
1103:                         emptyIterator.remove();
1104:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1105:                 } catch (IllegalStateException e) {
1106:                         // expected
1107:                 }
1108:
1109:                 Iterator<Object> concurrentIterator = set.iterator();
1110:                 set.add(null);
1111:                 try {
1112:                         concurrentIterator.next();
1113:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1114:                 } catch (ConcurrentModificationException e) {
1115:                         // expected
1116:                 }
1117:                 try {
1118:                         concurrentIterator.remove();
1119:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1120:                 } catch (IllegalStateException e) {
1121:                         // expected
1122:                 }
1123:                 set.clear();
1124:
1125:                 set.add(null);
1126:                 concurrentIterator = set.iterator();
1127:                 assertNull(concurrentIterator.next());
1128:                 set.add(new Object());
1129:                 try {
1130:                         concurrentIterator.remove();
1131:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1132:                 } catch (ConcurrentModificationException e) {
1133:                         // expected
1134:                 }
1135:                 set.clear();
1136:
1137:                 set.addAll(listInt10);
1138:                 set.addAll(setString20);
1139:                 set.addAll(dequeString40);
1140:
1141:                 Iterator<Object> containedValues = set.iterator();
1142:•                while (containedValues.hasNext()) {
1143:                         Object next = containedValues.next();
1144:•                        assertTrue(listInt10.contains(next) || setString20.contains(next) || dequeString40.contains(next));
1145:                 }
1146:                 assertFalse(containedValues.hasNext());
1147:
1148:•                for (Integer val : listInt10) {
1149:                         set.remove(val);
1150:                 }
1151:                 set.addAll(listInt10);
1152:
1153:                 containedValues = set.iterator();
1154:•                while (containedValues.hasNext()) {
1155:                         Object next = containedValues.next();
1156:•                        assertTrue(listInt10.contains(next) || setString20.contains(next) || dequeString40.contains(next));
1157:                 }
1158:                 assertFalse(containedValues.hasNext());
1159:                 try {
1160:                         containedValues.next();
1161:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1162:                 } catch (NoSuchElementException e) {
1163:                         // expected
1164:                 }
1165:
1166:                 set.clear();
1167:                 assertFalse(set.iterator().hasNext());
1168:                 containedValues = set.iterator();
1169:                 try {
1170:                         containedValues.next();
1171:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1172:                 } catch (NoSuchElementException e) {
1173:                         // expected
1174:                 }
1175:         }
1176:
1177:         /**
1178:          * Tests the removal of elements of the Set through the iterator.remove method.
1179:          */
1180:         @Test
1181:         public void testIteratorRemove() {
1182:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.<Integer> emptySet());
1183:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.<String> emptySet());
1184:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1185:
1186:                 Set<Object> set = createSet();
1187:
1188:                 Iterator<Object> emptyIterator = set.iterator();
1189:                 assertFalse(emptyIterator.hasNext());
1190:                 try {
1191:                         emptyIterator.next();
1192:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1193:                 } catch (NoSuchElementException e) {
1194:                         // expected
1195:                 }
1196:                 try {
1197:                         emptyIterator.remove();
1198:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1199:                 } catch (IllegalStateException e) {
1200:                         // expected
1201:                 }
1202:
1203:                 Iterator<Object> concurrentIterator = set.iterator();
1204:                 set.add(null);
1205:                 try {
1206:                         concurrentIterator.next();
1207:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1208:                 } catch (ConcurrentModificationException e) {
1209:                         // expected
1210:                 }
1211:                 try {
1212:                         concurrentIterator.remove();
1213:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1214:                 } catch (IllegalStateException e) {
1215:                         // expected
1216:                 }
1217:                 set.clear();
1218:
1219:                 set.addAll(listInt10);
1220:                 set.addAll(setString20);
1221:                 set.addAll(dequeString40);
1222:
1223:                 Iterator<Object> containedValues = set.iterator();
1224:                 int size = set.size();
1225:•                while (containedValues.hasNext()) {
1226:                         final Object next = containedValues.next();
1227:•                        assertTrue(listInt10.contains(next) || setString20.contains(next) || dequeString40.contains(next));
1228:                         assertSame(size, set.size());
1229:                         containedValues.remove();
1230:                         assertFalse(set.contains(next));
1231:                         assertSame(--size, set.size());
1232:                 }
1233:                 assertFalse(containedValues.hasNext());
1234:                 assertSame(0, set.size());
1235:         }
1236:
1237:         /**
1238:          * This will try and ensure that rehashing works properly both when we have a high count of "deleted"
1239:          * entries and when no entry has been deleted.
1240:          */
1241:         @Test
1242:         public void testRehashing() {
1243:                 /*
1244:                  * We're using for this test values which we know the hashCode so as to prevent all collisions. We
1245:                  * need to test the rehashing when adding a new value into a set which only contains deleted
1246:                  * elements... rehashing won't happen if the value's hash collides with a deleted element.
1247:                  */
1248:                 Set<Object> set1 = createSet();
1249:                 Set<Object> set2 = createSet();
1250:
1251:                 List<Integer> integers = new ArrayList<Integer>();
1252:•                for (int i = 1; i < 14; i++) {
1253:                         integers.add(Integer.valueOf(i));
1254:                 }
1255:
1256:                 assertSame(0, set1.size());
1257:                 assertSame(16, getInternalCapacity(set1));
1258:                 assertSame(0, set2.size());
1259:                 assertSame(16, getInternalCapacity(set2));
1260:
1261:                 /*
1262:                  * With the default capacity and load factor, the rehashing takes place at 13 insertions. For now, add
1263:                  * 12 elements in each set.
1264:                  */
1265:•                for (int i = 0; i < 12; i++) {
1266:                         set1.add(integers.get(i));
1267:                         set2.add(integers.get(i));
1268:                 }
1269:
1270:                 // Make sure that the rehashing did not take place
1271:                 assertSame(12, set1.size());
1272:                 assertSame(16, getInternalCapacity(set1));
1273:                 assertSame(12, set2.size());
1274:                 assertSame(16, getInternalCapacity(set2));
1275:
1276:                 // Delete 11 elements from set 1
1277:•                for (int i = 0; i < 11; i++) {
1278:                         set1.remove(integers.get(i));
1279:                 }
1280:
1281:                 assertSame(1, set1.size());
1282:                 assertSame(16, getInternalCapacity(set1));
1283:                 assertSame(12, set2.size());
1284:                 assertSame(16, getInternalCapacity(set2));
1285:
1286:                 // Now, add a 13th element to both sets
1287:                 set1.add(integers.get(12));
1288:                 set2.add(integers.get(12));
1289:
1290:                 /*
1291:                  * And ensure that the first set's capacity hasn't been increased while the second set's has been
1292:                  * doubled.
1293:                  */
1294:                 assertSame(2, set1.size());
1295:                 assertSame(16, getInternalCapacity(set1));
1296:                 assertSame(13, set2.size());
1297:                 assertSame(32, getInternalCapacity(set2));
1298:         }
1299:
1300:         /**
1301:          * Tests the behavior of {@link CompactHashSet#remove(Object)} with random elements.
1302:          */
1303:         @Test
1304:         public void testRemove() {
1305:                 Set<Object> set = createSet();
1306:                 List<String> objects = randomStringListNotIn(20, Collections.<String> emptySet());
1307:
1308:                 assertFalse(set.containsAll(objects));
1309:
1310:•                for (Object o : objects) {
1311:                         boolean removed = set.remove(o);
1312:                         assertFalse(removed);
1313:                         assertFalse(set.contains(o));
1314:                 }
1315:
1316:•                for (Object o : objects) {
1317:                         set.add(o);
1318:                 }
1319:                 assertTrue(set.containsAll(objects));
1320:
1321:•                for (Object o : objects) {
1322:                         assertTrue(set.contains(o));
1323:                         boolean removed = set.remove(o);
1324:                         assertTrue(removed);
1325:                         assertFalse(set.contains(o));
1326:                 }
1327:
1328:                 assertFalse(set.containsAll(objects));
1329:
1330:•                for (Object o : objects) {
1331:                         boolean removed = set.remove(o);
1332:                         assertFalse(removed);
1333:                         assertFalse(set.contains(o));
1334:                 }
1335:         }
1336:
1337:         /**
1338:          * Creates an empty set on which to execute these tests.
1339:          *
1340:          * @return The set to execute these tests on.
1341:          */
1342:         protected Set<Object> createSet() {
1343:                 return new CompactHashSet<Object>();
1344:         }
1345:
1346:         /**
1347:          * Creates a set containing all of the elements from the given collection.
1348:          *
1349:          * @param collection
1350:          * The collection which elements are to be added to the new set.
1351:          * @return The set to execute these tests on.
1352:          */
1353:         protected Set<Object> createSet(Collection<? extends Object> collection) {
1354:                 return new CompactHashSet<Object>(collection);
1355:         }
1356:
1357:         /**
1358:          * Creates a set using the single int constructor.
1359:          *
1360:          * @param elementCount
1361:          * Number of elements this set is meant to contain.
1362:          * @return The set to execute these tests on.
1363:          */
1364:         protected Set<Object> createSet(int elementCount) {
1365:                 return new CompactHashSet<Object>(elementCount);
1366:         }
1367:
1368:         /**
1369:          * Creates a new set given its initial capacity and load factor.
1370:          *
1371:          * @param elementCount
1372:          * Number of elements this set is meant to contain.
1373:          * @param loadFactor
1374:          * Load factor of the new set.
1375:          * @return The set to execute these tests on.
1376:          */
1377:         protected Set<Object> createSet(int elementCount, float loadFactor) {
1378:                 return new CompactHashSet<Object>(elementCount, loadFactor);
1379:         }
1380:
1381:         /**
1382:          * Returns a list containing <code>size</code> random Integers.
1383:          *
1384:          * @param size
1385:          * Size of the list to create.
1386:          * @param excluded
1387:          * Values that cannot be in our returned list.
1388:          * @return A list containing <code>size</code> random Integers.
1389:          */
1390:         protected List<Integer> randomIntegerListNotIn(int size, Collection<?> excluded) {
1391:                 List<Integer> list = new ArrayList<Integer>(size);
1392:•                for (int i = 0; i < size; i++) {
1393:                         Integer integer = getRandomInteger();
1394:•                        while (list.contains(integer) || excluded.contains(integer)) {
1395:                                 integer = getRandomInteger();
1396:                         }
1397:                         list.add(integer);
1398:                 }
1399:                 return list;
1400:         }
1401:
1402:         /**
1403:          * Returns a list containing <code>size</code> random Strings.
1404:          *
1405:          * @param size
1406:          * Size of the list to create.
1407:          * @param excluded
1408:          * Values that cannot be in our returned list.
1409:          * @return A list containing <code>size</code> random Strings.
1410:          */
1411:         protected List<String> randomStringListNotIn(int size, Collection<?> excluded) {
1412:                 List<String> list = new ArrayList<String>(size);
1413:•                for (int i = 0; i < size; i++) {
1414:                         String string = getRandomString();
1415:•                        while (list.contains(string) || excluded.contains(string)) {
1416:                                 string = getRandomString();
1417:                         }
1418:                         list.add(string);
1419:                 }
1420:                 return list;
1421:         }
1422:
1423:         /**
1424:          * Returns a deque containing <code>size</code> random Strings.
1425:          *
1426:          * @param size
1427:          * Size of the deque to create.
1428:          * @param excluded
1429:          * Values that cannot be in our returned list.
1430:          * @return A deque containing <code>size</code> random Strings.
1431:          */
1432:         protected Deque<String> randomStringDequeNotIn(int size, Collection<?> excluded) {
1433:                 Deque<String> deque = new CircularArrayDeque<String>(size);
1434:•                for (int i = 0; i < size; i++) {
1435:                         String s = getRandomString();
1436:•                        while (deque.contains(s) || excluded.contains(s)) {
1437:                                 s = getRandomString();
1438:                         }
1439:                         deque.add(s);
1440:                 }
1441:                 return deque;
1442:         }
1443:
1444:         /**
1445:          * Returns a set containing <code>size</code> random Strings.
1446:          *
1447:          * @param size
1448:          * Size of the set to create.
1449:          * @param excluded
1450:          * Values that cannot be in our returned list.
1451:          * @return A set containing <code>size</code> random Strings.
1452:          */
1453:         protected Set<String> randomStringSetNotIn(int size, Collection<?> excluded) {
1454:                 Set<String> set = new HashSet<String>(size);
1455:•                for (int i = 0; i < size; i++) {
1456:                         String s = getRandomString();
1457:•                        while (set.contains(s) || excluded.contains(s)) {
1458:                                 s = getRandomString();
1459:                         }
1460:                         set.add(s);
1461:                 }
1462:                 return set;
1463:         }
1464:
1465:         /**
1466:          * Makes the "data" field of the given set public in order to retrieve it.
1467:          *
1468:          * @param set
1469:          * The set we need the internal array of.
1470:          * @return The internal array of the given set.
1471:          */
1472:         private Object[] getInternalArray(Set<?> set) {
1473:•                if (!(set instanceof CompactHashSet<?>)) {
1474:                         fail("Unexpected set implementation"); //$NON-NLS-1$
1475:                 }
1476:                 Field dataField = null;
1477:•                for (Field field : CompactHashSet.class.getDeclaredFields()) {
1478:•                        if (field.getName().equals("data")) { //$NON-NLS-1$
1479:                                 dataField = field;
1480:                                 break;
1481:                         }
1482:                 }
1483:                 assertNotNull(dataField);
1484:•                assert dataField != null;
1485:                 dataField.setAccessible(true);
1486:                 Object[] data = null;
1487:                 try {
1488:                         data = (Object[])dataField.get(set);
1489:                 } catch (IllegalArgumentException e) {
1490:                         // carry on
1491:                 } catch (IllegalAccessException e) {
1492:                         // carry on
1493:                 }
1494:•                if (data == null) {
1495:                         fail("could not retrieve internal data array of " + set); //$NON-NLS-1$
1496:                 }
1497:                 return data;
1498:         }
1499:
1500:         /**
1501:          * Makes the "data" field of the given set public in order to retrieve its current size.
1502:          *
1503:          * @param set
1504:          * The set we need the capacity of.
1505:          * @return The capacity of the given set.
1506:          */
1507:         private int getInternalCapacity(Set<?> set) {
1508:                 Object[] data = getInternalArray(set);
1509:                 return data.length;
1510:         }
1511:
1512:         /**
1513:          * Makes the "loadFactor" field of the given set public in order to retrieve it.
1514:          *
1515:          * @param set
1516:          * The set we need the internal loadFactor of.
1517:          * @return The loadFactor of the given set.
1518:          */
1519:         private float getInternalLoadFactor(Set<?> set) {
1520:•                if (!(set instanceof CompactHashSet<?>)) {
1521:                         fail("Unexpected set implementation"); //$NON-NLS-1$
1522:                 }
1523:                 Field loadFactorField = null;
1524:•                for (Field field : CompactHashSet.class.getDeclaredFields()) {
1525:•                        if (field.getName().equals("loadFactor")) { //$NON-NLS-1$
1526:                                 loadFactorField = field;
1527:                                 break;
1528:                         }
1529:                 }
1530:                 assertNotNull(loadFactorField);
1531:•                assert loadFactorField != null;
1532:                 loadFactorField.setAccessible(true);
1533:                 Float loadFactor = null;
1534:                 try {
1535:                         loadFactor = (Float)loadFactorField.get(set);
1536:                 } catch (IllegalArgumentException e) {
1537:                         // carry on
1538:                 } catch (IllegalAccessException e) {
1539:                         // carry on
1540:                 }
1541:•                if (loadFactor == null) {
1542:                         fail("could not retrieve load factor of " + set); //$NON-NLS-1$
1543:                 }
1544:•                assert loadFactor != null;
1545:                 return loadFactor.floatValue();
1546:         }
1547:
1548:         /**
1549:          * Get the closest power of two greater than <code>number</code>.
1550:          *
1551:          * @param number
1552:          * Number for which we seek the closest power of two.
1553:          * @return The closest power of two greater than <code>number</code>.
1554:          */
1555:         private int getNextPowerOfTwo(int number) {
1556:                 int powerOfTwo = number--;
1557:                 powerOfTwo |= powerOfTwo >> 1;
1558:                 powerOfTwo |= powerOfTwo >> 2;
1559:                 powerOfTwo |= powerOfTwo >> 4;
1560:                 powerOfTwo |= powerOfTwo >> 8;
1561:                 powerOfTwo |= powerOfTwo >> 16;
1562:                 powerOfTwo++;
1563:                 return powerOfTwo;
1564:         }
1565:
1566:         /**
1567:          * Returns a random Integer between 0 and 100000.
1568:          *
1569:          * @return A random Integer between 0 and 100000.
1570:          */
1571:         private Integer getRandomInteger() {
1572:                 return Integer.valueOf(Double.valueOf(Math.random() * 100000d).intValue());
1573:         }
1574:
1575:         /**
1576:          * Returns a random String representing an integer between 0 and 100000.
1577:          *
1578:          * @return A random String representing an integer between 0 and 100000.
1579:          */
1580:         private String getRandomString() {
1581:                 return getRandomInteger().toString();
1582:         }
1583: }