Mercurial > hg > blitz_condensed
diff src/EDU/oswego/cs/dl/util/concurrent/Heap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/EDU/oswego/cs/dl/util/concurrent/Heap.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,147 @@ +/* + File: Heap.java + + Originally written by Doug Lea and released into the public domain. + This may be used for any purposes whatsoever without acknowledgment. + Thanks for the assistance and support of Sun Microsystems Labs, + and everyone contributing, testing, and using this code. + + History: + Date Who What + 29Aug1998 dl Refactored from BoundedPriorityQueue + 08dec2001 dl Null out slots of removed items + 03feb2002 dl Also null out in clear +*/ + +package EDU.oswego.cs.dl.util.concurrent; +import java.util.Comparator; + +/** + * A heap-based priority queue, without any concurrency control + * (i.e., no blocking on empty/full states). + * This class provides the data structure mechanics for BoundedPriorityQueue. + * <p> + * The class currently uses a standard array-based heap, as described + * in, for example, Sedgewick's Algorithms text. All methods + * are fully synchronized. In the future, + * it may instead use structures permitting finer-grained locking. + * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] + **/ + +public class Heap { + protected Object[] nodes_; // the tree nodes, packed into an array + protected int count_ = 0; // number of used slots + protected final Comparator cmp_; // for ordering + + /** + * Create a Heap with the given initial capacity and comparator + * @exception IllegalArgumentException if capacity less or equal to zero + **/ + + public Heap(int capacity, Comparator cmp) + throws IllegalArgumentException { + if (capacity <= 0) throw new IllegalArgumentException(); + nodes_ = new Object[capacity]; + cmp_ = cmp; + } + + /** + * Create a Heap with the given capacity, + * and relying on natural ordering. + **/ + + public Heap(int capacity) { + this(capacity, null); + } + + + /** perform element comaprisons using comparator or natural ordering **/ + protected int compare(Object a, Object b) { + if (cmp_ == null) + return ((Comparable)a).compareTo(b); + else + return cmp_.compare(a, b); + } + + + // indexes of heap parents and children + protected final int parent(int k) { return (k - 1) / 2; } + protected final int left(int k) { return 2 * k + 1; } + protected final int right(int k) { return 2 * (k + 1); } + + /** + * insert an element, resize if necessary + **/ + public synchronized void insert(Object x) { + if (count_ >= nodes_.length) { + int newcap = 3 * nodes_.length / 2 + 1; + Object[] newnodes = new Object[newcap]; + System.arraycopy(nodes_, 0, newnodes, 0, nodes_.length); + nodes_ = newnodes; + } + + int k = count_; + ++count_; + while (k > 0) { + int par = parent(k); + if (compare(x, nodes_[par]) < 0) { + nodes_[k] = nodes_[par]; + k = par; + } + else break; + } + nodes_[k] = x; + } + + + /** + * Return and remove least element, or null if empty + **/ + + public synchronized Object extract() { + if (count_ < 1) return null; + + int k = 0; // take element at root; + Object least = nodes_[k]; + --count_; + Object x = nodes_[count_]; + nodes_[count_] = null; + for (;;) { + int l = left(k); + if (l >= count_) + break; + else { + int r = right(k); + int child = (r >= count_ || compare(nodes_[l], nodes_[r]) < 0)? l : r; + if (compare(x, nodes_[child]) > 0) { + nodes_[k] = nodes_[child]; + k = child; + } + else break; + } + } + nodes_[k] = x; + return least; + } + + /** Return least element without removing it, or null if empty **/ + public synchronized Object peek() { + if (count_ > 0) + return nodes_[0]; + else + return null; + } + + /** Return number of elements **/ + public synchronized int size() { + return count_; + } + + /** remove all elements **/ + public synchronized void clear() { + for (int i = 0; i < count_; ++i) + nodes_[i] = null; + count_ = 0; + } + +}