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.Arrays;
020: import java.util.Collection;
021: import java.util.Iterator;
022: import java.util.NoSuchElementException;
023:
024: /**
025: * The BoundedFifoBuffer is a very efficient implementation of
026: * Buffer that does not alter the size of the buffer at runtime.
027: * <p>
028: * The removal order of a <code>BoundedFifoBuffer</code> is based on the
029: * insertion order; elements are removed in the same order in which they
030: * were added. The iteration order is the same as the removal order.
031: * <p>
032: * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
033: * all perform in constant time. All other operations perform in linear
034: * time or worse.
035: * <p>
036: * Note that this implementation is not synchronized. The following can be
037: * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
038: * <pre>
039: * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
040: * </pre>
041: * <p>
042: * This buffer prevents null objects from being added.
043: *
044: * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
045: * @since 2.1
046: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
047: *
048: * @author Avalon
049: * @author Berin Loritsch
050: * @author Paul Jack
051: * @author Stephen Colebourne
052: * @author Herve Quiroz
053: */
054: public class BoundedFifoBuffer extends AbstractCollection implements
055: Buffer, BoundedCollection {
056:
057: private final Object[] m_elements;
058: private int m_start = 0;
059: private int m_end = 0;
060: private boolean m_full = false;
061: private final int maxElements;
062:
063: /**
064: * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
065: * 32 elements.
066: */
067: public BoundedFifoBuffer() {
068: this (32);
069: }
070:
071: /**
072: * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
073: * the specified number of elements.
074: *
075: * @param size the maximum number of elements for this fifo
076: * @throws IllegalArgumentException if the size is less than 1
077: */
078: public BoundedFifoBuffer(int size) {
079: if (size <= 0) {
080: throw new IllegalArgumentException(
081: "The size must be greater than 0");
082: }
083: m_elements = new Object[size];
084: maxElements = m_elements.length;
085: }
086:
087: /**
088: * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
089: * of the elements in the specified collection. That collection's
090: * elements will also be added to the buffer.
091: *
092: * @param coll the collection whose elements to add, may not be null
093: * @throws NullPointerException if the collection is null
094: */
095: public BoundedFifoBuffer(Collection coll) {
096: this (coll.size());
097: addAll(coll);
098: }
099:
100: /**
101: * Returns the number of elements stored in the buffer.
102: *
103: * @return this buffer's size
104: */
105: public int size() {
106: int size = 0;
107:
108: if (m_end < m_start) {
109: size = maxElements - m_start + m_end;
110: } else if (m_end == m_start) {
111: size = (m_full ? maxElements : 0);
112: } else {
113: size = m_end - m_start;
114: }
115:
116: return size;
117: }
118:
119: /**
120: * Returns true if this buffer is empty; false otherwise.
121: *
122: * @return true if this buffer is empty
123: */
124: public boolean isEmpty() {
125: return size() == 0;
126: }
127:
128: /**
129: * Returns true if this collection is full and no new elements can be added.
130: *
131: * @return <code>true</code> if the collection is full
132: */
133: public boolean isFull() {
134: return size() == maxElements;
135: }
136:
137: /**
138: * Gets the maximum size of the collection (the bound).
139: *
140: * @return the maximum number of elements the collection can hold
141: */
142: public int maxSize() {
143: return maxElements;
144: }
145:
146: /**
147: * Clears this buffer.
148: */
149: public void clear() {
150: m_full = false;
151: m_start = 0;
152: m_end = 0;
153: Arrays.fill(m_elements, null);
154: }
155:
156: /**
157: * Adds the given element to this buffer.
158: *
159: * @param element the element to add
160: * @return true, always
161: * @throws NullPointerException if the given element is null
162: * @throws BufferOverflowException if this buffer is full
163: */
164: public boolean add(Object element) {
165: if (null == element) {
166: throw new NullPointerException(
167: "Attempted to add null object to buffer");
168: }
169:
170: if (m_full) {
171: throw new BufferOverflowException(
172: "The buffer cannot hold more than " + maxElements
173: + " objects.");
174: }
175:
176: m_elements[m_end++] = element;
177:
178: if (m_end >= maxElements) {
179: m_end = 0;
180: }
181:
182: if (m_end == m_start) {
183: m_full = true;
184: }
185:
186: return true;
187: }
188:
189: /**
190: * Returns the least recently inserted element in this buffer.
191: *
192: * @return the least recently inserted element
193: * @throws BufferUnderflowException if the buffer is empty
194: */
195: public Object get() {
196: if (isEmpty()) {
197: throw new BufferUnderflowException(
198: "The buffer is already empty");
199: }
200:
201: return m_elements[m_start];
202: }
203:
204: /**
205: * Removes the least recently inserted element from this buffer.
206: *
207: * @return the least recently inserted element
208: * @throws BufferUnderflowException if the buffer is empty
209: */
210: public Object remove() {
211: if (isEmpty()) {
212: throw new BufferUnderflowException(
213: "The buffer is already empty");
214: }
215:
216: Object element = m_elements[m_start];
217:
218: if (null != element) {
219: m_elements[m_start++] = null;
220:
221: if (m_start >= maxElements) {
222: m_start = 0;
223: }
224:
225: m_full = false;
226: }
227:
228: return element;
229: }
230:
231: /**
232: * Increments the internal index.
233: *
234: * @param index the index to increment
235: * @return the updated index
236: */
237: private int increment(int index) {
238: index++;
239: if (index >= maxElements) {
240: index = 0;
241: }
242: return index;
243: }
244:
245: /**
246: * Decrements the internal index.
247: *
248: * @param index the index to decrement
249: * @return the updated index
250: */
251: private int decrement(int index) {
252: index--;
253: if (index < 0) {
254: index = maxElements - 1;
255: }
256: return index;
257: }
258:
259: /**
260: * Returns an iterator over this buffer's elements.
261: *
262: * @return an iterator over this buffer's elements
263: */
264: public Iterator iterator() {
265: return new Iterator() {
266:
267: private int index = m_start;
268: private int lastReturnedIndex = -1;
269: private boolean isFirst = m_full;
270:
271: public boolean hasNext() {
272: return isFirst || (index != m_end);
273:
274: }
275:
276: public Object next() {
277: if (!hasNext())
278: throw new NoSuchElementException();
279: isFirst = false;
280: lastReturnedIndex = index;
281: index = increment(index);
282: return m_elements[lastReturnedIndex];
283: }
284:
285: public void remove() {
286: if (lastReturnedIndex == -1)
287: throw new IllegalStateException();
288:
289: // First element can be removed quickly
290: if (lastReturnedIndex == m_start) {
291: BoundedFifoBuffer.this .remove();
292: lastReturnedIndex = -1;
293: return;
294: }
295:
296: // Other elements require us to shift the subsequent elements
297: int i = lastReturnedIndex + 1;
298: while (i != m_end) {
299: if (i >= maxElements) {
300: m_elements[i - 1] = m_elements[0];
301: i = 0;
302: } else {
303: m_elements[i - 1] = m_elements[i];
304: i++;
305: }
306: }
307:
308: lastReturnedIndex = -1;
309: m_end = decrement(m_end);
310: m_elements[m_end] = null;
311: m_full = false;
312: index = decrement(index);
313: }
314:
315: };
316: }
317:
318: }
|