Scippy

SCIP

Solving Constraint Integer Programs

stpprioqueue.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file stpprioqueue.c
17  * @brief priority queue with integer keys
18  * @author Daniel Rehfeldt
19  *
20  * Implements a (minimum) priority queue with integer keys.
21  * A list of all interface methods can be found in stpprioqueue.h
22  ** todo: if needed for other key type, either use template pattern
23  * or intrusive design with macros...
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 #include <assert.h>
30 #include <string.h>
31 #include <stdio.h>
32 #include "stpprioqueue.h"
33 
34 
35 #define STPPQ_MIN_KEY INT_MIN
36 
37 
38 /** PQ entry */
40 {
41  void* data;
42  int key;
43 } PQENTRY;
44 
45 
46 /** PQ with integer keys */
48 {
49  int capacity; /**< maximum size */
50  int size; /**< size */
51  PQENTRY* entries; /**< entries */
52 };
53 
54 
55 /*
56  * Local methods
57  */
58 
59 
60 /*
61  * Interface methods
62  */
63 
64 
65 /** clean the priority queue */
67  STP_PQ* prioqueue /**< the priority queue */
68  )
69 {
70  assert(prioqueue);
71 
72  prioqueue->size = 0;
73  assert(stpprioqueue_isClean(prioqueue));
74 }
75 
76 
77 /** is the priority queue clean? */
79  const STP_PQ* prioqueue /**< the priority queue */
80  )
81 {
82  assert(prioqueue);
83 
84  if( prioqueue->size != 0 )
85  {
86  SCIPdebugMessage("prioqueue size not 0! (=%d)\n", prioqueue->size);
87  return FALSE;
88  }
89 
90  return TRUE;
91 }
92 
93 
94 /** creates new prioqueue. If entries array is provided, it must be of size capacity + 2 */
96  SCIP* scip, /**< SCIP */
97  int capacity, /**< initial capacity */
98  STP_PQ** prioqueue /**< the priority queue */
99  )
100 {
101  PQENTRY* entries_heap;
102 
103  assert(scip && prioqueue);
104  assert(capacity >= 1);
105 
106  SCIP_CALL( SCIPallocMemory(scip, prioqueue) );
107  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(entries_heap), capacity + 1) );
108 
109  (*prioqueue)->capacity = capacity;
110  (*prioqueue)->entries = entries_heap;
111 
112  /* sentinel */
113  entries_heap[0].key = STPPQ_MIN_KEY;
114 
115  stpprioqueue_clean(*prioqueue);
116 
117  return SCIP_OKAY;
118 }
119 
120 /** frees the priority queue */
122  SCIP* scip, /**< SCIP */
123  STP_PQ** prioqueue /**< the priority queue */
124  )
125 {
126  assert(scip && prioqueue);
127 
128  SCIPfreeBlockMemoryArray(scip, &((*prioqueue)->entries), (*prioqueue)->capacity + 1);
129  SCIPfreeMemory(scip, prioqueue);
130 }
131 
132 /** shows top data */
134  const STP_PQ* prioqueue /**< the priority queue */
135  )
136 {
137  assert(prioqueue);
138  assert(prioqueue->size > 0);
139 
140  return prioqueue->entries[1].data;
141 }
142 
143 
144 /** shows top key */
146  const STP_PQ* prioqueue /**< the priority queue */
147  )
148 {
149  assert(prioqueue);
150  assert(prioqueue->size > 0);
151 
152  return prioqueue->entries[1].key;
153 }
154 
155 
156 /** deletes minimum and gives key and data */
158  void** data, /**< pointer to data of minimum */
159  int* key, /**< pointer to key of minimum */
160  STP_PQ* prioqueue /**< the priority queue */
161  )
162 {
163  assert(data && key && prioqueue);
164 
165  *key = prioqueue->entries[1].key;
166  *data = stpprioqueue_deleteMinReturnData(prioqueue);
167 }
168 
169 
170 /** deletes minimum and returns corresponding data */
172  STP_PQ* prioqueue /**< the priority queue */
173  )
174 {
175  PQENTRY* const RESTRICT entries = prioqueue->entries;
176  int fill;
177  int parent;
178  int hole = 1;
179  int child = 2;
180  void* data;
181  const int lastentry = prioqueue->size--;
182 
183  assert(prioqueue && entries);
184  assert(prioqueue->size >= 0);
185 
186  data = entries[1].data;
187 
188  /* move down along min-path */
189  while( child < lastentry )
190  {
191  const SCIP_Real key1 = entries[child].key;
192  const SCIP_Real key2 = entries[child + 1].key;
193  assert(hole >= 1);
194 
195  /* second child with smaller key? */
196  if( key1 > key2 )
197  {
198  entries[hole].key = key2;
199  child++;
200  }
201  else
202  {
203  entries[hole].key = key1;
204  }
205 
206  entries[hole].data = entries[child].data;
207 
208  hole = child;
209  child *= 2;
210  }
211 
212  /* now hole is at last tree level, fill it with last PQ entry and move it up */
213 
214  fill = entries[lastentry].key;
215  parent = hole / 2;
216 
217  while( entries[parent].key > fill )
218  {
219  assert(hole >= 1);
220 
221  entries[hole] = entries[parent];
222 
223  hole = parent;
224  parent /= 2;
225  }
226 
227  /* finally, fill the hole */
228  entries[hole].key = fill;
229  entries[hole].data = entries[lastentry].data;
230 
231  return data;
232 }
233 
234 
235 /** inserts data */
237  SCIP* scip, /**< SCIP */
238  void* data, /**< the data */
239  int newkey, /**< the key */
240  STP_PQ* prioqueue /**< the priority queue */
241  )
242 {
243  PQENTRY* RESTRICT entries;
244  int hole;
245  int parent;
246  int parentkey;
247 
248  assert(scip && prioqueue);
249  assert(prioqueue->entries);
250  assert(newkey > STPPQ_MIN_KEY);
251  assert(prioqueue->size <= prioqueue->capacity);
252 
253  if( prioqueue->size == prioqueue->capacity )
254  {
255  const int oldsize = prioqueue->capacity + 1;
256  prioqueue->capacity *= 2;
257  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(prioqueue->entries), oldsize, prioqueue->capacity + 1) );
258  }
259 
260  entries = prioqueue->entries;
261  hole = ++(prioqueue->size);
262  parent = hole / 2;
263  parentkey = entries[parent].key;
264 
265  /* move hole up */
266  while( parentkey > newkey )
267  {
268  assert(hole >= 1);
269 
270  entries[hole].key = parentkey;
271  entries[hole].data = entries[parent].data;
272  hole = parent;
273  parent /= 2;
274  parentkey = entries[parent].key;
275  }
276 
277  /* fill the hole */
278  entries[hole].key = newkey;
279  entries[hole].data = data;
280 
281  return SCIP_OKAY;
282 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
void * data
Definition: stpprioqueue.c:41
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE stpprioqueue_create(SCIP *scip, int capacity, STP_PQ **prioqueue)
Definition: stpprioqueue.c:95
void stpprioqueue_free(SCIP *scip, STP_PQ **prioqueue)
Definition: stpprioqueue.c:121
#define STPPQ_MIN_KEY
Definition: stpprioqueue.c:35
int key
Definition: stpprioqueue.c:42
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE stpprioqueue_insert(SCIP *scip, void *data, int newkey, STP_PQ *prioqueue)
Definition: stpprioqueue.c:236
void stpprioqueue_deleteMin(void **data, int *key, STP_PQ *prioqueue)
Definition: stpprioqueue.c:157
const void * stpprioqueue_peakMinData(const STP_PQ *prioqueue)
Definition: stpprioqueue.c:133
int stpprioqueue_peakMinKey(const STP_PQ *prioqueue)
Definition: stpprioqueue.c:145
priority queue with integer keys
#define SCIP_CALL(x)
Definition: def.h:384
Definition: graph_load.c:93
#define SCIP_Bool
Definition: def.h:84
Definition: stpprioqueue.c:39
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_Bool stpprioqueue_isClean(const STP_PQ *prioqueue)
Definition: stpprioqueue.c:78
void * stpprioqueue_deleteMinReturnData(STP_PQ *prioqueue)
Definition: stpprioqueue.c:171
#define SCIP_Real
Definition: def.h:177
struct stp_priority_queue_entry PQENTRY
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
void stpprioqueue_clean(STP_PQ *prioqueue)
Definition: stpprioqueue.c:66