001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections.buffer;
018    
019    import java.io.Serializable;
020    import java.util.AbstractCollection;
021    import java.util.Comparator;
022    import java.util.Iterator;
023    import java.util.NoSuchElementException;
024    
025    import org.apache.commons.collections.Buffer;
026    import org.apache.commons.collections.BufferUnderflowException;
027    
028    /**
029     * Binary heap implementation of <code>Buffer</code> that provides for
030     * removal based on <code>Comparator</code> ordering.
031     * <p>
032     * The removal order of a binary heap is based on either the natural sort
033     * order of its elements or a specified {@link Comparator}.  The 
034     * {@link #remove()} method always returns the first element as determined
035     * by the sort order.  (The <code>ascendingOrder</code> flag in the constructors
036     * can be used to reverse the sort order, in which case {@link #remove()}
037     * will always remove the last element.)  The removal order is 
038     * <i>not</i> the same as the order of iteration; elements are
039     * returned by the iterator in no particular order.
040     * <p>
041     * The {@link #add(Object)} and {@link #remove()} operations perform
042     * in logarithmic time.  The {@link #get()} operation performs in constant
043     * time.  All other operations perform in linear time or worse.
044     * <p>
045     * Note that this implementation is not synchronized.  Use 
046     * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
047     * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
048     * to provide synchronized access to a <code>PriorityBuffer</code>:
049     * <pre>
050     * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
051     * </pre>
052     * <p>
053     * This class is Serializable from Commons Collections 3.2.
054     *
055     * @since Commons Collections 3.0 (previously BinaryHeap v1.0)
056     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
057     * 
058     * @author Peter Donald
059     * @author Ram Chidambaram
060     * @author Michael A. Smith
061     * @author Paul Jack
062     * @author Stephen Colebourne
063     * @author Steve Phelps
064     */
065    public class PriorityBuffer extends AbstractCollection
066            implements Buffer, Serializable {
067    
068        /** Serialization lock. */
069        private static final long serialVersionUID = 6891186490470027896L;
070    
071        /**
072         * The default capacity for the buffer.
073         */
074        private static final int DEFAULT_CAPACITY = 13;
075        
076        /**
077         * The elements in this buffer.
078         */
079        protected Object[] elements;
080        /**
081         * The number of elements currently in this buffer.
082         */
083        protected int size;
084        /**
085         * If true, the first element as determined by the sort order will 
086         * be returned.  If false, the last element as determined by the
087         * sort order will be returned.
088         */
089        protected boolean ascendingOrder;
090        /**
091         * The comparator used to order the elements
092         */
093        protected Comparator comparator;
094    
095        //-----------------------------------------------------------------------
096        /**
097         * Constructs a new empty buffer that sorts in ascending order by the
098         * natural order of the objects added.
099         */
100        public PriorityBuffer() {
101            this(DEFAULT_CAPACITY, true, null);
102        }
103    
104        /**
105         * Constructs a new empty buffer that sorts in ascending order using the
106         * specified comparator.
107         * 
108         * @param comparator  the comparator used to order the elements,
109         *  null means use natural order
110         */
111        public PriorityBuffer(Comparator comparator) {
112            this(DEFAULT_CAPACITY, true, comparator);
113        }
114    
115        /**
116         * Constructs a new empty buffer specifying the sort order and using the
117         * natural order of the objects added.
118         *
119         * @param ascendingOrder  if <code>true</code> the heap is created as a 
120         * minimum heap; otherwise, the heap is created as a maximum heap
121         */
122        public PriorityBuffer(boolean ascendingOrder) {
123            this(DEFAULT_CAPACITY, ascendingOrder, null);
124        }
125    
126        /**
127         * Constructs a new empty buffer specifying the sort order and comparator.
128         *
129         * @param ascendingOrder  true to use the order imposed by the given 
130         *   comparator; false to reverse that order
131         * @param comparator  the comparator used to order the elements,
132         *  null means use natural order
133         */
134        public PriorityBuffer(boolean ascendingOrder, Comparator comparator) {
135            this(DEFAULT_CAPACITY, ascendingOrder, comparator);
136        }
137    
138        /**
139         * Constructs a new empty buffer that sorts in ascending order by the
140         * natural order of the objects added, specifying an initial capacity.
141         *  
142         * @param capacity  the initial capacity for the buffer, greater than zero
143         * @throws IllegalArgumentException if <code>capacity</code> is &lt;= <code>0</code>
144         */
145        public PriorityBuffer(int capacity) {
146            this(capacity, true, null);
147        }
148    
149        /**
150         * Constructs a new empty buffer that sorts in ascending order using the
151         * specified comparator and initial capacity.
152         *
153         * @param capacity  the initial capacity for the buffer, greater than zero
154         * @param comparator  the comparator used to order the elements,
155         *  null means use natural order
156         * @throws IllegalArgumentException if <code>capacity</code> is &lt;= <code>0</code>
157         */
158        public PriorityBuffer(int capacity, Comparator comparator) {
159            this(capacity, true, comparator);
160        }
161    
162        /**
163         * Constructs a new empty buffer that specifying initial capacity and
164         * sort order, using the natural order of the objects added.
165         *
166         * @param capacity  the initial capacity for the buffer, greater than zero
167         * @param ascendingOrder if <code>true</code> the heap is created as a 
168         *  minimum heap; otherwise, the heap is created as a maximum heap.
169         * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;= 0</code>
170         */
171        public PriorityBuffer(int capacity, boolean ascendingOrder) {
172            this(capacity, ascendingOrder, null);
173        }
174    
175        /**
176         * Constructs a new empty buffer that specifying initial capacity,
177         * sort order and comparator.
178         *
179         * @param capacity  the initial capacity for the buffer, greater than zero
180         * @param ascendingOrder  true to use the order imposed by the given 
181         *   comparator; false to reverse that order
182         * @param comparator  the comparator used to order the elements,
183         *  null means use natural order
184         * @throws IllegalArgumentException if <code>capacity</code> is <code>&lt;= 0</code>
185         */
186        public PriorityBuffer(int capacity, boolean ascendingOrder, Comparator comparator) {
187            super();
188            if (capacity <= 0) {
189                throw new IllegalArgumentException("invalid capacity");
190            }
191            this.ascendingOrder = ascendingOrder;
192    
193            //+1 as 0 is noop
194            this.elements = new Object[capacity + 1];
195            this.comparator = comparator;
196        }
197    
198        //-----------------------------------------------------------------------
199        /**
200         * Checks whether the heap is ascending or descending order.
201         * 
202         * @return true if ascending order (a min heap)
203         */
204        public boolean isAscendingOrder() {
205            return ascendingOrder;
206        }
207        
208        /**
209         * Gets the comparator being used for this buffer, null is natural order.
210         * 
211         * @return the comparator in use, null is natural order
212         */
213        public Comparator comparator() {
214            return comparator;
215        }
216        
217        //-----------------------------------------------------------------------
218        /**
219         * Returns the number of elements in this buffer.
220         *
221         * @return the number of elements in this buffer
222         */
223        public int size() {
224            return size;
225        }
226    
227        /**
228         * Clears all elements from the buffer.
229         */
230        public void clear() {
231            elements = new Object[elements.length]; // for gc
232            size = 0;
233        }
234    
235        /**
236         * Adds an element to the buffer.
237         * <p>
238         * The element added will be sorted according to the comparator in use.
239         *
240         * @param element  the element to be added
241         * @return true always
242         */
243        public boolean add(Object element) {
244            if (isAtCapacity()) {
245                grow();
246            }
247            // percolate element to it's place in tree
248            if (ascendingOrder) {
249                percolateUpMinHeap(element);
250            } else {
251                percolateUpMaxHeap(element);
252            }
253            return true;
254        }
255    
256        /**
257         * Gets the next element to be removed without actually removing it (peek).
258         *
259         * @return the next element
260         * @throws BufferUnderflowException if the buffer is empty
261         */
262        public Object get() {
263            if (isEmpty()) {
264                throw new BufferUnderflowException();
265            } else {
266                return elements[1];
267            }
268        }
269    
270        /**
271         * Gets and removes the next element (pop).
272         *
273         * @return the next element
274         * @throws BufferUnderflowException if the buffer is empty
275         */
276        public Object remove() {
277            final Object result = get();
278            elements[1] = elements[size--];
279    
280            // set the unused element to 'null' so that the garbage collector
281            // can free the object if not used anywhere else.(remove reference)
282            elements[size + 1] = null;
283    
284            if (size != 0) {
285                // percolate top element to it's place in tree
286                if (ascendingOrder) {
287                    percolateDownMinHeap(1);
288                } else {
289                    percolateDownMaxHeap(1);
290                }
291            }
292    
293            return result;
294        }
295    
296        //-----------------------------------------------------------------------
297        /**
298         * Tests if the buffer is at capacity.
299         *
300         * @return <code>true</code> if buffer is full; <code>false</code> otherwise.
301         */
302        protected boolean isAtCapacity() {
303            //+1 as element 0 is noop
304            return elements.length == size + 1;
305        }
306    
307        
308        /**
309         * Percolates element down heap from the position given by the index.
310         * <p>
311         * Assumes it is a minimum heap.
312         *
313         * @param index the index for the element
314         */
315        protected void percolateDownMinHeap(final int index) {
316            final Object element = elements[index];
317            int hole = index;
318    
319            while ((hole * 2) <= size) {
320                int child = hole * 2;
321    
322                // if we have a right child and that child can not be percolated
323                // up then move onto other child
324                if (child != size && compare(elements[child + 1], elements[child]) < 0) {
325                    child++;
326                }
327    
328                // if we found resting place of bubble then terminate search
329                if (compare(elements[child], element) >= 0) {
330                    break;
331                }
332    
333                elements[hole] = elements[child];
334                hole = child;
335            }
336    
337            elements[hole] = element;
338        }
339    
340        /**
341         * Percolates element down heap from the position given by the index.
342         * <p>
343         * Assumes it is a maximum heap.
344         *
345         * @param index the index of the element
346         */
347        protected void percolateDownMaxHeap(final int index) {
348            final Object element = elements[index];
349            int hole = index;
350    
351            while ((hole * 2) <= size) {
352                int child = hole * 2;
353    
354                // if we have a right child and that child can not be percolated
355                // up then move onto other child
356                if (child != size && compare(elements[child + 1], elements[child]) > 0) {
357                    child++;
358                }
359    
360                // if we found resting place of bubble then terminate search
361                if (compare(elements[child], element) <= 0) {
362                    break;
363                }
364    
365                elements[hole] = elements[child];
366                hole = child;
367            }
368    
369            elements[hole] = element;
370        }
371    
372        /**
373         * Percolates element up heap from the position given by the index.
374         * <p>
375         * Assumes it is a minimum heap.
376         *
377         * @param index the index of the element to be percolated up
378         */
379        protected void percolateUpMinHeap(final int index) {
380            int hole = index;
381            Object element = elements[hole];
382            while (hole > 1 && compare(element, elements[hole / 2]) < 0) {
383                // save element that is being pushed down
384                // as the element "bubble" is percolated up
385                final int next = hole / 2;
386                elements[hole] = elements[next];
387                hole = next;
388            }
389            elements[hole] = element;
390        }
391    
392        /**
393         * Percolates a new element up heap from the bottom.
394         * <p>
395         * Assumes it is a minimum heap.
396         *
397         * @param element the element
398         */
399        protected void percolateUpMinHeap(final Object element) {
400            elements[++size] = element;
401            percolateUpMinHeap(size);
402        }
403    
404        /**
405         * Percolates element up heap from from the position given by the index.
406         * <p>
407         * Assume it is a maximum heap.
408         *
409         * @param index the index of the element to be percolated up
410         */
411        protected void percolateUpMaxHeap(final int index) {
412            int hole = index;
413            Object element = elements[hole];
414    
415            while (hole > 1 && compare(element, elements[hole / 2]) > 0) {
416                // save element that is being pushed down
417                // as the element "bubble" is percolated up
418                final int next = hole / 2;
419                elements[hole] = elements[next];
420                hole = next;
421            }
422    
423            elements[hole] = element;
424        }
425    
426        /**
427         * Percolates a new element up heap from the bottom.
428         * <p>
429         * Assume it is a maximum heap.
430         *
431         * @param element the element
432         */
433        protected void percolateUpMaxHeap(final Object element) {
434            elements[++size] = element;
435            percolateUpMaxHeap(size);
436        }
437    
438        /**
439         * Compares two objects using the comparator if specified, or the
440         * natural order otherwise.
441         * 
442         * @param a  the first object
443         * @param b  the second object
444         * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
445         */
446        protected int compare(Object a, Object b) {
447            if (comparator != null) {
448                return comparator.compare(a, b);
449            } else {
450                return ((Comparable) a).compareTo(b);
451            }
452        }
453    
454        /**
455         * Increases the size of the heap to support additional elements
456         */
457        protected void grow() {
458            final Object[] array = new Object[elements.length * 2];
459            System.arraycopy(elements, 0, array, 0, elements.length);
460            elements = array;
461        }
462    
463        //-----------------------------------------------------------------------
464        /**
465         * Returns an iterator over this heap's elements.
466         *
467         * @return an iterator over this heap's elements
468         */
469        public Iterator iterator() {
470            return new Iterator() {
471    
472                private int index = 1;
473                private int lastReturnedIndex = -1;
474    
475                public boolean hasNext() {
476                    return index <= size;
477                }
478    
479                public Object next() {
480                    if (!hasNext()) {
481                        throw new NoSuchElementException();
482                    }
483                    lastReturnedIndex = index;
484                    index++;
485                    return elements[lastReturnedIndex];
486                }
487    
488                public void remove() {
489                    if (lastReturnedIndex == -1) {
490                        throw new IllegalStateException();
491                    }
492                    elements[ lastReturnedIndex ] = elements[ size ];
493                    elements[ size ] = null;
494                    size--;  
495                    if( size != 0 && lastReturnedIndex <= size) {
496                        int compareToParent = 0;
497                        if (lastReturnedIndex > 1) {
498                            compareToParent = compare(elements[lastReturnedIndex], 
499                                elements[lastReturnedIndex / 2]);  
500                        }
501                        if (ascendingOrder) {
502                            if (lastReturnedIndex > 1 && compareToParent < 0) {
503                                percolateUpMinHeap(lastReturnedIndex); 
504                            } else {
505                                percolateDownMinHeap(lastReturnedIndex);
506                            }
507                        } else {  // max heap
508                            if (lastReturnedIndex > 1 && compareToParent > 0) {
509                                percolateUpMaxHeap(lastReturnedIndex); 
510                            } else {
511                                percolateDownMaxHeap(lastReturnedIndex);
512                            }
513                        }          
514                    }
515                    index--;
516                    lastReturnedIndex = -1; 
517                }
518    
519            };
520        }
521    
522        /**
523         * Returns a string representation of this heap.  The returned string
524         * is similar to those produced by standard JDK collections.
525         *
526         * @return a string representation of this heap
527         */
528        public String toString() {
529            final StringBuffer sb = new StringBuffer();
530    
531            sb.append("[ ");
532    
533            for (int i = 1; i < size + 1; i++) {
534                if (i != 1) {
535                    sb.append(", ");
536                }
537                sb.append(elements[i]);
538            }
539    
540            sb.append(" ]");
541    
542            return sb.toString();
543        }
544    
545    }