gcgpqueue.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #include "gcgpqueue.h"
39 #include "pub_gcgpqueue.h"
40 
41 #include "gcg.h"
42 #include "scip/def.h"
43 #include "scip/scip.h"
44 #include "blockmemshell/memory.h"
45 
46 #include <assert.h>
47 
48 
49 
50 /*
51  * Priority Queue
52  */
53 
54 #define PQ_PARENT(q) (((q)+1)/2-1)
55 #define PQ_LEFTCHILD(p) (2*(p)+1)
56 #define PQ_RIGHTCHILD(p) (2*(p)+2)
57 
58 
60 static
61 SCIP_RETCODE pqueueResize(
62  GCG_PQUEUE* pqueue,
63  int minsize
64  )
65 {
66  assert(pqueue != NULL);
67 
68  if( minsize <= pqueue->size )
69  return SCIP_OKAY;
70 
71  pqueue->size = MAX(minsize, (int)(pqueue->size * pqueue->sizefac));
72  SCIP_ALLOC( BMSreallocMemoryArray(&pqueue->slots, pqueue->size) );
73 
74  return SCIP_OKAY;
75 }
76 
78 static
79 SCIP_RETCODE pqueueHeapify(
80  GCG_PQUEUE* pqueue,
81  int pos
82  )
83 {
84  int childpos;
85  int brotherpos;
86  void* elem;
87 
88  assert(pqueue != NULL);
89  assert(pqueue->len > 0);
90 
91  /* move the better child of elem to its parents position until element
92  * is better than its children
93  */
94  elem = pqueue->slots[pos];
95 
96  while( pos <= PQ_PARENT(pqueue->len-1) )
97  {
98  childpos = PQ_LEFTCHILD(pos);
99  brotherpos = PQ_RIGHTCHILD(pos);
100  if( brotherpos < pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
101  childpos = brotherpos;
102  if( (*pqueue->ptrcomp)(elem, pqueue->slots[childpos]) < 0 )
103  break;
104  pqueue->slots[pos] = pqueue->slots[childpos];
105  pqueue->slots[childpos] = elem;
106 
107  pos = childpos;
108  }
109  assert(0 <= pos && pos < pqueue->len);
110 
111  return SCIP_OKAY;
112 }
113 
114 
116 SCIP_RETCODE GCGpqueueCreate(
117  GCG_PQUEUE** pqueue,
118  int initsize,
119  SCIP_Real sizefac,
120  SCIP_DECL_SORTPTRCOMP((*ptrcomp))
121  )
122 {
123  assert(pqueue != NULL);
124  assert(ptrcomp != NULL);
125 
126  initsize = MAX(1, initsize);
127  sizefac = MAX(1.0, sizefac);
128 
129  SCIP_ALLOC( BMSallocMemory(pqueue) );
130  (*pqueue)->len = 0;
131  (*pqueue)->size = 0;
132  (*pqueue)->sizefac = sizefac;
133  (*pqueue)->slots = NULL;
134  (*pqueue)->ptrcomp = ptrcomp;
135  SCIP_CALL( pqueueResize(*pqueue, initsize) );
136 
137  return SCIP_OKAY;
138 }
139 
142  GCG_PQUEUE** pqueue
143  )
144 {
145  assert(pqueue != NULL);
146 
147  BMSfreeMemoryArray(&(*pqueue)->slots);
148  BMSfreeMemory(pqueue);
149 }
150 
153  GCG_PQUEUE* pqueue
154  )
155 {
156  assert(pqueue != NULL);
157 
158  pqueue->len = 0;
159 }
160 
162 SCIP_RETCODE GCGpqueueInsert(
163  GCG_PQUEUE* pqueue,
164  void* elem
165  )
166 {
167  int pos;
168  int parentpos;
169 
170  assert(pqueue != NULL);
171  assert(pqueue->len >= 0);
172  assert(elem != NULL);
173 
174  SCIP_CALL( pqueueResize(pqueue, pqueue->len+1) );
175 
176  /* insert element as leaf in the tree, move it towards the root as long it is better than its parent */
177  pos = pqueue->len;
178  parentpos = PQ_PARENT(pos);
179  pqueue->len++;
180  while( pos > 0 && (*pqueue->ptrcomp)(elem, pqueue->slots[parentpos]) < 0 )
181  {
182  pqueue->slots[pos] = pqueue->slots[parentpos];
183  pos = parentpos;
184  parentpos = PQ_PARENT(pos);
185  }
186  pqueue->slots[pos] = elem;
187 
188  return SCIP_OKAY;
189 }
190 
193  GCG_PQUEUE* pqueue
194  )
195 {
196  void* root;
197  void* last;
198  int pos;
199  int childpos;
200  int brotherpos;
201 
202  assert(pqueue != NULL);
203  assert(pqueue->len >= 0);
204 
205  if( pqueue->len == 0 )
206  return NULL;
207 
208  /* remove root element of the tree, move the better child to its parents position until the last element
209  * of the queue could be placed in the empty slot
210  */
211  root = pqueue->slots[0];
212  last = pqueue->slots[pqueue->len-1];
213  pqueue->len--;
214  pos = 0;
215  while( pos <= PQ_PARENT(pqueue->len-1) )
216  {
217  childpos = PQ_LEFTCHILD(pos);
218  brotherpos = PQ_RIGHTCHILD(pos);
219  if( brotherpos <= pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
220  childpos = brotherpos;
221  if( (*pqueue->ptrcomp)(last, pqueue->slots[childpos]) <= 0 )
222  break;
223  pqueue->slots[pos] = pqueue->slots[childpos];
224  pos = childpos;
225  }
226  assert(pos <= pqueue->len);
227  pqueue->slots[pos] = last;
228 
229  return root;
230 }
231 
233 SCIP_RETCODE GCGpqueueResort(
234  GCG_PQUEUE* pqueue
235  )
236 {
237  int lastinner;
238  int pos;
239 
240  assert(pqueue != NULL);
241  assert(pqueue->len >= 0);
242 
243  if( pqueue->len == 0 )
244  {
245  return SCIP_OKAY;
246  }
247 
248  lastinner = PQ_PARENT(pqueue->len - 1);
249 
250  for( pos = lastinner; pos >= 0; --pos )
251  {
252  SCIP_CALL( pqueueHeapify(pqueue, pos) );
253  }
254 
255  return SCIP_OKAY;
256 }
257 
258 
261  GCG_PQUEUE* pqueue,
262  SCIP_DECL_SORTPTRCOMP((*ptrcomp))
263  )
264 {
265  pqueue->ptrcomp = ptrcomp;
266 
267  return SCIP_OKAY;
268 }
269 
270 /* todo: write method to get comperator */
271 
273 SCIP_RETCODE GCGpqueueDelete(
274  GCG_PQUEUE* pqueue,
275  int pos,
276  void** elem
277  )
278 {
279  void* last;
280  int childpos;
281  int brotherpos;
282 
283  assert(pqueue != NULL);
284  assert(pqueue->len >= 0);
285 
286  assert(pos < pqueue->len);
287 
288  /* remove element at position pos of the tree, move the better child to its parents position until the last element
289  * of the queue could be placed in the empty slot
290  */
291  *elem = pqueue->slots[pos];
292  last = pqueue->slots[pqueue->len-1];
293  pqueue->len--;
294  while( pos <= PQ_PARENT(pqueue->len-1) )
295  {
296  childpos = PQ_LEFTCHILD(pos);
297  brotherpos = PQ_RIGHTCHILD(pos);
298  if( brotherpos <= pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
299  childpos = brotherpos;
300  if( (*pqueue->ptrcomp)(last, pqueue->slots[childpos]) <= 0 )
301  break;
302  pqueue->slots[pos] = pqueue->slots[childpos];
303  pos = childpos;
304  }
305  assert(pos <= pqueue->len);
306  pqueue->slots[pos] = last;
307 
308  return SCIP_OKAY;
309 }
310 
313  GCG_PQUEUE* pqueue
314  )
315 {
316  assert(pqueue != NULL);
317  assert(pqueue->len >= 0);
318 
319  if( pqueue->len == 0 )
320  return NULL;
321 
322  return pqueue->slots[0];
323 }
324 
327  GCG_PQUEUE* pqueue
328  )
329 {
330  assert(pqueue != NULL);
331  assert(pqueue->len >= 0);
332 
333  return pqueue->len;
334 }
335 
338  GCG_PQUEUE* pqueue
339  )
340 {
341  assert(pqueue != NULL);
342  assert(pqueue->len >= 0);
343 
344  return pqueue->slots;
345 }
void * GCGpqueueRemove(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:192
private methods for working with priority queue
static SCIP_DECL_SORTPTRCOMP(sortptrcons)
Definition: bliss.cpp:159
GCG interface methods.
SCIP_RETCODE GCGpqueueCreate(GCG_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
Definition: gcgpqueue.c:116
struct GCG_PQueue GCG_PQUEUE
void GCGpqueueClear(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:152
SCIP_RETCODE GCGpqueueResort(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:233
#define PQ_RIGHTCHILD(p)
Definition: gcgpqueue.c:56
SCIP_RETCODE GCGpqueueInsert(GCG_PQUEUE *pqueue, void *elem)
Definition: gcgpqueue.c:162
SCIP_RETCODE GCGpqueueDelete(GCG_PQUEUE *pqueue, int pos, void **elem)
Definition: gcgpqueue.c:273
SCIP_RETCODE GCGpqueueSetComperator(GCG_PQUEUE *pqueue, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
Definition: gcgpqueue.c:260
static SCIP_RETCODE pqueueResize(GCG_PQUEUE *pqueue, int minsize)
Definition: gcgpqueue.c:61
int GCGpqueueNElems(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:326
void ** GCGpqueueElems(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:337
void GCGpqueueFree(GCG_PQUEUE **pqueue)
Definition: gcgpqueue.c:141
#define PQ_PARENT(q)
Definition: gcgpqueue.c:54
static SCIP_RETCODE pqueueHeapify(GCG_PQUEUE *pqueue, int pos)
Definition: gcgpqueue.c:79
#define PQ_LEFTCHILD(p)
Definition: gcgpqueue.c:55
void * GCGpqueueFirst(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:312