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