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