EGeHeap

Detailed Description

Here we define the basic interface for d-heaps as an embeded structure. In this implementation the heap does not grow on the fly, meaning that it may fills-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:

2005-07-14
- Add EGeHeapEmpty to empty the heap (but keep its maximum size)
- Add EGeHeapIsFull to test wether a heap is full or not.
2005-07-07
- First Implementation

Note:: This implementatiton is designed as a template using as base the types of EGlpNum

Files

file eg_eheap.ex.c

file eg_eheap.h

Data Structures

struct EGeHeap_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 EGeHeapCn_t

Structure to store the information relevant to an element in the heap. More...

Defines

#define EG_EHEAP_DEBUG   1000

Debug level for the heap.

#define EG_EHEAP_POISON   UINT_MAX

Poison position for heap connector not in a heap.

#define EGeHeapAdd(hp, hcn)

Add an element to the heap.

#define EGeHeapChangeD(hp, width)

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

#define EGeHeapChangeVal(hp, hcn, new_val)

Change the value of an element in the heap.

#define EGeHeapCheck(hp)   0

Check the integrity of the given heap.

#define EGeHeapClear(hp)

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

#define EGeHeapCnClear(hcn)   EGlpNumClearVar((hcn)->val)

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 EGeHeapCnInit(hcn)   ({EGlpNumInitVar((hcn)->val);(hcn)->pos = EG_EHEAP_POISON;})

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 EGeHeapCnReset(hcn)   ((hcn)->pos = EG_EHEAP_POISON)

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

#define EGeHeapDel(hp, hcn)

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

#define EGeHeapEmpty(hp)   ((hp)->sz = 0)

set the number of elements in hte heap to zero.

#define EGeHeapFatherId(d, id)   ((id)?(((id)-1)/(d)):0)

return the index of the father of the given index.

#define EGeHeapFirstChildId(d, id)   ((d)*(id)+1)

Give the first child for a given position.

#define EGeHeapGetMin(hp)

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

#define EGeHeapGetMinVal(hp, number)

get the minimum value in the heap.

#define EGeHeapInit(hp)   (*(hp) = (EGeHeap_t){0,0,0,0})

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

#define EGeHeapIsFull(hp)   ({EGeHeap_t*const __EGehp = (hp); __EGehp->sz == __EGehp->max_sz;})

Return one if the heap is full, zero otherwise.

#define EGeHeapResize(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 EGeHeapSiftDown(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 EGeHeapSiftUp(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 EGeHepReset(hp)   EGeHeapInit(hp)

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

Typedefs

typedef EGeHeap_t EGeHeap_t

Structure to hold a whole heap structure, this structure is designed so that it can grow on the fly with a low cost.

typedef EGeHeapCn_t EGeHeapCn_t

Structure to store the information relevant to an element in the heap.

Functions

int eheap_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 eheap_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 EGeHeap structure and its associated functions. display the usage message for this program.

int main (int argc, char **argv)

main function

Define Documentation

#define EG_EHEAP_DEBUG 1000

Debug level for the heap.

Examples:
eg_eheap.ex.c.

Definition at line 62 of file eg_eheap.h.

#define EG_EHEAP_POISON UINT_MAX

Poison position for heap connector not in a heap.

Definition at line 78 of file eg_eheap.h.

#define EGeHeapAdd ( hp,
hcn )

Value:
({\ EGeHeap_t*const __EGlhp = (hp);\ EGeHeapCn_t*const __EGlcn = (hcn);\ __EGlhp->sz == __EGlhp->max_sz ? (fprintf(stderr,"Heap "#hp" is full, can't"\ " add element "#hcn), 1) : (__EGlcn->pos = __EGlhp->sz, \ __EGlhp->cn[__EGlhp->sz] = __EGlcn, __EGlhp->sz +=1, EGeHeapSiftUp(__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_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 218 of file eg_eheap.h.

#define EGeHeapChangeD ( hp,
width )

Value:
({\ EGeHeap_t*const __EGehp = (hp);\ __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_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 333 of file eg_eheap.h.

#define EGeHeapChangeVal ( hp,
hcn,
new_val )

Value:
({\ (EGlpNumIsLess(new_val,(hcn)->val)) ? (EGlpNumCopy((hcn)->val,new_val),EGeHeapSiftUp(hp,hcn)) : (EGlpNumCopy((hcn)->val,new_val),EGeHeapSiftDown(hp,hcn));})
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.

Returns:
zero on success, non-zero otherwise.

Examples:
eg_eheap.ex.c.

Definition at line 281 of file eg_eheap.h.

#define EGeHeapCheck ( hp ) 0

Check the integrity of the given heap.

Parameters:

hp heap to check.

Returns:
zero on success, non-zero otherwise.

Examples:
eg_eheap.ex.c.

Definition at line 323 of file eg_eheap.h.

#define EGeHeapClear ( hp )

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

Parameters:

hp heap to clear.

Examples:
eg_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 143 of file eg_eheap.h.

#define EGeHeapCnClear ( hcn ) EGlpNumClearVar((hcn)->val)

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_memslab.ex.c.

Definition at line 100 of file eg_eheap.h.

#define EGeHeapCnInit ( hcn ) ({EGlpNumInitVar((hcn)->val);(hcn)->pos = EG_EHEAP_POISON;})

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_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 86 of file eg_eheap.h.

#define EGeHeapCnReset ( hcn ) ((hcn)->pos = EG_EHEAP_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 93 of file eg_eheap.h.

#define EGeHeapDel ( hp,
hcn )

Value:
({\ EGeHeap_t*const __EGlhp = (hp);\ unsigned int const __EGlcn = (hcn)->pos;\ (hcn)->pos = EG_EHEAP_POISON;\ (__EGlhp->sz) -= 1;\ __EGlhp->cn[__EGlcn] = __EGlhp->cn[__EGlhp->sz];\ __EGlhp->cn[__EGlcn]->pos = __EGlcn;\ __EGlhp->cn[__EGlhp->sz] = 0;\ __EGlhp->sz ? EGeHeapSiftDown(__EGlhp,__EGlhp->cn[__EGlcn]):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_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 291 of file eg_eheap.h.

#define EGeHeapEmpty ( hp ) ((hp)->sz = 0)

set the number of elements in hte heap to zero.

Parameters:

hp heap to empty.

Definition at line 123 of file eg_eheap.h.

#define EGeHeapFatherId ( 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 183 of file eg_eheap.h.

#define EGeHeapFirstChildId ( 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 229 of file eg_eheap.h.

#define EGeHeapGetMin ( hp )

Value:
({\ EGeHeap_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_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 161 of file eg_eheap.h.

#define EGeHeapGetMinVal ( hp,
number )

Value:
({\ EGeHeap_t*const __EGehp = (hp);\ __EGehp->sz ? (EGlpNumCopy(number,__EGehp->cn[0]->val),0):1;})
get the minimum value in the heap.

Parameters:

hp heap where we are working.

number where to store the result

Returns:
zero on success, non-zero otherwise.

Definition at line 151 of file eg_eheap.h.

#define EGeHeapInit ( hp ) (*(hp) = (EGeHeap_t){0,0,0,0})

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

Parameters:

hp heap to initialize.

Examples:
eg_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 129 of file eg_eheap.h.

#define EGeHeapIsFull ( hp ) ({EGeHeap_t*const __EGehp = (hp); __EGehp->sz == __EGehp->max_sz;})

Return one if the heap is full, zero otherwise.

Parameters:

hp heat to check

Examples:
eg_memslab.ex.c.

Definition at line 117 of file eg_eheap.h.

#define EGeHeapResize ( hp,
new_sz )

Value:
({\ EGeHeap_t*const __EGehp = (hp);\ const unsigned int __EGehp_nsz = (new_sz);\ __EGehp->cn = EGrealloc((__EGehp->cn), __EGehp_nsz * sizeof(EGeHeapCn_t*));\ __EGehp->max_sz = __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 hew size for the cn array .

Examples:
eg_eheap.ex.c, and eg_memslab.ex.c.

Definition at line 172 of file eg_eheap.h.

#define EGeHeapSiftDown ( 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 239 of file eg_eheap.h.

#define EGeHeapSiftUp ( hp,
hcn )

Value:
({\ EGeHeap_t*const __EGehp = (hp);\ EGeHeapCn_t*const __EGecn = (hcn);\ unsigned int __EGcpos = __EGecn->pos;\ unsigned int __EGfpos = EGeHeapFatherId(__EGehp->d,__EGcpos);\ EGeHeapCn_t*__EGfcn = __EGehp->cn[__EGfpos];\ WARNINGL(EG_EHEAP_DEBUG,__EGehp->sz<=__EGcpos,"Heap Conector out of range");\ while(__EGcpos && \ EGlpNumIsLess(__EGecn->val,__EGfcn->val))\ {\ __EGfcn->pos = __EGcpos;\ __EGehp->cn[__EGcpos] = __EGfcn;\ __EGcpos = __EGfpos;\ __EGfpos = EGeHeapFatherId(__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 192 of file eg_eheap.h.

#define EGeHepReset ( hp ) EGeHeapInit(hp)

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

Parameters:

hp heap to reset

Definition at line 136 of file eg_eheap.h.

Typedef Documentation

typedef struct EGeHeap_t EGeHeap_t

Structure to hold a whole heap structure, this structure is designed so that it can grow on the fly with a low cost.

typedef struct EGeHeapCn_t EGeHeapCn_t

Structure to store the information relevant to an element in the heap.

Function Documentation

int eheap_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_eheap.ex.c.

Definition at line 63 of file eg_eheap.ex.c.
Here is the call graph for this function:

void eheap_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 EGeHeap structure and its associated functions. display the usage message for this program.

Examples:
eg_eheap.ex.c.

Definition at line 50 of file eg_eheap.ex.c.

int main ( int argc,

char ** argv

)

main function

Definition at line 111 of file eg_eheap.ex.c.
Here is the call graph for this function:

Generated on Mon Jan 30 08:55:31 2006 for EGlib by

1.4.5


Files
file	eg_eheap.ex.c
file	eg_eheap.h
Data Structures
struct	EGeHeap_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	EGeHeapCn_t
	Structure to store the information relevant to an element in the heap. More...
Defines
#define	EG_EHEAP_DEBUG 1000
	Debug level for the heap.
#define	EG_EHEAP_POISON UINT_MAX
	Poison position for heap connector not in a heap.
#define	EGeHeapAdd(hp, hcn)
	Add an element to the heap.
#define	EGeHeapChangeD(hp, width)
	set the breath of the heap, this function must be called only when the heap is empty.
#define	EGeHeapChangeVal(hp, hcn, new_val)
	Change the value of an element in the heap.
#define	EGeHeapCheck(hp) 0
	Check the integrity of the given heap.
#define	EGeHeapClear(hp)
	Clear a heap structure, and free any internal memory (not allocated by the user).
#define	EGeHeapCnClear(hcn) EGlpNumClearVar((hcn)->val)
	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	EGeHeapCnInit(hcn) ({EGlpNumInitVar((hcn)->val);(hcn)->pos = EG_EHEAP_POISON;})
	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	EGeHeapCnReset(hcn) ((hcn)->pos = EG_EHEAP_POISON)
	Reset a heap conector to the same state as after an init call, this function is provided only for completness.
#define	EGeHeapDel(hp, hcn)
	Eliminate an element from the heap, note that the position stored in the eliminated element is reset to zero.
#define	EGeHeapEmpty(hp) ((hp)->sz = 0)
	set the number of elements in hte heap to zero.
#define	EGeHeapFatherId(d, id) ((id)?(((id)-1)/(d)):0)
	return the index of the father of the given index.
#define	EGeHeapFirstChildId(d, id) ((d)*(id)+1)
	Give the first child for a given position.
#define	EGeHeapGetMin(hp)
	get the minimum conector in the heap, if the heap is empty, return NULL.
#define	EGeHeapGetMinVal(hp, number)
	get the minimum value in the heap.
#define	EGeHeapInit(hp) (*(hp) = (EGeHeap_t){0,0,0,0})
	Initialize a heap as an empty heap (with no space for conectors).
#define	EGeHeapIsFull(hp) ({EGeHeap_t*const __EGehp = (hp); __EGehp->sz == __EGehp->max_sz;})
	Return one if the heap is full, zero otherwise.
#define	EGeHeapResize(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	EGeHeapSiftDown(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	EGeHeapSiftUp(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	EGeHepReset(hp) EGeHeapInit(hp)
	Reset the given heap as an empty heap (just as returned by the init call.
Typedefs
typedef EGeHeap_t	EGeHeap_t
	Structure to hold a whole heap structure, this structure is designed so that it can grow on the fly with a low cost.
typedef EGeHeapCn_t	EGeHeapCn_t
	Structure to store the information relevant to an element in the heap.
Functions
int	eheap_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	eheap_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 EGeHeap structure and its associated functions. display the usage message for this program.
int	main (int argc, char **argv)
	main function