00001 00005 00006 #include "charm++.h" 00007 #include "CommLBHeap.h" 00008 00009 ObjectHeap::ObjectHeap(int sz) { 00010 size = sz; 00011 h = new hRecord[sz]; 00012 count = 0; 00013 } 00014 00015 int ObjectHeap::numElements() { 00016 return count; 00017 } 00018 00019 int ObjectHeap::insert(ObjectRecord *x) { 00020 h[count].info = x; 00021 h[count].deleted = 0; 00022 int current = count; 00023 count++; 00024 00025 if (count >= size) { 00026 CkPrintf("Heap overflow. \n"); 00027 return -1;} 00028 00029 int parent = (current - 1)/2; 00030 while (current != 0) 00031 { 00032 if (h[current].info->val > h[parent].info->val) 00033 { 00034 swap(current, parent); 00035 current = parent; 00036 parent = (current-1)/2; 00037 } 00038 else 00039 break; 00040 } 00041 return 0; 00042 } 00043 00044 ObjectRecord *ObjectHeap::deleteMax() { 00045 if (count == 0) return 0; 00046 ObjectRecord *tmp = h[0].info; 00047 int best; 00048 00049 h[0] = h[count-1]; 00050 count--; 00051 00052 int current = 0; 00053 int c1 = 1; 00054 int c2 = 2; 00055 while (c1 < count) 00056 { 00057 if (c2 >= count) 00058 best = c1; 00059 else 00060 { 00061 if (h[c1].info->val > h[c2].info->val) 00062 best = c1; 00063 else 00064 best = c2; 00065 } 00066 if (h[best].info->val > h[current].info->val) 00067 { 00068 swap(best, current); 00069 current = best; 00070 c1 = 2*current + 1; 00071 c2 = c1 + 1; 00072 } 00073 else 00074 break; 00075 } 00076 return tmp; 00077 } 00078 00079 ObjectRecord *ObjectHeap::iterator(hIterator *iter) { 00080 iter->next = 1; 00081 if (count == 0) 00082 return 0; 00083 return h[0].info; 00084 } 00085 00086 ObjectRecord *ObjectHeap::next(hIterator *iter) { 00087 if (iter->next >= count) 00088 return 0; 00089 iter->next += 1; 00090 return h[iter->next - 1].info; 00091 } 00092
1.5.5