001: /*
002: * Copyright 2002-2006 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.buffer;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.util.AbstractCollection;
023: import java.util.Arrays;
024: import java.util.Collection;
025: import java.util.Iterator;
026: import java.util.NoSuchElementException;
027:
028: import org.apache.commons.collections.BoundedCollection;
029: import org.apache.commons.collections.Buffer;
030: import org.apache.commons.collections.BufferOverflowException;
031: import org.apache.commons.collections.BufferUnderflowException;
032:
033: /**
034: * The BoundedFifoBuffer is a very efficient implementation of
035: * <code>Buffer</code> that is of a fixed size.
036: * <p>
037: * The removal order of a <code>BoundedFifoBuffer</code> is based on the
038: * insertion order; elements are removed in the same order in which they
039: * were added. The iteration order is the same as the removal order.
040: * <p>
041: * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
042: * all perform in constant time. All other operations perform in linear
043: * time or worse.
044: * <p>
045: * Note that this implementation is not synchronized. The following can be
046: * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
047: * <pre>
048: * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
049: * </pre>
050: * <p>
051: * This buffer prevents null objects from being added.
052: * <p>
053: * This class is Serializable from Commons Collections 3.1.
054: *
055: * @since Commons Collections 3.0 (previously in main package v2.1)
056: * @version $Revision: 405927 $ $Date: 2006-05-12 23:57:03 +0100 (Fri, 12 May 2006) $
057: *
058: * @author Avalon
059: * @author Berin Loritsch
060: * @author Paul Jack
061: * @author Stephen Colebourne
062: * @author Herve Quiroz
063: */
064: public class BoundedFifoBuffer extends AbstractCollection implements
065: Buffer, BoundedCollection, Serializable {
066:
067: /** Serialization version */
068: private static final long serialVersionUID = 5603722811189451017L;
069:
070: /** Underlying storage array */
071: private transient Object[] elements;
072:
073: /** Array index of first (oldest) buffer element */
074: private transient int start = 0;
075:
076: /**
077: * Index mod maxElements of the array position following the last buffer
078: * element. Buffer elements start at elements[start] and "wrap around"
079: * elements[maxElements-1], ending at elements[decrement(end)].
080: * For example, elements = {c,a,b}, start=1, end=1 corresponds to
081: * the buffer [a,b,c].
082: */
083: private transient int end = 0;
084:
085: /** Flag to indicate if the buffer is currently full. */
086: private transient boolean full = false;
087:
088: /** Capacity of the buffer */
089: private final int maxElements;
090:
091: /**
092: * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
093: * 32 elements.
094: */
095: public BoundedFifoBuffer() {
096: this (32);
097: }
098:
099: /**
100: * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
101: * the specified number of elements.
102: *
103: * @param size the maximum number of elements for this fifo
104: * @throws IllegalArgumentException if the size is less than 1
105: */
106: public BoundedFifoBuffer(int size) {
107: if (size <= 0) {
108: throw new IllegalArgumentException(
109: "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,
151: ClassNotFoundException {
152: in.defaultReadObject();
153: elements = new Object[maxElements];
154: int size = in.readInt();
155: for (int i = 0; i < size; i++) {
156: elements[i] = in.readObject();
157: }
158: start = 0;
159: full = (size == maxElements);
160: if (full) {
161: end = 0;
162: } else {
163: end = size;
164: }
165: }
166:
167: //-----------------------------------------------------------------------
168: /**
169: * Returns the number of elements stored in the buffer.
170: *
171: * @return this buffer's size
172: */
173: public int size() {
174: int size = 0;
175:
176: if (end < start) {
177: size = maxElements - start + end;
178: } else if (end == start) {
179: size = (full ? maxElements : 0);
180: } else {
181: size = end - start;
182: }
183:
184: return size;
185: }
186:
187: /**
188: * Returns true if this buffer is empty; false otherwise.
189: *
190: * @return true if this buffer is empty
191: */
192: public boolean isEmpty() {
193: return size() == 0;
194: }
195:
196: /**
197: * Returns true if this collection is full and no new elements can be added.
198: *
199: * @return <code>true</code> if the collection is full
200: */
201: public boolean isFull() {
202: return size() == maxElements;
203: }
204:
205: /**
206: * Gets the maximum size of the collection (the bound).
207: *
208: * @return the maximum number of elements the collection can hold
209: */
210: public int maxSize() {
211: return maxElements;
212: }
213:
214: /**
215: * Clears this buffer.
216: */
217: public void clear() {
218: full = false;
219: start = 0;
220: end = 0;
221: Arrays.fill(elements, null);
222: }
223:
224: /**
225: * Adds the given element to this buffer.
226: *
227: * @param element the element to add
228: * @return true, always
229: * @throws NullPointerException if the given element is null
230: * @throws BufferOverflowException if this buffer is full
231: */
232: public boolean add(Object element) {
233: if (null == element) {
234: throw new NullPointerException(
235: "Attempted to add null object to buffer");
236: }
237:
238: if (full) {
239: throw new BufferOverflowException(
240: "The buffer cannot hold more than " + maxElements
241: + " objects.");
242: }
243:
244: elements[end++] = element;
245:
246: if (end >= maxElements) {
247: end = 0;
248: }
249:
250: if (end == start) {
251: full = true;
252: }
253:
254: return true;
255: }
256:
257: /**
258: * Returns the least recently inserted element in this buffer.
259: *
260: * @return the least recently inserted element
261: * @throws BufferUnderflowException if the buffer is empty
262: */
263: public Object get() {
264: if (isEmpty()) {
265: throw new BufferUnderflowException(
266: "The buffer is already empty");
267: }
268:
269: return elements[start];
270: }
271:
272: /**
273: * Removes the least recently inserted element from this buffer.
274: *
275: * @return the least recently inserted element
276: * @throws BufferUnderflowException if the buffer is empty
277: */
278: public Object remove() {
279: if (isEmpty()) {
280: throw new BufferUnderflowException(
281: "The buffer is already empty");
282: }
283:
284: Object element = elements[start];
285:
286: if (null != element) {
287: elements[start++] = null;
288:
289: if (start >= maxElements) {
290: start = 0;
291: }
292:
293: full = false;
294: }
295:
296: return element;
297: }
298:
299: /**
300: * Increments the internal index.
301: *
302: * @param index the index to increment
303: * @return the updated index
304: */
305: private int increment(int index) {
306: index++;
307: if (index >= maxElements) {
308: index = 0;
309: }
310: return index;
311: }
312:
313: /**
314: * Decrements the internal index.
315: *
316: * @param index the index to decrement
317: * @return the updated index
318: */
319: private int decrement(int index) {
320: index--;
321: if (index < 0) {
322: index = maxElements - 1;
323: }
324: return index;
325: }
326:
327: /**
328: * Returns an iterator over this buffer's elements.
329: *
330: * @return an iterator over this buffer's elements
331: */
332: public Iterator iterator() {
333: return new Iterator() {
334:
335: private int index = start;
336: private int lastReturnedIndex = -1;
337: private boolean isFirst = full;
338:
339: public boolean hasNext() {
340: return isFirst || (index != end);
341:
342: }
343:
344: public Object next() {
345: if (!hasNext()) {
346: throw new NoSuchElementException();
347: }
348: isFirst = false;
349: lastReturnedIndex = index;
350: index = increment(index);
351: return elements[lastReturnedIndex];
352: }
353:
354: public void remove() {
355: if (lastReturnedIndex == -1) {
356: throw new IllegalStateException();
357: }
358:
359: // First element can be removed quickly
360: if (lastReturnedIndex == start) {
361: BoundedFifoBuffer.this .remove();
362: lastReturnedIndex = -1;
363: return;
364: }
365:
366: int pos = lastReturnedIndex + 1;
367: if (start < lastReturnedIndex && pos < end) {
368: // shift in one part
369: System.arraycopy(elements, pos, elements,
370: lastReturnedIndex, end - pos);
371: } else {
372: // Other elements require us to shift the subsequent elements
373: while (pos != end) {
374: if (pos >= maxElements) {
375: elements[pos - 1] = elements[0];
376: pos = 0;
377: } else {
378: elements[decrement(pos)] = elements[pos];
379: pos = increment(pos);
380: }
381: }
382: }
383:
384: lastReturnedIndex = -1;
385: end = decrement(end);
386: elements[end] = null;
387: full = false;
388: index = decrement(index);
389: }
390:
391: };
392: }
393:
394: }
|