View Javadoc

1   /*
2    * Copyright (c) 1998-2002 The Jgroup Team.
3    *
4    * This program is free software; you can redistribute it and/or modify
5    * it under the terms of the GNU Lesser General Public License version 2 as
6    * published by the Free Software Foundation.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU Lesser General Public License for more details.
12   *
13   * You should have received a copy of the GNU Lesser General Public License
14   * along with this program; if not, write to the Free Software
15   * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16   *
17   */
18  
19  package jgroup.util;
20  
21  import java.util.ConcurrentModificationException;
22  import java.util.Iterator;
23  import java.util.NoSuchElementException;
24  
25  /**
26   *  The <code>Queue</code> class implements a queue with last-in,
27   *  first-out semantics.  The queue is implemented as a linked list of
28   *  buckets, each of them contains a fixed number of objects.  Appended
29   *  objects are inserted in the last bucket (if full, a new bucket is
30   *  allocated), while removed object are extracted from the first
31   *  bucket.
32   *
33   *  @author Alberto Montresor
34   *  @author Hein Meling
35   *  @since Jgroup 0.1
36   */
37  public final class Queue
38  {
39  
40    ////////////////////////////////////////////////////////////////////////////////////////////
41    // Constants
42    ////////////////////////////////////////////////////////////////////////////////////////////
43  
44    /* The default bucket size */
45    private final static int QUEUE_BUCKET_SIZE = 32;
46  
47  
48    ////////////////////////////////////////////////////////////////////////////////////////////
49    // Fields
50    ////////////////////////////////////////////////////////////////////////////////////////////
51  
52    /** First bucket in the queue */
53    private Bucket head;
54  
55    /** Last bucket in the queue */
56    private Bucket tail;
57  
58    /** Number of object in a single bucket */
59    private int bucketSize;
60  
61    /** Current object index in the first bucket */
62    private int first = 0;
63  
64    /** Current object index in the last bucket */
65    private int last = 0;
66  
67    /** Number of elements in the queue */
68    private int ncount = 0;
69  
70    /**
71     * The number of times this Queue has been structurally modified.
72     * Structural modifications are those that change the number of
73     * elements in the queue.  This field is used to make the iterator
74     * fail-fast, without risk of rendering the datastructure in an
75     * inconsistent state.  (See ConcurrentModificationException).
76     */
77    private transient int modCount = 0;
78  
79  
80    ////////////////////////////////////////////////////////////////////////////////////////////
81    // Constructors
82    ////////////////////////////////////////////////////////////////////////////////////////////
83  
84    /**
85     *  Allocates a queue with bucket size equal to <code>bucketSize</code>.
86     *
87     *  @param bucketSize
88     *    The size of internal buckets.
89     */
90    public Queue(int bucketSize)
91    {
92      if (bucketSize < 1) 
93        throw new IllegalArgumentException("Bucket size must be greater than zero");
94      this.bucketSize = bucketSize;
95      head = new Bucket(bucketSize);
96      tail = head;
97    }
98  
99  
100   /**
101    *  Allocates a queue with default bucket size.
102    */
103   public Queue()
104   {
105     this(QUEUE_BUCKET_SIZE);
106   }
107 
108 
109   ////////////////////////////////////////////////////////////////////////////////////////////
110   // Methods
111   ////////////////////////////////////////////////////////////////////////////////////////////
112 
113   /**
114    *  Append <code>object</code> to the end of the queue.
115    *
116    *  @param object
117    *    The object to be inserted.
118    */
119   public void insert(Object object)
120   {
121     tail.objects[last] = object;
122     last++;
123     if (last == bucketSize) {
124       if (tail.next == null)
125         tail.next = new Bucket(bucketSize);
126       tail = tail.next;
127       last = 0;
128     }
129     modCount++;
130     ncount++;
131   }
132 
133 
134   /**
135    *  Returns the size of the queue.
136    */
137   public int size()
138   {
139     return ncount;
140   }
141 
142 
143   /**
144    *  Returns true if the queue is empty.
145    */
146   public boolean isEmpty()
147   {
148     return (ncount == 0);
149   }
150 
151 
152   /**
153    *  Returns the first element of the queue; null if the queue is
154    *  empty.
155    */
156   public Object getFirst()
157   {
158     if (ncount == 0)
159       return null;
160 
161     return head.objects[first];
162   }
163 
164 
165   /**
166    *  Removes the first element of the queue.
167    *
168    *  @return the first element of the queue; null if the queue is empty.
169    */
170   public Object removeFirst()
171   {
172     if (ncount == 0)
173       return null;
174     modCount++;
175 
176     Object ret = head.objects[first];
177     head.objects[first] = null;
178     ncount--;
179     first++;
180     if (first == bucketSize) {
181       Bucket temp = tail.next;
182       tail.next = head;                 // This avoid useless allocations
183       head = head.next;
184       tail.next.next = temp;
185       first = 0;
186     }
187     return ret;
188   }
189 
190 
191   /**
192    *  Add the elements of the addend queue at the end of this queue.
193    *
194    *  @param addend
195    *    The queue to be added to the end of this queue.
196    */
197   public void add(Queue addend)
198   {
199     modCount++;
200     
201     Object obj;
202     while ((obj = addend.removeFirst()) != null)
203       insert(obj);
204   }
205 
206 
207   /**
208    *  Removes all the elements from the queue.
209    */
210   public void clear()
211   {
212     modCount++;
213     for (int i = first; i < bucketSize; i++)
214       head.objects[i] = null;
215     head.next = null;
216     tail = head;
217     first  = 0;
218     last   = 0;
219     ncount = 0;
220   }
221 
222 
223   /**
224    *  Copies the element of the queue in an array of objects, in the
225    *  queue order.
226    */
227 //   public Object[] toArray()
228 //   {
229 //     Object[] ret = new Object[ncount];
230 //     Bucket scan = head;
231 //     int pos = first;
232 //     for (int i = 0; i < ncount; i++) {
233 //       ret[i] = scan.objects[pos];
234 //       pos++;
235 //       if (pos == bucketSize) {
236 //         pos = 0;
237 //         scan = scan.next;
238 //       }
239 //     }
240 //     return ret;
241 //   }
242 
243 
244   /**
245    *  Returns an iterator over the queue content.
246    */
247   public Iterator iterator()
248   {
249     return new QueueIterator();
250   }
251 
252 
253   public String toString()
254   {
255     StringBuilder buf = new StringBuilder("[Queue: ");
256     for (Iterator qi = iterator(); qi.hasNext();) {
257       buf.append(qi.next());
258       if (qi.hasNext()) 
259         buf.append(", ");
260     }
261     buf.append("]");
262     return buf.toString();
263   }
264 
265 
266   /**
267    *  Provides an iterator over the elements in the queue.
268    *
269    *  @author Hein Meling
270    *  @since Jgroup 1.2
271    */
272   private class QueueIterator
273     implements Iterator
274   {
275     private Bucket scan = head;
276     private int pos = first;
277     private int nextIndex = 0;
278 
279     /**
280      * The modCount value that the iterator believes that the backing
281      * Queue should have.  If this expectation is violated, the iterator
282      * has detected concurrent modification.
283      */
284     private int expectedModCount = modCount;
285 
286 
287     public boolean hasNext()
288     {
289       return nextIndex != ncount;
290     }
291 
292 
293     public Object next()
294     {
295       if (modCount != expectedModCount)
296         throw new ConcurrentModificationException();
297       if (nextIndex == ncount)
298         throw new NoSuchElementException();
299 
300       Object obj = scan.objects[pos++];
301       if (pos == bucketSize) {
302         pos = 0;
303         scan = scan.next;
304       }
305       nextIndex++;
306       return obj;
307     }
308 
309 
310     public void remove() 
311     {
312       throw new UnsupportedOperationException();
313     }
314 
315   } // END QueueIterator
316 
317 
318   /**
319    *  The <code>Bucket</code> class represents the container class used
320    *  in queue to avoid expensive allocations and to save memory.
321    *
322    *  @author Alberto Montresor
323    *  @since Jgroup 0.1
324    */
325   private class Bucket {
326 
327     //////////////////////////////////////////////////////////////////////////////////////////
328     // Fields
329     //////////////////////////////////////////////////////////////////////////////////////////
330 
331     /** Stored objects */
332     Object[] objects;
333 
334     /** Next element */
335     Bucket next;
336 
337 
338     //////////////////////////////////////////////////////////////////////////////////////////
339     // Constructor
340     //////////////////////////////////////////////////////////////////////////////////////////
341 
342     /**
343      *  Constructs a QueueBucket with the specified size
344      *
345      *  @param bucketSize
346      *    Number of elements in a bucket.
347      */
348     Bucket(int bucketSize)
349     {
350       this.objects = new Object[bucketSize];
351       this.next = null;
352     }
353 
354   } // END Bucket
355 
356 } // END Queue
357