001: /*
002: * Copyright 2002-2004 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;
017:
018: import java.util.AbstractCollection;
019: import java.util.Iterator;
020: import java.util.NoSuchElementException;
021:
022: /**
023: * UnboundedFifoBuffer is a very efficient buffer implementation.
024: * According to performance testing, it exhibits a constant access time, but it
025: * also outperforms ArrayList when used for the same purpose.
026: * <p>
027: * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
028: * order; elements are removed in the same order in which they were added.
029: * The iteration order is the same as the removal order.
030: * <p>
031: * The {@link #remove()} and {@link #get()} operations perform in constant time.
032: * The {@link #add(Object)} operation performs in amortized constant time. All
033: * other operations perform in linear time or worse.
034: * <p>
035: * Note that this implementation is not synchronized. The following can be
036: * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
037: * <pre>
038: * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
039: * </pre>
040: * <p>
041: * This buffer prevents null objects from being added.
042: *
043: * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
044: * @since Commons Collections 2.1
045: * @version $Revision: 219316 $ $Date: 2005-07-16 12:17:02 +0100 (Sat, 16 Jul 2005) $
046: *
047: * @author Avalon
048: * @author Federico Barbieri
049: * @author Berin Loritsch
050: * @author Paul Jack
051: * @author Stephen Colebourne
052: * @author Andreas Schlosser
053: */
054: public class UnboundedFifoBuffer extends AbstractCollection implements
055: Buffer {
056:
057: protected Object[] m_buffer;
058: protected int m_head;
059: protected int m_tail;
060:
061: /**
062: * Constructs an UnboundedFifoBuffer with the default number of elements.
063: * It is exactly the same as performing the following:
064: *
065: * <pre>
066: * new UnboundedFifoBuffer(32);
067: * </pre>
068: */
069: public UnboundedFifoBuffer() {
070: this (32);
071: }
072:
073: /**
074: * Constructs an UnboundedFifoBuffer with the specified number of elements.
075: * The integer must be a positive integer.
076: *
077: * @param initialSize the initial size of the buffer
078: * @throws IllegalArgumentException if the size is less than 1
079: */
080: public UnboundedFifoBuffer(int initialSize) {
081: if (initialSize <= 0) {
082: throw new IllegalArgumentException(
083: "The size must be greater than 0");
084: }
085: m_buffer = new Object[initialSize + 1];
086: m_head = 0;
087: m_tail = 0;
088: }
089:
090: /**
091: * Returns the number of elements stored in the buffer.
092: *
093: * @return this buffer's size
094: */
095: public int size() {
096: int size = 0;
097:
098: if (m_tail < m_head) {
099: size = m_buffer.length - m_head + m_tail;
100: } else {
101: size = m_tail - m_head;
102: }
103:
104: return size;
105: }
106:
107: /**
108: * Returns true if this buffer is empty; false otherwise.
109: *
110: * @return true if this buffer is empty
111: */
112: public boolean isEmpty() {
113: return (size() == 0);
114: }
115:
116: /**
117: * Adds the given element to this buffer.
118: *
119: * @param obj the element to add
120: * @return true, always
121: * @throws NullPointerException if the given element is null
122: * @throws BufferOverflowException if this buffer is full
123: */
124: public boolean add(final Object obj) {
125: if (obj == null) {
126: throw new NullPointerException(
127: "Attempted to add null object to buffer");
128: }
129:
130: if (size() + 1 >= m_buffer.length) {
131: Object[] tmp = new Object[((m_buffer.length - 1) * 2) + 1];
132:
133: int j = 0;
134: for (int i = m_head; i != m_tail;) {
135: tmp[j] = m_buffer[i];
136: m_buffer[i] = null;
137:
138: j++;
139: i++;
140: if (i == m_buffer.length) {
141: i = 0;
142: }
143: }
144:
145: m_buffer = tmp;
146: m_head = 0;
147: m_tail = j;
148: }
149:
150: m_buffer[m_tail] = obj;
151: m_tail++;
152: if (m_tail >= m_buffer.length) {
153: m_tail = 0;
154: }
155: return true;
156: }
157:
158: /**
159: * Returns the next object in the buffer.
160: *
161: * @return the next object in the buffer
162: * @throws BufferUnderflowException if this buffer is empty
163: */
164: public Object get() {
165: if (isEmpty()) {
166: throw new BufferUnderflowException(
167: "The buffer is already empty");
168: }
169:
170: return m_buffer[m_head];
171: }
172:
173: /**
174: * Removes the next object from the buffer
175: *
176: * @return the removed object
177: * @throws BufferUnderflowException if this buffer is empty
178: */
179: public Object remove() {
180: if (isEmpty()) {
181: throw new BufferUnderflowException(
182: "The buffer is already empty");
183: }
184:
185: Object element = m_buffer[m_head];
186:
187: if (null != element) {
188: m_buffer[m_head] = null;
189:
190: m_head++;
191: if (m_head >= m_buffer.length) {
192: m_head = 0;
193: }
194: }
195:
196: return element;
197: }
198:
199: /**
200: * Increments the internal index.
201: *
202: * @param index the index to increment
203: * @return the updated index
204: */
205: private int increment(int index) {
206: index++;
207: if (index >= m_buffer.length) {
208: index = 0;
209: }
210: return index;
211: }
212:
213: /**
214: * Decrements the internal index.
215: *
216: * @param index the index to decrement
217: * @return the updated index
218: */
219: private int decrement(int index) {
220: index--;
221: if (index < 0) {
222: index = m_buffer.length - 1;
223: }
224: return index;
225: }
226:
227: /**
228: * Returns an iterator over this buffer's elements.
229: *
230: * @return an iterator over this buffer's elements
231: */
232: public Iterator iterator() {
233: return new Iterator() {
234:
235: private int index = m_head;
236: private int lastReturnedIndex = -1;
237:
238: public boolean hasNext() {
239: return index != m_tail;
240:
241: }
242:
243: public Object next() {
244: if (!hasNext())
245: throw new NoSuchElementException();
246: lastReturnedIndex = index;
247: index = increment(index);
248: return m_buffer[lastReturnedIndex];
249: }
250:
251: public void remove() {
252: if (lastReturnedIndex == -1)
253: throw new IllegalStateException();
254:
255: // First element can be removed quickly
256: if (lastReturnedIndex == m_head) {
257: UnboundedFifoBuffer.this .remove();
258: lastReturnedIndex = -1;
259: return;
260: }
261:
262: // Other elements require us to shift the subsequent elements
263: int i = increment(lastReturnedIndex);
264: while (i != m_tail) {
265: m_buffer[decrement(i)] = m_buffer[i];
266: i = increment(i);
267: }
268:
269: lastReturnedIndex = -1;
270: m_tail = decrement(m_tail);
271: m_buffer[m_tail] = null;
272: index = decrement(index);
273: }
274:
275: };
276: }
277:
278: }
|