1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.mina.util;
21
22 import static org.junit.Assert.assertEquals;
23 import static org.junit.Assert.assertTrue;
24 import static org.junit.Assert.fail;
25
26 import java.util.Iterator;
27
28 import org.junit.Before;
29 import org.junit.Test;
30
31
32
33
34
35
36 public class CircularQueueTest {
37 private volatile int pushCount;
38
39 private volatile int popCount;
40
41 @Before
42 public void setUp() {
43 pushCount = 0;
44 popCount = 0;
45 }
46
47 @Test
48 public void testRotation() {
49 CircularQueue<Integer> q = new CircularQueue<>();
50 testRotation0(q);
51 }
52
53 @Test
54 public void testExpandingRotation() {
55 CircularQueue<Integer> q = new CircularQueue<>();
56 for (int i = 0; i < 10; i++) {
57 testRotation0(q);
58
59
60 int oldCapacity = q.capacity();
61 for (int j = q.capacity(); j >= 0; j--) {
62 q.offer(new Integer(++pushCount));
63 }
64
65 assertTrue(q.capacity() > oldCapacity);
66 testRotation0(q);
67 }
68 }
69
70 private void testRotation0(CircularQueue<Integer> q) {
71 for (int i = 0; i < q.capacity() * 7 / 4; i++) {
72 q.offer(new Integer(++pushCount));
73 assertEquals(++popCount, q.poll().intValue());
74 }
75 }
76
77 @Test
78 public void testRandomAddOnQueue() {
79 CircularQueue<Integer> q = new CircularQueue<>();
80
81 for (int i = 0; i < 5; i++) {
82 q.offer(new Integer(i));
83 }
84
85 q.add(0, new Integer(100));
86 q.add(3, new Integer(200));
87 q.add(7, new Integer(300));
88
89 Iterator<Integer> i = q.iterator();
90 assertEquals(8, q.size());
91 assertEquals(new Integer(100), i.next());
92 assertEquals(new Integer(0), i.next());
93 assertEquals(new Integer(1), i.next());
94 assertEquals(new Integer(200), i.next());
95 assertEquals(new Integer(2), i.next());
96 assertEquals(new Integer(3), i.next());
97 assertEquals(new Integer(4), i.next());
98 assertEquals(new Integer(300), i.next());
99
100 try {
101 i.next();
102 fail();
103 } catch (Exception e) {
104
105 assertTrue(true);
106 }
107 }
108
109 @Test
110 public void testRandomAddOnRotatedQueue() {
111 CircularQueue<Integer> q = getRotatedQueue();
112
113 q.add(0, new Integer(100));
114 q.add(2, new Integer(200));
115 q.add(4, new Integer(300));
116 q.add(10, new Integer(400));
117 q.add(12, new Integer(500));
118
119 Iterator<Integer> i = q.iterator();
120 assertEquals(13, q.size());
121 assertEquals(new Integer(100), i.next());
122 assertEquals(new Integer(0), i.next());
123 assertEquals(new Integer(200), i.next());
124 assertEquals(new Integer(1), i.next());
125 assertEquals(new Integer(300), i.next());
126 assertEquals(new Integer(2), i.next());
127 assertEquals(new Integer(3), i.next());
128 assertEquals(new Integer(4), i.next());
129 assertEquals(new Integer(5), i.next());
130 assertEquals(new Integer(6), i.next());
131 assertEquals(new Integer(400), i.next());
132 assertEquals(new Integer(7), i.next());
133 assertEquals(new Integer(500), i.next());
134
135 try {
136 i.next();
137 fail();
138 } catch (Exception e) {
139
140 assertTrue(true);
141 }
142 }
143
144 @Test
145 public void testRandomRemoveOnQueue() {
146 CircularQueue<Integer> q = new CircularQueue<>();
147
148
149 for (int i = 0; i < 5; i++) {
150 q.offer(new Integer(i));
151 }
152
153 q.remove(0);
154 q.remove(2);
155 q.remove(2);
156
157 Iterator<Integer> i = q.iterator();
158 assertEquals(2, q.size());
159 assertEquals(new Integer(1), i.next());
160 assertEquals(new Integer(2), i.next());
161
162 try {
163 i.next();
164 fail();
165 } catch (Exception e) {
166
167 assertTrue(true);
168 }
169 }
170
171 @Test
172 public void testRandomRemoveOnRotatedQueue() {
173 CircularQueue<Integer> q = getRotatedQueue();
174
175 q.remove(0);
176 q.remove(2);
177 q.remove(2);
178 q.remove(4);
179
180 Iterator<Integer> i = q.iterator();
181 assertEquals(4, q.size());
182 assertEquals(new Integer(1), i.next());
183 assertEquals(new Integer(2), i.next());
184 assertEquals(new Integer(5), i.next());
185 assertEquals(new Integer(6), i.next());
186
187 try {
188 i.next();
189 fail();
190 } catch (Exception e) {
191
192 assertTrue(true);
193 }
194 }
195
196 @Test
197 public void testExpandAndShrink() throws Exception {
198 CircularQueue<Integer> q = new CircularQueue<>();
199 for (int i = 0; i < 1024; i++) {
200 q.offer(i);
201 }
202
203 assertEquals(1024, q.capacity());
204
205 for (int i = 0; i < 512; i++) {
206 q.offer(i);
207 q.poll();
208 }
209
210 assertEquals(2048, q.capacity());
211
212 for (int i = 0; i < 1024; i++) {
213 q.poll();
214 }
215
216 assertEquals(4, q.capacity());
217 }
218
219 private CircularQueue<Integer> getRotatedQueue() {
220 CircularQueue<Integer> q = new CircularQueue<>();
221
222
223 for (int i = 0; i < 16; i++) {
224 q.offer(new Integer(-1));
225 }
226 q.clear();
227
228
229 for (int i = 0; i < 12; i++) {
230 q.offer(new Integer(-1));
231 q.poll();
232 }
233
234
235 for (int i = 0; i < 8; i++) {
236 q.offer(new Integer(i));
237 }
238
239 return q;
240 }
241 }