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 junit.framework.TestCase;
23  
24  import java.util.Iterator;
25  
26  /**
27   * Tests {@link org.apache.mina.util.CircularQueue}
28   * 
29   * @author The Apache MINA Project (dev@mina.apache.org)
30   * @version $Rev: 755170 $, $Date: 2009-03-17 10:46:58 +0100 (Tue, 17 Mar 2009) $
31   */
32  public class CircularQueueTest extends TestCase {
33      private volatile int pushCount;
34      private volatile int popCount;
35  
36      public void setUp() {
37          pushCount = 0;
38          popCount = 0;
39      }
40  
41      public void testRotation() {
42          CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
43          testRotation0(q);
44      }
45  
46      public void testExpandingRotation() {
47          CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
48          for (int i = 0; i < 10; i++) {
49              testRotation0(q);
50  
51              // make expansion happen
52              int oldCapacity = q.capacity();
53              for (int j = q.capacity(); j >= 0; j--) {
54                  q.offer(new Integer(++pushCount));
55              }
56  
57              assertTrue(q.capacity() > oldCapacity);
58              testRotation0(q);
59          }
60      }
61  
62      private void testRotation0(CircularQueue<Integer> q) {
63          for (int i = 0; i < q.capacity() * 7 / 4; i++) {
64              q.offer(new Integer(++pushCount));
65              assertEquals(++popCount, q.poll().intValue());
66          }
67      }
68  
69      public void testRandomAddOnQueue() {
70          CircularQueue<Integer> q = new CircularQueue<Integer>();
71          // Create a queue with 5 elements and capacity 8;
72          for (int i = 0; i < 5; i++) {
73              q.offer(new Integer(i));
74          }
75  
76          q.add(0, new Integer(100));
77          q.add(3, new Integer(200));
78          q.add(7, new Integer(300));
79  
80          Iterator<Integer> i = q.iterator();
81          assertEquals(8, q.size());
82          assertEquals(new Integer(100), i.next());
83          assertEquals(new Integer(0), i.next());
84          assertEquals(new Integer(1), i.next());
85          assertEquals(new Integer(200), i.next());
86          assertEquals(new Integer(2), i.next());
87          assertEquals(new Integer(3), i.next());
88          assertEquals(new Integer(4), i.next());
89          assertEquals(new Integer(300), i.next());
90  
91          try {
92              i.next();
93              fail();
94          } catch (Exception e) {
95              // an exception signifies a successfull test case
96              assertTrue(true);            
97          }
98      }
99  
100     public void testRandomAddOnRotatedQueue() {
101         CircularQueue<Integer> q = getRotatedQueue();
102 
103         q.add(0, new Integer(100)); // addFirst
104         q.add(2, new Integer(200));
105         q.add(4, new Integer(300));
106         q.add(10, new Integer(400));
107         q.add(12, new Integer(500)); // addLast
108 
109         Iterator<Integer> i = q.iterator();
110         assertEquals(13, q.size());
111         assertEquals(new Integer(100), i.next());
112         assertEquals(new Integer(0), i.next());
113         assertEquals(new Integer(200), i.next());
114         assertEquals(new Integer(1), i.next());
115         assertEquals(new Integer(300), i.next());
116         assertEquals(new Integer(2), i.next());
117         assertEquals(new Integer(3), i.next());
118         assertEquals(new Integer(4), i.next());
119         assertEquals(new Integer(5), i.next());
120         assertEquals(new Integer(6), i.next());
121         assertEquals(new Integer(400), i.next());
122         assertEquals(new Integer(7), i.next());
123         assertEquals(new Integer(500), i.next());
124 
125         try {
126             i.next();
127             fail();
128         } catch (Exception e) {
129             // an exception signifies a successfull test case
130             assertTrue(true);
131         }
132     }
133 
134     public void testRandomRemoveOnQueue() {
135         CircularQueue<Integer> q = new CircularQueue<Integer>();
136 
137         // Create a queue with 5 elements and capacity 8;
138         for (int i = 0; i < 5; i++) {
139             q.offer(new Integer(i));
140         }
141 
142         q.remove(0);
143         q.remove(2);
144         q.remove(2);
145 
146         Iterator<Integer> i = q.iterator();
147         assertEquals(2, q.size());
148         assertEquals(new Integer(1), i.next());
149         assertEquals(new Integer(2), i.next());
150 
151         try {
152             i.next();
153             fail();
154         } catch (Exception e) {
155             // an exception signifies a successfull test case
156             assertTrue(true);
157         }
158     }
159 
160     public void testRandomRemoveOnRotatedQueue() {
161         CircularQueue<Integer> q = getRotatedQueue();
162 
163         q.remove(0); // removeFirst
164         q.remove(2); // removeLast in the first half
165         q.remove(2); // removeFirst in the first half
166         q.remove(4); // removeLast
167 
168         Iterator<Integer> i = q.iterator();
169         assertEquals(4, q.size());
170         assertEquals(new Integer(1), i.next());
171         assertEquals(new Integer(2), i.next());
172         assertEquals(new Integer(5), i.next());
173         assertEquals(new Integer(6), i.next());
174 
175         try {
176             i.next();
177             fail();
178         } catch (Exception e) {
179             // an exception signifies a successfull test case
180             assertTrue(true);            
181         }
182     }
183     
184     public void testExpandAndShrink() throws Exception {
185         CircularQueue<Integer> q = new CircularQueue<Integer>();
186         for (int i = 0; i < 1024; i ++) {
187             q.offer(i);
188         }
189         
190         assertEquals(1024, q.capacity());
191         
192         for (int i = 0; i < 512; i ++) {
193             q.offer(i);
194             q.poll();
195         }
196         
197         assertEquals(2048, q.capacity());
198         
199         for (int i = 0; i < 1024; i ++) { 
200             q.poll();
201         }
202         
203         assertEquals(4, q.capacity());
204     }
205 
206     private CircularQueue<Integer> getRotatedQueue() {
207         CircularQueue<Integer> q = new CircularQueue<Integer>();
208 
209         // Ensure capacity: 16
210         for (int i = 0; i < 16; i++) {
211             q.offer(new Integer(-1));
212         }
213         q.clear();
214 
215         // Rotate it
216         for (int i = 0; i < 12; i++) {
217             q.offer(new Integer(-1));
218             q.poll();
219         }
220 
221         // Now push items
222         for (int i = 0; i < 8; i++) {
223             q.offer(new Integer(i));
224         }
225 
226         return q;
227     }
228 
229     public static void main(String[] args) {
230         junit.textui.TestRunner.run(CircularQueueTest.class);
231     }
232 }