001: /*
002: * Copyright 2001-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.buffer;
017:
018: import java.io.Serializable;
019: import java.util.AbstractCollection;
020: import java.util.Comparator;
021: import java.util.Iterator;
022: import java.util.NoSuchElementException;
023:
024: import org.apache.commons.collections.Buffer;
025: import org.apache.commons.collections.BufferUnderflowException;
026:
027: /**
028: * Binary heap implementation of <code>Buffer</code> that provides for
029: * removal based on <code>Comparator</code> ordering.
030: * <p>
031: * The removal order of a binary heap is based on either the natural sort
032: * order of its elements or a specified {@link Comparator}. The
033: * {@link #remove()} method always returns the first element as determined
034: * by the sort order. (The <code>ascendingOrder</code> flag in the constructors
035: * can be used to reverse the sort order, in which case {@link #remove()}
036: * will always remove the last element.) The removal order is
037: * <i>not</i> the same as the order of iteration; elements are
038: * returned by the iterator in no particular order.
039: * <p>
040: * The {@link #add(Object)} and {@link #remove()} operations perform
041: * in logarithmic time. The {@link #get()} operation performs in constant
042: * time. All other operations perform in linear time or worse.
043: * <p>
044: * Note that this implementation is not synchronized. Use
045: * {@link org.apache.commons.collections.BufferUtils#synchronizedBuffer(Buffer)} or
046: * {@link org.apache.commons.collections.buffer.SynchronizedBuffer#decorate(Buffer)}
047: * to provide synchronized access to a <code>PriorityBuffer</code>:
048: * <pre>
049: * Buffer heap = SynchronizedBuffer.decorate(new PriorityBuffer());
050: * </pre>
051: * <p>
052: * This class is Serializable from Commons Collections 3.2.
053: *
054: * @since Commons Collections 3.0 (previously BinaryHeap v1.0)
055: * @version $Revision: 405927 $ $Date: 2006-05-12 23:57:03 +0100 (Fri, 12 May 2006) $
056: *
057: * @author Peter Donald
058: * @author Ram Chidambaram
059: * @author Michael A. Smith
060: * @author Paul Jack
061: * @author Stephen Colebourne
062: * @author Steve Phelps
063: */
064: public class PriorityBuffer extends AbstractCollection implements
065: Buffer, Serializable {
066:
067: /** Serialization lock. */
068: private static final long serialVersionUID = 6891186490470027896L;
069:
070: /**
071: * The default capacity for the buffer.
072: */
073: private static final int DEFAULT_CAPACITY = 13;
074:
075: /**
076: * The elements in this buffer.
077: */
078: protected Object[] elements;
079: /**
080: * The number of elements currently in this buffer.
081: */
082: protected int size;
083: /**
084: * If true, the first element as determined by the sort order will
085: * be returned. If false, the last element as determined by the
086: * sort order will be returned.
087: */
088: protected boolean ascendingOrder;
089: /**
090: * The comparator used to order the elements
091: */
092: protected Comparator comparator;
093:
094: //-----------------------------------------------------------------------
095: /**
096: * Constructs a new empty buffer that sorts in ascending order by the
097: * natural order of the objects added.
098: */
099: public PriorityBuffer() {
100: this (DEFAULT_CAPACITY, true, null);
101: }
102:
103: /**
104: * Constructs a new empty buffer that sorts in ascending order using the
105: * specified comparator.
106: *
107: * @param comparator the comparator used to order the elements,
108: * null means use natural order
109: */
110: public PriorityBuffer(Comparator comparator) {
111: this (DEFAULT_CAPACITY, true, comparator);
112: }
113:
114: /**
115: * Constructs a new empty buffer specifying the sort order and using the
116: * natural order of the objects added.
117: *
118: * @param ascendingOrder if <code>true</code> the heap is created as a
119: * minimum heap; otherwise, the heap is created as a maximum heap
120: */
121: public PriorityBuffer(boolean ascendingOrder) {
122: this (DEFAULT_CAPACITY, ascendingOrder, null);
123: }
124:
125: /**
126: * Constructs a new empty buffer specifying the sort order and comparator.
127: *
128: * @param ascendingOrder true to use the order imposed by the given
129: * comparator; false to reverse that order
130: * @param comparator the comparator used to order the elements,
131: * null means use natural order
132: */
133: public PriorityBuffer(boolean ascendingOrder, Comparator comparator) {
134: this (DEFAULT_CAPACITY, ascendingOrder, comparator);
135: }
136:
137: /**
138: * Constructs a new empty buffer that sorts in ascending order by the
139: * natural order of the objects added, specifying an initial capacity.
140: *
141: * @param capacity the initial capacity for the buffer, greater than zero
142: * @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code>
143: */
144: public PriorityBuffer(int capacity) {
145: this (capacity, true, null);
146: }
147:
148: /**
149: * Constructs a new empty buffer that sorts in ascending order using the
150: * specified comparator and initial capacity.
151: *
152: * @param capacity the initial capacity for the buffer, greater than zero
153: * @param comparator the comparator used to order the elements,
154: * null means use natural order
155: * @throws IllegalArgumentException if <code>capacity</code> is <= <code>0</code>
156: */
157: public PriorityBuffer(int capacity, Comparator comparator) {
158: this (capacity, true, comparator);
159: }
160:
161: /**
162: * Constructs a new empty buffer that specifying initial capacity and
163: * sort order, using the natural order of the objects added.
164: *
165: * @param capacity the initial capacity for the buffer, greater than zero
166: * @param ascendingOrder if <code>true</code> the heap is created as a
167: * minimum heap; otherwise, the heap is created as a maximum heap.
168: * @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code>
169: */
170: public PriorityBuffer(int capacity, boolean ascendingOrder) {
171: this (capacity, ascendingOrder, null);
172: }
173:
174: /**
175: * Constructs a new empty buffer that specifying initial capacity,
176: * sort order and comparator.
177: *
178: * @param capacity the initial capacity for the buffer, greater than zero
179: * @param ascendingOrder true to use the order imposed by the given
180: * comparator; false to reverse that order
181: * @param comparator the comparator used to order the elements,
182: * null means use natural order
183: * @throws IllegalArgumentException if <code>capacity</code> is <code><= 0</code>
184: */
185: public PriorityBuffer(int capacity, boolean ascendingOrder,
186: 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: * Percolates element down heap from the position given by the index.
309: * <p>
310: * Assumes it is a minimum heap.
311: *
312: * @param index the index for the element
313: */
314: protected void percolateDownMinHeap(final int index) {
315: final Object element = elements[index];
316: int hole = index;
317:
318: while ((hole * 2) <= size) {
319: int child = hole * 2;
320:
321: // if we have a right child and that child can not be percolated
322: // up then move onto other child
323: if (child != size
324: && 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
357: && compare(elements[child + 1], elements[child]) > 0) {
358: child++;
359: }
360:
361: // if we found resting place of bubble then terminate search
362: if (compare(elements[child], element) <= 0) {
363: break;
364: }
365:
366: elements[hole] = elements[child];
367: hole = child;
368: }
369:
370: elements[hole] = element;
371: }
372:
373: /**
374: * Percolates element up heap from the position given by the index.
375: * <p>
376: * Assumes it is a minimum heap.
377: *
378: * @param index the index of the element to be percolated up
379: */
380: protected void percolateUpMinHeap(final int index) {
381: int hole = index;
382: Object element = elements[hole];
383: while (hole > 1 && compare(element, elements[hole / 2]) < 0) {
384: // save element that is being pushed down
385: // as the element "bubble" is percolated up
386: final int next = hole / 2;
387: elements[hole] = elements[next];
388: hole = next;
389: }
390: elements[hole] = element;
391: }
392:
393: /**
394: * Percolates a new element up heap from the bottom.
395: * <p>
396: * Assumes it is a minimum heap.
397: *
398: * @param element the element
399: */
400: protected void percolateUpMinHeap(final Object element) {
401: elements[++size] = element;
402: percolateUpMinHeap(size);
403: }
404:
405: /**
406: * Percolates element up heap from from the position given by the index.
407: * <p>
408: * Assume it is a maximum heap.
409: *
410: * @param index the index of the element to be percolated up
411: */
412: protected void percolateUpMaxHeap(final int index) {
413: int hole = index;
414: Object element = elements[hole];
415:
416: while (hole > 1 && compare(element, elements[hole / 2]) > 0) {
417: // save element that is being pushed down
418: // as the element "bubble" is percolated up
419: final int next = hole / 2;
420: elements[hole] = elements[next];
421: hole = next;
422: }
423:
424: elements[hole] = element;
425: }
426:
427: /**
428: * Percolates a new element up heap from the bottom.
429: * <p>
430: * Assume it is a maximum heap.
431: *
432: * @param element the element
433: */
434: protected void percolateUpMaxHeap(final Object element) {
435: elements[++size] = element;
436: percolateUpMaxHeap(size);
437: }
438:
439: /**
440: * Compares two objects using the comparator if specified, or the
441: * natural order otherwise.
442: *
443: * @param a the first object
444: * @param b the second object
445: * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
446: */
447: protected int compare(Object a, Object b) {
448: if (comparator != null) {
449: return comparator.compare(a, b);
450: } else {
451: return ((Comparable) a).compareTo(b);
452: }
453: }
454:
455: /**
456: * Increases the size of the heap to support additional elements
457: */
458: protected void grow() {
459: final Object[] array = new Object[elements.length * 2];
460: System.arraycopy(elements, 0, array, 0, elements.length);
461: elements = array;
462: }
463:
464: //-----------------------------------------------------------------------
465: /**
466: * Returns an iterator over this heap's elements.
467: *
468: * @return an iterator over this heap's elements
469: */
470: public Iterator iterator() {
471: return new Iterator() {
472:
473: private int index = 1;
474: private int lastReturnedIndex = -1;
475:
476: public boolean hasNext() {
477: return index <= size;
478: }
479:
480: public Object next() {
481: if (!hasNext()) {
482: throw new NoSuchElementException();
483: }
484: lastReturnedIndex = index;
485: index++;
486: return elements[lastReturnedIndex];
487: }
488:
489: public void remove() {
490: if (lastReturnedIndex == -1) {
491: throw new IllegalStateException();
492: }
493: elements[lastReturnedIndex] = elements[size];
494: elements[size] = null;
495: size--;
496: if (size != 0 && lastReturnedIndex <= size) {
497: int compareToParent = 0;
498: if (lastReturnedIndex > 1) {
499: compareToParent = compare(
500: elements[lastReturnedIndex],
501: elements[lastReturnedIndex / 2]);
502: }
503: if (ascendingOrder) {
504: if (lastReturnedIndex > 1
505: && compareToParent < 0) {
506: percolateUpMinHeap(lastReturnedIndex);
507: } else {
508: percolateDownMinHeap(lastReturnedIndex);
509: }
510: } else { // max heap
511: if (lastReturnedIndex > 1
512: && compareToParent > 0) {
513: percolateUpMaxHeap(lastReturnedIndex);
514: } else {
515: percolateDownMaxHeap(lastReturnedIndex);
516: }
517: }
518: }
519: index--;
520: lastReturnedIndex = -1;
521: }
522:
523: };
524: }
525:
526: /**
527: * Returns a string representation of this heap. The returned string
528: * is similar to those produced by standard JDK collections.
529: *
530: * @return a string representation of this heap
531: */
532: public String toString() {
533: final StringBuffer sb = new StringBuffer();
534:
535: sb.append("[ ");
536:
537: for (int i = 1; i < size + 1; i++) {
538: if (i != 1) {
539: sb.append(", ");
540: }
541: sb.append(elements[i]);
542: }
543:
544: sb.append(" ]");
545:
546: return sb.toString();
547: }
548:
549: }
|