Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/Heap.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 /*
2 File: Heap.java
3
4 Originally written by Doug Lea and released into the public domain.
5 This may be used for any purposes whatsoever without acknowledgment.
6 Thanks for the assistance and support of Sun Microsystems Labs,
7 and everyone contributing, testing, and using this code.
8
9 History:
10 Date Who What
11 29Aug1998 dl Refactored from BoundedPriorityQueue
12 08dec2001 dl Null out slots of removed items
13 03feb2002 dl Also null out in clear
14 */
15
16 package EDU.oswego.cs.dl.util.concurrent;
17 import java.util.Comparator;
18
19 /**
20 * A heap-based priority queue, without any concurrency control
21 * (i.e., no blocking on empty/full states).
22 * This class provides the data structure mechanics for BoundedPriorityQueue.
23 * <p>
24 * The class currently uses a standard array-based heap, as described
25 * in, for example, Sedgewick's Algorithms text. All methods
26 * are fully synchronized. In the future,
27 * it may instead use structures permitting finer-grained locking.
28 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
29 **/
30
31 public class Heap {
32 protected Object[] nodes_; // the tree nodes, packed into an array
33 protected int count_ = 0; // number of used slots
34 protected final Comparator cmp_; // for ordering
35
36 /**
37 * Create a Heap with the given initial capacity and comparator
38 * @exception IllegalArgumentException if capacity less or equal to zero
39 **/
40
41 public Heap(int capacity, Comparator cmp)
42 throws IllegalArgumentException {
43 if (capacity <= 0) throw new IllegalArgumentException();
44 nodes_ = new Object[capacity];
45 cmp_ = cmp;
46 }
47
48 /**
49 * Create a Heap with the given capacity,
50 * and relying on natural ordering.
51 **/
52
53 public Heap(int capacity) {
54 this(capacity, null);
55 }
56
57
58 /** perform element comaprisons using comparator or natural ordering **/
59 protected int compare(Object a, Object b) {
60 if (cmp_ == null)
61 return ((Comparable)a).compareTo(b);
62 else
63 return cmp_.compare(a, b);
64 }
65
66
67 // indexes of heap parents and children
68 protected final int parent(int k) { return (k - 1) / 2; }
69 protected final int left(int k) { return 2 * k + 1; }
70 protected final int right(int k) { return 2 * (k + 1); }
71
72 /**
73 * insert an element, resize if necessary
74 **/
75 public synchronized void insert(Object x) {
76 if (count_ >= nodes_.length) {
77 int newcap = 3 * nodes_.length / 2 + 1;
78 Object[] newnodes = new Object[newcap];
79 System.arraycopy(nodes_, 0, newnodes, 0, nodes_.length);
80 nodes_ = newnodes;
81 }
82
83 int k = count_;
84 ++count_;
85 while (k > 0) {
86 int par = parent(k);
87 if (compare(x, nodes_[par]) < 0) {
88 nodes_[k] = nodes_[par];
89 k = par;
90 }
91 else break;
92 }
93 nodes_[k] = x;
94 }
95
96
97 /**
98 * Return and remove least element, or null if empty
99 **/
100
101 public synchronized Object extract() {
102 if (count_ < 1) return null;
103
104 int k = 0; // take element at root;
105 Object least = nodes_[k];
106 --count_;
107 Object x = nodes_[count_];
108 nodes_[count_] = null;
109 for (;;) {
110 int l = left(k);
111 if (l >= count_)
112 break;
113 else {
114 int r = right(k);
115 int child = (r >= count_ || compare(nodes_[l], nodes_[r]) < 0)? l : r;
116 if (compare(x, nodes_[child]) > 0) {
117 nodes_[k] = nodes_[child];
118 k = child;
119 }
120 else break;
121 }
122 }
123 nodes_[k] = x;
124 return least;
125 }
126
127 /** Return least element without removing it, or null if empty **/
128 public synchronized Object peek() {
129 if (count_ > 0)
130 return nodes_[0];
131 else
132 return null;
133 }
134
135 /** Return number of elements **/
136 public synchronized int size() {
137 return count_;
138 }
139
140 /** remove all elements **/
141 public synchronized void clear() {
142 for (int i = 0; i < count_; ++i)
143 nodes_[i] = null;
144 count_ = 0;
145 }
146
147 }