KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > BoundedFifoBuffer


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.util.AbstractCollection JavaDoc;
19 import java.util.Arrays JavaDoc;
20 import java.util.Collection JavaDoc;
21 import java.util.Iterator JavaDoc;
22 import java.util.NoSuchElementException JavaDoc;
23
24 /**
25  * The BoundedFifoBuffer is a very efficient implementation of
26  * Buffer that does not alter the size of the buffer at runtime.
27  * <p>
28  * The removal order of a <code>BoundedFifoBuffer</code> is based on the
29  * insertion order; elements are removed in the same order in which they
30  * were added. The iteration order is the same as the removal order.
31  * <p>
32  * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
33  * all perform in constant time. All other operations perform in linear
34  * time or worse.
35  * <p>
36  * Note that this implementation is not synchronized. The following can be
37  * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
38  * <pre>
39  * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
40  * </pre>
41  * <p>
42  * This buffer prevents null objects from being added.
43  *
44  * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
45  * @since 2.1
46  * @version $Revision: 1.16 $ $Date: 2004/02/18 01:15:43 $
47  *
48  * @author Avalon
49  * @author Berin Loritsch
50  * @author Paul Jack
51  * @author Stephen Colebourne
52  * @author Herve Quiroz
53  */
54 public class BoundedFifoBuffer extends AbstractCollection JavaDoc
55         implements Buffer, BoundedCollection {
56             
57     private final Object JavaDoc[] m_elements;
58     private int m_start = 0;
59     private int m_end = 0;
60     private boolean m_full = false;
61     private final int maxElements;
62
63     /**
64      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
65      * 32 elements.
66      */
67     public BoundedFifoBuffer() {
68         this(32);
69     }
70
71     /**
72      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
73      * the specified number of elements.
74      *
75      * @param size the maximum number of elements for this fifo
76      * @throws IllegalArgumentException if the size is less than 1
77      */
78     public BoundedFifoBuffer(int size) {
79         if (size <= 0) {
80             throw new IllegalArgumentException JavaDoc("The size must be greater than 0");
81         }
82         m_elements = new Object JavaDoc[size];
83         maxElements = m_elements.length;
84     }
85
86     /**
87      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
88      * of the elements in the specified collection. That collection's
89      * elements will also be added to the buffer.
90      *
91      * @param coll the collection whose elements to add, may not be null
92      * @throws NullPointerException if the collection is null
93      */
94     public BoundedFifoBuffer(Collection JavaDoc coll) {
95         this(coll.size());
96         addAll(coll);
97     }
98
99     /**
100      * Returns the number of elements stored in the buffer.
101      *
102      * @return this buffer's size
103      */
104     public int size() {
105         int size = 0;
106
107         if (m_end < m_start) {
108             size = maxElements - m_start + m_end;
109         } else if (m_end == m_start) {
110             size = (m_full ? maxElements : 0);
111         } else {
112             size = m_end - m_start;
113         }
114
115         return size;
116     }
117
118     /**
119      * Returns true if this buffer is empty; false otherwise.
120      *
121      * @return true if this buffer is empty
122      */
123     public boolean isEmpty() {
124         return size() == 0;
125     }
126
127     /**
128      * Returns true if this collection is full and no new elements can be added.
129      *
130      * @return <code>true</code> if the collection is full
131      */
132     public boolean isFull() {
133         return size() == maxElements;
134     }
135     
136     /**
137      * Gets the maximum size of the collection (the bound).
138      *
139      * @return the maximum number of elements the collection can hold
140      */
141     public int maxSize() {
142         return maxElements;
143     }
144     
145     /**
146      * Clears this buffer.
147      */
148     public void clear() {
149         m_full = false;
150         m_start = 0;
151         m_end = 0;
152         Arrays.fill(m_elements, null);
153     }
154
155     /**
156      * Adds the given element to this buffer.
157      *
158      * @param element the element to add
159      * @return true, always
160      * @throws NullPointerException if the given element is null
161      * @throws BufferOverflowException if this buffer is full
162      */
163     public boolean add(Object JavaDoc element) {
164         if (null == element) {
165             throw new NullPointerException JavaDoc("Attempted to add null object to buffer");
166         }
167
168         if (m_full) {
169             throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
170         }
171
172         m_elements[m_end++] = element;
173
174         if (m_end >= maxElements) {
175             m_end = 0;
176         }
177
178         if (m_end == m_start) {
179             m_full = true;
180         }
181
182         return true;
183     }
184
185     /**
186      * Returns the least recently inserted element in this buffer.
187      *
188      * @return the least recently inserted element
189      * @throws BufferUnderflowException if the buffer is empty
190      */
191     public Object JavaDoc get() {
192         if (isEmpty()) {
193             throw new BufferUnderflowException("The buffer is already empty");
194         }
195
196         return m_elements[m_start];
197     }
198
199     /**
200      * Removes the least recently inserted element from this buffer.
201      *
202      * @return the least recently inserted element
203      * @throws BufferUnderflowException if the buffer is empty
204      */
205     public Object JavaDoc remove() {
206         if (isEmpty()) {
207             throw new BufferUnderflowException("The buffer is already empty");
208         }
209
210         Object JavaDoc element = m_elements[m_start];
211
212         if (null != element) {
213             m_elements[m_start++] = null;
214
215             if (m_start >= maxElements) {
216                 m_start = 0;
217             }
218
219             m_full = false;
220         }
221
222         return element;
223     }
224
225     /**
226      * Increments the internal index.
227      *
228      * @param index the index to increment
229      * @return the updated index
230      */
231     private int increment(int index) {
232         index++;
233         if (index >= maxElements) {
234             index = 0;
235         }
236         return index;
237     }
238
239     /**
240      * Decrements the internal index.
241      *
242      * @param index the index to decrement
243      * @return the updated index
244      */
245     private int decrement(int index) {
246         index--;
247         if (index < 0) {
248             index = maxElements - 1;
249         }
250         return index;
251     }
252
253     /**
254      * Returns an iterator over this buffer's elements.
255      *
256      * @return an iterator over this buffer's elements
257      */
258     public Iterator JavaDoc iterator() {
259         return new Iterator JavaDoc() {
260
261             private int index = m_start;
262             private int lastReturnedIndex = -1;
263             private boolean isFirst = m_full;
264
265             public boolean hasNext() {
266                 return isFirst || (index != m_end);
267                 
268             }
269
270             public Object JavaDoc next() {
271                 if (!hasNext()) throw new NoSuchElementException JavaDoc();
272                 isFirst = false;
273                 lastReturnedIndex = index;
274                 index = increment(index);
275                 return m_elements[lastReturnedIndex];
276             }
277
278             public void remove() {
279                 if (lastReturnedIndex == -1) throw new IllegalStateException JavaDoc();
280
281                 // First element can be removed quickly
282 if (lastReturnedIndex == m_start) {
283                     BoundedFifoBuffer.this.remove();
284                     lastReturnedIndex = -1;
285                     return;
286                 }
287
288                 // Other elements require us to shift the subsequent elements
289 int i = lastReturnedIndex + 1;
290                 while (i != m_end) {
291                     if (i >= maxElements) {
292                         m_elements[i - 1] = m_elements[0];
293                         i = 0;
294                     } else {
295                         m_elements[i - 1] = m_elements[i];
296                         i++;
297                     }
298                 }
299
300                 lastReturnedIndex = -1;
301                 m_end = decrement(m_end);
302                 m_elements[m_end] = null;
303                 m_full = false;
304                 index = decrement(index);
305             }
306
307         };
308     }
309
310 }
311
Popular Tags