|
|
heap.c File ReferenceImplementation of the functions operating on Theap. More... #include "heap.h" #include "error.h" #include "defines.h" #include <math.h> Go to the source code of this file.
Detailed DescriptionImplementation of the functions operating on Theap. Definition in file heap.c. Define Documentation
Returns the identifier of a child node in a binary heap from the identifier of the parent nodel Actually a node has two children. The first is directly the identifier returned here, the second is the returned value +1.
Definition at line 38 of file heap.c. Referenced by HeapDown(). Function Documentation
Moves an element up in the heap until it reaches a parent node larger than the moved node The nodes are compared using the LessThan function given in the heap constructor.
Definition at line 69 of file heap.c. References Theap::data, Theap::data2id, FALSE, GetVectorElement(), Theap::hasIDs, HEAP_PARENT, Theap::id2data, Theap::LessThan, SwapVectorElements(), TRUE, and Theap::userData. Referenced by AddElement2Heap(), and UpdateHeapElement().
Here is the call graph for this function:
Here is the caller graph for this function:
Moves an element up in the heap until it reaches a children nodes smaller than the moved node The nodes are compared using the LessThan function given in the heap constructor.
Definition at line 105 of file heap.c. References Theap::data, Theap::data2id, FALSE, GetVectorElement(), Theap::hasIDs, HEAP_CHILD, Theap::id2data, Theap::LessThan, SwapVectorElements(), TRUE, and Theap::userData. Referenced by ExtractMinElement(), and UpdateHeapElement().
Here is the call graph for this function:
Here is the caller graph for this function:
Comparison operator for identifiers identifying the lower of the two given identifiers.
Comparison operator for doubles identifying the lower of the two given doubles.
Comparison operator for pointers identifying the lower of the two given pointers.
Initializes an empty heap Examples of use:
Definition at line 172 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 InitHeapOfBoxes().
Here is the call graph for this function:
Here is the caller graph for this function:
Copies h_src into h_dst. This is a constructor and, thus, h_dst is initialized inside this function.
Definition at line 194 of file heap.c. References CopyVector(), Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, Theap::LessThan, and Theap::userData.
Here is the call graph for this function:
Returns the number of elements in a heap.
Definition at line 208 of file heap.c. References Theap::last. Referenced by Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), MPI_SolveCuikSystem(), and PrintHeapOfBoxes().
Here is the caller graph for this function:
Checks if a heap is empty
Definition at line 213 of file heap.c. References Theap::last. Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().
Here is the caller graph for this function:
Adds an element to the heap.
Definition at line 218 of file heap.c. References Theap::data, Theap::data2id, Theap::hasIDs, HeapUp(), Theap::id2data, Theap::last, and SetVectorElement(). Referenced by AddBox2HeapOfBoxes(), and AddList2Heap().
Here is the call graph for this function:
Here is the caller graph for this function:
Updates the position of an element in the heap given its identifier. This is to be used after the priority of an object has been updated. 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.
Definition at line 232 of file heap.c. References Error(), GetHeapPosition(), Theap::hasIDs, HeapDown(), and HeapUp().
Here is the call graph for this function:
Returns a pointer to a given heap element.
Definition at line 253 of file heap.c. References Theap::data, and GetVectorElement(). Referenced by GetHeapElementWithID(), Heap2List(), HeapOfBoxesMaxDiagonal(), HeapOfBoxesMaxSize(), HeapOfBoxesVolume(), and PrintHeapOfBoxes().
Here is the call graph for this function:
Here is the caller graph for this function:
Returns a pointer to a heap element given the element identifier.
Definition at line 262 of file heap.c. References GetHeapElement(), GetHeapPosition(), and Theap::hasIDs.
Here is the call graph for this function:
Returns the current position in the heap of an element given its identifier.
Definition at line 270 of file heap.c. References GetVectorElement(), Theap::hasIDs, Theap::id2data, and NO_UINT. Referenced by GetHeapElementWithID(), and UpdateHeapElement().
Here is the call graph for this function:
Here is the caller graph for this function:
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.
Definition at line 278 of file heap.c. References Theap::data, Theap::data2id, Error(), ExtractVectorElement(), GetVectorElement(), Theap::hasIDs, HeapDown(), Theap::id2data, Theap::last, RemoveVectorElement(), and SwapVectorElements(). Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
Removes all the elements from a heap.
Definition at line 304 of file heap.c. References Theap::data, Theap::data2id, Theap::hasIDs, Theap::id2data, Theap::last, and ResetVector(). Referenced by DeleteHeap().
Here is the call graph for this function:
Here is the caller graph for this function:
Deletes the information stored in the heap and frees the allocated memory space.
Definition at line 316 of file heap.c. References Theap::data, Theap::data2id, DeleteVector(), Theap::hasIDs, Theap::id2data, and ResetHeap(). Referenced by MPI_SolveCuikSystem(), and SolveCuikSystem().
Here is the call graph for this function:
Here is the caller graph for this function:
|