001/*
002 *  Licensed to the Apache Software Foundation (ASF) under one
003 *  or more contributor license agreements.  See the NOTICE file
004 *  distributed with this work for additional information
005 *  regarding copyright ownership.  The ASF licenses this file
006 *  to you under the Apache License, Version 2.0 (the
007 *  "License"); you may not use this file except in compliance
008 *  with the License.  You may obtain a copy of the License at
009 *  
010 *    http://www.apache.org/licenses/LICENSE-2.0
011 *  
012 *  Unless required by applicable law or agreed to in writing,
013 *  software distributed under the License is distributed on an
014 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 *  KIND, either express or implied.  See the License for the
016 *  specific language governing permissions and limitations
017 *  under the License. 
018 *  
019 */
020package org.apache.mina.util;
021
022import static org.junit.Assert.assertEquals;
023import static org.junit.Assert.assertTrue;
024import static org.junit.Assert.fail;
025
026import java.util.Iterator;
027
028import org.junit.Before;
029import org.junit.Test;
030
031/**
032 * Tests {@link org.apache.mina.util.CircularQueue}
033 * 
034 * @author <a href="http://mina.apache.org">Apache MINA Project</a>
035 */
036public class CircularQueueTest {
037    private volatile int pushCount;
038
039    private volatile int popCount;
040
041    @Before
042    public void setUp() {
043        pushCount = 0;
044        popCount = 0;
045    }
046
047    @Test
048    public void testRotation() {
049        CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
050        testRotation0(q);
051    }
052
053    @Test
054    public void testExpandingRotation() {
055        CircularQueue<Integer> q = new CircularQueue<Integer>(); // DEFAULT_CAPACITY = 4
056        for (int i = 0; i < 10; i++) {
057            testRotation0(q);
058
059            // make expansion happen
060            int oldCapacity = q.capacity();
061            for (int j = q.capacity(); j >= 0; j--) {
062                q.offer(new Integer(++pushCount));
063            }
064
065            assertTrue(q.capacity() > oldCapacity);
066            testRotation0(q);
067        }
068    }
069
070    private void testRotation0(CircularQueue<Integer> q) {
071        for (int i = 0; i < q.capacity() * 7 / 4; i++) {
072            q.offer(new Integer(++pushCount));
073            assertEquals(++popCount, q.poll().intValue());
074        }
075    }
076
077    @Test
078    public void testRandomAddOnQueue() {
079        CircularQueue<Integer> q = new CircularQueue<Integer>();
080        // Create a queue with 5 elements and capacity 8;
081        for (int i = 0; i < 5; i++) {
082            q.offer(new Integer(i));
083        }
084
085        q.add(0, new Integer(100));
086        q.add(3, new Integer(200));
087        q.add(7, new Integer(300));
088
089        Iterator<Integer> i = q.iterator();
090        assertEquals(8, q.size());
091        assertEquals(new Integer(100), i.next());
092        assertEquals(new Integer(0), i.next());
093        assertEquals(new Integer(1), i.next());
094        assertEquals(new Integer(200), i.next());
095        assertEquals(new Integer(2), i.next());
096        assertEquals(new Integer(3), i.next());
097        assertEquals(new Integer(4), i.next());
098        assertEquals(new Integer(300), i.next());
099
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}