doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / ckheap.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 class minheap;
7 class maxHeap;
8
9 #include "elements.h"
10 #include "ckheap.h"
11
12 // Heap of pointers. The field to be compared is:
13
14 minHeap::minHeap(int nsize)
15 {
16   size = nsize;
17   h = new heapRecord[size];
18   count = 0;
19 }
20
21 minHeap::~minHeap()
22 {
23   delete [] h;
24 }
25
26 int minHeap::insert(InfoRecord *x)
27 {
28   int current;
29
30   if (count < size) {
31     h[count].info = x;
32     h[count].deleted = 0;
33     current = count;
34     count++;
35   } else {
36     printf("minHeap overflow. \n") ; 
37     return -1;
38   }
39
40   int parent = (current - 1)/2;
41   while (current != 0)
42     {
43       if (h[current].info->load < h[parent].info->load)
44         {
45           swap(current, parent);
46           current = parent;
47           parent = (current-1)/2;
48         }
49       else
50         break;
51     }
52   return 0;
53 }
54
55 InfoRecord *minHeap::deleteMin()
56 {
57   if (count == 0) return 0;
58
59   InfoRecord *tmp = h[0].info;
60   int best;
61
62   h[0] = h[count-1];
63   count--;
64
65   int current = 0;
66   int c1 = 1;
67   int c2 = 2;
68   while (c1 < count)
69     {
70       if (c2 >= count)
71         best = c1;
72       else
73         {
74           if (h[c1].info->load < h[c2].info->load)
75             best = c1;
76           else
77             best = c2;
78         }
79       if (h[best].info->load < h[current].info->load)
80         {
81           swap(best, current);
82           current = best;
83           c1 = 2*current + 1;
84           c2 = c1 + 1;
85         }
86       else
87         break;
88     }
89   return tmp;
90 }
91
92 InfoRecord *minHeap::iterator(heapIterator *iter){
93   iter->next = 1;
94   if (count == 0)
95     return 0;
96   return h[0].info;
97 }
98 InfoRecord *minHeap::next(heapIterator *iter){
99   if (iter->next >= count)
100     return 0;
101   iter->next += 1;
102   return h[iter->next - 1].info;
103 }
104
105 int minHeap::least(int a, int b, int c){
106     int smaller;
107                                                                                 
108     if(h[a].info->load < h[b].info->load)
109       smaller=a;
110     else
111       smaller=b;
112                                                                                 
113     if(h[smaller].info->load < h[c].info->load)
114       return smaller;
115     else
116       return c;
117 }
118
119 void minHeap::update(InfoRecord *x) {
120     // find index
121     // TODO:  OPTIMIZE it!
122     int index;
123     for (index=0; index<numElements(); index++) 
124       if (x == h[index].info) break;
125     if (index == numElements()) {
126       CmiAbort("minHeap: update a non-existent element!\n");
127     }
128     update(index);
129 }
130
131 void minHeap::update(int index) {
132     int parent = (index-1)/2;
133                                                                                 
134     if((index != 0) && h[index].info->load < h[parent].info->load) {
135       swap(parent,index);
136       update(parent);
137     }
138                                                                                 
139     int c1 = 2*index+1;
140     int c2 = 2*index+2;
141                                                                                 
142     if(c2<numElements()){
143       int smaller = least(index,c1,c2);
144       if(smaller != index){
145         swap(smaller,index);
146         update(smaller);
147         return;
148       }
149     }
150     if(c1<numElements() && h[c1].info->load < h[index].info->load) {
151       swap(c1,index);
152       update(c1);
153       return;
154     }
155 }
156
157 //*****************
158
159
160 maxHeap::maxHeap(int nsize)
161 {
162   size = nsize;
163   h = new heapRecord[size];
164   count = 0;
165 }
166
167 maxHeap::~maxHeap()
168 {
169   delete [] h;
170 }
171
172 int maxHeap::numElements()
173 {
174   return count;
175 }
176
177 int maxHeap::insert(InfoRecord *x)
178 {
179   int current;
180
181   if (count < size) {
182     h[count].info = x;
183     h[count].deleted  = 0;
184     current = count;
185     count++;
186   } else {
187     printf("maxHeap overflow. \n"); 
188     return -1;
189   }
190
191   int parent = (current - 1)/2;
192   while (current != 0)
193     {
194       if (h[current].info->load > h[parent].info->load)
195         {
196           swap(current, parent);
197           current = parent;
198           parent = (current-1)/2;
199         }
200       else
201         break;
202     }
203   return 0;
204 }
205
206 InfoRecord *maxHeap::deleteMax()
207 {
208   if (count == 0) return 0;
209   InfoRecord *tmp = h[0].info;
210   int best;
211
212   h[0] = h[count-1];
213   count--;
214
215   int current = 0;
216   int c1 = 1;
217   int c2 = 2;
218   while (c1 < count)
219     {
220       if (c2 >= count)
221         best = c1;
222       else
223         {
224           if (h[c1].info->load > h[c2].info->load)
225             best = c1;
226           else
227             best = c2;
228         }
229       if (h[best].info->load > h[current].info->load)
230         {
231           swap(best, current);
232           current = best;
233           c1 = 2*current + 1;
234           c2 = c1 + 1;
235         }
236       else
237         break;
238     }
239   return tmp;
240 }
241
242
243 InfoRecord *maxHeap::iterator(heapIterator *iter){
244   iter->next = 1;
245   if (count == 0)
246     return 0;
247   return h[0].info;
248 }
249
250 InfoRecord *maxHeap::next(heapIterator *iter){
251   if (iter->next >= count)
252     return 0;
253   iter->next += 1;
254   return h[iter->next - 1].info;
255 }
256
257 /*@}*/