heap.c
Go to the documentation of this file.
1 #include "heap.h"
2 
3 #include "error.h"
4 #include "defines.h"
5 
6 #include <math.h>
7 
25 #define HEAP_PARENT(i) ((unsigned int)floor(((i)-1)/2))
26 
38 #define HEAP_CHILD(i) (2*(i)+1)
39 
47 void CheckHeap(Theap *heap);
48 
63 boolean HeapUp(unsigned int i,Theap *heap);
64 
79 boolean HeapDown(unsigned int i,Theap *heap);
80 
81 /********************************************************/
82 void CheckHeap(Theap *heap)
83 {
84  unsigned int i,m;
85  unsigned int *p,*s;
86 
87  if (heap->last>0)
88  {
89  m=VectorSize(&(heap->id2data));
90  for(i=0;i<m;i++)
91  {
92  p=(unsigned int *)GetVectorElement(i,&(heap->id2data));
93  if (p!=NULL)
94  {
95  if (*p>=heap->last)
96  Error("Error in heap (I)");
97  s=(unsigned int *)GetVectorElement(*p,&(heap->data2id));
98  if (s==NULL)
99  Error("Error in heap (II)");
100  if (i!=*s)
101  Error("Error in heap (III)");
102  }
103  }
104 
105  for(i=0;i<heap->last;i++)
106  {
107  p=(unsigned int *)GetVectorElement(i,&(heap->data2id));
108  if (p==NULL)
109  Error("Error in heap (IV)");
110  s=(unsigned int *)GetVectorElement(*p,&(heap->id2data));
111  if (s==NULL)
112  Error("Error in heap (V)");
113  if (i!=*s)
114  Error("Error in heap (VI)");
115  }
116  }
117 }
118 
119 boolean HeapUp(unsigned int i,Theap *heap)
120 {
121  unsigned int p,c;
122  void *ep,*ec;
123  boolean swap;
124  unsigned int idC,idP;
125  boolean moved;
126 
127  swap=TRUE;
128  moved=FALSE;
129  c=i;
130  ec=GetVectorElement(c,&(heap->data));
131  while((c>0)&&(swap))
132  {
133  p=HEAP_PARENT(c);
134  ep=GetVectorElement(p,&(heap->data));
135 
136  if (heap->LessThan(ec,ep,heap->userData))
137  {
138  if (heap->hasIDs)
139  {
140  idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
141  idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
142  SwapVectorElements(idC,idP,&(heap->id2data));
143  SwapVectorElements(c,p,&(heap->data2id));
144  }
145  SwapVectorElements(c,p,&(heap->data));
146 
147  moved=TRUE;
148  swap=TRUE;
149  /*Prepare to continue moving up*/
150  c=p;
151  ec=GetVectorElement(c,&(heap->data));
152  }
153  else
154  swap=FALSE;
155  }
156  return(moved);
157 }
158 
159 boolean HeapDown(unsigned int i,Theap *heap)
160 {
161  unsigned int p,c,c1,c2;
162  void *ep,*ec,*ec1,*ec2;
163  boolean swap;
164  unsigned int idC,idP;
165  boolean moved;
166 
167  moved=FALSE;
168  swap=TRUE;
169  p=i;
170  ep=GetVectorElement(p,&(heap->data));
171  while((p<heap->last)&&(swap))
172  {
173  swap=FALSE;
174  c1=HEAP_CHILD(p);
175  /* determine the child with lower priority */
176  if (c1<heap->last)
177  {
178  ec1=GetVectorElement(c1,&(heap->data));
179  c2=c1+1;
180  if (c2<heap->last)
181  {
182  ec2=GetVectorElement(c2,&(heap->data));
183  if (heap->LessThan(ec1,ec2,heap->userData))
184  {c=c1; ec=ec1;}
185  else
186  {c=c2; ec=ec2;}
187  }
188  else
189  {c=c1; ec=ec1;}
190 
191  if (heap->LessThan(ec,ep,heap->userData))
192  {
193  if (heap->hasIDs)
194  {
195  idC=*(unsigned int *)GetVectorElement(c,&(heap->data2id));
196  idP=*(unsigned int *)GetVectorElement(p,&(heap->data2id));
197  SwapVectorElements(idC,idP,&(heap->id2data));
198  SwapVectorElements(c,p,&(heap->data2id));
199  }
200  SwapVectorElements(c,p,&(heap->data));
201 
202  moved=TRUE;
203  swap=TRUE;
204 
205  /*Prepare to continue moving down*/
206  p=c;
207  ep=GetVectorElement(p,&(heap->data));
208  }
209  }
210  }
211  return(moved);
212 }
213 
214 boolean LessThanID(void *a,void *b,void *userData)
215 {
216  return(*((unsigned int *)a)<*((unsigned int *)b));
217 }
218 
219 boolean LessThanDouble(void *a,void *b,void *userData)
220 {
221  return(*((double *)a)<*((double *)b));
222 }
223 
224 boolean LessThanDoublePair(void *a,void *b,void *userData)
225 {
226  return((((TDoublePair *)a)->f<((TDoublePair *)b)->f)||
227  ((((TDoublePair *)a)->f==((TDoublePair *)b)->f)&&
228  (((TDoublePair *)a)->s<((TDoublePair *)b)->s)));
229 }
230 
231 boolean LessThanPtr(void *a,void *b,void *userData)
232 {
233  return(*((void **)a)<*((void **)b));
234 }
235 
236 
237 void InitHeap(unsigned int ele_size,
238  void (* Copy)(void *,void*),
239  void (* Delete)(void *),
240  boolean (* LessThan)(void *,void*,void *),
241  void *userData,
242  boolean hasIDs,
243  unsigned int max_ele,Theap *heap)
244 {
245  InitVector(ele_size,Copy,Delete,max_ele,&(heap->data));
246  heap->hasIDs=hasIDs;
247  if (heap->hasIDs)
248  {
249  InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->data2id));
250  /*mapping id2data can be larger that max_element but it will be extended
251  as necessary*/
252  InitVector(sizeof(unsigned int),CopyID,DeleteID,max_ele,&(heap->id2data));
253  }
254  heap->last=0;
255  heap->LessThan=LessThan;
256  heap->userData=userData;
257 }
258 
259 void CopyHeap(Theap *h_dst,Theap *h_src)
260 {
261  CopyVector(&(h_dst->data),&(h_src->data));
262  h_dst->hasIDs=h_src->hasIDs;
263  if (h_dst->hasIDs)
264  {
265  CopyVector(&(h_dst->data2id),&(h_src->data2id));
266  CopyVector(&(h_dst->id2data),&(h_src->id2data));
267  }
268  h_dst->last=h_src->last;
269  h_dst->LessThan=h_src->LessThan;
270  h_dst->userData=h_src->userData;
271 }
272 
273 void ResetHeap(Theap *heap)
274 {
275  if (heap->hasIDs)
276  {
277  ResetVector(&(heap->data2id));
278  ResetVector(&(heap->id2data));
279  }
280  ResetVector(&(heap->data));
281  heap->last=0;
282 }
283 
284 unsigned int HeapSize(Theap *heap)
285 {
286  return(heap->last);
287 }
288 
289 boolean HeapEmpty(Theap *heap)
290 {
291  return(heap->last==0);
292 }
293 
294 void AddElement2Heap(unsigned int id,void *e,Theap *heap)
295 {
296  SetVectorElement(heap->last,e,&(heap->data));
297  if (heap->hasIDs)
298  {
299  SetVectorElement(heap->last,&id,&(heap->data2id));
300  SetVectorElement(id,&(heap->last),&(heap->id2data));
301  }
302 
303  heap->last++;
304 
305  HeapUp(heap->last-1,heap);
306 }
307 
308 void UpdateHeapElement(unsigned int id,void *e,Theap *heap)
309 {
310  if (heap->hasIDs)
311  {
312  unsigned int i,*p;
313 
314  p=(unsigned int *)GetVectorElement(id,&(heap->id2data));
315  if (p==NULL)
316  AddElement2Heap(id,e,heap);
317  else
318  {
319  i=*p;
320  if (i>=heap->last) Error("Incorrect reference to a heap position");
321  SetVectorElement(i,e,&(heap->data));
322 
323  if (!HeapUp(i,heap))
324  HeapDown(i,heap);
325  }
326  }
327  else
328  Error("Elements without associated identifier can not be updated");
329 }
330 
331 void *GetHeapElement(unsigned int i,Theap *heap)
332 {
333  if (i<heap->last)
334  return(GetVectorElement(i,&(heap->data)));
335  else
336  return(NULL);
337 }
338 
339 
340 void *GetHeapElementWithID(unsigned int id,Theap *heap)
341 {
342  if (heap->hasIDs)
343  return(GetHeapElement(GetHeapPosition(id,heap),heap));
344  else
345  return((void *)NULL);
346 }
347 
348 unsigned int GetHeapPosition(unsigned int id,Theap *heap)
349 {
350  if (heap->hasIDs)
351  return(*(unsigned int *)GetVectorElement(id,&(heap->id2data)));
352  else
353  return(NO_UINT);
354 }
355 
356 unsigned int ExtractMinElement(void *e,Theap *heap)
357 {
358  unsigned int idFirst,idLast;
359 
360  idFirst=NO_UINT;
361 
362  if (heap->last>0)
363  {
364  if (heap->hasIDs)
365  {
366  idFirst=*(unsigned int *)GetVectorElement(0,&(heap->data2id));
367  idLast=*(unsigned int *)GetVectorElement(heap->last-1,&(heap->data2id));
368 
369  SwapVectorElements(idLast,idFirst,&(heap->id2data));
370  RemoveVectorElement(idFirst,&(heap->id2data));
371 
372  SwapVectorElements(heap->last-1,0,&(heap->data2id));
373  RemoveVectorElement(heap->last-1,&(heap->data2id));
374  }
375 
376  SwapVectorElements(heap->last-1,0,&(heap->data));
377  ExtractVectorElement(heap->last-1,e,&(heap->data));
378 
379  heap->last--;
380  HeapDown(0,heap);
381  }
382  else
383  Error("Extracting an element from a empty heap");
384 
385  return(idFirst);
386 }
387 
388 void DeleteHeap(Theap *heap)
389 {
390  ResetHeap(heap);
391  if (heap->hasIDs)
392  {
393  DeleteVector((void *)&(heap->id2data));
394  DeleteVector((void *)&(heap->data2id));
395  }
396  DeleteVector((void *)&(heap->data));
397 }
boolean LessThanID(void *a, void *b, void *userData)
Comparison operator for identifiers.
Definition: heap.c:214
void DeleteVector(void *vector)
Destructor.
Definition: vector.c:388
unsigned int VectorSize(Tvector *vector)
Gets the number of elements in a vector.
Definition: vector.c:169
void ResetHeap(Theap *heap)
Resets a heap.
Definition: heap.c:273
#define FALSE
FALSE.
Definition: boolean.h:30
void DeleteID(void *a)
Destructor for identifiers.
Definition: vector.c:29
A pair of dubles.
Definition: vector.h:114
boolean(* LessThan)(void *, void *, void *)
Definition: heap.h:114
void * GetVectorElement(unsigned int i, Tvector *vector)
Returns a pointer to a vector element.
Definition: vector.c:269
unsigned int GetHeapPosition(unsigned int id, Theap *heap)
Returns the current position in the heap of an element given its identifier.
Definition: heap.c:348
boolean LessThanPtr(void *a, void *b, void *userData)
Comparison operator for pointers.
Definition: heap.c:231
void CopyVector(Tvector *v_dst, Tvector *v_src)
Copy constructor.
Definition: vector.c:134
void RemoveVectorElement(unsigned int i, Tvector *vector)
Removes an element from the vector.
Definition: vector.c:285
boolean LessThanDouble(void *a, void *b, void *userData)
Comparison operator for doubles.
Definition: heap.c:219
#define TRUE
TRUE.
Definition: boolean.h:21
void Error(const char *s)
General error function.
Definition: error.c:80
void ExtractVectorElement(unsigned int i, void *e, Tvector *vector)
Extracts an element from a vector.
Definition: vector.c:341
boolean HeapDown(unsigned int i, Theap *heap)
Moves an element down in the heap.
Definition: heap.c:159
void AddElement2Heap(unsigned int id, void *e, Theap *heap)
Adds an element to the heap.
Definition: heap.c:294
Error and warning functions.
Definition of a binary heap used to implement priority queues.
void CopyHeap(Theap *h_dst, Theap *h_src)
Copy constructor.
Definition: heap.c:259
boolean LessThanDoublePair(void *a, void *b, void *userData)
Comparison operator for paris of doubles.
Definition: heap.c:224
void CheckHeap(Theap *heap)
Verifies the integrity of the heap.
Definition: heap.c:82
void ResetVector(Tvector *vector)
Resets a vector.
Definition: vector.c:116
void * GetHeapElement(unsigned int i, Theap *heap)
Returns a pointer to a heap element.
Definition: heap.c:331
unsigned int HeapSize(Theap *heap)
Gets the number of elements in a heap.
Definition: heap.c:284
#define HEAP_PARENT(i)
Returns the identifier of a parent node in a binary heap.
Definition: heap.c:25
Definitions of constants and macros used in several parts of the cuik library.
void InitVector(unsigned int ele_size, void(*Copy)(void *, void *), void(*Delete)(void *), unsigned int max_ele, Tvector *vector)
Constructor.
Definition: vector.c:100
void SetVectorElement(unsigned int i, void *e, Tvector *vector)
Adds an element to the vector in a given position.
Definition: vector.c:234
boolean HeapEmpty(Theap *heap)
Checks if a heap is empty.
Definition: heap.c:289
Tvector data2id
Definition: heap.h:111
void DeleteHeap(Theap *heap)
Destructor.
Definition: heap.c:388
Tvector data
Definition: heap.h:107
boolean hasIDs
Definition: heap.h:108
unsigned int last
Definition: heap.h:113
void InitHeap(unsigned int ele_size, void(*Copy)(void *, void *), void(*Delete)(void *), boolean(*LessThan)(void *, void *, void *), void *userData, boolean hasIDs, unsigned int max_ele, Theap *heap)
Constructor.
Definition: heap.c:237
boolean HeapUp(unsigned int i, Theap *heap)
Moves an element up in the heap.
Definition: heap.c:119
#define NO_UINT
Used to denote an identifier that has not been initialized.
Definition: defines.h:435
#define HEAP_CHILD(i)
Returns the identifier of a child node in a binary heap.
Definition: heap.c:38
Tvector id2data
Definition: heap.h:109
unsigned int ExtractMinElement(void *e, Theap *heap)
Extracts and removes the minimal element of a heap.
Definition: heap.c:356
A generic binary heap.
Definition: heap.h:105
void * GetHeapElementWithID(unsigned int id, Theap *heap)
Returns a pointer to a heap element given the element identifier.
Definition: heap.c:340
void * userData
Definition: heap.h:116
void SwapVectorElements(unsigned int i, unsigned int j, Tvector *vector)
Swaps two elements in a vector.
Definition: vector.c:298
void UpdateHeapElement(unsigned int id, void *e, Theap *heap)
Updates the position of an element in the heap.
Definition: heap.c:308
void CopyID(void *a, void *b)
Copy constructor for identifiers.
Definition: vector.c:24