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.Arrays; 025 import java.util.Collection; 026 import java.util.Iterator; 027 import java.util.NoSuchElementException; 028 029 import org.apache.commons.collections.BoundedCollection; 030 import org.apache.commons.collections.Buffer; 031 import org.apache.commons.collections.BufferOverflowException; 032 import org.apache.commons.collections.BufferUnderflowException; 033 034 /** 035 * The BoundedFifoBuffer is a very efficient implementation of 036 * <code>Buffer</code> that is of a fixed size. 037 * <p> 038 * The removal order of a <code>BoundedFifoBuffer</code> is based on the 039 * insertion order; elements are removed in the same order in which they 040 * were added. The iteration order is the same as the removal order. 041 * <p> 042 * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations 043 * all perform in constant time. All other operations perform in linear 044 * time or worse. 045 * <p> 046 * Note that this implementation is not synchronized. The following can be 047 * used to provide synchronized access to your <code>BoundedFifoBuffer</code>: 048 * <pre> 049 * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer()); 050 * </pre> 051 * <p> 052 * This buffer prevents null objects from being added. 053 * <p> 054 * This class is Serializable from Commons Collections 3.1. 055 * 056 * @since Commons Collections 3.0 (previously in main package v2.1) 057 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 058 * 059 * @author Avalon 060 * @author Berin Loritsch 061 * @author Paul Jack 062 * @author Stephen Colebourne 063 * @author Herve Quiroz 064 */ 065 public class BoundedFifoBuffer extends AbstractCollection 066 implements Buffer, BoundedCollection, Serializable { 067 068 /** Serialization version */ 069 private static final long serialVersionUID = 5603722811189451017L; 070 071 /** Underlying storage array */ 072 private transient Object[] elements; 073 074 /** Array index of first (oldest) buffer element */ 075 private transient int start = 0; 076 077 /** 078 * Index mod maxElements of the array position following the last buffer 079 * element. Buffer elements start at elements[start] and "wrap around" 080 * elements[maxElements-1], ending at elements[decrement(end)]. 081 * For example, elements = {c,a,b}, start=1, end=1 corresponds to 082 * the buffer [a,b,c]. 083 */ 084 private transient int end = 0; 085 086 /** Flag to indicate if the buffer is currently full. */ 087 private transient boolean full = false; 088 089 /** Capacity of the buffer */ 090 private final int maxElements; 091 092 /** 093 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold 094 * 32 elements. 095 */ 096 public BoundedFifoBuffer() { 097 this(32); 098 } 099 100 /** 101 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold 102 * the specified number of elements. 103 * 104 * @param size the maximum number of elements for this fifo 105 * @throws IllegalArgumentException if the size is less than 1 106 */ 107 public BoundedFifoBuffer(int size) { 108 if (size <= 0) { 109 throw new IllegalArgumentException("The size must be greater than 0"); 110 } 111 elements = new Object[size]; 112 maxElements = elements.length; 113 } 114 115 /** 116 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all 117 * of the elements in the specified collection. That collection's 118 * elements will also be added to the buffer. 119 * 120 * @param coll the collection whose elements to add, may not be null 121 * @throws NullPointerException if the collection is null 122 */ 123 public BoundedFifoBuffer(Collection coll) { 124 this(coll.size()); 125 addAll(coll); 126 } 127 128 //----------------------------------------------------------------------- 129 /** 130 * Write the buffer out using a custom routine. 131 * 132 * @param out the output stream 133 * @throws IOException 134 */ 135 private void writeObject(ObjectOutputStream out) throws IOException { 136 out.defaultWriteObject(); 137 out.writeInt(size()); 138 for (Iterator it = iterator(); it.hasNext();) { 139 out.writeObject(it.next()); 140 } 141 } 142 143 /** 144 * Read the buffer in using a custom routine. 145 * 146 * @param in the input stream 147 * @throws IOException 148 * @throws ClassNotFoundException 149 */ 150 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 151 in.defaultReadObject(); 152 elements = new Object[maxElements]; 153 int size = in.readInt(); 154 for (int i = 0; i < size; i++) { 155 elements[i] = in.readObject(); 156 } 157 start = 0; 158 full = (size == maxElements); 159 if (full) { 160 end = 0; 161 } else { 162 end = size; 163 } 164 } 165 166 //----------------------------------------------------------------------- 167 /** 168 * Returns the number of elements stored in the buffer. 169 * 170 * @return this buffer's size 171 */ 172 public int size() { 173 int size = 0; 174 175 if (end < start) { 176 size = maxElements - start + end; 177 } else if (end == start) { 178 size = (full ? maxElements : 0); 179 } else { 180 size = end - start; 181 } 182 183 return size; 184 } 185 186 /** 187 * Returns true if this buffer is empty; false otherwise. 188 * 189 * @return true if this buffer is empty 190 */ 191 public boolean isEmpty() { 192 return size() == 0; 193 } 194 195 /** 196 * Returns true if this collection is full and no new elements can be added. 197 * 198 * @return <code>true</code> if the collection is full 199 */ 200 public boolean isFull() { 201 return size() == maxElements; 202 } 203 204 /** 205 * Gets the maximum size of the collection (the bound). 206 * 207 * @return the maximum number of elements the collection can hold 208 */ 209 public int maxSize() { 210 return maxElements; 211 } 212 213 /** 214 * Clears this buffer. 215 */ 216 public void clear() { 217 full = false; 218 start = 0; 219 end = 0; 220 Arrays.fill(elements, null); 221 } 222 223 /** 224 * Adds the given element to this buffer. 225 * 226 * @param element the element to add 227 * @return true, always 228 * @throws NullPointerException if the given element is null 229 * @throws BufferOverflowException if this buffer is full 230 */ 231 public boolean add(Object element) { 232 if (null == element) { 233 throw new NullPointerException("Attempted to add null object to buffer"); 234 } 235 236 if (full) { 237 throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects."); 238 } 239 240 elements[end++] = element; 241 242 if (end >= maxElements) { 243 end = 0; 244 } 245 246 if (end == start) { 247 full = true; 248 } 249 250 return true; 251 } 252 253 /** 254 * Returns the least recently inserted element in this buffer. 255 * 256 * @return the least recently inserted element 257 * @throws BufferUnderflowException if the buffer is empty 258 */ 259 public Object get() { 260 if (isEmpty()) { 261 throw new BufferUnderflowException("The buffer is already empty"); 262 } 263 264 return elements[start]; 265 } 266 267 /** 268 * Removes the least recently inserted element from this buffer. 269 * 270 * @return the least recently inserted element 271 * @throws BufferUnderflowException if the buffer is empty 272 */ 273 public Object remove() { 274 if (isEmpty()) { 275 throw new BufferUnderflowException("The buffer is already empty"); 276 } 277 278 Object element = elements[start]; 279 280 if (null != element) { 281 elements[start++] = null; 282 283 if (start >= maxElements) { 284 start = 0; 285 } 286 287 full = false; 288 } 289 290 return element; 291 } 292 293 /** 294 * Increments the internal index. 295 * 296 * @param index the index to increment 297 * @return the updated index 298 */ 299 private int increment(int index) { 300 index++; 301 if (index >= maxElements) { 302 index = 0; 303 } 304 return index; 305 } 306 307 /** 308 * Decrements the internal index. 309 * 310 * @param index the index to decrement 311 * @return the updated index 312 */ 313 private int decrement(int index) { 314 index--; 315 if (index < 0) { 316 index = maxElements - 1; 317 } 318 return index; 319 } 320 321 /** 322 * Returns an iterator over this buffer's elements. 323 * 324 * @return an iterator over this buffer's elements 325 */ 326 public Iterator iterator() { 327 return new Iterator() { 328 329 private int index = start; 330 private int lastReturnedIndex = -1; 331 private boolean isFirst = full; 332 333 public boolean hasNext() { 334 return isFirst || (index != end); 335 336 } 337 338 public Object next() { 339 if (!hasNext()) { 340 throw new NoSuchElementException(); 341 } 342 isFirst = false; 343 lastReturnedIndex = index; 344 index = increment(index); 345 return elements[lastReturnedIndex]; 346 } 347 348 public void remove() { 349 if (lastReturnedIndex == -1) { 350 throw new IllegalStateException(); 351 } 352 353 // First element can be removed quickly 354 if (lastReturnedIndex == start) { 355 BoundedFifoBuffer.this.remove(); 356 lastReturnedIndex = -1; 357 return; 358 } 359 360 int pos = lastReturnedIndex + 1; 361 if (start < lastReturnedIndex && pos < end) { 362 // shift in one part 363 System.arraycopy(elements, pos, elements, 364 lastReturnedIndex, end - pos); 365 } else { 366 // Other elements require us to shift the subsequent elements 367 while (pos != end) { 368 if (pos >= maxElements) { 369 elements[pos - 1] = elements[0]; 370 pos = 0; 371 } else { 372 elements[decrement(pos)] = elements[pos]; 373 pos = increment(pos); 374 } 375 } 376 } 377 378 lastReturnedIndex = -1; 379 end = decrement(end); 380 elements[end] = null; 381 full = false; 382 index = decrement(index); 383 } 384 385 }; 386 } 387 388 }