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.Iterator;
024: import java.util.NoSuchElementException;
025:
026: import org.apache.commons.collections.Buffer;
027: import org.apache.commons.collections.BufferUnderflowException;
028:
029: /**
030: * UnboundedFifoBuffer is a very efficient implementation of
031: * <code>Buffer</code> that can grow to any size.
032: * According to performance testing, it exhibits a constant access time, but it
033: * also outperforms ArrayList when used for the same purpose.
034: * <p>
035: * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
036: * order; elements are removed in the same order in which they were added.
037: * The iteration order is the same as the removal order.
038: * <p>
039: * The {@link #remove()} and {@link #get()} operations perform in constant time.
040: * The {@link #add(Object)} operation performs in amortized constant time. All
041: * other operations perform in linear time or worse.
042: * <p>
043: * Note that this implementation is not synchronized. The following can be
044: * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
045: * <pre>
046: * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
047: * </pre>
048: * <p>
049: * This buffer prevents null objects from being added.
050: * <p>
051: * This class is Serializable from Commons Collections 3.1.
052: *
053: * @since Commons Collections 3.0 (previously in main package v2.1)
054: * @version $Revision: 405927 $ $Date: 2006-05-12 23:57:03 +0100 (Fri, 12 May 2006) $
055: *
056: * @author Avalon
057: * @author Federico Barbieri
058: * @author Berin Loritsch
059: * @author Paul Jack
060: * @author Stephen Colebourne
061: * @author Andreas Schlosser
062: * @author Thomas Knych
063: * @author Jordan Krey
064: */
065: public class UnboundedFifoBuffer extends AbstractCollection implements
066: 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(
102: "The size must be greater than 0");
103: }
104: buffer = new Object[initialSize + 1];
105: head = 0;
106: tail = 0;
107: }
108:
109: //-----------------------------------------------------------------------
110: /**
111: * Write the buffer out using a custom routine.
112: *
113: * @param out the output stream
114: * @throws IOException
115: */
116: private void writeObject(ObjectOutputStream out) throws IOException {
117: out.defaultWriteObject();
118: out.writeInt(size());
119: for (Iterator it = iterator(); it.hasNext();) {
120: out.writeObject(it.next());
121: }
122: }
123:
124: /**
125: * Read the buffer in using a custom routine.
126: *
127: * @param in the input stream
128: * @throws IOException
129: * @throws ClassNotFoundException
130: */
131: private void readObject(ObjectInputStream in) throws IOException,
132: ClassNotFoundException {
133: in.defaultReadObject();
134: int size = in.readInt();
135: buffer = new Object[size + 1];
136: for (int i = 0; i < size; i++) {
137: buffer[i] = in.readObject();
138: }
139: head = 0;
140: tail = size;
141: }
142:
143: //-----------------------------------------------------------------------
144: /**
145: * Returns the number of elements stored in the buffer.
146: *
147: * @return this buffer's size
148: */
149: public int size() {
150: int size = 0;
151:
152: if (tail < head) {
153: size = buffer.length - head + tail;
154: } else {
155: size = tail - head;
156: }
157:
158: return size;
159: }
160:
161: /**
162: * Returns true if this buffer is empty; false otherwise.
163: *
164: * @return true if this buffer is empty
165: */
166: public boolean isEmpty() {
167: return (size() == 0);
168: }
169:
170: /**
171: * Adds the given element to this buffer.
172: *
173: * @param obj the element to add
174: * @return true, always
175: * @throws NullPointerException if the given element is null
176: */
177: public boolean add(final Object obj) {
178: if (obj == null) {
179: throw new NullPointerException(
180: "Attempted to add null object to buffer");
181: }
182:
183: if (size() + 1 >= buffer.length) {
184: // copy contents to a new buffer array
185: Object[] tmp = new Object[((buffer.length - 1) * 2) + 1];
186: int j = 0;
187: // move head to element zero in the new array
188: for (int i = head; i != tail;) {
189: tmp[j] = buffer[i];
190: buffer[i] = null;
191:
192: j++;
193: i = increment(i);
194: }
195: buffer = tmp;
196: head = 0;
197: tail = j;
198: }
199:
200: buffer[tail] = obj;
201: tail = increment(tail);
202: return true;
203: }
204:
205: /**
206: * Returns the next object in the buffer.
207: *
208: * @return the next object in the buffer
209: * @throws BufferUnderflowException if this buffer is empty
210: */
211: public Object get() {
212: if (isEmpty()) {
213: throw new BufferUnderflowException(
214: "The buffer is already empty");
215: }
216:
217: return buffer[head];
218: }
219:
220: /**
221: * Removes the next object from the buffer
222: *
223: * @return the removed object
224: * @throws BufferUnderflowException if this buffer is empty
225: */
226: public Object remove() {
227: if (isEmpty()) {
228: throw new BufferUnderflowException(
229: "The buffer is already empty");
230: }
231:
232: Object element = buffer[head];
233: if (element != null) {
234: buffer[head] = null;
235: head = increment(head);
236: }
237: return element;
238: }
239:
240: /**
241: * Increments the internal index.
242: *
243: * @param index the index to increment
244: * @return the updated index
245: */
246: private int increment(int index) {
247: index++;
248: if (index >= buffer.length) {
249: index = 0;
250: }
251: return index;
252: }
253:
254: /**
255: * Decrements the internal index.
256: *
257: * @param index the index to decrement
258: * @return the updated index
259: */
260: private int decrement(int index) {
261: index--;
262: if (index < 0) {
263: index = buffer.length - 1;
264: }
265: return index;
266: }
267:
268: /**
269: * Returns an iterator over this buffer's elements.
270: *
271: * @return an iterator over this buffer's elements
272: */
273: public Iterator iterator() {
274: return new Iterator() {
275:
276: private int index = head;
277: private int lastReturnedIndex = -1;
278:
279: public boolean hasNext() {
280: return index != tail;
281:
282: }
283:
284: public Object next() {
285: if (!hasNext()) {
286: throw new NoSuchElementException();
287: }
288: lastReturnedIndex = index;
289: index = increment(index);
290: return buffer[lastReturnedIndex];
291: }
292:
293: public void remove() {
294: if (lastReturnedIndex == -1) {
295: throw new IllegalStateException();
296: }
297:
298: // First element can be removed quickly
299: if (lastReturnedIndex == head) {
300: UnboundedFifoBuffer.this .remove();
301: lastReturnedIndex = -1;
302: return;
303: }
304:
305: // Other elements require us to shift the subsequent elements
306: int i = increment(lastReturnedIndex);
307: while (i != tail) {
308: buffer[decrement(i)] = buffer[i];
309: i = increment(i);
310: }
311:
312: lastReturnedIndex = -1;
313: tail = decrement(tail);
314: buffer[tail] = null;
315: index = decrement(index);
316: }
317:
318: };
319: }
320:
321: }
|