Detailed Description

Implementation of a generic binary heap to be used to implement priority queues. The implementation works on generic objects as far as they have

A copy constructor.
A destructor.
A comparison operator identifying the lower of two given objects.

The implementation heavely relies in the use of the vector structure and, thus, default opeators (constructor, destructor, comparison) for doubles, integers, and pointers are already provided.

The only distintive feature of this implementation is that element can have an identifier assigned by the caller attending to the semantic of the objects in the heap. This is useful to efficiently retrive the position in the heap of an element given its identifier. This is required in several applications (for instance by efficient incremental A* algorithms).

See Also: Theap, heap.c.

Definition in file heap.h.

Data Structures
struct	Theap
	A generic binary heap. More...

Functions
boolean	LessThanID (void a, void b, void *userData)
	Comparison operator for identifiers. More...

boolean	LessThanDouble (void a, void b, void *userData)
	Comparison operator for doubles. More...

boolean	LessThanDoublePair (void a, void b, void *userData)
	Comparison operator for paris of doubles. More...

boolean	LessThanPtr (void a, void b, void *userData)
	Comparison operator for pointers. More...

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. More...

void	CopyHeap (Theap h_dst, Theap h_src)
	Copy constructor. More...

void	ResetHeap (Theap *heap)
	Resets a heap. More...

unsigned int	HeapSize (Theap *heap)
	Gets the number of elements in a heap. More...

boolean	HeapEmpty (Theap *heap)
	Checks if a heap is empty. More...

void	AddElement2Heap (unsigned int id, void e, Theap heap)
	Adds an element to the heap. More...

void	UpdateHeapElement (unsigned int id, void e, Theap heap)
	Updates the position of an element in the heap. More...

void *	GetHeapElement (unsigned int i, Theap *heap)
	Returns a pointer to a heap element. More...

void *	GetHeapElementWithID (unsigned int id, Theap *heap)
	Returns a pointer to a heap element given the element identifier. More...

unsigned int	GetHeapPosition (unsigned int id, Theap *heap)
	Returns the current position in the heap of an element given its identifier. More...

unsigned int	ExtractMinElement (void e, Theap heap)
	Extracts and removes the minimal element of a heap. More...

void	DeleteHeap (Theap *heap)
	Destructor. More...

Function Documentation

boolean LessThanID	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for identifiers identifying the lower of the two given identifiers.

Parameters

a	Pointer to the first identifier to compare.
b	Pointer to the second identifier to compare.
userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns: TRUE if the first input is smaller than the second.

Definition at line 214 of file heap.c.

boolean LessThanDouble	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for doubles identifying the lower of the two given doubles.

Parameters

a	Pointer to the first double to compare.
b	Pointer to the second double to compare.
userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns: TRUE if the first input is smaller than the second.

Definition at line 219 of file heap.c.

boolean LessThanDoublePair	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for doubles identifying the lower of the two given pairs of doubles. The first double has priority and the second one is only considered if the first one are the same.

Parameters

a	Pointer to the first pair of doubles to compare.
b	Pointer to the second pairs of doubles to compare.
userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns: TRUE if the first input is smaller than the second.

Definition at line 224 of file heap.c.

Referenced by AtlasBiRRTstar(), AtlasRRTstar(), BiRRTstar(), and RRTstar().

boolean LessThanPtr	(	void *	a,
		void *	b,
		void *	userData
	)

Comparison operator for pointers identifying the lower of the two given pointers.

Parameters

a	Pointer to the first pointer to compare.
b	Pointer to the second pointer to compare.
userData	Pointer to the user data given when defining the heap. It is not used in this case but given for compatibility with more complex LessThan operators.

Returns: TRUE if the first input is smaller than the second.

Definition at line 231 of file heap.c.

void InitHeap	(	unsigned int	ele_size,
		void()(void , void *)	Copy,
		void()(void )	Delete,
		boolean()(void , void , void )	LessThan,
		void *	userData,
		boolean	hasIDs,
		unsigned int	max_ele,
		Theap *	heap
	)

Initializes an empty heap Examples of use:

InitHeap(sizeof(unsigned int),CopyID,DeleteID,LessThanID,NULL,MaxNumEle,&heap);
InitHeap(sizeof(double),CopyDouble,DeleteDouble,LessThanDouble,NULL,MaxNumEle,&heap);
InitHeap(sizeof(void *),CopyPtr,DeletePtr,LessThanPtr,NULL,MaxNumEle,&heap);

Parameters

ele_size	Number of bytes taken by each element in the list.
Copy	Copy constructor for the elements in the list.
Delete	Destructor for the elements in the list.
LessThan	The operator to use when sorting the elements in the heap. Smaller elements are in the top of the heap and, thus, are returned first using ExtractMinElement.
userData	The pointer to the data to pass to the LessThan operator as a third parameter.
hasIDs	TRUE if elements in the heap have will have an identifier.
max_ele	Initial number of elements in the heap. This can be extended on-line but the execution it is more efficient if we have a good guess for this value.
heap	The heap to initialize.

Definition at line 237 of file heap.c.

References CopyID(), Theap::data, Theap::data2id, DeleteID(), Theap::hasIDs, Theap::id2data, InitVector(), Theap::last, Theap::LessThan, and Theap::userData.

Referenced by AtlasAStar(), AtlasBiRRTstar(), AtlasGBF(), AtlasRRTstar(), BiRRTstar(), BuildAtlasFromPoint(), InitHeapOfBoxes(), and RRTstar().

void CopyHeap	(	Theap *	h_dst,
		Theap *	h_src
	)

Copies h_src into h_dst. This is a constructor and, thus, h_dst is initialized inside this function.

Parameters

h_dst	The heap to define.
h_src	The heap from where to get the data.

Definition at line 259 of file heap.c.

References CopyVector(), Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, Theap::LessThan, and Theap::userData.

void ResetHeap ( Theap * heap )

Removes all the elements from a heap.

Parameters

heap	The heap to reset.

Definition at line 273 of file heap.c.

References Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, and ResetVector().

Referenced by DeleteHeap().

unsigned int HeapSize ( Theap * heap )

Returns the number of elements in a heap.

Parameters

heap	The heap to query.

Returns: The number of elements in the heap.

Definition at line 284 of file heap.c.

References Theap::last.

Referenced by AtlasAStar(), Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), MPI_SolveCuikSystem(), and PrintHeapOfBoxes().

boolean HeapEmpty ( Theap * heap )

Checks if a heap is empty

Parameters

heap	The heap to query.

Returns: TRUE if there are no elements in the heap.

Definition at line 289 of file heap.c.

References Theap::last.

Referenced by AtlasAStar(), AtlasGBF(), BuildAtlasFromPoint(), MPI_SolveCuikSystem(), RecursiveReWireRRTstar(), and SolveCuikSystem().

void AddElement2Heap	(	unsigned int	id,
		void *	e,
		Theap *	heap
	)

Adds an element to the heap.

Parameters

id	The identifier of the element.
e	The element add to the heap.
heap	The heap to update.

Definition at line 294 of file heap.c.

References Theap::data, Theap::data2id, Theap::hasIDs, HeapUp(), Theap::id2data, Theap::last, and SetVectorElement().

Referenced by AddBox2HeapOfBoxes(), AddList2Heap(), AtlasAStar(), AtlasGBF(), BuildAtlasFromPoint(), UpdateHeapElement(), WireAtlasRRTstar(), and WireRRTstar().

void UpdateHeapElement	(	unsigned int	id,
		void *	e,
		Theap *	heap
	)

Updates the position of an element in the heap given its identifier.

This function only works for heaps whose elements have an associated identifier (the identifier is required to locate the element to update in the heap). If the elements have no asssocated identifer this function triggers an error.

If the element is not included in the heap, it is added.

Parameters

id	The identifier the element whose priority need to be reconsidered.
e	The new value for the heap element with the given identifier.
heap	The heap to update.

Definition at line 308 of file heap.c.

References AddElement2Heap(), Theap::data, Error(), GetVectorElement(), Theap::hasIDs, HeapDown(), HeapUp(), Theap::id2data, Theap::last, and SetVectorElement().

Referenced by RecursiveReWireRRTstar().

void* GetHeapElement	(	unsigned int	i,
		Theap *	heap
	)

Returns a pointer to a given heap element.

Parameters

i	The heap position to retrive.
heap	The heap to query.

Returns: A pointer to the requested heap element or NULL if the heap position i is free.

Definition at line 331 of file heap.c.

References Theap::data, and GetVectorElement().

Referenced by AtlasAStar(), GetHeapElementWithID(), Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), PrintHeapOfBoxes(), and RecursiveReWireRRTstar().

void* GetHeapElementWithID	(	unsigned int	id,
		Theap *	heap
	)

Returns a pointer to a heap element given the element identifier.

Parameters

id	The identifier of the object to retrive.
heap	The heap to query.

Definition at line 340 of file heap.c.

References GetHeapElement(), GetHeapPosition(), and Theap::hasIDs.

unsigned int GetHeapPosition	(	unsigned int	id,
		Theap *	heap
	)

Returns the current position in the heap of an element given its identifier.

Parameters

id	The identifier of the object whose position is to be retrived.
heap	The heap to query.

Definition at line 348 of file heap.c.

References GetVectorElement(), Theap::hasIDs, Theap::id2data, and NO_UINT.

Referenced by GetHeapElementWithID().

unsigned int ExtractMinElement	(	void *	e,
		Theap *	heap
	)

Returns a pointer to a the minimal (i.e., the first) element of a heap and removes the element from the heap.

This function triggers an error if the heap is empty.

Parameters

e	Pointer to a space where to store the element to be extracted from the heap.
heap	The heap to query and update.

Returns: The identifier of the extracted element, if any. NO_UINT otherwise.

Definition at line 356 of file heap.c.

References Theap::data, Theap::data2id, Error(), ExtractVectorElement(), GetVectorElement(), Theap::hasIDs, HeapDown(), Theap::id2data, Theap::last, NO_UINT, RemoveVectorElement(), and SwapVectorElements().

Referenced by AtlasAStar(), AtlasGBF(), BuildAtlasFromPoint(), MPI_SolveCuikSystem(), RecursiveReWireRRTstar(), and SolveCuikSystem().

void DeleteHeap ( Theap * heap )

Deletes the information stored in the heap and frees the allocated memory space.

Parameters

heap	The heap to be deleted.

Definition at line 388 of file heap.c.

References Theap::data, Theap::data2id, DeleteVector(), Theap::hasIDs, Theap::id2data, and ResetHeap().

Referenced by AtlasAStar(), AtlasBiRRTstar(), AtlasGBF(), AtlasRRTstar(), BiRRTstar(), BuildAtlasFromPoint(), MPI_SolveCuikSystem(), RRTstar(), and SolveCuikSystem().

Institut de Robòtica i Informàtica Industrial

Detailed Description

Data Structures

Functions

Function Documentation

Institut de Robòtica
i Informàtica Industrial