00001 #include "heap.h"
00002
00003 #include "error.h"
00004 #include "defines.h"
00005
00006 #include <math.h>
00007
00025 #define HEAP_PARENT(i) ((unsigned int)floor(((i)-1)/2))
00026
00038 #define HEAP_CHILD(i) (2*(i)+1)
00039
00052 void HeapUp(unsigned int i,Theap *heap);
00053
00066 void HeapDown(unsigned int i,Theap *heap);
00067
00068
00069 void HeapUp(unsigned int i,Theap *heap)
00070 {
00071 unsigned int p,c;
00072 void *ep,*ec;
00073 boolean swap;
00074 unsigned int idC,idP;
00075
00076 swap=TRUE;
00077 c=i;
00078 ec=GetVectorElement(c,&(heap->data));
00079 while((c>0)&&(swap))
00080 {
00081 p=HEAP_PARENT(c);
00082 ep=GetVectorElement(p,&(heap->data));
00083
00084 if (heap->LessThan(ec,ep,heap->userData))
00085 {
00086 if (heap->hasIDs)
00087 {
00088 idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
00089 idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
00090 SwapVectorElements(idC,idP,&(heap->id2data));
00091 SwapVectorElements(c,p,&(heap->data2id));
00092 }
00093 SwapVectorElements(c,p,&(heap->data));
00094
00095 swap=TRUE;
00096
00097 c=p;
00098 ec=GetVectorElement(c,&(heap->data));
00099 }
00100 else
00101 swap=FALSE;
00102 }
00103 }
00104
00105 void HeapDown(unsigned int i,Theap *heap)
00106 {
00107 unsigned int p,c,c1,c2;
00108 void *ep,*ec,*ec1,*ec2;
00109 boolean swap;
00110 unsigned int idC,idP;
00111
00112 swap=TRUE;
00113 p=i;
00114 ep=GetVectorElement(p,&(heap->data));
00115 while((p<heap->last)&&(swap))
00116 {
00117 swap=FALSE;
00118 c1=HEAP_CHILD(p);
00119
00120 if (c1<heap->last)
00121 {
00122 ec1=GetVectorElement(c1,&(heap->data));
00123 c2=c1+1;
00124 if (c2<heap->last)
00125 {
00126 ec2=GetVectorElement(c2,&(heap->data));
00127 if (heap->LessThan(ec1,ec2,heap->userData))
00128 {c=c1; ec=ec1;}
00129 else
00130 {c=c2; ec=ec2;}
00131 }
00132 else
00133 {c=c1; ec=ec1;}
00134
00135 if (heap->LessThan(ec,ep,heap->userData))
00136 {
00137 if (heap->hasIDs)
00138 {
00139 idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
00140 idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
00141 SwapVectorElements(idC,idP,&(heap->id2data));
00142 SwapVectorElements(c,p,&(heap->data2id));
00143 }
00144 SwapVectorElements(c,p,&(heap->data));
00145
00146 swap=TRUE;
00147
00148
00149 p=c;
00150 ep=GetVectorElement(p,&(heap->data));
00151 }
00152 }
00153 }
00154 }
00155
00156 boolean LessThanID(void *a,void *b,void *userData)
00157 {
00158 return(*((unsigned int *)a)<*((unsigned int *)b));
00159 }
00160
00161 boolean LessThanDouble(void *a,void *b,void *userData)
00162 {
00163 return(*((double *)a)<*((double *)b));
00164 }
00165
00166 boolean LessThanPtr(void *a,void *b,void *userData)
00167 {
00168 return(*((void **)a)<*((void **)b));
00169 }
00170
00171
00172 void InitHeap(unsigned int ele_size,
00173 void (* Copy)(void *,void*),
00174 void (* Delete)(void *),
00175 boolean (* LessThan)(void *,void*,void *),
00176 void *userData,
00177 boolean hasIDs,
00178 unsigned int max_ele,Theap *heap)
00179 {
00180 InitVector(ele_size,Copy,Delete,max_ele,&(heap->data));
00181 heap->hasIDs=hasIDs;
00182 if (heap->hasIDs)
00183 {
00184 InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->data2id));
00185
00186
00187 InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->id2data));
00188 }
00189 heap->last=0;
00190 heap->LessThan=LessThan;
00191 heap->userData=userData;
00192 }
00193
00194 void CopyHeap(Theap *h_dst,Theap *h_src)
00195 {
00196 CopyVector(&(h_dst->data),&(h_src->data));
00197 h_dst->hasIDs=h_src->hasIDs;
00198 if (h_dst->hasIDs)
00199 {
00200 CopyVector(&(h_dst->data2id),&(h_src->data2id));
00201 CopyVector(&(h_dst->id2data),&(h_src->id2data));
00202 }
00203 h_dst->last=h_src->last;
00204 h_dst->LessThan=h_src->LessThan;
00205 h_dst->userData=h_src->userData;
00206 }
00207
00208 unsigned int HeapSize(Theap *heap)
00209 {
00210 return(heap->last);
00211 }
00212
00213 boolean HeapEmpty(Theap *heap)
00214 {
00215 return(heap->last==0);
00216 }
00217
00218 void AddElement2Heap(unsigned int id,void *e,Theap *heap)
00219 {
00220 SetVectorElement(heap->last,e,&(heap->data));
00221 if (heap->hasIDs)
00222 {
00223 SetVectorElement(heap->last,&id,&(heap->data2id));
00224 SetVectorElement(id,&(heap->last),&(heap->id2data));
00225 }
00226
00227 heap->last++;
00228
00229 HeapUp(heap->last-1,heap);
00230 }
00231
00232 void UpdateHeapElement(unsigned int id,Theap *heap)
00233 {
00234 if (heap->hasIDs)
00235 {
00236 unsigned int i;
00237
00238 i=GetHeapPosition(id,heap);
00239
00240
00241 HeapUp(i,heap);
00242
00243
00244
00245
00246
00247 HeapDown(i,heap);
00248 }
00249 else
00250 Error("Elements without associated identifier can not be updated");
00251 }
00252
00253 void *GetHeapElement(unsigned int i,Theap *heap)
00254 {
00255 if (i<heap->last)
00256 return(GetVectorElement(i,&(heap->data)));
00257 else
00258 return(NULL);
00259 }
00260
00261
00262 void *GetHeapElementWithID(unsigned int id,Theap *heap)
00263 {
00264 if (heap->hasIDs)
00265 return(GetHeapElement(GetHeapPosition(id,heap),heap));
00266 else
00267 return((void *)NULL);
00268 }
00269
00270 unsigned int GetHeapPosition(unsigned int id,Theap *heap)
00271 {
00272 if (heap->hasIDs)
00273 return(*(unsigned int *)GetVectorElement(id,&(heap->id2data)));
00274 else
00275 return(NO_UINT);
00276 }
00277
00278 void ExtractMinElement(void *e,Theap *heap)
00279 {
00280 if (heap->last>0)
00281 {
00282 unsigned int id;
00283
00284 if (heap->hasIDs)
00285 {
00286 id=*(unsigned int *)GetVectorElement(0,&(heap->data2id));
00287 RemoveVectorElement(id,&(heap->id2data));
00288
00289 SwapVectorElements(heap->last-1,0,&(heap->data2id));
00290 RemoveVectorElement(heap->last-1,&(heap->data2id));
00291 }
00292
00293 SwapVectorElements(heap->last-1,0,&(heap->data));
00294 ExtractVectorElement(heap->last-1,e,&(heap->data));
00295
00296 heap->last--;
00297 HeapDown(0,heap);
00298 }
00299 else
00300 Error("Extracting an element from a empty heap");
00301 }
00302
00303
00304 void ResetHeap(Theap *heap)
00305 {
00306 if (heap->hasIDs)
00307 {
00308 ResetVector(&(heap->data2id));
00309 ResetVector(&(heap->id2data));
00310 }
00311 ResetVector(&(heap->data));
00312 heap->last=0;
00313 }
00314
00315
00316 void DeleteHeap(Theap *heap)
00317 {
00318 ResetHeap(heap);
00319 if (heap->hasIDs)
00320 {
00321 DeleteVector((void *)&(heap->id2data));
00322 DeleteVector((void *)&(heap->data2id));
00323 }
00324 DeleteVector((void *)&(heap->data));
00325 }