Build identifier class
[dyninst.git] / pdutil / src / PriorityQueue.C
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.C
43
44 /*
45  * $Log: PriorityQueue.C,v $
46  * Revision 1.4  1996/11/26 16:09:33  naim
47  * Fixing asserts - naim
48  *
49  * Revision 1.3  1996/08/16 21:31:46  tamches
50  * updated copyright for release 1.1
51  *
52  * Revision 1.2  1995/12/08 21:30:40  tamches
53  * added printing (for debugging purposes)
54  *
55  * Revision 1.1  1995/12/08 04:55:41  tamches
56  * first version of priority queue class
57  *
58  */
59
60 #include <assert.h>
61 #include "util/h/PriorityQueue.h"
62
63 template <class KEY, class DATA>
64 PriorityQueue<KEY, DATA>::PriorityQueue() {
65    // data is left an empty array
66 }
67
68 template <class KEY, class DATA>
69 PriorityQueue<KEY, DATA>::PriorityQueue(const PriorityQueue<KEY, DATA> &src) :
70                       data(src.data) {
71 }
72
73 template <class KEY, class DATA>
74 PriorityQueue<KEY, DATA>::~PriorityQueue() {
75 }
76
77 template <class KEY, class DATA>
78 PriorityQueue<KEY, DATA> &
79 PriorityQueue<KEY, DATA>::operator=(const PriorityQueue<KEY, DATA> &src) {
80    data = src.data;
81    return *this;
82 }
83
84 /* **************************************************************** */
85
86 template <class KEY, class DATA>
87 unsigned PriorityQueue<KEY, DATA>::size() const {
88    return data.size();
89 }
90
91 template <class KEY, class DATA>
92 bool PriorityQueue<KEY, DATA>::empty() const {
93    return data.size()==0;
94 }
95
96 template <class KEY, class DATA>
97 void PriorityQueue<KEY, DATA>::add(const KEY &k, const DATA &d) {
98    PriorityQueue<KEY, DATA>::pair p(k, d);
99    data += p;
100
101    // our situation is as follows:
102    // the heap is OK except perhaps for the last (newly added) item,
103    // which may not be in proper heap order.
104    assert(size() > 0);
105    const unsigned index = size() - 1;
106    reheapify_with_parent(index);
107 }
108
109 template <class KEY, class DATA>
110 const KEY &PriorityQueue<KEY, DATA>::peek_first_key() const {
111    bool aflag;
112    aflag=!empty();
113    assert(aflag);
114    return data[0].theKey;
115 }
116
117 template <class KEY, class DATA>
118 const DATA &PriorityQueue<KEY, DATA>::peek_first_data() const {
119    bool aflag;
120    aflag=!empty();
121    assert(aflag);
122    return data[0].theData;
123 }
124
125 template <class KEY, class DATA>
126 void PriorityQueue<KEY, DATA>::delete_first() {
127    bool aflag;
128    aflag=!empty();
129    assert(aflag);
130
131    if (size()==1) {
132       // the queue will now be empty
133       data.resize(0);
134       return;
135    }
136
137    // swap first item with last item; fry last item (used to be first);
138    // reheapify first item (used to be last)
139    assert(size() > 1);
140
141    swap_items(0, size()-1);
142
143    data.resize(size()-1);
144
145    // our situation: the top item in the heap may be out of heap
146    // order w.r.t. its children
147    reheapify_with_children(0);
148 }
149
150 /* **************************************************************************** */
151
152 template <class KEY, class DATA>
153 void PriorityQueue<KEY, DATA>::swap_items(unsigned index1, unsigned index2) {
154    PriorityQueue<KEY, DATA>::pair temp = data[index1];
155    data[index1] = data[index2];
156    data[index2] = temp;
157 }
158
159 template <class KEY, class DATA>
160 void PriorityQueue<KEY, DATA>::reheapify_with_parent(unsigned index) {
161    // item w/ given index may not be in proper heap order; make it so
162    // in time O(log(size())) by moving the item upwards as far as necessary
163
164    while (index > 0) {
165       unsigned parentIndex = (index-1) / 2;
166
167       if (data[index].theKey < data[parentIndex].theKey) {
168          // out of order; swap
169          swap_items(parentIndex, index);
170
171          index = parentIndex;
172       }
173       else
174          break;
175    }
176 }
177
178 template <class KEY, class DATA>
179 void PriorityQueue<KEY, DATA>::reheapify_with_children(unsigned index) {
180    // item w/ given index may not be in proper heap order; make it so
181    // in time O(log(size())) by moving the item downwards as far as necessary
182
183    while (true) {
184       // does at least 1 child exist?
185       unsigned child1index = 2*index + 1;
186       unsigned child2index = 2*index + 2;
187
188       if (child1index >= size())
189          break; // neither child is in range
190
191       // invariant: at least one child (child1index) is in range
192       unsigned smallerChildIndex = child1index;
193
194       if (child2index < size())
195          // the second child exists; perhaps its key is the smaller of the 2 children
196          if (data[child2index].theKey < data[child1index].theKey)
197             smallerChildIndex = child2index;
198
199       if (data[smallerChildIndex].theKey < data[index].theKey) {
200          swap_items(index, smallerChildIndex);
201
202          index = smallerChildIndex;
203       }
204       else
205          break;
206    }
207 }
208
209 template <class KEY, class DATA>
210 int PriorityQueue<KEY, DATA>::cmpfunc(const void *ptr1, const void *ptr2) {
211    const PriorityQueue<KEY, DATA>::pair &pair1 = *(const PriorityQueue<KEY, DATA>::pair *)ptr1;
212    const PriorityQueue<KEY, DATA>::pair &pair2 = *(const PriorityQueue<KEY, DATA>::pair *)ptr2;
213
214    if (pair1 < pair2)
215       return -1;
216    else if (pair1 > pair2)
217       return 1;
218    else
219       return 0;
220 }
221
222 template <class KEY, class DATA>
223 ostream &PriorityQueue<KEY, DATA>::operator<<(ostream &os) const {
224    // we need to walk the priority queue (in key order), printing each item.
225    // However, this is surprisingly hard.  We end up needing to make a copy
226    // of the array and sorting it...
227
228    vector<PriorityQueue<KEY,DATA>::pair> copy = data;
229    copy.sort(cmpfunc);
230
231    for (unsigned i=0; i < copy.size(); i++) {
232       const PriorityQueue<KEY, DATA>::pair &p = copy[i];
233
234       os << "[" << i << "]: ";
235       p.operator<<(os);
236       os << endl;
237    }
238
239    return os;
240 }
241
242 template <class KEY, class DATA>
243 ostream &operator<<(ostream &os, PriorityQueue<KEY, DATA> &q) {
244    return q.operator<<(os);
245 }