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;
018
019 import java.util.AbstractCollection;
020 import java.util.Arrays;
021 import java.util.Collection;
022 import java.util.Iterator;
023 import java.util.NoSuchElementException;
024
025 /**
026 * The BoundedFifoBuffer is a very efficient implementation of
027 * Buffer that does not alter the size of the buffer at runtime.
028 * <p>
029 * The removal order of a <code>BoundedFifoBuffer</code> is based on the
030 * insertion order; elements are removed in the same order in which they
031 * were added. The iteration order is the same as the removal order.
032 * <p>
033 * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
034 * all perform in constant time. All other operations perform in linear
035 * time or worse.
036 * <p>
037 * Note that this implementation is not synchronized. The following can be
038 * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
039 * <pre>
040 * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
041 * </pre>
042 * <p>
043 * This buffer prevents null objects from being added.
044 *
045 * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
046 * @since 2.1
047 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
048 *
049 * @author Avalon
050 * @author Berin Loritsch
051 * @author Paul Jack
052 * @author Stephen Colebourne
053 * @author Herve Quiroz
054 */
055 public class BoundedFifoBuffer extends AbstractCollection
056 implements Buffer, BoundedCollection {
057
058 private final Object[] m_elements;
059 private int m_start = 0;
060 private int m_end = 0;
061 private boolean m_full = false;
062 private final int maxElements;
063
064 /**
065 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
066 * 32 elements.
067 */
068 public BoundedFifoBuffer() {
069 this(32);
070 }
071
072 /**
073 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
074 * the specified number of elements.
075 *
076 * @param size the maximum number of elements for this fifo
077 * @throws IllegalArgumentException if the size is less than 1
078 */
079 public BoundedFifoBuffer(int size) {
080 if (size <= 0) {
081 throw new IllegalArgumentException("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("Attempted to add null object to buffer");
167 }
168
169 if (m_full) {
170 throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
171 }
172
173 m_elements[m_end++] = element;
174
175 if (m_end >= maxElements) {
176 m_end = 0;
177 }
178
179 if (m_end == m_start) {
180 m_full = true;
181 }
182
183 return true;
184 }
185
186 /**
187 * Returns the least recently inserted element in this buffer.
188 *
189 * @return the least recently inserted element
190 * @throws BufferUnderflowException if the buffer is empty
191 */
192 public Object get() {
193 if (isEmpty()) {
194 throw new BufferUnderflowException("The buffer is already empty");
195 }
196
197 return m_elements[m_start];
198 }
199
200 /**
201 * Removes the least recently inserted element from this buffer.
202 *
203 * @return the least recently inserted element
204 * @throws BufferUnderflowException if the buffer is empty
205 */
206 public Object remove() {
207 if (isEmpty()) {
208 throw new BufferUnderflowException("The buffer is already empty");
209 }
210
211 Object element = m_elements[m_start];
212
213 if (null != element) {
214 m_elements[m_start++] = null;
215
216 if (m_start >= maxElements) {
217 m_start = 0;
218 }
219
220 m_full = false;
221 }
222
223 return element;
224 }
225
226 /**
227 * Increments the internal index.
228 *
229 * @param index the index to increment
230 * @return the updated index
231 */
232 private int increment(int index) {
233 index++;
234 if (index >= maxElements) {
235 index = 0;
236 }
237 return index;
238 }
239
240 /**
241 * Decrements the internal index.
242 *
243 * @param index the index to decrement
244 * @return the updated index
245 */
246 private int decrement(int index) {
247 index--;
248 if (index < 0) {
249 index = maxElements - 1;
250 }
251 return index;
252 }
253
254 /**
255 * Returns an iterator over this buffer's elements.
256 *
257 * @return an iterator over this buffer's elements
258 */
259 public Iterator iterator() {
260 return new Iterator() {
261
262 private int index = m_start;
263 private int lastReturnedIndex = -1;
264 private boolean isFirst = m_full;
265
266 public boolean hasNext() {
267 return isFirst || (index != m_end);
268
269 }
270
271 public Object next() {
272 if (!hasNext()) throw new NoSuchElementException();
273 isFirst = false;
274 lastReturnedIndex = index;
275 index = increment(index);
276 return m_elements[lastReturnedIndex];
277 }
278
279 public void remove() {
280 if (lastReturnedIndex == -1) throw new IllegalStateException();
281
282 // First element can be removed quickly
283 if (lastReturnedIndex == m_start) {
284 BoundedFifoBuffer.this.remove();
285 lastReturnedIndex = -1;
286 return;
287 }
288
289 // Other elements require us to shift the subsequent elements
290 int i = lastReturnedIndex + 1;
291 while (i != m_end) {
292 if (i >= maxElements) {
293 m_elements[i - 1] = m_elements[0];
294 i = 0;
295 } else {
296 m_elements[i - 1] = m_elements[i];
297 i++;
298 }
299 }
300
301 lastReturnedIndex = -1;
302 m_end = decrement(m_end);
303 m_elements[m_end] = null;
304 m_full = false;
305 index = decrement(index);
306 }
307
308 };
309 }
310
311 }