KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > buffer > 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.buffer;
17
18 import java.io.IOException JavaDoc;
19 import java.io.ObjectInputStream JavaDoc;
20 import java.io.ObjectOutputStream JavaDoc;
21 import java.io.Serializable JavaDoc;
22 import java.util.AbstractCollection JavaDoc;
23 import java.util.Arrays JavaDoc;
24 import java.util.Collection JavaDoc;
25 import java.util.Iterator JavaDoc;
26 import java.util.NoSuchElementException JavaDoc;
27
28 import org.apache.commons.collections.BoundedCollection;
29 import org.apache.commons.collections.Buffer;
30 import org.apache.commons.collections.BufferOverflowException;
31 import org.apache.commons.collections.BufferUnderflowException;
32
33 /**
34  * The BoundedFifoBuffer is a very efficient implementation of
35  * Buffer that does not alter the size of the buffer at runtime.
36  * <p>
37  * The removal order of a <code>BoundedFifoBuffer</code> is based on the
38  * insertion order; elements are removed in the same order in which they
39  * were added. The iteration order is the same as the removal order.
40  * <p>
41  * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
42  * all perform in constant time. All other operations perform in linear
43  * time or worse.
44  * <p>
45  * Note that this implementation is not synchronized. The following can be
46  * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
47  * <pre>
48  * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
49  * </pre>
50  * <p>
51  * This buffer prevents null objects from being added.
52  * <p>
53  * This class is Serializable from Commons Collections 3.1.
54  *
55  * @since Commons Collections 3.0 (previously in main package v2.1)
56  * @version $Revision: 1.8 $ $Date: 2004/06/02 23:12:44 $
57  *
58  * @author Avalon
59  * @author Berin Loritsch
60  * @author Paul Jack
61  * @author Stephen Colebourne
62  * @author Herve Quiroz
63  */
64 public class BoundedFifoBuffer extends AbstractCollection JavaDoc
65         implements Buffer, BoundedCollection, Serializable JavaDoc {
66
67     /** Serialization version */
68     private static final long serialVersionUID = 5603722811189451017L;
69
70     private transient Object JavaDoc[] elements;
71     private transient int start = 0;
72     private transient int end = 0;
73     private transient boolean full = false;
74     private final int maxElements;
75
76     /**
77      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
78      * 32 elements.
79      */
80     public BoundedFifoBuffer() {
81         this(32);
82     }
83
84     /**
85      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
86      * the specified number of elements.
87      *
88      * @param size the maximum number of elements for this fifo
89      * @throws IllegalArgumentException if the size is less than 1
90      */
91     public BoundedFifoBuffer(int size) {
92         if (size <= 0) {
93             throw new IllegalArgumentException JavaDoc("The size must be greater than 0");
94         }
95         elements = new Object JavaDoc[size];
96         maxElements = elements.length;
97     }
98
99     /**
100      * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
101      * of the elements in the specified collection. That collection's
102      * elements will also be added to the buffer.
103      *
104      * @param coll the collection whose elements to add, may not be null
105      * @throws NullPointerException if the collection is null
106      */
107     public BoundedFifoBuffer(Collection JavaDoc coll) {
108         this(coll.size());
109         addAll(coll);
110     }
111
112     //-----------------------------------------------------------------------
113 /**
114      * Write the buffer out using a custom routine.
115      *
116      * @param out the output stream
117      * @throws IOException
118      */
119     private void writeObject(ObjectOutputStream JavaDoc out) throws IOException JavaDoc {
120         out.defaultWriteObject();
121         out.writeInt(size());
122         for (Iterator JavaDoc it = iterator(); it.hasNext();) {
123             out.writeObject(it.next());
124         }
125     }
126
127     /**
128      * Read the buffer in using a custom routine.
129      *
130      * @param in the input stream
131      * @throws IOException
132      * @throws ClassNotFoundException
133      */
134     private void readObject(ObjectInputStream JavaDoc in) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
135         in.defaultReadObject();
136         elements = new Object JavaDoc[maxElements];
137         int size = in.readInt();
138         for (int i = 0; i < size; i++) {
139             elements[i] = in.readObject();
140         }
141         start = 0;
142         end = size;
143         full = (size == maxElements);
144     }
145
146     //-----------------------------------------------------------------------
147 /**
148      * Returns the number of elements stored in the buffer.
149      *
150      * @return this buffer's size
151      */
152     public int size() {
153         int size = 0;
154
155         if (end < start) {
156             size = maxElements - start + end;
157         } else if (end == start) {
158             size = (full ? maxElements : 0);
159         } else {
160             size = end - start;
161         }
162
163         return size;
164     }
165
166     /**
167      * Returns true if this buffer is empty; false otherwise.
168      *
169      * @return true if this buffer is empty
170      */
171     public boolean isEmpty() {
172         return size() == 0;
173     }
174
175     /**
176      * Returns true if this collection is full and no new elements can be added.
177      *
178      * @return <code>true</code> if the collection is full
179      */
180     public boolean isFull() {
181         return size() == maxElements;
182     }
183     
184     /**
185      * Gets the maximum size of the collection (the bound).
186      *
187      * @return the maximum number of elements the collection can hold
188      */
189     public int maxSize() {
190         return maxElements;
191     }
192     
193     /**
194      * Clears this buffer.
195      */
196     public void clear() {
197         full = false;
198         start = 0;
199         end = 0;
200         Arrays.fill(elements, null);
201     }
202
203     /**
204      * Adds the given element to this buffer.
205      *
206      * @param element the element to add
207      * @return true, always
208      * @throws NullPointerException if the given element is null
209      * @throws BufferOverflowException if this buffer is full
210      */
211     public boolean add(Object JavaDoc element) {
212         if (null == element) {
213             throw new NullPointerException JavaDoc("Attempted to add null object to buffer");
214         }
215
216         if (full) {
217             throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
218         }
219
220         elements[end++] = element;
221
222         if (end >= maxElements) {
223             end = 0;
224         }
225
226         if (end == start) {
227             full = true;
228         }
229
230         return true;
231     }
232
233     /**
234      * Returns the least recently inserted element in this buffer.
235      *
236      * @return the least recently inserted element
237      * @throws BufferUnderflowException if the buffer is empty
238      */
239     public Object JavaDoc get() {
240         if (isEmpty()) {
241             throw new BufferUnderflowException("The buffer is already empty");
242         }
243
244         return elements[start];
245     }
246
247     /**
248      * Removes the least recently inserted element from this buffer.
249      *
250      * @return the least recently inserted element
251      * @throws BufferUnderflowException if the buffer is empty
252      */
253     public Object JavaDoc remove() {
254         if (isEmpty()) {
255             throw new BufferUnderflowException("The buffer is already empty");
256         }
257
258         Object JavaDoc element = elements[start];
259
260         if (null != element) {
261             elements[start++] = null;
262
263             if (start >= maxElements) {
264                 start = 0;
265             }
266
267             full = false;
268         }
269
270         return element;
271     }
272
273     /**
274      * Increments the internal index.
275      *
276      * @param index the index to increment
277      * @return the updated index
278      */
279     private int increment(int index) {
280         index++;
281         if (index >= maxElements) {
282             index = 0;
283         }
284         return index;
285     }
286
287     /**
288      * Decrements the internal index.
289      *
290      * @param index the index to decrement
291      * @return the updated index
292      */
293     private int decrement(int index) {
294         index--;
295         if (index < 0) {
296             index = maxElements - 1;
297         }
298         return index;
299     }
300
301     /**
302      * Returns an iterator over this buffer's elements.
303      *
304      * @return an iterator over this buffer's elements
305      */
306     public Iterator JavaDoc iterator() {
307         return new Iterator JavaDoc() {
308
309             private int index = start;
310             private int lastReturnedIndex = -1;
311             private boolean isFirst = full;
312
313             public boolean hasNext() {
314                 return isFirst || (index != end);
315                 
316             }
317
318             public Object JavaDoc next() {
319                 if (!hasNext()) {
320                     throw new NoSuchElementException JavaDoc();
321                 }
322                 isFirst = false;
323                 lastReturnedIndex = index;
324                 index = increment(index);
325                 return elements[lastReturnedIndex];
326             }
327
328             public void remove() {
329                 if (lastReturnedIndex == -1) {
330                     throw new IllegalStateException JavaDoc();
331                 }
332
333                 // First element can be removed quickly
334 if (lastReturnedIndex == start) {
335                     BoundedFifoBuffer.this.remove();
336                     lastReturnedIndex = -1;
337                     return;
338                 }
339
340                 // Other elements require us to shift the subsequent elements
341 int i = lastReturnedIndex + 1;
342                 while (i != end) {
343                     if (i >= maxElements) {
344                         elements[i - 1] = elements[0];
345                         i = 0;
346                     } else {
347                         elements[i - 1] = elements[i];
348                         i++;
349                     }
350                 }
351
352                 lastReturnedIndex = -1;
353                 end = decrement(end);
354                 elements[end] = null;
355                 full = false;
356                 index = decrement(index);
357             }
358
359         };
360     }
361
362 }
363
Popular Tags