001: /*
002: File: Heap.java
003:
004: Originally written by Doug Lea and released into the public domain.
005: This may be used for any purposes whatsoever without acknowledgment.
006: Thanks for the assistance and support of Sun Microsystems Labs,
007: and everyone contributing, testing, and using this code.
008:
009: History:
010: Date Who What
011: 29Aug1998 dl Refactored from BoundedPriorityQueue
012: 08dec2001 dl Null out slots of removed items
013: 03feb2002 dl Also null out in clear
014: */
015:
016: package EDU.oswego.cs.dl.util.concurrent;
017:
018: import java.util.Comparator;
019:
020: /**
021: * A heap-based priority queue, without any concurrency control
022: * (i.e., no blocking on empty/full states).
023: * This class provides the data structure mechanics for BoundedPriorityQueue.
024: * <p>
025: * The class currently uses a standard array-based heap, as described
026: * in, for example, Sedgewick's Algorithms text. All methods
027: * are fully synchronized. In the future,
028: * it may instead use structures permitting finer-grained locking.
029: * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
030: **/
031:
032: public class Heap {
033: protected Object[] nodes_; // the tree nodes, packed into an array
034: protected int count_ = 0; // number of used slots
035: protected final Comparator cmp_; // for ordering
036:
037: /**
038: * Create a Heap with the given initial capacity and comparator
039: * @exception IllegalArgumentException if capacity less or equal to zero
040: **/
041:
042: public Heap(int capacity, Comparator cmp)
043: throws IllegalArgumentException {
044: if (capacity <= 0)
045: throw new IllegalArgumentException();
046: nodes_ = new Object[capacity];
047: cmp_ = cmp;
048: }
049:
050: /**
051: * Create a Heap with the given capacity,
052: * and relying on natural ordering.
053: **/
054:
055: public Heap(int capacity) {
056: this (capacity, null);
057: }
058:
059: /** perform element comaprisons using comparator or natural ordering **/
060: protected int compare(Object a, Object b) {
061: if (cmp_ == null)
062: return ((Comparable) a).compareTo(b);
063: else
064: return cmp_.compare(a, b);
065: }
066:
067: // indexes of heap parents and children
068: protected final int parent(int k) {
069: return (k - 1) / 2;
070: }
071:
072: protected final int left(int k) {
073: return 2 * k + 1;
074: }
075:
076: protected final int right(int k) {
077: return 2 * (k + 1);
078: }
079:
080: /**
081: * insert an element, resize if necessary
082: **/
083: public synchronized void insert(Object x) {
084: if (count_ >= nodes_.length) {
085: int newcap = 3 * nodes_.length / 2 + 1;
086: Object[] newnodes = new Object[newcap];
087: System.arraycopy(nodes_, 0, newnodes, 0, nodes_.length);
088: nodes_ = newnodes;
089: }
090:
091: int k = count_;
092: ++count_;
093: while (k > 0) {
094: int par = parent(k);
095: if (compare(x, nodes_[par]) < 0) {
096: nodes_[k] = nodes_[par];
097: k = par;
098: } else
099: break;
100: }
101: nodes_[k] = x;
102: }
103:
104: /**
105: * Return and remove least element, or null if empty
106: **/
107:
108: public synchronized Object extract() {
109: if (count_ < 1)
110: return null;
111:
112: int k = 0; // take element at root;
113: Object least = nodes_[k];
114: --count_;
115: Object x = nodes_[count_];
116: nodes_[count_] = null;
117: for (;;) {
118: int l = left(k);
119: if (l >= count_)
120: break;
121: else {
122: int r = right(k);
123: int child = (r >= count_ || compare(nodes_[l],
124: nodes_[r]) < 0) ? l : r;
125: if (compare(x, nodes_[child]) > 0) {
126: nodes_[k] = nodes_[child];
127: k = child;
128: } else
129: break;
130: }
131: }
132: nodes_[k] = x;
133: return least;
134: }
135:
136: /** Return least element without removing it, or null if empty **/
137: public synchronized Object peek() {
138: if (count_ > 0)
139: return nodes_[0];
140: else
141: return null;
142: }
143:
144: /** Return number of elements **/
145: public synchronized int size() {
146: return count_;
147: }
148:
149: /** remove all elements **/
150: public synchronized void clear() {
151: for (int i = 0; i < count_; ++i)
152: nodes_[i] = null;
153: count_ = 0;
154: }
155:
156: }
|