Scippy

SCIP

Solving Constraint Integer Programs

misc.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-2020 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 misc.c
17  * @ingroup OTHER_CFILES
18  * @brief miscellaneous methods
19  * @author Tobias Achterberg
20  * @author Gerald Gamrath
21  * @author Stefan Heinz
22  * @author Michael Winkler
23  * @author Kati Wolter
24  * @author Gregor Hendel
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 <stdarg.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <errno.h>
35 
36 #include "scip/def.h"
37 #include "scip/pub_message.h"
38 #include "scip/misc.h"
39 #include "scip/intervalarith.h"
40 #include "scip/pub_misc.h"
41 
42 #ifndef NDEBUG
43 #include "scip/struct_misc.h"
44 #endif
45 
46 /*
47  * methods for statistical tests
48  */
49 
50 #define SQRTOFTWO 1.4142136 /**< the square root of 2 with sufficient precision */
51 
52 /**< contains all critical values for a one-sided two sample t-test up to 15 degrees of freedom
53  * a critical value represents a threshold for rejecting the null-hypothesis in hypothesis testing at
54  * a certain confidence level;
55  *
56  * access through method SCIPstudentTGetCriticalValue()
57  *
58  * source: German Wikipedia
59  *
60  * for confidence levels
61  * c =
62  * 0.75 0.875 0.90 0.95 0.975 (one-sided)
63  * 0.50 0.750 0.80 0.90 0.950 (two-sided)
64  *
65  */
66 static const SCIP_Real studentt_quartiles[] = { /* df:*/
67  1.000, 2.414, 3.078, 6.314, 12.706, /* 1 */
68  0.816, 1.604, 1.886, 2.920, 4.303, /* 2 */
69  0.765, 1.423, 1.638, 2.353, 3.182, /* 3 */
70  0.741, 1.344, 1.533, 2.132, 2.776, /* 4 */
71  0.727, 1.301, 1.476, 2.015, 2.571, /* 5 */
72  0.718, 1.273, 1.440, 1.943, 2.447, /* 6 */
73  0.711, 1.254, 1.415, 1.895, 2.365, /* 7 */
74  0.706, 1.240, 1.397, 1.860, 2.306, /* 8 */
75  0.703, 1.230, 1.383, 1.833, 2.262, /* 9 */
76  0.700, 1.221, 1.372, 1.812, 2.228, /* 10 */
77  0.697, 1.214, 1.363, 1.796, 2.201, /* 11 */
78  0.695, 1.209, 1.356, 1.782, 2.179, /* 12 */
79  0.694, 1.204, 1.350, 1.771, 2.160, /* 13 */
80  0.692, 1.200, 1.345, 1.761, 2.145, /* 14 */
81  0.691, 1.197, 1.341, 1.753, 2.131 /* 15 */
82 };
83 
84 /**< critical values for higher degrees of freedom of Student-T distribution for the same error probabilities; infact,
85  * these are critical values of the standard normal distribution with mean 0 and variance 1
86  */
88  0.674, 1.150, 1.282, 1.645, 1.960
89 };
90 
91 /** the maximum degrees of freedom represented before switching to normal approximation */
92 static const int studentt_maxdf = sizeof(studentt_quartiles)/(5 * sizeof(SCIP_Real));
93 
94 /** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */
96  SCIP_CONFIDENCELEVEL clevel, /**< (one-sided) confidence level */
97  int df /**< degrees of freedom */
98  )
99 {
100  if( df > studentt_maxdf )
101  return studentt_quartilesabove[(int)clevel];
102  else
103  return studentt_quartiles[(int)clevel + 5 * (df - 1)];
104 }
105 
106 /** compute a t-value for the hypothesis that x and y are from the same population; Assuming that
107  * x and y represent normally distributed random samples with equal variance, the returned value
108  * comes from a Student-T distribution with countx + county - 2 degrees of freedom; this
109  * value can be compared with a critical value (see also SCIPstudentTGetCriticalValue()) at
110  * a predefined confidence level for checking if x and y significantly differ in location
111  */
113  SCIP_Real meanx, /**< the mean of the first distribution */
114  SCIP_Real meany, /**< the mean of the second distribution */
115  SCIP_Real variancex, /**< the variance of the x-distribution */
116  SCIP_Real variancey, /**< the variance of the y-distribution */
117  SCIP_Real countx, /**< number of samples of x */
118  SCIP_Real county /**< number of samples of y */
119  )
120 {
121  SCIP_Real pooledvariance;
122  SCIP_Real tresult;
123 
124  /* too few samples */
125  if( countx < 1.9 || county < 1.9 )
126  return SCIP_INVALID;
127 
128  /* pooled variance is the weighted average of the two variances */
129  pooledvariance = (countx - 1) * variancex + (county - 1) * variancey;
130  pooledvariance /= (countx + county - 2);
131 
132  /* a variance close to zero means the distributions are basically constant */
133  pooledvariance = MAX(pooledvariance, 1e-9);
134 
135  /* tresult can be understood as realization of a Student-T distributed variable with
136  * countx + county - 2 degrees of freedom
137  */
138  tresult = (meanx - meany) / pooledvariance;
139  tresult *= SQRT(countx * county / (countx + county));
140 
141  return tresult;
142 }
143 
144 /** returns the value of the Gauss error function evaluated at a given point */
146  SCIP_Real x /**< value to evaluate */
147  )
148 {
149 #if defined(_WIN32) || defined(_WIN64)
150  SCIP_Real a1, a2, a3, a4, a5, p, t, y;
151  int sign;
152 
153  a1 = 0.254829592;
154  a2 = -0.284496736;
155  a3 = 1.421413741;
156  a4 = -1.453152027;
157  a5 = 1.061405429;
158  p = 0.3275911;
159 
160  sign = (x >= 0) ? 1 : -1;
161  x = REALABS(x);
162 
163  t = 1.0/(1.0 + p*x);
164  y = 1.0 - (((((a5*t + a4)*t) + a3)*t + a2)*t + a1)*t*exp(-x*x);
165  return sign * y;
166 #else
167  return erf(x);
168 #endif
169 }
170 
171 /** get critical value of a standard normal distribution at a given confidence level */
173  SCIP_CONFIDENCELEVEL clevel /**< (one-sided) confidence level */
174  )
175 {
176  return studentt_quartilesabove[(int)clevel];
177 }
178 
179 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
180  * random variable x takes a value between -infinity and parameter \p value.
181  *
182  * The distribution is given by the respective mean and deviation. This implementation
183  * uses the error function SCIPerf().
184  */
186  SCIP_Real mean, /**< the mean value of the distribution */
187  SCIP_Real variance, /**< the square of the deviation of the distribution */
188  SCIP_Real value /**< the upper limit of the calculated distribution integral */
189  )
190 {
191  SCIP_Real normvalue;
192  SCIP_Real std;
193 
194  /* we need to calculate the standard deviation from the variance */
195  assert(variance >= -1e-9);
196  if( variance < 1e-9 )
197  std = 0.0;
198  else
199  std = sqrt(variance);
200 
201  /* special treatment for zero variance */
202  if( std < 1e-9 )
203  {
204  if( value < mean + 1e-9 )
205  return 1.0;
206  else
207  return 0.0;
208  }
209  assert( std != 0.0 ); /* for lint */
210 
211  /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
212  normvalue = (value - mean)/(std * SQRTOFTWO);
213 
214  SCIPdebugMessage(" Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
215 
216  /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate the normvalue and
217  * use the oddness of the SCIPerf()-function; special treatment for values close to zero.
218  */
219  if( normvalue < 1e-9 && normvalue > -1e-9 )
220  return .5;
221  else if( normvalue > 0 )
222  {
223  SCIP_Real erfresult;
224 
225  erfresult = SCIPerf(normvalue);
226  return erfresult / 2.0 + 0.5;
227  }
228  else
229  {
230  SCIP_Real erfresult;
231 
232  erfresult = SCIPerf(-normvalue);
233 
234  return 0.5 - erfresult / 2.0;
235  }
236 }
237 
238 /*
239  * SCIP regression methods
240  */
241 
242 /** returns the number of observations of this regression */
244  SCIP_REGRESSION* regression /**< regression data structure */
245  )
246 {
247  assert(regression != NULL);
248 
249  return regression->nobservations;
250 }
251 
252 /** return the current slope of the regression */
254  SCIP_REGRESSION* regression /**< regression data structure */
255  )
256 {
257  assert(regression != NULL);
258 
259  return regression->slope;
260 }
261 
262 /** get the current y-intercept of the regression */
264  SCIP_REGRESSION* regression /**< regression data structure */
265  )
266 {
267  assert(regression != NULL);
268 
269  return regression->intercept;
270 }
271 
272 /** recomputes regression coefficients from available observation data */
273 static
275  SCIP_REGRESSION* regression /**< regression data structure */
276  )
277 {
278  /* regression coefficients require two or more observations and variance in x */
279  if( regression->nobservations <= 1 || EPSZ(regression->variancesumx, 1e-9) )
280  {
281  regression->slope = SCIP_INVALID;
282  regression->intercept = SCIP_INVALID;
283  regression->corrcoef = SCIP_INVALID;
284  }
285  else if( EPSZ(regression->variancesumy, 1e-9) )
286  {
287  /* if there is no variance in the y's (but in the x's), the regression line is horizontal with y-intercept through the mean y */
288  regression->slope = 0.0;
289  regression->corrcoef = 0.0;
290  regression->intercept = regression->meany;
291  }
292  else
293  {
294  /* we ruled this case out already, but to please some compilers... */
295  assert(regression->variancesumx > 0.0);
296  assert(regression->variancesumy > 0.0);
297 
298  /* compute slope */
299  regression->slope = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) / regression->variancesumx;
300 
301  /* compute y-intercept */
302  regression->intercept = regression->meany - regression->slope * regression->meanx;
303 
304  /* compute empirical correlation coefficient */
305  regression->corrcoef = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) /
306  sqrt(regression->variancesumx * regression->variancesumy);
307  }
308 }
309 
310 /* incremental update of statistics describing mean and variance */
311 static
313  SCIP_Real value, /**< current value to be added to incremental statistics */
314  SCIP_Real* meanptr, /**< pointer to value of current mean */
315  SCIP_Real* sumvarptr, /**< pointer to the value of the current variance sum term */
316  int nobservations, /**< total number of observations */
317  SCIP_Bool add /**< TRUE if the value should be added, FALSE for removing it */
318  )
319 {
320  SCIP_Real oldmean;
321  SCIP_Real addfactor;
322  assert(meanptr != NULL);
323  assert(sumvarptr != NULL);
324  assert(nobservations > 0 || add);
325 
326  addfactor = add ? 1.0 : -1.0;
327 
328  oldmean = *meanptr;
329  *meanptr = oldmean + addfactor * (value - oldmean)/(SCIP_Real)nobservations;
330  *sumvarptr += addfactor * (value - oldmean) * (value - (*meanptr));
331 
332  /* it may happen that *sumvarptr is slightly negative, especially after a series of add/removal operations */
333  assert(*sumvarptr >= -1e-4);
334  *sumvarptr = MAX(0.0, *sumvarptr);
335 }
336 
337 /** removes an observation (x,y) from the regression */
339  SCIP_REGRESSION* regression, /**< regression data structure */
340  SCIP_Real x, /**< X of observation */
341  SCIP_Real y /**< Y of the observation */
342  )
343 {
344  assert(regression != NULL);
345  assert(regression->nobservations > 0);
346 
347  /* simply call the reset function in the case of a single remaining observation to avoid numerical troubles */
348  if( regression->nobservations == 1 )
349  {
350  SCIPregressionReset(regression);
351  }
352  else
353  {
354  SCIP_Bool add = FALSE;
355  --regression->nobservations;
356 
357  /* decrement individual means and variances */
358  incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
359  incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
360 
361  /* decrement product sum */
362  regression->sumxy -= (x * y);
363  }
364 
365  /* recompute regression parameters */
366  regressionRecompute(regression);
367 }
368 
369 /** update regression by a new observation (x,y) */
371  SCIP_REGRESSION* regression, /**< regression data structure */
372  SCIP_Real x, /**< X of observation */
373  SCIP_Real y /**< Y of the observation */
374  )
375 {
376  SCIP_Bool add = TRUE;
377  assert(regression != NULL);
378 
379  ++(regression->nobservations);
380  incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
381  incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
382 
383  regression->sumxy += x * y;
384 
385  regressionRecompute(regression);
386 }
387 
388 /** reset regression data structure */
390  SCIP_REGRESSION* regression /**< regression data structure */
391  )
392 {
393  regression->intercept = SCIP_INVALID;
394  regression->slope = SCIP_INVALID;
395  regression->corrcoef = SCIP_INVALID;
396  regression->meanx = 0;
397  regression->variancesumx = 0;
398  regression->sumxy = 0;
399  regression->meany = 0;
400  regression->variancesumy = 0;
401  regression->nobservations = 0;
402 }
403 
404 /** creates and resets a regression */
406  SCIP_REGRESSION** regression /**< regression data structure */
407  )
408 {
409  assert(regression != NULL);
410 
411  /* allocate necessary memory */
412  SCIP_ALLOC (BMSallocMemory(regression) );
413 
414  /* reset the regression */
415  SCIPregressionReset(*regression);
416 
417  return SCIP_OKAY;
418 }
419 
420 /** creates and resets a regression */
422  SCIP_REGRESSION** regression /**< regression data structure */
423  )
424 {
425  BMSfreeMemory(regression);
426 }
427 
428 /** calculate memory size for dynamically allocated arrays (copied from scip/set.c) */
429 static
431  int initsize, /**< initial size of array */
432  SCIP_Real growfac, /**< growing factor of array */
433  int num /**< minimum number of entries to store */
434  )
435 {
436  int size;
437 
438  assert(initsize >= 0);
439  assert(growfac >= 1.0);
440  assert(num >= 0);
441 
442  if( growfac == 1.0 )
443  size = MAX(initsize, num);
444  else
445  {
446  int oldsize;
447 
448  /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
449  initsize = MAX(initsize, 4);
450  size = initsize;
451  oldsize = size - 1;
452 
453  /* second condition checks against overflow */
454  while( size < num && size > oldsize )
455  {
456  oldsize = size;
457  size = (int)(growfac * size + initsize);
458  }
459 
460  /* if an overflow happened, set the correct value */
461  if( size <= oldsize )
462  size = num;
463  }
464 
465  assert(size >= initsize);
466  assert(size >= num);
467 
468  return size;
469 }
470 
471 /*
472  * GML graphical printing methods
473  * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html
474  */
475 
476 #define GMLNODEWIDTH 120.0
477 #define GMLNODEHEIGTH 30.0
478 #define GMLFONTSIZE 13
479 #define GMLNODETYPE "rectangle"
480 #define GMLNODEFILLCOLOR "#ff0000"
481 #define GMLEDGECOLOR "black"
482 #define GMLNODEBORDERCOLOR "#000000"
483 
484 
485 /** writes a node section to the given graph file */
487  FILE* file, /**< file to write to */
488  unsigned int id, /**< id of the node */
489  const char* label, /**< label of the node */
490  const char* nodetype, /**< type of the node, or NULL */
491  const char* fillcolor, /**< color of the node's interior, or NULL */
492  const char* bordercolor /**< color of the node's border, or NULL */
493  )
494 {
495  assert(file != NULL);
496  assert(label != NULL);
497 
498  fprintf(file, " node\n");
499  fprintf(file, " [\n");
500  fprintf(file, " id %u\n", id);
501  fprintf(file, " label \"%s\"\n", label);
502  fprintf(file, " graphics\n");
503  fprintf(file, " [\n");
504  fprintf(file, " w %g\n", GMLNODEWIDTH);
505  fprintf(file, " h %g\n", GMLNODEHEIGTH);
506 
507  if( nodetype != NULL )
508  fprintf(file, " type \"%s\"\n", nodetype);
509  else
510  fprintf(file, " type \"%s\"\n", GMLNODETYPE);
511 
512  if( fillcolor != NULL )
513  fprintf(file, " fill \"%s\"\n", fillcolor);
514  else
515  fprintf(file, " fill \"%s\"\n", GMLNODEFILLCOLOR);
516 
517  if( bordercolor != NULL )
518  fprintf(file, " outline \"%s\"\n", bordercolor);
519  else
520  fprintf(file, " outline \"%s\"\n", GMLNODEBORDERCOLOR);
521 
522  fprintf(file, " ]\n");
523  fprintf(file, " LabelGraphics\n");
524  fprintf(file, " [\n");
525  fprintf(file, " text \"%s\"\n", label);
526  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
527  fprintf(file, " fontName \"Dialog\"\n");
528  fprintf(file, " anchor \"c\"\n");
529  fprintf(file, " ]\n");
530  fprintf(file, " ]\n");
531 }
532 
533 /** writes a node section including weight to the given graph file */
535  FILE* file, /**< file to write to */
536  unsigned int id, /**< id of the node */
537  const char* label, /**< label of the node */
538  const char* nodetype, /**< type of the node, or NULL */
539  const char* fillcolor, /**< color of the node's interior, or NULL */
540  const char* bordercolor, /**< color of the node's border, or NULL */
541  SCIP_Real weight /**< weight of node */
542  )
543 {
544  assert(file != NULL);
545  assert(label != NULL);
546 
547  fprintf(file, " node\n");
548  fprintf(file, " [\n");
549  fprintf(file, " id %u\n", id);
550  fprintf(file, " label \"%s\"\n", label);
551  fprintf(file, " weight %g\n", weight);
552  fprintf(file, " graphics\n");
553  fprintf(file, " [\n");
554  fprintf(file, " w %g\n", GMLNODEWIDTH);
555  fprintf(file, " h %g\n", GMLNODEHEIGTH);
556 
557  if( nodetype != NULL )
558  fprintf(file, " type \"%s\"\n", nodetype);
559  else
560  fprintf(file, " type \"%s\"\n", GMLNODETYPE);
561 
562  if( fillcolor != NULL )
563  fprintf(file, " fill \"%s\"\n", fillcolor);
564  else
565  fprintf(file, " fill \"%s\"\n", GMLNODEFILLCOLOR);
566 
567  if( bordercolor != NULL )
568  fprintf(file, " outline \"%s\"\n", bordercolor);
569  else
570  fprintf(file, " outline \"%s\"\n", GMLNODEBORDERCOLOR);
571 
572  fprintf(file, " ]\n");
573  fprintf(file, " LabelGraphics\n");
574  fprintf(file, " [\n");
575  fprintf(file, " text \"%s\"\n", label);
576  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
577  fprintf(file, " fontName \"Dialog\"\n");
578  fprintf(file, " anchor \"c\"\n");
579  fprintf(file, " ]\n");
580  fprintf(file, " ]\n");
581 }
582 
583 /** writes an edge section to the given graph file */
585  FILE* file, /**< file to write to */
586  unsigned int source, /**< source node id of the node */
587  unsigned int target, /**< target node id of the edge */
588  const char* label, /**< label of the edge, or NULL */
589  const char* color /**< color of the edge, or NULL */
590  )
591 {
592  assert(file != NULL);
593 
594  fprintf(file, " edge\n");
595  fprintf(file, " [\n");
596  fprintf(file, " source %u\n", source);
597  fprintf(file, " target %u\n", target);
598 
599  if( label != NULL)
600  fprintf(file, " label \"%s\"\n", label);
601 
602  fprintf(file, " graphics\n");
603  fprintf(file, " [\n");
604 
605  if( color != NULL )
606  fprintf(file, " fill \"%s\"\n", color);
607  else
608  fprintf(file, " fill \"%s\"\n", GMLEDGECOLOR);
609 
610  /* fprintf(file, " arrow \"both\"\n"); */
611  fprintf(file, " ]\n");
612 
613  if( label != NULL)
614  {
615  fprintf(file, " LabelGraphics\n");
616  fprintf(file, " [\n");
617  fprintf(file, " text \"%s\"\n", label);
618  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
619  fprintf(file, " fontName \"Dialog\"\n");
620  fprintf(file, " anchor \"c\"\n");
621  fprintf(file, " ]\n");
622  }
623 
624  fprintf(file, " ]\n");
625 }
626 
627 /** writes an arc section to the given graph file */
629  FILE* file, /**< file to write to */
630  unsigned int source, /**< source node id of the node */
631  unsigned int target, /**< target node id of the edge */
632  const char* label, /**< label of the edge, or NULL */
633  const char* color /**< color of the edge, or NULL */
634  )
635 {
636  assert(file != NULL);
637 
638  fprintf(file, " edge\n");
639  fprintf(file, " [\n");
640  fprintf(file, " source %u\n", source);
641  fprintf(file, " target %u\n", target);
642 
643  if( label != NULL)
644  fprintf(file, " label \"%s\"\n", label);
645 
646  fprintf(file, " graphics\n");
647  fprintf(file, " [\n");
648 
649  if( color != NULL )
650  fprintf(file, " fill \"%s\"\n", color);
651  else
652  fprintf(file, " fill \"%s\"\n", GMLEDGECOLOR);
653 
654  fprintf(file, " targetArrow \"standard\"\n");
655  fprintf(file, " ]\n");
656 
657  if( label != NULL)
658  {
659  fprintf(file, " LabelGraphics\n");
660  fprintf(file, " [\n");
661  fprintf(file, " text \"%s\"\n", label);
662  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
663  fprintf(file, " fontName \"Dialog\"\n");
664  fprintf(file, " anchor \"c\"\n");
665  fprintf(file, " ]\n");
666  }
667 
668  fprintf(file, " ]\n");
669 }
670 
671 /** writes the starting line to a GML graph file, does not open a file */
673  FILE* file, /**< file to write to */
674  SCIP_Bool directed /**< is the graph directed */
675  )
676 {
677  assert(file != NULL);
678 
679  fprintf(file, "graph\n");
680  fprintf(file, "[\n");
681  fprintf(file, " hierarchic 1\n");
682 
683  if( directed )
684  fprintf(file, " directed 1\n");
685 }
686 
687 /** writes the ending lines to a GML graph file, does not close a file */
689  FILE* file /**< file to close */
690  )
691 {
692  assert(file != NULL);
693 
694  fprintf(file, "]\n");
695 }
696 
697 
698 /*
699  * Sparse solution
700  */
701 
702 /** creates a sparse solution */
704  SCIP_SPARSESOL** sparsesol, /**< pointer to store the created sparse solution */
705  SCIP_VAR** vars, /**< variables in the sparse solution, must not contain continuous
706  * variables
707  */
708  int nvars, /**< number of variables to store, size of the lower and upper bound
709  * arrays
710  */
711  SCIP_Bool cleared /**< should the lower and upper bound arrays be cleared (entries set to
712  * 0)
713  */
714  )
715 {
716  assert(sparsesol != NULL);
717  assert(vars != NULL);
718  assert(nvars >= 0);
719 
720  SCIP_ALLOC( BMSallocMemory(sparsesol) );
721 
722 #ifndef NDEBUG
723  {
724  int v;
725 
726  for( v = nvars - 1; v >= 0; --v )
727  {
728  assert(vars[v] != NULL);
729  /* assert(SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS); */
730  }
731  }
732 #endif
733 
734  /* copy variables */
735  SCIP_ALLOC( BMSduplicateMemoryArray(&((*sparsesol)->vars), vars, nvars) );
736 
737  /* create bound arrays */
738  if( cleared )
739  {
740  SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->lbvalues), nvars) );
741  SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->ubvalues), nvars) );
742  }
743  else
744  {
745  SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->lbvalues), nvars) );
746  SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->ubvalues), nvars) );
747  }
748 
749  (*sparsesol)->nvars = nvars;
750 
751  return SCIP_OKAY;
752 }
753 
754 /** frees sparse solution */
756  SCIP_SPARSESOL** sparsesol /**< pointer to a sparse solution */
757  )
758 {
759  assert(sparsesol != NULL);
760  assert(*sparsesol != NULL);
761 
762  BMSfreeMemoryArray(&((*sparsesol)->vars));
763  BMSfreeMemoryArray(&((*sparsesol)->ubvalues));
764  BMSfreeMemoryArray(&((*sparsesol)->lbvalues));
765  BMSfreeMemory(sparsesol);
766 }
767 
768 /** returns the variables stored in the given sparse solution */
770  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
771  )
772 {
773  assert(sparsesol != NULL);
774 
775  return sparsesol->vars;
776 }
777 
778 /** returns the number of variables stored in the given sparse solution */
780  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
781  )
782 {
783  assert(sparsesol != NULL);
784 
785  return sparsesol->nvars;
786 }
787 
788 /** returns the lower bound array for all variables for a given sparse solution */
790  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
791  )
792 {
793  assert(sparsesol != NULL);
794 
795  return sparsesol->lbvalues;
796 }
797 
798 /** returns the upper bound array for all variables for a given sparse solution */
800  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
801  )
802 {
803  assert(sparsesol != NULL);
804 
805  return sparsesol->ubvalues;
806 }
807 
808 /** constructs the first solution of sparse solution (all variables are set to their lower bound value */
810  SCIP_SPARSESOL* sparsesol, /**< sparse solutions */
811  SCIP_Longint* sol, /**< array to store the first solution */
812  int nvars /**< number of variables */
813  )
814 {
815  SCIP_Longint* lbvalues;
816  int v;
817 
818  assert(sparsesol != NULL);
819  assert(sol != NULL);
820  assert(nvars == SCIPsparseSolGetNVars(sparsesol));
821 
822  lbvalues = SCIPsparseSolGetLbs(sparsesol);
823  assert(lbvalues != NULL);
824 
825  /* copy the lower bounds */
826  for( v = 0; v < nvars; ++v )
827  sol[v] = lbvalues[v];
828 }
829 
830 
831 /** constructs the next solution of the sparse solution and return whether there was one more or not */
833  SCIP_SPARSESOL* sparsesol, /**< sparse solutions */
834  SCIP_Longint* sol, /**< current solution array which get changed to the next solution */
835  int nvars /**< number of variables */
836  )
837 {
838  SCIP_Longint* lbvalues;
839  SCIP_Longint* ubvalues;
840  SCIP_Longint lbvalue;
841  SCIP_Longint ubvalue;
842  SCIP_Bool singular;
843  SCIP_Bool carryflag;
844  int v;
845 
846  assert(sparsesol != NULL);
847  assert(sol != NULL);
848 
849  if( nvars == 0 )
850  return FALSE;
851 
852  assert(nvars > 0);
853  assert(nvars == SCIPsparseSolGetNVars(sparsesol));
854 
855  lbvalues = SCIPsparseSolGetLbs(sparsesol);
856  ubvalues = SCIPsparseSolGetUbs(sparsesol);
857  assert(lbvalues != NULL);
858  assert(ubvalues != NULL);
859 
860  singular = TRUE;
861  carryflag = FALSE;
862 
863  for( v = 0; v < nvars; ++v )
864  {
865  lbvalue = lbvalues[v];
866  ubvalue = ubvalues[v];
867 
868  if( lbvalue < ubvalue )
869  {
870  singular = FALSE;
871 
872  if( carryflag == FALSE )
873  {
874  if( sol[v] < ubvalue )
875  {
876  sol[v]++;
877  break;
878  }
879  else
880  {
881  /* in the last solution the variables v was set to its upper bound value */
882  assert(sol[v] == ubvalue);
883  sol[v] = lbvalue;
884  carryflag = TRUE;
885  }
886  }
887  else
888  {
889  if( sol[v] < ubvalue )
890  {
891  sol[v]++;
892  carryflag = FALSE;
893  break;
894  }
895  else
896  {
897  assert(sol[v] == ubvalue);
898  sol[v] = lbvalue;
899  }
900  }
901  }
902  }
903 
904  return (!carryflag && !singular);
905 }
906 
907 
908 /*
909  * Queue
910  */
911 
912 /** resizes element memory to hold at least the given number of elements */
913 static
915  SCIP_QUEUE* queue, /**< pointer to a queue */
916  int minsize /**< minimal number of storable elements */
917  )
918 {
919  assert(queue != NULL);
920  assert(minsize > 0);
921 
922  if( minsize <= queue->size )
923  return SCIP_OKAY;
924 
925  queue->size = MAX(minsize, (int)(queue->size * queue->sizefac));
926  SCIP_ALLOC( BMSreallocMemoryArray(&queue->slots, queue->size) );
927 
928  return SCIP_OKAY;
929 }
930 
931 
932 /** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */
934  SCIP_QUEUE** queue, /**< pointer to the new queue */
935  int initsize, /**< initial number of available element slots */
936  SCIP_Real sizefac /**< memory growing factor applied, if more element slots are needed */
937  )
938 {
939  assert(queue != NULL);
940 
941  initsize = MAX(1, initsize);
942  sizefac = MAX(1.0, sizefac);
943 
944  SCIP_ALLOC( BMSallocMemory(queue) );
945  (*queue)->firstfree = 0;
946  (*queue)->firstused = -1;
947  (*queue)->size = 0;
948  (*queue)->sizefac = sizefac;
949  (*queue)->slots = NULL;
950 
951  SCIP_CALL( queueResize(*queue, initsize) );
952 
953  return SCIP_OKAY;
954 }
955 
956 /** frees queue, but not the data elements themselves */
958  SCIP_QUEUE** queue /**< pointer to a queue */
959  )
960 {
961  assert(queue != NULL);
962 
963  BMSfreeMemoryArray(&(*queue)->slots);
964  BMSfreeMemory(queue);
965 }
966 
967 /** clears the queue, but doesn't free the data elements themselves */
969  SCIP_QUEUE* queue /**< queue */
970  )
971 {
972  assert(queue != NULL);
973 
974  queue->firstfree = 0;
975  queue->firstused = -1;
976 }
977 
978 /** reallocates slots if queue is necessary */
979 static
981  SCIP_QUEUE* queue /**< queue */
982  )
983 {
984  if( queue->firstfree == queue->firstused )
985  {
986  int sizediff;
987  int oldsize = queue->size;
988 
989  SCIP_CALL( queueResize(queue, queue->size+1) );
990  assert(oldsize < queue->size);
991 
992  sizediff = queue->size - oldsize;
993 
994  /* move the used memory at the slots to the end */
995  BMSmoveMemoryArray(&(queue->slots[queue->firstused + sizediff]), &(queue->slots[queue->firstused]), oldsize - queue->firstused); /*lint !e866*/
996  queue->firstused += sizediff;
997  }
998  assert(queue->firstfree != queue->firstused);
999 
1000  return SCIP_OKAY;
1001 }
1002 
1003 /** checks and adjusts marker of first free and first used slot */
1004 static
1006  SCIP_QUEUE* queue /**< queue */
1007  )
1008 {
1009  /* if we saved the value at the last position we need to reset the firstfree position */
1010  if( queue->firstfree == queue->size )
1011  queue->firstfree = 0;
1012 
1013  /* if a first element was added, we need to update the firstused counter */
1014  if( queue->firstused == -1 )
1015  queue->firstused = 0;
1016 }
1017 
1018 /** inserts pointer element at the end of the queue */
1020  SCIP_QUEUE* queue, /**< queue */
1021  void* elem /**< element to be inserted */
1022  )
1023 {
1024  assert(queue != NULL);
1025  assert(queue->slots != NULL);
1026  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1027  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1028  assert(queue->firstused > -1 || queue->firstfree == 0);
1029  assert(elem != NULL);
1030 
1031  /* check allocated memory */
1032  SCIP_CALL( queueCheckSize(queue) );
1033 
1034  /* insert element at the first free slot */
1035  queue->slots[queue->firstfree].ptr = elem;
1036  ++(queue->firstfree);
1037 
1038  /* check and adjust marker */
1039  queueCheckMarker(queue);
1040 
1041  return SCIP_OKAY;
1042 }
1043 
1044 /** inserts unsigned integer element at the end of the queue */
1046  SCIP_QUEUE* queue, /**< queue */
1047  unsigned int elem /**< element to be inserted */
1048  )
1049 {
1050  assert(queue != NULL);
1051  assert(queue->slots != NULL);
1052  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1053  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1054  assert(queue->firstused > -1 || queue->firstfree == 0);
1055 
1056  /* check allocated memory */
1057  SCIP_CALL( queueCheckSize(queue) );
1058 
1059  /* insert element at the first free slot */
1060  queue->slots[queue->firstfree].uinteger = elem;
1061  ++(queue->firstfree);
1062 
1063  /* check and adjust marker */
1064  queueCheckMarker(queue);
1065 
1066  return SCIP_OKAY;
1067 }
1068 
1069 /** removes and returns the first pointer element of the queue, or NULL if no element exists */
1071  SCIP_QUEUE* queue /**< queue */
1072  )
1073 {
1074  int pos;
1075 
1076  assert(queue != NULL);
1077  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1078  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1079  assert(queue->firstused > -1 || queue->firstfree == 0);
1080 
1081  if( queue->firstused == -1 )
1082  return NULL;
1083 
1084  assert(queue->slots != NULL);
1085 
1086  pos = queue->firstused;
1087  ++(queue->firstused);
1088 
1089  /* if we removed the value at the last position we need to reset the firstused position */
1090  if( queue->firstused == queue->size )
1091  queue->firstused = 0;
1092 
1093  /* if we reached the first free position we can reset both, firstused and firstused, positions */
1094  if( queue->firstused == queue->firstfree )
1095  {
1096  queue->firstused = -1;
1097  queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1098  }
1099 
1100  return (queue->slots[pos].ptr);
1101 }
1102 
1103 /** removes and returns the first unsigned integer element of the queue, or UINT_MAX if no element exists */
1104 unsigned int SCIPqueueRemoveUInt(
1105  SCIP_QUEUE* queue /**< queue */
1106  )
1107 {
1108  int pos;
1109 
1110  assert(queue != NULL);
1111  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1112  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1113  assert(queue->firstused > -1 || queue->firstfree == 0);
1114 
1115  if( queue->firstused == -1 )
1116  return UINT_MAX;
1117 
1118  assert(queue->slots != NULL);
1119 
1120  pos = queue->firstused;
1121  ++(queue->firstused);
1122 
1123  /* if we removed the value at the last position we need to reset the firstused position */
1124  if( queue->firstused == queue->size )
1125  queue->firstused = 0;
1126 
1127  /* if we reached the first free position we can reset both, firstused and firstused, positions */
1128  if( queue->firstused == queue->firstfree )
1129  {
1130  queue->firstused = -1;
1131  queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1132  }
1133 
1134  return (queue->slots[pos].uinteger);
1135 }
1136 
1137 /** returns the first element of the queue without removing it, or NULL if no element exists */
1139  SCIP_QUEUE* queue /**< queue */
1140  )
1141 {
1142  assert(queue != NULL);
1143  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1144  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1145  assert(queue->firstused > -1 || queue->firstfree == 0);
1146 
1147  if( queue->firstused == -1 )
1148  return NULL;
1149 
1150  assert(queue->slots != NULL);
1151 
1152  return queue->slots[queue->firstused].ptr;
1153 }
1154 
1155 /** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */
1156 unsigned int SCIPqueueFirstUInt(
1157  SCIP_QUEUE* queue /**< queue */
1158  )
1159 {
1160  assert(queue != NULL);
1161  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1162  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1163  assert(queue->firstused > -1 || queue->firstfree == 0);
1164 
1165  if( queue->firstused == -1 )
1166  return UINT_MAX;
1167 
1168  assert(queue->slots != NULL);
1169 
1170  return queue->slots[queue->firstused].uinteger;
1171 }
1172 
1173 /** returns whether the queue is empty */
1175  SCIP_QUEUE* queue /**< queue */
1176  )
1177 {
1178  assert(queue != NULL);
1179  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1180  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1181  assert(queue->firstused > -1 || queue->firstfree == 0);
1182 
1183  return (queue->firstused == -1);
1184 }
1185 
1186 /** returns the number of elements in the queue */
1188  SCIP_QUEUE* queue /**< queue */
1189  )
1190 {
1191  assert(queue != NULL);
1192  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1193  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1194  assert(queue->firstused > -1 || queue->firstfree == 0);
1195 
1196  if( queue->firstused == -1 )
1197  return 0;
1198  else if( queue->firstused < queue->firstfree )
1199  return queue->firstfree - queue->firstused;
1200  else if( queue->firstused == queue->firstfree )
1201  return queue->size;
1202  else
1203  return queue->firstfree + (queue->size - queue->firstused);
1204 }
1205 
1206 
1207 /*
1208  * Priority Queue
1209  */
1210 
1211 #define PQ_PARENT(q) (((q)+1)/2-1)
1212 #define PQ_LEFTCHILD(p) (2*(p)+1)
1213 #define PQ_RIGHTCHILD(p) (2*(p)+2)
1214 
1215 
1216 /** resizes element memory to hold at least the given number of elements */
1217 static
1219  SCIP_PQUEUE* pqueue, /**< pointer to a priority queue */
1220  int minsize /**< minimal number of storable elements */
1221  )
1222 {
1223  assert(pqueue != NULL);
1224 
1225  if( minsize <= pqueue->size )
1226  return SCIP_OKAY;
1227 
1228  pqueue->size = MAX(minsize, (int)(pqueue->size * pqueue->sizefac));
1229  SCIP_ALLOC( BMSreallocMemoryArray(&pqueue->slots, pqueue->size) );
1230 
1231  return SCIP_OKAY;
1232 }
1233 
1234 /** creates priority queue */
1236  SCIP_PQUEUE** pqueue, /**< pointer to a priority queue */
1237  int initsize, /**< initial number of available element slots */
1238  SCIP_Real sizefac, /**< memory growing factor applied, if more element slots are needed */
1239  SCIP_DECL_SORTPTRCOMP((*ptrcomp)), /**< data element comparator */
1240  SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) /**< callback to act on position change of elem in priority queue, or NULL */
1241  )
1242 {
1243  assert(pqueue != NULL);
1244  assert(ptrcomp != NULL);
1245 
1246  initsize = MAX(1, initsize);
1247  sizefac = MAX(1.0, sizefac);
1248 
1249  SCIP_ALLOC( BMSallocMemory(pqueue) );
1250  (*pqueue)->len = 0;
1251  (*pqueue)->size = 0;
1252  (*pqueue)->sizefac = sizefac;
1253  (*pqueue)->slots = NULL;
1254  (*pqueue)->ptrcomp = ptrcomp;
1255  (*pqueue)->elemchgpos = elemchgpos;
1256  SCIP_CALL( pqueueResize(*pqueue, initsize) );
1257 
1258  return SCIP_OKAY;
1259 }
1260 
1261 /** frees priority queue, but not the data elements themselves */
1263  SCIP_PQUEUE** pqueue /**< pointer to a priority queue */
1264  )
1265 {
1266  assert(pqueue != NULL);
1267 
1268  BMSfreeMemoryArray(&(*pqueue)->slots);
1269  BMSfreeMemory(pqueue);
1270 }
1271 
1272 /** clears the priority queue, but doesn't free the data elements themselves */
1274  SCIP_PQUEUE* pqueue /**< priority queue */
1275  )
1276 {
1277  assert(pqueue != NULL);
1278 
1279  pqueue->len = 0;
1280 }
1281 
1282 /** assign element to new slot in priority queue */
1283 static
1285  SCIP_PQUEUE* pqueue, /**< priority queue */
1286  void* elem, /**< element whose position changes */
1287  int oldpos, /**< old position or -1 if elem is newly inserted */
1288  int newpos /**< new position */
1289  )
1290 {
1291  pqueue->slots[newpos] = elem;
1292 
1293  /* act on position change */
1294  if( pqueue->elemchgpos != NULL )
1295  {
1296  pqueue->elemchgpos(elem, oldpos, newpos);
1297  }
1298 }
1299 
1300 #ifdef SCIP_MORE_DEBUG
1301 /** ensure that the priority queue still has the heap property */
1302 static
1303 SCIP_Bool pqueueHasHeapProperty(
1304  SCIP_PQUEUE* pqueue /**< priority queue */
1305  )
1306 {
1307  int i;
1308 
1309  if( SCIPpqueueNElems(pqueue) == 0 )
1310  return TRUE;
1311 
1312  /* check local heap property between parents and children */
1313  for( i = 0; i < SCIPpqueueNElems(pqueue); ++i )
1314  {
1315  if( i > 0 && pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[PQ_PARENT(i)]) < 0 )
1316  return FALSE;
1317  if( i < PQ_PARENT(SCIPpqueueNElems(pqueue)) )
1318  {
1319  int leftchild = PQ_LEFTCHILD(i);
1320  int rightchild = PQ_RIGHTCHILD(i);
1321  assert(leftchild < SCIPpqueueNElems(pqueue));
1322  assert(rightchild <= SCIPpqueueNElems(pqueue));
1323  if( pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[leftchild]) > 0 )
1324  return FALSE;
1325  if( rightchild < SCIPpqueueNElems(pqueue) && pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[rightchild]) > 0)
1326  return FALSE;
1327  }
1328  }
1329  return TRUE;
1330 }
1331 #endif
1332 
1333 /** inserts element into priority queue */
1335  SCIP_PQUEUE* pqueue, /**< priority queue */
1336  void* elem /**< element to be inserted */
1337  )
1338 {
1339  int pos;
1340  int parentpos;
1341 
1342  assert(pqueue != NULL);
1343  assert(pqueue->len >= 0);
1344  assert(elem != NULL);
1345 
1346  SCIP_CALL( pqueueResize(pqueue, pqueue->len+1) );
1347 
1348  /* insert element as leaf in the tree, move it towards the root as long it is better than its parent */
1349  pos = pqueue->len;
1350  pqueue->len++;
1351  parentpos = PQ_PARENT(pos);
1352  while( pos > 0 && (*pqueue->ptrcomp)(elem, pqueue->slots[parentpos]) < 0 )
1353  {
1354  assert((*pqueue->ptrcomp)(pqueue->slots[parentpos], elem) >= 0);
1355  pqueueElemChgPos(pqueue, pqueue->slots[parentpos], parentpos, pos);
1356 
1357  pos = parentpos;
1358  parentpos = PQ_PARENT(pos);
1359  }
1360 
1361  /* insert element at the found position */
1362  pqueueElemChgPos(pqueue, elem, -1, pos);
1363 
1364 #ifdef SCIP_MORE_DEBUG
1365  assert(pqueueHasHeapProperty(pqueue));
1366 #endif
1367 
1368  return SCIP_OKAY;
1369 }
1370 
1371 
1372 /** delete element at specified position, maintaining the heap property */
1374  SCIP_PQUEUE* pqueue, /**< priority queue */
1375  int pos /**< position of element that should be deleted */
1376  )
1377 {
1378  void* last;
1379 
1380  assert(pqueue != NULL);
1381  assert(pos >= 0);
1382  assert(pos < SCIPpqueueNElems(pqueue));
1383 
1384  /* remove element at specified position of the tree, move the better child to its parents position until the last element
1385  * of the queue could be placed in the empty slot
1386  */
1387  pqueue->len--;
1388 
1389  /* everything in place */
1390  if( pos == pqueue->len )
1391  return;
1392 
1393  last = pqueue->slots[pqueue->len];
1394 
1395  /* last element is brought to pos. it may now violate the heap property compared to its parent, or to its children.
1396  * In the first case, move it up, otherwise, move it down.
1397  */
1398  while( pos > 0 && (*pqueue->ptrcomp)(last, pqueue->slots[PQ_PARENT(pos)]) < 0 )
1399  {
1400  pqueueElemChgPos(pqueue, pqueue->slots[PQ_PARENT(pos)], PQ_PARENT(pos), pos);
1401  pos = PQ_PARENT(pos);
1402  }
1403 
1404  while( pos <= PQ_PARENT(pqueue->len-1) )
1405  {
1406  int childpos = PQ_LEFTCHILD(pos);
1407  int brotherpos = PQ_RIGHTCHILD(pos);
1408 
1409  /* determine better of the two children */
1410  if( brotherpos < pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
1411  childpos = brotherpos;
1412 
1413  if( (*pqueue->ptrcomp)(last, pqueue->slots[childpos]) <= 0 )
1414  break;
1415 
1416  /* move better element from childpos to pos */
1417  pqueueElemChgPos(pqueue, pqueue->slots[childpos], childpos, pos);
1418 
1419  pos = childpos;
1420  }
1421 
1422  /* pos must point into a valid position */
1423  assert(pos <= pqueue->len - 1);
1424 
1425  pqueueElemChgPos(pqueue, last, pqueue->len, pos);
1426 
1427 #ifdef SCIP_MORE_DEBUG
1428  assert(pqueueHasHeapProperty(pqueue));
1429 #endif
1430 }
1431 
1432 /** removes and returns best element from the priority queue */
1434  SCIP_PQUEUE* pqueue /**< priority queue */
1435  )
1436 {
1437  void* root;
1438 
1439  assert(pqueue != NULL);
1440  assert(pqueue->len >= 0);
1441 
1442  if( pqueue->len == 0 )
1443  return NULL;
1444 
1445  root = pqueue->slots[0];
1446 
1447  SCIPpqueueDelPos(pqueue, 0);
1448 
1449  return root;
1450 }
1451 
1452 /** returns the best element of the queue without removing it */
1454  SCIP_PQUEUE* pqueue /**< priority queue */
1455  )
1456 {
1457  assert(pqueue != NULL);
1458  assert(pqueue->len >= 0);
1459 
1460  if( pqueue->len == 0 )
1461  return NULL;
1462 
1463  return pqueue->slots[0];
1464 }
1465 
1466 /** returns the number of elements in the queue */
1468  SCIP_PQUEUE* pqueue /**< priority queue */
1469  )
1470 {
1471  assert(pqueue != NULL);
1472  assert(pqueue->len >= 0);
1473 
1474  return pqueue->len;
1475 }
1476 
1477 /** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */
1479  SCIP_PQUEUE* pqueue /**< priority queue */
1480  )
1481 {
1482  assert(pqueue != NULL);
1483  assert(pqueue->len >= 0);
1484 
1485  return pqueue->slots;
1486 }
1487 
1488 /** return the position of @p elem in the priority queue, or -1 if element is not found */
1490  SCIP_PQUEUE* pqueue, /**< priority queue */
1491  void* elem /**< element to be inserted */
1492  )
1493 {
1494  int pos = -1;
1495 
1496  while( ++pos < SCIPpqueueNElems(pqueue) )
1497  {
1498  if( pqueue->slots[pos] == elem )
1499  return pos;
1500  }
1501 
1502  return -1;
1503 }
1504 
1505 
1506 
1507 
1508 /*
1509  * Hash Table
1510  */
1511 
1512 /** table of some prime numbers */
1513 static int primetable[] = {
1514  2,
1515  7,
1516  19,
1517  31,
1518  59,
1519  227,
1520  617,
1521  1523,
1522  3547,
1523  8011,
1524  17707,
1525  38723,
1526  83833,
1527  180317,
1528  385897,
1529  821411,
1530  1742369,
1531  3680893,
1532  5693959,
1533  7753849,
1534  9849703,
1535  11973277,
1536  14121853,
1537  17643961,
1538  24273817,
1539  32452843,
1540  49979687,
1541  67867967,
1542  86028121,
1543  104395301,
1544  122949823,
1545  141650939,
1546  160481183,
1547  179424673,
1548  198491317,
1549  217645177,
1550  256203161,
1551  314606869,
1552  373587883,
1553  433024223,
1554  492876847,
1555  553105243,
1556  613651349,
1557  694847533,
1558  756065159,
1559  817504243,
1560  879190747,
1561  941083981,
1562  982451653,
1563  INT_MAX
1564 };
1565 static const int primetablesize = sizeof(primetable)/sizeof(int);
1566 
1567 /** simple and fast 2-universal hash function using multiply and shift */
1568 static
1569 uint32_t hashvalue(
1570  uint64_t input /**< key value */
1571  )
1572 {
1573  return ( (uint32_t) ((UINT64_C(0x9e3779b97f4a7c15) * input)>>32) ) | 1u;
1574 }
1575 
1576 /** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
1578  int minsize /**< minimal size of the hash table */
1579  )
1580 {
1581  int pos;
1582 
1583  (void) SCIPsortedvecFindInt(primetable, minsize, primetablesize, &pos);
1584  assert(0 <= pos && pos < primetablesize);
1585 
1586  return primetable[pos];
1587 }
1588 
1589 /** appends element to the multihash list */
1590 static
1592  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to hash list */
1593  BMS_BLKMEM* blkmem, /**< block memory */
1594  void* element /**< element to append to the list */
1595  )
1596 {
1597  SCIP_MULTIHASHLIST* newlist;
1598 
1599  assert(multihashlist != NULL);
1600  assert(blkmem != NULL);
1601  assert(element != NULL);
1602 
1603  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &newlist) );
1604  newlist->element = element;
1605  newlist->next = *multihashlist;
1606  *multihashlist = newlist;
1607 
1608  return SCIP_OKAY;
1609 }
1610 
1611 /** frees a multihash list entry and all its successors */
1612 static
1614  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to multihash list to free */
1615  BMS_BLKMEM* blkmem /**< block memory */
1616  )
1617 {
1618  SCIP_MULTIHASHLIST* list;
1619  SCIP_MULTIHASHLIST* nextlist;
1620 
1621  assert(multihashlist != NULL);
1622  assert(blkmem != NULL);
1623 
1624  list = *multihashlist;
1625  while( list != NULL )
1626  {
1627  nextlist = list->next;
1628  BMSfreeBlockMemory(blkmem, &list);
1629  list = nextlist;
1630  }
1631 
1632  *multihashlist = NULL;
1633 }
1634 
1635 /** finds multihash list entry pointing to element with given key in the multihash list, returns NULL if not found */
1636 static
1638  SCIP_MULTIHASHLIST* multihashlist, /**< multihash list */
1639  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1640  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1641  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1642  void* userptr, /**< user pointer */
1643  uint64_t keyval, /**< hash value of key */
1644  void* key /**< key to retrieve */
1645  )
1646 {
1647  uint64_t currentkeyval;
1648  void* currentkey;
1649 
1650  assert(hashkeyeq != NULL);
1651  assert(key != NULL);
1652 
1653  while( multihashlist != NULL )
1654  {
1655  currentkey = hashgetkey(userptr, multihashlist->element);
1656  currentkeyval = hashkeyval(userptr, currentkey);
1657  if( currentkeyval == keyval && hashkeyeq(userptr, currentkey, key) )
1658  return multihashlist;
1659 
1660  multihashlist = multihashlist->next;
1661  }
1662 
1663  return NULL;
1664 }
1665 
1666 /** retrieves element with given key from the multihash list, or NULL */
1667 static
1669  SCIP_MULTIHASHLIST* multihashlist, /**< hash list */
1670  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1671  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1672  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1673  void* userptr, /**< user pointer */
1674  uint64_t keyval, /**< hash value of key */
1675  void* key /**< key to retrieve */
1676  )
1677 {
1679 
1680  /* find hash list entry */
1681  h = multihashlistFind(multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1682 
1683  /* return element */
1684  if( h != NULL )
1685  {
1686 #ifndef NDEBUG
1687  SCIP_MULTIHASHLIST* h2;
1688 
1689  h2 = multihashlistFind(h->next, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1690 
1691  if( h2 != NULL )
1692  {
1693  void* key1;
1694  void* key2;
1695 
1696  key1 = hashgetkey(userptr, h->element);
1697  key2 = hashgetkey(userptr, h2->element);
1698  assert(hashkeyval(userptr, key1) == hashkeyval(userptr, key2));
1699 
1700  if( hashkeyeq(userptr, key1, key2) )
1701  {
1702  SCIPerrorMessage("WARNING: hashkey with same value exists multiple times (e.g. duplicate constraint/variable names), so the return value is maybe not correct\n");
1703  }
1704  }
1705 #endif
1706 
1707  return h->element;
1708  }
1709  else
1710  return NULL;
1711 }
1712 
1713 
1714 /** retrieves element with given key from the multihash list, or NULL
1715  * returns pointer to multihash table list entry
1716  */
1717 static
1719  SCIP_MULTIHASHLIST** multihashlist, /**< on input: hash list to search; on exit: hash list entry corresponding
1720  * to element after retrieved one, or NULL */
1721  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1722  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1723  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1724  void* userptr, /**< user pointer */
1725  uint64_t keyval, /**< hash value of key */
1726  void* key /**< key to retrieve */
1727  )
1728 {
1730 
1731  assert(multihashlist != NULL);
1732 
1733  /* find hash list entry */
1734  h = multihashlistFind(*multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1735 
1736  /* return element */
1737  if( h != NULL )
1738  {
1739  *multihashlist = h->next;
1740 
1741  return h->element;
1742  }
1743 
1744  *multihashlist = NULL;
1745 
1746  return NULL;
1747 }
1748 
1749 /** removes element from the multihash list */
1750 static
1752  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to hash list */
1753  BMS_BLKMEM* blkmem, /**< block memory */
1754  void* element /**< element to remove from the list */
1755  )
1756 {
1757  SCIP_MULTIHASHLIST* nextlist;
1758 
1759  assert(multihashlist != NULL);
1760  assert(blkmem != NULL);
1761  assert(element != NULL);
1762 
1763  while( *multihashlist != NULL && (*multihashlist)->element != element )
1764  multihashlist = &(*multihashlist)->next;
1765 
1766  if( *multihashlist != NULL )
1767  {
1768  nextlist = (*multihashlist)->next;
1769  BMSfreeBlockMemory(blkmem, multihashlist);
1770  *multihashlist = nextlist;
1771 
1772  return TRUE;
1773  }
1774 
1775  return FALSE;
1776 }
1777 
1778 #define SCIP_MULTIHASH_MAXSIZE 33554431 /* 2^25 - 1*/
1779 #define SCIP_MULTIHASH_RESIZE_PERCENTAGE 65
1780 #define SCIP_MULTIHASH_GROW_FACTOR 1.31
1781 
1782 /** resizing(increasing) the given multihash */
1783 static
1785  SCIP_MULTIHASH* multihash /**< hash table */
1786  )
1787 {
1788  SCIP_MULTIHASHLIST** newlists;
1789  SCIP_MULTIHASHLIST* multihashlist;
1790  SCIP_Longint nelements;
1791  int nnewlists;
1792  int l;
1793 
1794  assert(multihash != NULL);
1795  assert(multihash->lists != NULL);
1796  assert(multihash->nlists > 0);
1797  assert(multihash->hashgetkey != NULL);
1798  assert(multihash->hashkeyeq != NULL);
1799  assert(multihash->hashkeyval != NULL);
1800 
1801  /* get new memeory for hash table lists */
1802  nnewlists = (int) MIN((unsigned int)(multihash->nlists * SCIP_MULTIHASH_GROW_FACTOR), SCIP_MULTIHASH_MAXSIZE);
1803  nnewlists = MAX(nnewlists, multihash->nlists);
1804 
1805  SCIPdebugMessage("load = %g, nelements = %" SCIP_LONGINT_FORMAT ", nlists = %d, nnewlist = %d\n", SCIPmultihashGetLoad(multihash), multihash->nelements, multihash->nlists, nnewlists);
1806 
1807  if( nnewlists > multihash->nlists )
1808  {
1809  SCIP_Bool onlyone;
1810  void* key;
1811  uint64_t keyval;
1812  unsigned int hashval;
1813 
1814  SCIP_ALLOC( BMSallocClearBlockMemoryArray(multihash->blkmem, &newlists, nnewlists) );
1815 
1816  /* move all lists */
1817  for( l = multihash->nlists - 1; l >= 0; --l )
1818  {
1819  multihashlist = multihash->lists[l];
1820  onlyone = TRUE;
1821 
1822  /* move all elements frmm the old lists into the new lists */
1823  while( multihashlist != NULL )
1824  {
1825  /* get the hash key and its hash value */
1826  key = multihash->hashgetkey(multihash->userptr, multihashlist->element);
1827  keyval = multihash->hashkeyval(multihash->userptr, key);
1828  hashval = keyval % nnewlists; /*lint !e573*/
1829 
1830  /* if the old hash table list consists of only one entry, we still can use this old memory block instead
1831  * of creating a new one
1832  */
1833  if( multihashlist->next == NULL && onlyone )
1834  {
1835  /* the new list is also empty, we can directly copy the entry */
1836  if( newlists[hashval] == NULL )
1837  newlists[hashval] = multihashlist;
1838  /* the new list is not empty, so we need to find the first empty spot */
1839  else
1840  {
1841  SCIP_MULTIHASHLIST* lastnext = newlists[hashval];
1842  SCIP_MULTIHASHLIST* next = lastnext->next;
1843 
1844  while( next != NULL )
1845  {
1846  lastnext = next;
1847  next = next->next;
1848  }
1849 
1850  lastnext->next = multihashlist;
1851  }
1852 
1853  multihash->lists[l] = NULL;
1854  }
1855  else
1856  {
1857  /* append old element to the list at the hash position */
1858  SCIP_CALL( multihashlistAppend(&(newlists[hashval]), multihash->blkmem, multihashlist->element) );
1859  }
1860 
1861  onlyone = FALSE;
1862  multihashlist = multihashlist->next;
1863  }
1864  }
1865 
1866  /* remember number of elements */
1867  nelements = multihash->nelements;
1868  /* clear old lists */
1869  SCIPmultihashRemoveAll(multihash);
1870  /* free old lists */
1871  BMSfreeBlockMemoryArray(multihash->blkmem, &(multihash->lists), multihash->nlists);
1872 
1873  /* set new data */
1874  multihash->lists = newlists;
1875  multihash->nlists = nnewlists;
1876  multihash->nelements = nelements;
1877 
1878 #ifdef SCIP_MORE_DEBUG
1879  {
1880  SCIP_Longint sumslotsize = 0;
1881 
1882  for( l = 0; l < multihash->nlists; ++l )
1883  {
1884  multihashlist = multihash->lists[l];
1885  while( multihashlist != NULL )
1886  {
1887  sumslotsize++;
1888  multihashlist = multihashlist->next;
1889  }
1890  }
1891  assert(sumslotsize == multihash->nelements);
1892  }
1893 #endif
1894  }
1895 
1896  return SCIP_OKAY;
1897 }
1898 
1899 /** creates a multihash table */
1901  SCIP_MULTIHASH** multihash, /**< pointer to store the created multihash table */
1902  BMS_BLKMEM* blkmem, /**< block memory used to store multihash table entries */
1903  int tablesize, /**< size of the hash table */
1904  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1905  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1906  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1907  void* userptr /**< user pointer */
1908  )
1909 {
1910  /* only assert non negative to catch overflow errors
1911  * but not zeros due to integer divison
1912  */
1913  assert(tablesize >= 0);
1914  assert(multihash != NULL);
1915  assert(hashgetkey != NULL);
1916  assert(hashkeyeq != NULL);
1917  assert(hashkeyval != NULL);
1918 
1919  SCIP_ALLOC( BMSallocBlockMemory(blkmem, multihash) );
1920  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*multihash)->lists, tablesize) );
1921  (*multihash)->blkmem = blkmem;
1922  (*multihash)->nlists = tablesize;
1923  (*multihash)->hashgetkey = hashgetkey;
1924  (*multihash)->hashkeyeq = hashkeyeq;
1925  (*multihash)->hashkeyval = hashkeyval;
1926  (*multihash)->userptr = userptr;
1927  (*multihash)->nelements = 0;
1928 
1929  return SCIP_OKAY;
1930 }
1931 
1932 /** frees the multihash table */
1934  SCIP_MULTIHASH** multihash /**< pointer to the multihash table */
1935  )
1936 {
1937  int i;
1938  SCIP_MULTIHASH* table;
1939  BMS_BLKMEM* blkmem;
1940  SCIP_MULTIHASHLIST** lists;
1941 
1942  assert(multihash != NULL);
1943  assert(*multihash != NULL);
1944 
1945  table = (*multihash);
1946  blkmem = table->blkmem;
1947  lists = table->lists;
1948 
1949  /* free hash lists */
1950  for( i = table->nlists - 1; i >= 0; --i )
1951  multihashlistFree(&lists[i], blkmem);
1952 
1953  /* free main hash table data structure */
1954  BMSfreeBlockMemoryArray(blkmem, &table->lists, table->nlists);
1955  BMSfreeBlockMemory(blkmem, multihash);
1956 }
1957 
1958 
1959 /** inserts element in multihash table (multiple inserts of same element possible)
1960  *
1961  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
1962  * to the hash table, due to dynamic resizing.
1963  */
1965  SCIP_MULTIHASH* multihash, /**< multihash table */
1966  void* element /**< element to insert into the table */
1967  )
1968 {
1969  void* key;
1970  uint64_t keyval;
1971  unsigned int hashval;
1972 
1973  assert(multihash != NULL);
1974  assert(multihash->lists != NULL);
1975  assert(multihash->nlists > 0);
1976  assert(multihash->hashgetkey != NULL);
1977  assert(multihash->hashkeyeq != NULL);
1978  assert(multihash->hashkeyval != NULL);
1979  assert(element != NULL);
1980 
1981  /* dynamically resizing the hashtables */
1983  {
1984  SCIP_CALL( multihashResize(multihash) );
1985  }
1986 
1987  /* get the hash key and its hash value */
1988  key = multihash->hashgetkey(multihash->userptr, element);
1989  keyval = multihash->hashkeyval(multihash->userptr, key);
1990  hashval = keyval % multihash->nlists; /*lint !e573*/
1991 
1992  /* append element to the list at the hash position */
1993  SCIP_CALL( multihashlistAppend(&multihash->lists[hashval], multihash->blkmem, element) );
1994 
1995  ++(multihash->nelements);
1996 
1997  return SCIP_OKAY;
1998 }
1999 
2000 /** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
2001  *
2002  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
2003  * element to the multihash table, due to dynamic resizing.
2004  */
2006  SCIP_MULTIHASH* multihash, /**< multihash table */
2007  void* element /**< element to insert into the table */
2008  )
2009 {
2010  assert(multihash != NULL);
2011  assert(multihash->hashgetkey != NULL);
2012 
2013  /* check, if key is already existing */
2014  if( SCIPmultihashRetrieve(multihash, multihash->hashgetkey(multihash->userptr, element)) != NULL )
2015  return SCIP_KEYALREADYEXISTING;
2016 
2017  /* insert element in hash table */
2018  SCIP_CALL( SCIPmultihashInsert(multihash, element) );
2019 
2020  return SCIP_OKAY;
2021 }
2022 
2023 /** retrieve element with key from multihash table, returns NULL if not existing */
2025  SCIP_MULTIHASH* multihash, /**< multihash table */
2026  void* key /**< key to retrieve */
2027  )
2028 {
2029  uint64_t keyval;
2030  unsigned int hashval;
2031 
2032  assert(multihash != NULL);
2033  assert(multihash->lists != NULL);
2034  assert(multihash->nlists > 0);
2035  assert(multihash->hashgetkey != NULL);
2036  assert(multihash->hashkeyeq != NULL);
2037  assert(multihash->hashkeyval != NULL);
2038  assert(key != NULL);
2039 
2040  /* get the hash value of the key */
2041  keyval = multihash->hashkeyval(multihash->userptr, key);
2042  hashval = keyval % multihash->nlists; /*lint !e573*/
2043 
2044  return multihashlistRetrieve(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
2045  multihash->hashkeyval, multihash->userptr, keyval, key);
2046 }
2047 
2048 /** retrieve element with key from multihash table, returns NULL if not existing
2049  * can be used to retrieve all entries with the same key (one-by-one)
2050  *
2051  * @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
2052  */
2054  SCIP_MULTIHASH* multihash, /**< multihash table */
2055  SCIP_MULTIHASHLIST** multihashlist, /**< input: entry in hash table list from which to start searching, or NULL
2056  * output: entry in hash table list corresponding to element after
2057  * retrieved one, or NULL */
2058  void* key /**< key to retrieve */
2059  )
2060 {
2061  uint64_t keyval;
2062 
2063  assert(multihash != NULL);
2064  assert(multihash->lists != NULL);
2065  assert(multihash->nlists > 0);
2066  assert(multihash->hashgetkey != NULL);
2067  assert(multihash->hashkeyeq != NULL);
2068  assert(multihash->hashkeyval != NULL);
2069  assert(multihashlist != NULL);
2070  assert(key != NULL);
2071 
2072  keyval = multihash->hashkeyval(multihash->userptr, key);
2073 
2074  if( *multihashlist == NULL )
2075  {
2076  unsigned int hashval;
2077 
2078  /* get the hash value of the key */
2079  hashval = keyval % multihash->nlists; /*lint !e573*/
2080 
2081  *multihashlist = multihash->lists[hashval];
2082  }
2083 
2084  return multihashlistRetrieveNext(multihashlist, multihash->hashgetkey, multihash->hashkeyeq,
2085  multihash->hashkeyval, multihash->userptr, keyval, key);
2086 }
2087 
2088 /** returns whether the given element exists in the multihash table */
2090  SCIP_MULTIHASH* multihash, /**< multihash table */
2091  void* element /**< element to search in the table */
2092  )
2093 {
2094  void* key;
2095  uint64_t keyval;
2096  unsigned int hashval;
2097 
2098  assert(multihash != NULL);
2099  assert(multihash->lists != NULL);
2100  assert(multihash->nlists > 0);
2101  assert(multihash->hashgetkey != NULL);
2102  assert(multihash->hashkeyeq != NULL);
2103  assert(multihash->hashkeyval != NULL);
2104  assert(element != NULL);
2105 
2106  /* get the hash key and its hash value */
2107  key = multihash->hashgetkey(multihash->userptr, element);
2108  keyval = multihash->hashkeyval(multihash->userptr, key);
2109  hashval = keyval % multihash->nlists; /*lint !e573*/
2110 
2111  return (multihashlistFind(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
2112  multihash->hashkeyval, multihash->userptr, keyval, key) != NULL);
2113 }
2114 
2115 /** removes element from the multihash table, if it exists */
2117  SCIP_MULTIHASH* multihash, /**< multihash table */
2118  void* element /**< element to remove from the table */
2119  )
2120 {
2121  void* key;
2122  uint64_t keyval;
2123  unsigned int hashval;
2124 
2125  assert(multihash != NULL);
2126  assert(multihash->lists != NULL);
2127  assert(multihash->nlists > 0);
2128  assert(multihash->hashgetkey != NULL);
2129  assert(multihash->hashkeyeq != NULL);
2130  assert(multihash->hashkeyval != NULL);
2131  assert(element != NULL);
2132 
2133  /* get the hash key and its hash value */
2134  key = multihash->hashgetkey(multihash->userptr, element);
2135  keyval = multihash->hashkeyval(multihash->userptr, key);
2136  hashval = keyval % multihash->nlists; /*lint !e573*/
2137 
2138  /* remove element from the list at the hash position */
2139  if( multihashlistRemove(&multihash->lists[hashval], multihash->blkmem, element) )
2140  --(multihash->nelements);
2141 
2142  return SCIP_OKAY;
2143 }
2144 
2145 /** removes all elements of the multihash table
2146  *
2147  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2148  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2149  */
2151  SCIP_MULTIHASH* multihash /**< multihash table */
2152  )
2153 {
2154  BMS_BLKMEM* blkmem;
2155  SCIP_MULTIHASHLIST** lists;
2156  int i;
2157 
2158  assert(multihash != NULL);
2159 
2160  blkmem = multihash->blkmem;
2161  lists = multihash->lists;
2162 
2163  /* free hash lists */
2164  for( i = multihash->nlists - 1; i >= 0; --i )
2165  multihashlistFree(&lists[i], blkmem);
2166 
2167  multihash->nelements = 0;
2168 }
2169 
2170 /** returns number of multihash table elements */
2172  SCIP_MULTIHASH* multihash /**< multihash table */
2173  )
2174 {
2175  assert(multihash != NULL);
2176 
2177  return multihash->nelements;
2178 }
2179 
2180 /** returns the load of the given multihash table in percentage */
2182  SCIP_MULTIHASH* multihash /**< multihash table */
2183  )
2184 {
2185  assert(multihash != NULL);
2186 
2187  return ((SCIP_Real)(multihash->nelements) / (multihash->nlists) * 100.0);
2188 }
2189 
2190 /** prints statistics about multihash table usage */
2192  SCIP_MULTIHASH* multihash, /**< multihash table */
2193  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
2194  )
2195 {
2196  SCIP_MULTIHASHLIST* multihashlist;
2197  int usedslots;
2198  int maxslotsize;
2199  int sumslotsize;
2200  int slotsize;
2201  int i;
2202 
2203  assert(multihash != NULL);
2204 
2205  usedslots = 0;
2206  maxslotsize = 0;
2207  sumslotsize = 0;
2208  for( i = 0; i < multihash->nlists; ++i )
2209  {
2210  multihashlist = multihash->lists[i];
2211  if( multihashlist != NULL )
2212  {
2213  usedslots++;
2214  slotsize = 0;
2215  while( multihashlist != NULL )
2216  {
2217  slotsize++;
2218  multihashlist = multihashlist->next;
2219  }
2220  maxslotsize = MAX(maxslotsize, slotsize);
2221  sumslotsize += slotsize;
2222  }
2223  }
2224  assert(sumslotsize == multihash->nelements);
2225 
2226  SCIPmessagePrintInfo(messagehdlr, "%" SCIP_LONGINT_FORMAT " multihash entries, used %d/%d slots (%.1f%%)",
2227  multihash->nelements, usedslots, multihash->nlists, 100.0*(SCIP_Real)usedslots/(SCIP_Real)(multihash->nlists));
2228  if( usedslots > 0 )
2229  SCIPmessagePrintInfo(messagehdlr, ", avg. %.1f entries/used slot, max. %d entries in slot",
2230  (SCIP_Real)(multihash->nelements)/(SCIP_Real)usedslots, maxslotsize);
2231  SCIPmessagePrintInfo(messagehdlr, "\n");
2232 }
2233 
2234 /** creates a hash table */
2236  SCIP_HASHTABLE** hashtable, /**< pointer to store the created hash table */
2237  BMS_BLKMEM* blkmem, /**< block memory used to store hash table entries */
2238  int tablesize, /**< size of the hash table */
2239  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
2240  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
2241  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
2242  void* userptr /**< user pointer */
2243  )
2244 {
2245  unsigned int nslots;
2246 
2247  /* only assert non negative to catch overflow errors
2248  * but not zeros due to integer divison
2249  */
2250  assert(tablesize >= 0);
2251  assert(hashtable != NULL);
2252  assert(hashgetkey != NULL);
2253  assert(hashkeyeq != NULL);
2254  assert(hashkeyval != NULL);
2255  assert(blkmem != NULL);
2256 
2257  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashtable) );
2258 
2259  /* dont create too small hashtables, i.e. at least size 32, and increase
2260  * the given size by divinding it by 0.9, since then no rebuilding will
2261  * be necessary if the given number of elements are inserted. Finally round
2262  * to the next power of two.
2263  */
2264  (*hashtable)->shift = 32;
2265  (*hashtable)->shift -= (int)ceil(LOG2(MAX(32.0, tablesize / 0.9)));
2266 
2267  /* compute size from shift */
2268  nslots = 1u << (32 - (*hashtable)->shift);
2269 
2270  /* compute mask to do a fast modulo by nslots using bitwise and */
2271  (*hashtable)->mask = nslots - 1;
2272  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*hashtable)->slots, nslots) );
2273  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashtable)->hashes, nslots) );
2274  (*hashtable)->blkmem = blkmem;
2275  (*hashtable)->hashgetkey = hashgetkey;
2276  (*hashtable)->hashkeyeq = hashkeyeq;
2277  (*hashtable)->hashkeyval = hashkeyval;
2278  (*hashtable)->userptr = userptr;
2279  (*hashtable)->nelements = 0;
2280 
2281  return SCIP_OKAY;
2282 }
2283 
2284 /** frees the hash table */
2286  SCIP_HASHTABLE** hashtable /**< pointer to the hash table */
2287  )
2288 {
2289  uint32_t nslots;
2290  SCIP_HASHTABLE* table;
2291 
2292  assert(hashtable != NULL);
2293  assert(*hashtable != NULL);
2294  table = *hashtable;
2295  nslots = (*hashtable)->mask + 1;
2296 #ifdef SCIP_DEBUG
2297  {
2298  uint32_t maxprobelen = 0;
2299  uint64_t probelensum = 0;
2300  uint32_t i;
2301 
2302  assert(table != NULL);
2303 
2304  for( i = 0; i < nslots; ++i )
2305  {
2306  if( table->hashes[i] != 0 )
2307  {
2308  uint32_t probelen = ((i + table->mask + 1 - (table->hashes[i]>>(table->shift))) & table->mask) + 1;
2309  probelensum += probelen;
2310  maxprobelen = MAX(probelen, maxprobelen);
2311  }
2312  }
2313 
2314  SCIPdebugMessage("%u hash table entries, used %u/%u slots (%.1f%%)",
2315  (unsigned int)table->nelements, (unsigned int)table->nelements, (unsigned int)nslots,
2316  100.0*(SCIP_Real)table->nelements/(SCIP_Real)(nslots));
2317  if( table->nelements > 0 )
2318  SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
2319  (SCIP_Real)(probelensum)/(SCIP_Real)table->nelements, (unsigned int)maxprobelen);
2320  SCIPdebugMessage("\n");
2321  }
2322 #endif
2323 
2324  /* free main hash table data structure */
2325  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->hashes, nslots);
2326  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->slots, nslots);
2327  BMSfreeBlockMemory((*hashtable)->blkmem, hashtable);
2328 }
2329 
2330 /** removes all elements of the hash table
2331  *
2332  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2333  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2334  *
2335  * @deprecated Please use SCIPhashtableRemoveAll()
2336  */
2338  SCIP_HASHTABLE* hashtable /**< hash table */
2339  )
2340 {
2341  SCIPhashtableRemoveAll(hashtable);
2342 }
2343 
2344 /* computes the distance from it's desired position for the element stored at pos */
2345 #define ELEM_DISTANCE(pos) (((pos) + hashtable->mask + 1 - (hashtable->hashes[(pos)]>>(hashtable->shift))) & hashtable->mask)
2346 
2347 /** inserts element in hash table (multiple inserts of same element overrides previous one) */
2348 static
2350  SCIP_HASHTABLE* hashtable, /**< hash table */
2351  void* element, /**< element to insert into the table */
2352  void* key, /**< key of element */
2353  uint32_t hashval, /**< hash value of element */
2354  SCIP_Bool override /**< should element be overridden or an error be returned if already existing */
2355  )
2356 {
2357  uint32_t elemdistance;
2358  uint32_t pos;
2359 #ifndef NDEBUG
2360  SCIP_Bool swapped = FALSE;
2361 #endif
2362 
2363  assert(hashtable != NULL);
2364  assert(hashtable->slots != NULL);
2365  assert(hashtable->hashes != NULL);
2366  assert(hashtable->mask > 0);
2367  assert(hashtable->hashgetkey != NULL);
2368  assert(hashtable->hashkeyeq != NULL);
2369  assert(hashtable->hashkeyval != NULL);
2370  assert(element != NULL);
2371 
2372  pos = hashval>>(hashtable->shift);
2373  elemdistance = 0;
2374  while( TRUE ) /*lint !e716*/
2375  {
2376  uint32_t distance;
2377 
2378  /* if position is empty or key equal insert element */
2379  if( hashtable->hashes[pos] == 0 )
2380  {
2381  hashtable->slots[pos] = element;
2382  hashtable->hashes[pos] = hashval;
2383  ++hashtable->nelements;
2384  return SCIP_OKAY;
2385  }
2386 
2387  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2388  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2389  {
2390  if( override )
2391  {
2392 #ifndef NDEBUG
2393  assert(! swapped);
2394 #endif
2395  hashtable->slots[pos] = element;
2396  hashtable->hashes[pos] = hashval;
2397  return SCIP_OKAY;
2398  }
2399  else
2400  {
2401  return SCIP_KEYALREADYEXISTING;
2402  }
2403  }
2404 
2405  /* otherwise check if the current element at this position is closer to its hashvalue */
2406  distance = ELEM_DISTANCE(pos);
2407  if( distance < elemdistance )
2408  {
2409  uint32_t tmp;
2410 
2411  /* if this is the case we insert the new element here and find a new position for the old one */
2412  elemdistance = distance;
2413  SCIPswapPointers(&hashtable->slots[pos], &element);
2414  tmp = hashval;
2415  hashval = hashtable->hashes[pos];
2416  hashtable->hashes[pos] = tmp;
2417  key = hashtable->hashgetkey(hashtable->userptr, element);
2418 
2419  /* after doing a swap the case that other elements are replaced must not happen anymore */
2420 #ifndef NDEBUG
2421  swapped = TRUE;
2422 #endif
2423  }
2424 
2425  /* continue until we have found an empty position */
2426  pos = (pos + 1) & hashtable->mask;
2427  ++elemdistance;
2428  }
2429 }
2430 
2431 /** check if the load factor of the hashtable is too high and rebuild if necessary */
2432 static
2434  SCIP_HASHTABLE* hashtable /**< hash table */
2435  )
2436 {
2437  assert(hashtable != NULL);
2438  assert(hashtable->shift < 32);
2439 
2440  /* use integer arithmetic to approximately check if load factor is above 90% */
2441  if( ((((uint64_t)hashtable->nelements)<<10)>>(32-hashtable->shift) > 921) )
2442  {
2443  void** slots;
2444  uint32_t* hashes;
2445  uint32_t nslots;
2446  uint32_t newnslots;
2447  uint32_t i;
2448 
2449  /* calculate new size (always power of two) */
2450  nslots = hashtable->mask + 1;
2451  newnslots = 2*nslots;
2452  hashtable->mask = newnslots-1;
2453  --hashtable->shift;
2454 
2455  /* reallocate array */
2456  SCIP_ALLOC( BMSallocBlockMemoryArray(hashtable->blkmem, &slots, newnslots) );
2457  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashtable->blkmem, &hashes, newnslots) );
2458 
2459  SCIPswapPointers((void**) &slots, (void**) &hashtable->slots);
2460  SCIPswapPointers((void**) &hashes, (void**) &hashtable->hashes);
2461  hashtable->nelements = 0;
2462 
2463  /* reinsert all elements */
2464  for( i = 0; i < nslots; ++i )
2465  {
2466  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2467  * and thus no bad return codes when inserting the elements
2468  */
2469  if( hashes[i] != 0 )
2470  {
2471  SCIP_CALL_ABORT( hashtableInsert(hashtable, slots[i], hashtable->hashgetkey(hashtable->userptr, slots[i]), hashes[i], FALSE) );
2472  }
2473  }
2474  BMSfreeBlockMemoryArray(hashtable->blkmem, &hashes, nslots);
2475  BMSfreeBlockMemoryArray(hashtable->blkmem, &slots, nslots);
2476  }
2477 
2478  return SCIP_OKAY;
2479 }
2480 
2481 
2482 /** inserts element in hash table
2483  *
2484  * @note multiple inserts of same element overrides previous one
2485  */
2487  SCIP_HASHTABLE* hashtable, /**< hash table */
2488  void* element /**< element to insert into the table */
2489  )
2490 {
2491  void* key;
2492  uint64_t keyval;
2493  uint32_t hashval;
2494 
2495  assert(hashtable != NULL);
2496  assert(hashtable->slots != NULL);
2497  assert(hashtable->hashes != NULL);
2498  assert(hashtable->mask > 0);
2499  assert(hashtable->hashgetkey != NULL);
2500  assert(hashtable->hashkeyeq != NULL);
2501  assert(hashtable->hashkeyval != NULL);
2502  assert(element != NULL);
2503 
2504  SCIP_CALL( hashtableCheckLoad(hashtable) );
2505 
2506  /* get the hash key and its hash value */
2507  key = hashtable->hashgetkey(hashtable->userptr, element);
2508  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2509  hashval = hashvalue(keyval);
2510 
2511  return hashtableInsert(hashtable, element, key, hashval, TRUE);
2512 }
2513 
2514 /** inserts element in hash table
2515  *
2516  * @note multiple insertion of same element is checked and results in an error
2517  */
2519  SCIP_HASHTABLE* hashtable, /**< hash table */
2520  void* element /**< element to insert into the table */
2521  )
2522 {
2523  void* key;
2524  uint64_t keyval;
2525  uint32_t hashval;
2526 
2527  assert(hashtable != NULL);
2528  assert(hashtable->slots != NULL);
2529  assert(hashtable->hashes != NULL);
2530  assert(hashtable->mask > 0);
2531  assert(hashtable->hashgetkey != NULL);
2532  assert(hashtable->hashkeyeq != NULL);
2533  assert(hashtable->hashkeyval != NULL);
2534  assert(element != NULL);
2535 
2536  SCIP_CALL( hashtableCheckLoad(hashtable) );
2537 
2538  /* get the hash key and its hash value */
2539  key = hashtable->hashgetkey(hashtable->userptr, element);
2540  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2541  hashval = hashvalue(keyval);
2542 
2543  return hashtableInsert(hashtable, element, key, hashval, FALSE);
2544 }
2545 
2546 /** retrieve element with key from hash table, returns NULL if not existing */
2548  SCIP_HASHTABLE* hashtable, /**< hash table */
2549  void* key /**< key to retrieve */
2550  )
2551 {
2552  uint64_t keyval;
2553  uint32_t hashval;
2554  uint32_t pos;
2555  uint32_t elemdistance;
2556 
2557  assert(hashtable != NULL);
2558  assert(hashtable->slots != NULL);
2559  assert(hashtable->hashes != NULL);
2560  assert(hashtable->mask > 0);
2561  assert(hashtable->hashgetkey != NULL);
2562  assert(hashtable->hashkeyeq != NULL);
2563  assert(hashtable->hashkeyval != NULL);
2564  assert(key != NULL);
2565 
2566  /* get the hash value of the key */
2567  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2568  hashval = hashvalue(keyval);
2569 
2570  pos = hashval>>(hashtable->shift);
2571  elemdistance = 0;
2572 
2573  while( TRUE ) /*lint !e716*/
2574  {
2575  uint32_t distance;
2576 
2577  /* slots is empty so element cannot be contained */
2578  if( hashtable->hashes[pos] == 0 )
2579  return NULL;
2580 
2581  distance = ELEM_DISTANCE(pos);
2582 
2583  /* element cannot be contained since otherwise we would have swapped it with this one during insert */
2584  if( elemdistance > distance )
2585  return NULL;
2586 
2587  /* found element */
2588  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2589  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2590  return hashtable->slots[pos];
2591 
2592  pos = (pos + 1) & hashtable->mask;
2593  ++elemdistance;
2594  }
2595 }
2596 
2597 /** returns whether the given element exists in the table */
2599  SCIP_HASHTABLE* hashtable, /**< hash table */
2600  void* element /**< element to search in the table */
2601  )
2602 {
2603  assert(hashtable != NULL);
2604  assert(hashtable->slots != NULL);
2605  assert(hashtable->hashes != NULL);
2606  assert(hashtable->mask > 0);
2607  assert(hashtable->hashgetkey != NULL);
2608  assert(hashtable->hashkeyeq != NULL);
2609  assert(hashtable->hashkeyval != NULL);
2610  assert(element != NULL);
2611 
2612  return (SCIPhashtableRetrieve(hashtable, hashtable->hashgetkey(hashtable->userptr, element)) != NULL);
2613 }
2614 
2615 /** removes element from the hash table, if it exists */
2617  SCIP_HASHTABLE* hashtable, /**< hash table */
2618  void* element /**< element to remove from the table */
2619  )
2620 {
2621  void* key;
2622  uint64_t keyval;
2623  uint32_t hashval;
2624  uint32_t elemdistance;
2625  uint32_t distance;
2626  uint32_t pos;
2627 
2628  assert(hashtable != NULL);
2629  assert(hashtable->slots != NULL);
2630  assert(hashtable->hashes != NULL);
2631  assert(hashtable->mask > 0);
2632  assert(hashtable->hashgetkey != NULL);
2633  assert(hashtable->hashkeyeq != NULL);
2634  assert(hashtable->hashkeyval != NULL);
2635  assert(element != NULL);
2636 
2637  /* get the hash key and its hash value */
2638  key = hashtable->hashgetkey(hashtable->userptr, element);
2639  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2640  hashval = hashvalue(keyval);
2641 
2642  elemdistance = 0;
2643  pos = hashval>>(hashtable->shift);
2644  while( TRUE ) /*lint !e716*/
2645  {
2646  /* slots empty so element not contained */
2647  if( hashtable->hashes[pos] == 0 )
2648  return SCIP_OKAY;
2649 
2650  distance = ELEM_DISTANCE(pos);
2651 
2652  /* element can not be contained since otherwise we would have swapped it with this one */
2653  if( elemdistance > distance )
2654  return SCIP_OKAY;
2655 
2656  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2657  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2658  {
2659  /* element exists at pos so break out of loop */
2660  break;
2661  }
2662 
2663  pos = (pos + 1) & hashtable->mask;
2664  ++elemdistance;
2665  }
2666 
2667  /* remove element */
2668  hashtable->hashes[pos] = 0;
2669  --hashtable->nelements;
2670  while( TRUE ) /*lint !e716*/
2671  {
2672  uint32_t nextpos = (pos + 1) & hashtable->mask;
2673 
2674  /* nothing to do since there is no chain that needs to be moved */
2675  if( hashtable->hashes[nextpos] == 0 )
2676  break;
2677 
2678  /* check if the element is the start of a new chain and return if that is the case */
2679  if( (hashtable->hashes[nextpos]>>(hashtable->shift)) == nextpos )
2680  break;
2681 
2682  /* element should be moved to the left and next element needs to be checked */
2683  hashtable->slots[pos] = hashtable->slots[nextpos];
2684  hashtable->hashes[pos] = hashtable->hashes[nextpos];
2685  hashtable->hashes[nextpos] = 0;
2686 
2687  pos = nextpos;
2688  }
2689 
2690  return SCIP_OKAY;
2691 }
2692 
2693 /** removes all elements of the hash table */
2695  SCIP_HASHTABLE* hashtable /**< hash table */
2696  )
2697 {
2698  assert(hashtable != NULL);
2699 
2700  BMSclearMemoryArray(hashtable->hashes, hashtable->mask + 1);
2701 
2702  hashtable->nelements = 0;
2703 }
2704 
2705 /** returns number of hash table elements */
2707  SCIP_HASHTABLE* hashtable /**< hash table */
2708  )
2709 {
2710  assert(hashtable != NULL);
2711 
2712  return hashtable->nelements;
2713 }
2714 
2715 /** gives the number of entries in the internal arrays of a hash table */
2717  SCIP_HASHTABLE* hashtable /**< hash table */
2718  )
2719 {
2720  return (int) hashtable->mask + 1;
2721 }
2722 
2723 /** gives the element at the given index or NULL if entry at that index has no element */
2725  SCIP_HASHTABLE* hashtable, /**< hash table */
2726  int entryidx /**< index of hash table entry */
2727  )
2728 {
2729  return hashtable->hashes[entryidx] == 0 ? NULL : hashtable->slots[entryidx];
2730 }
2731 
2732 /** returns the load of the given hash table in percentage */
2734  SCIP_HASHTABLE* hashtable /**< hash table */
2735  )
2736 {
2737  assert(hashtable != NULL);
2738 
2739  return ((SCIP_Real)(hashtable->nelements) / (hashtable->mask + 1) * 100.0);
2740 }
2741 
2742 /** prints statistics about hash table usage */
2744  SCIP_HASHTABLE* hashtable, /**< hash table */
2745  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
2746  )
2747 {
2748  uint32_t maxprobelen = 0;
2749  uint64_t probelensum = 0;
2750  uint32_t nslots;
2751  uint32_t i;
2752 
2753  assert(hashtable != NULL);
2754 
2755  nslots = hashtable->mask + 1;
2756 
2757  /* compute the maximum and average probe length */
2758  for( i = 0; i < nslots; ++i )
2759  {
2760  if( hashtable->hashes[i] != 0 )
2761  {
2762  uint32_t probelen = ELEM_DISTANCE(i) + 1;
2763  probelensum += probelen;
2764  maxprobelen = MAX(probelen, maxprobelen);
2765  }
2766  }
2767 
2768  /* print general hash table statistics */
2769  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
2770  (unsigned int)hashtable->nelements, (unsigned int)hashtable->nelements,
2771  (unsigned int)nslots, 100.0*(SCIP_Real)hashtable->nelements/(SCIP_Real)(nslots));
2772 
2773  /* if not empty print average and maximum probe length */
2774  if( hashtable->nelements > 0 )
2775  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
2776  (SCIP_Real)(probelensum)/(SCIP_Real)hashtable->nelements, (unsigned int)maxprobelen);
2777  SCIPmessagePrintInfo(messagehdlr, "\n");
2778 }
2779 
2780 /** returns TRUE iff both keys (i.e. strings) are equal */
2781 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString)
2782 { /*lint --e{715}*/
2783  const char* string1 = (const char*)key1;
2784  const char* string2 = (const char*)key2;
2785 
2786  return (strcmp(string1, string2) == 0);
2787 }
2788 
2789 /** returns the hash value of the key (i.e. string) */
2790 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString)
2791 { /*lint --e{715}*/
2792  const char* str;
2793  uint64_t hash;
2794 
2795  str = (const char*)key;
2796  hash = 37;
2797  while( *str != '\0' )
2798  {
2799  hash *= 11;
2800  hash += (unsigned int)(*str); /*lint !e571*/
2801  str++;
2802  }
2803 
2804  return hash;
2805 }
2806 
2807 
2808 /** gets the element as the key */
2809 SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard)
2810 { /*lint --e{715}*/
2811  /* the key is the element itself */
2812  return elem;
2813 }
2814 
2815 /** returns TRUE iff both keys(pointer) are equal */
2816 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr)
2817 { /*lint --e{715}*/
2818  return (key1 == key2);
2819 }
2820 
2821 /** returns the hash value of the key */
2822 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr)
2823 { /*lint --e{715}*/
2824  /* the key is used as the keyvalue too */
2825  return (uint64_t) (uintptr_t) key;
2826 }
2827 
2828 
2829 
2830 /*
2831  * Hash Map
2832  */
2833 
2834 /* redefine ELEM_DISTANCE macro for hashmap */
2835 #undef ELEM_DISTANCE
2836 /* computes the distance from it's desired position for the element stored at pos */
2837 #define ELEM_DISTANCE(pos) (((pos) + hashmap->mask + 1 - (hashmap->hashes[(pos)]>>(hashmap->shift))) & hashmap->mask)
2838 
2839 /** inserts element in hash table */
2840 static
2842  SCIP_HASHMAP* hashmap, /**< hash map */
2843  void* origin, /**< element to insert into the table */
2844  SCIP_HASHMAPIMAGE image, /**< key of element */
2845  uint32_t hashval, /**< hash value of element */
2846  SCIP_Bool override /**< should element be overridden or error be returned if already existing */
2847  )
2848 {
2849  uint32_t elemdistance;
2850  uint32_t pos;
2851 
2852  assert(hashmap != NULL);
2853  assert(hashmap->slots != NULL);
2854  assert(hashmap->hashes != NULL);
2855  assert(hashmap->mask > 0);
2856  assert(hashval != 0);
2857 
2858  pos = hashval>>(hashmap->shift);
2859  elemdistance = 0;
2860  while( TRUE ) /*lint !e716*/
2861  {
2862  uint32_t distance;
2863 
2864  /* if position is empty or key equal insert element */
2865  if( hashmap->hashes[pos] == 0 )
2866  {
2867  hashmap->slots[pos].origin = origin;
2868  hashmap->slots[pos].image = image;
2869  hashmap->hashes[pos] = hashval;
2870  ++hashmap->nelements;
2871  return SCIP_OKAY;
2872  }
2873 
2874  if( hashval == hashmap->hashes[pos] && origin == hashmap->slots[pos].origin )
2875  {
2876  if( override )
2877  {
2878  hashmap->slots[pos].origin = origin;
2879  hashmap->slots[pos].image = image;
2880  hashmap->hashes[pos] = hashval;
2881  return SCIP_OKAY;
2882  }
2883  else
2884  {
2885  return SCIP_KEYALREADYEXISTING;
2886  }
2887  }
2888 
2889  /* otherwise check if the current element at this position is closer to its hashvalue */
2890  distance = ELEM_DISTANCE(pos);
2891  if( distance < elemdistance )
2892  {
2893  SCIP_HASHMAPIMAGE tmp;
2894  uint32_t tmphash;
2895 
2896  /* if this is the case we insert the new element here and find a new position for the old one */
2897  elemdistance = distance;
2898  tmphash = hashval;
2899  hashval = hashmap->hashes[pos];
2900  hashmap->hashes[pos] = tmphash;
2901  SCIPswapPointers(&hashmap->slots[pos].origin, &origin);
2902  tmp = image;
2903  image = hashmap->slots[pos].image;
2904  hashmap->slots[pos].image = tmp;
2905  }
2906 
2907  /* continue until we have found an empty position */
2908  pos = (pos + 1) & hashmap->mask;
2909  ++elemdistance;
2910  }
2911 }
2912 
2913 /** lookup origin in the hashmap. If element is found returns true and the position of the element,
2914  * otherwise returns FALSE.
2915  */
2916 static
2918  SCIP_HASHMAP* hashmap, /**< hash table */
2919  void* origin, /**< origin to lookup */
2920  uint32_t* pos /**< pointer to store position of element, if exists */
2921  )
2922 {
2923  uint32_t hashval;
2924  uint32_t elemdistance;
2925 
2926  assert(hashmap != NULL);
2927  assert(hashmap->slots != NULL);
2928  assert(hashmap->hashes != NULL);
2929  assert(hashmap->mask > 0);
2930 
2931  /* get the hash value */
2932  hashval = hashvalue((size_t)origin);
2933  assert(hashval != 0);
2934 
2935  *pos = hashval>>(hashmap->shift);
2936  elemdistance = 0;
2937 
2938  while( TRUE ) /*lint !e716*/
2939  {
2940  uint32_t distance;
2941 
2942  /* slots is empty so element cannot be contained */
2943  if( hashmap->hashes[*pos] == 0 )
2944  return FALSE;
2945 
2946  distance = ELEM_DISTANCE(*pos);
2947  /* element can not be contained since otherwise we would have swapped it with this one during insert */
2948  if( elemdistance > distance )
2949  return FALSE;
2950 
2951  /* found element */
2952  if( hashmap->hashes[*pos] == hashval && hashmap->slots[*pos].origin == origin )
2953  return TRUE;
2954 
2955  *pos = (*pos + 1) & hashmap->mask;
2956  ++elemdistance;
2957  }
2958 }
2959 
2960 /** check if the load factor of the hashmap is too high and rebuild if necessary */
2961 static
2963  SCIP_HASHMAP* hashmap /**< hash table */
2964  )
2965 {
2966  assert(hashmap != NULL);
2967  assert(hashmap->shift < 32);
2968 
2969  /* use integer arithmetic to approximately check if load factor is above 90% */
2970  if( ((((uint64_t)hashmap->nelements)<<10)>>(32-hashmap->shift) > 921) )
2971  {
2972  SCIP_HASHMAPENTRY* slots;
2973  uint32_t* hashes;
2974  uint32_t nslots;
2975  uint32_t newnslots;
2976  uint32_t i;
2977 
2978  /* calculate new size (always power of two) */
2979  nslots = hashmap->mask + 1;
2980  --hashmap->shift;
2981  newnslots = 2*nslots;
2982  hashmap->mask = newnslots-1;
2983 
2984  /* reallocate array */
2985  SCIP_ALLOC( BMSallocBlockMemoryArray(hashmap->blkmem, &slots, newnslots) );
2986  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashmap->blkmem, &hashes, newnslots) );
2987 
2988  SCIPswapPointers((void**) &slots, (void**) &hashmap->slots);
2989  SCIPswapPointers((void**) &hashes, (void**) &hashmap->hashes);
2990  hashmap->nelements = 0;
2991 
2992  /* reinsert all elements */
2993  for( i = 0; i < nslots; ++i )
2994  {
2995  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2996  * and thus no bad return codes when inserting the elements
2997  */
2998  if( hashes[i] != 0 )
2999  {
3000  SCIP_CALL_ABORT( hashmapInsert(hashmap, slots[i].origin, slots[i].image, hashes[i], FALSE) );
3001  }
3002  }
3003 
3004  /* free old arrays */
3005  BMSfreeBlockMemoryArray(hashmap->blkmem, &hashes, nslots);
3006  BMSfreeBlockMemoryArray(hashmap->blkmem, &slots, nslots);
3007  }
3008 
3009  return SCIP_OKAY;
3010 }
3011 
3012 /** creates a hash map mapping pointers to pointers */
3014  SCIP_HASHMAP** hashmap, /**< pointer to store the created hash map */
3015  BMS_BLKMEM* blkmem, /**< block memory used to store hash map entries */
3016  int mapsize /**< size of the hash map */
3017  )
3018 {
3019  uint32_t nslots;
3020 
3021  assert(hashmap != NULL);
3022  assert(mapsize >= 0);
3023  assert(blkmem != NULL);
3024 
3025  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashmap) );
3026 
3027  /* dont create too small hashtables, i.e. at least size 32, and increase
3028  * the given size by divinding it by 0.9, since then no rebuilding will
3029  * be necessary if the given number of elements are inserted. Finally round
3030  * to the next power of two.
3031  */
3032  (*hashmap)->shift = 32;
3033  (*hashmap)->shift -= (int)ceil(log(MAX(32, mapsize / 0.9)) / log(2.0));
3034  nslots = 1u << (32 - (*hashmap)->shift);
3035  (*hashmap)->mask = nslots - 1;
3036  (*hashmap)->blkmem = blkmem;
3037  (*hashmap)->nelements = 0;
3038  (*hashmap)->hashmaptype = SCIP_HASHMAPTYPE_UNKNOWN;
3039 
3040  SCIP_ALLOC( BMSallocBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots) );
3041  SCIP_ALLOC( BMSallocClearBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots) );
3042 
3043  return SCIP_OKAY;
3044 }
3045 
3046 /** frees the hash map */
3048  SCIP_HASHMAP** hashmap /**< pointer to the hash map */
3049  )
3050 {
3051  uint32_t nslots;
3052 
3053  assert(hashmap != NULL);
3054  assert(*hashmap != NULL);
3055 
3056  nslots = (*hashmap)->mask + 1;
3057 #ifdef SCIP_DEBUG
3058  {
3059  uint32_t maxprobelen = 0;
3060  uint64_t probelensum = 0;
3061  uint32_t i;
3062 
3063  assert(hashmap != NULL);
3064 
3065  for( i = 0; i < nslots; ++i )
3066  {
3067  if( (*hashmap)->hashes[i] != 0 )
3068  {
3069  uint32_t probelen = ((i + (*hashmap)->mask + 1 - ((*hashmap)->hashes[i]>>((*hashmap)->shift))) & (*hashmap)->mask) + 1;
3070  probelensum += probelen;
3071  maxprobelen = MAX(probelen, maxprobelen);
3072  }
3073  }
3074 
3075  SCIPdebugMessage("%u hash map entries, used %u/%u slots (%.1f%%)",
3076  (unsigned int)(*hashmap)->nelements, (unsigned int)(*hashmap)->nelements, (unsigned int)nslots,
3077  100.0*(SCIP_Real)(*hashmap)->nelements/(SCIP_Real)(nslots));
3078  if( (*hashmap)->nelements > 0 )
3079  SCIPdebugPrintf(", avg. probe length is %.1f, max. probe length is %u",
3080  (SCIP_Real)(probelensum)/(SCIP_Real)(*hashmap)->nelements, (unsigned int)maxprobelen);
3081  SCIPdebugPrintf("\n");
3082  }
3083 #endif
3084 
3085  /* free main hash map data structure */
3086  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots);
3087  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots);
3088  BMSfreeBlockMemory((*hashmap)->blkmem, hashmap);
3089 }
3090 
3091 /** inserts new origin->image pair in hash map
3092  *
3093  * @note multiple insertion of same element is checked and results in an error
3094  */
3096  SCIP_HASHMAP* hashmap, /**< hash map */
3097  void* origin, /**< origin to set image for */
3098  void* image /**< new image for origin */
3099  )
3100 {
3101  uint32_t hashval;
3102  SCIP_HASHMAPIMAGE img;
3103 
3104  assert(hashmap != NULL);
3105  assert(hashmap->slots != NULL);
3106  assert(hashmap->hashes != NULL);
3107  assert(hashmap->mask > 0);
3108  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3109 
3110 #ifndef NDEBUG
3111  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3113 #endif
3114 
3115  SCIP_CALL( hashmapCheckLoad(hashmap) );
3116 
3117  /* get the hash value */
3118  hashval = hashvalue((size_t)origin);
3119 
3120  /* append origin->image pair to hash map */
3121  img.ptr = image;
3122  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3123 
3124  return SCIP_OKAY;
3125 }
3126 
3127 /** inserts new origin->image pair in hash map
3128  *
3129  * @note multiple insertion of same element is checked and results in an error
3130  */
3132  SCIP_HASHMAP* hashmap, /**< hash map */
3133  void* origin, /**< origin to set image for */
3134  int image /**< new image for origin */
3135  )
3136 {
3137  uint32_t hashval;
3138  SCIP_HASHMAPIMAGE img;
3139 
3140  assert(hashmap != NULL);
3141  assert(hashmap->slots != NULL);
3142  assert(hashmap->hashes != NULL);
3143  assert(hashmap->mask > 0);
3144  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3145 
3146 #ifndef NDEBUG
3147  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3148  hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
3149 #endif
3150 
3151  SCIP_CALL( hashmapCheckLoad(hashmap) );
3152 
3153  /* get the hash value */
3154  hashval = hashvalue((size_t)origin);
3155 
3156  /* append origin->image pair to hash map */
3157  img.integer = image;
3158  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3159 
3160  return SCIP_OKAY;
3161 }
3162 
3163 /** inserts new origin->image pair in hash map
3164  *
3165  * @note multiple insertion of same element is checked and results in an error
3166  */
3168  SCIP_HASHMAP* hashmap, /**< hash map */
3169  void* origin, /**< origin to set image for */
3170  SCIP_Real image /**< new image for origin */
3171  )
3172 {
3173  uint32_t hashval;
3174  SCIP_HASHMAPIMAGE img;
3175 
3176  assert(hashmap != NULL);
3177  assert(hashmap->slots != NULL);
3178  assert(hashmap->hashes != NULL);
3179  assert(hashmap->mask > 0);
3180  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3181 
3182 #ifndef NDEBUG
3183  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3185 #endif
3186 
3187  SCIP_CALL( hashmapCheckLoad(hashmap) );
3188 
3189  /* get the hash value */
3190  hashval = hashvalue((size_t)origin);
3191 
3192  /* append origin->image pair to hash map */
3193  img.real = image;
3194  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3195 
3196  return SCIP_OKAY;
3197 }
3198 
3199 /** retrieves image of given origin from the hash map, or NULL if no image exists */
3201  SCIP_HASHMAP* hashmap, /**< hash map */
3202  void* origin /**< origin to retrieve image for */
3203  )
3204 {
3205  uint32_t pos;
3206 
3207  assert(hashmap != NULL);
3208  assert(hashmap->slots != NULL);
3209  assert(hashmap->hashes != NULL);
3210  assert(hashmap->mask > 0);
3211  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3212 
3213  if( hashmapLookup(hashmap, origin, &pos) )
3214  return hashmap->slots[pos].image.ptr;
3215 
3216  return NULL;
3217 }
3218 
3219 /** retrieves image of given origin from the hash map, or INT_MAX if no image exists */
3221  SCIP_HASHMAP* hashmap, /**< hash map */
3222  void* origin /**< origin to retrieve image for */
3223  )
3224 {
3225  uint32_t pos;
3226 
3227  assert(hashmap != NULL);
3228  assert(hashmap->slots != NULL);
3229  assert(hashmap->hashes != NULL);
3230  assert(hashmap->mask > 0);
3231  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3232 
3233  if( hashmapLookup(hashmap, origin, &pos) )
3234  return hashmap->slots[pos].image.integer;
3235 
3236  return INT_MAX;
3237 }
3238 
3239 /** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */
3241  SCIP_HASHMAP* hashmap, /**< hash map */
3242  void* origin /**< origin to retrieve image for */
3243  )
3244 {
3245  uint32_t pos;
3246 
3247  assert(hashmap != NULL);
3248  assert(hashmap->slots != NULL);
3249  assert(hashmap->hashes != NULL);
3250  assert(hashmap->mask > 0);
3251  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3252 
3253  if( hashmapLookup(hashmap, origin, &pos) )
3254  return hashmap->slots[pos].image.real;
3255 
3256  return SCIP_INVALID;
3257 }
3258 
3259 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3260  * or by appending a new origin->image pair
3261  */
3263  SCIP_HASHMAP* hashmap, /**< hash map */
3264  void* origin, /**< origin to set image for */
3265  void* image /**< new image for origin */
3266  )
3267 {
3268  uint32_t hashval;
3269  SCIP_HASHMAPIMAGE img;
3270 
3271  assert(hashmap != NULL);
3272  assert(hashmap->slots != NULL);
3273  assert(hashmap->mask > 0);
3274  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3275 
3276 #ifndef NDEBUG
3277  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3279 #endif
3280 
3281  SCIP_CALL( hashmapCheckLoad(hashmap) );
3282 
3283  /* get the hash value */
3284  hashval = hashvalue((size_t)origin);
3285 
3286  /* append origin->image pair to hash map */
3287  img.ptr = image;
3288  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3289 
3290  return SCIP_OKAY;
3291 }
3292 
3293 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3294  * or by appending a new origin->image pair
3295  */
3297  SCIP_HASHMAP* hashmap, /**< hash map */
3298  void* origin, /**< origin to set image for */
3299  int image /**< new image for origin */
3300  )
3301 {
3302  uint32_t hashval;
3303  SCIP_HASHMAPIMAGE img;
3304 
3305  assert(hashmap != NULL);
3306  assert(hashmap->slots != NULL);
3307  assert(hashmap->mask > 0);
3308  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3309 
3310 #ifndef NDEBUG
3311  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3312  hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
3313 #endif
3314 
3315  SCIP_CALL( hashmapCheckLoad(hashmap) );
3316 
3317  /* get the hash value */
3318  hashval = hashvalue((size_t)origin);
3319 
3320  /* append origin->image pair to hash map */
3321  img.integer = image;
3322  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3323 
3324  return SCIP_OKAY;
3325 }
3326 
3327 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3328  * or by appending a new origin->image pair
3329  */
3331  SCIP_HASHMAP* hashmap, /**< hash map */
3332  void* origin, /**< origin to set image for */
3333  SCIP_Real image /**< new image for origin */
3334  )
3335 {
3336  uint32_t hashval;
3337  SCIP_HASHMAPIMAGE img;
3338 
3339  assert(hashmap != NULL);
3340  assert(hashmap->slots != NULL);
3341  assert(hashmap->mask > 0);
3342  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3343 
3344 #ifndef NDEBUG
3345  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3347 #endif
3348 
3349  SCIP_CALL( hashmapCheckLoad(hashmap) );
3350 
3351  /* get the hash value */
3352  hashval = hashvalue((size_t)origin);
3353 
3354  /* append origin->image pair to hash map */
3355  img.real = image;
3356  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3357 
3358  return SCIP_OKAY;
3359 }
3360 
3361 /** checks whether an image to the given origin exists in the hash map */
3363  SCIP_HASHMAP* hashmap, /**< hash map */
3364  void* origin /**< origin to search for */
3365  )
3366 {
3367  uint32_t pos;
3368 
3369  assert(hashmap != NULL);
3370  assert(hashmap->slots != NULL);
3371  assert(hashmap->hashes != NULL);
3372  assert(hashmap->mask > 0);
3373 
3374  return hashmapLookup(hashmap, origin, &pos);
3375 }
3376 
3377 /** removes origin->image pair from the hash map, if it exists */
3379  SCIP_HASHMAP* hashmap, /**< hash map */
3380  void* origin /**< origin to remove from the list */
3381  )
3382 {
3383  uint32_t pos;
3384 
3385  assert(hashmap != NULL);
3386  assert(hashmap->slots != NULL);
3387  assert(hashmap->mask > 0);
3388 
3389  assert(origin != NULL);
3390 
3391  if( hashmapLookup(hashmap, origin, &pos) )
3392  {
3393  /* remove element */
3394  hashmap->hashes[pos] = 0;
3395  --hashmap->nelements;
3396 
3397  /* move other elements if necessary */
3398  while( TRUE ) /*lint !e716*/
3399  {
3400  uint32_t nextpos = (pos + 1) & hashmap->mask;
3401 
3402  /* nothing to do since there is no chain that needs to be moved */
3403  if( hashmap->hashes[nextpos] == 0 )
3404  return SCIP_OKAY;
3405 
3406  /* check if the element is the start of a new chain and return if that is the case */
3407  if( (hashmap->hashes[nextpos]>>(hashmap->shift)) == nextpos )
3408  return SCIP_OKAY;
3409 
3410  /* element should be moved to the left and next element needs to be checked */
3411  hashmap->slots[pos].origin = hashmap->slots[nextpos].origin;
3412  hashmap->slots[pos].image = hashmap->slots[nextpos].image;
3413  hashmap->hashes[pos] = hashmap->hashes[nextpos];
3414  hashmap->hashes[nextpos] = 0;
3415 
3416  pos = nextpos;
3417  }
3418  }
3419 
3420  return SCIP_OKAY;
3421 }
3422 
3423 /** prints statistics about hash map usage */
3425  SCIP_HASHMAP* hashmap, /**< hash map */
3426  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
3427  )
3428 {
3429  uint32_t maxprobelen = 0;
3430  uint64_t probelensum = 0;
3431  uint32_t nslots;
3432  uint32_t i;
3433 
3434  assert(hashmap != NULL);
3435 
3436  nslots = hashmap->mask + 1;
3437 
3438  /* compute the maximum and average probe length */
3439  for( i = 0; i < nslots; ++i )
3440  {
3441  if( hashmap->hashes[i] != 0 )
3442  {
3443  uint32_t probelen = ELEM_DISTANCE(i) + 1;
3444  probelensum += probelen;
3445  maxprobelen = MAX(probelen, maxprobelen);
3446  }
3447  }
3448 
3449  /* print general hash map statistics */
3450  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
3451  (unsigned int)hashmap->nelements, (unsigned int)hashmap->nelements,
3452  (unsigned int)nslots, 100.0*(SCIP_Real)hashmap->nelements/(SCIP_Real)(nslots));
3453 
3454  /* if not empty print average and maximum probe length */
3455  if( hashmap->nelements > 0 )
3456  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
3457  (SCIP_Real)(probelensum)/(SCIP_Real)hashmap->nelements, (unsigned int)maxprobelen);
3458  SCIPmessagePrintInfo(messagehdlr, "\n");
3459 }
3460 
3461 /** indicates whether a hash map has no entries */
3463  SCIP_HASHMAP* hashmap /**< hash map */
3464  )
3465 {
3466  assert(hashmap != NULL);
3467 
3468  return hashmap->nelements == 0;
3469 }
3470 
3471 /** gives the number of elements in a hash map */
3473  SCIP_HASHMAP* hashmap /**< hash map */
3474  )
3475 {
3476  return (int) hashmap->nelements;
3477 }
3478 
3479 /** gives the number of entries in the internal arrays of a hash map */
3481  SCIP_HASHMAP* hashmap /**< hash map */
3482  )
3483 {
3484  return (int) hashmap->mask + 1;
3485 }
3486 
3487 /** gives the hashmap entry at the given index or NULL if entry is empty */
3489  SCIP_HASHMAP* hashmap, /**< hash map */
3490  int entryidx /**< index of hash map entry */
3491  )
3492 {
3493  assert(hashmap != NULL);
3494 
3495  return hashmap->hashes[entryidx] == 0 ? NULL : &hashmap->slots[entryidx];
3496 }
3497 
3498 /** gives the origin of the hashmap entry */
3500  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3501  )
3502 {
3503  assert(entry != NULL);
3504 
3505  return entry->origin;
3506 }
3507 
3508 /** gives the image of the hashmap entry */
3510  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3511  )
3512 {
3513  assert(entry != NULL);
3514 
3515  return entry->image.ptr;
3516 }
3517 
3518 /** gives the image of the hashmap entry */
3520  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3521  )
3522 {
3523  assert(entry != NULL);
3524 
3525  return entry->image.integer;
3526 }
3527 
3528 /** gives the image of the hashmap entry */
3530  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3531  )
3532 {
3533  assert(entry != NULL);
3534 
3535  return entry->image.real;
3536 }
3537 
3538 /** sets pointer image of a hashmap entry */
3540  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3541  void* image /**< new image */
3542  )
3543 {
3544  assert(entry != NULL);
3545 
3546  entry->image.ptr = image;
3547 }
3548 
3549 /** sets integer image of a hashmap entry */
3551  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3552  int image /**< new image */
3553  )
3554 {
3555  assert(entry != NULL);
3556 
3557  entry->image.integer = image;
3558 }
3559 
3560 /** sets real image of a hashmap entry */
3562  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3563  SCIP_Real image /**< new image */
3564  )
3565 {
3566  assert(entry != NULL);
3567 
3568  entry->image.real = image;
3569 }
3570 
3571 /** removes all entries in a hash map. */
3573  SCIP_HASHMAP* hashmap /**< hash map */
3574  )
3575 {
3576  assert(hashmap != NULL);
3577 
3578  BMSclearMemoryArray(hashmap->hashes, hashmap->mask + 1);
3579 
3580  hashmap->nelements = 0;
3581 
3582  return SCIP_OKAY;
3583 }
3584 
3585 
3586 /*
3587  * Hash Set
3588  */
3589 
3590 /* redefine ELEM_DISTANCE macro for hashset */
3591 #undef ELEM_DISTANCE
3592 /* computes the distance from it's desired position for the element stored at pos */
3593 #define ELEM_DISTANCE(pos) (((pos) + nslots - hashSetDesiredPos(hashset, hashset->slots[(pos)])) & mask)
3594 
3595 /* calculate desired position of element in hash set */
3596 static
3598  SCIP_HASHSET* hashset, /**< the hash set */
3599  void* element /**< element to calculate position for */
3600  )
3601 {
3602  return (uint32_t)((UINT64_C(0x9e3779b97f4a7c15) * (uintptr_t)element)>>(hashset->shift));
3603 }
3604 
3605 static
3607  SCIP_HASHSET* hashset, /**< hash set */
3608  void* element /**< element to insert */
3609  )
3610 {
3611  uint32_t elemdistance;
3612  uint32_t pos;
3613  uint32_t nslots;
3614  uint32_t mask;
3615 
3616  assert(hashset != NULL);
3617  assert(hashset->slots != NULL);
3618  assert(element != NULL);
3619 
3620  pos = hashSetDesiredPos(hashset, element);
3621  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3622  mask = nslots - 1;
3623 
3624  elemdistance = 0;
3625  while( TRUE ) /*lint !e716*/
3626  {
3627  uint32_t distance;
3628 
3629  /* if position is empty or key equal insert element */
3630  if( hashset->slots[pos] == NULL )
3631  {
3632  hashset->slots[pos] = element;
3633  ++hashset->nelements;
3634  return;
3635  }
3636 
3637  if( hashset->slots[pos] == element )
3638  return;
3639 
3640  /* otherwise check if the current element at this position is closer to its hashvalue */
3641  distance = ELEM_DISTANCE(pos);
3642  if( distance < elemdistance )
3643  {
3644  /* if this is the case we insert the new element here and find a new position for the old one */
3645  elemdistance = distance;
3646  SCIPswapPointers(&hashset->slots[pos], &element);
3647  }
3648 
3649  /* continue until we have found an empty position */
3650  pos = (pos + 1) & mask;
3651  ++elemdistance;
3652  }
3653 }
3654 
3655 /** check if the load factor of the hash set is too high and rebuild if necessary */
3656 static
3658  SCIP_HASHSET* hashset, /**< hash set */
3659  BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */
3660  )
3661 {
3662  assert(hashset != NULL);
3663  assert(hashset->shift < 64);
3664 
3665  /* use integer arithmetic to approximately check if load factor is above 90% */
3666  if( ((((uint64_t)hashset->nelements)<<10)>>(64-hashset->shift) > 921) )
3667  {
3668  void** slots;
3669  uint32_t nslots;
3670  uint32_t newnslots;
3671  uint32_t i;
3672 
3673  /* calculate new size (always power of two) */
3674  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3675  newnslots = 2*nslots;
3676  --hashset->shift;
3677 
3678  /* reallocate array */
3679  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &slots, newnslots) );
3680 
3681  SCIPswapPointers((void**) &slots, (void**) &hashset->slots);
3682  hashset->nelements = 0;
3683 
3684  /* reinsert all elements */
3685  for( i = 0; i < nslots; ++i )
3686  {
3687  if( slots[i] != NULL )
3688  hashsetInsert(hashset, slots[i]);
3689  }
3690 
3691  BMSfreeBlockMemoryArray(blkmem, &slots, nslots);
3692  }
3693 
3694  return SCIP_OKAY;
3695 }
3696 
3697 /** creates a hash set of pointers */
3699  SCIP_HASHSET** hashset, /**< pointer to store the created hash set */
3700  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
3701  int size /**< initial size of the hash set; it is guaranteed that the set is not
3702  * resized if at most that many elements are inserted */
3703  )
3704 {
3705  uint32_t nslots;
3706 
3707  assert(hashset != NULL);
3708  assert(size >= 0);
3709  assert(blkmem != NULL);
3710 
3711  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashset) );
3712 
3713  /* do not create too small hashtables, i.e. at least size 32, and increase
3714  * the given size by dividing it by 0.9, since then no rebuilding will
3715  * be necessary if the given number of elements are inserted. Finally round
3716  * to the next power of two.
3717  */
3718  (*hashset)->shift = 64;
3719  (*hashset)->shift -= (int)ceil(log(MAX(8.0, size / 0.9)) / log(2.0));
3720  nslots = (uint32_t)SCIPhashsetGetNSlots(*hashset);
3721  (*hashset)->nelements = 0;
3722 
3723  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashset)->slots, nslots) );
3724 
3725  return SCIP_OKAY;
3726 }
3727 
3728 /** frees the hash set */
3730  SCIP_HASHSET** hashset, /**< pointer to the hash set */
3731  BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */
3732  )
3733 {
3734  BMSfreeBlockMemoryArray(blkmem, &(*hashset)->slots, SCIPhashsetGetNSlots(*hashset));
3735  BMSfreeBlockMemory(blkmem, hashset);
3736 }
3737 
3738 /** inserts new element into the hash set */
3740  SCIP_HASHSET* hashset, /**< hash set */
3741  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
3742  void* element /**< element to insert */
3743  )
3744 {
3745  assert(hashset != NULL);
3746  assert(hashset->slots != NULL);
3747 
3748  SCIP_CALL( hashsetCheckLoad(hashset, blkmem) );
3749 
3750  hashsetInsert(hashset, element);
3751 
3752  return SCIP_OKAY;
3753 }
3754 
3755 /** checks whether an element exists in the hash set */
3757  SCIP_HASHSET* hashset, /**< hash set */
3758  void* element /**< element to search for */
3759  )
3760 {
3761  uint32_t pos;
3762  uint32_t nslots;
3763  uint32_t mask;
3764  uint32_t elemdistance;
3765 
3766  assert(hashset != NULL);
3767  assert(hashset->slots != NULL);
3768 
3769  pos = hashSetDesiredPos(hashset, element);
3770  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3771  mask = nslots - 1;
3772  elemdistance = 0;
3773 
3774  while( TRUE ) /*lint !e716*/
3775  {
3776  uint32_t distance;
3777 
3778  /* found element */
3779  if( hashset->slots[pos] == element )
3780  return TRUE;
3781 
3782  /* slots is empty so element cannot be contained */
3783  if( hashset->slots[pos] == NULL )
3784  return FALSE;
3785 
3786  distance = ELEM_DISTANCE(pos);
3787  /* element can not be contained since otherwise we would have swapped it with this one during insert */
3788  if( elemdistance > distance )
3789  return FALSE;
3790 
3791  pos = (pos + 1) & mask;
3792  ++elemdistance;
3793  }
3794 }
3795 
3796 /** removes an element from the hash set, if it exists */
3798  SCIP_HASHSET* hashset, /**< hash set */
3799  void* element /**< origin to remove from the list */
3800  )
3801 {
3802  uint32_t pos;
3803  uint32_t nslots;
3804  uint32_t mask;
3805  uint32_t elemdistance;
3806 
3807  assert(hashset != NULL);
3808  assert(hashset->slots != NULL);
3809  assert(element != NULL);
3810 
3811  pos = hashSetDesiredPos(hashset, element);
3812  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3813  mask = nslots - 1;
3814  elemdistance = 0;
3815 
3816  while( TRUE ) /*lint !e716*/
3817  {
3818  uint32_t distance;
3819 
3820  /* found element */
3821  if( hashset->slots[pos] == element )
3822  break;
3823 
3824  /* slots is empty so element cannot be contained */
3825  if( hashset->slots[pos] == NULL )
3826  return SCIP_OKAY;
3827 
3828  distance = ELEM_DISTANCE(pos);
3829  /* element can not be contained since otherwise we would have swapped it with this one during insert */
3830  if( elemdistance > distance )
3831  return SCIP_OKAY;
3832 
3833  pos = (pos + 1) & mask;
3834  ++elemdistance;
3835  }
3836 
3837  assert(hashset->slots[pos] == element);
3838  assert(SCIPhashsetExists(hashset, element));
3839 
3840  /* remove element */
3841  --hashset->nelements;
3842 
3843  /* move other elements if necessary */
3844  while( TRUE ) /*lint !e716*/
3845  {
3846  uint32_t nextpos = (pos + 1) & mask;
3847 
3848  /* nothing to do since there is no chain that needs to be moved */
3849  if( hashset->slots[nextpos] == NULL )
3850  {
3851  hashset->slots[pos] = NULL;
3852  assert(!SCIPhashsetExists(hashset, element));
3853  return SCIP_OKAY;
3854  }
3855 
3856  /* check if the element is the start of a new chain and return if that is the case */
3857  if( hashSetDesiredPos(hashset, hashset->slots[nextpos]) == nextpos )
3858  {
3859  hashset->slots[pos] = NULL;
3860  assert(!SCIPhashsetExists(hashset, element));
3861  return SCIP_OKAY;
3862  }
3863 
3864  /* element should be moved to the left and next element needs to be checked */
3865  hashset->slots[pos] = hashset->slots[nextpos];
3866 
3867  pos = nextpos;
3868  }
3869 }
3870 
3871 /** prints statistics about hash set usage */
3873  SCIP_HASHSET* hashset, /**< hash set */
3874  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
3875  )
3876 {
3877  uint32_t maxprobelen = 0;
3878  uint64_t probelensum = 0;
3879  uint32_t nslots;
3880  uint32_t mask;
3881  uint32_t i;
3882 
3883  assert(hashset != NULL);
3884 
3885  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3886  mask = nslots - 1;
3887 
3888  /* compute the maximum and average probe length */
3889  for( i = 0; i < nslots; ++i )
3890  {
3891  if( hashset->slots[i] != NULL )
3892  {
3893  uint32_t probelen = ((hashSetDesiredPos(hashset, hashset->slots[i]) + nslots - i) & mask) + 1;
3894  probelensum += probelen;
3895  maxprobelen = MAX(probelen, maxprobelen);
3896  }
3897  }
3898 
3899  /* print general hash set statistics */
3900  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
3901  (unsigned int)hashset->nelements, (unsigned int)hashset->nelements,
3902  (unsigned int)nslots, 100.0*(SCIP_Real)hashset->nelements/(SCIP_Real)(nslots));
3903 
3904  /* if not empty print average and maximum probe length */
3905  if( hashset->nelements > 0 )
3906  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
3907  (SCIP_Real)(probelensum)/(SCIP_Real)hashset->nelements, (unsigned int)maxprobelen);
3908  SCIPmessagePrintInfo(messagehdlr, "\n");
3909 }
3910 
3911 /* In debug mode, the following methods are implemented as function calls to ensure
3912  * type validity.
3913  * In optimized mode, the methods are implemented as defines to improve performance.
3914  * However, we want to have them in the library anyways, so we have to undef the defines.
3915  */
3916 
3917 #undef SCIPhashsetIsEmpty
3918 #undef SCIPhashsetGetNElements
3919 #undef SCIPhashsetGetNSlots
3920 #undef SCIPhashsetGetSlots
3921 
3922 /** indicates whether a hash set has no entries */
3924  SCIP_HASHSET* hashset /**< hash set */
3925  )
3926 {
3927  return hashset->nelements == 0;
3928 }
3929 
3930 /** gives the number of elements in a hash set */
3932  SCIP_HASHSET* hashset /**< hash set */
3933  )
3934 {
3935  return (int)hashset->nelements;
3936 }
3937 
3938 /** gives the number of slots of a hash set */
3940  SCIP_HASHSET* hashset /**< hash set */
3941  )
3942 {
3943  return (int) (1u << (64 - hashset->shift));
3944 }
3945 
3946 /** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
3948  SCIP_HASHSET* hashset /**< hash set */
3949  )
3950 {
3951  return hashset->slots;
3952 }
3953 
3954 /** removes all entries in a hash set. */
3956  SCIP_HASHSET* hashset /**< hash set */
3957  )
3958 {
3959  BMSclearMemoryArray(hashset->slots, SCIPhashsetGetNSlots(hashset));
3960 
3961  hashset->nelements = 0;
3962 }
3963 
3964 /*
3965  * Dynamic Arrays
3966  */
3967 
3968 /** creates a dynamic array of real values */
3970  SCIP_REALARRAY** realarray, /**< pointer to store the real array */
3971  BMS_BLKMEM* blkmem /**< block memory */
3972  )
3973 {
3974  assert(realarray != NULL);
3975  assert(blkmem != NULL);
3976 
3977  SCIP_ALLOC( BMSallocBlockMemory(blkmem, realarray) );
3978  (*realarray)->blkmem = blkmem;
3979  (*realarray)->vals = NULL;
3980  (*realarray)->valssize = 0;
3981  (*realarray)->firstidx = -1;
3982  (*realarray)->minusedidx = INT_MAX;
3983  (*realarray)->maxusedidx = INT_MIN;
3984 
3985  return SCIP_OKAY;
3986 }
3987 
3988 /** creates a copy of a dynamic array of real values */
3990  SCIP_REALARRAY** realarray, /**< pointer to store the copied real array */
3991  BMS_BLKMEM* blkmem, /**< block memory */
3992  SCIP_REALARRAY* sourcerealarray /**< dynamic real array to copy */
3993  )
3994 {
3995  assert(realarray != NULL);
3996  assert(sourcerealarray != NULL);
3997 
3998  SCIP_CALL( SCIPrealarrayCreate(realarray, blkmem) );
3999  if( sourcerealarray->valssize > 0 )
4000  {
4001  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*realarray)->vals, sourcerealarray->vals, \
4002  sourcerealarray->valssize) );
4003  }
4004  (*realarray)->valssize = sourcerealarray->valssize;
4005  (*realarray)->firstidx = sourcerealarray->firstidx;
4006  (*realarray)->minusedidx = sourcerealarray->minusedidx;
4007  (*realarray)->maxusedidx = sourcerealarray->maxusedidx;
4008 
4009  return SCIP_OKAY;
4010 }
4011 
4012 /** frees a dynamic array of real values */
4014  SCIP_REALARRAY** realarray /**< pointer to the real array */
4015  )
4016 {
4017  assert(realarray != NULL);
4018  assert(*realarray != NULL);
4019 
4020  BMSfreeBlockMemoryArrayNull((*realarray)->blkmem, &(*realarray)->vals, (*realarray)->valssize);
4021  BMSfreeBlockMemory((*realarray)->blkmem, realarray);
4022 
4023  return SCIP_OKAY;
4024 }
4025 
4026 /** extends dynamic array to be able to store indices from minidx to maxidx */
4028  SCIP_REALARRAY* realarray, /**< dynamic real array */
4029  int arraygrowinit, /**< initial size of array */
4030  SCIP_Real arraygrowfac, /**< growing factor of array */
4031  int minidx, /**< smallest index to allocate storage for */
4032  int maxidx /**< largest index to allocate storage for */
4033  )
4034 {
4035  int nused;
4036  int nfree;
4037  int newfirstidx;
4038  int i;
4039 
4040  assert(realarray != NULL);
4041  assert(realarray->minusedidx == INT_MAX || realarray->firstidx >= 0);
4042  assert(realarray->maxusedidx == INT_MIN || realarray->firstidx >= 0);
4043  assert(realarray->minusedidx == INT_MAX || realarray->minusedidx >= realarray->firstidx);
4044  assert(realarray->maxusedidx == INT_MIN || realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4045  assert(0 <= minidx);
4046  assert(minidx <= maxidx);
4047 
4048  minidx = MIN(minidx, realarray->minusedidx);
4049  maxidx = MAX(maxidx, realarray->maxusedidx);
4050  assert(0 <= minidx);
4051  assert(minidx <= maxidx);
4052 
4053  SCIPdebugMessage("extending realarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4054  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, minidx, maxidx);
4055 
4056  /* check, whether we have to allocate additional memory, or shift the array */
4057  nused = maxidx - minidx + 1;
4058  if( nused > realarray->valssize )
4059  {
4060  SCIP_Real* newvals;
4061  int newvalssize;
4062 
4063  /* allocate new memory storage */
4064  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4065  SCIP_ALLOC( BMSallocBlockMemoryArray(realarray->blkmem, &newvals, newvalssize) );
4066  nfree = newvalssize - nused;
4067  newfirstidx = minidx - nfree/2;
4068  newfirstidx = MAX(newfirstidx, 0);
4069  assert(newfirstidx <= minidx);
4070  assert(maxidx < newfirstidx + newvalssize);
4071 
4072  /* initialize memory array by copying old values and setting new values to zero */
4073  if( realarray->firstidx != -1 )
4074  {
4075  for( i = 0; i < realarray->minusedidx - newfirstidx; ++i )
4076  newvals[i] = 0.0;
4077 
4078  /* check for possible overflow or negative value */
4079  assert(realarray->maxusedidx - realarray->minusedidx + 1 > 0);
4080 
4081  BMScopyMemoryArray(&newvals[realarray->minusedidx - newfirstidx],
4082  &(realarray->vals[realarray->minusedidx - realarray->firstidx]),
4083  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866 !e776*/
4084  for( i = realarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4085  newvals[i] = 0.0;
4086  }
4087  else
4088  {
4089  for( i = 0; i < newvalssize; ++i )
4090  newvals[i] = 0.0;
4091  }
4092 
4093  /* free old memory storage, and set the new array parameters */
4094  BMSfreeBlockMemoryArrayNull(realarray->blkmem, &realarray->vals, realarray->valssize);
4095  realarray->vals = newvals;
4096  realarray->valssize = newvalssize;
4097  realarray->firstidx = newfirstidx;
4098  }
4099  else if( realarray->firstidx == -1 )
4100  {
4101  /* a sufficiently large memory storage exists, but it was cleared */
4102  nfree = realarray->valssize - nused;
4103  assert(nfree >= 0);
4104  realarray->firstidx = minidx - nfree/2;
4105  assert(realarray->firstidx <= minidx);
4106  assert(maxidx < realarray->firstidx + realarray->valssize);
4107 #ifndef NDEBUG
4108  for( i = 0; i < realarray->valssize; ++i )
4109  assert(realarray->vals[i] == 0.0);
4110 #endif
4111  }
4112  else if( minidx < realarray->firstidx )
4113  {
4114  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4115  nfree = realarray->valssize - nused;
4116  assert(nfree >= 0);
4117  newfirstidx = minidx - nfree/2;
4118  newfirstidx = MAX(newfirstidx, 0);
4119  assert(newfirstidx <= minidx);
4120  assert(maxidx < newfirstidx + realarray->valssize);
4121 
4122  if( realarray->minusedidx <= realarray->maxusedidx )
4123  {
4124  int shift;
4125 
4126  assert(realarray->firstidx <= realarray->minusedidx);
4127  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4128 
4129  /* shift used part of array to the right */
4130  shift = realarray->firstidx - newfirstidx;
4131  assert(shift > 0);
4132  for( i = realarray->maxusedidx - realarray->firstidx; i >= realarray->minusedidx - realarray->firstidx; --i )
4133  {
4134  assert(0 <= i + shift && i + shift < realarray->valssize);
4135  realarray->vals[i + shift] = realarray->vals[i];
4136  }
4137  /* clear the formerly used head of the array */
4138  for( i = 0; i < shift; ++i )
4139  realarray->vals[realarray->minusedidx - realarray->firstidx + i] = 0.0;
4140  }
4141  realarray->firstidx = newfirstidx;
4142  }
4143  else if( maxidx >= realarray->firstidx + realarray->valssize )
4144  {
4145  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4146  nfree = realarray->valssize - nused;
4147  assert(nfree >= 0);
4148  newfirstidx = minidx - nfree/2;
4149  newfirstidx = MAX(newfirstidx, 0);
4150  assert(newfirstidx <= minidx);
4151  assert(maxidx < newfirstidx + realarray->valssize);
4152 
4153  if( realarray->minusedidx <= realarray->maxusedidx )
4154  {
4155  int shift;
4156 
4157  assert(realarray->firstidx <= realarray->minusedidx);
4158  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4159 
4160  /* shift used part of array to the left */
4161  shift = newfirstidx - realarray->firstidx;
4162  assert(shift > 0);
4163  for( i = realarray->minusedidx - realarray->firstidx; i <= realarray->maxusedidx - realarray->firstidx; ++i )
4164  {
4165  assert(0 <= i - shift && i - shift < realarray->valssize);
4166  realarray->vals[i - shift] = realarray->vals[i];
4167  }
4168  /* clear the formerly used tail of the array */
4169  for( i = 0; i < shift; ++i )
4170  realarray->vals[realarray->maxusedidx - realarray->firstidx - i] = 0.0;
4171  }
4172  realarray->firstidx = newfirstidx;
4173  }
4174 
4175  assert(minidx >= realarray->firstidx);
4176  assert(maxidx < realarray->firstidx + realarray->valssize);
4177 
4178  return SCIP_OKAY;
4179 }
4180 
4181 /** clears a dynamic real array */
4183  SCIP_REALARRAY* realarray /**< dynamic real array */
4184  )
4185 {
4186  assert(realarray != NULL);
4187 
4188  SCIPdebugMessage("clearing realarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4189  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx);
4190 
4191  if( realarray->minusedidx <= realarray->maxusedidx )
4192  {
4193  assert(realarray->firstidx <= realarray->minusedidx);
4194  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4195  assert(realarray->firstidx != -1);
4196  assert(realarray->valssize > 0);
4197 
4198  /* clear the used part of array */
4199  BMSclearMemoryArray(&realarray->vals[realarray->minusedidx - realarray->firstidx],
4200  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866*/
4201 
4202  /* mark the array cleared */
4203  realarray->minusedidx = INT_MAX;
4204  realarray->maxusedidx = INT_MIN;
4205  }
4206  assert(realarray->minusedidx == INT_MAX);
4207  assert(realarray->maxusedidx == INT_MIN);
4208 
4209  return SCIP_OKAY;
4210 }
4211 
4212 /** gets value of entry in dynamic array */
4214  SCIP_REALARRAY* realarray, /**< dynamic real array */
4215  int idx /**< array index to get value for */
4216  )
4217 {
4218  assert(realarray != NULL);
4219  assert(idx >= 0);
4220 
4221  if( idx < realarray->minusedidx || idx > realarray->maxusedidx )
4222  return 0.0;
4223  else
4224  {
4225  assert(realarray->vals != NULL);
4226  assert(idx - realarray->firstidx >= 0);
4227  assert(idx - realarray->firstidx < realarray->valssize);
4228 
4229  return realarray->vals[idx - realarray->firstidx];
4230  }
4231 }
4232 
4233 /** sets value of entry in dynamic array */
4235  SCIP_REALARRAY* realarray, /**< dynamic real array */
4236  int arraygrowinit, /**< initial size of array */
4237  SCIP_Real arraygrowfac, /**< growing factor of array */
4238  int idx, /**< array index to set value for */
4239  SCIP_Real val /**< value to set array index to */
4240  )
4241 {
4242  assert(realarray != NULL);
4243  assert(idx >= 0);
4244 
4245  SCIPdebugMessage("setting realarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %g\n",
4246  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, idx, val);
4247 
4248  if( val != 0.0 )
4249  {
4250  /* extend array to be able to store the index */
4251  SCIP_CALL( SCIPrealarrayExtend(realarray, arraygrowinit, arraygrowfac, idx, idx) );
4252  assert(idx >= realarray->firstidx);
4253  assert(idx < realarray->firstidx + realarray->valssize);
4254 
4255  /* set the array value of the index */
4256  realarray->vals[idx - realarray->firstidx] = val;
4257 
4258  /* update min/maxusedidx */
4259  realarray->minusedidx = MIN(realarray->minusedidx, idx);
4260  realarray->maxusedidx = MAX(realarray->maxusedidx, idx);
4261  }
4262  else if( idx >= realarray->firstidx && idx < realarray->firstidx + realarray->valssize )
4263  {
4264  /* set the array value of the index to zero */
4265  realarray->vals[idx - realarray->firstidx] = 0.0;
4266 
4267  /* check, if we can tighten the min/maxusedidx */
4268  if( idx == realarray->minusedidx )
4269  {
4270  assert(realarray->maxusedidx >= 0);
4271  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4272  do
4273  {
4274  realarray->minusedidx++;
4275  }
4276  while( realarray->minusedidx <= realarray->maxusedidx
4277  && realarray->vals[realarray->minusedidx - realarray->firstidx] == 0.0 );
4278 
4279  if( realarray->minusedidx > realarray->maxusedidx )
4280  {
4281  realarray->minusedidx = INT_MAX;
4282  realarray->maxusedidx = INT_MIN;
4283  }
4284  }
4285  else if( idx == realarray->maxusedidx )
4286  {
4287  assert(realarray->minusedidx >= 0);
4288  assert(realarray->minusedidx < realarray->maxusedidx);
4289  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4290  do
4291  {
4292  realarray->maxusedidx--;
4293  assert(realarray->minusedidx <= realarray->maxusedidx);
4294  }
4295  while( realarray->vals[realarray->maxusedidx - realarray->firstidx] == 0.0 );
4296  }
4297  }
4298 
4299  return SCIP_OKAY;
4300 }
4301 
4302 /** increases value of entry in dynamic array */
4304  SCIP_REALARRAY* realarray, /**< dynamic real array */
4305  int arraygrowinit, /**< initial size of array */
4306  SCIP_Real arraygrowfac, /**< growing factor of array */
4307  int idx, /**< array index to increase value for */
4308  SCIP_Real incval /**< value to increase array index */
4309  )
4310 {
4311  SCIP_Real oldval;
4312 
4313  oldval = SCIPrealarrayGetVal(realarray, idx);
4314  if( oldval != SCIP_INVALID ) /*lint !e777*/
4315  return SCIPrealarraySetVal(realarray, arraygrowinit, arraygrowfac, idx, oldval + incval);
4316  else
4317  return SCIP_OKAY;
4318 }
4319 
4320 /** returns the minimal index of all stored non-zero elements */
4322  SCIP_REALARRAY* realarray /**< dynamic real array */
4323  )
4324 {
4325  assert(realarray != NULL);
4326 
4327  return realarray->minusedidx;
4328 }
4329 
4330 /** returns the maximal index of all stored non-zero elements */
4332  SCIP_REALARRAY* realarray /**< dynamic real array */
4333  )
4334 {
4335  assert(realarray != NULL);
4336 
4337  return realarray->maxusedidx;
4338 }
4339 
4340 /** creates a dynamic array of int values */
4342  SCIP_INTARRAY** intarray, /**< pointer to store the int array */
4343  BMS_BLKMEM* blkmem /**< block memory */
4344  )
4345 {
4346  assert(intarray != NULL);
4347  assert(blkmem != NULL);
4348 
4349  SCIP_ALLOC( BMSallocBlockMemory(blkmem, intarray) );
4350  (*intarray)->blkmem = blkmem;
4351  (*intarray)->vals = NULL;
4352  (*intarray)->valssize = 0;
4353  (*intarray)->firstidx = -1;
4354  (*intarray)->minusedidx = INT_MAX;
4355  (*intarray)->maxusedidx = INT_MIN;
4356 
4357  return SCIP_OKAY;
4358 }
4359 
4360 /** creates a copy of a dynamic array of int values */
4362  SCIP_INTARRAY** intarray, /**< pointer to store the copied int array */
4363  BMS_BLKMEM* blkmem, /**< block memory */
4364  SCIP_INTARRAY* sourceintarray /**< dynamic int array to copy */
4365  )
4366 {
4367  assert(intarray != NULL);
4368  assert(sourceintarray != NULL);
4369 
4370  SCIP_CALL( SCIPintarrayCreate(intarray, blkmem) );
4371  if( sourceintarray->valssize > 0 )
4372  {
4373  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*intarray)->vals, sourceintarray->vals, sourceintarray->valssize) );
4374  }
4375  (*intarray)->valssize = sourceintarray->valssize;
4376  (*intarray)->firstidx = sourceintarray->firstidx;
4377  (*intarray)->minusedidx = sourceintarray->minusedidx;
4378  (*intarray)->maxusedidx = sourceintarray->maxusedidx;
4379 
4380  return SCIP_OKAY;
4381 }
4382 
4383 /** frees a dynamic array of int values */
4385  SCIP_INTARRAY** intarray /**< pointer to the int array */
4386  )
4387 {
4388  assert(intarray != NULL);
4389  assert(*intarray != NULL);
4390 
4391  BMSfreeBlockMemoryArrayNull((*intarray)->blkmem, &(*intarray)->vals, (*intarray)->valssize);
4392  BMSfreeBlockMemory((*intarray)->blkmem, intarray);
4393 
4394  return SCIP_OKAY;
4395 }
4396 
4397 /** extends dynamic array to be able to store indices from minidx to maxidx */
4399  SCIP_INTARRAY* intarray, /**< dynamic int array */
4400  int arraygrowinit, /**< initial size of array */
4401  SCIP_Real arraygrowfac, /**< growing factor of array */
4402  int minidx, /**< smallest index to allocate storage for */
4403  int maxidx /**< largest index to allocate storage for */
4404  )
4405 {
4406  int nused;
4407  int nfree;
4408  int newfirstidx;
4409  int i;
4410 
4411  assert(intarray != NULL);
4412  assert(intarray->minusedidx == INT_MAX || intarray->firstidx >= 0);
4413  assert(intarray->maxusedidx == INT_MIN || intarray->firstidx >= 0);
4414  assert(intarray->minusedidx == INT_MAX || intarray->minusedidx >= intarray->firstidx);
4415  assert(intarray->maxusedidx == INT_MIN || intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4416  assert(0 <= minidx);
4417  assert(minidx <= maxidx);
4418 
4419  minidx = MIN(minidx, intarray->minusedidx);
4420  maxidx = MAX(maxidx, intarray->maxusedidx);
4421  assert(0 <= minidx);
4422  assert(minidx <= maxidx);
4423 
4424  SCIPdebugMessage("extending intarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4425  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, minidx, maxidx);
4426 
4427  /* check, whether we have to allocate additional memory, or shift the array */
4428  nused = maxidx - minidx + 1;
4429  if( nused > intarray->valssize )
4430  {
4431  int* newvals;
4432  int newvalssize;
4433 
4434  /* allocate new memory storage */
4435  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4436  SCIP_ALLOC( BMSallocBlockMemoryArray(intarray->blkmem, &newvals, newvalssize) );
4437  nfree = newvalssize - nused;
4438  newfirstidx = minidx - nfree/2;
4439  newfirstidx = MAX(newfirstidx, 0);
4440  assert(newfirstidx <= minidx);
4441  assert(maxidx < newfirstidx + newvalssize);
4442 
4443  /* initialize memory array by copying old values and setting new values to zero */
4444  if( intarray->firstidx != -1 )
4445  {
4446  for( i = 0; i < intarray->minusedidx - newfirstidx; ++i )
4447  newvals[i] = 0;
4448 
4449  /* check for possible overflow or negative value */
4450  assert(intarray->maxusedidx - intarray->minusedidx + 1 > 0);
4451 
4452  BMScopyMemoryArray(&newvals[intarray->minusedidx - newfirstidx],
4453  &intarray->vals[intarray->minusedidx - intarray->firstidx],
4454  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866 !e776*/
4455  for( i = intarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4456  newvals[i] = 0;
4457  }
4458  else
4459  {
4460  for( i = 0; i < newvalssize; ++i )
4461  newvals[i] = 0;
4462  }
4463 
4464  /* free old memory storage, and set the new array parameters */
4465  BMSfreeBlockMemoryArrayNull(intarray->blkmem, &intarray->vals, intarray->valssize);
4466  intarray->vals = newvals;
4467  intarray->valssize = newvalssize;
4468  intarray->firstidx = newfirstidx;
4469  }
4470  else if( intarray->firstidx == -1 )
4471  {
4472  /* a sufficiently large memory storage exists, but it was cleared */
4473  nfree = intarray->valssize - nused;
4474  assert(nfree >= 0);
4475  intarray->firstidx = minidx - nfree/2;
4476  assert(intarray->firstidx <= minidx);
4477  assert(maxidx < intarray->firstidx + intarray->valssize);
4478 #ifndef NDEBUG
4479  for( i = 0; i < intarray->valssize; ++i )
4480  assert(intarray->vals[i] == 0);
4481 #endif
4482  }
4483  else if( minidx < intarray->firstidx )
4484  {
4485  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4486  nfree = intarray->valssize - nused;
4487  assert(nfree >= 0);
4488  newfirstidx = minidx - nfree/2;
4489  newfirstidx = MAX(newfirstidx, 0);
4490  assert(newfirstidx <= minidx);
4491  assert(maxidx < newfirstidx + intarray->valssize);
4492 
4493  if( intarray->minusedidx <= intarray->maxusedidx )
4494  {
4495  int shift;
4496 
4497  assert(intarray->firstidx <= intarray->minusedidx);
4498  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4499 
4500  /* shift used part of array to the right */
4501  shift = intarray->firstidx - newfirstidx;
4502  assert(shift > 0);
4503  for( i = intarray->maxusedidx - intarray->firstidx; i >= intarray->minusedidx - intarray->firstidx; --i )
4504  {
4505  assert(0 <= i + shift && i + shift < intarray->valssize);
4506  intarray->vals[i + shift] = intarray->vals[i];
4507  }
4508  /* clear the formerly used head of the array */
4509  for( i = 0; i < shift; ++i )
4510  intarray->vals[intarray->minusedidx - intarray->firstidx + i] = 0;
4511  }
4512  intarray->firstidx = newfirstidx;
4513  }
4514  else if( maxidx >= intarray->firstidx + intarray->valssize )
4515  {
4516  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4517  nfree = intarray->valssize - nused;
4518  assert(nfree >= 0);
4519  newfirstidx = minidx - nfree/2;
4520  newfirstidx = MAX(newfirstidx, 0);
4521  assert(newfirstidx <= minidx);
4522  assert(maxidx < newfirstidx + intarray->valssize);
4523 
4524  if( intarray->minusedidx <= intarray->maxusedidx )
4525  {
4526  int shift;
4527 
4528  assert(intarray->firstidx <= intarray->minusedidx);
4529  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4530 
4531  /* shift used part of array to the left */
4532  shift = newfirstidx - intarray->firstidx;
4533  assert(shift > 0);
4534  for( i = intarray->minusedidx - intarray->firstidx; i <= intarray->maxusedidx - intarray->firstidx; ++i )
4535  {
4536  assert(0 <= i - shift && i - shift < intarray->valssize);
4537  intarray->vals[i - shift] = intarray->vals[i];
4538  }
4539  /* clear the formerly used tail of the array */
4540  for( i = 0; i < shift; ++i )
4541  intarray->vals[intarray->maxusedidx - intarray->firstidx - i] = 0;
4542  }
4543  intarray->firstidx = newfirstidx;
4544  }
4545 
4546  assert(minidx >= intarray->firstidx);
4547  assert(maxidx < intarray->firstidx + intarray->valssize);
4548 
4549  return SCIP_OKAY;
4550 }
4551 
4552 /** clears a dynamic int array */
4554  SCIP_INTARRAY* intarray /**< dynamic int array */
4555  )
4556 {
4557  assert(intarray != NULL);
4558 
4559  SCIPdebugMessage("clearing intarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4560  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx);
4561 
4562  if( intarray->minusedidx <= intarray->maxusedidx )
4563  {
4564  assert(intarray->firstidx <= intarray->minusedidx);
4565  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4566  assert(intarray->firstidx != -1);
4567  assert(intarray->valssize > 0);
4568 
4569  /* clear the used part of array */
4570  BMSclearMemoryArray(&intarray->vals[intarray->minusedidx - intarray->firstidx],
4571  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866*/
4572 
4573  /* mark the array cleared */
4574  intarray->minusedidx = INT_MAX;
4575  intarray->maxusedidx = INT_MIN;
4576  }
4577  assert(intarray->minusedidx == INT_MAX);
4578  assert(intarray->maxusedidx == INT_MIN);
4579 
4580  return SCIP_OKAY;
4581 }
4582 
4583 /** gets value of entry in dynamic array */
4585  SCIP_INTARRAY* intarray, /**< dynamic int array */
4586  int idx /**< array index to get value for */
4587  )
4588 {
4589  assert(intarray != NULL);
4590  assert(idx >= 0);
4591 
4592  if( idx < intarray->minusedidx || idx > intarray->maxusedidx )
4593  return 0;
4594  else
4595  {
4596  assert(intarray->vals != NULL);
4597  assert(idx - intarray->firstidx >= 0);
4598  assert(idx - intarray->firstidx < intarray->valssize);
4599 
4600  return intarray->vals[idx - intarray->firstidx];
4601  }
4602 }
4603 
4604 /** sets value of entry in dynamic array */
4606  SCIP_INTARRAY* intarray, /**< dynamic int array */
4607  int arraygrowinit, /**< initial size of array */
4608  SCIP_Real arraygrowfac, /**< growing factor of array */
4609  int idx, /**< array index to set value for */
4610  int val /**< value to set array index to */
4611  )
4612 {
4613  assert(intarray != NULL);
4614  assert(idx >= 0);
4615 
4616  SCIPdebugMessage("setting intarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %d\n",
4617  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, idx, val);
4618 
4619  if( val != 0 )
4620  {
4621  /* extend array to be able to store the index */
4622  SCIP_CALL( SCIPintarrayExtend(intarray, arraygrowinit, arraygrowfac, idx, idx) );
4623  assert(idx >= intarray->firstidx);
4624  assert(idx < intarray->firstidx + intarray->valssize);
4625 
4626  /* set the array value of the index */
4627  intarray->vals[idx - intarray->firstidx] = val;
4628 
4629  /* update min/maxusedidx */
4630  intarray->minusedidx = MIN(intarray->minusedidx, idx);
4631  intarray->maxusedidx = MAX(intarray->maxusedidx, idx);
4632  }
4633  else if( idx >= intarray->firstidx && idx < intarray->firstidx + intarray->valssize )
4634  {
4635  /* set the array value of the index to zero */
4636  intarray->vals[idx - intarray->firstidx] = 0;
4637 
4638  /* check, if we can tighten the min/maxusedidx */
4639  if( idx == intarray->minusedidx )
4640  {
4641  assert(intarray->maxusedidx >= 0);
4642  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4643  do
4644  {
4645  intarray->minusedidx++;
4646  }
4647  while( intarray->minusedidx <= intarray->maxusedidx
4648  && intarray->vals[intarray->minusedidx - intarray->firstidx] == 0 );
4649  if( intarray->minusedidx > intarray->maxusedidx )
4650  {
4651  intarray->minusedidx = INT_MAX;
4652  intarray->maxusedidx = INT_MIN;
4653  }
4654  }
4655  else if( idx == intarray->maxusedidx )
4656  {
4657  assert(intarray->minusedidx >= 0);
4658  assert(intarray->minusedidx < intarray->maxusedidx);
4659  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4660  do
4661  {
4662  intarray->maxusedidx--;
4663  assert(intarray->minusedidx <= intarray->maxusedidx);
4664  }
4665  while( intarray->vals[intarray->maxusedidx - intarray->firstidx] == 0 );
4666  }
4667  }
4668 
4669  return SCIP_OKAY;
4670 }
4671 
4672 /** increases value of entry in dynamic array */
4674  SCIP_INTARRAY* intarray, /**< dynamic int array */
4675  int arraygrowinit, /**< initial size of array */
4676  SCIP_Real arraygrowfac, /**< growing factor of array */
4677  int idx, /**< array index to increase value for */
4678  int incval /**< value to increase array index */
4679  )
4680 {
4681  return SCIPintarraySetVal(intarray, arraygrowinit, arraygrowfac, idx, SCIPintarrayGetVal(intarray, idx) + incval);
4682 }
4683 
4684 /** returns the minimal index of all stored non-zero elements */
4686  SCIP_INTARRAY* intarray /**< dynamic int array */
4687  )
4688 {
4689  assert(intarray != NULL);
4690 
4691  return intarray->minusedidx;
4692 }
4693 
4694 /** returns the maximal index of all stored non-zero elements */
4696  SCIP_INTARRAY* intarray /**< dynamic int array */
4697  )
4698 {
4699  assert(intarray != NULL);
4700 
4701  return intarray->maxusedidx;
4702 }
4703 
4704 
4705 /** creates a dynamic array of bool values */
4707  SCIP_BOOLARRAY** boolarray, /**< pointer to store the bool array */
4708  BMS_BLKMEM* blkmem /**< block memory */
4709  )
4710 {
4711  assert(boolarray != NULL);
4712  assert(blkmem != NULL);
4713 
4714  SCIP_ALLOC( BMSallocBlockMemory(blkmem, boolarray) );
4715  (*boolarray)->blkmem = blkmem;
4716  (*boolarray)->vals = NULL;
4717  (*boolarray)->valssize = 0;
4718  (*boolarray)->firstidx = -1;
4719  (*boolarray)->minusedidx = INT_MAX;
4720  (*boolarray)->maxusedidx = INT_MIN;
4721 
4722  return SCIP_OKAY;
4723 }
4724 
4725 /** creates a copy of a dynamic array of bool values */
4727  SCIP_BOOLARRAY** boolarray, /**< pointer to store the copied bool array */
4728  BMS_BLKMEM* blkmem, /**< block memory */
4729  SCIP_BOOLARRAY* sourceboolarray /**< dynamic bool array to copy */
4730  )
4731 {
4732  assert(boolarray != NULL);
4733  assert(sourceboolarray != NULL);
4734 
4735  SCIP_CALL( SCIPboolarrayCreate(boolarray, blkmem) );
4736  if( sourceboolarray->valssize > 0 )
4737  {
4738  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*boolarray)->vals, sourceboolarray->vals, \
4739  sourceboolarray->valssize) );
4740  }
4741  (*boolarray)->valssize = sourceboolarray->valssize;
4742  (*boolarray)->firstidx = sourceboolarray->firstidx;
4743  (*boolarray)->minusedidx = sourceboolarray->minusedidx;
4744  (*boolarray)->maxusedidx = sourceboolarray->maxusedidx;
4745 
4746  return SCIP_OKAY;
4747 }
4748 
4749 /** frees a dynamic array of bool values */
4751  SCIP_BOOLARRAY** boolarray /**< pointer to the bool array */
4752  )
4753 {
4754  assert(boolarray != NULL);
4755  assert(*boolarray != NULL);
4756 
4757  BMSfreeBlockMemoryArrayNull((*boolarray)->blkmem, &(*boolarray)->vals, (*boolarray)->valssize);
4758  BMSfreeBlockMemory((*boolarray)->blkmem, boolarray);
4759 
4760  return SCIP_OKAY;
4761 }
4762 
4763 /** extends dynamic array to be able to store indices from minidx to maxidx */
4765  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4766  int arraygrowinit, /**< initial size of array */
4767  SCIP_Real arraygrowfac, /**< growing factor of array */
4768  int minidx, /**< smallest index to allocate storage for */
4769  int maxidx /**< largest index to allocate storage for */
4770  )
4771 {
4772  int nused;
4773  int nfree;
4774  int newfirstidx;
4775  int i;
4776 
4777  assert(boolarray != NULL);
4778  assert(boolarray->minusedidx == INT_MAX || boolarray->firstidx >= 0);
4779  assert(boolarray->maxusedidx == INT_MIN || boolarray->firstidx >= 0);
4780  assert(boolarray->minusedidx == INT_MAX || boolarray->minusedidx >= boolarray->firstidx);
4781  assert(boolarray->maxusedidx == INT_MIN || boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4782  assert(0 <= minidx);
4783  assert(minidx <= maxidx);
4784 
4785  minidx = MIN(minidx, boolarray->minusedidx);
4786  maxidx = MAX(maxidx, boolarray->maxusedidx);
4787  assert(0 <= minidx);
4788  assert(minidx <= maxidx);
4789 
4790  SCIPdebugMessage("extending boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4791  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, minidx, maxidx);
4792 
4793  /* check, whether we have to allocate additional memory, or shift the array */
4794  nused = maxidx - minidx + 1;
4795  if( nused > boolarray->valssize )
4796  {
4797  SCIP_Bool* newvals;
4798  int newvalssize;
4799 
4800  /* allocate new memory storage */
4801  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4802  SCIP_ALLOC( BMSallocBlockMemoryArray(boolarray->blkmem, &newvals, newvalssize) );
4803  nfree = newvalssize - nused;
4804  newfirstidx = minidx - nfree/2;
4805  newfirstidx = MAX(newfirstidx, 0);
4806  assert(newfirstidx <= minidx);
4807  assert(maxidx < newfirstidx + newvalssize);
4808 
4809  /* initialize memory array by copying old values and setting new values to zero */
4810  if( boolarray->firstidx != -1 )
4811  {
4812  for( i = 0; i < boolarray->minusedidx - newfirstidx; ++i )
4813  newvals[i] = FALSE;
4814 
4815  /* check for possible overflow or negative value */
4816  assert(boolarray->maxusedidx - boolarray->minusedidx + 1 > 0);
4817 
4818  BMScopyMemoryArray(&newvals[boolarray->minusedidx - newfirstidx],
4819  &boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4820  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866 !e776*/
4821  for( i = boolarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4822  newvals[i] = FALSE;
4823  }
4824  else
4825  {
4826  for( i = 0; i < newvalssize; ++i )
4827  newvals[i] = FALSE;
4828  }
4829 
4830  /* free old memory storage, and set the new array parameters */
4831  BMSfreeBlockMemoryArrayNull(boolarray->blkmem, &boolarray->vals, boolarray->valssize);
4832  boolarray->vals = newvals;
4833  boolarray->valssize = newvalssize;
4834  boolarray->firstidx = newfirstidx;
4835  }
4836  else if( boolarray->firstidx == -1 )
4837  {
4838  /* a sufficiently large memory storage exists, but it was cleared */
4839  nfree = boolarray->valssize - nused;
4840  assert(nfree >= 0);
4841  boolarray->firstidx = minidx - nfree/2;
4842  assert(boolarray->firstidx <= minidx);
4843  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4844 #ifndef NDEBUG
4845  for( i = 0; i < boolarray->valssize; ++i )
4846  assert(boolarray->vals[i] == FALSE);
4847 #endif
4848  }
4849  else if( minidx < boolarray->firstidx )
4850  {
4851  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4852  nfree = boolarray->valssize - nused;
4853  assert(nfree >= 0);
4854  newfirstidx = minidx - nfree/2;
4855  newfirstidx = MAX(newfirstidx, 0);
4856  assert(newfirstidx <= minidx);
4857  assert(maxidx < newfirstidx + boolarray->valssize);
4858 
4859  if( boolarray->minusedidx <= boolarray->maxusedidx )
4860  {
4861  int shift;
4862 
4863  assert(boolarray->firstidx <= boolarray->minusedidx);
4864  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4865 
4866  /* shift used part of array to the right */
4867  shift = boolarray->firstidx - newfirstidx;
4868  assert(shift > 0);
4869  for( i = boolarray->maxusedidx - boolarray->firstidx; i >= boolarray->minusedidx - boolarray->firstidx; --i )
4870  {
4871  assert(0 <= i + shift && i + shift < boolarray->valssize);
4872  boolarray->vals[i + shift] = boolarray->vals[i];
4873  }
4874  /* clear the formerly used head of the array */
4875  for( i = 0; i < shift; ++i )
4876  boolarray->vals[boolarray->minusedidx - boolarray->firstidx + i] = FALSE;
4877  }
4878  boolarray->firstidx = newfirstidx;
4879  }
4880  else if( maxidx >= boolarray->firstidx + boolarray->valssize )
4881  {
4882  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4883  nfree = boolarray->valssize - nused;
4884  assert(nfree >= 0);
4885  newfirstidx = minidx - nfree/2;
4886  newfirstidx = MAX(newfirstidx, 0);
4887  assert(newfirstidx <= minidx);
4888  assert(maxidx < newfirstidx + boolarray->valssize);
4889 
4890  if( boolarray->minusedidx <= boolarray->maxusedidx )
4891  {
4892  int shift;
4893 
4894  assert(boolarray->firstidx <= boolarray->minusedidx);
4895  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4896 
4897  /* shift used part of array to the left */
4898  shift = newfirstidx - boolarray->firstidx;
4899  assert(shift > 0);
4900 
4901  assert(0 <= boolarray->minusedidx - boolarray->firstidx - shift);
4902  assert(boolarray->maxusedidx - boolarray->firstidx - shift < boolarray->valssize);
4903  BMSmoveMemoryArray(&(boolarray->vals[boolarray->minusedidx - boolarray->firstidx - shift]),
4904  &(boolarray->vals[boolarray->minusedidx - boolarray->firstidx]),
4905  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4906 
4907  /* clear the formerly used tail of the array */
4908  for( i = 0; i < shift; ++i )
4909  boolarray->vals[boolarray->maxusedidx - boolarray->firstidx - i] = FALSE;
4910  }
4911  boolarray->firstidx = newfirstidx;
4912  }
4913 
4914  assert(minidx >= boolarray->firstidx);
4915  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4916 
4917  return SCIP_OKAY;
4918 }
4919 
4920 /** clears a dynamic bool array */
4922  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4923  )
4924 {
4925  assert(boolarray != NULL);
4926 
4927  SCIPdebugMessage("clearing boolarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4928  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx);
4929 
4930  if( boolarray->minusedidx <= boolarray->maxusedidx )
4931  {
4932  assert(boolarray->firstidx <= boolarray->minusedidx);
4933  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4934  assert(boolarray->firstidx != -1);
4935  assert(boolarray->valssize > 0);
4936 
4937  /* clear the used part of array */
4938  BMSclearMemoryArray(&boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4939  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4940 
4941  /* mark the array cleared */
4942  boolarray->minusedidx = INT_MAX;
4943  boolarray->maxusedidx = INT_MIN;
4944  }
4945  assert(boolarray->minusedidx == INT_MAX);
4946  assert(boolarray->maxusedidx == INT_MIN);
4947 
4948  return SCIP_OKAY;
4949 }
4950 
4951 /** gets value of entry in dynamic array */
4953  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4954  int idx /**< array index to get value for */
4955  )
4956 {
4957  assert(boolarray != NULL);
4958  assert(idx >= 0);
4959 
4960  if( idx < boolarray->minusedidx || idx > boolarray->maxusedidx )
4961  return FALSE;
4962  else
4963  {
4964  assert(boolarray->vals != NULL);
4965  assert(idx - boolarray->firstidx >= 0);
4966  assert(idx - boolarray->firstidx < boolarray->valssize);
4967 
4968  return boolarray->vals[idx - boolarray->firstidx];
4969  }
4970 }
4971 
4972 /** sets value of entry in dynamic array */
4974  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4975  int arraygrowinit, /**< initial size of array */
4976  SCIP_Real arraygrowfac, /**< growing factor of array */
4977  int idx, /**< array index to set value for */
4978  SCIP_Bool val /**< value to set array index to */
4979  )
4980 {
4981  assert(boolarray != NULL);
4982  assert(idx >= 0);
4983 
4984  SCIPdebugMessage("setting boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %u\n",
4985  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, idx, val);
4986 
4987  if( val != FALSE )
4988  {
4989  /* extend array to be able to store the index */
4990  SCIP_CALL( SCIPboolarrayExtend(boolarray, arraygrowinit, arraygrowfac, idx, idx) );
4991  assert(idx >= boolarray->firstidx);
4992  assert(idx < boolarray->firstidx + boolarray->valssize);
4993 
4994  /* set the array value of the index */
4995  boolarray->vals[idx - boolarray->firstidx] = val;
4996 
4997  /* update min/maxusedidx */
4998  boolarray->minusedidx = MIN(boolarray->minusedidx, idx);
4999  boolarray->maxusedidx = MAX(boolarray->maxusedidx, idx);
5000  }
5001  else if( idx >= boolarray->firstidx && idx < boolarray->firstidx + boolarray->valssize )
5002  {
5003  /* set the array value of the index to zero */
5004  boolarray->vals[idx - boolarray->firstidx] = FALSE;
5005 
5006  /* check, if we can tighten the min/maxusedidx */
5007  if( idx == boolarray->minusedidx )
5008  {
5009  assert(boolarray->maxusedidx >= 0);
5010  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
5011  do
5012  {
5013  boolarray->minusedidx++;
5014  }
5015  while( boolarray->minusedidx <= boolarray->maxusedidx
5016  && boolarray->vals[boolarray->minusedidx - boolarray->firstidx] == FALSE );
5017  if( boolarray->minusedidx > boolarray->maxusedidx )
5018  {
5019  boolarray->minusedidx = INT_MAX;
5020  boolarray->maxusedidx = INT_MIN;
5021  }
5022  }
5023  else if( idx == boolarray->maxusedidx )
5024  {
5025  assert(boolarray->minusedidx >= 0);
5026  assert(boolarray->minusedidx < boolarray->maxusedidx);
5027  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
5028  do
5029  {
5030  boolarray->maxusedidx--;
5031  assert(boolarray->minusedidx <= boolarray->maxusedidx);
5032  }
5033  while( boolarray->vals[boolarray->maxusedidx - boolarray->firstidx] == FALSE );
5034  }
5035  }
5036 
5037  return SCIP_OKAY;
5038 }
5039 
5040 /** returns the minimal index of all stored non-zero elements */
5042  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
5043  )
5044 {
5045  assert(boolarray != NULL);
5046 
5047  return boolarray->minusedidx;
5048 }
5049 
5050 /** returns the maximal index of all stored non-zero elements */
5052  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
5053  )
5054 {
5055  assert(boolarray != NULL);
5056 
5057  return boolarray->maxusedidx;
5058 }
5059 
5060 
5061 /** creates a dynamic array of pointer values */
5063  SCIP_PTRARRAY** ptrarray, /**< pointer to store the ptr array */
5064  BMS_BLKMEM* blkmem /**< block memory */
5065  )
5066 {
5067  assert(ptrarray != NULL);
5068  assert(blkmem != NULL);
5069 
5070  SCIP_ALLOC( BMSallocBlockMemory(blkmem, ptrarray) );
5071  (*ptrarray)->blkmem = blkmem;
5072  (*ptrarray)->vals = NULL;
5073  (*ptrarray)->valssize = 0;
5074  (*ptrarray)->firstidx = -1;
5075  (*ptrarray)->minusedidx = INT_MAX;
5076  (*ptrarray)->maxusedidx = INT_MIN;
5077 
5078  return SCIP_OKAY;
5079 }
5080 
5081 /** creates a copy of a dynamic array of pointer values */
5083  SCIP_PTRARRAY** ptrarray, /**< pointer to store the copied ptr array */
5084  BMS_BLKMEM* blkmem, /**< block memory */
5085  SCIP_PTRARRAY* sourceptrarray /**< dynamic ptr array to copy */
5086  )
5087 {
5088  assert(ptrarray != NULL);
5089  assert(sourceptrarray != NULL);
5090 
5091  SCIP_CALL( SCIPptrarrayCreate(ptrarray, blkmem) );
5092  if( sourceptrarray->valssize > 0 )
5093  {
5094  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*ptrarray)->vals, sourceptrarray->vals, sourceptrarray->valssize) );
5095  }
5096  (*ptrarray)->valssize = sourceptrarray->valssize;
5097  (*ptrarray)->firstidx = sourceptrarray->firstidx;
5098  (*ptrarray)->minusedidx = sourceptrarray->minusedidx;
5099  (*ptrarray)->maxusedidx = sourceptrarray->maxusedidx;
5100 
5101  return SCIP_OKAY;
5102 }
5103 
5104 /** frees a dynamic array of pointer values */
5106  SCIP_PTRARRAY** ptrarray /**< pointer to the ptr array */
5107  )
5108 {
5109  assert(ptrarray != NULL);
5110  assert(*ptrarray != NULL);
5111 
5112  BMSfreeBlockMemoryArrayNull((*ptrarray)->blkmem, &(*ptrarray)->vals, (*ptrarray)->valssize);
5113  BMSfreeBlockMemory((*ptrarray)->blkmem, ptrarray);
5114 
5115  return SCIP_OKAY;
5116 }
5117 
5118 /** extends dynamic array to be able to store indices from minidx to maxidx */
5120  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
5121  int arraygrowinit, /**< initial size of array */
5122  SCIP_Real arraygrowfac, /**< growing factor of array */
5123  int minidx, /**< smallest index to allocate storage for */
5124  int maxidx /**< largest index to allocate storage for */
5125  )
5126 {
5127  int nused;
5128  int nfree;
5129  int newfirstidx;
5130  int i;
5131 
5132  assert(ptrarray != NULL);
5133  assert(ptrarray->minusedidx == INT_MAX || ptrarray->firstidx >= 0);
5134  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->firstidx >= 0);
5135  assert(ptrarray->minusedidx == INT_MAX || ptrarray->minusedidx >= ptrarray->firstidx);
5136  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5137  assert(0 <= minidx);
5138  assert(minidx <= maxidx);
5139 
5140  minidx = MIN(minidx, ptrarray->minusedidx);
5141  maxidx = MAX(maxidx, ptrarray->maxusedidx);
5142  assert(0 <= minidx);
5143  assert(minidx <= maxidx);
5144 
5145  SCIPdebugMessage("extending ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
5146  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, minidx, maxidx);
5147 
5148  /* check, whether we have to allocate additional memory, or shift the array */
5149  nused = maxidx - minidx + 1;
5150  if( nused > ptrarray->valssize )
5151  {
5152  void** newvals;
5153  int newvalssize;
5154 
5155  /* allocate new memory storage */
5156  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
5157  SCIP_ALLOC( BMSallocBlockMemoryArray(ptrarray->blkmem, &newvals, newvalssize) );
5158  nfree = newvalssize - nused;
5159  newfirstidx = minidx - nfree/2;
5160  newfirstidx = MAX(newfirstidx, 0);
5161  assert(newfirstidx <= minidx);
5162  assert(maxidx < newfirstidx + newvalssize);
5163 
5164  /* initialize memory array by copying old values and setting new values to zero */
5165  if( ptrarray->firstidx != -1 )
5166  {
5167  for( i = 0; i < ptrarray->minusedidx - newfirstidx; ++i )
5168  newvals[i] = NULL;
5169 
5170  /* check for possible overflow or negative value */
5171  assert(ptrarray->maxusedidx - ptrarray->minusedidx + 1 > 0);
5172 
5173  BMScopyMemoryArray(&newvals[ptrarray->minusedidx - newfirstidx],
5174  &(ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx]),
5175  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866 !e776*/
5176  for( i = ptrarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
5177  newvals[i] = NULL;
5178  }
5179  else
5180  {
5181  for( i = 0; i < newvalssize; ++i )
5182  newvals[i] = NULL;
5183  }
5184 
5185  /* free old memory storage, and set the new array parameters */
5186  BMSfreeBlockMemoryArrayNull(ptrarray->blkmem, &ptrarray->vals, ptrarray->valssize);
5187  ptrarray->vals = newvals;
5188  ptrarray->valssize = newvalssize;
5189  ptrarray->firstidx = newfirstidx;
5190  }
5191  else if( ptrarray->firstidx == -1 )
5192  {
5193  /* a sufficiently large memory storage exists, but it was cleared */
5194  nfree = ptrarray->valssize - nused;
5195  assert(nfree >= 0);
5196  ptrarray->firstidx = minidx - nfree/2;
5197  assert(ptrarray->firstidx <= minidx);
5198  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
5199 #ifndef NDEBUG
5200  for( i = 0; i < ptrarray->valssize; ++i )
5201  assert(ptrarray->vals[i] == NULL);
5202 #endif
5203  }
5204  else if( minidx < ptrarray->firstidx )
5205  {
5206  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
5207  nfree = ptrarray->valssize - nused;
5208  assert(nfree >= 0);
5209  newfirstidx = minidx - nfree/2;
5210  newfirstidx = MAX(newfirstidx, 0);
5211  assert(newfirstidx <= minidx);
5212  assert(maxidx < newfirstidx + ptrarray->valssize);
5213 
5214  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5215  {
5216  int shift;
5217 
5218  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5219  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5220 
5221  /* shift used part of array to the right */
5222  shift = ptrarray->firstidx - newfirstidx;
5223  assert(shift > 0);
5224  for( i = ptrarray->maxusedidx - ptrarray->firstidx; i >= ptrarray->minusedidx - ptrarray->firstidx; --i )
5225  {
5226  assert(0 <= i + shift && i + shift < ptrarray->valssize);
5227  ptrarray->vals[i + shift] = ptrarray->vals[i];
5228  }
5229  /* clear the formerly used head of the array */
5230  for( i = 0; i < shift; ++i )
5231  ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx + i] = NULL;
5232  }
5233  ptrarray->firstidx = newfirstidx;
5234  }
5235  else if( maxidx >= ptrarray->firstidx + ptrarray->valssize )
5236  {
5237  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
5238  nfree = ptrarray->valssize - nused;
5239  assert(nfree >= 0);
5240  newfirstidx = minidx - nfree/2;
5241  newfirstidx = MAX(newfirstidx, 0);
5242  assert(newfirstidx <= minidx);
5243  assert(maxidx < newfirstidx + ptrarray->valssize);
5244 
5245  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5246  {
5247  int shift;
5248 
5249  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5250  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5251 
5252  /* shift used part of array to the left */
5253  shift = newfirstidx - ptrarray->firstidx;
5254  assert(shift > 0);
5255  for( i = ptrarray->minusedidx - ptrarray->firstidx; i <= ptrarray->maxusedidx - ptrarray->firstidx; ++i )
5256  {
5257  assert(0 <= i - shift && i - shift < ptrarray->valssize);
5258  ptrarray->vals[i - shift] = ptrarray->vals[i];
5259  }
5260  /* clear the formerly used tail of the array */
5261  for( i = 0; i < shift; ++i )
5262  ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx - i] = NULL;
5263  }
5264  ptrarray->firstidx = newfirstidx;
5265  }
5266 
5267  assert(minidx >= ptrarray->firstidx);
5268  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
5269 
5270  return SCIP_OKAY;
5271 }
5272 
5273 /** clears a dynamic pointer array */
5275  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5276  )
5277 {
5278  assert(ptrarray != NULL);
5279 
5280  SCIPdebugMessage("clearing ptrarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
5281  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx);
5282 
5283  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5284  {
5285  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5286  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5287  assert(ptrarray->firstidx != -1);
5288  assert(ptrarray->valssize > 0);
5289 
5290  /* clear the used part of array */
5291  BMSclearMemoryArray(&ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx],
5292  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866*/
5293 
5294  /* mark the array cleared */
5295  ptrarray->minusedidx = INT_MAX;
5296  ptrarray->maxusedidx = INT_MIN;
5297  }
5298  assert(ptrarray->minusedidx == INT_MAX);
5299  assert(ptrarray->maxusedidx == INT_MIN);
5300 
5301  return SCIP_OKAY;
5302 }
5303 
5304 /** gets value of entry in dynamic array */
5306  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
5307  int idx /**< array index to get value for */
5308  )
5309 {
5310  assert(ptrarray != NULL);
5311  assert(idx >= 0);
5312 
5313  if( idx < ptrarray->minusedidx || idx > ptrarray->maxusedidx )
5314  return NULL;
5315  else
5316  {
5317  assert(ptrarray->vals != NULL);
5318  assert(idx - ptrarray->firstidx >= 0);
5319  assert(idx - ptrarray->firstidx < ptrarray->valssize);
5320 
5321  return ptrarray->vals[idx - ptrarray->firstidx];
5322  }
5323 }
5324 
5325 /** sets value of entry in dynamic array */
5327  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
5328  int arraygrowinit, /**< initial size of array */
5329  SCIP_Real arraygrowfac, /**< growing factor of array */
5330  int idx, /**< array index to set value for */
5331  void* val /**< value to set array index to */
5332  )
5333 {
5334  assert(ptrarray != NULL);
5335  assert(idx >= 0);
5336 
5337  SCIPdebugMessage("setting ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %p\n",
5338  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, idx, val);
5339 
5340  if( val != NULL )
5341  {
5342  /* extend array to be able to store the index */
5343  SCIP_CALL( SCIPptrarrayExtend(ptrarray, arraygrowinit, arraygrowfac, idx, idx) );
5344  assert(idx >= ptrarray->firstidx);
5345  assert(idx < ptrarray->firstidx + ptrarray->valssize);
5346 
5347  /* set the array value of the index */
5348  ptrarray->vals[idx - ptrarray->firstidx] = val;
5349 
5350  /* update min/maxusedidx */
5351  ptrarray->minusedidx = MIN(ptrarray->minusedidx, idx);
5352  ptrarray->maxusedidx = MAX(ptrarray->maxusedidx, idx);
5353  }
5354  else if( idx >= ptrarray->firstidx && idx < ptrarray->firstidx + ptrarray->valssize )
5355  {
5356  /* set the array value of the index to zero */
5357  ptrarray->vals[idx - ptrarray->firstidx] = NULL;
5358 
5359  /* check, if we can tighten the min/maxusedidx */
5360  if( idx == ptrarray->minusedidx )
5361  {
5362  assert(ptrarray->maxusedidx >= 0);
5363  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5364  do
5365  {
5366  ptrarray->minusedidx++;
5367  }
5368  while( ptrarray->minusedidx <= ptrarray->maxusedidx
5369  && ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx] == NULL );
5370  if( ptrarray->minusedidx > ptrarray->maxusedidx )
5371  {
5372  ptrarray->minusedidx = INT_MAX;
5373  ptrarray->maxusedidx = INT_MIN;
5374  }
5375  }
5376  else if( idx == ptrarray->maxusedidx )
5377  {
5378  assert(ptrarray->minusedidx >= 0);
5379  assert(ptrarray->minusedidx < ptrarray->maxusedidx);
5380  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5381  do
5382  {
5383  ptrarray->maxusedidx--;
5384  assert(ptrarray->minusedidx <= ptrarray->maxusedidx);
5385  }
5386  while( ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx] == NULL );
5387  }
5388  }
5389 
5390  return SCIP_OKAY;
5391 }
5392 
5393 /** returns the minimal index of all stored non-zero elements */
5395  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5396  )
5397 {
5398  assert(ptrarray != NULL);
5399 
5400  return ptrarray->minusedidx;
5401 }
5402 
5403 /** returns the maximal index of all stored non-zero elements */
5405  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5406  )
5407 {
5408  assert(ptrarray != NULL);
5409 
5410  return ptrarray->maxusedidx;
5411 }
5412 
5413 
5414 /*
5415  * Sorting algorithms
5416  */
5417 
5418 /** default comparer for integers */
5419 SCIP_DECL_SORTPTRCOMP(SCIPsortCompInt)
5420 {
5421  int value1;
5422  int value2;
5423 
5424  value1 = (int)(size_t)elem1;
5425  value2 = (int)(size_t)elem2;
5426 
5427  if( value1 < value2 )
5428  return -1;
5429 
5430  if( value2 < value1 )
5431  return 1;
5432 
5433  return 0;
5434 }
5435 
5436 /* first all upwards-sorting methods */
5437 
5438 /** sort an indexed element set in non-decreasing order, resulting in a permutation index array */
5440  int* perm, /**< pointer to store the resulting permutation */
5441  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
5442  void* dataptr, /**< pointer to data field that is given to the external compare method */
5443  int len /**< number of elements to be sorted (valid index range) */
5444  )
5445 {
5446  int pos;
5447 
5448  assert(indcomp != NULL);
5449  assert(len == 0 || perm != NULL);
5450 
5451  /* create identity permutation */
5452  for( pos = 0; pos < len; ++pos )
5453  perm[pos] = pos;
5454 
5455  SCIPsortInd(perm, indcomp, dataptr, len);
5456 }
5457 
5458 /* SCIPsortInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5459 #define SORTTPL_NAMEEXT Ind
5460 #define SORTTPL_KEYTYPE int
5461 #define SORTTPL_INDCOMP
5462 #include "scip/sorttpl.c" /*lint !e451*/
5463 
5464 
5465 /* SCIPsortPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5466 #define SORTTPL_NAMEEXT Ptr
5467 #define SORTTPL_KEYTYPE void*
5468 #define SORTTPL_PTRCOMP
5469 #include "scip/sorttpl.c" /*lint !e451*/
5470 
5471 
5472 /* SCIPsortPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5473 #define SORTTPL_NAMEEXT PtrPtr
5474 #define SORTTPL_KEYTYPE void*
5475 #define SORTTPL_FIELD1TYPE void*
5476 #define SORTTPL_PTRCOMP
5477 #include "scip/sorttpl.c" /*lint !e451*/
5478 
5479 
5480 /* SCIPsortPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5481 #define SORTTPL_NAMEEXT PtrReal
5482 #define SORTTPL_KEYTYPE void*
5483 #define SORTTPL_FIELD1TYPE SCIP_Real
5484 #define SORTTPL_PTRCOMP
5485 #include "scip/sorttpl.c" /*lint !e451*/
5486 
5487 
5488 /* SCIPsortPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5489 #define SORTTPL_NAMEEXT PtrInt
5490 #define SORTTPL_KEYTYPE void*
5491 #define SORTTPL_FIELD1TYPE int
5492 #define SORTTPL_PTRCOMP
5493 #include "scip/sorttpl.c" /*lint !e451*/
5494 
5495 
5496 /* SCIPsortPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5497 #define SORTTPL_NAMEEXT PtrBool
5498 #define SORTTPL_KEYTYPE void*
5499 #define SORTTPL_FIELD1TYPE SCIP_Bool
5500 #define SORTTPL_PTRCOMP
5501 #include "scip/sorttpl.c" /*lint !e451*/
5502 
5503 
5504 /* SCIPsortPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5505 #define SORTTPL_NAMEEXT PtrIntInt
5506 #define SORTTPL_KEYTYPE void*
5507 #define SORTTPL_FIELD1TYPE int
5508 #define SORTTPL_FIELD2TYPE int
5509 #define SORTTPL_PTRCOMP
5510 #include "scip/sorttpl.c" /*lint !e451*/
5511 
5512 
5513 /* SCIPsortPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5514 #define SORTTPL_NAMEEXT PtrRealInt
5515 #define SORTTPL_KEYTYPE void*
5516 #define SORTTPL_FIELD1TYPE SCIP_Real
5517 #define SORTTPL_FIELD2TYPE int
5518 #define SORTTPL_PTRCOMP
5519 #include "scip/sorttpl.c" /*lint !e451*/
5520 
5521 /* SCIPsortPtrRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5522 #define SORTTPL_NAMEEXT PtrRealRealInt
5523 #define SORTTPL_KEYTYPE void*
5524 #define SORTTPL_FIELD1TYPE SCIP_Real
5525 #define SORTTPL_FIELD2TYPE SCIP_Real
5526 #define SORTTPL_FIELD3TYPE int
5527 #define SORTTPL_PTRCOMP
5528 #include "scip/sorttpl.c" /*lint !e451*/
5529 
5530 /* SCIPsortPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5531 #define SORTTPL_NAMEEXT PtrRealRealIntBool
5532 #define SORTTPL_KEYTYPE void*
5533 #define SORTTPL_FIELD1TYPE SCIP_Real
5534 #define SORTTPL_FIELD2TYPE SCIP_Real
5535 #define SORTTPL_FIELD3TYPE int
5536 #define SORTTPL_FIELD4TYPE SCIP_Bool
5537 #define SORTTPL_PTRCOMP
5538 #include "scip/sorttpl.c" /*lint !e451*/
5539 
5540 /* SCIPsortPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5541 #define SORTTPL_NAMEEXT PtrRealBool
5542 #define SORTTPL_KEYTYPE void*
5543 #define SORTTPL_FIELD1TYPE SCIP_Real
5544 #define SORTTPL_FIELD2TYPE SCIP_Bool
5545 #define SORTTPL_PTRCOMP
5546 #include "scip/sorttpl.c" /*lint !e451*/
5547 
5548 
5549 /* SCIPsortPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5550 #define SORTTPL_NAMEEXT PtrPtrInt
5551 #define SORTTPL_KEYTYPE void*
5552 #define SORTTPL_FIELD1TYPE void*
5553 #define SORTTPL_FIELD2TYPE int
5554 #define SORTTPL_PTRCOMP
5555 #include "scip/sorttpl.c" /*lint !e451*/
5556 
5557 
5558 /* SCIPsortPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5559 #define SORTTPL_NAMEEXT PtrPtrReal
5560 #define SORTTPL_KEYTYPE void*
5561 #define SORTTPL_FIELD1TYPE void*
5562 #define SORTTPL_FIELD2TYPE SCIP_Real
5563 #define SORTTPL_PTRCOMP
5564 #include "scip/sorttpl.c" /*lint !e451*/
5565 
5566 
5567 /* SCIPsortPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5568 #define SORTTPL_NAMEEXT PtrRealIntInt
5569 #define SORTTPL_KEYTYPE void*
5570 #define SORTTPL_FIELD1TYPE SCIP_Real
5571 #define SORTTPL_FIELD2TYPE int
5572 #define SORTTPL_FIELD3TYPE int
5573 #define SORTTPL_PTRCOMP
5574 #include "scip/sorttpl.c" /*lint !e451*/
5575 
5576 
5577 /* SCIPsortPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5578 #define SORTTPL_NAMEEXT PtrPtrIntInt
5579 #define SORTTPL_KEYTYPE void*
5580 #define SORTTPL_FIELD1TYPE void*
5581 #define SORTTPL_FIELD2TYPE int
5582 #define SORTTPL_FIELD3TYPE int
5583 #define SORTTPL_PTRCOMP
5584 #include "scip/sorttpl.c" /*lint !e451*/
5585 
5586 
5587 /* SCIPsortPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5588 #define SORTTPL_NAMEEXT PtrPtrRealInt
5589 #define SORTTPL_KEYTYPE void*
5590 #define SORTTPL_FIELD1TYPE void*
5591 #define SORTTPL_FIELD2TYPE SCIP_Real
5592 #define SORTTPL_FIELD3TYPE int
5593 #define SORTTPL_PTRCOMP
5594 #include "scip/sorttpl.c" /*lint !e451*/
5595 
5596 
5597 /* SCIPsortPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5598 #define SORTTPL_NAMEEXT PtrPtrRealBool
5599 #define SORTTPL_KEYTYPE void*
5600 #define SORTTPL_FIELD1TYPE void*
5601 #define SORTTPL_FIELD2TYPE SCIP_Real
5602 #define SORTTPL_FIELD3TYPE SCIP_Bool
5603 #define SORTTPL_PTRCOMP
5604 #include "scip/sorttpl.c" /*lint !e451*/
5605 
5606 
5607 /* SCIPsortPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5608 #define SORTTPL_NAMEEXT PtrPtrLongInt
5609 #define SORTTPL_KEYTYPE void*
5610 #define SORTTPL_FIELD1TYPE void*
5611 #define SORTTPL_FIELD2TYPE SCIP_Longint
5612 #define SORTTPL_FIELD3TYPE int
5613 #define SORTTPL_PTRCOMP
5614 #include "scip/sorttpl.c" /*lint !e451*/
5615 
5616 
5617 /* SCIPsortPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5618 #define SORTTPL_NAMEEXT PtrPtrLongIntInt
5619 #define SORTTPL_KEYTYPE void*
5620 #define SORTTPL_FIELD1TYPE void*
5621 #define SORTTPL_FIELD2TYPE SCIP_Longint
5622 #define SORTTPL_FIELD3TYPE int
5623 #define SORTTPL_FIELD4TYPE int
5624 #define SORTTPL_PTRCOMP
5625 #include "scip/sorttpl.c" /*lint !e451*/
5626 
5627 
5628 /* SCIPsortReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5629 #define SORTTPL_NAMEEXT Real
5630 #define SORTTPL_KEYTYPE SCIP_Real
5631 #include "scip/sorttpl.c" /*lint !e451*/
5632 
5633 
5634 /* SCIPsortRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5635 #define SORTTPL_NAMEEXT RealBoolPtr
5636 #define SORTTPL_KEYTYPE SCIP_Real
5637 #define SORTTPL_FIELD1TYPE SCIP_Bool
5638 #define SORTTPL_FIELD2TYPE void*
5639 #include "scip/sorttpl.c" /*lint !e451*/
5640 
5641 
5642 /* SCIPsortRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5643 #define SORTTPL_NAMEEXT RealPtr
5644 #define SORTTPL_KEYTYPE SCIP_Real
5645 #define SORTTPL_FIELD1TYPE void*
5646 #include "scip/sorttpl.c" /*lint !e451*/
5647 
5648 
5649 /* SCIPsortRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5650 #define SORTTPL_NAMEEXT RealInt
5651 #define SORTTPL_KEYTYPE SCIP_Real
5652 #define SORTTPL_FIELD1TYPE int
5653 #include "scip/sorttpl.c" /*lint !e451*/
5654 
5655 
5656 /* SCIPsortRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5657 #define SORTTPL_NAMEEXT RealIntInt
5658 #define SORTTPL_KEYTYPE SCIP_Real
5659 #define SORTTPL_FIELD1TYPE int
5660 #define SORTTPL_FIELD2TYPE int
5661 #include "scip/sorttpl.c" /*lint !e451*/
5662 
5663 
5664 /* SCIPsortRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5665 #define SORTTPL_NAMEEXT RealIntLong
5666 #define SORTTPL_KEYTYPE SCIP_Real
5667 #define SORTTPL_FIELD1TYPE int
5668 #define SORTTPL_FIELD2TYPE SCIP_Longint
5669 #include "scip/sorttpl.c" /*lint !e451*/
5670 
5671 
5672 /* SCIPsortRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5673 #define SORTTPL_NAMEEXT RealIntPtr
5674 #define SORTTPL_KEYTYPE SCIP_Real
5675 #define SORTTPL_FIELD1TYPE int
5676 #define SORTTPL_FIELD2TYPE void*
5677 #include "scip/sorttpl.c" /*lint !e451*/
5678 
5679 
5680 /* SCIPsortRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5681 #define SORTTPL_NAMEEXT RealRealPtr
5682 #define SORTTPL_KEYTYPE SCIP_Real
5683 #define SORTTPL_FIELD1TYPE SCIP_Real
5684 #define SORTTPL_FIELD2TYPE void*
5685 #include "scip/sorttpl.c" /*lint !e451*/
5686 
5687 
5688 /* SCIPsortRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5689 #define SORTTPL_NAMEEXT RealLongRealInt
5690 #define SORTTPL_KEYTYPE SCIP_Real
5691 #define SORTTPL_FIELD1TYPE SCIP_Longint
5692 #define SORTTPL_FIELD2TYPE SCIP_Real
5693 #define SORTTPL_FIELD3TYPE int
5694 #include "scip/sorttpl.c" /*lint !e451*/
5695 
5696 /* SCIPsortRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5697 #define SORTTPL_NAMEEXT RealRealIntInt
5698 #define SORTTPL_KEYTYPE SCIP_Real
5699 #define SORTTPL_FIELD1TYPE SCIP_Real
5700 #define SORTTPL_FIELD2TYPE int
5701 #define SORTTPL_FIELD3TYPE int
5702 #include "scip/sorttpl.c" /*lint !e451*/
5703 
5704 
5705 /* SCIPsortRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5706 #define SORTTPL_NAMEEXT RealRealRealInt
5707 #define SORTTPL_KEYTYPE SCIP_Real
5708 #define SORTTPL_FIELD1TYPE SCIP_Real
5709 #define SORTTPL_FIELD2TYPE SCIP_Real
5710 #define SORTTPL_FIELD3TYPE int
5711 #include "scip/sorttpl.c" /*lint !e451*/
5712 
5713 
5714 /* SCIPsortRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5715 #define SORTTPL_NAMEEXT RealRealRealPtr
5716 #define SORTTPL_KEYTYPE SCIP_Real
5717 #define SORTTPL_FIELD1TYPE SCIP_Real
5718 #define SORTTPL_FIELD2TYPE SCIP_Real
5719 #define SORTTPL_FIELD3TYPE void*
5720 #include "scip/sorttpl.c" /*lint !e451*/
5721 
5722 
5723 /* SCIPsortRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5724 #define SORTTPL_NAMEEXT RealPtrPtrInt
5725 #define SORTTPL_KEYTYPE SCIP_Real
5726 #define SORTTPL_FIELD1TYPE void*
5727 #define SORTTPL_FIELD2TYPE void*
5728 #define SORTTPL_FIELD3TYPE int
5729 #include "scip/sorttpl.c" /*lint !e451*/
5730 
5731 
5732 /* SCIPsortRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5733 #define SORTTPL_NAMEEXT RealPtrPtrIntInt
5734 #define SORTTPL_KEYTYPE SCIP_Real
5735 #define SORTTPL_FIELD1TYPE void*
5736 #define SORTTPL_FIELD2TYPE void*
5737 #define SORTTPL_FIELD3TYPE int
5738 #define SORTTPL_FIELD4TYPE int
5739 #include "scip/sorttpl.c" /*lint !e451*/
5740 
5741 
5742 /* SCIPsortRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5743 #define SORTTPL_NAMEEXT RealRealRealBoolPtr
5744 #define SORTTPL_KEYTYPE SCIP_Real
5745 #define SORTTPL_FIELD1TYPE SCIP_Real
5746 #define SORTTPL_FIELD2TYPE SCIP_Real
5747 #define SORTTPL_FIELD3TYPE SCIP_Bool
5748 #define SORTTPL_FIELD4TYPE void*
5749 #include "scip/sorttpl.c" /*lint !e451*/
5750 
5751 
5752 /* SCIPsortRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5753 #define SORTTPL_NAMEEXT RealRealRealBoolBoolPtr
5754 #define SORTTPL_KEYTYPE SCIP_Real
5755 #define SORTTPL_FIELD1TYPE SCIP_Real
5756 #define SORTTPL_FIELD2TYPE SCIP_Real
5757 #define SORTTPL_FIELD3TYPE SCIP_Bool
5758 #define SORTTPL_FIELD4TYPE SCIP_Bool
5759 #define SORTTPL_FIELD5TYPE void*
5760 #include "scip/sorttpl.c" /*lint !e451*/
5761 
5762 
5763 /* SCIPsortInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5764 #define SORTTPL_NAMEEXT Int
5765 #define SORTTPL_KEYTYPE int
5766 #include "scip/sorttpl.c" /*lint !e451*/
5767 
5768 
5769 /* SCIPsortIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5770 #define SORTTPL_NAMEEXT IntInt
5771 #define SORTTPL_KEYTYPE int
5772 #define SORTTPL_FIELD1TYPE int
5773 #include "scip/sorttpl.c" /*lint !e451*/
5774 
5775 
5776 /* SCIPsortIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5777 #define SORTTPL_NAMEEXT IntReal
5778 #define SORTTPL_KEYTYPE int
5779 #define SORTTPL_FIELD1TYPE SCIP_Real
5780 #include "scip/sorttpl.c" /*lint !e451*/
5781 
5782 
5783 /* SCIPsortIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5784 #define SORTTPL_NAMEEXT IntPtr
5785 #define SORTTPL_KEYTYPE int
5786 #define SORTTPL_FIELD1TYPE void*
5787 #include "scip/sorttpl.c" /*lint !e451*/
5788 
5789 
5790 /* SCIPsortIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5791 #define SORTTPL_NAMEEXT IntIntInt
5792 #define SORTTPL_KEYTYPE int
5793 #define SORTTPL_FIELD1TYPE int
5794 #define SORTTPL_FIELD2TYPE int
5795 #include "scip/sorttpl.c" /*lint !e451*/
5796 
5797 
5798 /* SCIPsortIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5799 #define SORTTPL_NAMEEXT IntIntLong
5800 #define SORTTPL_KEYTYPE int
5801 #define SORTTPL_FIELD1TYPE int
5802 #define SORTTPL_FIELD2TYPE SCIP_Longint
5803 #include "scip/sorttpl.c" /*lint !e451*/
5804 
5805 /* SCIPsortIntRealLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5806 #define SORTTPL_NAMEEXT IntRealLong
5807 #define SORTTPL_KEYTYPE int
5808 #define SORTTPL_FIELD1TYPE SCIP_Real
5809 #define SORTTPL_FIELD2TYPE SCIP_Longint
5810 #include "scip/sorttpl.c" /*lint !e451*/
5811 
5812 
5813 /* SCIPsortIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5814 #define SORTTPL_NAMEEXT IntIntPtr
5815 #define SORTTPL_KEYTYPE int
5816 #define SORTTPL_FIELD1TYPE int
5817 #define SORTTPL_FIELD2TYPE void*
5818 #include "scip/sorttpl.c" /*lint !e451*/
5819 
5820 
5821 /* SCIPsortIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5822 #define SORTTPL_NAMEEXT IntIntReal
5823 #define SORTTPL_KEYTYPE int
5824 #define SORTTPL_FIELD1TYPE int
5825 #define SORTTPL_FIELD2TYPE SCIP_Real
5826 #include "scip/sorttpl.c" /*lint !e451*/
5827 
5828 
5829 /* SCIPsortIntPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5830 #define SORTTPL_NAMEEXT IntPtrReal
5831 #define SORTTPL_KEYTYPE int
5832 #define SORTTPL_FIELD1TYPE void*
5833 #define SORTTPL_FIELD2TYPE SCIP_Real
5834 #include "scip/sorttpl.c" /*lint !e451*/
5835 
5836 
5837 /* SCIPsortIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5838 #define SORTTPL_NAMEEXT IntIntIntPtr
5839 #define SORTTPL_KEYTYPE int
5840 #define SORTTPL_FIELD1TYPE int
5841 #define SORTTPL_FIELD2TYPE int
5842 #define SORTTPL_FIELD3TYPE void*
5843 #include "scip/sorttpl.c" /*lint !e451*/
5844 
5845 /* SCIPsortIntIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5846 #define SORTTPL_NAMEEXT IntIntIntReal
5847 #define SORTTPL_KEYTYPE int
5848 #define SORTTPL_FIELD1TYPE int
5849 #define SORTTPL_FIELD2TYPE int
5850 #define SORTTPL_FIELD3TYPE SCIP_Real
5851 #include "scip/sorttpl.c" /*lint !e451*/
5852 
5853 /* SCIPsortIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5854 #define SORTTPL_NAMEEXT IntPtrIntReal
5855 #define SORTTPL_KEYTYPE int
5856 #define SORTTPL_FIELD1TYPE void*
5857 #define SORTTPL_FIELD2TYPE int
5858 #define SORTTPL_FIELD3TYPE SCIP_Real
5859 #include "scip/sorttpl.c" /*lint !e451*/
5860 
5861 
5862 /* SCIPsortLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5863 #define SORTTPL_NAMEEXT Long
5864 #define SORTTPL_KEYTYPE SCIP_Longint
5865 #include "scip/sorttpl.c" /*lint !e451*/
5866 
5867 
5868 /* SCIPsortLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5869 #define SORTTPL_NAMEEXT LongPtr
5870 #define SORTTPL_KEYTYPE SCIP_Longint
5871 #define SORTTPL_FIELD1TYPE void*
5872 #include "scip/sorttpl.c" /*lint !e451*/
5873 
5874 
5875 /* SCIPsortLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5876 #define SORTTPL_NAMEEXT LongPtrInt
5877 #define SORTTPL_KEYTYPE SCIP_Longint
5878 #define SORTTPL_FIELD1TYPE void*
5879 #define SORTTPL_FIELD2TYPE int
5880 #include "scip/sorttpl.c" /*lint !e451*/
5881 
5882 
5883 /* SCIPsortLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5884 #define SORTTPL_NAMEEXT LongPtrRealBool
5885 #define SORTTPL_KEYTYPE SCIP_Longint
5886 #define SORTTPL_FIELD1TYPE void*
5887 #define SORTTPL_FIELD2TYPE SCIP_Real
5888 #define SORTTPL_FIELD3TYPE SCIP_Bool
5889 #include "scip/sorttpl.c" /*lint !e451*/
5890 
5891 
5892 /* SCIPsortLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5893 #define SORTTPL_NAMEEXT LongPtrRealRealBool
5894 #define SORTTPL_KEYTYPE SCIP_Longint
5895 #define SORTTPL_FIELD1TYPE void*
5896 #define SORTTPL_FIELD2TYPE SCIP_Real
5897 #define SORTTPL_FIELD3TYPE SCIP_Real
5898 #define SORTTPL_FIELD4TYPE SCIP_Bool
5899 #include "scip/sorttpl.c" /*lint !e451*/
5900 
5901 
5902 /* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5903 #define SORTTPL_NAMEEXT LongPtrRealRealIntBool
5904 #define SORTTPL_KEYTYPE SCIP_Longint
5905 #define SORTTPL_FIELD1TYPE void*
5906 #define SORTTPL_FIELD2TYPE SCIP_Real
5907 #define SORTTPL_FIELD3TYPE SCIP_Real
5908 #define SORTTPL_FIELD4TYPE int
5909 #define SORTTPL_FIELD5TYPE SCIP_Bool
5910 #include "scip/sorttpl.c" /*lint !e451*/
5911 
5912 
5913 /* SCIPsortLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5914 #define SORTTPL_NAMEEXT LongPtrPtrInt
5915 #define SORTTPL_KEYTYPE SCIP_Longint
5916 #define SORTTPL_FIELD1TYPE void*
5917 #define SORTTPL_FIELD2TYPE void*
5918 #define SORTTPL_FIELD3TYPE int
5919 #include "scip/sorttpl.c" /*lint !e451*/
5920 
5921 
5922 /* SCIPsortLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5923 #define SORTTPL_NAMEEXT LongPtrPtrIntInt
5924 #define SORTTPL_KEYTYPE SCIP_Longint
5925 #define SORTTPL_FIELD1TYPE void*
5926 #define SORTTPL_FIELD2TYPE void*
5927 #define SORTTPL_FIELD3TYPE int
5928 #define SORTTPL_FIELD4TYPE int
5929 #include "scip/sorttpl.c" /*lint !e451*/
5930 
5931 
5932 /* SCIPsortLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5933 #define SORTTPL_NAMEEXT LongPtrPtrBoolInt
5934 #define SORTTPL_KEYTYPE SCIP_Longint
5935 #define SORTTPL_FIELD1TYPE void*
5936 #define SORTTPL_FIELD2TYPE void*
5937 #define SORTTPL_FIELD3TYPE SCIP_Bool
5938 #define SORTTPL_FIELD4TYPE int
5939 #include "scip/sorttpl.c" /*lint !e451*/
5940 
5941 
5942 /* SCIPsortPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5943 #define SORTTPL_NAMEEXT PtrIntIntBoolBool
5944 #define SORTTPL_KEYTYPE void*
5945 #define SORTTPL_FIELD1TYPE int
5946 #define SORTTPL_FIELD2TYPE int
5947 #define SORTTPL_FIELD3TYPE SCIP_Bool
5948 #define SORTTPL_FIELD4TYPE SCIP_Bool
5949 #define SORTTPL_PTRCOMP
5950 #include "scip/sorttpl.c" /*lint !e451*/
5951 
5952 
5953 /* SCIPsortIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5954 #define SORTTPL_NAMEEXT IntPtrIntIntBoolBool
5955 #define SORTTPL_KEYTYPE int
5956 #define SORTTPL_FIELD1TYPE void*
5957 #define SORTTPL_FIELD2TYPE int
5958 #define SORTTPL_FIELD3TYPE int
5959 #define SORTTPL_FIELD4TYPE SCIP_Bool
5960 #define SORTTPL_FIELD5TYPE SCIP_Bool
5961 #include "scip/sorttpl.c" /*lint !e451*/
5962 
5963 
5964 /* now all downwards-sorting methods */
5965 
5966 
5967 /** sort an indexed element set in non-increasing order, resulting in a permutation index array */
5969  int* perm, /**< pointer to store the resulting permutation */
5970  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
5971  void* dataptr, /**< pointer to data field that is given to the external compare method */
5972  int len /**< number of elements to be sorted (valid index range) */
5973  )
5974 {
5975  int pos;
5976 
5977  assert(indcomp != NULL);
5978  assert(len == 0 || perm != NULL);
5979 
5980  /* create identity permutation */
5981  for( pos = 0; pos < len; ++pos )
5982  perm[pos] = pos;
5983 
5984  SCIPsortDownInd(perm, indcomp, dataptr, len);
5985 }
5986 
5987 
5988 /* SCIPsortDownInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5989 #define SORTTPL_NAMEEXT DownInd
5990 #define SORTTPL_KEYTYPE int
5991 #define SORTTPL_INDCOMP
5992 #define SORTTPL_BACKWARDS
5993 #include "scip/sorttpl.c" /*lint !e451*/
5994 
5995 
5996 /* SCIPsortDownPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5997 #define SORTTPL_NAMEEXT DownPtr
5998 #define SORTTPL_KEYTYPE void*
5999 #define SORTTPL_PTRCOMP
6000 #define SORTTPL_BACKWARDS
6001 #include "scip/sorttpl.c" /*lint !e451*/
6002 
6003 
6004 /* SCIPsortDownPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6005 #define SORTTPL_NAMEEXT DownPtrPtr
6006 #define SORTTPL_KEYTYPE void*
6007 #define SORTTPL_FIELD1TYPE void*
6008 #define SORTTPL_PTRCOMP
6009 #define SORTTPL_BACKWARDS
6010 #include "scip/sorttpl.c" /*lint !e451*/
6011 
6012 
6013 /* SCIPsortDownPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6014 #define SORTTPL_NAMEEXT DownPtrReal
6015 #define SORTTPL_KEYTYPE void*
6016 #define SORTTPL_FIELD1TYPE SCIP_Real
6017 #define SORTTPL_PTRCOMP
6018 #define SORTTPL_BACKWARDS
6019 #include "scip/sorttpl.c" /*lint !e451*/
6020 
6021 
6022 /* SCIPsortDownPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6023 #define SORTTPL_NAMEEXT DownPtrInt
6024 #define SORTTPL_KEYTYPE void*
6025 #define SORTTPL_FIELD1TYPE int
6026 #define SORTTPL_PTRCOMP
6027 #define SORTTPL_BACKWARDS
6028 #include "scip/sorttpl.c" /*lint !e451*/
6029 
6030 /* SCIPsortDownPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6031 #define SORTTPL_NAMEEXT DownPtrBool
6032 #define SORTTPL_KEYTYPE void*
6033 #define SORTTPL_FIELD1TYPE SCIP_Bool
6034 #define SORTTPL_PTRCOMP
6035 #define SORTTPL_BACKWARDS
6036 #include "scip/sorttpl.c" /*lint !e451*/
6037 
6038 /* SCIPsortDownPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6039 #define SORTTPL_NAMEEXT DownPtrIntInt
6040 #define SORTTPL_KEYTYPE void*
6041 #define SORTTPL_FIELD1TYPE int
6042 #define SORTTPL_FIELD2TYPE int
6043 #define SORTTPL_PTRCOMP
6044 #define SORTTPL_BACKWARDS
6045 #include "scip/sorttpl.c" /*lint !e451*/
6046 
6047 
6048 /* SCIPsortDownPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6049 #define SORTTPL_NAMEEXT DownPtrRealInt
6050 #define SORTTPL_KEYTYPE void*
6051 #define SORTTPL_FIELD1TYPE SCIP_Real
6052 #define SORTTPL_FIELD2TYPE int
6053 #define SORTTPL_PTRCOMP
6054 #define SORTTPL_BACKWARDS
6055 #include "scip/sorttpl.c" /*lint !e451*/
6056 
6057 
6058 /* SCIPsortDownPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6059 #define SORTTPL_NAMEEXT DownPtrRealBool
6060 #define SORTTPL_KEYTYPE void*
6061 #define SORTTPL_FIELD1TYPE SCIP_Real
6062 #define SORTTPL_FIELD2TYPE SCIP_Bool
6063 #define SORTTPL_PTRCOMP
6064 #define SORTTPL_BACKWARDS
6065 #include "scip/sorttpl.c" /*lint !e451*/
6066 
6067 
6068 /* SCIPsortDownPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6069 #define SORTTPL_NAMEEXT DownPtrPtrInt
6070 #define SORTTPL_KEYTYPE void*
6071 #define SORTTPL_FIELD1TYPE void*
6072 #define SORTTPL_FIELD2TYPE int
6073 #define SORTTPL_PTRCOMP
6074 #define SORTTPL_BACKWARDS
6075 #include "scip/sorttpl.c" /*lint !e451*/
6076 
6077 
6078 /* SCIPsortDownPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6079 #define SORTTPL_NAMEEXT DownPtrPtrReal
6080 #define SORTTPL_KEYTYPE void*
6081 #define SORTTPL_FIELD1TYPE void*
6082 #define SORTTPL_FIELD2TYPE SCIP_Real
6083 #define SORTTPL_PTRCOMP
6084 #define SORTTPL_BACKWARDS
6085 #include "scip/sorttpl.c" /*lint !e451*/
6086 
6087 
6088 /* SCIPsortDownPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6089 #define SORTTPL_NAMEEXT DownPtrRealIntInt
6090 #define SORTTPL_KEYTYPE void*
6091 #define SORTTPL_FIELD1TYPE SCIP_Real
6092 #define SORTTPL_FIELD2TYPE int
6093 #define SORTTPL_FIELD3TYPE int
6094 #define SORTTPL_PTRCOMP
6095 #define SORTTPL_BACKWARDS
6096 #include "scip/sorttpl.c" /*lint !e451*/
6097 
6098 
6099 /* SCIPsortDownPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6100 #define SORTTPL_NAMEEXT DownPtrPtrIntInt
6101 #define SORTTPL_KEYTYPE void*
6102 #define SORTTPL_FIELD1TYPE void*
6103 #define SORTTPL_FIELD2TYPE int
6104 #define SORTTPL_FIELD3TYPE int
6105 #define SORTTPL_PTRCOMP
6106 #define SORTTPL_BACKWARDS
6107 #include "scip/sorttpl.c" /*lint !e451*/
6108 
6109 
6110 /* SCIPsortDownPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6111 #define SORTTPL_NAMEEXT DownPtrPtrRealInt
6112 #define SORTTPL_KEYTYPE void*
6113 #define SORTTPL_FIELD1TYPE void*
6114 #define SORTTPL_FIELD2TYPE SCIP_Real
6115 #define SORTTPL_FIELD3TYPE int
6116 #define SORTTPL_PTRCOMP
6117 #define SORTTPL_BACKWARDS
6118 #include "scip/sorttpl.c" /*lint !e451*/
6119 
6120 
6121 /* SCIPsortDownPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6122 #define SORTTPL_NAMEEXT DownPtrPtrRealBool
6123 #define SORTTPL_KEYTYPE void*
6124 #define SORTTPL_FIELD1TYPE void*
6125 #define SORTTPL_FIELD2TYPE SCIP_Real
6126 #define SORTTPL_FIELD3TYPE SCIP_Bool
6127 #define SORTTPL_PTRCOMP
6128 #define SORTTPL_BACKWARDS
6129 #include "scip/sorttpl.c" /*lint !e451*/
6130 
6131 
6132 /* SCIPsortDownPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6133 #define SORTTPL_NAMEEXT DownPtrPtrLongInt
6134 #define SORTTPL_KEYTYPE void*
6135 #define SORTTPL_FIELD1TYPE void*
6136 #define SORTTPL_FIELD2TYPE SCIP_Longint
6137 #define SORTTPL_FIELD3TYPE int
6138 #define SORTTPL_PTRCOMP
6139 #define SORTTPL_BACKWARDS
6140 #include "scip/sorttpl.c" /*lint !e451*/
6141 
6142 
6143 /* SCIPsortDownPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6144 #define SORTTPL_NAMEEXT DownPtrPtrLongIntInt
6145 #define SORTTPL_KEYTYPE void*
6146 #define SORTTPL_FIELD1TYPE void*
6147 #define SORTTPL_FIELD2TYPE SCIP_Longint
6148 #define SORTTPL_FIELD3TYPE int
6149 #define SORTTPL_FIELD4TYPE int
6150 #define SORTTPL_PTRCOMP
6151 #define SORTTPL_BACKWARDS
6152 #include "scip/sorttpl.c" /*lint !e451*/
6153 
6154 
6155 /* SCIPsortDownReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6156 #define SORTTPL_NAMEEXT DownReal
6157 #define SORTTPL_KEYTYPE SCIP_Real
6158 #define SORTTPL_BACKWARDS
6159 #include "scip/sorttpl.c" /*lint !e451*/
6160 
6161 
6162 /* SCIPsortDownRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6163 #define SORTTPL_NAMEEXT DownRealBoolPtr
6164 #define SORTTPL_KEYTYPE SCIP_Real
6165 #define SORTTPL_FIELD1TYPE SCIP_Bool
6166 #define SORTTPL_FIELD2TYPE void*
6167 #define SORTTPL_BACKWARDS
6168 #include "scip/sorttpl.c" /*lint !e451*/
6169 
6170 
6171 /* SCIPsortDownRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6172 #define SORTTPL_NAMEEXT DownRealPtr
6173 #define SORTTPL_KEYTYPE SCIP_Real
6174 #define SORTTPL_FIELD1TYPE void*
6175 #define SORTTPL_BACKWARDS
6176 #include "scip/sorttpl.c" /*lint !e451*/
6177 
6178 
6179 /* SCIPsortDownRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6180 #define SORTTPL_NAMEEXT DownRealInt
6181 #define SORTTPL_KEYTYPE SCIP_Real
6182 #define SORTTPL_FIELD1TYPE int
6183 #define SORTTPL_BACKWARDS
6184 #include "scip/sorttpl.c" /*lint !e451*/
6185 
6186 /* SCIPsortDownRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6187 #define SORTTPL_NAMEEXT DownRealIntInt
6188 #define SORTTPL_KEYTYPE SCIP_Real
6189 #define SORTTPL_FIELD1TYPE int
6190 #define SORTTPL_FIELD2TYPE int
6191 #define SORTTPL_BACKWARDS
6192 #include "scip/sorttpl.c" /*lint !e451*/
6193 
6194 /* SCIPsortDownRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6195 #define SORTTPL_NAMEEXT DownRealIntLong
6196 #define SORTTPL_KEYTYPE SCIP_Real
6197 #define SORTTPL_FIELD1TYPE int
6198 #define SORTTPL_FIELD2TYPE SCIP_Longint
6199 #define SORTTPL_BACKWARDS
6200 #include "