Mercurial > hg > blitz_condensed
comparison 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 |
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 } |