Changes having to due with my new 2-pass function relocator code.
[dyninst.git] / pdutil / h / PriorityQueue.h
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // PriorityQueue.h
43
44 /*
45  * $Log: PriorityQueue.h,v $
46  * Revision 1.4  1996/08/16 21:30:12  tamches
47  * updated copyright for release 1.1
48  *
49  * Revision 1.3  1995/12/10 01:03:54  tamches
50  * added some comments
51  *
52  * Revision 1.2  1995/12/08 21:30:26  tamches
53  * added printing (for debugging purposes)
54  *
55  * Revision 1.1  1995/12/08 04:55:29  tamches
56  * first version of priority queue class
57  *
58  */
59
60 // Note: in this priority queue class, the item with the _smallest_ key
61 //       will be the first item.
62
63 // class KEY must have the following defined:
64 // -- operators < and >  (very important; determines the heap ordering)
65 // -- the usual copy constructors and assignment (single-=) operators
66 //    that any well-written class will have
67 // -- operator<< for writing to an ostream&
68 //
69 // class DATA must have the following defined:
70 // -- same as above except no < or > are needed
71
72 #ifndef _PRIORITY_QUEUE_H_
73 #define _PRIORITY_QUEUE_H_
74
75 #include <iostream.h>
76 #include "util/h/Vector.h"
77
78 template <class KEY, class DATA>
79 class PriorityQueue {
80  private:
81    struct pair {
82       KEY theKey;
83       DATA theData;
84       pair(const KEY &k, const DATA &d) : theKey(k), theData(d) {}
85       pair() {} // required by Vector.h
86       bool operator<(const pair &other) const {return theKey < other.theKey;}
87       bool operator>(const pair &other) const {return theKey > other.theKey;}
88       ostream &operator<<(ostream &os) const {
89          os << theKey << ',' << theData;
90          return os;
91       }
92    };
93
94    vector<pair> data;
95
96  private:
97    static int cmpfunc(const void *ptr1, const void *ptr2);
98       // for sorting w/in operator<<()
99
100    void swap_items(unsigned index1, unsigned index2);
101
102    void reheapify_with_parent(unsigned index);
103       // item w/ given index may not be in proper heap order; make it so
104       // in time O(log(size())) by moving the item upwards as far as necessary
105
106    void reheapify_with_children(unsigned index);
107       // item w/ given index may not be in proper heap order; make it so
108       // in time O(log(size())) by moving the item downwards as far as necessary
109
110  public:
111    PriorityQueue();
112    PriorityQueue(const PriorityQueue &src);
113   ~PriorityQueue();
114
115    PriorityQueue &operator=(const PriorityQueue &src);
116
117    unsigned size() const; // returns # items in the queue
118    bool empty() const; // returns true iff empty queue
119
120    void add(const KEY &, const DATA &);
121
122    // Peek at the first elem in the heap (bomb if heap is empty):
123    const KEY  &peek_first_key()  const;
124    const DATA &peek_first_data() const;
125    
126    void delete_first(); // bombs if empty
127
128    ostream &operator<<(ostream &os) const; // just for debugging, nach...
129
130    friend ostream &operator<<(ostream &os, PriorityQueue<KEY, DATA> &q);
131 };
132
133 #endif