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 <= <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 <= <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><= 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><= 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 }