Package: CircularArrayDequeTest

CircularArrayDequeTest

nameinstructionbranchcomplexitylinemethod
CircularArrayDequeTest()
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%
assertEqualContent(Object[], Object[])
M: 35 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
getInternalArray(Deque)
M: 64 C: 0
0%
M: 10 C: 0
0%
M: 6 C: 0
0%
M: 15 C: 0
0%
M: 1 C: 0
0%
getInternalCapacity(Deque)
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%
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%
internalTestAddAllRandomAccessLeftRotate(List)
M: 592 C: 0
0%
M: 36 C: 0
0%
M: 19 C: 0
0%
M: 84 C: 0
0%
M: 1 C: 0
0%
internalTestAddAllRandomAccessRightRotate(List)
M: 597 C: 0
0%
M: 34 C: 0
0%
M: 18 C: 0
0%
M: 87 C: 0
0%
M: 1 C: 0
0%
internalTestAddRandomAccessLeftRotate(Object)
M: 378 C: 0
0%
M: 28 C: 0
0%
M: 15 C: 0
0%
M: 59 C: 0
0%
M: 1 C: 0
0%
internalTestAddRandomAccessRightRotate(Object)
M: 398 C: 0
0%
M: 26 C: 0
0%
M: 14 C: 0
0%
M: 65 C: 0
0%
M: 1 C: 0
0%
internalTestRemoveAllBothRotate(List)
M: 859 C: 0
0%
M: 52 C: 0
0%
M: 27 C: 0
0%
M: 133 C: 0
0%
M: 1 C: 0
0%
internalTestRemoveAllLeftRotate(List)
M: 504 C: 0
0%
M: 34 C: 0
0%
M: 18 C: 0
0%
M: 80 C: 0
0%
M: 1 C: 0
0%
internalTestRemoveAllRightRotate(List)
M: 514 C: 0
0%
M: 36 C: 0
0%
M: 19 C: 0
0%
M: 83 C: 0
0%
M: 1 C: 0
0%
internalTestRemoveLeftRotate(Object)
M: 337 C: 0
0%
M: 24 C: 0
0%
M: 13 C: 0
0%
M: 54 C: 0
0%
M: 1 C: 0
0%
internalTestRemoveRightRotate(Object)
M: 355 C: 0
0%
M: 26 C: 0
0%
M: 14 C: 0
0%
M: 57 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%
readDeque(byte[])
M: 33 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 12 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: 280 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 70 C: 0
0%
M: 1 C: 0
0%
testAddAll()
M: 278 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 51 C: 0
0%
M: 1 C: 0
0%
testAddAllRandomAccess()
M: 300 C: 0
0%
M: 34 C: 0
0%
M: 18 C: 0
0%
M: 65 C: 0
0%
M: 1 C: 0
0%
testAddAllRandomAccessLeftRotate()
M: 87 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
testAddAllRandomAccessRightRotate()
M: 87 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
testAddAllRandomOutOfBounds()
M: 109 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 14 C: 0
0%
M: 1 C: 0
0%
testAddFirst()
M: 255 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testAddLast()
M: 255 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testAddRandomAccessLeftRotate()
M: 68 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 5 C: 0
0%
M: 1 C: 0
0%
testAddRandomAccessOutOfBounds()
M: 90 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 11 C: 0
0%
M: 1 C: 0
0%
testAddRandomAccessRightRotate()
M: 68 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 5 C: 0
0%
M: 1 C: 0
0%
testClear()
M: 120 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 27 C: 0
0%
M: 1 C: 0
0%
testContains()
M: 86 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 19 C: 0
0%
M: 1 C: 0
0%
testContainsAll()
M: 109 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 24 C: 0
0%
M: 1 C: 0
0%
testElement()
M: 117 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 31 C: 0
0%
M: 1 C: 0
0%
testEquals()
M: 237 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 59 C: 0
0%
M: 1 C: 0
0%
testGet()
M: 91 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 22 C: 0
0%
M: 1 C: 0
0%
testGetFirst()
M: 117 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 31 C: 0
0%
M: 1 C: 0
0%
testGetLast()
M: 122 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 31 C: 0
0%
M: 1 C: 0
0%
testHashCode()
M: 418 C: 0
0%
M: 52 C: 0
0%
M: 27 C: 0
0%
M: 64 C: 0
0%
M: 1 C: 0
0%
testIndexOf()
M: 405 C: 0
0%
M: 26 C: 0
0%
M: 14 C: 0
0%
M: 54 C: 0
0%
M: 1 C: 0
0%
testInstantiationCopy()
M: 103 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 19 C: 0
0%
M: 1 C: 0
0%
testInstantiationEmpty()
M: 80 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 17 C: 0
0%
M: 1 C: 0
0%
testInstantiationError()
M: 15 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 7 C: 0
0%
M: 1 C: 0
0%
testIsEmpty()
M: 89 C: 0
0%
M: 10 C: 0
0%
M: 6 C: 0
0%
M: 24 C: 0
0%
M: 1 C: 0
0%
testIsSerializable()
M: 195 C: 0
0%
M: 14 C: 0
0%
M: 8 C: 0
0%
M: 48 C: 0
0%
M: 1 C: 0
0%
testIterator()
M: 229 C: 0
0%
M: 14 C: 0
0%
M: 8 C: 0
0%
M: 71 C: 0
0%
M: 1 C: 0
0%
testIteratorRemove()
M: 149 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 50 C: 0
0%
M: 1 C: 0
0%
testLastIndexOf()
M: 405 C: 0
0%
M: 26 C: 0
0%
M: 14 C: 0
0%
M: 54 C: 0
0%
M: 1 C: 0
0%
testListIterator()
M: 726 C: 0
0%
M: 26 C: 0
0%
M: 14 C: 0
0%
M: 199 C: 0
0%
M: 1 C: 0
0%
testListIteratorStartAt()
M: 226 C: 0
0%
M: 10 C: 0
0%
M: 6 C: 0
0%
M: 38 C: 0
0%
M: 1 C: 0
0%
testOffer()
M: 264 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testOfferAll()
M: 260 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 45 C: 0
0%
M: 1 C: 0
0%
testOfferFirst()
M: 255 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testOfferLast()
M: 255 C: 0
0%
M: 4 C: 0
0%
M: 3 C: 0
0%
M: 62 C: 0
0%
M: 1 C: 0
0%
testParameterizedToArray()
M: 247 C: 0
0%
M: 14 C: 0
0%
M: 8 C: 0
0%
M: 45 C: 0
0%
M: 1 C: 0
0%
testPeek()
M: 109 C: 0
0%
M: 10 C: 0
0%
M: 6 C: 0
0%
M: 26 C: 0
0%
M: 1 C: 0
0%
testPeekFirst()
M: 117 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 31 C: 0
0%
M: 1 C: 0
0%
testPeekLast()
M: 122 C: 0
0%
M: 12 C: 0
0%
M: 7 C: 0
0%
M: 31 C: 0
0%
M: 1 C: 0
0%
testPoll()
M: 106 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 22 C: 0
0%
M: 1 C: 0
0%
testPop()
M: 118 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 28 C: 0
0%
M: 1 C: 0
0%
testRemove()
M: 100 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 21 C: 0
0%
M: 1 C: 0
0%
testRemoveAll()
M: 322 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 70 C: 0
0%
M: 1 C: 0
0%
testRemoveAllBothRotate()
M: 87 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
testRemoveAllLeftRotate()
M: 87 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
testRemoveAllRightRotate()
M: 87 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 8 C: 0
0%
M: 1 C: 0
0%
testRemoveFirst()
M: 118 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 28 C: 0
0%
M: 1 C: 0
0%
testRemoveLast()
M: 118 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 28 C: 0
0%
M: 1 C: 0
0%
testRemoveLeftRotate()
M: 68 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 5 C: 0
0%
M: 1 C: 0
0%
testRemoveQueue()
M: 118 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 28 C: 0
0%
M: 1 C: 0
0%
testRemoveRightRotate()
M: 68 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 5 C: 0
0%
M: 1 C: 0
0%
testRetainAll()
M: 369 C: 0
0%
M: 24 C: 0
0%
M: 13 C: 0
0%
M: 71 C: 0
0%
M: 1 C: 0
0%
testSet()
M: 314 C: 0
0%
M: 8 C: 0
0%
M: 5 C: 0
0%
M: 52 C: 0
0%
M: 1 C: 0
0%
testSize()
M: 70 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 15 C: 0
0%
M: 1 C: 0
0%
testSubList()
M: 128 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 30 C: 0
0%
M: 1 C: 0
0%
testToArray()
M: 121 C: 0
0%
M: 6 C: 0
0%
M: 4 C: 0
0%
M: 25 C: 0
0%
M: 1 C: 0
0%
writeDeque(Deque)
M: 23 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 8 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.io.ByteArrayInputStream;
22: import java.io.ByteArrayOutputStream;
23: import java.io.IOException;
24: import java.io.InputStream;
25: import java.io.ObjectInputStream;
26: import java.io.ObjectOutputStream;
27: import java.lang.reflect.Field;
28: import java.util.ArrayList;
29: import java.util.Collection;
30: import java.util.Collections;
31: import java.util.ConcurrentModificationException;
32: import java.util.HashSet;
33: import java.util.Iterator;
34: import java.util.List;
35: import java.util.ListIterator;
36: import java.util.NoSuchElementException;
37: import java.util.Set;
38:
39: import org.eclipse.acceleo.common.utils.CircularArrayDeque;
40: import org.eclipse.acceleo.common.utils.Deque;
41: import org.junit.Test;
42:
43: /**
44: * Tests for the {@link CircularArrayDeque} behavior.
45: *
46: * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
47: */
48: @SuppressWarnings("nls")
49:•public class CircularArrayDequeTest {
50:         /**
51:          * Tests the behavior of {@link CircularArrayDeque#add(Object)} with random elements.
52:          */
53:         @Test
54:         public void testAdd() {
55:                 Integer integer1 = -1;
56:                 Integer integer2 = -2;
57:                 String string1 = "a";
58:                 String string2 = "b";
59:                 Object object1 = new Object();
60:                 Object object2 = new Object();
61:
62:                 Deque<Object> deque = new CircularArrayDeque<Object>();
63:
64:                 boolean modified = deque.add(integer1);
65:                 assertTrue(modified);
66:                 assertSame(1, deque.size());
67:                 assertEquals(integer1, deque.getFirst());
68:                 assertEquals(integer1, deque.getLast());
69:                 assertEquals(integer1, deque.peek());
70:
71:                 modified = deque.add(integer2);
72:                 assertTrue(modified);
73:                 assertSame(2, deque.size());
74:                 assertEquals(integer1, deque.getFirst());
75:                 assertEquals(integer1, deque.peek());
76:                 assertEquals(integer2, deque.getLast());
77:
78:                 modified = deque.add(string1);
79:                 assertTrue(modified);
80:                 assertSame(3, deque.size());
81:                 assertEquals(integer1, deque.getFirst());
82:                 assertEquals(integer1, deque.peek());
83:                 assertEquals(string1, deque.getLast());
84:
85:                 modified = deque.add(string2);
86:                 assertTrue(modified);
87:                 assertSame(4, deque.size());
88:                 assertEquals(integer1, deque.getFirst());
89:                 assertEquals(integer1, deque.peek());
90:                 assertEquals(string2, deque.getLast());
91:
92:                 modified = deque.add(object1);
93:                 assertTrue(modified);
94:                 assertSame(5, deque.size());
95:                 assertEquals(integer1, deque.getFirst());
96:                 assertEquals(integer1, deque.peek());
97:                 assertEquals(object1, deque.getLast());
98:
99:                 modified = deque.add(object2);
100:                 assertTrue(modified);
101:                 assertSame(6, deque.size());
102:                 assertEquals(integer1, deque.getFirst());
103:                 assertEquals(integer1, deque.peek());
104:                 assertEquals(object2, deque.getLast());
105:
106:                 modified = deque.add(null);
107:                 assertTrue(modified);
108:                 assertSame(7, deque.size());
109:                 assertEquals(integer1, deque.getFirst());
110:                 assertEquals(integer1, deque.peek());
111:                 assertSame(null, deque.getLast());
112:
113:                 deque.pop();
114:                 assertSame(6, deque.size());
115:                 assertEquals(integer1, deque.getFirst());
116:                 assertEquals(integer1, deque.peek());
117:                 assertEquals(object2, deque.getLast());
118:
119:                 modified = deque.add(null);
120:                 assertTrue(modified);
121:                 assertSame(7, deque.size());
122:                 assertEquals(integer1, deque.getFirst());
123:                 assertEquals(integer1, deque.peek());
124:                 assertSame(null, deque.getLast());
125:
126:                 // Ensure we go above capacity
127:•                for (int i = 0; i < 100; i++) {
128:                         String rand = getRandomString();
129:•                        while (deque.contains(rand)) {
130:                                 rand = getRandomString();
131:                         }
132:                         deque.add(rand);
133:                         assertSame(7 + i + 1, deque.size());
134:                         assertEquals(integer1, deque.getFirst());
135:                         assertEquals(integer1, deque.peek());
136:                         assertSame(rand, deque.getLast());
137:                 }
138:         }
139:
140:         /**
141:          * Tests the behavior of {@link CircularArrayDeque#addAll(Collection)} with random elements.
142:          */
143:         @Test
144:         public void testAddAll() {
145:                 Collection<Object> emptyCollection = Collections.emptyList();
146:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
147:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
148:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
149:
150:                 Deque<Object> deque = new CircularArrayDeque<Object>();
151:
152:                 boolean modified = deque.addAll(listInt10);
153:                 assertTrue(modified);
154:                 assertEquals(listInt10.size(), deque.size());
155:                 assertTrue(deque.containsAll(listInt10));
156:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
157:
158:                 modified = deque.addAll(emptyCollection);
159:                 assertFalse(modified);
160:                 assertEquals(listInt10.size(), deque.size());
161:                 assertTrue(deque.containsAll(listInt10));
162:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
163:
164:                 modified = deque.addAll(setString20);
165:                 assertTrue(modified);
166:                 assertEquals(listInt10.size() + setString20.size(), deque.size());
167:                 assertTrue(deque.containsAll(listInt10));
168:                 assertTrue(deque.containsAll(setString20));
169:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
170:
171:                 modified = deque.addAll(dequeString40);
172:                 assertTrue(modified);
173:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
174:                 assertTrue(deque.containsAll(listInt10));
175:                 assertTrue(deque.containsAll(setString20));
176:                 assertTrue(deque.containsAll(dequeString40));
177:                 int expectedCapacity = getNextPowerOfTwo(deque.size());
178:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
179:
180:                 for (@SuppressWarnings("unused")
181:•                Integer val : listInt10) {
182:                         deque.removeFirst();
183:                 }
184:                 assertEquals(setString20.size() + dequeString40.size(), deque.size());
185:                 assertFalse(deque.containsAll(listInt10));
186:                 assertTrue(deque.containsAll(setString20));
187:                 assertTrue(deque.containsAll(dequeString40));
188:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
189:
190:                 modified = deque.addAll(listInt10);
191:                 assertTrue(modified);
192:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
193:                 assertTrue(deque.containsAll(listInt10));
194:                 assertTrue(deque.containsAll(setString20));
195:                 assertTrue(deque.containsAll(dequeString40));
196:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
197:
198:                 modified = deque.addAll(emptyCollection);
199:                 assertFalse(modified);
200:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
201:                 assertTrue(deque.containsAll(listInt10));
202:                 assertTrue(deque.containsAll(setString20));
203:                 assertTrue(deque.containsAll(dequeString40));
204:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
205:         }
206:
207:         /**
208:          * Tests the behavior of {@link CircularArrayDeque#addAll(Collection)} with random elements.
209:          */
210:         @Test
211:         public void testAddAllRandomAccess() {
212:                 Collection<Object> emptyCollection = Collections.emptyList();
213:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
214:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
215:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
216:
217:                 /*
218:                  * we'll do this five times : one by adding at the beginning (0), one by adding at the end
219:                  * (deque.size), one by adding in the first half (deque.size / 4), one by adding in the last half
220:                  * (deque.size / 4 * 3) and finally by adding at the middle (deque.size / 2).
221:                  */
222:•                for (int i = 0; i < 5; i++) {
223:                         Deque<Object> deque = new CircularArrayDeque<Object>();
224:
225:                         int insertionIndex = 0;
226:•                        if (i == 1) {
227:                                 insertionIndex = deque.size();
228:•                        } else if (i == 2) {
229:                                 insertionIndex = deque.size() / 4;
230:•                        } else if (i == 3) {
231:                                 insertionIndex = deque.size() / 4 * 3;
232:•                        } else if (i == 4) {
233:                                 insertionIndex = deque.size() / 2;
234:                         }
235:                         boolean modified = deque.addAll(insertionIndex, emptyCollection);
236:                         assertFalse(modified);
237:                         assertEquals(0, deque.size());
238:                         assertEquals(16, getInternalCapacity(deque));
239:
240:                         insertionIndex = 0;
241:•                        if (i == 1) {
242:                                 insertionIndex = deque.size();
243:•                        } else if (i == 2) {
244:                                 insertionIndex = deque.size() / 4;
245:•                        } else if (i == 3) {
246:                                 insertionIndex = deque.size() / 4 * 3;
247:•                        } else if (i == 4) {
248:                                 insertionIndex = deque.size() / 2;
249:                         }
250:                         modified = deque.addAll(insertionIndex, listInt10);
251:                         assertTrue(modified);
252:                         assertEquals(listInt10.size(), deque.size());
253:                         assertTrue(deque.containsAll(listInt10));
254:                         assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
255:
256:                         insertionIndex = 0;
257:•                        if (i == 1) {
258:                                 insertionIndex = deque.size();
259:•                        } else if (i == 2) {
260:                                 insertionIndex = deque.size() / 4;
261:•                        } else if (i == 3) {
262:                                 insertionIndex = deque.size() / 4 * 3;
263:•                        } else if (i == 4) {
264:                                 insertionIndex = deque.size() / 2;
265:                         }
266:                         modified = deque.addAll(insertionIndex, setString20);
267:                         assertTrue(modified);
268:                         assertEquals(listInt10.size() + setString20.size(), deque.size());
269:                         assertTrue(deque.containsAll(listInt10));
270:                         assertTrue(deque.containsAll(setString20));
271:                         assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
272:
273:                         insertionIndex = 0;
274:•                        if (i == 1) {
275:                                 insertionIndex = deque.size();
276:•                        } else if (i == 2) {
277:                                 insertionIndex = deque.size() / 4;
278:•                        } else if (i == 3) {
279:                                 insertionIndex = deque.size() / 4 * 3;
280:•                        } else if (i == 4) {
281:                                 insertionIndex = deque.size() / 2;
282:                         }
283:                         modified = deque.addAll(insertionIndex, dequeString40);
284:                         assertTrue(modified);
285:                         assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
286:                         assertTrue(deque.containsAll(listInt10));
287:                         assertTrue(deque.containsAll(setString20));
288:                         assertTrue(deque.containsAll(dequeString40));
289:                         assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
290:                 }
291:         }
292:
293:         /**
294:          * Tests the behavior of {@link CircularArrayDeque#addAll(int, Collection)} with random elements.
295:          */
296:         @Test
297:         public void testAddAllRandomAccessLeftRotate() {
298:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
299:                                 new Object() };
300:
301:•                for (int i = 0; i < testObjects.length; i++) {
302:                         List<Object> testCollection = new ArrayList<Object>();
303:                         testCollection.add(testObjects[i]);
304:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
305:                         internalTestAddAllRandomAccessLeftRotate(testCollection);
306:                 }
307:         }
308:
309:         /**
310:          * Tests the behavior of {@link CircularArrayDeque#addAll(int, Collection)} with random elements.
311:          */
312:         @Test
313:         public void testAddAllRandomAccessRightRotate() {
314:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
315:                                 new Object() };
316:
317:•                for (int i = 0; i < testObjects.length; i++) {
318:                         List<Object> testCollection = new ArrayList<Object>();
319:                         testCollection.add(testObjects[i]);
320:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
321:                         internalTestAddAllRandomAccessRightRotate(testCollection);
322:                 }
323:         }
324:
325:         /**
326:          * Tests the behavior of {@link CircularArrayDeque#addAll(int, Collection)} with random elements but with
327:          * out of bounds indices.
328:          */
329:         @Test
330:         public void testAddAllRandomOutOfBounds() {
331:                 Deque<Object> deque = new CircularArrayDeque<Object>();
332:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
333:                                 new Object() };
334:
335:•                for (int i = 0; i < testObjects.length; i++) {
336:                         List<Object> testCollection = new ArrayList<Object>();
337:                         testCollection.add(testObjects[i]);
338:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
339:
340:                         try {
341:                                 deque.addAll(-1, testCollection);
342:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
343:                         } catch (IndexOutOfBoundsException e) {
344:                                 // expected
345:                         }
346:                         try {
347:                                 deque.addAll(deque.size() + 1, testCollection);
348:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
349:                         } catch (IndexOutOfBoundsException e) {
350:                                 // expected
351:                         }
352:                 }
353:         }
354:
355:         /**
356:          * Tests the behavior of {@link CircularArrayDeque#addFirst(Object)} with random elements.
357:          */
358:         @Test
359:         public void testAddFirst() {
360:                 Integer integer1 = -1;
361:                 Integer integer2 = -2;
362:                 String string1 = "a";
363:                 String string2 = "b";
364:                 Object object1 = new Object();
365:                 Object object2 = new Object();
366:
367:                 Deque<Object> deque = new CircularArrayDeque<Object>();
368:
369:                 deque.addFirst(integer1);
370:                 assertSame(1, deque.size());
371:                 assertEquals(integer1, deque.getFirst());
372:                 assertEquals(integer1, deque.peek());
373:                 assertEquals(integer1, deque.getLast());
374:
375:                 deque.addFirst(integer2);
376:                 assertSame(2, deque.size());
377:                 assertEquals(integer2, deque.getFirst());
378:                 assertEquals(integer2, deque.peek());
379:                 assertEquals(integer1, deque.getLast());
380:
381:                 deque.addFirst(string1);
382:                 assertSame(3, deque.size());
383:                 assertEquals(string1, deque.getFirst());
384:                 assertEquals(string1, deque.peek());
385:                 assertEquals(integer1, deque.getLast());
386:
387:                 deque.addFirst(string2);
388:                 assertSame(4, deque.size());
389:                 assertEquals(string2, deque.getFirst());
390:                 assertEquals(string2, deque.peek());
391:                 assertEquals(integer1, deque.getLast());
392:
393:                 deque.addFirst(object1);
394:                 assertSame(5, deque.size());
395:                 assertEquals(object1, deque.getFirst());
396:                 assertEquals(object1, deque.peek());
397:                 assertEquals(integer1, deque.getLast());
398:
399:                 deque.addFirst(object2);
400:                 assertSame(6, deque.size());
401:                 assertEquals(object2, deque.getFirst());
402:                 assertEquals(object2, deque.peek());
403:                 assertEquals(integer1, deque.getLast());
404:
405:                 deque.addFirst(null);
406:                 assertSame(7, deque.size());
407:                 assertSame(null, deque.getFirst());
408:                 assertSame(null, deque.peek());
409:                 assertEquals(integer1, deque.getLast());
410:
411:                 deque.removeFirst();
412:                 assertSame(6, deque.size());
413:                 assertEquals(object2, deque.getFirst());
414:                 assertEquals(object2, deque.peek());
415:                 assertEquals(integer1, deque.getLast());
416:
417:                 deque.addFirst(null);
418:                 assertSame(7, deque.size());
419:                 assertSame(null, deque.getFirst());
420:                 assertSame(null, deque.peek());
421:                 assertEquals(integer1, deque.getLast());
422:
423:                 // Ensure we go above capacity
424:•                for (int i = 0; i < 100; i++) {
425:                         String rand = getRandomString();
426:•                        while (deque.contains(rand)) {
427:                                 rand = getRandomString();
428:                         }
429:                         deque.addFirst(rand);
430:                         assertSame(7 + i + 1, deque.size());
431:                         assertEquals(rand, deque.getFirst());
432:                         assertEquals(rand, deque.peek());
433:                         assertSame(integer1, deque.getLast());
434:                 }
435:         }
436:
437:         /**
438:          * Tests the behavior of {@link CircularArrayDeque#addLast(Object)} with random elements.
439:          */
440:         @Test
441:         public void testAddLast() {
442:                 Integer integer1 = -1;
443:                 Integer integer2 = -2;
444:                 String string1 = "a";
445:                 String string2 = "b";
446:                 Object object1 = new Object();
447:                 Object object2 = new Object();
448:
449:                 Deque<Object> deque = new CircularArrayDeque<Object>();
450:
451:                 deque.addLast(integer1);
452:                 assertSame(1, deque.size());
453:                 assertEquals(integer1, deque.getFirst());
454:                 assertEquals(integer1, deque.getLast());
455:                 assertEquals(integer1, deque.peek());
456:
457:                 deque.addLast(integer2);
458:                 assertSame(2, deque.size());
459:                 assertEquals(integer1, deque.getFirst());
460:                 assertEquals(integer1, deque.peek());
461:                 assertEquals(integer2, deque.getLast());
462:
463:                 deque.addLast(string1);
464:                 assertSame(3, deque.size());
465:                 assertEquals(integer1, deque.getFirst());
466:                 assertEquals(integer1, deque.peek());
467:                 assertEquals(string1, deque.getLast());
468:
469:                 deque.addLast(string2);
470:                 assertSame(4, deque.size());
471:                 assertEquals(integer1, deque.getFirst());
472:                 assertEquals(integer1, deque.peek());
473:                 assertEquals(string2, deque.getLast());
474:
475:                 deque.addLast(object1);
476:                 assertSame(5, deque.size());
477:                 assertEquals(integer1, deque.getFirst());
478:                 assertEquals(integer1, deque.peek());
479:                 assertEquals(object1, deque.getLast());
480:
481:                 deque.addLast(object2);
482:                 assertSame(6, deque.size());
483:                 assertEquals(integer1, deque.getFirst());
484:                 assertEquals(integer1, deque.peek());
485:                 assertEquals(object2, deque.getLast());
486:
487:                 deque.addLast(null);
488:                 assertSame(7, deque.size());
489:                 assertEquals(integer1, deque.getFirst());
490:                 assertEquals(integer1, deque.peek());
491:                 assertSame(null, deque.getLast());
492:
493:                 deque.pop();
494:                 assertSame(6, deque.size());
495:                 assertEquals(integer1, deque.getFirst());
496:                 assertEquals(integer1, deque.peek());
497:                 assertEquals(object2, deque.getLast());
498:
499:                 deque.addLast(null);
500:                 assertSame(7, deque.size());
501:                 assertEquals(integer1, deque.getFirst());
502:                 assertEquals(integer1, deque.peek());
503:                 assertSame(null, deque.getLast());
504:
505:                 // Ensure we go above capacity
506:•                for (int i = 0; i < 100; i++) {
507:                         String rand = getRandomString();
508:•                        while (deque.contains(rand)) {
509:                                 rand = getRandomString();
510:                         }
511:                         deque.addLast(rand);
512:                         assertSame(7 + i + 1, deque.size());
513:                         assertEquals(integer1, deque.getFirst());
514:                         assertEquals(integer1, deque.peek());
515:                         assertSame(rand, deque.getLast());
516:                 }
517:         }
518:
519:         /**
520:          * Tests the behavior of {@link CircularArrayDeque#add(int, Object)} with random elements.
521:          */
522:         @Test
523:         public void testAddRandomAccessLeftRotate() {
524:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
525:                                 new Object() };
526:
527:•                for (int i = 0; i < testObjects.length; i++) {
528:                         internalTestAddRandomAccessLeftRotate(testObjects[i]);
529:                 }
530:         }
531:
532:         /**
533:          * Tests the behavior of {@link CircularArrayDeque#add(int, Object)} with random elements but with out of
534:          * bounds indices.
535:          */
536:         @Test
537:         public void testAddRandomAccessOutOfBounds() {
538:                 Deque<Object> deque = new CircularArrayDeque<Object>();
539:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
540:                                 new Object() };
541:
542:•                for (int i = 0; i < testObjects.length; i++) {
543:                         try {
544:                                 deque.add(-1, testObjects[i]);
545:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
546:                         } catch (IndexOutOfBoundsException e) {
547:                                 // expected
548:                         }
549:                         try {
550:                                 deque.add(deque.size() + 1, testObjects[i]);
551:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
552:                         } catch (IndexOutOfBoundsException e) {
553:                                 // expected
554:                         }
555:                 }
556:         }
557:
558:         /**
559:          * Tests the behavior of {@link CircularArrayDeque#add(int, Object)} with random elements.
560:          */
561:         @Test
562:         public void testAddRandomAccessRightRotate() {
563:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
564:                                 new Object() };
565:
566:•                for (int i = 0; i < testObjects.length; i++) {
567:                         internalTestAddRandomAccessRightRotate(testObjects[i]);
568:                 }
569:         }
570:
571:         /**
572:          * Tests the behavior of {@link CircularArrayDeque#clear()} with random elements.
573:          */
574:         @Test
575:         public void testClear() {
576:                 Deque<Object> deque = new CircularArrayDeque<Object>();
577:                 assertSame(0, deque.size());
578:                 assertTrue(deque.isEmpty());
579:                 assertEquals(16, getInternalCapacity(deque));
580:
581:                 deque.clear();
582:                 assertSame(0, deque.size());
583:                 assertTrue(deque.isEmpty());
584:                 assertEquals(16, getInternalCapacity(deque));
585:
586:•                for (int i = 0; i < 100; i++) {
587:                         String rand = getRandomString();
588:•                        while (deque.contains(rand)) {
589:                                 rand = getRandomString();
590:                         }
591:                         deque.offer(rand);
592:                 }
593:                 deque.offer(null);
594:                 assertSame(101, deque.size());
595:                 assertFalse(deque.isEmpty());
596:                 int expectedCapacity = getNextPowerOfTwo(deque.size());
597:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
598:
599:                 deque.clear();
600:                 assertTrue(deque.isEmpty());
601:                 assertSame(0, deque.size());
602:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
603:
604:                 deque.clear();
605:                 assertTrue(deque.isEmpty());
606:                 assertSame(0, deque.size());
607:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
608:         }
609:
610:         /**
611:          * Tests the behavior of {@link CircularArrayDeque#contains()} with random elements.
612:          */
613:         @Test
614:         public void testContains() {
615:                 Deque<Object> deque = new CircularArrayDeque<Object>();
616:
617:                 deque.offer(null);
618:                 assertTrue(deque.contains(null));
619:•                for (int i = 0; i < 100; i++) {
620:                         String rand = getRandomString();
621:•                        while (deque.contains(rand)) {
622:                                 rand = getRandomString();
623:                         }
624:                         deque.offer(rand);
625:                         assertTrue(deque.contains(null));
626:                         assertTrue(deque.contains(rand));
627:                 }
628:
629:                 Deque<Object> dequeCopy = new CircularArrayDeque<Object>(deque);
630:                 assertTrue(deque.contains(null));
631:•                for (Object o : dequeCopy) {
632:                         assertTrue(deque.contains(o));
633:                 }
634:
635:                 deque.clear();
636:                 assertFalse(deque.contains(null));
637:•                for (Object o : dequeCopy) {
638:                         assertFalse(deque.contains(o));
639:                 }
640:         }
641:
642:         /**
643:          * Tests the behavior of {@link CircularArrayDeque#containsAll()} with random elements.
644:          */
645:         @Test
646:         public void testContainsAll() {
647:                 Deque<Object> deque = new CircularArrayDeque<Object>();
648:
649:                 Collection<Object> objects1 = new ArrayList<Object>();
650:                 objects1.add(null);
651:                 objects1.addAll(randomStringDequeNotIn(40, Collections.emptySet()));
652:                 objects1.add(null);
653:                 assertSame(42, objects1.size());
654:
655:                 assertFalse(deque.containsAll(objects1));
656:
657:                 deque.addAll(objects1);
658:                 assertSame(42, deque.size());
659:                 assertTrue(deque.containsAll(objects1));
660:
661:                 Collection<Object> objects2 = new ArrayList<Object>();
662:                 objects2.add(null);
663:                 objects2.addAll(randomStringSetNotIn(40, objects1));
664:                 objects2.add(null);
665:                 assertSame(42, objects2.size());
666:
667:                 assertFalse(deque.containsAll(objects2));
668:
669:                 deque.addAll(objects2);
670:                 assertSame(objects1.size() + objects2.size(), deque.size());
671:                 assertTrue(deque.containsAll(objects1));
672:                 assertTrue(deque.containsAll(objects2));
673:
674:                 deque.clear();
675:                 assertFalse(deque.containsAll(objects1));
676:                 assertFalse(deque.containsAll(objects2));
677:         }
678:
679:         /**
680:          * Tests the behavior of {@link CircularArrayDeque#element()} with random elements.
681:          */
682:         @Test
683:         public void testElement() {
684:                 Deque<Object> deque = new CircularArrayDeque<Object>();
685:
686:                 try {
687:                         deque.element();
688:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
689:                 } catch (NoSuchElementException e) {
690:                         // expected
691:                 }
692:
693:                 deque.offer(null);
694:                 assertSame(null, deque.element());
695:•                for (int i = 0; i < 20; i++) {
696:                         String rand = getRandomString();
697:•                        while (deque.contains(rand)) {
698:                                 rand = getRandomString();
699:                         }
700:                         deque.offer(rand);
701:                         assertSame(null, deque.element());
702:                 }
703:                 List<Object> lastAdded = new ArrayList<Object>();
704:•                for (int i = 0; i < 20; i++) {
705:                         String rand = getRandomString();
706:•                        while (deque.contains(rand)) {
707:                                 rand = getRandomString();
708:                         }
709:                         deque.addFirst(rand);
710:                         lastAdded.add(rand);
711:                         assertEquals(rand, deque.element());
712:                 }
713:•                for (int i = 0; i < 20; i++) {
714:                         deque.removeFirst();
715:•                        if (i < 19) {
716:                                 assertEquals(lastAdded.get(lastAdded.size() - i - 2), deque.element());
717:                         } else {
718:                                 assertSame(null, deque.element());
719:                         }
720:                 }
721:
722:                 deque.clear();
723:                 try {
724:                         deque.element();
725:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
726:                 } catch (NoSuchElementException e) {
727:                         // expected
728:                 }
729:         }
730:
731:         /**
732:          * Tests the behavior of {@link CircularArrayDeque#equals()} with random elements.
733:          */
734:         @Test
735:         public void testEquals() {
736:                 Deque<Object> deque1 = new CircularArrayDeque<Object>();
737:                 Deque<Object> deque2 = new CircularArrayDeque<Object>();
738:
739:                 Collection<Object> objects1 = new ArrayList<Object>();
740:                 objects1.add(null);
741:                 objects1.addAll(randomStringDequeNotIn(40, Collections.emptySet()));
742:                 objects1.add(null);
743:                 assertSame(42, objects1.size());
744:
745:                 deque1.addAll(objects1);
746:                 deque2.addAll(objects1);
747:
748:                 Deque<Object> deque3 = new CircularArrayDeque<Object>(deque1);
749:
750:                 assertTrue(deque1.equals(deque2));
751:                 assertTrue(deque1.equals(deque3));
752:                 assertTrue(deque2.equals(deque1));
753:                 assertTrue(deque2.equals(deque3));
754:                 assertTrue(deque3.equals(deque1));
755:                 assertTrue(deque3.equals(deque2));
756:
757:•                for (int i = 0; i < 100; i++) {
758:                         String rand = getRandomString();
759:•                        while (deque1.contains(rand)) {
760:                                 rand = getRandomString();
761:                         }
762:                         deque1.offer(rand);
763:                         deque2.offer(rand);
764:                 }
765:                 assertTrue(deque1.equals(deque2));
766:                 assertFalse(deque1.equals(deque3));
767:                 assertTrue(deque2.equals(deque1));
768:                 assertFalse(deque2.equals(deque3));
769:                 assertFalse(deque3.equals(deque1));
770:                 assertFalse(deque3.equals(deque2));
771:
772:                 Object removed = deque1.pop();
773:                 assertFalse(deque1.equals(deque2));
774:                 assertFalse(deque1.equals(deque3));
775:                 assertFalse(deque2.equals(deque1));
776:                 assertFalse(deque2.equals(deque3));
777:                 assertFalse(deque3.equals(deque1));
778:                 assertFalse(deque3.equals(deque2));
779:
780:                 deque1.addFirst(removed);
781:                 assertFalse(deque1.equals(deque2));
782:                 assertFalse(deque1.equals(deque3));
783:                 assertFalse(deque2.equals(deque1));
784:                 assertFalse(deque2.equals(deque3));
785:                 assertFalse(deque3.equals(deque1));
786:                 assertFalse(deque3.equals(deque2));
787:
788:                 deque1.removeFirst();
789:                 deque2.pop();
790:                 assertTrue(deque1.equals(deque2));
791:                 assertFalse(deque1.equals(deque3));
792:                 assertTrue(deque2.equals(deque1));
793:                 assertFalse(deque2.equals(deque3));
794:                 assertFalse(deque3.equals(deque1));
795:                 assertFalse(deque3.equals(deque2));
796:
797:                 deque1.offer(removed);
798:                 deque2.offer(removed);
799:                 assertTrue(deque1.equals(deque2));
800:                 assertFalse(deque1.equals(deque3));
801:                 assertTrue(deque2.equals(deque1));
802:                 assertFalse(deque2.equals(deque3));
803:                 assertFalse(deque3.equals(deque1));
804:                 assertFalse(deque3.equals(deque2));
805:         }
806:
807:         /**
808:          * Tests the behavior of {@link CircularArrayDeque#get(int))} with random indices.
809:          */
810:         @Test
811:         public void testGet() {
812:                 Deque<Object> deque = new CircularArrayDeque<Object>();
813:                 List<Object> objects = new ArrayList<Object>();
814:                 int max = 100000;
815:
816:                 try {
817:                         deque.get(0);
818:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
819:                 } catch (IndexOutOfBoundsException e) {
820:                         // expected
821:                 }
822:
823:•                for (int i = 0; i < max; i++) {
824:                         String rand = getRandomString();
825:•                        while (deque.contains(rand)) {
826:                                 rand = getRandomString();
827:                         }
828:                         deque.add(rand);
829:                         objects.add(rand);
830:                 }
831:
832:                 try {
833:                         deque.get(-1);
834:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
835:                 } catch (IndexOutOfBoundsException e) {
836:                         // expected
837:                 }
838:
839:•                for (int i = 0; i < max; i++) {
840:                         assertEquals(objects.get(i), deque.get(i));
841:                         assertEquals(objects.get(max - 1 - i), deque.get(max - 1 - i));
842:                 }
843:
844:                 try {
845:                         deque.get(deque.size());
846:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
847:                 } catch (IndexOutOfBoundsException e) {
848:                         // expected
849:                 }
850:         }
851:
852:         /**
853:          * Tests the behavior of {@link CircularArrayDeque#getFirst()} with random elements.
854:          */
855:         @Test
856:         public void testGetFirst() {
857:                 Deque<Object> deque = new CircularArrayDeque<Object>();
858:
859:                 try {
860:                         deque.getFirst();
861:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
862:                 } catch (NoSuchElementException e) {
863:                         // expected
864:                 }
865:
866:                 deque.offer(null);
867:                 assertSame(null, deque.getFirst());
868:•                for (int i = 0; i < 20; i++) {
869:                         String rand = getRandomString();
870:•                        while (deque.contains(rand)) {
871:                                 rand = getRandomString();
872:                         }
873:                         deque.offer(rand);
874:                         assertSame(null, deque.getFirst());
875:                 }
876:                 List<Object> lastAdded = new ArrayList<Object>();
877:•                for (int i = 0; i < 20; i++) {
878:                         String rand = getRandomString();
879:•                        while (deque.contains(rand)) {
880:                                 rand = getRandomString();
881:                         }
882:                         deque.addFirst(rand);
883:                         lastAdded.add(rand);
884:                         assertEquals(rand, deque.getFirst());
885:                 }
886:•                for (int i = 0; i < 20; i++) {
887:                         deque.removeFirst();
888:•                        if (i < 19) {
889:                                 assertEquals(lastAdded.get(lastAdded.size() - i - 2), deque.getFirst());
890:                         } else {
891:                                 assertSame(null, deque.getFirst());
892:                         }
893:                 }
894:
895:                 deque.clear();
896:                 try {
897:                         deque.getFirst();
898:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
899:                 } catch (NoSuchElementException e) {
900:                         // expected
901:                 }
902:         }
903:
904:         /**
905:          * Tests the behavior of {@link CircularArrayDeque#getLast()} with random elements.
906:          */
907:         @Test
908:         public void testGetLast() {
909:                 Deque<Object> deque = new CircularArrayDeque<Object>();
910:
911:                 try {
912:                         deque.getLast();
913:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
914:                 } catch (NoSuchElementException e) {
915:                         // expected
916:                 }
917:
918:                 deque.offer(null);
919:                 assertSame(null, deque.getLast());
920:                 List<Object> lastAdded = new ArrayList<Object>();
921:•                for (int i = 0; i < 20; i++) {
922:                         String rand = getRandomString();
923:•                        while (deque.contains(rand)) {
924:                                 rand = getRandomString();
925:                         }
926:                         deque.offer(rand);
927:                         lastAdded.add(rand);
928:                         assertEquals(rand, deque.getLast());
929:                 }
930:•                for (int i = 0; i < 20; i++) {
931:                         String rand = getRandomString();
932:•                        while (deque.contains(rand)) {
933:                                 rand = getRandomString();
934:                         }
935:                         deque.addFirst(rand);
936:                         assertEquals(lastAdded.get(lastAdded.size() - 1), deque.getLast());
937:                 }
938:•                for (int i = 0; i < 20; i++) {
939:                         deque.removeLast();
940:•                        if (i < 19) {
941:                                 assertEquals(lastAdded.get(lastAdded.size() - i - 2), deque.getLast());
942:                         } else {
943:                                 assertSame(null, deque.getLast());
944:                         }
945:                 }
946:
947:                 deque.clear();
948:                 try {
949:                         deque.getLast();
950:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
951:                 } catch (NoSuchElementException e) {
952:                         // expected
953:                 }
954:         }
955:
956:         /**
957:          * Tests the behavior of {@link CircularArrayDeque#hashCode()} with random elements.
958:          */
959:         @Test
960:         public void testHashCode() {
961:                 Deque<Object> deque1 = new CircularArrayDeque<Object>();
962:                 Deque<Object> deque2 = new CircularArrayDeque<Object>();
963:
964:                 Collection<Object> objects1 = new ArrayList<Object>();
965:                 objects1.add(null);
966:                 objects1.addAll(randomStringDequeNotIn(40, Collections.emptySet()));
967:                 objects1.add(null);
968:                 assertSame(42, objects1.size());
969:
970:                 Collection<Object> objects2 = new ArrayList<Object>();
971:                 objects2.add(null);
972:                 objects2.addAll(randomStringSetNotIn(40, objects1));
973:                 objects2.add(null);
974:                 assertSame(42, objects2.size());
975:
976:                 deque1.addAll(objects1);
977:                 deque2.addAll(objects1);
978:
979:                 Deque<Object> deque3 = new CircularArrayDeque<Object>(deque1);
980:
981:                 assertEquals(deque1.hashCode(), deque2.hashCode());
982:                 assertEquals(deque1.hashCode(), deque3.hashCode());
983:                 assertEquals(deque2.hashCode(), deque1.hashCode());
984:                 assertEquals(deque2.hashCode(), deque3.hashCode());
985:                 assertEquals(deque3.hashCode(), deque1.hashCode());
986:                 assertEquals(deque3.hashCode(), deque2.hashCode());
987:
988:•                for (int i = 0; i < 100; i++) {
989:                         String rand = getRandomString();
990:•                        while (deque1.contains(rand)) {
991:                                 rand = getRandomString();
992:                         }
993:                         deque1.offer(rand);
994:                         deque2.offer(rand);
995:                 }
996:                 assertEquals(deque1.hashCode(), deque2.hashCode());
997:•                assertFalse(deque1.hashCode() == deque3.hashCode());
998:                 assertEquals(deque2.hashCode(), deque1.hashCode());
999:•                assertFalse(deque2.hashCode() == deque3.hashCode());
1000:•                assertFalse(deque3.hashCode() == deque1.hashCode());
1001:•                assertFalse(deque3.hashCode() == deque2.hashCode());
1002:
1003:                 Object removed = deque1.pop();
1004:•                assertFalse(deque1.hashCode() == deque2.hashCode());
1005:•                assertFalse(deque1.hashCode() == deque3.hashCode());
1006:•                assertFalse(deque2.hashCode() == deque1.hashCode());
1007:•                assertFalse(deque2.hashCode() == deque3.hashCode());
1008:•                assertFalse(deque3.hashCode() == deque1.hashCode());
1009:•                assertFalse(deque3.hashCode() == deque2.hashCode());
1010:
1011:                 deque1.addFirst(removed);
1012:•                assertFalse(deque1.hashCode() == deque2.hashCode());
1013:•                assertFalse(deque1.hashCode() == deque3.hashCode());
1014:•                assertFalse(deque2.hashCode() == deque1.hashCode());
1015:•                assertFalse(deque2.hashCode() == deque3.hashCode());
1016:•                assertFalse(deque3.hashCode() == deque1.hashCode());
1017:•                assertFalse(deque3.hashCode() == deque2.hashCode());
1018:
1019:                 deque1.removeFirst();
1020:                 deque2.pop();
1021:                 assertEquals(deque1.hashCode(), deque2.hashCode());
1022:•                assertFalse(deque1.hashCode() == deque3.hashCode());
1023:                 assertEquals(deque2.hashCode(), deque1.hashCode());
1024:•                assertFalse(deque2.hashCode() == deque3.hashCode());
1025:•                assertFalse(deque3.hashCode() == deque1.hashCode());
1026:•                assertFalse(deque3.hashCode() == deque2.hashCode());
1027:
1028:                 deque1.offer(removed);
1029:                 deque2.offer(removed);
1030:                 assertEquals(deque1.hashCode(), deque2.hashCode());
1031:•                assertFalse(deque1.hashCode() == deque3.hashCode());
1032:                 assertEquals(deque2.hashCode(), deque1.hashCode());
1033:•                assertFalse(deque2.hashCode() == deque3.hashCode());
1034:•                assertFalse(deque3.hashCode() == deque1.hashCode());
1035:•                assertFalse(deque3.hashCode() == deque2.hashCode());
1036:         }
1037:
1038:         /**
1039:          * Tests the behavior of {@link CircularArrayDeque#indexOf(Object)} with random elements.
1040:          */
1041:         @Test
1042:         public void testIndexOf() {
1043:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 5.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
1044:                                 new Object() };
1045:
1046:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1047:•                for (int i = 0; i < testObjects.length; i++) {
1048:                         assertEquals(Integer.valueOf(-1), Integer.valueOf(deque.indexOf(testObjects[i])));
1049:                 }
1050:
1051:•                for (Object o : testObjects) {
1052:                         deque.offer(o);
1053:                 }
1054:
1055:                 Object[] expected = new Object[16];
1056:•                for (int i = 0; i < testObjects.length; i++) {
1057:                         expected[i] = testObjects[i];
1058:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.indexOf(testObjects[i])));
1059:                 }
1060:                 assertEqualContent(expected, getInternalArray(deque));
1061:
1062:                 deque.clear();
1063:•                for (int i = 0; i < testObjects.length; i++) {
1064:                         assertEquals(Integer.valueOf(-1), Integer.valueOf(deque.indexOf(testObjects[i])));
1065:                 }
1066:
1067:                 deque = new CircularArrayDeque<Object>();
1068:                 deque.offer("a"); //$NON-NLS-1$
1069:•                for (Object o : testObjects) {
1070:                         deque.offer(o);
1071:                 }
1072:                 deque.removeFirst();
1073:                 int offset = 1;
1074:                 expected = new Object[16];
1075:•                for (int i = 0; i < testObjects.length; i++) {
1076:                         expected[i + offset] = testObjects[i];
1077:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.indexOf(testObjects[i])));
1078:                 }
1079:                 assertEqualContent(expected, getInternalArray(deque));
1080:
1081:                 deque = new CircularArrayDeque<Object>();
1082:•                for (int i = 0; i < 10; i++) {
1083:                         deque.offer("a"); //$NON-NLS-1$                        
1084:                 }
1085:•                for (int i = 0; i < 9; i++) {
1086:                         deque.removeFirst();
1087:                 }
1088:•                for (Object o : testObjects) {
1089:                         deque.offer(o);
1090:                 }
1091:                 deque.removeFirst();
1092:                 offset = 10;
1093:                 expected = new Object[16];
1094:•                for (int i = 0; i < testObjects.length; i++) {
1095:                         expected[(i + offset) & (expected.length - 1)] = testObjects[i];
1096:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.indexOf(testObjects[i])));
1097:                 }
1098:                 assertEqualContent(expected, getInternalArray(deque));
1099:
1100:                 deque = new CircularArrayDeque<Object>();
1101:•                for (Object o : testObjects) {
1102:                         deque.offer(o);
1103:                 }
1104:•                for (Object o : testObjects) {
1105:                         deque.offer(o);
1106:                 }
1107:                 expected = new Object[getNextPowerOfTwo(testObjects.length * 2)];
1108:•                for (int i = 0; i < testObjects.length; i++) {
1109:                         expected[i] = testObjects[i];
1110:                         expected[i + testObjects.length] = testObjects[i];
1111:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.indexOf(testObjects[i])));
1112:                         assertEquals(Integer.valueOf(i + testObjects.length), Integer.valueOf(deque
1113:                                         .lastIndexOf(testObjects[i])));
1114:                 }
1115:                 assertEqualContent(expected, getInternalArray(deque));
1116:         }
1117:
1118:         /**
1119:          * Tests that the copy constructor of the Deque creates a deque with all objects of the initial
1120:          * collection.
1121:          */
1122:         @Test
1123:         public void testInstantiationCopy() {
1124:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
1125:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
1126:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1127:
1128:                 Deque<Object> deque = new CircularArrayDeque<Object>(listInt10);
1129:                 assertFalse(deque.isEmpty());
1130:                 assertEquals(listInt10.size(), deque.size());
1131:                 assertTrue(deque.containsAll(listInt10));
1132:                 assertEquals(getNextPowerOfTwo(listInt10.size()), getInternalCapacity(deque));
1133:
1134:                 deque = new CircularArrayDeque<Object>(setString20);
1135:                 assertFalse(deque.isEmpty());
1136:                 assertEquals(setString20.size(), deque.size());
1137:                 assertTrue(deque.containsAll(setString20));
1138:                 assertEquals(getNextPowerOfTwo(setString20.size()), getInternalCapacity(deque));
1139:
1140:                 deque = new CircularArrayDeque<Object>(dequeString40);
1141:                 assertFalse(deque.isEmpty());
1142:                 assertEquals(dequeString40.size(), deque.size());
1143:                 assertTrue(deque.containsAll(dequeString40));
1144:                 assertEquals(getNextPowerOfTwo(dequeString40.size()), getInternalCapacity(deque));
1145:         }
1146:
1147:         /**
1148:          * Tests the two constructors of the Deque that initialize an empty deque.
1149:          */
1150:         @Test
1151:         public void testInstantiationEmpty() {
1152:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1153:                 assertTrue(deque.isEmpty());
1154:                 assertSame(0, deque.size());
1155:                 // Default capacity is 16
1156:                 assertEquals(16, getInternalCapacity(deque));
1157:
1158:                 deque = new CircularArrayDeque<Object>((1 << 10) - 1);
1159:                 assertTrue(deque.isEmpty());
1160:                 assertSame(0, deque.size());
1161:                 assertEquals(1 << 10, getInternalCapacity(deque));
1162:
1163:                 deque = new CircularArrayDeque<Object>(1 << 31);
1164:                 assertTrue(deque.isEmpty());
1165:                 assertSame(0, deque.size());
1166:                 assertEquals(4, getInternalCapacity(deque));
1167:
1168:                 deque = new CircularArrayDeque<Object>(-1);
1169:                 assertTrue(deque.isEmpty());
1170:                 assertSame(0, deque.size());
1171:                 assertEquals(4, getInternalCapacity(deque));
1172:         }
1173:
1174:         /**
1175:          * Tests the constructors of the Deque with out of bounds or erroneous values.
1176:          */
1177:         @Test
1178:         public void testInstantiationError() {
1179:                 try {
1180:                         new CircularArrayDeque<Object>(Integer.MAX_VALUE);
1181:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1182:                 } catch (IndexOutOfBoundsException e) {
1183:                         // Expected
1184:                 }
1185:                 try {
1186:                         /*
1187:                          * The last possible size for our internal array is 2^30, trying to hold that much elements will
1188:                          * yield a size of -1, which is invalid.
1189:                          */
1190:                         new CircularArrayDeque<Object>((1 << 30) + 1);
1191:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1192:                 } catch (IndexOutOfBoundsException e) {
1193:                         // Expected
1194:                 }
1195:         }
1196:
1197:         /**
1198:          * Tests the behavior of {@link CircularArrayDeque#isEmpty()} with random elements.
1199:          */
1200:         @Test
1201:         public void testIsEmpty() {
1202:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1203:                 assertTrue(deque.isEmpty());
1204:
1205:                 deque.offer(null);
1206:                 assertFalse(deque.isEmpty());
1207:
1208:•                for (int i = 0; i < 100; i++) {
1209:                         String rand = getRandomString();
1210:•                        while (deque.contains(rand)) {
1211:                                 rand = getRandomString();
1212:                         }
1213:                         deque.offer(rand);
1214:                         assertFalse(deque.isEmpty());
1215:                 }
1216:•                for (int i = 0; i < 100; i++) {
1217:                         deque.pop();
1218:                         assertFalse(deque.isEmpty());
1219:                 }
1220:
1221:                 deque.pop();
1222:                 assertTrue(deque.isEmpty());
1223:
1224:•                for (int i = 0; i < 100; i++) {
1225:                         String rand = getRandomString();
1226:•                        while (deque.contains(rand)) {
1227:                                 rand = getRandomString();
1228:                         }
1229:                         deque.offer(rand);
1230:                         assertFalse(deque.isEmpty());
1231:                 }
1232:
1233:                 deque.clear();
1234:                 assertTrue(deque.isEmpty());
1235:         }
1236:
1237:         /**
1238:          * Tests the behavior of the serialization and deserialization support of the {@link CircularArrayDeque}.
1239:          * FIXME test deserialization from file to ensure we do not break support of older serialized deques.
1240:          */
1241:         @Test
1242:         public void testIsSerializable() {
1243:                 Collection<Object> emptyCollection = Collections.emptyList();
1244:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
1245:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
1246:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1247:                 Collection<Object> duplicatesList = new ArrayList<Object>();
1248:•                for (int i = 0; i < 40; i++) {
1249:                         int dupe = i / 2;
1250:                         duplicatesList.add(Integer.valueOf(dupe));
1251:                         duplicatesList.add(String.valueOf(dupe));
1252:                 }
1253:                 duplicatesList.add(null);
1254:                 duplicatesList.add(null);
1255:
1256:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1257:
1258:                 byte[] serialized = writeDeque(deque);
1259:•                assertTrue(serialized.length > 0);
1260:                 Deque<Object> read = readDeque(serialized);
1261:                 assertNotNull(read);
1262:                 assertEquals(deque, read);
1263:
1264:                 deque.addAll(emptyCollection);
1265:                 serialized = writeDeque(deque);
1266:•                assertTrue(serialized.length > 0);
1267:                 read = readDeque(serialized);
1268:                 assertNotNull(read);
1269:                 assertEquals(deque, read);
1270:
1271:                 deque.addAll(listInt10);
1272:                 serialized = writeDeque(deque);
1273:•                assertTrue(serialized.length > 0);
1274:                 read = readDeque(serialized);
1275:                 assertNotNull(read);
1276:                 assertEquals(deque, read);
1277:
1278:                 deque.addAll(setString20);
1279:                 serialized = writeDeque(deque);
1280:•                assertTrue(serialized.length > 0);
1281:                 read = readDeque(serialized);
1282:                 assertNotNull(read);
1283:                 assertEquals(deque, read);
1284:
1285:                 deque.addAll(dequeString40);
1286:                 serialized = writeDeque(deque);
1287:•                assertTrue(serialized.length > 0);
1288:                 read = readDeque(serialized);
1289:                 assertNotNull(read);
1290:                 assertEquals(deque, read);
1291:
1292:                 deque.addAll(duplicatesList);
1293:                 serialized = writeDeque(deque);
1294:•                assertTrue(serialized.length > 0);
1295:                 read = readDeque(serialized);
1296:                 assertNotNull(read);
1297:                 assertEquals(deque, read);
1298:         }
1299:
1300:         /**
1301:          * Tests the behavior of {@link CircularArrayDeque#iterator()} with random elements.
1302:          */
1303:         @Test
1304:         public void testIterator() {
1305:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
1306:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
1307:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1308:
1309:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1310:
1311:                 Iterator<Object> emptyIterator = deque.iterator();
1312:                 assertFalse(emptyIterator.hasNext());
1313:                 try {
1314:                         emptyIterator.next();
1315:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1316:                 } catch (NoSuchElementException e) {
1317:                         // expected
1318:                 }
1319:                 try {
1320:                         emptyIterator.remove();
1321:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1322:                 } catch (IllegalStateException e) {
1323:                         // expected
1324:                 }
1325:
1326:                 Iterator<Object> concurrentIterator = deque.iterator();
1327:                 deque.addFirst(null);
1328:                 try {
1329:                         concurrentIterator.next();
1330:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1331:                 } catch (ConcurrentModificationException e) {
1332:                         // expected
1333:                 }
1334:                 try {
1335:                         concurrentIterator.remove();
1336:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1337:                 } catch (IllegalStateException e) {
1338:                         // expected
1339:                 }
1340:                 deque.pop();
1341:
1342:                 concurrentIterator = deque.iterator();
1343:                 deque.addLast(null);
1344:                 try {
1345:                         concurrentIterator.next();
1346:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1347:                 } catch (ConcurrentModificationException e) {
1348:                         // expected
1349:                 }
1350:                 try {
1351:                         concurrentIterator.remove();
1352:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1353:                 } catch (IllegalStateException e) {
1354:                         // expected
1355:                 }
1356:                 deque.pop();
1357:
1358:                 deque.addLast(null);
1359:                 concurrentIterator = deque.iterator();
1360:                 assertNull(concurrentIterator.next());
1361:                 deque.addLast(null);
1362:                 try {
1363:                         concurrentIterator.remove();
1364:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1365:                 } catch (ConcurrentModificationException e) {
1366:                         // expected
1367:                 }
1368:                 deque.clear();
1369:
1370:                 deque.addAll(listInt10);
1371:                 deque.addAll(setString20);
1372:                 deque.addAll(dequeString40);
1373:
1374:                 Iterator<Integer> listIterator = listInt10.iterator();
1375:                 Iterator<String> setIterator = setString20.iterator();
1376:                 Iterator<String> dequeIterator = dequeString40.iterator();
1377:                 Iterator<Object> containedValues = deque.iterator();
1378:•                while (listIterator.hasNext()) {
1379:                         assertEquals(listIterator.next(), containedValues.next());
1380:                 }
1381:                 assertTrue(containedValues.hasNext());
1382:•                while (setIterator.hasNext()) {
1383:                         assertEquals(setIterator.next(), containedValues.next());
1384:                 }
1385:                 assertTrue(containedValues.hasNext());
1386:•                while (dequeIterator.hasNext()) {
1387:                         assertEquals(dequeIterator.next(), containedValues.next());
1388:                 }
1389:                 assertFalse(containedValues.hasNext());
1390:
1391:                 for (@SuppressWarnings("unused")
1392:•                Integer val : listInt10) {
1393:                         deque.removeFirst();
1394:                 }
1395:                 deque.addAll(listInt10);
1396:
1397:                 listIterator = listInt10.iterator();
1398:                 setIterator = setString20.iterator();
1399:                 dequeIterator = dequeString40.iterator();
1400:                 containedValues = deque.iterator();
1401:•                while (setIterator.hasNext()) {
1402:                         assertEquals(setIterator.next(), containedValues.next());
1403:                 }
1404:                 assertTrue(containedValues.hasNext());
1405:•                while (dequeIterator.hasNext()) {
1406:                         assertEquals(dequeIterator.next(), containedValues.next());
1407:                 }
1408:                 assertTrue(containedValues.hasNext());
1409:•                while (listIterator.hasNext()) {
1410:                         assertEquals(listIterator.next(), containedValues.next());
1411:                 }
1412:                 assertFalse(containedValues.hasNext());
1413:         }
1414:
1415:         /**
1416:          * Tests the removal of elements of the Deque through the iterator.remove method.
1417:          */
1418:         @Test
1419:         public void testIteratorRemove() {
1420:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
1421:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
1422:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1423:
1424:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1425:
1426:                 Iterator<Object> emptyIterator = deque.iterator();
1427:                 assertFalse(emptyIterator.hasNext());
1428:                 try {
1429:                         emptyIterator.next();
1430:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1431:                 } catch (NoSuchElementException e) {
1432:                         // expected
1433:                 }
1434:                 try {
1435:                         emptyIterator.remove();
1436:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1437:                 } catch (IllegalStateException e) {
1438:                         // expected
1439:                 }
1440:
1441:                 Iterator<Object> concurrentIterator = deque.iterator();
1442:                 deque.addFirst(null);
1443:                 try {
1444:                         concurrentIterator.next();
1445:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1446:                 } catch (ConcurrentModificationException e) {
1447:                         // expected
1448:                 }
1449:                 try {
1450:                         concurrentIterator.remove();
1451:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1452:                 } catch (IllegalStateException e) {
1453:                         // expected
1454:                 }
1455:                 deque.pop();
1456:
1457:                 concurrentIterator = deque.iterator();
1458:                 deque.addLast(null);
1459:                 try {
1460:                         concurrentIterator.next();
1461:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1462:                 } catch (ConcurrentModificationException e) {
1463:                         // expected
1464:                 }
1465:                 try {
1466:                         concurrentIterator.remove();
1467:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1468:                 } catch (IllegalStateException e) {
1469:                         // expected
1470:                 }
1471:                 deque.pop();
1472:
1473:                 deque.addAll(listInt10);
1474:                 deque.addAll(setString20);
1475:                 deque.addAll(dequeString40);
1476:
1477:                 Iterator<Integer> listIterator = listInt10.iterator();
1478:                 Iterator<String> setIterator = setString20.iterator();
1479:                 Iterator<String> dequeIterator = dequeString40.iterator();
1480:                 Iterator<Object> containedValues = deque.iterator();
1481:•                while (listIterator.hasNext()) {
1482:                         assertEquals(listIterator.next(), containedValues.next());
1483:                         containedValues.remove();
1484:                 }
1485:                 assertTrue(containedValues.hasNext());
1486:•                while (setIterator.hasNext()) {
1487:                         assertEquals(setIterator.next(), containedValues.next());
1488:                         containedValues.remove();
1489:                 }
1490:                 assertTrue(containedValues.hasNext());
1491:•                while (dequeIterator.hasNext()) {
1492:                         assertEquals(dequeIterator.next(), containedValues.next());
1493:                         containedValues.remove();
1494:                 }
1495:                 assertFalse(containedValues.hasNext());
1496:         }
1497:
1498:         /**
1499:          * Tests the behavior of {@link CircularArrayDeque#lastIndexOf(Object)} with random elements.
1500:          */
1501:         @Test
1502:         public void testLastIndexOf() {
1503:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 5.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
1504:                                 new Object() };
1505:
1506:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1507:•                for (int i = 0; i < testObjects.length; i++) {
1508:                         assertEquals(Integer.valueOf(-1), Integer.valueOf(deque.lastIndexOf(testObjects[i])));
1509:                 }
1510:
1511:•                for (Object o : testObjects) {
1512:                         deque.offer(o);
1513:                 }
1514:
1515:                 Object[] expected = new Object[16];
1516:•                for (int i = 0; i < testObjects.length; i++) {
1517:                         expected[i] = testObjects[i];
1518:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.lastIndexOf(testObjects[i])));
1519:                 }
1520:                 assertEqualContent(expected, getInternalArray(deque));
1521:
1522:                 deque.clear();
1523:•                for (int i = 0; i < testObjects.length; i++) {
1524:                         assertEquals(Integer.valueOf(-1), Integer.valueOf(deque.lastIndexOf(testObjects[i])));
1525:                 }
1526:
1527:                 deque = new CircularArrayDeque<Object>();
1528:                 deque.offer("a"); //$NON-NLS-1$
1529:•                for (Object o : testObjects) {
1530:                         deque.offer(o);
1531:                 }
1532:                 deque.removeFirst();
1533:                 int offset = 1;
1534:                 expected = new Object[16];
1535:•                for (int i = 0; i < testObjects.length; i++) {
1536:                         expected[i + offset] = testObjects[i];
1537:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.lastIndexOf(testObjects[i])));
1538:                 }
1539:                 assertEqualContent(expected, getInternalArray(deque));
1540:
1541:                 deque = new CircularArrayDeque<Object>();
1542:•                for (int i = 0; i < 10; i++) {
1543:                         deque.offer("a"); //$NON-NLS-1$                        
1544:                 }
1545:•                for (int i = 0; i < 9; i++) {
1546:                         deque.removeFirst();
1547:                 }
1548:•                for (Object o : testObjects) {
1549:                         deque.offer(o);
1550:                 }
1551:                 deque.removeFirst();
1552:                 offset = 10;
1553:                 expected = new Object[16];
1554:•                for (int i = 0; i < testObjects.length; i++) {
1555:                         expected[(i + offset) & (expected.length - 1)] = testObjects[i];
1556:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.lastIndexOf(testObjects[i])));
1557:                 }
1558:                 assertEqualContent(expected, getInternalArray(deque));
1559:
1560:                 deque = new CircularArrayDeque<Object>();
1561:•                for (Object o : testObjects) {
1562:                         deque.offer(o);
1563:                 }
1564:•                for (Object o : testObjects) {
1565:                         deque.offer(o);
1566:                 }
1567:                 expected = new Object[getNextPowerOfTwo(testObjects.length * 2)];
1568:•                for (int i = 0; i < testObjects.length; i++) {
1569:                         expected[i] = testObjects[i];
1570:                         expected[i + testObjects.length] = testObjects[i];
1571:                         assertEquals(Integer.valueOf(i), Integer.valueOf(deque.indexOf(testObjects[i])));
1572:                         assertEquals(Integer.valueOf(i + testObjects.length), Integer.valueOf(deque
1573:                                         .lastIndexOf(testObjects[i])));
1574:                 }
1575:                 assertEqualContent(expected, getInternalArray(deque));
1576:         }
1577:
1578:         /**
1579:          * Tests the behavior of {@link CircularArrayDeque#listIterator()} with random elements.
1580:          */
1581:         @Test
1582:         public void testListIterator() {
1583:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1584:
1585:                 ListIterator<Object> emptyIterator = deque.listIterator();
1586:                 assertFalse(emptyIterator.hasNext());
1587:                 assertFalse(emptyIterator.hasPrevious());
1588:                 assertSame(0, emptyIterator.nextIndex());
1589:                 assertSame(-1, emptyIterator.previousIndex());
1590:                 try {
1591:                         emptyIterator.next();
1592:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1593:                 } catch (NoSuchElementException e) {
1594:                         // expected
1595:                 }
1596:                 try {
1597:                         emptyIterator.previous();
1598:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1599:                 } catch (NoSuchElementException e) {
1600:                         // expected
1601:                 }
1602:                 try {
1603:                         emptyIterator.set(new Object());
1604:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1605:                 } catch (IllegalStateException e) {
1606:                         // expected
1607:                 }
1608:                 try {
1609:                         emptyIterator.remove();
1610:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1611:                 } catch (IllegalStateException e) {
1612:                         // expected
1613:                 }
1614:                 Object a = new Object();
1615:                 emptyIterator.add(a);
1616:                 assertSame(1, deque.size());
1617:                 assertFalse(emptyIterator.hasNext());
1618:                 assertTrue(emptyIterator.hasPrevious());
1619:                 assertSame(1, emptyIterator.nextIndex());
1620:                 assertSame(0, emptyIterator.previousIndex());
1621:
1622:                 assertEquals(a, emptyIterator.previous());
1623:                 assertTrue(emptyIterator.hasNext());
1624:                 assertFalse(emptyIterator.hasPrevious());
1625:                 assertSame(0, emptyIterator.nextIndex());
1626:                 assertSame(-1, emptyIterator.previousIndex());
1627:
1628:                 assertEquals(a, emptyIterator.next());
1629:                 assertFalse(emptyIterator.hasNext());
1630:                 assertTrue(emptyIterator.hasPrevious());
1631:                 assertSame(1, emptyIterator.nextIndex());
1632:                 assertSame(0, emptyIterator.previousIndex());
1633:
1634:                 Object b = new Object();
1635:                 emptyIterator.add(b);
1636:                 assertSame(2, deque.size());
1637:                 assertFalse(emptyIterator.hasNext());
1638:                 assertTrue(emptyIterator.hasPrevious());
1639:                 assertSame(2, emptyIterator.nextIndex());
1640:                 assertSame(1, emptyIterator.previousIndex());
1641:
1642:                 assertEquals(b, emptyIterator.previous());
1643:                 assertTrue(emptyIterator.hasNext());
1644:                 assertTrue(emptyIterator.hasPrevious());
1645:                 assertSame(1, emptyIterator.nextIndex());
1646:                 assertSame(0, emptyIterator.previousIndex());
1647:
1648:                 Object c = new Object();
1649:                 emptyIterator.set(c);
1650:                 assertSame(2, deque.size());
1651:                 assertTrue(emptyIterator.hasNext());
1652:                 assertTrue(emptyIterator.hasPrevious());
1653:                 assertSame(1, emptyIterator.nextIndex());
1654:                 assertSame(0, emptyIterator.previousIndex());
1655:
1656:                 assertEquals(c, emptyIterator.next());
1657:                 assertFalse(emptyIterator.hasNext());
1658:                 assertTrue(emptyIterator.hasPrevious());
1659:                 assertSame(2, emptyIterator.nextIndex());
1660:                 assertSame(1, emptyIterator.previousIndex());
1661:
1662:                 assertEquals(c, emptyIterator.previous());
1663:                 assertTrue(emptyIterator.hasNext());
1664:                 assertTrue(emptyIterator.hasPrevious());
1665:                 assertSame(1, emptyIterator.nextIndex());
1666:                 assertSame(0, emptyIterator.previousIndex());
1667:
1668:                 emptyIterator.remove();
1669:                 assertSame(1, deque.size());
1670:                 assertFalse(emptyIterator.hasNext());
1671:                 assertTrue(emptyIterator.hasPrevious());
1672:                 assertSame(1, emptyIterator.nextIndex());
1673:                 assertSame(0, emptyIterator.previousIndex());
1674:
1675:                 try {
1676:                         emptyIterator.next();
1677:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1678:                 } catch (NoSuchElementException e) {
1679:                         // expected
1680:                 }
1681:
1682:                 assertEquals(a, emptyIterator.previous());
1683:                 assertTrue(emptyIterator.hasNext());
1684:                 assertFalse(emptyIterator.hasPrevious());
1685:                 assertSame(0, emptyIterator.nextIndex());
1686:                 assertSame(-1, emptyIterator.previousIndex());
1687:
1688:                 emptyIterator.remove();
1689:                 assertSame(0, deque.size());
1690:                 assertFalse(emptyIterator.hasNext());
1691:                 assertFalse(emptyIterator.hasPrevious());
1692:                 assertSame(0, emptyIterator.nextIndex());
1693:                 assertSame(-1, emptyIterator.previousIndex());
1694:
1695:                 try {
1696:                         emptyIterator.next();
1697:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1698:                 } catch (NoSuchElementException e) {
1699:                         // expected
1700:                 }
1701:                 try {
1702:                         emptyIterator.previous();
1703:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
1704:                 } catch (NoSuchElementException e) {
1705:                         // expected
1706:                 }
1707:                 try {
1708:                         emptyIterator.set(new Object());
1709:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1710:                 } catch (IllegalStateException e) {
1711:                         // expected
1712:                 }
1713:                 try {
1714:                         emptyIterator.remove();
1715:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1716:                 } catch (IllegalStateException e) {
1717:                         // expected
1718:                 }
1719:
1720:                 ListIterator<Object> concurrentIterator = deque.listIterator();
1721:                 deque.addFirst(null);
1722:                 try {
1723:                         concurrentIterator.next();
1724:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1725:                 } catch (ConcurrentModificationException e) {
1726:                         // expected
1727:                 }
1728:                 try {
1729:                         concurrentIterator.previous();
1730:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1731:                 } catch (ConcurrentModificationException e) {
1732:                         // expected
1733:                 }
1734:                 try {
1735:                         concurrentIterator.add(new Object());
1736:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1737:                 } catch (ConcurrentModificationException e) {
1738:                         // expected
1739:                 }
1740:                 try {
1741:                         concurrentIterator.set(new Object());
1742:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1743:                 } catch (IllegalStateException e) {
1744:                         // expected
1745:                 }
1746:                 try {
1747:                         concurrentIterator.remove();
1748:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1749:                 } catch (IllegalStateException e) {
1750:                         // expected
1751:                 }
1752:                 deque.pop();
1753:
1754:                 concurrentIterator = deque.listIterator();
1755:                 deque.addLast(null);
1756:                 try {
1757:                         concurrentIterator.next();
1758:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1759:                 } catch (ConcurrentModificationException e) {
1760:                         // expected
1761:                 }
1762:                 try {
1763:                         concurrentIterator.previous();
1764:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1765:                 } catch (ConcurrentModificationException e) {
1766:                         // expected
1767:                 }
1768:                 try {
1769:                         concurrentIterator.add(new Object());
1770:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1771:                 } catch (ConcurrentModificationException e) {
1772:                         // expected
1773:                 }
1774:                 try {
1775:                         concurrentIterator.set(new Object());
1776:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1777:                 } catch (IllegalStateException e) {
1778:                         // expected
1779:                 }
1780:                 try {
1781:                         concurrentIterator.remove();
1782:                         fail("Expected IllegalStateException hasn't been thrown"); //$NON-NLS-1$
1783:                 } catch (IllegalStateException e) {
1784:                         // expected
1785:                 }
1786:                 deque.pop();
1787:
1788:                 deque.addLast(null);
1789:                 concurrentIterator = deque.listIterator();
1790:                 assertNull(concurrentIterator.next());
1791:                 deque.addLast(null);
1792:                 try {
1793:                         concurrentIterator.next();
1794:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1795:                 } catch (ConcurrentModificationException e) {
1796:                         // expected
1797:                 }
1798:                 try {
1799:                         concurrentIterator.previous();
1800:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1801:                 } catch (ConcurrentModificationException e) {
1802:                         // expected
1803:                 }
1804:                 try {
1805:                         concurrentIterator.add(new Object());
1806:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1807:                 } catch (ConcurrentModificationException e) {
1808:                         // expected
1809:                 }
1810:                 try {
1811:                         concurrentIterator.set(new Object());
1812:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1813:                 } catch (ConcurrentModificationException e) {
1814:                         // expected
1815:                 }
1816:                 try {
1817:                         concurrentIterator.remove();
1818:                         fail("Expected ConcurrentModificationException hasn't been thrown"); //$NON-NLS-1$
1819:                 } catch (ConcurrentModificationException e) {
1820:                         // expected
1821:                 }
1822:                 deque.clear();
1823:
1824:                 List<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
1825:                 Set<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
1826:                 List<String> dequeString40 = randomStringDequeNotIn(40, setString20);
1827:
1828:                 deque.addAll(listInt10);
1829:                 deque.addAll(setString20);
1830:                 deque.addAll(dequeString40);
1831:
1832:                 Iterator<Integer> listIterator = listInt10.iterator();
1833:                 Iterator<String> setIterator = setString20.iterator();
1834:                 Iterator<String> dequeIterator = dequeString40.iterator();
1835:                 ListIterator<Object> containedValues = deque.listIterator();
1836:•                while (listIterator.hasNext()) {
1837:                         assertEquals(listIterator.next(), containedValues.next());
1838:                 }
1839:                 assertTrue(containedValues.hasNext());
1840:•                while (setIterator.hasNext()) {
1841:                         assertEquals(setIterator.next(), containedValues.next());
1842:                 }
1843:                 assertTrue(containedValues.hasNext());
1844:•                while (dequeIterator.hasNext()) {
1845:                         assertEquals(dequeIterator.next(), containedValues.next());
1846:                 }
1847:                 assertFalse(containedValues.hasNext());
1848:                 assertTrue(containedValues.hasPrevious());
1849:•                for (int i = dequeString40.size() - 1; i >= 0 && containedValues.hasPrevious(); i--) {
1850:                         assertEquals(dequeString40.get(i), containedValues.previous());
1851:                 }
1852:                 assertTrue(containedValues.hasPrevious());
1853:                 List<Object> setCopy = new ArrayList<Object>(setString20);
1854:•                for (int i = setString20.size() - 1; i >= 0 && containedValues.hasPrevious(); i--) {
1855:                         assertEquals(setCopy.get(i), containedValues.previous());
1856:                 }
1857:                 assertTrue(containedValues.hasPrevious());
1858:•                for (int i = listInt10.size() - 1; i >= 0 && containedValues.hasPrevious(); i--) {
1859:                         assertEquals(listInt10.get(i), containedValues.previous());
1860:                 }
1861:                 assertFalse(containedValues.hasPrevious());
1862:
1863:                 for (@SuppressWarnings("unused")
1864:•                Integer val : listInt10) {
1865:                         deque.removeFirst();
1866:                 }
1867:                 deque.addAll(listInt10);
1868:
1869:                 listIterator = listInt10.iterator();
1870:                 setIterator = setString20.iterator();
1871:                 dequeIterator = dequeString40.iterator();
1872:                 containedValues = deque.listIterator();
1873:•                while (setIterator.hasNext()) {
1874:                         assertEquals(setIterator.next(), containedValues.next());
1875:                 }
1876:                 assertTrue(containedValues.hasNext());
1877:•                while (dequeIterator.hasNext()) {
1878:                         assertEquals(dequeIterator.next(), containedValues.next());
1879:                 }
1880:                 assertTrue(containedValues.hasNext());
1881:•                while (listIterator.hasNext()) {
1882:                         assertEquals(listIterator.next(), containedValues.next());
1883:                 }
1884:                 assertFalse(containedValues.hasNext());
1885:         }
1886:
1887:         /**
1888:          * Tests the behavior of {@link CircularArrayDeque#listIterator(int)} with random elements.
1889:          */
1890:         @Test
1891:         public void testListIteratorStartAt() {
1892:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1893:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
1894:                                 new Object() };
1895:
1896:                 try {
1897:                         deque.listIterator(-1);
1898:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1899:                 } catch (IndexOutOfBoundsException e) {
1900:                         // expected
1901:                 }
1902:                 try {
1903:                         deque.listIterator(deque.size() + 1);
1904:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1905:                 } catch (IndexOutOfBoundsException e) {
1906:                         // expected
1907:                 }
1908:
1909:•                for (Object o : testObjects) {
1910:                         deque.add(o);
1911:                 }
1912:                 try {
1913:                         deque.listIterator(-1);
1914:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1915:                 } catch (IndexOutOfBoundsException e) {
1916:                         // expected
1917:                 }
1918:
1919:                 ListIterator<Object> iterator = deque.listIterator(0);
1920:                 assertFalse(iterator.hasPrevious());
1921:•                for (Object o : testObjects) {
1922:                         assertTrue(iterator.hasNext());
1923:                         assertEquals(o, iterator.next());
1924:                 }
1925:                 assertFalse(iterator.hasNext());
1926:•                for (int i = testObjects.length - 1; i >= 0; i--) {
1927:                         assertTrue(iterator.hasPrevious());
1928:                         assertEquals(testObjects[i], iterator.previous());
1929:                 }
1930:                 assertFalse(iterator.hasPrevious());
1931:
1932:                 iterator = deque.listIterator(deque.size());
1933:                 assertFalse(iterator.hasNext());
1934:•                for (int i = testObjects.length - 1; i >= 0; i--) {
1935:                         assertTrue(iterator.hasPrevious());
1936:                         assertEquals(testObjects[i], iterator.previous());
1937:                 }
1938:                 assertFalse(iterator.hasPrevious());
1939:•                for (Object o : testObjects) {
1940:                         assertTrue(iterator.hasNext());
1941:                         assertEquals(o, iterator.next());
1942:                 }
1943:                 assertFalse(iterator.hasNext());
1944:
1945:                 try {
1946:                         deque.listIterator(deque.size() + 1);
1947:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
1948:                 } catch (IndexOutOfBoundsException e) {
1949:                         // expected
1950:                 }
1951:         }
1952:
1953:         /**
1954:          * Tests the behavior of {@link CircularArrayDeque#offer(Object) with random elements.
1955:          */
1956:         @Test
1957:         public void testOffer() {
1958:                 Integer integer1 = -1;
1959:                 Integer integer2 = -2;
1960:                 String string1 = "a";
1961:                 String string2 = "b";
1962:                 Object object1 = new Object();
1963:                 Object object2 = new Object();
1964:
1965:                 Deque<Object> deque = new CircularArrayDeque<Object>();
1966:
1967:                 deque.offer(integer1);
1968:                 assertSame(1, deque.size());
1969:                 assertEquals(integer1, deque.getFirst());
1970:                 assertEquals(integer1, deque.getLast());
1971:                 assertEquals(integer1, deque.peek());
1972:
1973:                 deque.offer(integer2);
1974:                 assertSame(2, deque.size());
1975:                 assertEquals(integer1, deque.getFirst());
1976:                 assertEquals(integer1, deque.peek());
1977:                 assertEquals(integer2, deque.getLast());
1978:
1979:                 deque.offer(string1);
1980:                 assertSame(3, deque.size());
1981:                 assertEquals(integer1, deque.getFirst());
1982:                 assertEquals(integer1, deque.peek());
1983:                 assertEquals(string1, deque.getLast());
1984:
1985:                 deque.offer(string2);
1986:                 assertSame(4, deque.size());
1987:                 assertEquals(integer1, deque.getFirst());
1988:                 assertEquals(integer1, deque.peek());
1989:                 assertEquals(string2, deque.getLast());
1990:
1991:                 deque.offer(object1);
1992:                 assertSame(5, deque.size());
1993:                 assertEquals(integer1, deque.getFirst());
1994:                 assertEquals(integer1, deque.peek());
1995:                 assertEquals(object1, deque.getLast());
1996:
1997:                 deque.offer(object2);
1998:                 assertSame(6, deque.size());
1999:                 assertEquals(integer1, deque.getFirst());
2000:                 assertEquals(integer1, deque.peek());
2001:                 assertEquals(object2, deque.getLast());
2002:
2003:                 deque.offer(null);
2004:                 assertSame(7, deque.size());
2005:                 assertEquals(integer1, deque.getFirst());
2006:                 assertEquals(integer1, deque.peek());
2007:                 assertSame(null, deque.getLast());
2008:
2009:                 deque.pop();
2010:                 assertSame(6, deque.size());
2011:                 assertEquals(integer1, deque.getFirst());
2012:                 assertEquals(integer1, deque.peek());
2013:                 assertEquals(object2, deque.getLast());
2014:
2015:                 deque.offer(null);
2016:                 assertSame(7, deque.size());
2017:                 assertEquals(integer1, deque.getFirst());
2018:                 assertEquals(integer1, deque.peek());
2019:                 assertSame(null, deque.getLast());
2020:
2021:                 // Ensure we go above capacity
2022:•                for (int i = 0; i < 100; i++) {
2023:                         String rand = getRandomString();
2024:•                        while (deque.contains(rand)) {
2025:                                 rand = getRandomString();
2026:                         }
2027:                         deque.offer(rand);
2028:                         assertSame(7 + i + 1, deque.size());
2029:                         assertEquals(integer1, deque.getFirst());
2030:                         assertEquals(integer1, deque.peek());
2031:                         assertSame(rand, deque.getLast());
2032:                 }
2033:         }
2034:
2035:         /**
2036:          * Tests the behavior of {@link CircularArrayDeque#offerAll(Collection)} with random elements.
2037:          */
2038:         @Test
2039:         public void testOfferAll() {
2040:                 Collection<Object> emptyCollection = Collections.emptyList();
2041:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
2042:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
2043:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
2044:
2045:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2046:
2047:                 deque.offerAll(listInt10);
2048:                 assertEquals(listInt10.size(), deque.size());
2049:                 assertTrue(deque.containsAll(listInt10));
2050:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
2051:
2052:                 deque.offerAll(emptyCollection);
2053:                 assertEquals(listInt10.size(), deque.size());
2054:                 assertTrue(deque.containsAll(listInt10));
2055:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
2056:
2057:                 deque.offerAll(setString20);
2058:                 assertEquals(listInt10.size() + setString20.size(), deque.size());
2059:                 assertTrue(deque.containsAll(listInt10));
2060:                 assertTrue(deque.containsAll(setString20));
2061:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
2062:
2063:                 deque.offerAll(dequeString40);
2064:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
2065:                 assertTrue(deque.containsAll(listInt10));
2066:                 assertTrue(deque.containsAll(setString20));
2067:                 assertTrue(deque.containsAll(dequeString40));
2068:                 int expectedCapacity = getNextPowerOfTwo(deque.size());
2069:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2070:
2071:                 for (@SuppressWarnings("unused")
2072:•                Integer val : listInt10) {
2073:                         deque.removeFirst();
2074:                 }
2075:                 assertEquals(setString20.size() + dequeString40.size(), deque.size());
2076:                 assertFalse(deque.containsAll(listInt10));
2077:                 assertTrue(deque.containsAll(setString20));
2078:                 assertTrue(deque.containsAll(dequeString40));
2079:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2080:
2081:                 deque.offerAll(listInt10);
2082:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
2083:                 assertTrue(deque.containsAll(listInt10));
2084:                 assertTrue(deque.containsAll(setString20));
2085:                 assertTrue(deque.containsAll(dequeString40));
2086:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
2087:
2088:                 deque.offerAll(emptyCollection);
2089:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
2090:                 assertTrue(deque.containsAll(listInt10));
2091:                 assertTrue(deque.containsAll(setString20));
2092:                 assertTrue(deque.containsAll(dequeString40));
2093:                 assertEquals(getNextPowerOfTwo(deque.size()), getInternalCapacity(deque));
2094:         }
2095:
2096:         /**
2097:          * Tests the behavior of {@link CircularArrayDeque#offerFirst(Object)} with random elements.
2098:          */
2099:         @Test
2100:         public void testOfferFirst() {
2101:                 Integer integer1 = -1;
2102:                 Integer integer2 = -2;
2103:                 String string1 = "a";
2104:                 String string2 = "b";
2105:                 Object object1 = new Object();
2106:                 Object object2 = new Object();
2107:
2108:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2109:
2110:                 deque.offerFirst(integer1);
2111:                 assertSame(1, deque.size());
2112:                 assertEquals(integer1, deque.getFirst());
2113:                 assertEquals(integer1, deque.peek());
2114:                 assertEquals(integer1, deque.getLast());
2115:
2116:                 deque.offerFirst(integer2);
2117:                 assertSame(2, deque.size());
2118:                 assertEquals(integer2, deque.getFirst());
2119:                 assertEquals(integer2, deque.peek());
2120:                 assertEquals(integer1, deque.getLast());
2121:
2122:                 deque.offerFirst(string1);
2123:                 assertSame(3, deque.size());
2124:                 assertEquals(string1, deque.getFirst());
2125:                 assertEquals(string1, deque.peek());
2126:                 assertEquals(integer1, deque.getLast());
2127:
2128:                 deque.offerFirst(string2);
2129:                 assertSame(4, deque.size());
2130:                 assertEquals(string2, deque.getFirst());
2131:                 assertEquals(string2, deque.peek());
2132:                 assertEquals(integer1, deque.getLast());
2133:
2134:                 deque.offerFirst(object1);
2135:                 assertSame(5, deque.size());
2136:                 assertEquals(object1, deque.getFirst());
2137:                 assertEquals(object1, deque.peek());
2138:                 assertEquals(integer1, deque.getLast());
2139:
2140:                 deque.offerFirst(object2);
2141:                 assertSame(6, deque.size());
2142:                 assertEquals(object2, deque.getFirst());
2143:                 assertEquals(object2, deque.peek());
2144:                 assertEquals(integer1, deque.getLast());
2145:
2146:                 deque.offerFirst(null);
2147:                 assertSame(7, deque.size());
2148:                 assertSame(null, deque.getFirst());
2149:                 assertSame(null, deque.peek());
2150:                 assertEquals(integer1, deque.getLast());
2151:
2152:                 deque.removeFirst();
2153:                 assertSame(6, deque.size());
2154:                 assertEquals(object2, deque.getFirst());
2155:                 assertEquals(object2, deque.peek());
2156:                 assertEquals(integer1, deque.getLast());
2157:
2158:                 deque.offerFirst(null);
2159:                 assertSame(7, deque.size());
2160:                 assertSame(null, deque.getFirst());
2161:                 assertSame(null, deque.peek());
2162:                 assertEquals(integer1, deque.getLast());
2163:
2164:                 // Ensure we go above capacity
2165:•                for (int i = 0; i < 100; i++) {
2166:                         String rand = getRandomString();
2167:•                        while (deque.contains(rand)) {
2168:                                 rand = getRandomString();
2169:                         }
2170:                         deque.offerFirst(rand);
2171:                         assertSame(7 + i + 1, deque.size());
2172:                         assertEquals(rand, deque.getFirst());
2173:                         assertEquals(rand, deque.peek());
2174:                         assertSame(integer1, deque.getLast());
2175:                 }
2176:         }
2177:
2178:         /**
2179:          * Tests the behavior of {@link CircularArrayDeque#offerLast(Object)} with random elements.
2180:          */
2181:         @Test
2182:         public void testOfferLast() {
2183:                 Integer integer1 = -1;
2184:                 Integer integer2 = -2;
2185:                 String string1 = "a";
2186:                 String string2 = "b";
2187:                 Object object1 = new Object();
2188:                 Object object2 = new Object();
2189:
2190:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2191:
2192:                 deque.offerLast(integer1);
2193:                 assertSame(1, deque.size());
2194:                 assertEquals(integer1, deque.getFirst());
2195:                 assertEquals(integer1, deque.getLast());
2196:                 assertEquals(integer1, deque.peek());
2197:
2198:                 deque.offerLast(integer2);
2199:                 assertSame(2, deque.size());
2200:                 assertEquals(integer1, deque.getFirst());
2201:                 assertEquals(integer1, deque.peek());
2202:                 assertEquals(integer2, deque.getLast());
2203:
2204:                 deque.offerLast(string1);
2205:                 assertSame(3, deque.size());
2206:                 assertEquals(integer1, deque.getFirst());
2207:                 assertEquals(integer1, deque.peek());
2208:                 assertEquals(string1, deque.getLast());
2209:
2210:                 deque.offerLast(string2);
2211:                 assertSame(4, deque.size());
2212:                 assertEquals(integer1, deque.getFirst());
2213:                 assertEquals(integer1, deque.peek());
2214:                 assertEquals(string2, deque.getLast());
2215:
2216:                 deque.offerLast(object1);
2217:                 assertSame(5, deque.size());
2218:                 assertEquals(integer1, deque.getFirst());
2219:                 assertEquals(integer1, deque.peek());
2220:                 assertEquals(object1, deque.getLast());
2221:
2222:                 deque.offerLast(object2);
2223:                 assertSame(6, deque.size());
2224:                 assertEquals(integer1, deque.getFirst());
2225:                 assertEquals(integer1, deque.peek());
2226:                 assertEquals(object2, deque.getLast());
2227:
2228:                 deque.offerLast(null);
2229:                 assertSame(7, deque.size());
2230:                 assertEquals(integer1, deque.getFirst());
2231:                 assertEquals(integer1, deque.peek());
2232:                 assertSame(null, deque.getLast());
2233:
2234:                 deque.pop();
2235:                 assertSame(6, deque.size());
2236:                 assertEquals(integer1, deque.getFirst());
2237:                 assertEquals(integer1, deque.peek());
2238:                 assertEquals(object2, deque.getLast());
2239:
2240:                 deque.offerLast(null);
2241:                 assertSame(7, deque.size());
2242:                 assertEquals(integer1, deque.getFirst());
2243:                 assertEquals(integer1, deque.peek());
2244:                 assertSame(null, deque.getLast());
2245:
2246:                 // Ensure we go above capacity
2247:•                for (int i = 0; i < 100; i++) {
2248:                         String rand = getRandomString();
2249:•                        while (deque.contains(rand)) {
2250:                                 rand = getRandomString();
2251:                         }
2252:                         deque.offerLast(rand);
2253:                         assertSame(7 + i + 1, deque.size());
2254:                         assertEquals(integer1, deque.getFirst());
2255:                         assertEquals(integer1, deque.peek());
2256:                         assertSame(rand, deque.getLast());
2257:                 }
2258:         }
2259:
2260:         /**
2261:          * Tests the behavior of {@link CircularArrayDeque#toArray(Object[])} with random elements.
2262:          */
2263:         @Test
2264:         public void testParameterizedToArray() {
2265:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2266:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2267:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2268:
2269:                 Object[] array = deque.toArray(new Object[0]);
2270:                 assertSame(0, array.length);
2271:                 array = deque.toArray(new Object[21]);
2272:                 assertSame(21, array.length);
2273:•                for (Object o : array) {
2274:                         assertNull(o);
2275:                 }
2276:
2277:                 deque.addAll(objectsLast);
2278:                 array = deque.toArray(new Object[0]);
2279:                 assertSame(deque.size(), array.length);
2280:                 Iterator<Object> dequeIterator = deque.iterator();
2281:•                for (int i = 0; i < deque.size(); i++) {
2282:                         assertEquals(dequeIterator.next(), array[i]);
2283:                 }
2284:                 array = new String[21];
2285:                 deque.toArray(array);
2286:                 assertSame(21, array.length);
2287:                 dequeIterator = deque.iterator();
2288:•                for (int i = 0; i < deque.size(); i++) {
2289:                         assertEquals(dequeIterator.next(), array[i]);
2290:                 }
2291:                 deque.clear();
2292:
2293:                 deque.addAll(objectsLast);
2294:•                for (Object o : objectsFirst) {
2295:                         deque.addFirst(o);
2296:                 }
2297:                 array = deque.toArray(new Object[0]);
2298:                 assertSame(deque.size(), array.length);
2299:                 dequeIterator = deque.iterator();
2300:•                for (int i = 0; i < deque.size(); i++) {
2301:                         assertEquals(dequeIterator.next(), array[i]);
2302:                 }
2303:                 array = new String[41];
2304:                 deque.toArray(array);
2305:                 assertSame(41, array.length);
2306:                 dequeIterator = deque.iterator();
2307:•                for (int i = 0; i < deque.size(); i++) {
2308:                         assertEquals(dequeIterator.next(), array[i]);
2309:                 }
2310:
2311:                 deque.clear();
2312:                 assertEquals(getNextPowerOfTwo(40), getInternalCapacity(deque));
2313:                 array = deque.toArray(new Object[0]);
2314:                 assertSame(0, array.length);
2315:                 array = deque.toArray(new Object[41]);
2316:                 assertSame(41, array.length);
2317:•                for (Object o : array) {
2318:                         assertNull(o);
2319:                 }
2320:         }
2321:
2322:         /**
2323:          * Tests the behavior of {@link CircularArrayDeque#peek()} with random elements.
2324:          */
2325:         @Test
2326:         public void testPeek() {
2327:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2328:
2329:                 assertNull(deque.peek());
2330:
2331:                 deque.offer(null);
2332:                 assertSame(null, deque.peek());
2333:                 List<Object> lastAdded = new ArrayList<Object>();
2334:•                for (int i = 0; i < 20; i++) {
2335:                         String rand = getRandomString();
2336:•                        while (deque.contains(rand)) {
2337:                                 rand = getRandomString();
2338:                         }
2339:                         deque.offer(rand);
2340:                         assertSame(null, deque.peek());
2341:                 }
2342:•                for (int i = 0; i < 20; i++) {
2343:                         String rand = getRandomString();
2344:•                        while (deque.contains(rand)) {
2345:                                 rand = getRandomString();
2346:                         }
2347:                         deque.addFirst(rand);
2348:                         lastAdded.add(rand);
2349:                         assertEquals(rand, deque.peek());
2350:                 }
2351:•                for (int i = 0; i < 20; i++) {
2352:                         assertEquals(lastAdded.get(lastAdded.size() - i - 1), deque.peek());
2353:                         deque.removeFirst();
2354:                 }
2355:                 assertSame(null, deque.peek());
2356:
2357:                 deque.addAll(lastAdded);
2358:                 deque.clear();
2359:
2360:                 assertNull(deque.peek());
2361:         }
2362:
2363:         /**
2364:          * Tests the behavior of {@link CircularArrayDeque#peekFirst()} with random elements.
2365:          */
2366:         @Test
2367:         public void testPeekFirst() {
2368:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2369:
2370:                 try {
2371:                         deque.peekFirst();
2372:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
2373:                 } catch (NoSuchElementException e) {
2374:                         // expected
2375:                 }
2376:
2377:                 deque.offer(null);
2378:                 assertSame(null, deque.peekFirst());
2379:•                for (int i = 0; i < 20; i++) {
2380:                         String rand = getRandomString();
2381:•                        while (deque.contains(rand)) {
2382:                                 rand = getRandomString();
2383:                         }
2384:                         deque.offer(rand);
2385:                         assertSame(null, deque.peekFirst());
2386:                 }
2387:                 List<Object> lastAdded = new ArrayList<Object>();
2388:•                for (int i = 0; i < 20; i++) {
2389:                         String rand = getRandomString();
2390:•                        while (deque.contains(rand)) {
2391:                                 rand = getRandomString();
2392:                         }
2393:                         deque.addFirst(rand);
2394:                         lastAdded.add(rand);
2395:                         assertEquals(rand, deque.peekFirst());
2396:                 }
2397:•                for (int i = 0; i < 20; i++) {
2398:                         deque.removeFirst();
2399:•                        if (i < 19) {
2400:                                 assertEquals(lastAdded.get(lastAdded.size() - i - 2), deque.peekFirst());
2401:                         } else {
2402:                                 assertSame(null, deque.peekFirst());
2403:                         }
2404:                 }
2405:
2406:                 deque.clear();
2407:                 try {
2408:                         deque.peekFirst();
2409:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
2410:                 } catch (NoSuchElementException e) {
2411:                         // expected
2412:                 }
2413:         }
2414:
2415:         /**
2416:          * Tests the behavior of {@link CircularArrayDeque#peekLast()} with random elements.
2417:          */
2418:         @Test
2419:         public void testPeekLast() {
2420:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2421:
2422:                 try {
2423:                         deque.peekLast();
2424:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
2425:                 } catch (NoSuchElementException e) {
2426:                         // expected
2427:                 }
2428:
2429:                 deque.offer(null);
2430:                 assertSame(null, deque.peekLast());
2431:                 List<Object> lastAdded = new ArrayList<Object>();
2432:•                for (int i = 0; i < 20; i++) {
2433:                         String rand = getRandomString();
2434:•                        while (deque.contains(rand)) {
2435:                                 rand = getRandomString();
2436:                         }
2437:                         deque.offer(rand);
2438:                         lastAdded.add(rand);
2439:                         assertEquals(rand, deque.peekLast());
2440:                 }
2441:•                for (int i = 0; i < 20; i++) {
2442:                         String rand = getRandomString();
2443:•                        while (deque.contains(rand)) {
2444:                                 rand = getRandomString();
2445:                         }
2446:                         deque.addFirst(rand);
2447:                         assertEquals(lastAdded.get(lastAdded.size() - 1), deque.peekLast());
2448:                 }
2449:•                for (int i = 0; i < 20; i++) {
2450:                         deque.removeLast();
2451:•                        if (i < 19) {
2452:                                 assertEquals(lastAdded.get(lastAdded.size() - i - 2), deque.peekLast());
2453:                         } else {
2454:                                 assertSame(null, deque.peekLast());
2455:                         }
2456:                 }
2457:
2458:                 deque.clear();
2459:                 try {
2460:                         deque.peekLast();
2461:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$
2462:                 } catch (NoSuchElementException e) {
2463:                         // expected
2464:                 }
2465:         }
2466:
2467:         /**
2468:          * Tests the behavior of {@link CircularArrayDeque#poll()} with random elements.
2469:          */
2470:         @Test
2471:         public void testPoll() {
2472:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2473:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2474:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2475:
2476:                 assertFalse(deque.containsAll(objectsFirst));
2477:                 assertFalse(deque.containsAll(objectsLast));
2478:
2479:                 assertNull(deque.poll());
2480:
2481:•                for (Object o : objectsLast) {
2482:                         deque.offer(o);
2483:                 }
2484:•                for (Object o : objectsFirst) {
2485:                         deque.addFirst(o);
2486:                 }
2487:                 assertTrue(deque.containsAll(objectsFirst));
2488:                 assertTrue(deque.containsAll(objectsLast));
2489:
2490:•                for (int i = objectsFirst.size() - 1; i >= 0; i--) {
2491:                         assertEquals(objectsFirst.get(i), deque.poll());
2492:                 }
2493:•                for (Object o : objectsLast) {
2494:                         assertEquals(o, deque.poll());
2495:                 }
2496:
2497:                 assertNull(deque.poll());
2498:
2499:                 deque.addAll(objectsFirst);
2500:                 deque.addAll(objectsLast);
2501:                 deque.clear();
2502:
2503:                 assertNull(deque.poll());
2504:         }
2505:
2506:         /**
2507:          * Tests the behavior of {@link CircularArrayDeque#pop()} with random elements.
2508:          */
2509:         @Test
2510:         public void testPop() {
2511:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2512:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2513:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2514:
2515:                 assertFalse(deque.containsAll(objectsFirst));
2516:                 assertFalse(deque.containsAll(objectsLast));
2517:
2518:                 try {
2519:                         deque.pop();
2520:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2521:                 } catch (NoSuchElementException e) {
2522:                         // expected
2523:                 }
2524:
2525:•                for (Object o : objectsLast) {
2526:                         deque.offer(o);
2527:                 }
2528:•                for (Object o : objectsFirst) {
2529:                         deque.addFirst(o);
2530:                 }
2531:                 assertTrue(deque.containsAll(objectsFirst));
2532:                 assertTrue(deque.containsAll(objectsLast));
2533:
2534:•                for (int i = objectsLast.size() - 1; i >= 0; i--) {
2535:                         assertEquals(objectsLast.get(i), deque.pop());
2536:                 }
2537:•                for (Object o : objectsFirst) {
2538:                         assertEquals(o, deque.pop());
2539:                 }
2540:
2541:                 try {
2542:                         deque.pop();
2543:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2544:                 } catch (NoSuchElementException e) {
2545:                         // expected
2546:                 }
2547:
2548:                 deque.addAll(objectsFirst);
2549:                 deque.addAll(objectsLast);
2550:                 deque.clear();
2551:                 try {
2552:                         deque.pop();
2553:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2554:                 } catch (NoSuchElementException e) {
2555:                         // expected
2556:                 }
2557:         }
2558:
2559:         /**
2560:          * Tests the behavior of {@link CircularArrayDeque#remove(Object)} with random elements.
2561:          */
2562:         @Test
2563:         public void testRemove() {
2564:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2565:                 List<String> objects = randomStringListNotIn(20, Collections.emptySet());
2566:
2567:                 assertFalse(deque.containsAll(objects));
2568:
2569:•                for (Object o : objects) {
2570:                         boolean removed = deque.remove(o);
2571:                         assertFalse(removed);
2572:                         assertFalse(deque.contains(o));
2573:                 }
2574:
2575:•                for (Object o : objects) {
2576:                         deque.offer(o);
2577:                 }
2578:                 assertTrue(deque.containsAll(objects));
2579:
2580:•                for (Object o : objects) {
2581:                         assertTrue(deque.contains(o));
2582:                         boolean removed = deque.remove(o);
2583:                         assertTrue(removed);
2584:                         assertFalse(deque.contains(o));
2585:                 }
2586:
2587:                 assertFalse(deque.containsAll(objects));
2588:
2589:•                for (Object o : objects) {
2590:                         boolean removed = deque.remove(o);
2591:                         assertFalse(removed);
2592:                         assertFalse(deque.contains(o));
2593:                 }
2594:         }
2595:
2596:         /**
2597:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with random elements.
2598:          */
2599:         @Test
2600:         public void testRemoveAll() {
2601:                 Collection<Object> emptyCollection = Collections.emptyList();
2602:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
2603:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
2604:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
2605:
2606:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2607:
2608:                 deque.addAll(listInt10);
2609:                 deque.addAll(emptyCollection);
2610:                 deque.addAll(setString20);
2611:                 deque.addAll(dequeString40);
2612:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
2613:                 assertTrue(deque.containsAll(listInt10));
2614:                 assertTrue(deque.containsAll(setString20));
2615:                 assertTrue(deque.containsAll(dequeString40));
2616:                 int expectedCapacity = getNextPowerOfTwo(deque.size());
2617:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2618:
2619:                 boolean modified = deque.removeAll(listInt10);
2620:                 assertTrue(modified);
2621:                 assertEquals(setString20.size() + dequeString40.size(), deque.size());
2622:                 assertFalse(deque.containsAll(listInt10));
2623:                 assertTrue(deque.containsAll(setString20));
2624:                 assertTrue(deque.containsAll(dequeString40));
2625:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2626:
2627:                 modified = deque.removeAll(emptyCollection);
2628:                 assertFalse(modified);
2629:                 assertEquals(setString20.size() + dequeString40.size(), deque.size());
2630:                 assertFalse(deque.containsAll(listInt10));
2631:                 assertTrue(deque.containsAll(setString20));
2632:                 assertTrue(deque.containsAll(dequeString40));
2633:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2634:
2635:                 deque.addAll(listInt10);
2636:                 assertEquals(listInt10.size() + setString20.size() + dequeString40.size(), deque.size());
2637:                 assertTrue(deque.containsAll(listInt10));
2638:                 assertTrue(deque.containsAll(setString20));
2639:                 assertTrue(deque.containsAll(dequeString40));
2640:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2641:
2642:                 modified = deque.removeAll(setString20);
2643:                 assertTrue(modified);
2644:                 assertEquals(listInt10.size() + dequeString40.size(), deque.size());
2645:                 assertTrue(deque.containsAll(listInt10));
2646:                 assertFalse(deque.containsAll(setString20));
2647:                 assertTrue(deque.containsAll(dequeString40));
2648:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2649:
2650:                 modified = deque.removeAll(dequeString40);
2651:                 assertTrue(modified);
2652:                 assertEquals(listInt10.size(), deque.size());
2653:                 assertTrue(deque.containsAll(listInt10));
2654:                 assertFalse(deque.containsAll(setString20));
2655:                 assertFalse(deque.containsAll(dequeString40));
2656:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2657:
2658:                 modified = deque.removeAll(listInt10);
2659:                 assertTrue(modified);
2660:                 assertEquals(0, deque.size());
2661:                 assertFalse(deque.containsAll(listInt10));
2662:                 assertFalse(deque.containsAll(setString20));
2663:                 assertFalse(deque.containsAll(dequeString40));
2664:                 assertEquals(expectedCapacity, getInternalCapacity(deque));
2665:
2666:                 assertTrue(deque.isEmpty());
2667:
2668:                 modified = deque.removeAll(listInt10);
2669:                 assertFalse(modified);
2670:                 modified = deque.removeAll(setString20);
2671:                 assertFalse(modified);
2672:                 modified = deque.removeAll(dequeString40);
2673:                 assertFalse(modified);
2674:
2675:                 deque.add(null);
2676:                 assertTrue(deque.contains(null));
2677:                 assertFalse(deque.isEmpty());
2678:                 deque.removeAll(Collections.singleton(null));
2679:                 assertFalse(deque.contains(null));
2680:                 assertTrue(deque.isEmpty());
2681:         }
2682:
2683:         /**
2684:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with random elements.
2685:          */
2686:         @Test
2687:         public void testRemoveAllBothRotate() {
2688:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
2689:                                 new Object() };
2690:
2691:•                for (int i = 0; i < testObjects.length; i++) {
2692:                         List<Object> testCollection = new ArrayList<Object>();
2693:                         testCollection.add(testObjects[i]);
2694:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
2695:                         internalTestRemoveAllBothRotate(testCollection);
2696:                 }
2697:         }
2698:
2699:         /**
2700:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with random elements.
2701:          */
2702:         @Test
2703:         public void testRemoveAllLeftRotate() {
2704:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
2705:                                 new Object() };
2706:
2707:•                for (int i = 0; i < testObjects.length; i++) {
2708:                         List<Object> testCollection = new ArrayList<Object>();
2709:                         testCollection.add(testObjects[i]);
2710:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
2711:                         internalTestRemoveAllLeftRotate(testCollection);
2712:                 }
2713:         }
2714:
2715:         /**
2716:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with random elements.
2717:          */
2718:         @Test
2719:         public void testRemoveAllRightRotate() {
2720:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
2721:                                 new Object() };
2722:
2723:•                for (int i = 0; i < testObjects.length; i++) {
2724:                         List<Object> testCollection = new ArrayList<Object>();
2725:                         testCollection.add(testObjects[i]);
2726:                         testCollection.add(testObjects[testObjects.length - 1 - i]);
2727:                         internalTestRemoveAllRightRotate(testCollection);
2728:                 }
2729:         }
2730:
2731:         /**
2732:          * Tests the behavior of {@link CircularArrayDeque#removeFirst()} with random elements.
2733:          */
2734:         @Test
2735:         public void testRemoveFirst() {
2736:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2737:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2738:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2739:
2740:                 assertFalse(deque.containsAll(objectsFirst));
2741:                 assertFalse(deque.containsAll(objectsLast));
2742:
2743:                 try {
2744:                         deque.removeFirst();
2745:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2746:                 } catch (NoSuchElementException e) {
2747:                         // expected
2748:                 }
2749:
2750:•                for (Object o : objectsLast) {
2751:                         deque.offer(o);
2752:                 }
2753:•                for (Object o : objectsFirst) {
2754:                         deque.addFirst(o);
2755:                 }
2756:                 assertTrue(deque.containsAll(objectsFirst));
2757:                 assertTrue(deque.containsAll(objectsLast));
2758:
2759:•                for (int i = objectsFirst.size() - 1; i >= 0; i--) {
2760:                         assertEquals(objectsFirst.get(i), deque.removeFirst());
2761:                 }
2762:•                for (Object o : objectsLast) {
2763:                         assertEquals(o, deque.removeFirst());
2764:                 }
2765:
2766:                 try {
2767:                         deque.removeFirst();
2768:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2769:                 } catch (NoSuchElementException e) {
2770:                         // expected
2771:                 }
2772:
2773:                 deque.addAll(objectsFirst);
2774:                 deque.addAll(objectsLast);
2775:                 deque.clear();
2776:                 try {
2777:                         deque.removeFirst();
2778:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2779:                 } catch (NoSuchElementException e) {
2780:                         // expected
2781:                 }
2782:         }
2783:
2784:         /**
2785:          * Tests the behavior of {@link CircularArrayDeque#removeLast()} with random elements.
2786:          */
2787:         @Test
2788:         public void testRemoveLast() {
2789:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2790:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2791:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2792:
2793:                 assertFalse(deque.containsAll(objectsFirst));
2794:                 assertFalse(deque.containsAll(objectsLast));
2795:
2796:                 try {
2797:                         deque.removeLast();
2798:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2799:                 } catch (NoSuchElementException e) {
2800:                         // expected
2801:                 }
2802:
2803:•                for (Object o : objectsLast) {
2804:                         deque.offer(o);
2805:                 }
2806:•                for (Object o : objectsFirst) {
2807:                         deque.addFirst(o);
2808:                 }
2809:                 assertTrue(deque.containsAll(objectsFirst));
2810:                 assertTrue(deque.containsAll(objectsLast));
2811:
2812:•                for (int i = objectsLast.size() - 1; i >= 0; i--) {
2813:                         assertEquals(objectsLast.get(i), deque.removeLast());
2814:                 }
2815:•                for (Object o : objectsFirst) {
2816:                         assertEquals(o, deque.removeLast());
2817:                 }
2818:
2819:                 try {
2820:                         deque.removeLast();
2821:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2822:                 } catch (NoSuchElementException e) {
2823:                         // expected
2824:                 }
2825:
2826:                 deque.addAll(objectsFirst);
2827:                 deque.addAll(objectsLast);
2828:                 deque.clear();
2829:                 try {
2830:                         deque.removeLast();
2831:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2832:                 } catch (NoSuchElementException e) {
2833:                         // expected
2834:                 }
2835:         }
2836:
2837:         /**
2838:          * Tests the behavior of {@link CircularArrayDeque#remove(Object)} with random elements.
2839:          */
2840:         @Test
2841:         public void testRemoveLeftRotate() {
2842:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
2843:                                 new Object() };
2844:•                for (int i = 0; i < testObjects.length; i++) {
2845:                         internalTestRemoveLeftRotate(testObjects[i]);
2846:                 }
2847:         }
2848:
2849:         /**
2850:          * Tests the behavior of {@link CircularArrayDeque#remove()} with random elements.
2851:          */
2852:         @Test
2853:         public void testRemoveQueue() {
2854:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2855:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
2856:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
2857:
2858:                 assertFalse(deque.containsAll(objectsFirst));
2859:                 assertFalse(deque.containsAll(objectsLast));
2860:
2861:                 try {
2862:                         deque.remove();
2863:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2864:                 } catch (NoSuchElementException e) {
2865:                         // expected
2866:                 }
2867:
2868:•                for (Object o : objectsLast) {
2869:                         deque.offer(o);
2870:                 }
2871:•                for (Object o : objectsFirst) {
2872:                         deque.addFirst(o);
2873:                 }
2874:                 assertTrue(deque.containsAll(objectsFirst));
2875:                 assertTrue(deque.containsAll(objectsLast));
2876:
2877:•                for (int i = objectsFirst.size() - 1; i >= 0; i--) {
2878:                         assertEquals(objectsFirst.get(i), deque.remove());
2879:                 }
2880:•                for (Object o : objectsLast) {
2881:                         assertEquals(o, deque.remove());
2882:                 }
2883:
2884:                 try {
2885:                         deque.remove();
2886:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2887:                 } catch (NoSuchElementException e) {
2888:                         // expected
2889:                 }
2890:
2891:                 deque.addAll(objectsFirst);
2892:                 deque.addAll(objectsLast);
2893:                 deque.clear();
2894:                 try {
2895:                         deque.remove();
2896:                         fail("Expected NoSuchElementException hasn't been thrown"); //$NON-NLS-1$                        
2897:                 } catch (NoSuchElementException e) {
2898:                         // expected
2899:                 }
2900:         }
2901:
2902:         /**
2903:          * Tests the behavior of {@link CircularArrayDeque#remove(Object)} with random elements.
2904:          */
2905:         @Test
2906:         public void testRemoveRightRotate() {
2907:                 Object[] testObjects = new Object[] {"abcd", "", "*", "?", "\n", '\'', null, 4, 4.3, 5L, 4.3d, //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$
2908:                                 new Object() };
2909:•                for (int i = 0; i < testObjects.length; i++) {
2910:                         internalTestRemoveRightRotate(testObjects[i]);
2911:                 }
2912:         }
2913:
2914:         /**
2915:          * Tests the behavior of {@link CircularArrayDeque#retainAll(Collection)} with random elements.
2916:          */
2917:         @Test
2918:         public void testRetainAll() {
2919:                 Collection<Object> emptyCollection = Collections.emptyList();
2920:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
2921:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
2922:                 Collection<String> dequeString40 = randomStringDequeNotIn(40, setString20);
2923:
2924:                 Deque<Object> deque = new CircularArrayDeque<Object>();
2925:                 deque.addAll(listInt10);
2926:                 deque.addAll(emptyCollection);
2927:                 deque.addAll(setString20);
2928:                 deque.addAll(dequeString40);
2929:
2930:                 boolean modified = deque.retainAll(dequeString40);
2931:                 assertTrue(modified);
2932:                 assertSame(dequeString40.size(), deque.size());
2933:•                for (Integer integer : listInt10) {
2934:                         assertFalse(deque.contains(integer));
2935:                 }
2936:•                for (String string : setString20) {
2937:                         assertFalse(deque.contains(string));
2938:                 }
2939:•                for (String string : dequeString40) {
2940:                         assertTrue(deque.contains(string));
2941:                 }
2942:
2943:                 deque = new CircularArrayDeque<Object>();
2944:                 deque.addAll(listInt10);
2945:                 deque.addAll(emptyCollection);
2946:                 deque.addAll(setString20);
2947:                 deque.addAll(dequeString40);
2948:
2949:                 modified = deque.retainAll(setString20);
2950:                 assertTrue(modified);
2951:                 assertSame(setString20.size(), deque.size());
2952:•                for (Integer integer : listInt10) {
2953:                         assertFalse(deque.contains(integer));
2954:                 }
2955:•                for (String string : setString20) {
2956:                         assertTrue(deque.contains(string));
2957:                 }
2958:•                for (String string : dequeString40) {
2959:                         assertFalse(deque.contains(string));
2960:                 }
2961:
2962:                 deque = new CircularArrayDeque<Object>();
2963:                 deque.addAll(listInt10);
2964:                 deque.addAll(emptyCollection);
2965:                 deque.addAll(setString20);
2966:                 deque.addAll(dequeString40);
2967:
2968:                 modified = deque.retainAll(listInt10);
2969:                 assertTrue(modified);
2970:                 assertSame(listInt10.size(), deque.size());
2971:•                for (Integer integer : listInt10) {
2972:                         assertTrue(deque.contains(integer));
2973:                 }
2974:•                for (String string : setString20) {
2975:                         assertFalse(deque.contains(string));
2976:                 }
2977:•                for (String string : dequeString40) {
2978:                         assertFalse(deque.contains(string));
2979:                 }
2980:
2981:                 deque = new CircularArrayDeque<Object>();
2982:                 deque.addAll(listInt10);
2983:                 deque.addAll(emptyCollection);
2984:                 deque.addAll(setString20);
2985:                 deque.addAll(dequeString40);
2986:
2987:                 modified = deque.retainAll(emptyCollection);
2988:                 assertTrue(modified);
2989:                 assertSame(0, deque.size());
2990:•                for (Integer integer : listInt10) {
2991:                         assertFalse(deque.contains(integer));
2992:                 }
2993:•                for (String string : setString20) {
2994:                         assertFalse(deque.contains(string));
2995:                 }
2996:•                for (String string : dequeString40) {
2997:                         assertFalse(deque.contains(string));
2998:                 }
2999:
3000:                 deque = new CircularArrayDeque<Object>();
3001:                 modified = deque.retainAll(emptyCollection);
3002:                 assertFalse(modified);
3003:                 assertSame(0, deque.size());
3004:
3005:                 modified = deque.retainAll(listInt10);
3006:                 assertFalse(modified);
3007:                 assertSame(0, deque.size());
3008:
3009:                 modified = deque.retainAll(dequeString40);
3010:                 assertFalse(modified);
3011:                 assertSame(0, deque.size());
3012:         }
3013:
3014:         /**
3015:          * Tests the behavior of {@link CircularArrayDeque#set(int, Object)} with random elements.
3016:          */
3017:         @Test
3018:         public void testSet() {
3019:                 Integer integer1 = -1;
3020:                 Integer integer2 = -2;
3021:                 String string1 = "a";
3022:                 String string2 = "b";
3023:                 Object object1 = new Object();
3024:                 Object object2 = new Object();
3025:
3026:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3027:
3028:                 int[] invalidIndices = new int[] {0, -1, Integer.MIN_VALUE, deque.size() + 1 };
3029:•                for (int i : invalidIndices) {
3030:                         try {
3031:                                 deque.set(i, string2);
3032:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3033:                         } catch (IndexOutOfBoundsException e) {
3034:                                 // expected
3035:                         }
3036:                 }
3037:
3038:                 deque.add(integer1);
3039:                 deque.add(string1);
3040:                 deque.add(object1);
3041:
3042:                 invalidIndices = new int[] {-1, Integer.MIN_VALUE, deque.size() + 1 };
3043:•                for (int i : invalidIndices) {
3044:                         try {
3045:                                 deque.set(i, string2);
3046:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3047:                         } catch (IndexOutOfBoundsException e) {
3048:                                 // expected
3049:                         }
3050:                 }
3051:
3052:                 assertEquals(integer1, deque.set(0, integer2));
3053:                 assertEquals(integer2, deque.get(0));
3054:                 assertFalse(deque.contains(integer1));
3055:                 assertSame(3, deque.size());
3056:
3057:                 assertEquals(string1, deque.set(1, string2));
3058:                 assertEquals(string2, deque.get(1));
3059:                 assertFalse(deque.contains(string1));
3060:                 assertSame(3, deque.size());
3061:
3062:                 assertEquals(object1, deque.set(2, object2));
3063:                 assertEquals(object2, deque.get(2));
3064:                 assertFalse(deque.contains(object1));
3065:                 assertSame(3, deque.size());
3066:
3067:                 assertEquals(string2, deque.set(1, integer2));
3068:                 assertEquals(integer2, deque.get(1));
3069:                 assertFalse(deque.contains(string2));
3070:                 assertSame(3, deque.size());
3071:
3072:                 assertEquals(object2, deque.set(2, integer2));
3073:                 assertEquals(integer2, deque.get(2));
3074:                 assertFalse(deque.contains(object2));
3075:                 assertSame(3, deque.size());
3076:
3077:                 invalidIndices = new int[] {-1, Integer.MIN_VALUE, deque.size() + 1 };
3078:•                for (int i : invalidIndices) {
3079:                         try {
3080:                                 deque.set(i, string2);
3081:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3082:                         } catch (IndexOutOfBoundsException e) {
3083:                                 // expected
3084:                         }
3085:                 }
3086:
3087:                 deque.clear();
3088:
3089:                 invalidIndices = new int[] {0, -1, Integer.MIN_VALUE, deque.size() + 1 };
3090:•                for (int i : invalidIndices) {
3091:                         try {
3092:                                 deque.set(i, string2);
3093:                                 fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3094:                         } catch (IndexOutOfBoundsException e) {
3095:                                 // expected
3096:                         }
3097:                 }
3098:         }
3099:
3100:         /**
3101:          * Tests the behavior of {@link CircularArrayDeque#size()} with random elements.
3102:          */
3103:         @Test
3104:         public void testSize() {
3105:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3106:
3107:                 int size = 0;
3108:                 assertSame(size, deque.size());
3109:
3110:                 deque.offer(null);
3111:                 assertSame(++size, deque.size());
3112:
3113:•                for (int i = 0; i < 100; i++) {
3114:                         String rand = getRandomString();
3115:•                        while (deque.contains(rand)) {
3116:                                 rand = getRandomString();
3117:                         }
3118:                         deque.offer(rand);
3119:                         assertSame(++size, deque.size());
3120:                 }
3121:
3122:•                for (int i = 0; i < 100; i++) {
3123:                         deque.pop();
3124:                         assertSame(--size, deque.size());
3125:                 }
3126:         }
3127:
3128:         /**
3129:          * Tests the behavior of {@link CircularArrayDeque#subList(int, int)} with random elements. As this is
3130:          * fully inherited from AbstractList, we'll only test that the operation is accessible.
3131:          */
3132:         @Test
3133:         public void testSubList() {
3134:                 Collection<Integer> listInt10 = randomIntegerListNotIn(10, Collections.emptySet());
3135:                 Collection<String> setString20 = randomStringSetNotIn(20, Collections.emptySet());
3136:
3137:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3138:
3139:                 List<Object> subList = deque.subList(0, 0);
3140:                 assertEquals(subList, deque);
3141:                 assertTrue(subList.isEmpty());
3142:
3143:                 try {
3144:                         deque.subList(0, 5);
3145:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3146:                 } catch (IndexOutOfBoundsException e) {
3147:                         // Expected
3148:                 }
3149:
3150:                 deque.addAll(listInt10);
3151:                 deque.addAll(setString20);
3152:
3153:                 subList = deque.subList(0, deque.size());
3154:                 assertEquals(subList, deque);
3155:
3156:                 subList = deque.subList(0, listInt10.size());
3157:                 assertSame(listInt10.size(), subList.size());
3158:                 assertTrue(subList.containsAll(listInt10));
3159:
3160:                 subList = deque.subList(0, listInt10.size() + setString20.size());
3161:                 assertSame(listInt10.size() + setString20.size(), subList.size());
3162:                 assertTrue(subList.containsAll(listInt10));
3163:                 assertTrue(subList.containsAll(setString20));
3164:
3165:                 try {
3166:                         deque.subList(-1, 10);
3167:                         fail("Expected IndexOutOfBoundsException hasn't been thrown"); //$NON-NLS-1$
3168:                 } catch (IndexOutOfBoundsException e) {
3169:                         // Expected
3170:                 }
3171:
3172:                 try {
3173:                         deque.subList(5, 0);
3174:                         fail("Expected IllegalArgumentException hasn't been thrown"); //$NON-NLS-1$
3175:                 } catch (IllegalArgumentException e) {
3176:                         // Expected
3177:                 }
3178:
3179:                 subList = deque.subList(5, 5);
3180:                 assertSame(0, subList.size());
3181:                 assertTrue(subList.isEmpty());
3182:         }
3183:
3184:         /**
3185:          * Tests the behavior of {@link CircularArrayDeque#toArray()} with random elements.
3186:          */
3187:         @Test
3188:         public void testToArray() {
3189:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3190:                 List<String> objectsFirst = randomStringListNotIn(20, Collections.emptySet());
3191:                 List<String> objectsLast = randomStringListNotIn(20, objectsFirst);
3192:
3193:                 Object[] array = deque.toArray();
3194:                 assertSame(0, array.length);
3195:
3196:                 deque.addAll(objectsLast);
3197:                 array = deque.toArray();
3198:                 assertSame(deque.size(), array.length);
3199:                 Iterator<Object> dequeIterator = deque.iterator();
3200:•                for (int i = 0; i < array.length; i++) {
3201:                         assertEquals(dequeIterator.next(), array[i]);
3202:                 }
3203:                 deque.clear();
3204:
3205:                 deque.addAll(objectsLast);
3206:•                for (Object o : objectsFirst) {
3207:                         deque.addFirst(o);
3208:                 }
3209:                 array = deque.toArray();
3210:                 assertSame(deque.size(), array.length);
3211:                 dequeIterator = deque.iterator();
3212:•                for (int i = 0; i < array.length; i++) {
3213:                         assertEquals(dequeIterator.next(), array[i]);
3214:                 }
3215:
3216:                 deque.clear();
3217:                 array = deque.toArray();
3218:                 assertEquals(getNextPowerOfTwo(40), getInternalCapacity(deque));
3219:                 assertSame(0, array.length);
3220:         }
3221:
3222:         /**
3223:          * Checks that the two arrays contain the same content.
3224:          *
3225:          * @param expected
3226:          * First of the two array to compare.
3227:          * @param actual
3228:          * Second of the two array to compare.
3229:          */
3230:         private void assertEqualContent(Object[] expected, Object[] actual) {
3231:                 assertEquals(expected.length, actual.length);
3232:•                for (int i = 0; i < expected.length; i++) {
3233:•                        if (expected[i] == null) {
3234:                                 assertSame(expected[i], actual[i]);
3235:                         } else {
3236:                                 assertEquals(expected[i], actual[i]);
3237:                         }
3238:                 }
3239:         }
3240:
3241:         /**
3242:          * Makes the "data" field of the given deque public in order to retrieve it.
3243:          *
3244:          * @param deque
3245:          * The deque we need the internal array of.
3246:          * @return The internal array of the given deque.
3247:          */
3248:         private Object[] getInternalArray(Deque<?> deque) {
3249:                 Field dataField = null;
3250:•                for (Field field : deque.getClass().getDeclaredFields()) {
3251:•                        if (field.getName().equals("data")) { //$NON-NLS-1$
3252:                                 dataField = field;
3253:                                 break;
3254:                         }
3255:                 }
3256:                 assertNotNull(dataField);
3257:•                assert dataField != null;
3258:                 dataField.setAccessible(true);
3259:                 Object[] data = null;
3260:                 try {
3261:                         data = (Object[])dataField.get(deque);
3262:                 } catch (IllegalArgumentException e) {
3263:                         // carry on
3264:                 } catch (IllegalAccessException e) {
3265:                         // carry on
3266:                 }
3267:•                if (data == null) {
3268:                         fail("could not retrieve capacity of " + deque); //$NON-NLS-1$
3269:                 }
3270:                 return data;
3271:         }
3272:
3273:         /**
3274:          * Makes the "data" field of the given deque public in order to retrieve its current size.
3275:          *
3276:          * @param deque
3277:          * The deque we need the capacity of.
3278:          * @return The capacity of the given deque.
3279:          */
3280:         private int getInternalCapacity(Deque<?> deque) {
3281:                 Object[] data = getInternalArray(deque);
3282:                 return data.length;
3283:         }
3284:
3285:         /**
3286:          * Get the closest power of two greater than <code>number</code>.
3287:          *
3288:          * @param number
3289:          * Number for which we seek the closest power of two.
3290:          * @return The closest power of two greater than <code>number</code>.
3291:          */
3292:         private int getNextPowerOfTwo(int number) {
3293:                 int powerOfTwo = number--;
3294:                 powerOfTwo |= powerOfTwo >> 1;
3295:                 powerOfTwo |= powerOfTwo >> 2;
3296:                 powerOfTwo |= powerOfTwo >> 4;
3297:                 powerOfTwo |= powerOfTwo >> 8;
3298:                 powerOfTwo |= powerOfTwo >> 16;
3299:                 powerOfTwo++;
3300:                 return powerOfTwo;
3301:         }
3302:
3303:         /**
3304:          * Returns a random Integer between 0 and 10000000.
3305:          *
3306:          * @return A random Integer between 0 and 10000000.
3307:          */
3308:         private Integer getRandomInteger() {
3309:                 return Integer.valueOf(Double.valueOf(Math.random() * 10000000d).intValue());
3310:         }
3311:
3312:         /**
3313:          * Returns a random String representing an integer between 0 and 10000000.
3314:          *
3315:          * @return A random String representing an integer between 0 and 10000000.
3316:          */
3317:         private String getRandomString() {
3318:                 return getRandomInteger().toString();
3319:         }
3320:
3321:         /**
3322:          * Tests the behavior of {@link CircularArrayDeque#addAll(int, Collection)} with the given Collection. For
3323:          * the sake of this test, all collections will have a size of 2.
3324:          *
3325:          * @param collection
3326:          * Collection to insert into the deque.
3327:          */
3328:         private void internalTestAddAllRandomAccessLeftRotate(List<Object> collection) {
3329:                 // //////////////////////////////////////////
3330:                 // Array : _ _ _ _ _ _ _ _ a a a a a a _ _ //
3331:                 // expect: _ _ _ _ _ _ a a ? ? a a a a _ _ //
3332:                 // //////////////////////////////////////////
3333:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3334:
3335:•                for (int i = 0; i < 14; i++) {
3336:                         deque.offer("a");
3337:                 }
3338:•                for (int i = 0; i < 8; i++) {
3339:                         deque.removeFirst();
3340:                 }
3341:
3342:                 deque.addAll(2, collection);
3343:                 Object[] data = getInternalArray(deque);
3344:                 Object[] expected = new Object[] {null, null, null, null, null, null, "a", "a", collection.get(0),
3345:                                 collection.get(1), "a", "a", "a", "a", null, null };
3346:                 assertEqualContent(expected, data);
3347:
3348:                 // //////////////////////////////////////////
3349:                 // Array : _ a a a a a a _ _ _ _ _ _ _ _ _ //
3350:                 // expect: a ? ? a a a a _ _ _ _ _ _ _ _ a //
3351:                 // //////////////////////////////////////////
3352:                 deque = new CircularArrayDeque<Object>();
3353:
3354:•                for (int i = 0; i < 7; i++) {
3355:                         deque.offer("a");
3356:                 }
3357:                 deque.removeFirst();
3358:
3359:                 deque.addAll(2, collection);
3360:                 data = getInternalArray(deque);
3361:                 expected = new Object[] {"a", collection.get(0), collection.get(1), "a", "a", "a", "a", null, null,
3362:                                 null, null, null, null, null, null, "a" };
3363:                 assertEqualContent(expected, data);
3364:
3365:                 // //////////////////////////////////////////
3366:                 // Array : a a a a a a a _ _ _ _ _ _ _ _ _ //
3367:                 // expect: a ? ? a a a a _ _ _ _ _ _ _ a a //
3368:                 // //////////////////////////////////////////
3369:                 deque = new CircularArrayDeque<Object>();
3370:
3371:•                for (int i = 0; i < 7; i++) {
3372:                         deque.offer("a");
3373:                 }
3374:
3375:                 deque.addAll(3, collection);
3376:                 data = getInternalArray(deque);
3377:                 expected = new Object[] {"a", collection.get(0), collection.get(1), "a", "a", "a", "a", null, null,
3378:                                 null, null, null, null, null, "a", "a" };
3379:                 assertEqualContent(expected, data);
3380:
3381:                 // //////////////////////////////////////////
3382:                 // Array : a a a a a a _ _ _ _ _ _ _ _ _ a //
3383:                 // expect: ? ? a a a a _ _ _ _ _ _ _ a a a //
3384:                 // //////////////////////////////////////////
3385:                 deque = new CircularArrayDeque<Object>();
3386:
3387:•                for (int i = 0; i < 15; i++) {
3388:                         deque.offer("a");
3389:                 }
3390:•                for (int i = 0; i < 14; i++) {
3391:                         deque.removeFirst();
3392:                 }
3393:•                for (int i = 0; i < 7; i++) {
3394:                         deque.offer("a");
3395:                 }
3396:                 deque.removeFirst();
3397:
3398:                 deque.addAll(3, collection);
3399:                 data = getInternalArray(deque);
3400:                 expected = new Object[] {collection.get(0), collection.get(1), "a", "a", "a", "a", null, null, null,
3401:                                 null, null, null, null, "a", "a", "a" };
3402:                 assertEqualContent(expected, data);
3403:
3404:                 // //////////////////////////////////////////
3405:                 // Array : a a a a a _ _ _ _ _ _ _ _ _ a a //
3406:                 // expect: ? a a a a _ _ _ _ _ _ _ a a a ? //
3407:                 // //////////////////////////////////////////
3408:                 deque = new CircularArrayDeque<Object>();
3409:
3410:•                for (int i = 0; i < 15; i++) {
3411:                         deque.offer("a");
3412:                 }
3413:•                for (int i = 0; i < 14; i++) {
3414:                         deque.removeFirst();
3415:                 }
3416:•                for (int i = 0; i < 6; i++) {
3417:                         deque.offer("a");
3418:                 }
3419:
3420:                 deque.addAll(3, collection);
3421:                 data = getInternalArray(deque);
3422:                 expected = new Object[] {collection.get(1), "a", "a", "a", "a", null, null, null, null, null, null,
3423:                                 null, "a", "a", "a", collection.get(0) };
3424:                 assertEqualContent(expected, data);
3425:
3426:                 // //////////////////////////////////////////
3427:                 // Array : a a a a _ _ _ _ _ _ _ _ _ a a a //
3428:                 // expect: a a a a _ _ _ _ _ _ _ a a a ? ? //
3429:                 // //////////////////////////////////////////
3430:                 deque = new CircularArrayDeque<Object>();
3431:
3432:•                for (int i = 0; i < 15; i++) {
3433:                         deque.offer("a");
3434:                 }
3435:•                for (int i = 0; i < 13; i++) {
3436:                         deque.removeFirst();
3437:                 }
3438:•                for (int i = 0; i < 5; i++) {
3439:                         deque.offer("a");
3440:                 }
3441:
3442:                 deque.addAll(3, collection);
3443:                 data = getInternalArray(deque);
3444:                 expected = new Object[] {"a", "a", "a", "a", null, null, null, null, null, null, null, "a", "a", "a",
3445:                                 collection.get(0), collection.get(1) };
3446:                 assertEqualContent(expected, data);
3447:
3448:                 // //////////////////////////////////////////////////////////////////////////
3449:                 // Array : a a a a a a a _ a a a a a a a a //
3450:                 // expect: a a ? ? a a a a a a a a a a a _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ a a //
3451:                 // //////////////////////////////////////////////////////////////////////////
3452:                 deque = new CircularArrayDeque<Object>();
3453:
3454:•                for (int i = 0; i < 15; i++) {
3455:                         deque.offer("a");
3456:                 }
3457:•                for (int i = 0; i < 8; i++) {
3458:                         deque.removeFirst();
3459:                 }
3460:•                for (int i = 0; i < 8; i++) {
3461:                         deque.offer("a");
3462:                 }
3463:
3464:                 deque.addAll(4, collection);
3465:                 data = getInternalArray(deque);
3466:                 expected = new Object[32];
3467:•                for (int i = 0; i < 2; i++) {
3468:                         expected[i] = "a";
3469:                 }
3470:                 expected[2] = collection.get(0);
3471:                 expected[3] = collection.get(1);
3472:•                for (int i = 4; i < 15; i++) {
3473:                         expected[i] = "a";
3474:                 }
3475:                 expected[30] = "a";
3476:                 expected[31] = "a";
3477:                 assertEqualContent(expected, data);
3478:         }
3479:
3480:         /**
3481:          * Tests the behavior of {@link CircularArrayDeque#addAll(int, Collection)} with the given Collection. For
3482:          * the sake of this test, all collections will have a size of 2.
3483:          *
3484:          * @param collection
3485:          * Collection to insert into the deque.
3486:          */
3487:         private void internalTestAddAllRandomAccessRightRotate(List<Object> collection) {
3488:                 // //////////////////////////////////////////
3489:                 // Array : _ _ _ _ _ _ _ _ a a a a a a _ _ //
3490:                 // expect: _ _ _ _ _ _ _ _ a a a a ? ? a a //
3491:                 // //////////////////////////////////////////
3492:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3493:
3494:•                for (int i = 0; i < 14; i++) {
3495:                         deque.offer("a");
3496:                 }
3497:•                for (int i = 0; i < 8; i++) {
3498:                         deque.removeFirst();
3499:                 }
3500:
3501:                 deque.addAll(4, collection);
3502:                 Object[] data = getInternalArray(deque);
3503:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
3504:                                 collection.get(0), collection.get(1), "a", "a" };
3505:                 assertEqualContent(expected, data);
3506:
3507:                 // //////////////////////////////////////////
3508:                 // Array : _ _ _ _ _ _ _ _ _ a a a a a a _ //
3509:                 // expect: a _ _ _ _ _ _ _ _ a a a a ? ? a //
3510:                 // //////////////////////////////////////////
3511:                 deque = new CircularArrayDeque<Object>();
3512:
3513:•                for (int i = 0; i < 15; i++) {
3514:                         deque.offer("a");
3515:                 }
3516:•                for (int i = 0; i < 9; i++) {
3517:                         deque.removeFirst();
3518:                 }
3519:
3520:                 deque.addAll(4, collection);
3521:                 data = getInternalArray(deque);
3522:                 expected = new Object[] {"a", null, null, null, null, null, null, null, null, "a", "a", "a", "a",
3523:                                 collection.get(0), collection.get(1), "a" };
3524:                 assertEqualContent(expected, data);
3525:
3526:                 // //////////////////////////////////////////
3527:                 // Array : _ _ _ _ _ _ _ _ _ a a a a a a a //
3528:                 // expect: a a _ _ _ _ _ _ _ a a a a ? ? a //
3529:                 // //////////////////////////////////////////
3530:                 deque = new CircularArrayDeque<Object>();
3531:
3532:•                for (int i = 0; i < 15; i++) {
3533:                         deque.offer("a");
3534:                 }
3535:•                for (int i = 0; i < 9; i++) {
3536:                         deque.removeFirst();
3537:                 }
3538:                 deque.offer("a");
3539:
3540:                 deque.addAll(4, collection);
3541:                 data = getInternalArray(deque);
3542:                 expected = new Object[] {"a", "a", null, null, null, null, null, null, null, "a", "a", "a", "a",
3543:                                 collection.get(0), collection.get(1), "a" };
3544:                 assertEqualContent(expected, data);
3545:
3546:                 // //////////////////////////////////////////
3547:                 // Array : a _ _ _ _ _ _ _ _ _ a a a a a a //
3548:                 // expect: a a a _ _ _ _ _ _ _ a a a a ? ? //
3549:                 // //////////////////////////////////////////
3550:                 deque = new CircularArrayDeque<Object>();
3551:
3552:•                for (int i = 0; i < 15; i++) {
3553:                         deque.offer("a");
3554:                 }
3555:•                for (int i = 0; i < 10; i++) {
3556:                         deque.removeFirst();
3557:                 }
3558:                 deque.offer("a");
3559:                 deque.offer("a");
3560:
3561:                 deque.addAll(4, collection);
3562:                 data = getInternalArray(deque);
3563:                 expected = new Object[] {"a", "a", "a", null, null, null, null, null, null, null, "a", "a", "a", "a",
3564:                                 collection.get(0), collection.get(1) };
3565:                 assertEqualContent(expected, data);
3566:
3567:                 // //////////////////////////////////////////
3568:                 // Array : a a _ _ _ _ _ _ _ _ _ a a a a a //
3569:                 // expect: ? a a a _ _ _ _ _ _ _ a a a a ? //
3570:                 // //////////////////////////////////////////
3571:                 deque = new CircularArrayDeque<Object>();
3572:
3573:•                for (int i = 0; i < 15; i++) {
3574:                         deque.offer("a");
3575:                 }
3576:•                for (int i = 0; i < 11; i++) {
3577:                         deque.removeFirst();
3578:                 }
3579:                 deque.offer("a");
3580:                 deque.offer("a");
3581:                 deque.offer("a");
3582:
3583:                 deque.addAll(4, collection);
3584:                 data = getInternalArray(deque);
3585:                 expected = new Object[] {collection.get(1), "a", "a", "a", null, null, null, null, null, null, null,
3586:                                 "a", "a", "a", "a", collection.get(0) };
3587:                 assertEqualContent(expected, data);
3588:
3589:                 // //////////////////////////////////////////
3590:                 // Array : a a _ _ _ _ _ _ _ _ _ _ a a a a //
3591:                 // expect: ? ? a a _ _ _ _ _ _ _ _ a a a a //
3592:                 // //////////////////////////////////////////
3593:                 deque = new CircularArrayDeque<Object>();
3594:
3595:•                for (int i = 0; i < 15; i++) {
3596:                         deque.offer("a");
3597:                 }
3598:•                for (int i = 0; i < 12; i++) {
3599:                         deque.removeFirst();
3600:                 }
3601:                 deque.offer("a");
3602:                 deque.offer("a");
3603:                 deque.offer("a");
3604:
3605:                 deque.addAll(4, collection);
3606:                 data = getInternalArray(deque);
3607:                 expected = new Object[] {collection.get(0), collection.get(1), "a", "a", null, null, null, null,
3608:                                 null, null, null, null, "a", "a", "a", "a" };
3609:                 assertEqualContent(expected, data);
3610:
3611:                 // //////////////////////////////////////////////////////////////////////////
3612:                 // Array : a a a a a a a _ a a a a a a a a //
3613:                 // expect: a a a a a a a a a a a ? ? a a a a _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ //
3614:                 // //////////////////////////////////////////////////////////////////////////
3615:                 deque = new CircularArrayDeque<Object>();
3616:
3617:•                for (int i = 0; i < 15; i++) {
3618:                         deque.offer("a");
3619:                 }
3620:•                for (int i = 0; i < 7; i++) {
3621:                         deque.removeFirst();
3622:                 }
3623:•                for (int i = 0; i < 7; i++) {
3624:                         deque.offer("a");
3625:                 }
3626:
3627:                 deque.addAll(11, collection);
3628:                 data = getInternalArray(deque);
3629:                 expected = new Object[32];
3630:•                for (int i = 0; i < 11; i++) {
3631:                         expected[i] = "a";
3632:                 }
3633:                 expected[11] = collection.get(0);
3634:                 expected[12] = collection.get(1);
3635:•                for (int i = 13; i < 17; i++) {
3636:                         expected[i] = "a";
3637:                 }
3638:                 assertEqualContent(expected, data);
3639:         }
3640:
3641:         /**
3642:          * Tests the behavior of {@link CircularArrayDeque#add(int, Object)} with the given element.
3643:          *
3644:          * @param element
3645:          * Element to insert into the deque.
3646:          */
3647:         private void internalTestAddRandomAccessLeftRotate(Object element) {
3648:                 // //////////////////////////////////////////
3649:                 // Array : _ _ _ _ _ _ _ _ a a a a a a a _ //
3650:                 // expect: _ _ _ _ _ _ _ a a a ? a a a a _ //
3651:                 // //////////////////////////////////////////
3652:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3653:
3654:•                for (int i = 0; i < 15; i++) {
3655:                         deque.offer("a");
3656:                 }
3657:•                for (int i = 0; i < 8; i++) {
3658:                         deque.removeFirst();
3659:                 }
3660:
3661:                 deque.add(3, element);
3662:                 Object[] data = getInternalArray(deque);
3663:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, "a", "a", "a", element,
3664:                                 "a", "a", "a", "a", null };
3665:                 assertEqualContent(expected, data);
3666:
3667:                 // //////////////////////////////////////////
3668:                 // Array : a a a a a a a _ _ _ _ _ _ _ _ _ //
3669:                 // expect: a a ? a a a a _ _ _ _ _ _ _ _ a //
3670:                 // //////////////////////////////////////////
3671:                 deque = new CircularArrayDeque<Object>();
3672:
3673:•                for (int i = 0; i < 7; i++) {
3674:                         deque.offer("a");
3675:                 }
3676:
3677:                 deque.add(3, element);
3678:                 data = getInternalArray(deque);
3679:                 expected = new Object[] {"a", "a", element, "a", "a", "a", "a", null, null, null, null, null, null,
3680:                                 null, null, "a" };
3681:                 assertEqualContent(expected, data);
3682:
3683:                 // //////////////////////////////////////////
3684:                 // Array : a a a a a _ _ _ _ _ _ _ _ _ a a //
3685:                 // expect: ? a a a a _ _ _ _ _ _ _ _ a a a //
3686:                 // //////////////////////////////////////////
3687:                 deque = new CircularArrayDeque<Object>();
3688:
3689:•                for (int i = 0; i < 15; i++) {
3690:                         deque.offer("a");
3691:                 }
3692:•                for (int i = 0; i < 14; i++) {
3693:                         deque.removeFirst();
3694:                 }
3695:•                for (int i = 0; i < 6; i++) {
3696:                         deque.offer("a");
3697:                 }
3698:
3699:                 deque.add(3, element);
3700:                 data = getInternalArray(deque);
3701:                 expected = new Object[] {element, "a", "a", "a", "a", null, null, null, null, null, null, null, null,
3702:                                 "a", "a", "a" };
3703:                 assertEqualContent(expected, data);
3704:
3705:                 // //////////////////////////////////////////
3706:                 // Array : a a a a _ _ _ _ _ _ _ _ _ a a a //
3707:                 // expect: a a a a _ _ _ _ _ _ _ _ a a a ? //
3708:                 // //////////////////////////////////////////
3709:                 deque = new CircularArrayDeque<Object>();
3710:
3711:•                for (int i = 0; i < 15; i++) {
3712:                         deque.offer("a");
3713:                 }
3714:•                for (int i = 0; i < 13; i++) {
3715:                         deque.removeFirst();
3716:                 }
3717:•                for (int i = 0; i < 5; i++) {
3718:                         deque.offer("a");
3719:                 }
3720:
3721:                 deque.add(3, element);
3722:                 data = getInternalArray(deque);
3723:                 expected = new Object[] {"a", "a", "a", "a", null, null, null, null, null, null, null, null, "a",
3724:                                 "a", "a", element };
3725:                 assertEqualContent(expected, data);
3726:
3727:                 // //////////////////////////////////////////////////////////////////////////
3728:                 // Array : a a a a a a a _ a a a a a a a a //
3729:                 // expect: a a a ? a a a a a a a a a a a a _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ //
3730:                 // //////////////////////////////////////////////////////////////////////////
3731:                 deque = new CircularArrayDeque<Object>();
3732:
3733:•                for (int i = 0; i < 15; i++) {
3734:                         deque.offer("a");
3735:                 }
3736:•                for (int i = 0; i < 7; i++) {
3737:                         deque.removeFirst();
3738:                 }
3739:•                for (int i = 0; i < 7; i++) {
3740:                         deque.offer("a");
3741:                 }
3742:
3743:                 deque.add(3, element);
3744:                 data = getInternalArray(deque);
3745:                 expected = new Object[32];
3746:•                for (int i = 0; i < 3; i++) {
3747:                         expected[i] = "a";
3748:                 }
3749:                 expected[3] = element;
3750:•                for (int i = 4; i < 16; i++) {
3751:                         expected[i] = "a";
3752:                 }
3753:                 assertEqualContent(expected, data);
3754:         }
3755:
3756:         /**
3757:          * Tests the behavior of {@link CircularArrayDeque#add(int, Object)} with the given element.
3758:          *
3759:          * @param element
3760:          * Element to insert into the deque.
3761:          */
3762:         private void internalTestAddRandomAccessRightRotate(Object element) {
3763:                 // //////////////////////////////////////////
3764:                 // Array : _ _ _ _ _ _ _ _ a a a a a a a _ //
3765:                 // expect: _ _ _ _ _ _ _ _ a a a a ? a a a //
3766:                 // //////////////////////////////////////////
3767:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3768:
3769:•                for (int i = 0; i < 15; i++) {
3770:                         deque.offer("a");
3771:                 }
3772:•                for (int i = 0; i < 8; i++) {
3773:                         deque.removeFirst();
3774:                 }
3775:
3776:                 deque.add(4, element);
3777:                 Object[] data = getInternalArray(deque);
3778:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
3779:                                 element, "a", "a", "a" };
3780:                 assertEqualContent(expected, data);
3781:
3782:                 // //////////////////////////////////////////
3783:                 // Array : _ _ _ _ _ _ _ _ _ a a a a a a a //
3784:                 // expect: a _ _ _ _ _ _ _ _ a a a a ? a a //
3785:                 // //////////////////////////////////////////
3786:                 deque = new CircularArrayDeque<Object>();
3787:
3788:•                for (int i = 0; i < 15; i++) {
3789:                         deque.offer("a");
3790:                 }
3791:•                for (int i = 0; i < 9; i++) {
3792:                         deque.removeFirst();
3793:                 }
3794:                 deque.offer("a");
3795:
3796:                 deque.add(4, element);
3797:                 data = getInternalArray(deque);
3798:                 expected = new Object[] {"a", null, null, null, null, null, null, null, null, "a", "a", "a", "a",
3799:                                 element, "a", "a" };
3800:                 assertEqualContent(expected, data);
3801:
3802:                 // //////////////////////////////////////////
3803:                 // Array : a a _ _ _ _ _ _ _ _ _ a a a a a //
3804:                 // expect: a a a _ _ _ _ _ _ _ _ a a a a ? //
3805:                 // //////////////////////////////////////////
3806:                 deque = new CircularArrayDeque<Object>();
3807:
3808:•                for (int i = 0; i < 15; i++) {
3809:                         deque.offer("a");
3810:                 }
3811:•                for (int i = 0; i < 11; i++) {
3812:                         deque.removeFirst();
3813:                 }
3814:                 deque.offer("a");
3815:                 deque.offer("a");
3816:                 deque.offer("a");
3817:
3818:                 deque.add(4, element);
3819:                 data = getInternalArray(deque);
3820:                 expected = new Object[] {"a", "a", "a", null, null, null, null, null, null, null, null, "a", "a",
3821:                                 "a", "a", element };
3822:                 assertEqualContent(expected, data);
3823:
3824:                 // //////////////////////////////////////////
3825:                 // Array : a a a _ _ _ _ _ _ _ _ _ a a a a //
3826:                 // expect: ? a a a _ _ _ _ _ _ _ _ a a a a //
3827:                 // //////////////////////////////////////////
3828:                 deque = new CircularArrayDeque<Object>();
3829:
3830:•                for (int i = 0; i < 15; i++) {
3831:                         deque.offer("a");
3832:                 }
3833:•                for (int i = 0; i < 12; i++) {
3834:                         deque.removeFirst();
3835:                 }
3836:                 deque.offer("a");
3837:                 deque.offer("a");
3838:                 deque.offer("a");
3839:                 deque.offer("a");
3840:
3841:                 deque.add(4, element);
3842:                 data = getInternalArray(deque);
3843:                 expected = new Object[] {element, "a", "a", "a", null, null, null, null, null, null, null, null, "a",
3844:                                 "a", "a", "a" };
3845:                 assertEqualContent(expected, data);
3846:
3847:                 // //////////////////////////////////////////////////////////////////////////
3848:                 // Array : a a a a a a a _ a a a a a a a a //
3849:                 // expect: a a a a a a a a a a a ? a a a a _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ //
3850:                 // //////////////////////////////////////////////////////////////////////////
3851:                 deque = new CircularArrayDeque<Object>();
3852:
3853:•                for (int i = 0; i < 15; i++) {
3854:                         deque.offer("a");
3855:                 }
3856:•                for (int i = 0; i < 7; i++) {
3857:                         deque.removeFirst();
3858:                 }
3859:•                for (int i = 0; i < 7; i++) {
3860:                         deque.offer("a");
3861:                 }
3862:
3863:                 deque.add(11, element);
3864:                 data = getInternalArray(deque);
3865:                 expected = new Object[32];
3866:•                for (int i = 0; i < 11; i++) {
3867:                         expected[i] = "a";
3868:                 }
3869:                 expected[11] = element;
3870:•                for (int i = 12; i < 16; i++) {
3871:                         expected[i] = "a";
3872:                 }
3873:                 assertEqualContent(expected, data);
3874:         }
3875:
3876:         /**
3877:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with the given Collection. For
3878:          * the sake of this test, all collections will have a size of 2.
3879:          *
3880:          * @param collection
3881:          * Collection to remove from the deque.
3882:          */
3883:         private void internalTestRemoveAllBothRotate(List<Object> collection) {
3884:                 // //////////////////////////////////////////
3885:                 // Array : _ _ _ _ _ a a a ? ? a a a _ _ _ //
3886:                 // expect: _ _ _ _ _ _ a a a a a a _ _ _ _ //
3887:                 // //////////////////////////////////////////
3888:                 Deque<Object> deque = new CircularArrayDeque<Object>();
3889:
3890:•                for (int i = 0; i < 13; i++) {
3891:                         deque.offer("a");
3892:                 }
3893:•                for (int i = 0; i < 5; i++) {
3894:                         deque.removeFirst();
3895:                 }
3896:                 deque.set(3, collection.get(0));
3897:                 deque.set(4, collection.get(1));
3898:
3899:                 deque.removeAll(collection);
3900:                 Object[] data = getInternalArray(deque);
3901:                 Object[] expected = new Object[] {null, null, null, null, null, null, "a", "a", "a", "a", "a", "a",
3902:                                 null, null, null, null };
3903:                 assertEqualContent(expected, data);
3904:
3905:                 // //////////////////////////////////////////
3906:                 // Array : _ _ _ _ _ _ _ _ a a a ? ? a a a //
3907:                 // expect: _ _ _ _ _ _ _ _ _ a a a a a a _ //
3908:                 // //////////////////////////////////////////
3909:                 deque = new CircularArrayDeque<Object>();
3910:
3911:•                for (int i = 0; i < 15; i++) {
3912:                         deque.offer("a");
3913:                 }
3914:•                for (int i = 0; i < 8; i++) {
3915:                         deque.removeFirst();
3916:                 }
3917:                 deque.offer("a");
3918:                 deque.set(3, collection.get(0));
3919:                 deque.set(4, collection.get(1));
3920:
3921:                 deque.removeAll(collection);
3922:                 data = getInternalArray(deque);
3923:                 expected = new Object[] {null, null, null, null, null, null, null, null, null, "a", "a", "a", "a",
3924:                                 "a", "a", null };
3925:                 assertEqualContent(expected, data);
3926:
3927:                 // //////////////////////////////////////////
3928:                 // Array : a _ _ _ _ _ _ _ _ a a a ? ? a a //
3929:                 // expect: _ _ _ _ _ _ _ _ _ _ a a a a a a //
3930:                 // //////////////////////////////////////////
3931:                 deque = new CircularArrayDeque<Object>();
3932:
3933:•                for (int i = 0; i < 15; i++) {
3934:                         deque.offer("a");
3935:                 }
3936:•                for (int i = 0; i < 9; i++) {
3937:                         deque.removeFirst();
3938:                 }
3939:•                for (int i = 0; i < 2; i++) {
3940:                         deque.offer("a");
3941:                 }
3942:                 deque.set(3, collection.get(0));
3943:                 deque.set(4, collection.get(1));
3944:
3945:                 deque.removeAll(collection);
3946:                 data = getInternalArray(deque);
3947:                 expected = new Object[] {null, null, null, null, null, null, null, null, null, null, "a", "a", "a",
3948:                                 "a", "a", "a" };
3949:                 assertEqualContent(expected, data);
3950:
3951:                 // //////////////////////////////////////////
3952:                 // Array : a a _ _ _ _ _ _ _ _ a a a ? ? a //
3953:                 // expect: a _ _ _ _ _ _ _ _ _ _ a a a a a //
3954:                 // //////////////////////////////////////////
3955:                 deque = new CircularArrayDeque<Object>();
3956:
3957:•                for (int i = 0; i < 15; i++) {
3958:                         deque.offer("a");
3959:                 }
3960:•                for (int i = 0; i < 10; i++) {
3961:                         deque.removeFirst();
3962:                 }
3963:•                for (int i = 0; i < 3; i++) {
3964:                         deque.offer("a");
3965:                 }
3966:                 deque.set(3, collection.get(0));
3967:                 deque.set(4, collection.get(1));
3968:
3969:                 deque.removeAll(collection);
3970:                 data = getInternalArray(deque);
3971:                 expected = new Object[] {"a", null, null, null, null, null, null, null, null, null, null, "a", "a",
3972:                                 "a", "a", "a" };
3973:                 assertEqualContent(expected, data);
3974:
3975:                 // //////////////////////////////////////////
3976:                 // Array : a a a _ _ _ _ _ _ _ _ a a a ? ? //
3977:                 // expect: a a _ _ _ _ _ _ _ _ _ _ a a a a //
3978:                 // //////////////////////////////////////////
3979:                 deque = new CircularArrayDeque<Object>();
3980:
3981:•                for (int i = 0; i < 15; i++) {
3982:                         deque.offer("a");
3983:                 }
3984:•                for (int i = 0; i < 11; i++) {
3985:                         deque.removeFirst();
3986:                 }
3987:•                for (int i = 0; i < 4; i++) {
3988:                         deque.offer("a");
3989:                 }
3990:                 deque.set(3, collection.get(0));
3991:                 deque.set(4, collection.get(1));
3992:
3993:                 deque.removeAll(collection);
3994:                 data = getInternalArray(deque);
3995:                 expected = new Object[] {"a", "a", null, null, null, null, null, null, null, null, null, null, "a",
3996:                                 "a", "a", "a" };
3997:                 assertEqualContent(expected, data);
3998:
3999:                 // //////////////////////////////////////////
4000:                 // Array : ? a a a _ _ _ _ _ _ _ _ a a a ? //
4001:                 // expect: a a a _ _ _ _ _ _ _ _ _ _ a a a //
4002:                 // //////////////////////////////////////////
4003:                 deque = new CircularArrayDeque<Object>();
4004:
4005:•                for (int i = 0; i < 15; i++) {
4006:                         deque.offer("a");
4007:                 }
4008:•                for (int i = 0; i < 12; i++) {
4009:                         deque.removeFirst();
4010:                 }
4011:•                for (int i = 0; i < 5; i++) {
4012:                         deque.offer("a");
4013:                 }
4014:                 deque.set(3, collection.get(0));
4015:                 deque.set(4, collection.get(1));
4016:
4017:                 deque.removeAll(collection);
4018:                 data = getInternalArray(deque);
4019:                 expected = new Object[] {"a", "a", "a", null, null, null, null, null, null, null, null, null, null,
4020:                                 "a", "a", "a" };
4021:                 assertEqualContent(expected, data);
4022:
4023:                 // //////////////////////////////////////////
4024:                 // Array : ? ? a a a _ _ _ _ _ _ _ _ a a a //
4025:                 // expect: a a a a _ _ _ _ _ _ _ _ _ _ a a //
4026:                 // //////////////////////////////////////////
4027:                 deque = new CircularArrayDeque<Object>();
4028:
4029:•                for (int i = 0; i < 15; i++) {
4030:                         deque.offer("a");
4031:                 }
4032:•                for (int i = 0; i < 13; i++) {
4033:                         deque.removeFirst();
4034:                 }
4035:•                for (int i = 0; i < 6; i++) {
4036:                         deque.offer("a");
4037:                 }
4038:                 deque.set(3, collection.get(0));
4039:                 deque.set(4, collection.get(1));
4040:
4041:                 deque.removeAll(collection);
4042:                 data = getInternalArray(deque);
4043:                 expected = new Object[] {"a", "a", "a", "a", null, null, null, null, null, null, null, null, null,
4044:                                 null, "a", "a" };
4045:                 assertEqualContent(expected, data);
4046:
4047:                 // //////////////////////////////////////////
4048:                 // Array : a ? ? a a a _ _ _ _ _ _ _ _ a a //
4049:                 // expect: a a a a a _ _ _ _ _ _ _ _ _ _ a //
4050:                 // //////////////////////////////////////////
4051:                 deque = new CircularArrayDeque<Object>();
4052:
4053:•                for (int i = 0; i < 15; i++) {
4054:                         deque.offer("a");
4055:                 }
4056:•                for (int i = 0; i < 14; i++) {
4057:                         deque.removeFirst();
4058:                 }
4059:•                for (int i = 0; i < 7; i++) {
4060:                         deque.offer("a");
4061:                 }
4062:                 deque.set(3, collection.get(0));
4063:                 deque.set(4, collection.get(1));
4064:
4065:                 deque.removeAll(collection);
4066:                 data = getInternalArray(deque);
4067:                 expected = new Object[] {"a", "a", "a", "a", "a", null, null, null, null, null, null, null, null,
4068:                                 null, null, "a" };
4069:                 assertEqualContent(expected, data);
4070:
4071:                 // //////////////////////////////////////////
4072:                 // Array : a a ? ? a a a _ _ _ _ _ _ _ _ a //
4073:                 // expect: a a a a a a _ _ _ _ _ _ _ _ _ _ //
4074:                 // //////////////////////////////////////////
4075:                 deque = new CircularArrayDeque<Object>();
4076:
4077:•                for (int i = 0; i < 15; i++) {
4078:                         deque.offer("a");
4079:                 }
4080:                 deque.removeFirst();
4081:                 deque.offer("a");
4082:•                for (int i = 0; i < 14; i++) {
4083:                         deque.removeFirst();
4084:                 }
4085:•                for (int i = 0; i < 7; i++) {
4086:                         deque.offer("a");
4087:                 }
4088:                 deque.set(3, collection.get(0));
4089:                 deque.set(4, collection.get(1));
4090:
4091:                 deque.removeAll(collection);
4092:                 data = getInternalArray(deque);
4093:                 expected = new Object[] {"a", "a", "a", "a", "a", "a", null, null, null, null, null, null, null,
4094:                                 null, null, null };
4095:                 assertEqualContent(expected, data);
4096:
4097:                 // //////////////////////////////////////////
4098:                 // Array : a a a ? ? a a a _ _ _ _ _ _ _ _ //
4099:                 // expect: _ a a a a a a _ _ _ _ _ _ _ _ _ //
4100:                 // //////////////////////////////////////////
4101:                 deque = new CircularArrayDeque<Object>();
4102:
4103:•                for (int i = 0; i < 8; i++) {
4104:                         deque.offer("a");
4105:                 }
4106:                 deque.set(3, collection.get(0));
4107:                 deque.set(4, collection.get(1));
4108:
4109:                 deque.removeAll(collection);
4110:                 data = getInternalArray(deque);
4111:                 expected = new Object[] {null, "a", "a", "a", "a", "a", "a", null, null, null, null, null, null,
4112:                                 null, null, null };
4113:                 assertEqualContent(expected, data);
4114:         }
4115:
4116:         /**
4117:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with the given Collection. For
4118:          * the sake of this test, all collections will have a size of 2.
4119:          *
4120:          * @param collection
4121:          * Collection to remove from the deque.
4122:          */
4123:         private void internalTestRemoveAllLeftRotate(List<Object> collection) {
4124:                 // //////////////////////////////////////////
4125:                 // Array : _ _ _ _ _ _ _ _ a a a a ? ? a a //
4126:                 // expect: _ _ _ _ _ _ _ _ a a a a a a _ _ //
4127:                 // //////////////////////////////////////////
4128:                 Deque<Object> deque = new CircularArrayDeque<Object>();
4129:
4130:•                for (int i = 0; i < 12; i++) {
4131:                         deque.offer("a");
4132:                 }
4133:                 deque.addAll(collection);
4134:•                for (int i = 0; i < 8; i++) {
4135:                         deque.removeFirst();
4136:                 }
4137:•                for (int i = 0; i < 2; i++) {
4138:                         deque.offer("a");
4139:                 }
4140:
4141:                 deque.removeAll(collection);
4142:                 Object[] data = getInternalArray(deque);
4143:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4144:                                 "a", "a", null, null };
4145:                 assertEqualContent(expected, data);
4146:
4147:                 // //////////////////////////////////////////
4148:                 // Array : a _ _ _ _ _ _ _ _ a a a a ? ? a //
4149:                 // expect: _ _ _ _ _ _ _ _ _ a a a a a a _ //
4150:                 // //////////////////////////////////////////
4151:                 deque = new CircularArrayDeque<Object>();
4152:
4153:•                for (int i = 0; i < 13; i++) {
4154:                         deque.offer("a");
4155:                 }
4156:                 deque.addAll(collection);
4157:•                for (int i = 0; i < 9; i++) {
4158:                         deque.removeFirst();
4159:                 }
4160:•                for (int i = 0; i < 2; i++) {
4161:                         deque.offer("a");
4162:                 }
4163:
4164:                 deque.removeAll(collection);
4165:                 data = getInternalArray(deque);
4166:                 expected = new Object[] {null, null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4167:                                 "a", "a", null };
4168:                 assertEqualContent(expected, data);
4169:
4170:                 // //////////////////////////////////////////
4171:                 // Array : a a _ _ _ _ _ _ a a a a a ? ? a //
4172:                 // expect: _ _ _ _ _ _ _ _ a a a a a a a a //
4173:                 // //////////////////////////////////////////
4174:                 deque = new CircularArrayDeque<Object>();
4175:
4176:•                for (int i = 0; i < 13; i++) {
4177:                         deque.offer("a");
4178:                 }
4179:                 deque.addAll(collection);
4180:•                for (int i = 0; i < 8; i++) {
4181:                         deque.removeFirst();
4182:                 }
4183:•                for (int i = 0; i < 3; i++) {
4184:                         deque.offer("a");
4185:                 }
4186:
4187:                 deque.removeAll(collection);
4188:                 data = getInternalArray(deque);
4189:                 expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a", "a",
4190:                                 "a", "a", "a" };
4191:                 assertEqualContent(expected, data);
4192:
4193:                 // //////////////////////////////////////////
4194:                 // Array : a a a _ _ _ _ _ _ a a a a a ? ? //
4195:                 // expect: a _ _ _ _ _ _ _ _ a a a a a a a //
4196:                 // //////////////////////////////////////////
4197:                 deque = new CircularArrayDeque<Object>();
4198:
4199:•                for (int i = 0; i < 14; i++) {
4200:                         deque.offer("a");
4201:                 }
4202:•                for (int i = 0; i < 9; i++) {
4203:                         deque.removeFirst();
4204:                 }
4205:                 deque.addAll(collection);
4206:•                for (int i = 0; i < 3; i++) {
4207:                         deque.offer("a");
4208:                 }
4209:
4210:                 deque.removeAll(collection);
4211:                 data = getInternalArray(deque);
4212:                 expected = new Object[] {"a", null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4213:                                 "a", "a", "a" };
4214:                 assertEqualContent(expected, data);
4215:
4216:                 // //////////////////////////////////////////
4217:                 // Array : ? a a a _ _ _ _ _ _ a a a a a ? //
4218:                 // expect: a a _ _ _ _ _ _ _ _ a a a a a a //
4219:                 // //////////////////////////////////////////
4220:                 deque = new CircularArrayDeque<Object>();
4221:
4222:•                for (int i = 0; i < 15; i++) {
4223:                         deque.offer("a");
4224:                 }
4225:•                for (int i = 0; i < 10; i++) {
4226:                         deque.removeFirst();
4227:                 }
4228:                 deque.addAll(collection);
4229:•                for (int i = 0; i < 3; i++) {
4230:                         deque.offer("a");
4231:                 }
4232:
4233:                 deque.removeAll(collection);
4234:                 data = getInternalArray(deque);
4235:                 expected = new Object[] {"a", "a", null, null, null, null, null, null, null, null, "a", "a", "a",
4236:                                 "a", "a", "a" };
4237:                 assertEqualContent(expected, data);
4238:
4239:                 // //////////////////////////////////////////
4240:                 // Array : ? ? a a _ _ _ _ _ _ _ a a a a a //
4241:                 // expect: a a _ _ _ _ _ _ _ _ _ a a a a a //
4242:                 // //////////////////////////////////////////
4243:                 deque = new CircularArrayDeque<Object>();
4244:
4245:•                for (int i = 0; i < 15; i++) {
4246:                         deque.offer("a");
4247:                 }
4248:•                for (int i = 0; i < 11; i++) {
4249:                         deque.removeFirst();
4250:                 }
4251:                 deque.offer("a");
4252:                 deque.addAll(collection);
4253:                 deque.offer("a");
4254:                 deque.offer("a");
4255:
4256:                 deque.removeAll(collection);
4257:                 data = getInternalArray(deque);
4258:                 expected = new Object[] {"a", "a", null, null, null, null, null, null, null, null, null, "a", "a",
4259:                                 "a", "a", "a" };
4260:                 assertEqualContent(expected, data);
4261:         }
4262:
4263:         /**
4264:          * Tests the behavior of {@link CircularArrayDeque#removeAll(Collection)} with the given Collection. For
4265:          * the sake of this test, all collections will have a size of 2.
4266:          *
4267:          * @param collection
4268:          * Collection to remove from the deque.
4269:          */
4270:         private void internalTestRemoveAllRightRotate(List<Object> collection) {
4271:                 // //////////////////////////////////////////
4272:                 // Array : _ _ _ _ _ _ a a ? ? a a a a _ _ //
4273:                 // expect: _ _ _ _ _ _ _ _ a a a a a a _ _ //
4274:                 // //////////////////////////////////////////
4275:                 Deque<Object> deque = new CircularArrayDeque<Object>();
4276:
4277:•                for (int i = 0; i < 8; i++) {
4278:                         deque.offer("a");
4279:                 }
4280:                 deque.addAll(collection);
4281:•                for (int i = 0; i < 4; i++) {
4282:                         deque.offer("a");
4283:                 }
4284:•                for (int i = 0; i < 6; i++) {
4285:                         deque.removeFirst();
4286:                 }
4287:
4288:                 deque.removeAll(collection);
4289:                 Object[] data = getInternalArray(deque);
4290:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4291:                                 "a", "a", null, null };
4292:                 assertEqualContent(expected, data);
4293:
4294:                 // //////////////////////////////////////////
4295:                 // Array : a ? ? a a a a _ _ _ _ _ _ _ _ a //
4296:                 // expect: _ a a a a a a _ _ _ _ _ _ _ _ _ //
4297:                 // //////////////////////////////////////////
4298:                 deque = new CircularArrayDeque<Object>();
4299:
4300:•                for (int i = 0; i < 15; i++) {
4301:                         deque.offer("a");
4302:                 }
4303:                 deque.removeFirst();
4304:                 deque.offer("a");
4305:•                for (int i = 0; i < 14; i++) {
4306:                         deque.removeFirst();
4307:                 }
4308:                 deque.offer("a");
4309:                 deque.addAll(collection);
4310:•                for (int i = 0; i < 4; i++) {
4311:                         deque.offer("a");
4312:                 }
4313:
4314:                 deque.removeAll(collection);
4315:                 data = getInternalArray(deque);
4316:                 expected = new Object[] {null, "a", "a", "a", "a", "a", "a", null, null, null, null, null, null,
4317:                                 null, null, null };
4318:                 assertEqualContent(expected, data);
4319:
4320:                 // //////////////////////////////////////////
4321:                 // Array : a ? ? a a a a _ _ _ _ _ _ _ a a //
4322:                 // expect: a a a a a a a _ _ _ _ _ _ _ _ _ //
4323:                 // //////////////////////////////////////////
4324:                 deque = new CircularArrayDeque<Object>();
4325:
4326:•                for (int i = 0; i < 15; i++) {
4327:                         deque.offer("a");
4328:                 }
4329:•                for (int i = 0; i < 14; i++) {
4330:                         deque.removeFirst();
4331:                 }
4332:                 deque.offer("a");
4333:                 deque.offer("a");
4334:                 deque.addAll(collection);
4335:•                for (int i = 0; i < 4; i++) {
4336:                         deque.offer("a");
4337:                 }
4338:
4339:                 deque.removeAll(collection);
4340:                 data = getInternalArray(deque);
4341:                 expected = new Object[] {"a", "a", "a", "a", "a", "a", "a", null, null, null, null, null, null, null,
4342:                                 null, null };
4343:                 assertEqualContent(expected, data);
4344:
4345:                 // //////////////////////////////////////////
4346:                 // Array : ? ? a a a a _ _ _ _ _ _ _ a a a //
4347:                 // expect: a a a a a a _ _ _ _ _ _ _ _ _ a //
4348:                 // //////////////////////////////////////////
4349:                 deque = new CircularArrayDeque<Object>();
4350:
4351:•                for (int i = 0; i < 15; i++) {
4352:                         deque.offer("a");
4353:                 }
4354:•                for (int i = 0; i < 13; i++) {
4355:                         deque.removeFirst();
4356:                 }
4357:                 deque.offer("a");
4358:                 deque.addAll(collection);
4359:•                for (int i = 0; i < 4; i++) {
4360:                         deque.offer("a");
4361:                 }
4362:
4363:                 deque.removeAll(collection);
4364:                 data = getInternalArray(deque);
4365:                 expected = new Object[] {"a", "a", "a", "a", "a", "a", null, null, null, null, null, null, null,
4366:                                 null, null, "a" };
4367:                 assertEqualContent(expected, data);
4368:
4369:                 // //////////////////////////////////////////
4370:                 // Array : ? a a a a _ _ _ _ _ _ _ a a a ? //
4371:                 // expect: a a a a a _ _ _ _ _ _ _ _ _ a a //
4372:                 // //////////////////////////////////////////
4373:                 deque = new CircularArrayDeque<Object>();
4374:
4375:•                for (int i = 0; i < 15; i++) {
4376:                         deque.offer("a");
4377:                 }
4378:•                for (int i = 0; i < 12; i++) {
4379:                         deque.removeFirst();
4380:                 }
4381:                 deque.addAll(collection);
4382:•                for (int i = 0; i < 4; i++) {
4383:                         deque.offer("a");
4384:                 }
4385:
4386:                 deque.removeAll(collection);
4387:                 data = getInternalArray(deque);
4388:                 expected = new Object[] {"a", "a", "a", "a", "a", null, null, null, null, null, null, null, null,
4389:                                 null, "a", "a" };
4390:                 assertEqualContent(expected, data);
4391:
4392:                 // //////////////////////////////////////////
4393:                 // Array : a a a a _ _ _ _ _ _ _ a a a ? ? //
4394:                 // expect: a a a a _ _ _ _ _ _ _ _ _ a a a //
4395:                 // //////////////////////////////////////////
4396:                 deque = new CircularArrayDeque<Object>();
4397:
4398:•                for (int i = 0; i < 14; i++) {
4399:                         deque.offer("a");
4400:                 }
4401:•                for (int i = 0; i < 11; i++) {
4402:                         deque.removeFirst();
4403:                 }
4404:                 deque.addAll(collection);
4405:•                for (int i = 0; i < 4; i++) {
4406:                         deque.offer("a");
4407:                 }
4408:
4409:                 deque.removeAll(collection);
4410:                 data = getInternalArray(deque);
4411:                 expected = new Object[] {"a", "a", "a", "a", null, null, null, null, null, null, null, null, null,
4412:                                 "a", "a", "a" };
4413:                 assertEqualContent(expected, data);
4414:         }
4415:
4416:         /**
4417:          * Tests the behavior of {@link CircularArrayDeque#remove(Object)} with the given element.
4418:          *
4419:          * @param element
4420:          * Element to remove from the deque.
4421:          */
4422:         private void internalTestRemoveLeftRotate(Object element) {
4423:                 // //////////////////////////////////////////
4424:                 // Array : _ _ _ _ _ _ _ _ a a a a ? a a a //
4425:                 // expect: _ _ _ _ _ _ _ _ a a a a a a a _ //
4426:                 // //////////////////////////////////////////
4427:                 Deque<Object> deque = new CircularArrayDeque<Object>();
4428:
4429:•                for (int i = 0; i < 12; i++) {
4430:                         deque.offer("a");
4431:                 }
4432:                 deque.offer(element);
4433:•                for (int i = 0; i < 8; i++) {
4434:                         deque.removeFirst();
4435:                 }
4436:•                for (int i = 0; i < 3; i++) {
4437:                         deque.offer("a");
4438:                 }
4439:
4440:                 deque.remove(element);
4441:                 Object[] data = getInternalArray(deque);
4442:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4443:                                 "a", "a", "a", null };
4444:                 assertEqualContent(expected, data);
4445:
4446:                 // //////////////////////////////////////////
4447:                 // Array : a _ _ _ _ _ _ _ _ a a a a ? a a //
4448:                 // expect: _ _ _ _ _ _ _ _ _ a a a a a a a //
4449:                 // //////////////////////////////////////////
4450:                 deque = new CircularArrayDeque<Object>();
4451:
4452:•                for (int i = 0; i < 13; i++) {
4453:                         deque.offer("a");
4454:                 }
4455:                 deque.offer(element);
4456:•                for (int i = 0; i < 9; i++) {
4457:                         deque.removeFirst();
4458:                 }
4459:•                for (int i = 0; i < 3; i++) {
4460:                         deque.offer("a");
4461:                 }
4462:
4463:                 deque.remove(element);
4464:                 data = getInternalArray(deque);
4465:                 expected = new Object[] {null, null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4466:                                 "a", "a", "a" };
4467:                 assertEqualContent(expected, data);
4468:
4469:                 // //////////////////////////////////////////
4470:                 // Array : a a a _ _ _ _ _ _ _ _ a a a a ? //
4471:                 // expect: a a _ _ _ _ _ _ _ _ _ a a a a a //
4472:                 // //////////////////////////////////////////
4473:                 deque = new CircularArrayDeque<Object>();
4474:
4475:•                for (int i = 0; i < 15; i++) {
4476:                         deque.offer("a");
4477:                 }
4478:•                for (int i = 0; i < 11; i++) {
4479:                         deque.removeFirst();
4480:                 }
4481:                 deque.offer(element);
4482:•                for (int i = 0; i < 3; i++) {
4483:                         deque.offer("a");
4484:                 }
4485:
4486:                 deque.remove(element);
4487:                 data = getInternalArray(deque);
4488:                 expected = new Object[] {"a", "a", null, null, null, null, null, null, null, null, null, "a", "a",
4489:                                 "a", "a", "a" };
4490:                 assertEqualContent(expected, data);
4491:
4492:                 // //////////////////////////////////////////
4493:                 // Array : ? a a a _ _ _ _ _ _ _ _ a a a a //
4494:                 // expect: a a a _ _ _ _ _ _ _ _ _ a a a a //
4495:                 // //////////////////////////////////////////
4496:                 deque = new CircularArrayDeque<Object>();
4497:
4498:•                for (int i = 0; i < 15; i++) {
4499:                         deque.offer("a");
4500:                 }
4501:•                for (int i = 0; i < 12; i++) {
4502:                         deque.removeFirst();
4503:                 }
4504:                 deque.offer("a");
4505:                 deque.offer(element);
4506:•                for (int i = 0; i < 3; i++) {
4507:                         deque.offer("a");
4508:                 }
4509:
4510:                 deque.remove(element);
4511:                 data = getInternalArray(deque);
4512:                 expected = new Object[] {"a", "a", "a", null, null, null, null, null, null, null, null, null, "a",
4513:                                 "a", "a", "a" };
4514:                 assertEqualContent(expected, data);
4515:         }
4516:
4517:         /**
4518:          * Tests the behavior of {@link CircularArrayDeque#remove(Object)} with the given element.
4519:          *
4520:          * @param element
4521:          * Element to remove from the deque.
4522:          */
4523:         private void internalTestRemoveRightRotate(Object element) {
4524:                 // //////////////////////////////////////////
4525:                 // Array : _ _ _ _ _ _ _ a a a ? a a a a _ //
4526:                 // expect: _ _ _ _ _ _ _ _ a a a a a a a _ //
4527:                 // //////////////////////////////////////////
4528:                 Deque<Object> deque = new CircularArrayDeque<Object>();
4529:
4530:•                for (int i = 0; i < 10; i++) {
4531:                         deque.offer("a");
4532:                 }
4533:                 deque.offer(element);
4534:•                for (int i = 0; i < 7; i++) {
4535:                         deque.removeFirst();
4536:                 }
4537:•                for (int i = 0; i < 4; i++) {
4538:                         deque.offer("a");
4539:                 }
4540:
4541:                 deque.remove(element);
4542:                 Object[] data = getInternalArray(deque);
4543:                 Object[] expected = new Object[] {null, null, null, null, null, null, null, null, "a", "a", "a", "a",
4544:                                 "a", "a", "a", null };
4545:                 assertEqualContent(expected, data);
4546:
4547:                 // //////////////////////////////////////////
4548:                 // Array : a a ? a a a a _ _ _ _ _ _ _ _ a //
4549:                 // expect: a a a a a a a _ _ _ _ _ _ _ _ _ //
4550:                 // //////////////////////////////////////////
4551:                 deque = new CircularArrayDeque<Object>();
4552:
4553:•                for (int i = 0; i < 15; i++) {
4554:                         deque.offer("a");
4555:                 }
4556:•                for (int i = 0; i < 14; i++) {
4557:                         deque.removeFirst();
4558:                 }
4559:                 deque.offer("a");
4560:                 deque.removeFirst();
4561:•                for (int i = 0; i < 2; i++) {
4562:                         deque.offer("a");
4563:                 }
4564:                 deque.offer(element);
4565:•                for (int i = 0; i < 4; i++) {
4566:                         deque.offer("a");
4567:                 }
4568:
4569:                 deque.remove(element);
4570:                 data = getInternalArray(deque);
4571:                 expected = new Object[] {"a", "a", "a", "a", "a", "a", "a", null, null, null, null, null, null, null,
4572:                                 null, null };
4573:                 assertEqualContent(expected, data);
4574:
4575:                 // //////////////////////////////////////////
4576:                 // Array : ? a a a a _ _ _ _ _ _ _ _ a a a //
4577:                 // expect: a a a a a _ _ _ _ _ _ _ _ _ a a //
4578:                 // //////////////////////////////////////////
4579:                 deque = new CircularArrayDeque<Object>();
4580:
4581:•                for (int i = 0; i < 15; i++) {
4582:                         deque.offer("a");
4583:                 }
4584:•                for (int i = 0; i < 13; i++) {
4585:                         deque.removeFirst();
4586:                 }
4587:                 deque.offer("a");
4588:                 deque.offer(element);
4589:•                for (int i = 0; i < 4; i++) {
4590:                         deque.offer("a");
4591:                 }
4592:
4593:                 deque.remove(element);
4594:                 data = getInternalArray(deque);
4595:                 expected = new Object[] {"a", "a", "a", "a", "a", null, null, null, null, null, null, null, null,
4596:                                 null, "a", "a" };
4597:                 assertEqualContent(expected, data);
4598:
4599:                 // //////////////////////////////////////////
4600:                 // Array : a a a a _ _ _ _ _ _ _ _ a a a ? //
4601:                 // expect: a a a a _ _ _ _ _ _ _ _ _ a a a //
4602:                 // //////////////////////////////////////////
4603:                 deque = new CircularArrayDeque<Object>();
4604:
4605:•                for (int i = 0; i < 15; i++) {
4606:                         deque.offer("a");
4607:                 }
4608:•                for (int i = 0; i < 12; i++) {
4609:                         deque.removeFirst();
4610:                 }
4611:                 deque.offer(element);
4612:•                for (int i = 0; i < 4; i++) {
4613:                         deque.offer("a");
4614:                 }
4615:
4616:                 deque.remove(element);
4617:                 data = getInternalArray(deque);
4618:                 expected = new Object[] {"a", "a", "a", "a", null, null, null, null, null, null, null, null, null,
4619:                                 "a", "a", "a" };
4620:                 assertEqualContent(expected, data);
4621:         }
4622:
4623:         /**
4624:          * Returns a list containing <code>size</code> random Integers.
4625:          *
4626:          * @param size
4627:          * Size of the list to create.
4628:          * @param excluded
4629:          * Values that cannot be in our returned list.
4630:          * @return A list containing <code>size</code> random Integers.
4631:          */
4632:         private List<Integer> randomIntegerListNotIn(int size, Collection<?> excluded) {
4633:                 List<Integer> list = new ArrayList<Integer>(size);
4634:•                for (int i = 0; i < size; i++) {
4635:                         Integer integer = getRandomInteger();
4636:•                        while (list.contains(integer) || excluded.contains(integer)) {
4637:                                 integer = getRandomInteger();
4638:                         }
4639:                         list.add(integer);
4640:                 }
4641:                 return list;
4642:         }
4643:
4644:         /**
4645:          * Returns a list containing <code>size</code> random Strings.
4646:          *
4647:          * @param size
4648:          * Size of the list to create.
4649:          * @param excluded
4650:          * Values that cannot be in our returned list.
4651:          * @return A list containing <code>size</code> random Strings.
4652:          */
4653:         private List<String> randomStringListNotIn(int size, Collection<?> excluded) {
4654:                 List<String> list = new ArrayList<String>(size);
4655:•                for (int i = 0; i < size; i++) {
4656:                         String string = getRandomString();
4657:•                        while (list.contains(string) || excluded.contains(string)) {
4658:                                 string = getRandomString();
4659:                         }
4660:                         list.add(string);
4661:                 }
4662:                 return list;
4663:         }
4664:
4665:         /**
4666:          * Returns a deque containing <code>size</code> random Strings.
4667:          *
4668:          * @param size
4669:          * Size of the deque to create.
4670:          * @param excluded
4671:          * Values that cannot be in our returned list.
4672:          * @return A deque containing <code>size</code> random Strings.
4673:          */
4674:         private Deque<String> randomStringDequeNotIn(int size, Collection<?> excluded) {
4675:                 Deque<String> deque = new CircularArrayDeque<String>(size);
4676:•                for (int i = 0; i < size; i++) {
4677:                         String s = getRandomString();
4678:•                        while (deque.contains(s) || excluded.contains(s)) {
4679:                                 s = getRandomString();
4680:                         }
4681:                         deque.add(s);
4682:                 }
4683:                 return deque;
4684:         }
4685:
4686:         /**
4687:          * Returns a set containing <code>size</code> random Strings.
4688:          *
4689:          * @param size
4690:          * Size of the set to create.
4691:          * @param excluded
4692:          * Values that cannot be in our returned list.
4693:          * @return A set containing <code>size</code> random Strings.
4694:          */
4695:         private Set<String> randomStringSetNotIn(int size, Collection<?> excluded) {
4696:                 Set<String> set = new HashSet<String>(size);
4697:•                for (int i = 0; i < size; i++) {
4698:                         String s = getRandomString();
4699:•                        while (set.contains(s) || excluded.contains(s)) {
4700:                                 s = getRandomString();
4701:                         }
4702:                         set.add(s);
4703:                 }
4704:                 return set;
4705:         }
4706:
4707:         /**
4708:          * Reads a Deque from the given string.
4709:          *
4710:          * @param serialized
4711:          * The serialized deque we are to read.
4712:          * @return The read Deque.
4713:          */
4714:         @SuppressWarnings("unchecked")
4715:         private Deque<Object> readDeque(byte[] serialized) {
4716:                 try {
4717:                         InputStream bais = new ByteArrayInputStream(serialized);
4718:                         ObjectInputStream stream = new ObjectInputStream(bais);
4719:                         Object read = stream.readObject();
4720:                         stream.close();
4721:•                        if (read instanceof Deque<?>) {
4722:                                 return (Deque<Object>)read;
4723:                         }
4724:                         fail("The read Object wasn't a Deque"); //$NON-NLS-1$
4725:                 } catch (ClassNotFoundException e) {
4726:                         fail("Unexpected ClassNotFoundException thrown"); //$NON-NLS-1$
4727:                 } catch (IOException e) {
4728:                         fail("Unexpected IOException thrown"); //$NON-NLS-1$        
4729:                 }
4730:                 return null;
4731:         }
4732:
4733:         /**
4734:          * Serializes the given deque to a String.
4735:          *
4736:          * @param deque
4737:          * The deque we are to serialize.
4738:          * @return The serialized deque.
4739:          */
4740:         private byte[] writeDeque(Deque<Object> deque) {
4741:                 try {
4742:                         ByteArrayOutputStream baos = new ByteArrayOutputStream();
4743:                         ObjectOutputStream stream = new ObjectOutputStream(baos);
4744:                         stream.writeObject(deque);
4745:                         stream.close();
4746:                         return baos.toByteArray();
4747:                 } catch (IOException e) {
4748:                         fail("Unexpected IOException thrown"); //$NON-NLS-1$
4749:                 }
4750:                 return new byte[0];
4751:         }
4752: }