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}