KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > info > monitorenter > util > collections > RingBufferArray


1 /*
2  * RingBufferArray, an array- based implementation of a RingBuffer, which never
3  * drops stored elements in case of decreasing the buffer size.
4  * Copyright (C) 2002 Achim Westermann, Achim.Westermann@gmx.de
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19  *
20  * If you modify or optimize the code in a useful way please let me know.
21  * Achim.Westermann@gmx.de
22  */
23 package info.monitorenter.util.collections;
24
25 import info.monitorenter.util.StringUtil;
26
27 import java.util.Iterator JavaDoc;
28 import java.util.LinkedList JavaDoc;
29 import java.util.List JavaDoc;
30 import java.util.NoSuchElementException JavaDoc;
31
32
33 /**
34  * A RingBuffer can be used to store a limited number of entries of any type
35  * within a buffer.
36  * <p>
37  *
38  * As soon as the maximum number of entries is reached, the next entry is added
39  * to the end and the first entry is removed from it. In this case, all elements
40  * are stored in a Object[]. But don't worry there will not be a single call to
41  * <code>System.arraycopy</code> caused by invocation of the
42  * <code>add(Object element)</code>- method. Internal indexes into the array
43  * for the head and tail allow to reuse the same memory again and again. <br>
44  * No element is lost: If <code>setBufferSize(int asize)</code> decreases the
45  * size of the buffer and it will get smaller than the actual amount of elements
46  * stored, they will get cached until removed.
47  * <p>
48  * For allowing high performance single-threaded use this implementation and the
49  * implementations of the retrieveable <code>Iterator</code>- instances are
50  * not synchronized at all.
51  * <p>
52  *
53  * @author <a HREF='mailto:Achim.Westermann@gmx.de'>Achim Westermann </a>
54  *
55  * @version $Revision: 1.1 $
56  */
57 public class RingBufferArray extends RingBufferArrayFast {
58
59   /**
60    * Generated <code>serialVersionUID</code>.
61    */
62   private static final long serialVersionUID = 3977861774055585593L;
63
64   /**
65    * Elements that stores elements that have to be removed due to an invocation
66    * to {@link #setBufferSize(int)} with a smaller argument than the amount of
67    * elements stored.
68    */
69   protected List JavaDoc m_pendingremove = new LinkedList JavaDoc();
70
71   /**
72    * Constructs a RingBuffer with the given size.
73    * <p>
74    *
75    * @param aSize
76    * the size of the buffer.
77    */
78   public RingBufferArray(final int aSize) {
79     super(aSize);
80   }
81
82   /**
83    * @see info.monitorenter.util.collections.IRingBuffer#isEmpty()
84    */
85   public boolean isEmpty() {
86     return super.isEmpty() && (this.m_pendingremove.size() == 0);
87   }
88
89   /**
90    * Base class for ringbuffer iterators with pending removals (those who do not
91    * drop instances if size is exceeded).
92    * <p>
93    *
94    * @author <a HREF="mailto:Achim.Westermann@gmx.de">Achim Westermann</a>
95    *
96    *
97    * @version $Revision: 1.1 $
98    */
99   abstract class ARingBufferIterator extends RingBufferArrayFast.ARingBufferIterator {
100
101     /**
102      * The position of the next instance of the pending removed elements to
103      * return.
104      */
105     protected int m_pendpos;
106
107     /**
108      * @see info.monitorenter.util.collections.RingBufferArrayFast.RingBufferIterator#hasNext()
109      */
110     public boolean hasNext() {
111       return super.hasNext() || this.m_pendpos >= 0;
112     }
113
114     /**
115      * @see info.monitorenter.util.collections.RingBufferArrayFast.RingBufferIterator#incPos()
116      */
117     protected void incPos() {
118       // TODO Auto-generated method stub
119
120     }
121
122     /**
123      * @see java.util.Iterator#next()
124      */
125     public Object JavaDoc next() {
126       Object JavaDoc ret = null;
127       // Pending elements are the oldest
128 if (this.m_pendpos >= 0) {
129         ret = RingBufferArray.this.m_pendingremove.get(this.m_pendpos);
130         this.m_pendpos--;
131         if (ret == null) {
132           System.out
133               .println("RingBufferArray.iteratorF2L returns null: head:"
134                   + RingBufferArray.this.m_headpointer + " tail: "
135                   + RingBufferArray.this.m_tailpointer);
136         }
137         return ret;
138       }
139       if (!this.hasNext()) {
140         throw new NoSuchElementException JavaDoc();
141       }
142       ret = RingBufferArray.this.m_buffer[this.m_pos];
143       this.m_count++;
144       this.incPos();
145       return ret;
146     }
147
148   }
149
150   /**
151    * @see info.monitorenter.util.collections.IRingBuffer#iteratorF2L()
152    */
153   public java.util.Iterator JavaDoc iteratorF2L() {
154     return new ARingBufferIterator() {
155       {
156         this.m_pos = (m_headpointer == 0) ? m_size : m_headpointer - 1;
157         this.m_pendpos = RingBufferArray.this.m_pendingremove.size() - 1;
158       }
159
160       protected void incPos() {
161         if (this.m_pos == 0) {
162           this.m_pos = m_size;
163         } else {
164           this.m_pos--;
165         }
166
167       }
168     };
169   }
170
171   /**
172    * @see info.monitorenter.util.collections.IRingBuffer#iteratorL2F()
173    */
174   public java.util.Iterator JavaDoc iteratorL2F() {
175     return new ARingBufferIterator() {
176       {
177         this.m_pos = m_tailpointer;
178         this.m_pendpos = 0;
179       }
180
181      
182       protected void incPos() {
183         if (this.m_pos == RingBufferArray.this.m_size) {
184           this.m_pos = 0;
185         } else {
186           this.m_pos++;
187         }
188       }
189     };
190   }
191
192   /**
193    * @see info.monitorenter.util.collections.IRingBuffer#remove()
194    */
195   public Object JavaDoc remove() {
196     if (this.m_pendingremove.size() > 0) {
197       if (DEBUG) {
198         System.out.println("Removing pending element!!!");
199       }
200       return this.m_pendingremove.remove(0);
201     }
202     return super.remove();
203   }
204
205   /**
206    * @see info.monitorenter.util.collections.IRingBuffer#removeAll()
207    */
208   public Object JavaDoc[] removeAll() {
209     Object JavaDoc[] ret = new Object JavaDoc[this.size() + this.m_pendingremove.size()];
210     int stop = this.m_pendingremove.size();
211     int i;
212     for (i = 0; i < stop; i++) {
213       ret[i] = this.m_pendingremove.remove(0);
214     }
215     for (; i < ret.length; i++) {
216       ret[i] = this.remove();
217     }
218     return ret;
219   }
220
221   /**
222    * Sets a new buffer- size.
223    * <p>
224    * A new size is assigned but the elements "overhanging" are returned by the
225    * <code>Object remove()</code>- method first. This may take time until the
226    * buffer has its actual size again. Don't pretend on calling this method for
227    * saving of memory very often as the whole buffer has to be copied into a new
228    * array every time- and if newSize < getSize() additional the overhanging
229    * elements references have to be moved to the internal
230    * <code>List pendingremove</code>.
231    * <p>
232    *
233    * @param newSize
234    * the new size of the buffer.
235    *
236    */
237   public void setBufferSize(final int newSize) {
238     List JavaDoc newpending = null;
239     if (this.size() > newSize) {
240       newpending = new LinkedList JavaDoc();
241       int stop = this.size();
242       for (int i = newSize; i < stop; i++) {
243         Object JavaDoc add = this.remove();
244         newpending.add(add);
245       }
246     }
247     Object JavaDoc[] newbuffer = new Object JavaDoc[newSize];
248     int i = 0;
249     if (DEBUG) {
250       System.out.println("setBufferSize(" + newSize + "): isEmpty(): " + this.isEmpty() + " tail: "
251           + this.m_tailpointer + " head: " + this.m_headpointer);
252     }
253     while (!isEmpty()) {
254       newbuffer[i] = remove();
255       i++;
256     }
257     this.m_tailpointer = 0;
258     if (newSize == i) {
259       this.m_headpointer = 0;
260     } else {
261       this.m_headpointer = i;
262     }
263     this.m_buffer = newbuffer;
264     this.m_size = newSize - 1;
265     if (newpending != null) {
266       this.m_pendingremove = newpending;
267     }
268   }
269
270   /**
271    * @see info.monitorenter.util.collections.IRingBuffer#size()
272    */
273   public int size() {
274     return super.size() + this.m_pendingremove.size();
275   }
276
277   /**
278    * Returns a string representation of the RingBuffer and it's contents.
279    * <p>
280    *
281    * Don't call this in your application too often: hard arraycopy - operation
282    * an memalloc are triggered.
283    * <p>
284    *
285    * @return a string representation of the RingBuffer and it's contents.
286    */
287   public String JavaDoc toString() {
288     if (this.isEmpty()) {
289       if (DEBUG) {
290         System.out.println("toString(): isEmpty: true");
291       }
292       return "[]";
293     }
294     Object JavaDoc[] actualcontent = new Object JavaDoc[this.size()];
295     int tmp = this.m_tailpointer;
296     int stop = this.m_pendingremove.size();
297     Iterator JavaDoc it = this.m_pendingremove.iterator();
298     int i = 0;
299     for (; i < stop; i++) {
300       actualcontent[i] = it.next();
301     }
302     for (; i < actualcontent.length; i++) {
303       actualcontent[i] = this.m_buffer[tmp];
304       if (tmp == this.m_size) {
305         tmp = 0;
306       } else {
307         tmp++;
308       }
309       if (tmp == this.m_headpointer && this.m_empty) {
310         break;
311       }
312     }
313     return StringUtil.arrayToString(actualcontent);
314   }
315
316 }
317
Popular Tags