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