added printing (for debugging purposes)
[dyninst.git] / common / h / PriorityQueue.h
1 // PriorityQueue.h
2
3 /*
4  * $Log: PriorityQueue.h,v $
5  * Revision 1.2  1995/12/08 21:30:26  tamches
6  * added printing (for debugging purposes)
7  *
8  * Revision 1.1  1995/12/08 04:55:29  tamches
9  * first version of priority queue class
10  *
11  */
12
13 // Note: in this priority queue class, the item with the _smallest_ key
14 //       will be the first item.
15
16 #ifndef _PRIORITY_QUEUE_H_
17 #define _PRIORITY_QUEUE_H_
18
19 #include <iostream.h>
20 #include "util/h/Vector.h"
21
22 template <class KEY, class DATA>
23 // KEY must have operator<, operator>, etc. defined
24 // DATA can be an arbitrary type
25 class PriorityQueue {
26  private:
27    struct pair {
28       KEY theKey;
29       DATA theData;
30       pair(const KEY &k, const DATA &d) : theKey(k), theData(d) {}
31       pair() {} // required by Vector.h
32       bool operator<(const pair &other) const {return theKey < other.theKey;}
33       bool operator>(const pair &other) const {return theKey > other.theKey;}
34       ostream &operator<<(ostream &os) const {
35          os << theKey << ',' << theData;
36          return os;
37       }
38    };
39
40    vector<pair> data;
41
42  private:
43    static int cmpfunc(const void *ptr1, const void *ptr2);
44       // for sorting w/in operator<<()
45
46    void swap_items(unsigned index1, unsigned index2);
47
48    void reheapify_with_parent(unsigned index);
49       // item w/ given index may not be in proper heap order; make it so
50       // in time O(log(size())) by moving the item upwards as far as necessary
51
52    void reheapify_with_children(unsigned index);
53       // item w/ given index may not be in proper heap order; make it so
54       // in time O(log(size())) by moving the item downwards as far as necessary
55
56  public:
57    PriorityQueue();
58    PriorityQueue(const PriorityQueue &src);
59   ~PriorityQueue();
60
61    PriorityQueue &operator=(const PriorityQueue &src);
62
63    unsigned size() const; // returns # items in the queue
64    bool empty() const; // returns true iff empty queue
65
66    void add(const KEY &, const DATA &);
67
68    // Peek at the first elem in the heap (bomb if heap is empty):
69    const KEY  &peek_first_key()  const;
70    const DATA &peek_first_data() const;
71    
72    void delete_first(); // bombs if empty
73
74    ostream &operator<<(ostream &os) const; // just for debugging, nach...
75
76    friend ostream &operator<<(ostream &os, PriorityQueue<KEY, DATA> &q);
77 };
78
79 #endif