1 #ifndef VIENNA_RNA_PACKAGE_HEAP_H 2 #define VIENNA_RNA_PACKAGE_HEAP_H 3 4 /** 5 * @file ViennaRNA/datastructures/heap.h 6 * @ingroup heap_utils 7 * @brief Implementation of an abstract heap data structure 8 */ 9 10 /** 11 * @addtogroup heap_utils 12 * @{ 13 * @brief Interface for an abstract implementation of a heap data structure 14 * 15 */ 16 17 18 /** 19 * @brief An abstract heap data structure 20 * 21 * @see vrna_heap_init(), vrna_heap_free(), vrna_heap_insert(), 22 * vrna_heap_pop(), vrna_heap_top(), vrna_heap_remove(), 23 * vrna_heap_update() 24 */ 25 typedef struct vrna_heap_s *vrna_heap_t; 26 27 28 /** 29 * @brief Heap compare function prototype 30 * 31 * Use this prototype to design the compare function for the heap implementation. 32 * The arbitrary data pointer @p data may be used to get access to further information 33 * required to actually compare the two values @p a and @p b. 34 * 35 * @note The heap implementation acts as a <em>min-heap</em>, therefore, the minimum 36 * element will be present at the heap's root. In case a <em>max-heap</em> is 37 * required, simply reverse the logic of this compare function. 38 * 39 * @param a The first object to compare 40 * @param b The second object to compare 41 * @param data An arbitrary data pointer passed through from the heap implementation 42 * @return A value less than zero if @p a < @p b, a value greater than zero if @p a > @p b, and 0 otherwise 43 */ 44 typedef int (vrna_callback_heap_cmp)(const void *a, 45 const void *b, 46 void *data); 47 48 49 /** 50 * @brief Retrieve the position of a particular heap entry within the heap 51 * 52 * @param a The object to look-up within the heap 53 * @param data An arbitrary data pointer passed through from the heap implementation 54 * @return The position of the element @p a within the heap, or 0 if it is not in the heap 55 */ 56 typedef size_t (vrna_callback_heap_get_pos)(const void *a, 57 void *data); 58 59 60 /** 61 * @brief Store the position of a particular heap entry within the heap 62 * 63 * @param a The object whose position shall be stored 64 * @param pos The current position of @p a within the heap, or 0 if a was deleted 65 * @param data An arbitrary data pointer passed through from the heap implementation 66 */ 67 typedef void (vrna_callback_heap_set_pos)(const void *a, 68 size_t pos, 69 void *data); 70 71 72 /** 73 * @brief Initialize a heap data structure 74 * 75 * This function initializes a heap data structure. The implementation is based on a 76 * <em>min-heap</em>, i.e. the minimal element is located at the root of the heap. 77 * However, by reversing the logic of the compare function, one can easily transform 78 * this into a <em>max-heap</em> implementation. 79 * 80 * Beside the regular operations on a heap data structure, we implement removal and 81 * update of arbitrary elements within the heap. For that purpose, however, one requires 82 * a reverse-index lookup system that, (i) for a given element stores the current position 83 * in the heap, and (ii) allows for fast lookup of an elements current position within the 84 * heap. The corresponding getter- and setter- functions may be provided through the 85 * arguments @p get_entry_pos and @p set_entry_pos, respectively. 86 * 87 * Sometimes, it is difficult to simply compare two data structures without any context. 88 * Therefore, the compare function is provided with a user-defined data pointer that 89 * can hold any context required. 90 * 91 * @warning If any of the arguments @p get_entry_pos or @p set_entry_pos is NULL, the 92 * operations vrna_heap_update() and vrna_heap_remove() won't work. 93 * 94 * @see vrna_heap_free(), vrna_heap_insert(), vrna_heap_pop(), vrna_heap_top(), 95 * vrna_heap_remove(), vrna_heap_update(), #vrna_heap_t, #vrna_callback_heap_cmp, 96 * #vrna_callback_heap_get_pos, #vrna_callback_heap_set_pos 97 * 98 * @param n The initial size of the heap, i.e. the number of elements to store 99 * @param cmp The address of a compare function that will be used to fullfill the partial order requirement 100 * @param get_entry_pos The address of a function that retrieves the position of an element within the heap (or NULL) 101 * @param set_entry_pos The address of a function that stores the position of an element within the heap (or NULL) 102 * @param data An arbitrary data pointer passed through to the compare function @p cmp, and the set/get functions @p get_entry_pos / @p set_entry_pos 103 * @return An initialized heap data structure, or NULL on error 104 */ 105 vrna_heap_t 106 vrna_heap_init(size_t n, 107 vrna_callback_heap_cmp *cmp, 108 vrna_callback_heap_get_pos *get_entry_pos, 109 vrna_callback_heap_set_pos *set_entry_pos, 110 void *data); 111 112 113 /** 114 * @brief Free memory occupied by a heap data structure 115 * 116 * @see vrna_heap_init() 117 * 118 * @param h The heap that should be free'd 119 */ 120 void 121 vrna_heap_free(vrna_heap_t h); 122 123 124 /** 125 * @brief Get the size of a heap data structure, i.e. the number of stored elements 126 * 127 * @param h The heap data structure 128 * @return The number of elements currently stored in the heap, or 0 upon any error 129 */ 130 size_t 131 vrna_heap_size(struct vrna_heap_s *h); 132 133 134 /** 135 * @brief Insert an element into the heap 136 * 137 * @see vrna_heap_init(), vrna_heap_pop(), vrna_heap_top(), vrna_heap_free(), 138 * vrna_heap_remove(), vrna_heap_update() 139 * 140 * @param h The heap data structure 141 * @param v A pointer to the object that is about to be inserted into the heap 142 */ 143 void 144 vrna_heap_insert(vrna_heap_t h, 145 void *v); 146 147 148 /** 149 * @brief Pop (remove and return) the object at the root of the heap 150 * 151 * This function removes the root from the heap and returns it to the caller. 152 * 153 * @see vrna_heap_init(), vrna_heap_top(), vrna_heap_insert(), vrna_heap_free() 154 * vrna_heap_remove(), vrna_heap_update() 155 * 156 * @param h The heap data structure 157 * @return The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred) 158 */ 159 void * 160 vrna_heap_pop(vrna_heap_t h); 161 162 163 /** 164 * @brief Get the object at the root of the heap 165 * 166 * @see vrna_heap_init(), vrna_heap_pop(), vrna_heap_insert(), vrna_heap_free() 167 * vrna_heap_remove(), vrna_heap_update() 168 * 169 * @param h The heap data structure 170 * @return The object at the root of the heap, i.e. the minimal element (or NULL if (a) the heap is empty or (b) any error occurred) 171 */ 172 const void * 173 vrna_heap_top(vrna_heap_t h); 174 175 176 /** 177 * @brief Remove an arbitrary element within the heap 178 * 179 * @see vrna_heap_init(), #vrna_callback_heap_get_pos, #vrna_callback_heap_set_pos, 180 * vrna_heap_pop(), vrna_heap_free() 181 * 182 * @warning This function won't work if the heap was not properly initialized with 183 * callback functions for fast reverse-index mapping! 184 * 185 * @param h The heap data structure 186 * @param v The object to remove from the heap 187 * @return The object that was removed from the heap (or NULL if (a) it wasn't found or (b) any error occurred) 188 */ 189 void * 190 vrna_heap_remove(vrna_heap_t h, 191 const void *v); 192 193 194 /** 195 * @brief Update an arbitrary element within the heap 196 * 197 * @note If the object that is to be updated is not currently stored in the heap, 198 * it will be inserted. In this case, the function returns NULL. 199 * 200 * @warning This function won't work if the heap was not properly initialized with 201 * callback functions for fast reverse-index mapping! 202 * 203 * @see vrna_heap_init(), #vrna_callback_heap_get_pos, #vrna_callback_heap_set_pos 204 * vrna_heap_pop(), vrna_heap_remove(), vrna_heap_free() 205 * 206 * @param h The heap data structure 207 * @param v The object to update 208 * @return The 'previous' object within the heap that now got replaced by @p v (or NULL if (a) it wasn't found or (b) any error occurred) 209 */ 210 void * 211 vrna_heap_update(vrna_heap_t h, 212 void *v); 213 214 215 /** 216 * @} 217 */ 218 219 #endif 220