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 }