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