View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
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   * Tests {@link org.apache.mina.util.CircularQueue}
33   * 
34   * @author <a href="http://mina.apache.org">Apache MINA Project</a>
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<Integer>(); // DEFAULT_CAPACITY = 4
50          testRotation0(q);
51      }
52  
53      @Test
54      public void testExpandingRotation() {
55          CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
56          for (int i = 0; i < 10; i++) {
57              testRotation0(q);
58  
59              // make expansion happen
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<Integer>();
80          // Create a queue with 5 elements and capacity 8;
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             // an exception signifies a successfull test case
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)); // addFirst
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)); // addLast
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             // an exception signifies a successfull test case
140             assertTrue(true);
141         }
142     }
143 
144     @Test
145     public void testRandomRemoveOnQueue() {
146         CircularQueue<Integer> q = new CircularQueue<Integer>();
147 
148         // Create a queue with 5 elements and capacity 8;
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             // an exception signifies a successfull test case
167             assertTrue(true);
168         }
169     }
170 
171     @Test
172     public void testRandomRemoveOnRotatedQueue() {
173         CircularQueue<Integer> q = getRotatedQueue();
174 
175         q.remove(0); // removeFirst
176         q.remove(2); // removeLast in the first half
177         q.remove(2); // removeFirst in the first half
178         q.remove(4); // removeLast
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             // an exception signifies a successfull test case
192             assertTrue(true);
193         }
194     }
195 
196     @Test
197     public void testExpandAndShrink() throws Exception {
198         CircularQueue<Integer> q = new CircularQueue<Integer>();
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<Integer>();
221 
222         // Ensure capacity: 16
223         for (int i = 0; i < 16; i++) {
224             q.offer(new Integer(-1));
225         }
226         q.clear();
227 
228         // Rotate it
229         for (int i = 0; i < 12; i++) {
230             q.offer(new Integer(-1));
231             q.poll();
232         }
233 
234         // Now push items
235         for (int i = 0; i < 8; i++) {
236             q.offer(new Integer(i));
237         }
238 
239         return q;
240     }
241 }