1: // timerq_tc.H -- generic leftist heap for priority/timer queues, etc. Rj Brown, 08/13/93.
3: #ifndef __timerq_tc__H
4: #define __timerq_tc__H
6: #include <sys/types.h>
9: // This header file implements a generic template for leftist heaps of objects. A
10: // leftist heap is a particularly efficient way to implement a priority queue or timer
11: // queue. It is also useful for determining which element is an extremum (maximum or
12: // minimum) of a set, or even the n least or n greatest elements of a set.
13: //
14: // A leftist heap is implemented as a special kind of binary tree. Its definition
15: // guarantees that the root of the tree contains the extreme value member of the set of
16: // objects in the tree. This is also true for each of the sub-trees of the root, etc.
17: // Furthermore, it is guaranteed that the shortest path from any node to a terminal, or leaf,
18: // node may be found by following the right subtree. This causes the tree to become larger
19: // on the left side than the right, hence the name "leftist tree" -- it "leans to the left".
20: //
21: // The leftist heap is very good for merging 2 leftist heaps together to form a new
22: // leftist heap that contains all the members of the 2 original heaps. The merge can be
23: // done in O(log n) time, which is faster than a simple linear list for all but the smallest
24: // of sets. For details of the theory and implementation of leftist heaps, and complexity
25: // and timing analysis, see:
26: //
27: // Brown, R. J. 1987. An efficient algorithm for large priority queues. DDJ June 1987.
28: //
29: // Crane, C. A. 1972. Linear lists and priority queues as balanced binary trees. Tech. Rep.
30: // STAN-CS-72-259, Computer Science Dept., Stanford Univ. Stanford, CA.
31: //
32: // Knuth, D. E. 1973. The Art of Computer Programming, Vol 3: Sorting and Searching.
33: // Addison-Wesley, Reading, MA.
34: //
35: // Tarjan, R. E. 1983. Data Structures and Network Algorithms. SIAM, Philadelphia, PA.
38: // A node to control each element in the queue.
40: template<class data_c> class node_tc{
42: // FIXME
43: // This must eventually use an over-ridden "new" and "delete" that
44: // allocates and releases using a pool_tc<node_tc<data_c*> > instead of a
45: // call to "malloc" and "free" with the default "new" and "delete".
47: public:
49: node_tc<data_c>* parent; // back pointer to parent of this node
50: node_tc<data_c>* left; // pointer to left sub-tree
51: node_tc<data_c>* right; // pointer to right sub-tree
52: data_c* data; // pointer to users data
53: int dist; // minimum distance to a leaf
54:
55: // CONSTRUCTOR
56: //
57: // Wrap a data element up in a tree node.
58: // This effectivly makes a priority queue of one element.
60: node_tc(data_c* dp) {
61: data = dp; // hook up to data element
62: parent = NULL; // has no parent
63: left = NULL; // has no subtrees
64: right = NULL;
65: dist = 1; // distance to leaf is 1 for leaf-most nodes
66: // (NULL has distance of 0)
67: }
68:
70: // DESTRUCTOR
71: //
72: // We need to fix any pointers to the soon-to-be-deceased node so that
73: // they are NULL. This will help prevent dangling references.
74: //
75: // A problem could be that since we cut off the left and right kids, that
76: // a memory leak could occur if they had nobody else pointing to them.
77: // Oh well, that's why Lisp has a garbage collector! In stupid C++ you
78: // must keep track of these nits...
79: //
80: // FIXME Should we throw an error if the kids are *NOT* NULL?
82: ~node_tc() {
84: if (parent != NULL) { // does this node even have a parent?
85: if (parent->left == this) { // yes, is it seated on the left hand?
86: parent -> left = NULL; // yes, cut it off!
87: } else if (parent->right == this) { // or on the right hand?
88: parent -> right = NULL; // yes, cut it off!
89: } // should we throw an error otherwise?
90: // FIXME What if it is seated on *BOTH* sides !?!
91: }
92:
93: if (left != NULL) { // any left kids to cut off?
94: if (left->parent == this) { // yes, do they claim us as parents?
95: left->parent = NULL; // yes, cut them off!
96: } // should we throw an error otherwise?
97: }
98:
99: if (right != NULL) { // any right kids to cut off?
100: if (right->parent == this) { // yes, do they claim us as parents?
101: right->parent = NULL; // yes, cut them off!
102: }
103: } // should we throw an error otherwise?
104: // FIXME What about danglers in the data field ???
105: }
106:
108: // Return the distance from a given node to a leaf.
109: //
110: // This transparently handles case of NULL pointer to node.
111:
112: int distance(node_tc<data_c>* p) {
113: if (p == NULL) { // if node is non-existent,
114: return 0; // then it has a distance of zero,
115: } else { // otherwise
116: return p->dist; // it has the distance that p points to.
117: }
118: }
119:
120:
121: // TREE TRAVERSAL
122: //
123: // The following routine traverses a binary tree pointed to by p, visiting each node
124: // by deleting it, but only after deleting its subtrees recursively.
125: //
126: // See the folowing for details on the implementation and analysis of this tree
127: // traversal algorithm:
128: //
129: // Knuth D. E. 1969. The Art of Computer Programming, Vol 1. Fundamental Algorithms,
130: // Addison Wessley, Reading, MA.
131:
132: // Knuths end-order tree traversal
133:
134: void end_order_delete(void) {
136: if (this == NULL) { // if there is no tree at all,
137: return; // then do nothing!
138: }
140: left->end_order_delete(); // traverse the left subtree
141: right->end_order_delete(); // traverse the right subtree
142:
143: delete this; // delete this node
144: }
145:
146:
147: // Merge 2 priority/timer queues.
148: //
149: // This routine only merges the 2 right legs by descending down them;
150: // it does not balance the tree, or fix up the distances!
151: // It returns a pointer to the leaf-most node affected.
152: // The "balance" routine must be called after "merge" to fix up the tree.
153: //
154: // This "merge" routine, together with the "balance" routine, implement an
155: // iterative algorithm for combining 2 leftist heaps. This is similar
156: // to the algorithm given by Knuth, as contrasted with the recursive
157: // algorithm given by Tarjan. The implementation given here takes
158: // advantage of the presence of the "parent" back-pointers to simplify
159: // the balancing part of the process, whereas Knuth does not assume the
160: // presence of back-pointers. We need the back-pointers to perform
161: // the deletions needed to "advance" a node in the heap. The iterative
162: // implementation is prefered because its execution speed is faster,
163: // although the recursive implementation is somewhat easier to understand.
164:
165: // (p->data->precedes(q->data, p->data))
166: // (p->data->precedes(r->data, q->data))
167:
168: boolean in_order(node_tc<data_c>* a, node_tc<data_c>* b) { // are nodes *a and *b in proper order?
169:
170: if(b == NULL) { // if there ain't no b, then a's gotta be first!
171: return TRUE;
172: }
173:
174: if(a == NULL) { // we've got an a, but no b, so they're backwards!
175: return FALSE;
176: }
177:
178: return a->data->precedes(a->data, b->data); // we gotta do this one the HARD way!
179: }
182: node_tc<data_c>* merge(node_tc<data_c>* p, node_tc<data_c>* q) {
183: node_tc<data_c>* r; // a temporary pointer to a node
184: boolean precedes(data_c* p, data_c* q);
185:
186: if (q == NULL) { // is q empty?
187: return p; // yes, p is the answer, return
188: }
189:
190: while (p != NULL) { // for as long as p exists...
191:
192: // Make sure p precedes q. If not, fix it!
193:
194: if (!in_order(p, q)) { // does p come before q?
195: r = p; // no, we want p to be the earliest
196: p = q; // so swap p
197: q = r; // with q
198: }
199:
200: // Now we have p > q. By definition p > r. Check if p > q > r. If so, insert q between p and r.
201:
202: r = p->right; // descend down right side of tree leafwards
203:
204: if (in_order(q, r)) { // does q come before p's rite subtree?
205: p->right = q; // yes, insert q
206: q->parent = p; // between p and r
207: }
208:
209: p = r; // move down the right branch
210: }
211:
212: return q; // return the last node affected
213: }
214:
215:
216: // Balance the tree resulting from merge above, and fix up distances.
217: // This routine ascends up the tree produced by merge.
218: // The argument is the end of the merge, as returned by merge.
219: // The "balance" routine returns a pointer to the balanced tree.
220:
221: node_tc<data_c>* balance(node_tc<data_c>* q) {
222: node_tc<data_c>* p = NULL; // temporary pointer
223:
224: while (q != NULL) { // are we at the root yet?
225: p = q; // no, work on this node
226:
227: if (distance(p->left) < distance(p->right)) { // is this node out of balance?
228: q = p->left; // yes,
229: p->left = p->right; // swap left and
230: p->right = q; // right subtrees,
231: }
232:
233: p->dist = distance(p->right) + 1; // fix up distance
234: q = p->parent; // ascend up the tree root-wards
235: }
236:
237: return p; // return pointer to root of tree
238: }
239:
240:
241: // combine 2 priority/timer queues into 1 queue
242:
243: node_tc<data_c>* combine(node_tc<data_c>* p, node_tc<data_c>* q) {
244: return balance(merge(p, q)); // return result of balancing the merger of the 2 queues
245: }
246:
247: }; /* end class node_tc */
250: template<class data_c> class timerq_tc {
251:
252: private: // Private Instance Variables
253:
254: // The list head for the leftist heap.
255:
256: node_tc<data_c>* tree; // pointer to leftist tree
257: fifo_tc<node_tc<data_c> >* batch_que; // pointer to batchification queue
258:
259:
260: public: // Public Methods
261:
262: // Constructor
263:
264: timerq_tc() {
265: tree = NULL; // tree is initially empty
266: }
267:
268:
269: // Destructor
270:
271: ~timerq_tc() {
272: tree->end_order_delete(); // delete all the nodes & data items
273: }
274:
275:
276: // Return a pointer to the head data item on a queue.
277:
278: data_c* queue_head() {
279: if (tree == NULL) { // if no queue,
280: return NULL; // return NULL
281: } else { // otherwise,
282: return tree->data; // return pointer to users data
283: }
284: }
285:
286:
287: // enqueue a user data element on a queue
288: // returns a pointer to the queue node
289:
290: node_tc<data_c>* enque(data_c* dp) {
291: node_tc<data_c>* p = new node_tc<data_c>(dp); // wrap up user data as a 1 element heap
292:
293: tree = tree->node_tc<data_c>::combine(p, tree); // combine new element with old tree
294:
295: return p; // return pointer to new element
296: }
297:
298:
299: // dequeue the head element from the queue
300:
301: data_c* deque() {
302: node_tc<data_c>* tp = tree; // pointer to node at head of queue
303: node_tc<data_c>* lp = tp->left; // pointer to left subtree
304: node_tc<data_c>* rp = tp->right; // pointer to right subtree
305: data_c* dp = tp->data; // pointer to data at head of queue
307: if (lp != NULL) { // if the is a left kid,
308: lp->parent = NULL; // he forgets that the dequeued node
309: } // was his parent
311: if (rp != NULL) { // if the is a right kid,
312: rp->parent = NULL; // he forgets that the dequeued node
313: } // was his parent
315: tree = tp->combine(tp->left, // make tree less root by combining left
316: tp->right); // and right subtrees
318: delete tp; // get rid of the tree node
319: // that held the dequeued user data
320:
321: return dp; // return user data removed from head of queue
322: }
323:
324:
325: // Advance an element towards the head of the queue.
326: // This routine operates upon a node whose key has been modified.
327: // The assumptions are:
328: // 1. The new key precedes the old key. This means that both the left
329: // and right subtrees are therefore still in proper precedence order
330: // with respect to the affected node. The affected node, together
331: // with both its left and right subtrees, now needs to be moved
332: // towards the root of the tree.
333: // 2. The "advance" routine is called after the affected node has had
334: // its key altered, but *BEFORE* any other operations are performed
335: // on the queue. This is because after the key has been altered,
336: // the queue is in an essentially corrupt state. This corruption
337: // is corrected by calling "advance". Note especially that no
338: // premption should be permitted between altering the key and calling
339: // "advance", since one cannot predict what other processes may do
340: // regarding the queue. This "without premption" condition will be
341: // satisfied in CTES if the modification to the ley is made and then
342: // the "advance" call made without allowing exit from the current CTES
343: // process, since the CTES exec is non-pre-emptive.
344: // 3. This routine would perhaps be better formulated if it actually took
345: // as an argument the new value to assign to the key, but then it would
346: // need to be a template of its own, since the leftist heap routines
347: // have no knowledge of the types of data records and keys being manipulated.
348:
349: void advance(node_tc<data_c>* p) {
350: node_tc<data_c>* q;
351:
352: if (p == NULL) { // is there any node to advance?
353: return; // no, just return
354: }
355:
356: q = p->parent; // point to the nodes parent
357: if (q==NULL) { // is the node already the head of the queue?
358: return; // yes, just return
359: }
360:
361: if (q->left == p) { // are we our parents left child?
362: q->left = NULL; // yes, emancipate ourselves
363: } else { // no, then we must be the right child!
364: q->right = NULL; // emancipate ourselves
365: }
366:
367: tree = tree->combine(tree, p); // put the tree back together again
368: }
369:
370:
371: // put a user data element into a batch to be queued later
372: // returns a pointer to the queue node
373:
374: node_tc<data_c>* batchify(data_c* dp) {
375: node_tc<data_c>* p = new node_tc<data_c>(dp); // wrap up the data in a tree node
376:
377: (void) batch_que->enque(p); // put that node on the batch fifo queue
378:
379: return p; // return a pointer to the tree node
380: }
381:
382:
383: // turn a batch into a heap
384: // merges new heap with old queue to produce new queue
385:
386: void heapify(void) {
387: node_tc<data_c>* p = NULL;
388: node_tc<data_c>* q = NULL;
389:
390: // loop to successively combine heaps until only 1 remains.
391:
392: while (TRUE) {
393:
394: p = batch_que->deque(); // get a little heap
395: if (p == NULL) { // is it empty?
396: p = q; // yes, use the other heap
397: break; // drop out of this loop
398: }
399:
400: q = batch_que->deque(); // get another little heap
401: if (q == NULL) { // is it empty?
402: break; // yes, drop out of this loop
403: }
404:
405: (void) batch_que->enque(p->combine(p, q)); // combine the 2 little heaps,
406: // and put bigger heap back on fifo
407:
408: } /* end loop combine_heaps_on_fifo */
409:
410: tree = p; // result is the new priority queue
411: }
412:
413: }; /* end class timerq_tc */
415: #endif // #ifndef __timerq_tc__H