CMR  1.3.0
heap.h
Go to the documentation of this file.
1 #ifndef CMR_HEAP_INTERNAL_H
2 #define CMR_HEAP_INTERNAL_H
3 
4 #include <cmr/env.h>
5 #include "env_internal.h"
6 #include <limits.h>
7 
8 #ifdef __cplus
9 extern "C" {
10 #endif
11 
16 typedef struct
17 {
18  int size;
19  int memKeys;
20  int* values;
21  int* positions;
22  int* data;
23 } CMR_INTHEAP;
24 
30  CMR* cmr,
31  CMR_INTHEAP* heap,
32  int memKeys
33 );
34 
40  CMR* cmr,
41  CMR_INTHEAP* heap
42 );
43 
49  CMR_INTHEAP* heap,
50  int key,
51  int value
52 );
53 
59  CMR_INTHEAP* heap,
60  int key,
61  int newValue
62 );
63 
69  CMR_INTHEAP* heap,
70  int key,
71  int newValue
72 );
73 
78 static inline
80  CMR_INTHEAP* heap
81 )
82 {
83  return heap->size == 0;
84 }
85 
90 static inline
92  CMR_INTHEAP* heap
93 )
94 {
95  return heap->data[0];
96 }
97 
102 static inline
104  CMR_INTHEAP* heap
105 )
106 {
107  return heap->values[heap->data[0]];
108 }
109 
114 static inline
116  CMR_INTHEAP* heap,
117  int key
118 )
119 {
120  return heap->positions[key] >= 0;
121 }
122 
123 static inline
125  CMR_INTHEAP* heap, /*< Heap. */
126  int key /*< Key whose value shall be returned. */
127 )
128 {
129  return heap->values[key];
130 }
131 
136 static inline
138  CMR_INTHEAP* heap,
139  int key
140 )
141 {
142  if (heap->positions[key] >= 0)
143  return heap->values[key];
144  else
145  return INT_MAX;
146 }
147 
153  CMR_INTHEAP* heap
154 );
155 
156 #ifdef __cplusplus
157 }
158 #endif
159 
160 #endif /* CMR_HEAP_INTERNAL_H */
Basic functionality of the software library.
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:27
CMR_ERROR CMRintheapInsert(CMR_INTHEAP *heap, int key, int value)
Inserts a key value pair into the heap.
Definition: heap.c:62
static int CMRintheapGetValue(CMR_INTHEAP *heap, int key)
Definition: heap.h:124
CMR_ERROR CMRintheapDecreaseInsert(CMR_INTHEAP *heap, int key, int newValue)
Decreases the value of key to newValue or inserts it.
Definition: heap.c:137
int CMRintheapExtractMinimum(CMR_INTHEAP *heap)
Extracts the minimum element and returns its key.
Definition: heap.c:184
CMR_ERROR CMRintheapClearStack(CMR *cmr, CMR_INTHEAP *heap)
Clears the given heap.
Definition: heap.c:29
CMR_ERROR CMRintheapInitStack(CMR *cmr, CMR_INTHEAP *heap, int memKeys)
Initializes an empty heap using stack memory.
Definition: heap.c:9
CMR_ERROR CMRintheapDecrease(CMR_INTHEAP *heap, int key, int newValue)
Decreases the value of key to newValue.
Definition: heap.c:103
static int CMRintheapGetValueInfinity(CMR_INTHEAP *heap, int key)
Reutrns the value of key or INT_MAX if there is no such element.
Definition: heap.h:137
static bool CMRintheapContains(CMR_INTHEAP *heap, int key)
Returns true if an element with key is present in the heap.
Definition: heap.h:115
static int CMRintheapMinimumValue(CMR_INTHEAP *heap)
Returns the value of the minimum element.
Definition: heap.h:103
static int CMRintheapMinimumKey(CMR_INTHEAP *heap)
Returns the key of the minimum element.
Definition: heap.h:91
static bool CMRintheapEmpty(CMR_INTHEAP *heap)
Returns true if the heap is empty.
Definition: heap.h:79
Definition: env_internal.h:45
Structure for min-heap with unsigned int values.
Definition: heap.h:17
int memKeys
Memory for keys.
Definition: heap.h:19
int * positions
Array that maps keys to heap positions.
Definition: heap.h:21
int * data
Array that maps heap positions to keys.
Definition: heap.h:22
int size
Current size of the heap.
Definition: heap.h:18
int * values
Array that maps keys to values.
Definition: heap.h:20