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