001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections.buffer; 018 019 import java.io.IOException; 020 import java.io.ObjectInputStream; 021 import java.io.ObjectOutputStream; 022 import java.io.Serializable; 023 import java.util.AbstractCollection; 024 import java.util.Iterator; 025 import java.util.NoSuchElementException; 026 027 import org.apache.commons.collections.Buffer; 028 import org.apache.commons.collections.BufferUnderflowException; 029 030 /** 031 * UnboundedFifoBuffer is a very efficient implementation of 032 * <code>Buffer</code> that can grow to any size. 033 * According to performance testing, it exhibits a constant access time, but it 034 * also outperforms ArrayList when used for the same purpose. 035 * <p> 036 * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion 037 * order; elements are removed in the same order in which they were added. 038 * The iteration order is the same as the removal order. 039 * <p> 040 * The {@link #remove()} and {@link #get()} operations perform in constant time. 041 * The {@link #add(Object)} operation performs in amortized constant time. All 042 * other operations perform in linear time or worse. 043 * <p> 044 * Note that this implementation is not synchronized. The following can be 045 * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>: 046 * <pre> 047 * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer()); 048 * </pre> 049 * <p> 050 * This buffer prevents null objects from being added. 051 * <p> 052 * This class is Serializable from Commons Collections 3.1. 053 * 054 * @since Commons Collections 3.0 (previously in main package v2.1) 055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 056 * 057 * @author Avalon 058 * @author Federico Barbieri 059 * @author Berin Loritsch 060 * @author Paul Jack 061 * @author Stephen Colebourne 062 * @author Andreas Schlosser 063 * @author Thomas Knych 064 * @author Jordan Krey 065 */ 066 public class UnboundedFifoBuffer extends AbstractCollection implements Buffer, Serializable { 067 // invariant: buffer.length > size() 068 // ie.buffer always has at least one empty entry 069 070 /** Serialization vesrion */ 071 private static final long serialVersionUID = -3482960336579541419L; 072 073 /** The array of objects in the buffer. */ 074 protected transient Object[] buffer; 075 /** The current head index. */ 076 protected transient int head; 077 /** The current tail index. */ 078 protected transient int tail; 079 080 /** 081 * Constructs an UnboundedFifoBuffer with the default number of elements. 082 * It is exactly the same as performing the following: 083 * 084 * <pre> 085 * new UnboundedFifoBuffer(32); 086 * </pre> 087 */ 088 public UnboundedFifoBuffer() { 089 this(32); 090 } 091 092 /** 093 * Constructs an UnboundedFifoBuffer with the specified number of elements. 094 * The integer must be a positive integer. 095 * 096 * @param initialSize the initial size of the buffer 097 * @throws IllegalArgumentException if the size is less than 1 098 */ 099 public UnboundedFifoBuffer(int initialSize) { 100 if (initialSize <= 0) { 101 throw new IllegalArgumentException("The size must be greater than 0"); 102 } 103 buffer = new Object[initialSize + 1]; 104 head = 0; 105 tail = 0; 106 } 107 108 //----------------------------------------------------------------------- 109 /** 110 * Write the buffer out using a custom routine. 111 * 112 * @param out the output stream 113 * @throws IOException 114 */ 115 private void writeObject(ObjectOutputStream out) throws IOException { 116 out.defaultWriteObject(); 117 out.writeInt(size()); 118 for (Iterator it = iterator(); it.hasNext();) { 119 out.writeObject(it.next()); 120 } 121 } 122 123 /** 124 * Read the buffer in using a custom routine. 125 * 126 * @param in the input stream 127 * @throws IOException 128 * @throws ClassNotFoundException 129 */ 130 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 131 in.defaultReadObject(); 132 int size = in.readInt(); 133 buffer = new Object[size + 1]; 134 for (int i = 0; i < size; i++) { 135 buffer[i] = in.readObject(); 136 } 137 head = 0; 138 tail = size; 139 } 140 141 //----------------------------------------------------------------------- 142 /** 143 * Returns the number of elements stored in the buffer. 144 * 145 * @return this buffer's size 146 */ 147 public int size() { 148 int size = 0; 149 150 if (tail < head) { 151 size = buffer.length - head + tail; 152 } else { 153 size = tail - head; 154 } 155 156 return size; 157 } 158 159 /** 160 * Returns true if this buffer is empty; false otherwise. 161 * 162 * @return true if this buffer is empty 163 */ 164 public boolean isEmpty() { 165 return (size() == 0); 166 } 167 168 /** 169 * Adds the given element to this buffer. 170 * 171 * @param obj the element to add 172 * @return true, always 173 * @throws NullPointerException if the given element is null 174 */ 175 public boolean add(final Object obj) { 176 if (obj == null) { 177 throw new NullPointerException("Attempted to add null object to buffer"); 178 } 179 180 if (size() + 1 >= buffer.length) { 181 // copy contents to a new buffer array 182 Object[] tmp = new Object[((buffer.length - 1) * 2) + 1]; 183 int j = 0; 184 // move head to element zero in the new array 185 for (int i = head; i != tail;) { 186 tmp[j] = buffer[i]; 187 buffer[i] = null; 188 189 j++; 190 i = increment(i); 191 } 192 buffer = tmp; 193 head = 0; 194 tail = j; 195 } 196 197 buffer[tail] = obj; 198 tail = increment(tail); 199 return true; 200 } 201 202 /** 203 * Returns the next object in the buffer. 204 * 205 * @return the next object in the buffer 206 * @throws BufferUnderflowException if this buffer is empty 207 */ 208 public Object get() { 209 if (isEmpty()) { 210 throw new BufferUnderflowException("The buffer is already empty"); 211 } 212 213 return buffer[head]; 214 } 215 216 /** 217 * Removes the next object from the buffer 218 * 219 * @return the removed object 220 * @throws BufferUnderflowException if this buffer is empty 221 */ 222 public Object remove() { 223 if (isEmpty()) { 224 throw new BufferUnderflowException("The buffer is already empty"); 225 } 226 227 Object element = buffer[head]; 228 if (element != null) { 229 buffer[head] = null; 230 head = increment(head); 231 } 232 return element; 233 } 234 235 /** 236 * Increments the internal index. 237 * 238 * @param index the index to increment 239 * @return the updated index 240 */ 241 private int increment(int index) { 242 index++; 243 if (index >= buffer.length) { 244 index = 0; 245 } 246 return index; 247 } 248 249 /** 250 * Decrements the internal index. 251 * 252 * @param index the index to decrement 253 * @return the updated index 254 */ 255 private int decrement(int index) { 256 index--; 257 if (index < 0) { 258 index = buffer.length - 1; 259 } 260 return index; 261 } 262 263 /** 264 * Returns an iterator over this buffer's elements. 265 * 266 * @return an iterator over this buffer's elements 267 */ 268 public Iterator iterator() { 269 return new Iterator() { 270 271 private int index = head; 272 private int lastReturnedIndex = -1; 273 274 public boolean hasNext() { 275 return index != tail; 276 277 } 278 279 public Object next() { 280 if (!hasNext()) { 281 throw new NoSuchElementException(); 282 } 283 lastReturnedIndex = index; 284 index = increment(index); 285 return buffer[lastReturnedIndex]; 286 } 287 288 public void remove() { 289 if (lastReturnedIndex == -1) { 290 throw new IllegalStateException(); 291 } 292 293 // First element can be removed quickly 294 if (lastReturnedIndex == head) { 295 UnboundedFifoBuffer.this.remove(); 296 lastReturnedIndex = -1; 297 return; 298 } 299 300 // Other elements require us to shift the subsequent elements 301 int i = increment(lastReturnedIndex); 302 while (i != tail) { 303 buffer[decrement(i)] = buffer[i]; 304 i = increment(i); 305 } 306 307 lastReturnedIndex = -1; 308 tail = decrement(tail); 309 buffer[tail] = null; 310 index = decrement(index); 311 } 312 313 }; 314 } 315 316 }