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