KickJava.com: Code - Class EDU.oswego.cs.dl.util.concurrent.Heap

Java API By Example, From Geeks To Geeks.

| Browse | Search | Books |

Code - Class EDU.oswego.cs.dl.util.concurrent.Heap

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 }
148