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