Data Structures | Files | Defines | Functions

EGeKHeap

Data Structures

struct  EGeKHeap_t
 Structure to hold a whole heap structure, this structure is designed so that it can grow on the fly with a low cost. More...
struct  EGeKHeapCn_t
 Structure to store the information relevant to an element in the heap. More...

Files

file  eg_ekheap.c
file  eg_ekheap.ex.c
file  eg_ekheap.h

Defines

#define EG_EKHEAP_DEBUG   100
 Debug level for the heap.
#define EG_EKHEAP_ENTRY   3
 number of maximum entries in the vector values
#define EG_EKHEAP_POISON   UINT_MAX
 Poison position for heap connector not in a heap.
#define EGeKHeapAdd(__hp, __hcn)
 Add an element to the heap.
#define EGeKHeapChangeD(__hp, __width)
 set the breath of the heap, this function must be called only when the heap is empty.
#define EGeKHeapChangeVal(__hp, __hcn, __new_val)
 Change the value of an element in the heap.
#define EGeKHeapCheck(__hp)   0
 Check the integrity of the given heap.
#define EGeKHeapClear(__hp)   EGeKHeapResize(__hp,0)
 Clear a heap structure, and free any internal memory (not allocated by the user).
#define EGeKHeapCnClear(__hcn)
 Free all internal memory used by this structured not allocated by the user. This function should be called after an init call, and only once.
#define EGeKHeapCnInit(__hcn)
 Initialize a heap conector structure. This function will allocate any interal memory not allocated by the user, it should be called only once, or after a clear function call.
#define EGeKHeapCnReset(__hcn)   ((__hcn)->pos = EG_EKHEAP_POISON)
 Reset a heap conector to the same state as after an init call, this function is provided only for completness.
#define EGeKHeapDel(__hp, __hcn)
 Eliminate an element from the heap, note that the position stored in the eliminated element is reset to zero.
#define EGeKHeapEmpty(__hp)   ((__hp)->sz = 0)
 set the number of elements in hte heap to zero.
#define EGeKHeapFatherId(__d, __id)   ((__id)?(((__id)-1)/(__d)):0)
 return the index of the father of the given index.
#define EGeKHeapFirstChildId(__d, __id)   ((__d)*(__id)+1)
 Give the first child for a given position.
#define EGeKHeapGetMin(__hp)
 get the minimum conector in the heap, if the heap is empty, return NULL.
#define EGeKHeapGetMinKVal(__hp, __k, __number)
 get the k-th value of the first element in the heap.
#define EGeKHeapGetMinVal(__hp, __number)
 get the minimum value in the heap, note that since we are dealing with a vector of values sorted lexicographically, the value is the value in the first coordinate, other values can be accesses through EGeKHeapGetMinKVal function.
#define EGeKHeapInit(__hp)   (*(__hp) = (EGeKHeap_t){0,0,0,0})
 Initialize a heap as an empty heap (with no space for conectors).
#define EGeKHeapIsFull(__hp)   ({EGeKHeap_t*const __EGekhp = (__hp); __EGekhp->sz == __EGekhp->max_sz;})
 Return one if the heap is full, zero otherwise.
#define EGeKHeapIsLess(__hcn1, __hcn2)
 given two heap connectors, return one if the first is less than the second (in lexicographic order).
#define EGeKHeapResize(__hp, __new_sz)
 resize the heap cn array to the given size, if the new size is zero, it is equivalent to free the internal memory, and left the heap as an empty heap with zero space.
#define EGeKHeapSiftDown(__hp, __hcn)
 Move an element down in the heap (position 0 is the top), this kind of operation is needed whenever we increase the value in a heap element.
#define EGeKHeapSiftUp(__hp, __hcn)
 move an element in the heap up in the heap (position 0 is the top, this kind of move is neded whenever we decrease the value in a heap element).
#define EGeKHepReset(__hp)   EGeKHeapResize(__hp,0)
 Reset the given heap as an empty heap (just as returned by the init call.

Functions

void EGeKHeapCopyVal (EGlpNum_t *const dst, const EGlpNum_t *const src)
 copy two vector of values (only EG_EKHEAP_ENTRY positions) from the rource to the destination.
int ekheap_parseargs (int argc, char **argv, unsigned int *d, unsigned int *ch, EGlpNum_t *v, char **file_name)
 parse the input argumenbts for the program
void ekheap_usage (char *program)
 This program reads a list of double values from a text file and uses a heap to sort them. It also allows the user to change the value of one of the read numbers after they have been placed in the heap. The purpose of this program is to illustrate the use of the EGeKHeap structure and its associated functions.
int main (int argc, char **argv)
 main function

Test macros, enabled only if debug level is high enough.



#define EGeKHeapCHECK_CN(__hp, __hcn)
#define EGeKHeapCHECK_NF(__hp)

Detailed Description

Here we define the basic interface for d-heaps with an array of values with the lexicographic order for vectors as an embeded structure. In this implementation the heap does not grow on the fly, meaning that it may fill-up during an add call, to avoid that, the user must call re-allocate when necesary. the heap start as a heap of size zero. This implementatioon is a minimum-heap implementatiton. Note also that the internal connector array is shifted one position to the left. This is done so that the first element is in position 1, this also speed-up the computation of the parent and childrens of a given position.

Version:
0.0.1
History:
  • 2010-09-05
    • Change implementation of EGeKHeapClear to free all internal memory, including the one asked for the user during a EGeKHeapResize call.
  • 2008-07-30
    • First implementation
Note:
This implementatiton is designed as a template using as base the types of EGlpNum

Define Documentation

#define EG_EKHEAP_DEBUG   100

Debug level for the heap.

Examples:
eg_ekheap.ex.c.

Definition at line 60 of file eg_ekheap.h.

Referenced by main().

#define EG_EKHEAP_ENTRY   3

number of maximum entries in the vector values

Examples:
eg_ekheap.ex.c.

Definition at line 77 of file eg_ekheap.h.

Referenced by main().

#define EG_EKHEAP_POISON   UINT_MAX

Poison position for heap connector not in a heap.

Definition at line 93 of file eg_ekheap.h.

#define EGeKHeapAdd (   __hp,
  __hcn 
)
Value:
({\
  EGeKHeap_t*const __EGlhp = (__hp);\
  EGeKHeapCn_t*const __EGlcn = (__hcn);\
  EGeKHeapCHECK_NF(__EGlhp);\
  __EGlcn->pos = __EGlhp->sz, \
  __EGlhp->cn[__EGlhp->sz] = __EGlcn, \
  __EGlhp->sz +=1, \
  EGeKHeapSiftUp(__EGlhp,__EGlcn), 0;})

Add an element to the heap.

Parameters:
__hp heap where to add the element.
__hcn element to be added.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ekheap.ex.c.

Definition at line 285 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapChangeD (   __hp,
  __width 
)
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  EXIT((__width)<2,"Width should be at least 2 for heaps");\
  __EGehp->sz ? 1 : (__EGehp->d = (__width), 0);})

set the breath of the heap, this function must be called only when the heap is empty.

Parameters:
__hp heap to set breath.
__width new with for the heap.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ekheap.ex.c.

Definition at line 407 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapChangeVal (   __hp,
  __hcn,
  __new_val 
)
Value:
({\
  EGeKHeapCn_t*const __EGEKHcn = (__hcn);\
  (EGeKHeapIsLess(__new_val,(__EGEKHcn)->val)) ? (EGeKHeapCopyVal((__EGEKHcn)->val,__new_val),EGeKHeapSiftUp(__hp,__EGEKHcn)) : (EGeKHeapCopyVal((__EGEKHcn)->val,__new_val),EGeKHeapSiftDown(__hp,__EGEKHcn));})

Change the value of an element in the heap.

Parameters:
__hp heap where we are working.
__hcn element in the heap that we are going to change it's value.
__new_val new value for the element (note this is an array of size at least EG_EKHEAP_ENTRY.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ekheap.ex.c.

Definition at line 350 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCheck (   __hp  )     0

Check the integrity of the given heap.

Parameters:
__hp heap to check.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ekheap.ex.c.

Definition at line 397 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCHECK_CN (   __hp,
  __hcn 
)

Definition at line 70 of file eg_ekheap.h.

#define EGeKHeapCHECK_NF (   __hp  ) 

Definition at line 71 of file eg_ekheap.h.

#define EGeKHeapClear (   __hp  )     EGeKHeapResize(__hp,0)

Clear a heap structure, and free any internal memory (not allocated by the user).

Parameters:
__hp heap to clear.
Examples:
eg_ekheap.ex.c.

Definition at line 166 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnClear (   __hcn  ) 
Value:
do{\
  EGeKHeapCn_t*const __EKHcn = (__hcn);\
  int __EKHi = EG_EKHEAP_ENTRY;\
  for( ; __EKHi-- ; ){EGlpNumClearVar(__EKHcn->val[__EKHi]);}}while(0)

Free all internal memory used by this structured not allocated by the user. This function should be called after an init call, and only once.

Parameters:
__hcn conector to clear.
Examples:
eg_ekheap.ex.c.

Definition at line 120 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnInit (   __hcn  ) 
Value:
do{\
  EGeKHeapCn_t*const __EKHcn = (__hcn);\
  int __EKHi = EG_EKHEAP_ENTRY;\
  memset(__EKHcn,0,sizeof(EGeKHeapCn_t));\
  for( ; __EKHi-- ; ){EGlpNumInitVar(__EKHcn->val[__EKHi]);}\
  __EKHcn->pos = EG_EKHEAP_POISON;}while(0)

Initialize a heap conector structure. This function will allocate any interal memory not allocated by the user, it should be called only once, or after a clear function call.

Parameters:
__hcn conector to initialize.
Examples:
eg_ekheap.ex.c.

Definition at line 101 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnReset (   __hcn  )     ((__hcn)->pos = EG_EKHEAP_POISON)

Reset a heap conector to the same state as after an init call, this function is provided only for completness.

Parameters:
__hcn conector to reset

Definition at line 113 of file eg_ekheap.h.

#define EGeKHeapDel (   __hp,
  __hcn 
)
Value:
({\
  EGeKHeap_t*const __EGlhp = (__hp);\
  EGeKHeapCn_t*const __EGlhpcn = (__hcn);\
  unsigned int const __EGlcn = __EGlhpcn->pos;\
  unsigned int const __EGlhsz = __EGlhp->sz - 1;\
  __EGlhpcn->pos = EG_EKHEAP_POISON;\
  __EGlhp->sz = __EGlhsz;\
  if(__EGlhsz && __EGlhsz != __EGlcn){\
    __EGlhp->cn[__EGlcn] = __EGlhp->cn[__EGlhp->sz];\
    __EGlhp->cn[__EGlcn]->pos = __EGlcn;\
    EGeKHeapSiftDown(__EGlhp,__EGlhp->cn[__EGlcn]);}\
  __EGlhp->cn[__EGlhp->sz] = 0;})

Eliminate an element from the heap, note that the position stored in the eliminated element is reset to zero.

Parameters:
__hp heap where we are working.
__hcn element to eliminate from the heap.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ekheap.ex.c.

Definition at line 361 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapEmpty (   __hp  )     ((__hp)->sz = 0)

set the number of elements in hte heap to zero.

Parameters:
__hp heap to empty.

Definition at line 146 of file eg_ekheap.h.

#define EGeKHeapFatherId (   __d,
  __id 
)    ((__id)?(((__id)-1)/(__d)):0)

return the index of the father of the given index.

Parameters:
__d breadth of the heap.
__id position in the array to wich we want to compute it's father.

Definition at line 223 of file eg_ekheap.h.

#define EGeKHeapFirstChildId (   __d,
  __id 
)    ((__d)*(__id)+1)

Give the first child for a given position.

Parameters:
__id position that we want to get the first child.
__d breath of the heap.

Definition at line 298 of file eg_ekheap.h.

#define EGeKHeapGetMin (   __hp  ) 
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  __EGehp->sz ? __EGehp->cn[0] : 0;})

get the minimum conector in the heap, if the heap is empty, return NULL.

Parameters:
__hp eap where we are working.
Returns:
pointer to the minimum element in the heap.
Examples:
eg_ekheap.ex.c.

Definition at line 201 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapGetMinKVal (   __hp,
  __k,
  __number 
)
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  const int __EGki = (__k);\
  EXITL(EG_EKHEAP_DEBUG,(__EGki >= EG_EKHEAP_ENTRY) || (__EGki <0),\
        "K=%d out of range in EGeKHeapGetMinKVal", __EGki);\
  __EGehp->sz ? (EGlpNumCopy(__number,__EGehp->cn[0]->val[__EGki]),0):1;})

get the k-th value of the first element in the heap.

Parameters:
__hp heap where we are working.
__number where to store the result.
__k which value to get (between 0 and EG_EKHEAP_ENTRY.
Returns:
zero on success, non-zero otherwise.

Definition at line 188 of file eg_ekheap.h.

#define EGeKHeapGetMinVal (   __hp,
  __number 
)
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  __EGehp->sz ? (EGlpNumCopy(__number,__EGehp->cn[0]->val[0]),0):1;})

get the minimum value in the heap, note that since we are dealing with a vector of values sorted lexicographically, the value is the value in the first coordinate, other values can be accesses through EGeKHeapGetMinKVal function.

Parameters:
__hp heap where we are working.
__number where to store the result
Returns:
zero on success, non-zero otherwise.

Definition at line 177 of file eg_ekheap.h.

#define EGeKHeapInit (   __hp  )     (*(__hp) = (EGeKHeap_t){0,0,0,0})

Initialize a heap as an empty heap (with no space for conectors).

Parameters:
__hp heap to initialize.
Examples:
eg_ekheap.ex.c.

Definition at line 152 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapIsFull (   __hp  )     ({EGeKHeap_t*const __EGekhp = (__hp); __EGekhp->sz == __EGekhp->max_sz;})

Return one if the heap is full, zero otherwise.

Parameters:
__hp heat to check

Definition at line 140 of file eg_ekheap.h.

#define EGeKHeapIsLess (   __hcn1,
  __hcn2 
)
Value:
({\
  EGlpNum_t*const __EGEKH1 = (__hcn1);\
  EGlpNum_t*const __EGEKH2 = (__hcn2);\
  int __EGEKHj = 0, __EGEKHrval = 0;\
  for( ; __EGEKHj < EG_EKHEAP_ENTRY ; __EGEKHj++)\
  {\
    if(EGlpNumIsLess(__EGEKH1[__EGEKHj], __EGEKH2[__EGEKHj])){\
      __EGEKHrval = 1; break;}\
    else if (EGlpNumIsNeq(__EGEKH1[__EGEKHj], __EGEKH2[__EGEKHj],epsLpNum)){\
      __EGEKHrval = 0; break;}\
  }\
  __EGEKHrval;})

given two heap connectors, return one if the first is less than the second (in lexicographic order).

Parameters:
__hcn1 first vector array.
__hcn2 second vector array.
Returns:
one if __hcn1 <_LEX __hcn2

Definition at line 231 of file eg_ekheap.h.

#define EGeKHeapResize (   __hp,
  __new_sz 
)
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  const size_t __EGehp_nsz = (size_t)(__new_sz);\
  __EGehp->cn = EGrealloc((__EGehp->cn), __EGehp_nsz * sizeof(EGeKHeapCn_t*));\
  __EGehp->max_sz = (unsigned int)(__EGehp_nsz);})

resize the heap cn array to the given size, if the new size is zero, it is equivalent to free the internal memory, and left the heap as an empty heap with zero space.

Parameters:
__hp heap where we are working.
__new_sz new size for the cn array .
Examples:
eg_ekheap.ex.c.

Definition at line 212 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapSiftDown (   __hp,
  __hcn 
)

Move an element down in the heap (position 0 is the top), this kind of operation is needed whenever we increase the value in a heap element.

Parameters:
__hp heap where we are working.
__hcn element in the heap to move.
Returns:
zero on success, non-zero otherwise.

Definition at line 308 of file eg_ekheap.h.

#define EGeKHeapSiftUp (   __hp,
  __hcn 
)
Value:
({\
  EGeKHeap_t*const __EGehp = (__hp);\
  EGeKHeapCn_t*const __EGecn = (__hcn);\
  unsigned int __EGcpos = __EGecn->pos;\
  unsigned int __EGfpos = EGeKHeapFatherId(__EGehp->d,__EGcpos);\
  EGeKHeapCn_t*__EGfcn = __EGehp->cn[__EGfpos];\
  EGeKHeapCHECK_CN(__EGehp,__EGecn);\
  while(__EGcpos && \
        EGeKHeapIsLess(__EGecn->val,__EGfcn->val))\
  {\
    __EGfcn->pos = __EGcpos;\
    __EGehp->cn[__EGcpos] = __EGfcn;\
    __EGcpos = __EGfpos;\
    __EGfpos = EGeKHeapFatherId(__EGehp->d,__EGcpos);\
    __EGfcn = __EGehp->cn[__EGfpos];\
  }\
  __EGecn->pos = __EGcpos;\
  __EGehp->cn[__EGcpos] = __EGecn;\
  0;})

move an element in the heap up in the heap (position 0 is the top, this kind of move is neded whenever we decrease the value in a heap element).

Parameters:
__hp heap where we are working.
__hcn element in the heap to move.
Returns:
zero on success, non-zero otherwise.

Definition at line 259 of file eg_ekheap.h.

#define EGeKHepReset (   __hp  )     EGeKHeapResize(__hp,0)

Reset the given heap as an empty heap (just as returned by the init call.

Parameters:
__hp heap to reset

Definition at line 159 of file eg_ekheap.h.


Function Documentation

void EGeKHeapCopyVal ( EGlpNum_t *const   dst,
const EGlpNum_t *const   src 
)

copy two vector of values (only EG_EKHEAP_ENTRY positions) from the rource to the destination.

Parameters:
src source array.
dst destination array.
int ekheap_parseargs ( int  argc,
char **  argv,
unsigned int *  d,
unsigned int *  ch,
EGlpNum_t *  v,
char **  file_name 
)

parse the input argumenbts for the program

Examples:
eg_ekheap.ex.c.

Definition at line 57 of file eg_ekheap.ex.c.

References ekheap_usage().

Referenced by main().

Here is the call graph for this function:

void ekheap_usage ( char *  program  ) 

This program reads a list of double values from a text file and uses a heap to sort them. It also allows the user to change the value of one of the read numbers after they have been placed in the heap. The purpose of this program is to illustrate the use of the EGeKHeap structure and its associated functions.

The input file format is: n Value_0 Value_1 Value_2 Value_3 ... Value_n display the usage message for this program

Examples:
eg_ekheap.ex.c.

Definition at line 45 of file eg_ekheap.ex.c.

Referenced by ekheap_parseargs().

int main ( int  argc,
char **  argv 
)