Java > Open Source Codes > org > apache > commons > collections > buffer > PriorityBuffer


1 /*
2  * Copyright 2001-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.util.AbstractCollection ;
19 import java.util.Comparator ;
20 import java.util.Iterator ;
21 import java.util.NoSuchElementException ;
22
23 import org.apache.commons.collections.Buffer;
24 import org.apache.commons.collections.BufferUnderflowException;
25
26 /**
27  * Binary heap implementation of <code>Buffer</code> that provides for
28  * removal based on <code>Comparator</code> ordering.
29  * <p>
30  * The removal order of a binary heap is based on either the natural sort
31  * order of its elements or a specified {@link Comparator}. The
32  * {@link #remove()} method always returns the first element as determined
33  * by the sort order. (The <code>ascendingOrder</code> flag in the constructors
34  * can be used to reverse the sort order, in which case {@link #remove()}
35  * will always remove the last element.) The removal order is
36  * <i>not</i> the same as the order of iteration; elements are
37  * returned by the iterator in no particular order.
38  * <p>
39  * The {@link #add(Object)} and {@link #remove()} operations perform
40  * in logarithmic time. The {@link #get()} operation performs in constant
41  * time. All other operations perform in linear time or worse.
42  * <p>
43  * Note that this implementation is not synchronized. Use
44  * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
45  * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
46  * to provide synchronized access to a <code>PriorityBuffer</code>:
47  *
48  * <pre>
49  * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
50  * </pre>
51  *
52  * @since Commons Collections 3.0 (previously BinaryHeap v1.0)
53  * @version $Revision: 1.5 $ $Date: 2004/05/15 12:33:23 $
54  *
55  * @author Peter Donald
56  * @author Ram Chidambaram
57  * @author Michael A. Smith
58  * @author Paul Jack
59  * @author Stephen Colebourne
60  */
61 public class PriorityBuffer extends AbstractCollection implements Buffer {
62
63     /**
64      * The default capacity for the buffer.
65      */
66     private static final int DEFAULT_CAPACITY = 13;
67     
68     /**
69      * The elements in this buffer.
70      */
71     protected Object [] elements;
72     /**
73      * The number of elements currently in this buffer.
74      */
75     protected int size;
76     /**
77      * If true, the first element as determined by the sort order will
78      * be returned. If false, the last element as determined by the
79      * sort order will be returned.
80      */
81     protected boolean ascendingOrder;
82     /**
83      * The comparator used to order the elements
84      */
85     protected Comparator comparator;
86
87     //-----------------------------------------------------------------------
88 /**
89      * Constructs a new empty buffer that sorts in ascending order by the
90      * natural order of the objects added.
91      */
92     public PriorityBuffer() {
93         this(DEFAULT_CAPACITY, true, null);
94     }
95
96     /**
97      * Constructs a new empty buffer that sorts in ascending order using the
98      * specified comparator.
99      *
100      * @param comparator the comparator used to order the elements,
101      * null means use natural order
102      */
103     public PriorityBuffer(Comparator comparator) {
104         this(DEFAULT_CAPACITY, true, comparator);
105     }
106
107     /**
108      * Constructs a new empty buffer specifying the sort order and using the
109      * natural order of the objects added.
110      *
111      * @param ascendingOrder if <code>true</code> the heap is created as a
112      * minimum heap; otherwise, the heap is created as a maximum heap
113      */
114     public PriorityBuffer(boolean ascendingOrder) {
115         this(DEFAULT_CAPACITY, ascendingOrder, null);
116     }
117
118     /**
119      * Constructs a new empty buffer specifying the sort order and comparator.
120      *
121      * @param ascendingOrder true to use the order imposed by the given
122      * comparator; false to reverse that order
123      * @param comparator the comparator used to order the elements,
124      * null means use natural order
125      */
126     public PriorityBuffer(boolean ascendingOrder, Comparator comparator) {
127         this(DEFAULT_CAPACITY, ascendingOrder, comparator);
128     }
129
130     /**
131      * Constructs a new empty buffer that sorts in ascending order by the
132      * natural order of the objects added, specifying an initial capacity.
133      *
134      * @param capacity the initial capacity for the buffer, greater than zero
135      * @throws IllegalArgumentException if <code>capacity</code> is &lt;= <code>0</code>
136      */
137     public PriorityBuffer(int capacity) {
138         this(capacity, true, null);
139     }
140
141     /**
142      * Constructs a new empty buffer that sorts in ascending order using the
143      * specified comparator and initial capacity.
144      *
145      * @param capacity the initial capacity for the buffer, greater than zero
146      * @param comparator the comparator used to order the elements,
147      * null means use natural order
148      * @throws IllegalArgumentException if <code>capacity</code> is &lt;= <code>0</code>
149      */
150     public PriorityBuffer(int capacity, Comparator comparator) {
151         this(capacity, true, comparator);
152     }
153
154     /**
155      * Constructs a new empty buffer that specifying initial capacity and
156      * sort order, using the natural order of the objects added.
157      *
158      * @param capacity the initial capacity for the buffer, greater than zero
159      * @param ascendingOrder if <code>true</code> the heap is created as a
160      * minimum heap; otherwise, the heap is created as a maximum heap.
161      * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;= 0</code>
162      */
163     public PriorityBuffer(int capacity, boolean ascendingOrder) {
164         this(capacity, ascendingOrder, null);
165     }
166
167     /**
168      * Constructs a new empty buffer that specifying initial capacity,
169      * sort order and comparator.
170      *
171      * @param capacity the initial capacity for the buffer, greater than zero
172      * @param ascendingOrder true to use the order imposed by the given
173      * comparator; false to reverse that order
174      * @param comparator the comparator used to order the elements,
175      * null means use natural order
176      * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;= 0</code>
177      */
178     public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) {
179         super();
180         if (capacity <= 0) {
181             throw new IllegalArgumentException ("invalid capacity");
182         }
183         this.ascendingOrder = ascendingOrder;
184
185         //+1 as 0 is noop
186 this.elements = new Object [capacity + 1];
187         this.comparator = comparator;
188     }
189
190     //-----------------------------------------------------------------------
191 /**
192      * Checks whether the heap is ascending or descending order.
193      *
194      * @return true if ascending order (a min heap)
195      */
196     public boolean isAscendingOrder() {
197         return ascendingOrder;
198     }
199     
200     /**
201      * Gets the comparator being used for this buffer, null is natural order.
202      *
203      * @return the comparator in use, null is natural order
204      */
205     public Comparator comparator() {
206         return comparator;
207     }
208     
209     //-----------------------------------------------------------------------
210 /**
211      * Returns the number of elements in this buffer.
212      *
213      * @return the number of elements in this buffer
214      */
215     public int size() {
216         return size;
217     }
218
219     /**
220      * Clears all elements from the buffer.
221      */
222     public void clear() {
223         elements = new Object [elements.length]; // for gc
224 size = 0;
225     }
226
227     /**
228      * Adds an element to the buffer.
229      * <p>
230      * The element added will be sorted according to the comparator in use.
231      *
232      * @param element the element to be added
233      * @return true always
234      */
235     public boolean add(Object element) {
236         if (isAtCapacity()) {
237             grow();
238         }
239         // percolate element to it's place in tree
240 if (ascendingOrder) {
241             percolateUpMinHeap(element);
242         } else {
243             percolateUpMaxHeap(element);
244         }
245         return true;
246     }
247
248     /**
249      * Gets the next element to be removed without actually removing it (peek).
250      *
251      * @return the next element
252      * @throws BufferUnderflowException if the buffer is empty
253      */
254     public Object get() {
255         if (isEmpty()) {
256             throw new BufferUnderflowException();
257         } else {
258             return elements[1];
259         }
260     }
261
262     /**
263      * Gets and removes the next element (pop).
264      *
265      * @return the next element
266      * @throws BufferUnderflowException if the buffer is empty
267      */
268     public Object remove() {
269         final Object result = get();
270         elements[1] = elements[size--];
271
272         // set the unused element to 'null' so that the garbage collector
273 // can free the object if not used anywhere else.(remove reference)
274 elements[size + 1] = null;
275
276         if (size != 0) {
277             // percolate top element to it's place in tree
278 if (ascendingOrder) {
279                 percolateDownMinHeap(1);
280             } else {
281                 percolateDownMaxHeap(1);
282             }
283         }
284
285         return result;
286     }
287
288     //-----------------------------------------------------------------------
289 /**
290      * Tests if the buffer is at capacity.
291      *
292      * @return <code>true</code> if buffer is full; <code>false</code> otherwise.
293      */
294     protected boolean isAtCapacity() {
295         //+1 as element 0 is noop
296 return elements.length == size + 1;
297     }
298
299     
300     /**
301      * Percolates element down heap from the position given by the index.
302      * <p>
303      * Assumes it is a minimum heap.
304      *
305      * @param index the index for the element
306      */
307     protected void percolateDownMinHeap(final int index) {
308         final Object element = elements[index];
309         int hole = index;
310
311         while ((hole * 2) <= size) {
312             int child = hole * 2;
313
314             // if we have a right child and that child can not be percolated
315 // up then move onto other child
316 if (child != size && compare(elements[child + 1], elements[child]) < 0) {
317                 child++;
318             }
319
320             // if we found resting place of bubble then terminate search
321 if (compare(elements[child], element) >= 0) {
322                 break;
323             }
324
325             elements[hole] = elements[child];
326             hole = child;
327         }
328
329         elements[hole] = element;
330     }
331
332     /**
333      * Percolates element down heap from the position given by the index.
334      * <p>
335      * Assumes it is a maximum heap.
336      *
337      * @param index the index of the element
338      */
339     protected void percolateDownMaxHeap(final int index) {
340         final Object element = elements[index];
341         int hole = index;
342
343         while ((hole * 2) <= size) {
344             int child = hole * 2;
345
346             // if we have a right child and that child can not be percolated
347 // up then move onto other child
348 if (child != size && compare(elements[child + 1], elements[child]) > 0) {
349                 child++;
350             }
351
352             // if we found resting place of bubble then terminate search
353 if (compare(elements[child], element) <= 0) {
354                 break;
355             }
356
357             elements[hole] = elements[child];
358             hole = child;
359         }
360
361         elements[hole] = element;
362     }
363
364     /**
365      * Percolates element up heap from the position given by the index.
366      * <p>
367      * Assumes it is a minimum heap.
368      *
369      * @param index the index of the element to be percolated up
370      */
371     protected void percolateUpMinHeap(final int index) {
372         int hole = index;
373         Object element = elements[hole];
374         while (hole > 1 && compare(element, elements[hole / 2]) < 0) {
375             // save element that is being pushed down
376 // as the element "bubble" is percolated up
377 final int next = hole / 2;
378             elements[hole] = elements[next];
379             hole = next;
380         }
381         elements[hole] = element;
382     }
383
384     /**
385      * Percolates a new element up heap from the bottom.
386      * <p>
387      * Assumes it is a minimum heap.
388      *
389      * @param element the element
390      */
391     protected void percolateUpMinHeap(final Object element) {
392         elements[++size] = element;
393         percolateUpMinHeap(size);
394     }
395
396     /**
397      * Percolates element up heap from from the position given by the index.
398      * <p>
399      * Assume it is a maximum heap.
400      *
401      * @param index the index of the element to be percolated up
402      */
403     protected void percolateUpMaxHeap(final int index) {
404         int hole = index;
405         Object element = elements[hole];
406
407         while (hole > 1 && compare(element, elements[hole / 2]) > 0) {
408             // save element that is being pushed down
409 // as the element "bubble" is percolated up
410 final int next = hole / 2;
411             elements[hole] = elements[next];
412             hole = next;
413         }
414
415         elements[hole] = element;
416     }
417
418     /**
419      * Percolates a new element up heap from the bottom.
420      * <p>
421      * Assume it is a maximum heap.
422      *
423      * @param element the element
424      */
425     protected void percolateUpMaxHeap(final Object element) {
426         elements[++size] = element;
427         percolateUpMaxHeap(size);
428     }
429
430     /**
431      * Compares two objects using the comparator if specified, or the
432      * natural order otherwise.
433      *
434      * @param a the first object
435      * @param b the second object
436      * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
437      */
438     protected int compare(Object a, Object b) {
439         if (comparator != null) {
440             return comparator.compare(a, b);
441         } else {
442             return ((Comparable ) a).compareTo(b);
443         }
444     }
445
446     /**
447      * Increases the size of the heap to support additional elements
448      */
449     protected void grow() {
450         final Object [] array = new Object [elements.length * 2];
451         System.arraycopy(elements, 0, array, 0, elements.length);
452         elements = array;
453     }
454
455     //-----------------------------------------------------------------------
456 /**
457      * Returns an iterator over this heap's elements.
458      *
459      * @return an iterator over this heap's elements
460      */
461     public Iterator iterator() {
462         return new Iterator () {
463
464             private int index = 1;
465             private int lastReturnedIndex = -1;
466
467             public boolean hasNext() {
468                 return index <= size;
469             }
470
471             public Object next() {
472                 if (!hasNext()) {
473                     throw new NoSuchElementException ();
474                 }
475                 lastReturnedIndex = index;
476                 index++;
477                 return elements[lastReturnedIndex];
478             }
479
480             public void remove() {
481                 if (lastReturnedIndex == -1) {
482                     throw new IllegalStateException ();
483                 }
484                 elements[ lastReturnedIndex ] = elements[ size ];
485                 elements[ size ] = null;
486                 size--;
487                 if( size != 0 && lastReturnedIndex <= size) {
488                     int compareToParent = 0;
489                     if (lastReturnedIndex > 1) {
490                         compareToParent = compare(elements[lastReturnedIndex],
491                             elements[lastReturnedIndex / 2]);
492                     }
493                     if (ascendingOrder) {
494                         if (lastReturnedIndex > 1 && compareToParent < 0) {
495                             percolateUpMinHeap(lastReturnedIndex);
496                         } else {
497                             percolateDownMinHeap(lastReturnedIndex);
498                         }
499                     } else { // max heap
500 if (lastReturnedIndex > 1 && compareToParent > 0) {
501                             percolateUpMaxHeap(lastReturnedIndex);
502                         } else {
503                             percolateDownMaxHeap(lastReturnedIndex);
504                         }
505                     }
506                 }
507                 index--;
508                 lastReturnedIndex = -1;
509             }
510
511         };
512     }
513
514     /**
515      * Returns a string representation of this heap. The returned string
516      * is similar to those produced by standard JDK collections.
517      *
518      * @return a string representation of this heap
519      */
520     public String toString() {
521         final StringBuffer sb = new StringBuffer ();
522
523         sb.append("[ ");
524
525         for (int i = 1; i < size + 1; i++) {
526             if (i != 1) {
527                 sb.append(", ");
528             }
529             sb.append(elements[i]);
530         }
531
532         sb.append(" ]");
533
534         return sb.toString();
535     }
536
537 }
538

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags