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-2017 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 email to 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-6);
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) ((0x9e3779b97f4a7c15ULL * 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  unsigned int keyval, /**< hash value of key */
1423  void* key /**< key to retrieve */
1424  )
1425 {
1426  unsigned int 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  unsigned int keyval, /**< hash value of key */
1454  void* key /**< key to retrieve */
1455  )
1456 {
1457  SCIP_MULTIHASHLIST* h;
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  unsigned int keyval, /**< hash value of key */
1505  void* key /**< key to retrieve */
1506  )
1507 {
1508  SCIP_MULTIHASHLIST* h;
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  unsigned int 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  unsigned int 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  unsigned int 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  unsigned int 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  unsigned int 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  unsigned int 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 
2014 /** creates a hash table */
2016  SCIP_HASHTABLE** hashtable, /**< pointer to store the created hash table */
2017  BMS_BLKMEM* blkmem, /**< block memory used to store hash table entries */
2018  int tablesize, /**< size of the hash table */
2019  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
2020  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
2021  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
2022  void* userptr /**< user pointer */
2023  )
2024 {
2025  unsigned int nslots;
2026 
2027  /* only assert non negative to catch overflow errors
2028  * but not zeros due to integer divison
2029  */
2030  assert(tablesize >= 0);
2031  assert(hashtable != NULL);
2032  assert(hashgetkey != NULL);
2033  assert(hashkeyeq != NULL);
2034  assert(hashkeyval != NULL);
2035  assert(blkmem != NULL);
2036 
2037  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashtable) );
2038 
2039  /* dont create too small hashtables, i.e. at least size 32, and increase
2040  * the given size by divinding it by 0.9, since then no rebuilding will
2041  * be necessary if the given number of elements are inserted. Finally round
2042  * to the next power of two.
2043  */
2044  (*hashtable)->shift = 32;
2045  (*hashtable)->shift -= (int)ceil(log(MAX(32.0, tablesize / 0.9)) / log(2.0));
2046 
2047  /* compute size from shift */
2048  nslots = 1u << (32 - (*hashtable)->shift);
2049 
2050  /* compute mask to do a fast modulo by nslots using bitwise and */
2051  (*hashtable)->mask = nslots - 1;
2052  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*hashtable)->slots, nslots) );
2053  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashtable)->hashes, nslots) );
2054  (*hashtable)->blkmem = blkmem;
2055  (*hashtable)->hashgetkey = hashgetkey;
2056  (*hashtable)->hashkeyeq = hashkeyeq;
2057  (*hashtable)->hashkeyval = hashkeyval;
2058  (*hashtable)->userptr = userptr;
2059  (*hashtable)->nelements = 0;
2060 
2061  return SCIP_OKAY;
2062 }
2063 
2064 /** frees the hash table */
2066  SCIP_HASHTABLE** hashtable /**< pointer to the hash table */
2067  )
2068 {
2069  uint32_t nslots;
2070  SCIP_HASHTABLE* table;
2071 
2072  assert(hashtable != NULL);
2073  assert(*hashtable != NULL);
2074  table = *hashtable;
2075  nslots = (*hashtable)->mask + 1;
2076 #ifdef SCIP_DEBUG
2077  {
2078  uint32_t maxprobelen = 0;
2079  uint64_t probelensum = 0;
2080  uint32_t i;
2081 
2082  assert(table != NULL);
2083 
2084  for( i = 0; i < nslots; ++i )
2085  {
2086  if( table->hashes[i] != 0 )
2087  {
2088  uint32_t probelen = ((i + table->mask + 1 - (table->hashes[i]>>(table->shift))) & table->mask) + 1;
2089  probelensum += probelen;
2090  maxprobelen = MAX(probelen, maxprobelen);
2091  }
2092  }
2093 
2094  SCIPdebugMessage("%u hash table entries, used %u/%u slots (%.1f%%)",
2095  (unsigned int)table->nelements, (unsigned int)table->nelements, (unsigned int)nslots,
2096  100.0*(SCIP_Real)table->nelements/(SCIP_Real)(nslots));
2097  if( table->nelements > 0 )
2098  SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
2099  (SCIP_Real)(probelensum)/(SCIP_Real)table->nelements, (unsigned int)maxprobelen);
2100  SCIPdebugMessage("\n");
2101  }
2102 #endif
2103 
2104  /* free main hash table data structure */
2105  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->hashes, nslots);
2106  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->slots, nslots);
2107  BMSfreeBlockMemory((*hashtable)->blkmem, hashtable);
2108 }
2109 
2110 /** removes all elements of the hash table
2111  *
2112  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2113  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2114  *
2115  * @deprecated Please use SCIPhashtableRemoveAll()
2116  */
2118  SCIP_HASHTABLE* hashtable /**< hash table */
2119  )
2120 {
2121  SCIPhashtableRemoveAll(hashtable);
2122 }
2123 
2124 /* computes the distance from it's desired position for the element stored at pos */
2125 #define ELEM_DISTANCE(pos) (((pos) + hashtable->mask + 1 - (hashtable->hashes[(pos)]>>(hashtable->shift))) & hashtable->mask)
2126 
2127 /** inserts element in hash table (multiple inserts of same element overrides previous one) */
2128 static
2130  SCIP_HASHTABLE* hashtable, /**< hash table */
2131  void* element, /**< element to insert into the table */
2132  void* key, /**< key of element */
2133  uint32_t hashval, /**< hash value of element */
2134  SCIP_Bool override /**< should element be overridden or an error be returned if already existing */
2135  )
2136 {
2137  uint32_t elemdistance;
2138  uint32_t pos;
2139 
2140  assert(hashtable != NULL);
2141  assert(hashtable->slots != NULL);
2142  assert(hashtable->hashes != NULL);
2143  assert(hashtable->mask > 0);
2144  assert(hashtable->hashgetkey != NULL);
2145  assert(hashtable->hashkeyeq != NULL);
2146  assert(hashtable->hashkeyval != NULL);
2147  assert(element != NULL);
2148 
2149  pos = hashval>>(hashtable->shift);
2150  elemdistance = 0;
2151  while( TRUE ) /*lint !e716*/
2152  {
2153  uint32_t distance;
2154 
2155  /* if position is empty or key equal insert element */
2156  if( hashtable->hashes[pos] == 0 )
2157  {
2158  hashtable->slots[pos] = element;
2159  hashtable->hashes[pos] = hashval;
2160  ++hashtable->nelements;
2161  return SCIP_OKAY;
2162  }
2163 
2164  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2165  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2166  {
2167  if( override )
2168  {
2169  hashtable->slots[pos] = element;
2170  hashtable->hashes[pos] = hashval;
2171  return SCIP_OKAY;
2172  }
2173  else
2174  {
2175  return SCIP_KEYALREADYEXISTING;
2176  }
2177  }
2178 
2179  /* otherwise check if the current element at this position is closer to its hashvalue */
2180  distance = ELEM_DISTANCE(pos);
2181  if( distance < elemdistance )
2182  {
2183  uint32_t tmp;
2184 
2185  /* if this is the case we insert the new element here and find a new position for the old one */
2186  elemdistance = distance;
2187  SCIPswapPointers(&hashtable->slots[pos], &element);
2188  tmp = hashval;
2189  hashval = hashtable->hashes[pos];
2190  hashtable->hashes[pos] = tmp;
2191  }
2192 
2193  /* continue until we have found an empty position */
2194  pos = (pos + 1) & hashtable->mask;
2195  ++elemdistance;
2196  }
2197 }
2198 
2199 /** check if the load factor of the hashtable is too high and rebuild if necessary */
2200 static
2202  SCIP_HASHTABLE* hashtable /**< hash table */
2203  )
2204 {
2205  assert(hashtable != NULL);
2206  assert(hashtable->shift < 32);
2207 
2208  /* use integer arithmetic to approximately check if load factor is above 90% */
2209  if( ((hashtable->nelements<<10)>>(32-hashtable->shift) > 921) )
2210  {
2211  void** slots;
2212  uint32_t* hashes;
2213  uint32_t nslots;
2214  uint32_t newnslots;
2215  uint32_t i;
2216 
2217  /* calculate new size (always power of two) */
2218  nslots = hashtable->mask + 1;
2219  newnslots = 2*nslots;
2220  hashtable->mask = newnslots-1;
2221  --hashtable->shift;
2222 
2223  /* reallocate array */
2224  SCIP_ALLOC( BMSallocBlockMemoryArray(hashtable->blkmem, &slots, newnslots) );
2225  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashtable->blkmem, &hashes, newnslots) );
2226 
2227  SCIPswapPointers((void**) &slots, (void**) &hashtable->slots);
2228  SCIPswapPointers((void**) &hashes, (void**) &hashtable->hashes);
2229  hashtable->nelements = 0;
2230 
2231  /* reinsert all elements */
2232  for( i = 0; i < nslots; ++i )
2233  {
2234  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2235  * and thus no bad return codes when inserting the elements
2236  */
2237  if( hashes[i] != 0 )
2238  {
2239  SCIP_CALL_ABORT( hashtableInsert(hashtable, slots[i], hashtable->hashgetkey(hashtable->userptr, slots[i]), hashes[i], FALSE) );
2240  }
2241  }
2242  BMSfreeBlockMemoryArray(hashtable->blkmem, &hashes, nslots);
2243  BMSfreeBlockMemoryArray(hashtable->blkmem, &slots, nslots);
2244  }
2245 
2246  return SCIP_OKAY;
2247 }
2248 
2249 
2250 /** inserts element in hash table
2251  *
2252  * @note multiple inserts of same element overrides previous one
2253  */
2255  SCIP_HASHTABLE* hashtable, /**< hash table */
2256  void* element /**< element to insert into the table */
2257  )
2258 {
2259  void* key;
2260  unsigned int keyval;
2261  uint32_t hashval;
2262 
2263  assert(hashtable != NULL);
2264  assert(hashtable->slots != NULL);
2265  assert(hashtable->hashes != NULL);
2266  assert(hashtable->mask > 0);
2267  assert(hashtable->hashgetkey != NULL);
2268  assert(hashtable->hashkeyeq != NULL);
2269  assert(hashtable->hashkeyval != NULL);
2270  assert(element != NULL);
2271 
2272  SCIP_CALL( hashtableCheckLoad(hashtable) );
2273 
2274  /* get the hash key and its hash value */
2275  key = hashtable->hashgetkey(hashtable->userptr, element);
2276  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2277  hashval = hashvalue((uint64_t) keyval);
2278 
2279  return hashtableInsert(hashtable, element, key, hashval, TRUE);
2280 }
2281 
2282 /** inserts element in hash table
2283  *
2284  * @note multiple insertion of same element is checked and results in an error
2285  */
2287  SCIP_HASHTABLE* hashtable, /**< hash table */
2288  void* element /**< element to insert into the table */
2289  )
2290 {
2291  void* key;
2292  unsigned int keyval;
2293  uint32_t hashval;
2294 
2295  assert(hashtable != NULL);
2296  assert(hashtable->slots != NULL);
2297  assert(hashtable->hashes != NULL);
2298  assert(hashtable->mask > 0);
2299  assert(hashtable->hashgetkey != NULL);
2300  assert(hashtable->hashkeyeq != NULL);
2301  assert(hashtable->hashkeyval != NULL);
2302  assert(element != NULL);
2303 
2304  SCIP_CALL( hashtableCheckLoad(hashtable) );
2305 
2306  /* get the hash key and its hash value */
2307  key = hashtable->hashgetkey(hashtable->userptr, element);
2308  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2309  hashval = hashvalue((uint64_t) keyval);
2310 
2311  return hashtableInsert(hashtable, element, key, hashval, FALSE);
2312 }
2313 
2314 /** retrieve element with key from hash table, returns NULL if not existing */
2316  SCIP_HASHTABLE* hashtable, /**< hash table */
2317  void* key /**< key to retrieve */
2318  )
2319 {
2320  unsigned int keyval;
2321  uint32_t hashval;
2322  uint32_t pos;
2323  uint32_t elemdistance;
2324 
2325  assert(hashtable != NULL);
2326  assert(hashtable->slots != NULL);
2327  assert(hashtable->hashes != NULL);
2328  assert(hashtable->mask > 0);
2329  assert(hashtable->hashgetkey != NULL);
2330  assert(hashtable->hashkeyeq != NULL);
2331  assert(hashtable->hashkeyval != NULL);
2332  assert(key != NULL);
2333 
2334  /* get the hash value of the key */
2335  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2336  hashval = hashvalue((uint64_t) keyval);
2337 
2338  pos = hashval>>(hashtable->shift);
2339  elemdistance = 0;
2340 
2341  while( TRUE ) /*lint !e716*/
2342  {
2343  uint32_t distance;
2344 
2345  /* slots is empty so element cannot be contained */
2346  if( hashtable->hashes[pos] == 0 )
2347  return NULL;
2348 
2349  distance = ELEM_DISTANCE(pos);
2350 
2351  /* element cannot be contained since otherwise we would have swapped it with this one during insert */
2352  if( elemdistance > distance )
2353  return NULL;
2354 
2355  /* found element */
2356  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2357  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2358  return hashtable->slots[pos];
2359 
2360  pos = (pos + 1) & hashtable->mask;
2361  ++elemdistance;
2362  }
2363 }
2364 
2365 /** returns whether the given element exists in the table */
2367  SCIP_HASHTABLE* hashtable, /**< hash table */
2368  void* element /**< element to search in the table */
2369  )
2370 {
2371  assert(hashtable != NULL);
2372  assert(hashtable->slots != NULL);
2373  assert(hashtable->hashes != NULL);
2374  assert(hashtable->mask > 0);
2375  assert(hashtable->hashgetkey != NULL);
2376  assert(hashtable->hashkeyeq != NULL);
2377  assert(hashtable->hashkeyval != NULL);
2378  assert(element != NULL);
2379 
2380  return (SCIPhashtableRetrieve(hashtable, hashtable->hashgetkey(hashtable->userptr, element)) != NULL);
2381 }
2382 
2383 /** removes element from the hash table, if it exists */
2385  SCIP_HASHTABLE* hashtable, /**< hash table */
2386  void* element /**< element to remove from the table */
2387  )
2388 {
2389  void* key;
2390  unsigned int keyval;
2391  uint32_t hashval;
2392  uint32_t elemdistance;
2393  uint32_t distance;
2394  uint32_t pos;
2395 
2396  assert(hashtable != NULL);
2397  assert(hashtable->slots != NULL);
2398  assert(hashtable->hashes != NULL);
2399  assert(hashtable->mask > 0);
2400  assert(hashtable->hashgetkey != NULL);
2401  assert(hashtable->hashkeyeq != NULL);
2402  assert(hashtable->hashkeyval != NULL);
2403  assert(element != NULL);
2404 
2405  /* get the hash key and its hash value */
2406  key = hashtable->hashgetkey(hashtable->userptr, element);
2407  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2408  hashval = hashvalue((uint64_t) keyval);
2409 
2410  elemdistance = 0;
2411  pos = hashval>>(hashtable->shift);
2412  while( TRUE ) /*lint !e716*/
2413  {
2414  /* slots empty so element not contained */
2415  if( hashtable->hashes[pos] == 0 )
2416  return SCIP_OKAY;
2417 
2418  distance = ELEM_DISTANCE(pos);
2419 
2420  /* element can not be contained since otherwise we would have swapped it with this one */
2421  if( elemdistance > distance )
2422  return SCIP_OKAY;
2423 
2424  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2425  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2426  {
2427  /* element exists at pos so break out of loop */
2428  break;
2429  }
2430 
2431  pos = (pos + 1) & hashtable->mask;
2432  ++elemdistance;
2433  }
2434 
2435  /* remove element */
2436  hashtable->hashes[pos] = 0;
2437  --hashtable->nelements;
2438  while( TRUE ) /*lint !e716*/
2439  {
2440  uint32_t nextpos = (pos + 1) & hashtable->mask;
2441 
2442  /* nothing to do since there is no chain that needs to be moved */
2443  if( hashtable->hashes[nextpos] == 0 )
2444  break;
2445 
2446  /* check if the element is the start of a new chain and return if that is the case */
2447  if( (hashtable->hashes[nextpos]>>(hashtable->shift)) == nextpos )
2448  break;
2449 
2450  /* element should be moved to the left and next element needs to be checked */
2451  hashtable->slots[pos] = hashtable->slots[nextpos];
2452  hashtable->hashes[pos] = hashtable->hashes[nextpos];
2453  hashtable->hashes[nextpos] = 0;
2454 
2455  pos = nextpos;
2456  }
2457 
2458  return SCIP_OKAY;
2459 }
2460 
2461 /** removes all elements of the hash table */
2463  SCIP_HASHTABLE* hashtable /**< hash table */
2464  )
2465 {
2466  assert(hashtable != NULL);
2467 
2468  BMSclearMemoryArray(hashtable->hashes, hashtable->mask + 1);
2469 
2470  hashtable->nelements = 0;
2471 }
2472 
2473 /** returns number of hash table elements */
2475  SCIP_HASHTABLE* hashtable /**< hash table */
2476  )
2477 {
2478  assert(hashtable != NULL);
2479 
2480  return hashtable->nelements;
2481 }
2482 
2483 /** returns the load of the given hash table in percentage */
2485  SCIP_HASHTABLE* hashtable /**< hash table */
2486  )
2487 {
2488  assert(hashtable != NULL);
2489 
2490  return ((SCIP_Real)(hashtable->nelements) / (hashtable->mask + 1) * 100.0);
2491 }
2492 
2493 /** prints statistics about hash table usage */
2495  SCIP_HASHTABLE* hashtable, /**< hash table */
2496  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
2497  )
2498 {
2499  uint32_t maxprobelen = 0;
2500  uint64_t probelensum = 0;
2501  uint32_t nslots;
2502  uint32_t i;
2503 
2504  assert(hashtable != NULL);
2505 
2506  nslots = hashtable->mask + 1;
2507 
2508  /* compute the maximum and average probe length */
2509  for( i = 0; i < nslots; ++i )
2510  {
2511  if( hashtable->hashes[i] != 0 )
2512  {
2513  uint32_t probelen = ELEM_DISTANCE(i) + 1;
2514  probelensum += probelen;
2515  maxprobelen = MAX(probelen, maxprobelen);
2516  }
2517  }
2518 
2519  /* print general hash table statistics */
2520  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
2521  (unsigned int)hashtable->nelements, (unsigned int)hashtable->nelements,
2522  (unsigned int)nslots, 100.0*(SCIP_Real)hashtable->nelements/(SCIP_Real)(nslots));
2523 
2524  /* if not empty print average and maximum probe length */
2525  if( hashtable->nelements > 0 )
2526  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
2527  (SCIP_Real)(probelensum)/(SCIP_Real)hashtable->nelements, (unsigned int)maxprobelen);
2528  SCIPmessagePrintInfo(messagehdlr, "\n");
2529 }
2530 
2531 /** returns TRUE iff both keys (i.e. strings) are equal */
2532 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString)
2533 { /*lint --e{715}*/
2534  const char* string1 = (const char*)key1;
2535  const char* string2 = (const char*)key2;
2536 
2537  return (strcmp(string1, string2) == 0);
2538 }
2539 
2540 /** returns the hash value of the key (i.e. string) */
2541 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString)
2542 { /*lint --e{715}*/
2543  const char* str;
2544  unsigned int hash;
2545 
2546  str = (const char*)key;
2547  hash = 37;
2548  while( *str != '\0' )
2549  {
2550  hash *= 11;
2551  hash += (unsigned int)(*str); /*lint !e571*/
2552  str++;
2553  }
2554 
2555  return hash;
2556 }
2557 
2558 
2559 /** gets the element as the key */
2560 SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard)
2561 { /*lint --e{715}*/
2562  /* the key is the element itself */
2563  return elem;
2564 }
2565 
2566 /** returns TRUE iff both keys(pointer) are equal */
2567 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr)
2568 { /*lint --e{715}*/
2569  return (key1 == key2);
2570 }
2571 
2572 /** returns the hash value of the key */
2573 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr)
2574 { /*lint --e{715}*/
2575  /* the key is used as the keyvalue too */
2576  return (unsigned int) ((0xd37e9a1ce2148403ULL * (size_t) key)>>32);
2577 }
2578 
2579 
2580 
2581 /*
2582  * Hash Map
2583  */
2584 
2585 /* redefine ELEM_DISTANCE macro for hashmap */
2586 #undef ELEM_DISTANCE
2587 /* computes the distance from it's desired position for the element stored at pos */
2588 #define ELEM_DISTANCE(pos) (((pos) + hashmap->mask + 1 - (hashmap->hashes[(pos)]>>(hashmap->shift))) & hashmap->mask)
2589 
2590 
2591 /** inserts element in hash table */
2592 static
2594  SCIP_HASHMAP* hashmap, /**< hash map */
2595  void* origin, /**< element to insert into the table */
2596  SCIP_HASHMAPIMAGE image, /**< key of element */
2597  uint32_t hashval, /**< hash value of element */
2598  SCIP_Bool override /**< should element be overridden or error be returned if already existing */
2599  )
2600 {
2601  uint32_t elemdistance;
2602  uint32_t pos;
2603 
2604  assert(hashmap != NULL);
2605  assert(hashmap->slots != NULL);
2606  assert(hashmap->hashes != NULL);
2607  assert(hashmap->mask > 0);
2608  assert(hashval != 0);
2609 
2610  pos = hashval>>(hashmap->shift);
2611  elemdistance = 0;
2612  while( TRUE ) /*lint !e716*/
2613  {
2614  uint32_t distance;
2615 
2616  /* if position is empty or key equal insert element */
2617  if( hashmap->hashes[pos] == 0 )
2618  {
2619  hashmap->slots[pos].origin = origin;
2620  hashmap->slots[pos].image = image;
2621  hashmap->hashes[pos] = hashval;
2622  ++hashmap->nelements;
2623  return SCIP_OKAY;
2624  }
2625 
2626  if( hashval == hashmap->hashes[pos] && origin == hashmap->slots[pos].origin )
2627  {
2628  if( override )
2629  {
2630  hashmap->slots[pos].origin = origin;
2631  hashmap->slots[pos].image = image;
2632  hashmap->hashes[pos] = hashval;
2633  return SCIP_OKAY;
2634  }
2635  else
2636  {
2637  return SCIP_KEYALREADYEXISTING;
2638  }
2639  }
2640 
2641  /* otherwise check if the current element at this position is closer to its hashvalue */
2642  distance = ELEM_DISTANCE(pos);
2643  if( distance < elemdistance )
2644  {
2645  SCIP_HASHMAPIMAGE tmp;
2646  uint32_t tmphash;
2647 
2648  /* if this is the case we insert the new element here and find a new position for the old one */
2649  elemdistance = distance;
2650  tmphash = hashval;
2651  hashval = hashmap->hashes[pos];
2652  hashmap->hashes[pos] = tmphash;
2653  SCIPswapPointers(&hashmap->slots[pos].origin, &origin);
2654  tmp = image;
2655  image = hashmap->slots[pos].image;
2656  hashmap->slots[pos].image = tmp;
2657  }
2658 
2659  /* continue until we have found an empty position */
2660  pos = (pos + 1) & hashmap->mask;
2661  ++elemdistance;
2662  }
2663 }
2664 
2665 /** lookup origin in the hashmap. If element is found returns true and the position of the element,
2666  * otherwise returns FALSE.
2667  */
2668 static
2670  SCIP_HASHMAP* hashmap, /**< hash table */
2671  void* origin, /**< origin to lookup */
2672  uint32_t* pos /**< pointer to store position of element, if exists */
2673  )
2674 {
2675  uint32_t hashval;
2676  uint32_t elemdistance;
2677 
2678  assert(hashmap != NULL);
2679  assert(hashmap->slots != NULL);
2680  assert(hashmap->hashes != NULL);
2681  assert(hashmap->mask > 0);
2682 
2683  /* get the hash value */
2684  hashval = hashvalue((size_t)origin);
2685  assert(hashval != 0);
2686 
2687  *pos = hashval>>(hashmap->shift);
2688  elemdistance = 0;
2689 
2690  while( TRUE ) /*lint !e716*/
2691  {
2692  uint32_t distance;
2693 
2694  /* slots is empty so element cannot be contained */
2695  if( hashmap->hashes[*pos] == 0 )
2696  return FALSE;
2697 
2698  distance = ELEM_DISTANCE(*pos);
2699  /* element can not be contained since otherwise we would have swapped it with this one during insert */
2700  if( elemdistance > distance )
2701  return FALSE;
2702 
2703  /* found element */
2704  if( hashmap->hashes[*pos] == hashval && hashmap->slots[*pos].origin == origin )
2705  return TRUE;
2706 
2707  *pos = (*pos + 1) & hashmap->mask;
2708  ++elemdistance;
2709  }
2710 }
2711 
2712 /** check if the load factor of the hashmap is too high and rebuild if necessary */
2713 static
2715  SCIP_HASHMAP* hashmap /**< hash table */
2716  )
2717 {
2718  assert(hashmap != NULL);
2719  assert(hashmap->shift < 32);
2720 
2721  /* use integer arithmetic to approximately check if load factor is above 90% */
2722  if( ((hashmap->nelements<<10)>>(32-hashmap->shift) > 921) )
2723  {
2724  SCIP_HASHMAPENTRY* slots;
2725  uint32_t* hashes;
2726  uint32_t nslots;
2727  uint32_t newnslots;
2728  uint32_t i;
2729 
2730  /* calculate new size (always power of two) */
2731  nslots = hashmap->mask + 1;
2732  --hashmap->shift;
2733  newnslots = 2*nslots;
2734  hashmap->mask = newnslots-1;
2735 
2736  /* reallocate array */
2737  SCIP_ALLOC( BMSallocBlockMemoryArray(hashmap->blkmem, &slots, newnslots) );
2738  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashmap->blkmem, &hashes, newnslots) );
2739 
2740  SCIPswapPointers((void**) &slots, (void**) &hashmap->slots);
2741  SCIPswapPointers((void**) &hashes, (void**) &hashmap->hashes);
2742  hashmap->nelements = 0;
2743 
2744  /* reinsert all elements */
2745  for( i = 0; i < nslots; ++i )
2746  {
2747  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2748  * and thus no bad return codes when inserting the elements
2749  */
2750  if( hashes[i] != 0 )
2751  {
2752  SCIP_CALL_ABORT( hashmapInsert(hashmap, slots[i].origin, slots[i].image, hashes[i], FALSE) );
2753  }
2754  }
2755 
2756  /* free old arrays */
2757  BMSfreeBlockMemoryArray(hashmap->blkmem, &hashes, nslots);
2758  BMSfreeBlockMemoryArray(hashmap->blkmem, &slots, nslots);
2759  }
2760 
2761  return SCIP_OKAY;
2762 }
2763 
2764 /** creates a hash map mapping pointers to pointers */
2766  SCIP_HASHMAP** hashmap, /**< pointer to store the created hash map */
2767  BMS_BLKMEM* blkmem, /**< block memory used to store hash map entries */
2768  int mapsize /**< size of the hash map */
2769  )
2770 {
2771  uint32_t nslots;
2772 
2773  assert(hashmap != NULL);
2774  assert(mapsize >= 0);
2775  assert(blkmem != NULL);
2776 
2777  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashmap) );
2778 
2779  /* dont create too small hashtables, i.e. at least size 32, and increase
2780  * the given size by divinding it by 0.9, since then no rebuilding will
2781  * be necessary if the given number of elements are inserted. Finally round
2782  * to the next power of two.
2783  */
2784  (*hashmap)->shift = 32;
2785  (*hashmap)->shift -= (int)ceil(log(MAX(32, mapsize / 0.9)) / log(2.0));
2786  nslots = 1u << (32 - (*hashmap)->shift);
2787  (*hashmap)->mask = nslots - 1;
2788  (*hashmap)->blkmem = blkmem;
2789  (*hashmap)->nelements = 0;
2790 
2791  SCIP_ALLOC( BMSallocBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots) );
2792  SCIP_ALLOC( BMSallocClearBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots) );
2793 
2794  return SCIP_OKAY;
2795 }
2796 
2797 /** frees the hash map */
2799  SCIP_HASHMAP** hashmap /**< pointer to the hash map */
2800  )
2801 {
2802  uint32_t nslots;
2803 
2804  assert(hashmap != NULL);
2805  assert(*hashmap != NULL);
2806 
2807  nslots = (*hashmap)->mask + 1;
2808 #ifdef SCIP_DEBUG
2809  {
2810  uint32_t maxprobelen = 0;
2811  uint64_t probelensum = 0;
2812  uint32_t i;
2813 
2814  assert(hashmap != NULL);
2815 
2816  for( i = 0; i < nslots; ++i )
2817  {
2818  if( (*hashmap)->hashes[i] != 0 )
2819  {
2820  uint32_t probelen = ((i + (*hashmap)->mask + 1 - ((*hashmap)->hashes[i]>>((*hashmap)->shift))) & (*hashmap)->mask) + 1;
2821  probelensum += probelen;
2822  maxprobelen = MAX(probelen, maxprobelen);
2823  }
2824  }
2825 
2826  SCIPdebugMessage("%u hash map entries, used %u/%u slots (%.1f%%)",
2827  (unsigned int)(*hashmap)->nelements, (unsigned int)(*hashmap)->nelements, (unsigned int)nslots,
2828  100.0*(SCIP_Real)(*hashmap)->nelements/(SCIP_Real)(nslots));
2829  if( (*hashmap)->nelements > 0 )
2830  SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
2831  (SCIP_Real)(probelensum)/(SCIP_Real)(*hashmap)->nelements, (unsigned int)maxprobelen);
2832  SCIPdebugMessage("\n");
2833  }
2834 #endif
2835 
2836  /* free main hash map data structure */
2837  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots);
2838  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots);
2839  BMSfreeBlockMemory((*hashmap)->blkmem, hashmap);
2840 }
2841 
2842 /** inserts new origin->image pair in hash map
2843  *
2844  * @note multiple insertion of same element is checked and results in an error
2845  */
2847  SCIP_HASHMAP* hashmap, /**< hash map */
2848  void* origin, /**< origin to set image for */
2849  void* image /**< new image for origin */
2850  )
2851 {
2852  uint32_t hashval;
2853  SCIP_HASHMAPIMAGE img;
2854 
2855  assert(hashmap != NULL);
2856  assert(hashmap->slots != NULL);
2857  assert(hashmap->hashes != NULL);
2858  assert(hashmap->mask > 0);
2859 
2860  SCIP_CALL( hashmapCheckLoad(hashmap) );
2861 
2862  /* get the hash value */
2863  hashval = hashvalue((size_t)origin);
2864 
2865  /* append origin->image pair to hash map */
2866  img.ptr = image;
2867  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
2868 
2869  return SCIP_OKAY;
2870 }
2871 
2872 /** inserts new origin->image pair in hash map
2873  *
2874  * @note multiple insertion of same element is checked and results in an error
2875  */
2877  SCIP_HASHMAP* hashmap, /**< hash map */
2878  void* origin, /**< origin to set image for */
2879  SCIP_Real image /**< new image for origin */
2880  )
2881 {
2882  uint32_t hashval;
2883  SCIP_HASHMAPIMAGE img;
2884 
2885  assert(hashmap != NULL);
2886  assert(hashmap->slots != NULL);
2887  assert(hashmap->hashes != NULL);
2888  assert(hashmap->mask > 0);
2889 
2890  SCIP_CALL( hashmapCheckLoad(hashmap) );
2891 
2892  /* get the hash value */
2893  hashval = hashvalue((size_t)origin);
2894 
2895  /* append origin->image pair to hash map */
2896  img.real = image;
2897  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
2898 
2899  return SCIP_OKAY;
2900 }
2901 
2902 /** retrieves image of given origin from the hash map, or NULL if no image exists */
2904  SCIP_HASHMAP* hashmap, /**< hash map */
2905  void* origin /**< origin to retrieve image for */
2906  )
2907 {
2908  uint32_t pos;
2909 
2910  assert(hashmap != NULL);
2911  assert(hashmap->slots != NULL);
2912  assert(hashmap->hashes != NULL);
2913  assert(hashmap->mask > 0);
2914 
2915  if( hashmapLookup(hashmap, origin, &pos) )
2916  return hashmap->slots[pos].image.ptr;
2917 
2918  return NULL;
2919 }
2920 
2921 /** retrieves image of given origin from the hash map, or NULL if no image exists */
2923  SCIP_HASHMAP* hashmap, /**< hash map */
2924  void* origin /**< origin to retrieve image for */
2925  )
2926 {
2927  uint32_t pos;
2928 
2929  assert(hashmap != NULL);
2930  assert(hashmap->slots != NULL);
2931  assert(hashmap->hashes != NULL);
2932  assert(hashmap->mask > 0);
2933 
2934  if( hashmapLookup(hashmap, origin, &pos) )
2935  return hashmap->slots[pos].image.real;
2936 
2937  return SCIP_INVALID;
2938 }
2939 
2940 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
2941  * or by appending a new origin->image pair
2942  */
2944  SCIP_HASHMAP* hashmap, /**< hash map */
2945  void* origin, /**< origin to set image for */
2946  void* image /**< new image for origin */
2947  )
2948 {
2949  uint32_t hashval;
2950  SCIP_HASHMAPIMAGE img;
2951 
2952  assert(hashmap != NULL);
2953  assert(hashmap->slots != NULL);
2954  assert(hashmap->mask > 0);
2955 
2956  SCIP_CALL( hashmapCheckLoad(hashmap) );
2957 
2958  /* get the hash value */
2959  hashval = hashvalue((size_t)origin);
2960 
2961  /* append origin->image pair to hash map */
2962  img.ptr = image;
2963  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
2964 
2965  return SCIP_OKAY;
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  SCIP_Real 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.real = image;
2991  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
2992 
2993  return SCIP_OKAY;
2994 }
2995 
2996 /** checks whether an image to the given origin exists in the hash map */
2998  SCIP_HASHMAP* hashmap, /**< hash map */
2999  void* origin /**< origin to search for */
3000  )
3001 {
3002  uint32_t pos;
3003 
3004  assert(hashmap != NULL);
3005  assert(hashmap->slots != NULL);
3006  assert(hashmap->hashes != NULL);
3007  assert(hashmap->mask > 0);
3008 
3009  return hashmapLookup(hashmap, origin, &pos);
3010 }
3011 
3012 /** removes origin->image pair from the hash map, if it exists */
3014  SCIP_HASHMAP* hashmap, /**< hash map */
3015  void* origin /**< origin to remove from the list */
3016  )
3017 {
3018  uint32_t pos;
3019 
3020  assert(hashmap != NULL);
3021  assert(hashmap->slots != NULL);
3022  assert(hashmap->mask > 0);
3023 
3024  assert(origin != NULL);
3025 
3026  if( hashmapLookup(hashmap, origin, &pos) )
3027  {
3028  /* remove element */
3029  hashmap->hashes[pos] = 0;
3030  --hashmap->nelements;
3031 
3032  /* move other elements if necessary */
3033  while( TRUE ) /*lint !e716*/
3034  {
3035  uint32_t nextpos = (pos + 1) & hashmap->mask;
3036 
3037  /* nothing to do since there is no chain that needs to be moved */
3038  if( hashmap->hashes[nextpos] == 0 )
3039  return SCIP_OKAY;
3040 
3041  /* check if the element is the start of a new chain and return if that is the case */
3042  if( (hashmap->hashes[nextpos]>>(hashmap->shift)) == nextpos )
3043  return SCIP_OKAY;
3044 
3045  /* element should be moved to the left and next element needs to be checked */
3046  hashmap->slots[pos].origin = hashmap->slots[nextpos].origin;
3047  hashmap->slots[pos].image = hashmap->slots[nextpos].image;
3048  hashmap->hashes[pos] = hashmap->hashes[nextpos];
3049  hashmap->hashes[nextpos] = 0;
3050 
3051  pos = nextpos;
3052  }
3053  }
3054 
3055  return SCIP_OKAY;
3056 }
3057 
3058 /** prints statistics about hash map usage */
3060  SCIP_HASHMAP* hashmap, /**< hash map */
3061  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
3062  )
3063 {
3064  uint32_t maxprobelen = 0;
3065  uint64_t probelensum = 0;
3066  uint32_t nslots;
3067  uint32_t i;
3068 
3069  assert(hashmap != NULL);
3070 
3071  nslots = hashmap->mask + 1;
3072 
3073  /* compute the maximum and average probe length */
3074  for( i = 0; i < nslots; ++i )
3075  {
3076  if( hashmap->hashes[i] != 0 )
3077  {
3078  uint32_t probelen = ELEM_DISTANCE(i) + 1;
3079  probelensum += probelen;
3080  maxprobelen = MAX(probelen, maxprobelen);
3081  }
3082  }
3083 
3084  /* print general hash map statistics */
3085  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
3086  (unsigned int)hashmap->nelements, (unsigned int)hashmap->nelements,
3087  (unsigned int)nslots, 100.0*(SCIP_Real)hashmap->nelements/(SCIP_Real)(nslots));
3088 
3089  /* if not empty print average and maximum probe length */
3090  if( hashmap->nelements > 0 )
3091  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
3092  (SCIP_Real)(probelensum)/(SCIP_Real)hashmap->nelements, (unsigned int)maxprobelen);
3093  SCIPmessagePrintInfo(messagehdlr, "\n");
3094 }
3095 
3096 /** indicates whether a hash map has no entries */
3098  SCIP_HASHMAP* hashmap /**< hash map */
3099  )
3100 {
3101  assert(hashmap != NULL);
3102 
3103  return hashmap->nelements == 0;
3104 }
3105 
3106 /** gives the number of elements in a hash map */
3108  SCIP_HASHMAP* hashmap /**< hash map */
3109  )
3110 {
3111  return (int) hashmap->nelements;
3112 }
3113 
3114 /** gives the number of entries in the internal arrays of a hash map */
3116  SCIP_HASHMAP* hashmap /**< hash map */
3117  )
3118 {
3119  return (int) hashmap->mask + 1;
3120 }
3121 
3122 /** gives the hashmap entry at the given index or NULL if entry is empty */
3124  SCIP_HASHMAP* hashmap, /**< hash map */
3125  int entryidx /**< index of hash map entry */
3126  )
3127 {
3128  assert(hashmap != NULL);
3129 
3130  return hashmap->hashes[entryidx] == 0 ? NULL : &hashmap->slots[entryidx];
3131 }
3132 
3133 /** gives the origin of the hashmap entry */
3135  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3136  )
3137 {
3138  assert(entry != NULL);
3139 
3140  return entry->origin;
3141 }
3142 
3143 /** gives the image of the hashmap entry */
3145  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3146  )
3147 {
3148  assert(entry != NULL);
3149 
3150  return entry->image.ptr;
3151 }
3152 
3153 /** gives the image of the hashmap entry */
3155  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3156  )
3157 {
3158  assert(entry != NULL);
3159 
3160  return entry->image.real;
3161 }
3162 
3163 /** removes all entries in a hash map. */
3165  SCIP_HASHMAP* hashmap /**< hash map */
3166  )
3167 {
3168  assert(hashmap != NULL);
3169 
3170  BMSclearMemoryArray(hashmap->hashes, hashmap->mask + 1);
3171 
3172  hashmap->nelements = 0;
3173 
3174  return SCIP_OKAY;
3175 }
3176 
3177 
3178 /*
3179  * Dynamic Arrays
3180  */
3181 
3182 /** creates a dynamic array of real values */
3184  SCIP_REALARRAY** realarray, /**< pointer to store the real array */
3185  BMS_BLKMEM* blkmem /**< block memory */
3186  )
3187 {
3188  assert(realarray != NULL);
3189  assert(blkmem != NULL);
3190 
3191  SCIP_ALLOC( BMSallocBlockMemory(blkmem, realarray) );
3192  (*realarray)->blkmem = blkmem;
3193  (*realarray)->vals = NULL;
3194  (*realarray)->valssize = 0;
3195  (*realarray)->firstidx = -1;
3196  (*realarray)->minusedidx = INT_MAX;
3197  (*realarray)->maxusedidx = INT_MIN;
3198 
3199  return SCIP_OKAY;
3200 }
3201 
3202 /** creates a copy of a dynamic array of real values */
3204  SCIP_REALARRAY** realarray, /**< pointer to store the copied real array */
3205  BMS_BLKMEM* blkmem, /**< block memory */
3206  SCIP_REALARRAY* sourcerealarray /**< dynamic real array to copy */
3207  )
3208 {
3209  assert(realarray != NULL);
3210  assert(sourcerealarray != NULL);
3211 
3212  SCIP_CALL( SCIPrealarrayCreate(realarray, blkmem) );
3213  if( sourcerealarray->valssize > 0 )
3214  {
3215  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*realarray)->vals, sourcerealarray->vals,
3216  sourcerealarray->valssize) );
3217  }
3218  (*realarray)->valssize = sourcerealarray->valssize;
3219  (*realarray)->firstidx = sourcerealarray->firstidx;
3220  (*realarray)->minusedidx = sourcerealarray->minusedidx;
3221  (*realarray)->maxusedidx = sourcerealarray->maxusedidx;
3222 
3223  return SCIP_OKAY;
3224 }
3225 
3226 /** frees a dynamic array of real values */
3228  SCIP_REALARRAY** realarray /**< pointer to the real array */
3229  )
3230 {
3231  assert(realarray != NULL);
3232  assert(*realarray != NULL);
3233 
3234  BMSfreeBlockMemoryArrayNull((*realarray)->blkmem, &(*realarray)->vals, (*realarray)->valssize);
3235  BMSfreeBlockMemory((*realarray)->blkmem, realarray);
3236 
3237  return SCIP_OKAY;
3238 }
3239 
3240 /** extends dynamic array to be able to store indices from minidx to maxidx */
3242  SCIP_REALARRAY* realarray, /**< dynamic real array */
3243  int arraygrowinit, /**< initial size of array */
3244  SCIP_Real arraygrowfac, /**< growing factor of array */
3245  int minidx, /**< smallest index to allocate storage for */
3246  int maxidx /**< largest index to allocate storage for */
3247  )
3248 {
3249  int nused;
3250  int nfree;
3251  int newfirstidx;
3252  int i;
3253 
3254  assert(realarray != NULL);
3255  assert(realarray->minusedidx == INT_MAX || realarray->firstidx >= 0);
3256  assert(realarray->maxusedidx == INT_MIN || realarray->firstidx >= 0);
3257  assert(realarray->minusedidx == INT_MAX || realarray->minusedidx >= realarray->firstidx);
3258  assert(realarray->maxusedidx == INT_MIN || realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3259  assert(0 <= minidx);
3260  assert(minidx <= maxidx);
3261 
3262  minidx = MIN(minidx, realarray->minusedidx);
3263  maxidx = MAX(maxidx, realarray->maxusedidx);
3264  assert(0 <= minidx);
3265  assert(minidx <= maxidx);
3266 
3267  SCIPdebugMessage("extending realarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
3268  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, minidx, maxidx);
3269 
3270  /* check, whether we have to allocate additional memory, or shift the array */
3271  nused = maxidx - minidx + 1;
3272  if( nused > realarray->valssize )
3273  {
3274  SCIP_Real* newvals;
3275  int newvalssize;
3276 
3277  /* allocate new memory storage */
3278  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
3279  SCIP_ALLOC( BMSallocBlockMemoryArray(realarray->blkmem, &newvals, newvalssize) );
3280  nfree = newvalssize - nused;
3281  newfirstidx = minidx - nfree/2;
3282  newfirstidx = MAX(newfirstidx, 0);
3283  assert(newfirstidx <= minidx);
3284  assert(maxidx < newfirstidx + newvalssize);
3285 
3286  /* initialize memory array by copying old values and setting new values to zero */
3287  if( realarray->firstidx != -1 )
3288  {
3289  for( i = 0; i < realarray->minusedidx - newfirstidx; ++i )
3290  newvals[i] = 0.0;
3291 
3292  /* check for possible overflow or negative value */
3293  assert(realarray->maxusedidx - realarray->minusedidx + 1 > 0);
3294 
3295  BMScopyMemoryArray(&newvals[realarray->minusedidx - newfirstidx],
3296  &(realarray->vals[realarray->minusedidx - realarray->firstidx]),
3297  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866 !e776*/
3298  for( i = realarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
3299  newvals[i] = 0.0;
3300  }
3301  else
3302  {
3303  for( i = 0; i < newvalssize; ++i )
3304  newvals[i] = 0.0;
3305  }
3306 
3307  /* free old memory storage, and set the new array parameters */
3308  BMSfreeBlockMemoryArrayNull(realarray->blkmem, &realarray->vals, realarray->valssize);
3309  realarray->vals = newvals;
3310  realarray->valssize = newvalssize;
3311  realarray->firstidx = newfirstidx;
3312  }
3313  else if( realarray->firstidx == -1 )
3314  {
3315  /* a sufficiently large memory storage exists, but it was cleared */
3316  nfree = realarray->valssize - nused;
3317  assert(nfree >= 0);
3318  realarray->firstidx = minidx - nfree/2;
3319  assert(realarray->firstidx <= minidx);
3320  assert(maxidx < realarray->firstidx + realarray->valssize);
3321 #ifndef NDEBUG
3322  for( i = 0; i < realarray->valssize; ++i )
3323  assert(realarray->vals[i] == 0.0);
3324 #endif
3325  }
3326  else if( minidx < realarray->firstidx )
3327  {
3328  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
3329  nfree = realarray->valssize - nused;
3330  assert(nfree >= 0);
3331  newfirstidx = minidx - nfree/2;
3332  newfirstidx = MAX(newfirstidx, 0);
3333  assert(newfirstidx <= minidx);
3334  assert(maxidx < newfirstidx + realarray->valssize);
3335 
3336  if( realarray->minusedidx <= realarray->maxusedidx )
3337  {
3338  int shift;
3339 
3340  assert(realarray->firstidx <= realarray->minusedidx);
3341  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3342 
3343  /* shift used part of array to the right */
3344  shift = realarray->firstidx - newfirstidx;
3345  assert(shift > 0);
3346  for( i = realarray->maxusedidx - realarray->firstidx; i >= realarray->minusedidx - realarray->firstidx; --i )
3347  {
3348  assert(0 <= i + shift && i + shift < realarray->valssize);
3349  realarray->vals[i + shift] = realarray->vals[i];
3350  }
3351  /* clear the formerly used head of the array */
3352  for( i = 0; i < shift; ++i )
3353  realarray->vals[realarray->minusedidx - realarray->firstidx + i] = 0.0;
3354  }
3355  realarray->firstidx = newfirstidx;
3356  }
3357  else if( maxidx >= realarray->firstidx + realarray->valssize )
3358  {
3359  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
3360  nfree = realarray->valssize - nused;
3361  assert(nfree >= 0);
3362  newfirstidx = minidx - nfree/2;
3363  newfirstidx = MAX(newfirstidx, 0);
3364  assert(newfirstidx <= minidx);
3365  assert(maxidx < newfirstidx + realarray->valssize);
3366 
3367  if( realarray->minusedidx <= realarray->maxusedidx )
3368  {
3369  int shift;
3370 
3371  assert(realarray->firstidx <= realarray->minusedidx);
3372  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3373 
3374  /* shift used part of array to the left */
3375  shift = newfirstidx - realarray->firstidx;
3376  assert(shift > 0);
3377  for( i = realarray->minusedidx - realarray->firstidx; i <= realarray->maxusedidx - realarray->firstidx; ++i )
3378  {
3379  assert(0 <= i - shift && i - shift < realarray->valssize);
3380  realarray->vals[i - shift] = realarray->vals[i];
3381  }
3382  /* clear the formerly used tail of the array */
3383  for( i = 0; i < shift; ++i )
3384  realarray->vals[realarray->maxusedidx - realarray->firstidx - i] = 0.0;
3385  }
3386  realarray->firstidx = newfirstidx;
3387  }
3388 
3389  assert(minidx >= realarray->firstidx);
3390  assert(maxidx < realarray->firstidx + realarray->valssize);
3391 
3392  return SCIP_OKAY;
3393 }
3394 
3395 /** clears a dynamic real array */
3397  SCIP_REALARRAY* realarray /**< dynamic real array */
3398  )
3399 {
3400  assert(realarray != NULL);
3401 
3402  SCIPdebugMessage("clearing realarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
3403  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx);
3404 
3405  if( realarray->minusedidx <= realarray->maxusedidx )
3406  {
3407  assert(realarray->firstidx <= realarray->minusedidx);
3408  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3409  assert(realarray->firstidx != -1);
3410  assert(realarray->valssize > 0);
3411 
3412  /* clear the used part of array */
3413  BMSclearMemoryArray(&realarray->vals[realarray->minusedidx - realarray->firstidx],
3414  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866*/
3415 
3416  /* mark the array cleared */
3417  realarray->minusedidx = INT_MAX;
3418  realarray->maxusedidx = INT_MIN;
3419  }
3420  assert(realarray->minusedidx == INT_MAX);
3421  assert(realarray->maxusedidx == INT_MIN);
3422 
3423  return SCIP_OKAY;
3424 }
3425 
3426 /** gets value of entry in dynamic array */
3428  SCIP_REALARRAY* realarray, /**< dynamic real array */
3429  int idx /**< array index to get value for */
3430  )
3431 {
3432  assert(realarray != NULL);
3433  assert(idx >= 0);
3434 
3435  if( idx < realarray->minusedidx || idx > realarray->maxusedidx )
3436  return 0.0;
3437  else
3438  {
3439  assert(realarray->vals != NULL);
3440  assert(idx - realarray->firstidx >= 0);
3441  assert(idx - realarray->firstidx < realarray->valssize);
3442 
3443  return realarray->vals[idx - realarray->firstidx];
3444  }
3445 }
3446 
3447 /** sets value of entry in dynamic array */
3449  SCIP_REALARRAY* realarray, /**< dynamic real array */
3450  int arraygrowinit, /**< initial size of array */
3451  SCIP_Real arraygrowfac, /**< growing factor of array */
3452  int idx, /**< array index to set value for */
3453  SCIP_Real val /**< value to set array index to */
3454  )
3455 {
3456  assert(realarray != NULL);
3457  assert(idx >= 0);
3458 
3459  SCIPdebugMessage("setting realarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %g\n",
3460  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, idx, val);
3461 
3462  if( val != 0.0 )
3463  {
3464  /* extend array to be able to store the index */
3465  SCIP_CALL( SCIPrealarrayExtend(realarray, arraygrowinit, arraygrowfac, idx, idx) );
3466  assert(idx >= realarray->firstidx);
3467  assert(idx < realarray->firstidx + realarray->valssize);
3468 
3469  /* set the array value of the index */
3470  realarray->vals[idx - realarray->firstidx] = val;
3471 
3472  /* update min/maxusedidx */
3473  realarray->minusedidx = MIN(realarray->minusedidx, idx);
3474  realarray->maxusedidx = MAX(realarray->maxusedidx, idx);
3475  }
3476  else if( idx >= realarray->firstidx && idx < realarray->firstidx + realarray->valssize )
3477  {
3478  /* set the array value of the index to zero */
3479  realarray->vals[idx - realarray->firstidx] = 0.0;
3480 
3481  /* check, if we can tighten the min/maxusedidx */
3482  if( idx == realarray->minusedidx )
3483  {
3484  assert(realarray->maxusedidx >= 0);
3485  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3486  do
3487  {
3488  realarray->minusedidx++;
3489  }
3490  while( realarray->minusedidx <= realarray->maxusedidx
3491  && realarray->vals[realarray->minusedidx - realarray->firstidx] == 0.0 );
3492 
3493  if( realarray->minusedidx > realarray->maxusedidx )
3494  {
3495  realarray->minusedidx = INT_MAX;
3496  realarray->maxusedidx = INT_MIN;
3497  }
3498  }
3499  else if( idx == realarray->maxusedidx )
3500  {
3501  assert(realarray->minusedidx >= 0);
3502  assert(realarray->minusedidx < realarray->maxusedidx);
3503  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3504  do
3505  {
3506  realarray->maxusedidx--;
3507  assert(realarray->minusedidx <= realarray->maxusedidx);
3508  }
3509  while( realarray->vals[realarray->maxusedidx - realarray->firstidx] == 0.0 );
3510  }
3511  }
3512 
3513  return SCIP_OKAY;
3514 }
3515 
3516 /** increases value of entry in dynamic array */
3518  SCIP_REALARRAY* realarray, /**< dynamic real array */
3519  int arraygrowinit, /**< initial size of array */
3520  SCIP_Real arraygrowfac, /**< growing factor of array */
3521  int idx, /**< array index to increase value for */
3522  SCIP_Real incval /**< value to increase array index */
3523  )
3524 {
3525  SCIP_Real oldval;
3526 
3527  oldval = SCIPrealarrayGetVal(realarray, idx);
3528  if( oldval != SCIP_INVALID ) /*lint !e777*/
3529  return SCIPrealarraySetVal(realarray, arraygrowinit, arraygrowfac, idx, oldval + incval);
3530  else
3531  return SCIP_OKAY;
3532 }
3533 
3534 /** returns the minimal index of all stored non-zero elements */
3536  SCIP_REALARRAY* realarray /**< dynamic real array */
3537  )
3538 {
3539  assert(realarray != NULL);
3540 
3541  return realarray->minusedidx;
3542 }
3543 
3544 /** returns the maximal index of all stored non-zero elements */
3546  SCIP_REALARRAY* realarray /**< dynamic real array */
3547  )
3548 {
3549  assert(realarray != NULL);
3550 
3551  return realarray->maxusedidx;
3552 }
3553 
3554 /** creates a dynamic array of int values */
3556  SCIP_INTARRAY** intarray, /**< pointer to store the int array */
3557  BMS_BLKMEM* blkmem /**< block memory */
3558  )
3559 {
3560  assert(intarray != NULL);
3561  assert(blkmem != NULL);
3562 
3563  SCIP_ALLOC( BMSallocBlockMemory(blkmem, intarray) );
3564  (*intarray)->blkmem = blkmem;
3565  (*intarray)->vals = NULL;
3566  (*intarray)->valssize = 0;
3567  (*intarray)->firstidx = -1;
3568  (*intarray)->minusedidx = INT_MAX;
3569  (*intarray)->maxusedidx = INT_MIN;
3570 
3571  return SCIP_OKAY;
3572 }
3573 
3574 /** creates a copy of a dynamic array of int values */
3576  SCIP_INTARRAY** intarray, /**< pointer to store the copied int array */
3577  BMS_BLKMEM* blkmem, /**< block memory */
3578  SCIP_INTARRAY* sourceintarray /**< dynamic int array to copy */
3579  )
3580 {
3581  assert(intarray != NULL);
3582  assert(sourceintarray != NULL);
3583 
3584  SCIP_CALL( SCIPintarrayCreate(intarray, blkmem) );
3585  if( sourceintarray->valssize > 0 )
3586  {
3587  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*intarray)->vals, sourceintarray->vals, sourceintarray->valssize) );
3588  }
3589  (*intarray)->valssize = sourceintarray->valssize;
3590  (*intarray)->firstidx = sourceintarray->firstidx;
3591  (*intarray)->minusedidx = sourceintarray->minusedidx;
3592  (*intarray)->maxusedidx = sourceintarray->maxusedidx;
3593 
3594  return SCIP_OKAY;
3595 }
3596 
3597 /** frees a dynamic array of int values */
3599  SCIP_INTARRAY** intarray /**< pointer to the int array */
3600  )
3601 {
3602  assert(intarray != NULL);
3603  assert(*intarray != NULL);
3604 
3605  BMSfreeBlockMemoryArrayNull((*intarray)->blkmem, &(*intarray)->vals, (*intarray)->valssize);
3606  BMSfreeBlockMemory((*intarray)->blkmem, intarray);
3607 
3608  return SCIP_OKAY;
3609 }
3610 
3611 /** extends dynamic array to be able to store indices from minidx to maxidx */
3613  SCIP_INTARRAY* intarray, /**< dynamic int array */
3614  int arraygrowinit, /**< initial size of array */
3615  SCIP_Real arraygrowfac, /**< growing factor of array */
3616  int minidx, /**< smallest index to allocate storage for */
3617  int maxidx /**< largest index to allocate storage for */
3618  )
3619 {
3620  int nused;
3621  int nfree;
3622  int newfirstidx;
3623  int i;
3624 
3625  assert(intarray != NULL);
3626  assert(intarray->minusedidx == INT_MAX || intarray->firstidx >= 0);
3627  assert(intarray->maxusedidx == INT_MIN || intarray->firstidx >= 0);
3628  assert(intarray->minusedidx == INT_MAX || intarray->minusedidx >= intarray->firstidx);
3629  assert(intarray->maxusedidx == INT_MIN || intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3630  assert(0 <= minidx);
3631  assert(minidx <= maxidx);
3632 
3633  minidx = MIN(minidx, intarray->minusedidx);
3634  maxidx = MAX(maxidx, intarray->maxusedidx);
3635  assert(0 <= minidx);
3636  assert(minidx <= maxidx);
3637 
3638  SCIPdebugMessage("extending intarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
3639  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, minidx, maxidx);
3640 
3641  /* check, whether we have to allocate additional memory, or shift the array */
3642  nused = maxidx - minidx + 1;
3643  if( nused > intarray->valssize )
3644  {
3645  int* newvals;
3646  int newvalssize;
3647 
3648  /* allocate new memory storage */
3649  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
3650  SCIP_ALLOC( BMSallocBlockMemoryArray(intarray->blkmem, &newvals, newvalssize) );
3651  nfree = newvalssize - nused;
3652  newfirstidx = minidx - nfree/2;
3653  newfirstidx = MAX(newfirstidx, 0);
3654  assert(newfirstidx <= minidx);
3655  assert(maxidx < newfirstidx + newvalssize);
3656 
3657  /* initialize memory array by copying old values and setting new values to zero */
3658  if( intarray->firstidx != -1 )
3659  {
3660  for( i = 0; i < intarray->minusedidx - newfirstidx; ++i )
3661  newvals[i] = 0;
3662 
3663  /* check for possible overflow or negative value */
3664  assert(intarray->maxusedidx - intarray->minusedidx + 1 > 0);
3665 
3666  BMScopyMemoryArray(&newvals[intarray->minusedidx - newfirstidx],
3667  &intarray->vals[intarray->minusedidx - intarray->firstidx],
3668  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866 !e776*/
3669  for( i = intarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
3670  newvals[i] = 0;
3671  }
3672  else
3673  {
3674  for( i = 0; i < newvalssize; ++i )
3675  newvals[i] = 0;
3676  }
3677 
3678  /* free old memory storage, and set the new array parameters */
3679  BMSfreeBlockMemoryArrayNull(intarray->blkmem, &intarray->vals, intarray->valssize);
3680  intarray->vals = newvals;
3681  intarray->valssize = newvalssize;
3682  intarray->firstidx = newfirstidx;
3683  }
3684  else if( intarray->firstidx == -1 )
3685  {
3686  /* a sufficiently large memory storage exists, but it was cleared */
3687  nfree = intarray->valssize - nused;
3688  assert(nfree >= 0);
3689  intarray->firstidx = minidx - nfree/2;
3690  assert(intarray->firstidx <= minidx);
3691  assert(maxidx < intarray->firstidx + intarray->valssize);
3692 #ifndef NDEBUG
3693  for( i = 0; i < intarray->valssize; ++i )
3694  assert(intarray->vals[i] == 0);
3695 #endif
3696  }
3697  else if( minidx < intarray->firstidx )
3698  {
3699  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
3700  nfree = intarray->valssize - nused;
3701  assert(nfree >= 0);
3702  newfirstidx = minidx - nfree/2;
3703  newfirstidx = MAX(newfirstidx, 0);
3704  assert(newfirstidx <= minidx);
3705  assert(maxidx < newfirstidx + intarray->valssize);
3706 
3707  if( intarray->minusedidx <= intarray->maxusedidx )
3708  {
3709  int shift;
3710 
3711  assert(intarray->firstidx <= intarray->minusedidx);
3712  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3713 
3714  /* shift used part of array to the right */
3715  shift = intarray->firstidx - newfirstidx;
3716  assert(shift > 0);
3717  for( i = intarray->maxusedidx - intarray->firstidx; i >= intarray->minusedidx - intarray->firstidx; --i )
3718  {
3719  assert(0 <= i + shift && i + shift < intarray->valssize);
3720  intarray->vals[i + shift] = intarray->vals[i];
3721  }
3722  /* clear the formerly used head of the array */
3723  for( i = 0; i < shift; ++i )
3724  intarray->vals[intarray->minusedidx - intarray->firstidx + i] = 0;
3725  }
3726  intarray->firstidx = newfirstidx;
3727  }
3728  else if( maxidx >= intarray->firstidx + intarray->valssize )
3729  {
3730  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
3731  nfree = intarray->valssize - nused;
3732  assert(nfree >= 0);
3733  newfirstidx = minidx - nfree/2;
3734  newfirstidx = MAX(newfirstidx, 0);
3735  assert(newfirstidx <= minidx);
3736  assert(maxidx < newfirstidx + intarray->valssize);
3737 
3738  if( intarray->minusedidx <= intarray->maxusedidx )
3739  {
3740  int shift;
3741 
3742  assert(intarray->firstidx <= intarray->minusedidx);
3743  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3744 
3745  /* shift used part of array to the left */
3746  shift = newfirstidx - intarray->firstidx;
3747  assert(shift > 0);
3748  for( i = intarray->minusedidx - intarray->firstidx; i <= intarray->maxusedidx - intarray->firstidx; ++i )
3749  {
3750  assert(0 <= i - shift && i - shift < intarray->valssize);
3751  intarray->vals[i - shift] = intarray->vals[i];
3752  }
3753  /* clear the formerly used tail of the array */
3754  for( i = 0; i < shift; ++i )
3755  intarray->vals[intarray->maxusedidx - intarray->firstidx - i] = 0;
3756  }
3757  intarray->firstidx = newfirstidx;
3758  }
3759 
3760  assert(minidx >= intarray->firstidx);
3761  assert(maxidx < intarray->firstidx + intarray->valssize);
3762 
3763  return SCIP_OKAY;
3764 }
3765 
3766 /** clears a dynamic int array */
3768  SCIP_INTARRAY* intarray /**< dynamic int array */
3769  )
3770 {
3771  assert(intarray != NULL);
3772 
3773  SCIPdebugMessage("clearing intarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
3774  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx);
3775 
3776  if( intarray->minusedidx <= intarray->maxusedidx )
3777  {
3778  assert(intarray->firstidx <= intarray->minusedidx);
3779  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3780  assert(intarray->firstidx != -1);
3781  assert(intarray->valssize > 0);
3782 
3783  /* clear the used part of array */
3784  BMSclearMemoryArray(&intarray->vals[intarray->minusedidx - intarray->firstidx],
3785  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866*/
3786 
3787  /* mark the array cleared */
3788  intarray->minusedidx = INT_MAX;
3789  intarray->maxusedidx = INT_MIN;
3790  }
3791  assert(intarray->minusedidx == INT_MAX);
3792  assert(intarray->maxusedidx == INT_MIN);
3793 
3794  return SCIP_OKAY;
3795 }
3796 
3797 /** gets value of entry in dynamic array */
3799  SCIP_INTARRAY* intarray, /**< dynamic int array */
3800  int idx /**< array index to get value for */
3801  )
3802 {
3803  assert(intarray != NULL);
3804  assert(idx >= 0);
3805 
3806  if( idx < intarray->minusedidx || idx > intarray->maxusedidx )
3807  return 0;
3808  else
3809  {
3810  assert(intarray->vals != NULL);
3811  assert(idx - intarray->firstidx >= 0);
3812  assert(idx - intarray->firstidx < intarray->valssize);
3813 
3814  return intarray->vals[idx - intarray->firstidx];
3815  }
3816 }
3817 
3818 /** sets value of entry in dynamic array */
3820  SCIP_INTARRAY* intarray, /**< dynamic int array */
3821  int arraygrowinit, /**< initial size of array */
3822  SCIP_Real arraygrowfac, /**< growing factor of array */
3823  int idx, /**< array index to set value for */
3824  int val /**< value to set array index to */
3825  )
3826 {
3827  assert(intarray != NULL);
3828  assert(idx >= 0);
3829 
3830  SCIPdebugMessage("setting intarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %d\n",
3831  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, idx, val);
3832 
3833  if( val != 0 )
3834  {
3835  /* extend array to be able to store the index */
3836  SCIP_CALL( SCIPintarrayExtend(intarray, arraygrowinit, arraygrowfac, idx, idx) );
3837  assert(idx >= intarray->firstidx);
3838  assert(idx < intarray->firstidx + intarray->valssize);
3839 
3840  /* set the array value of the index */
3841  intarray->vals[idx - intarray->firstidx] = val;
3842 
3843  /* update min/maxusedidx */
3844  intarray->minusedidx = MIN(intarray->minusedidx, idx);
3845  intarray->maxusedidx = MAX(intarray->maxusedidx, idx);
3846  }
3847  else if( idx >= intarray->firstidx && idx < intarray->firstidx + intarray->valssize )
3848  {
3849  /* set the array value of the index to zero */
3850  intarray->vals[idx - intarray->firstidx] = 0;
3851 
3852  /* check, if we can tighten the min/maxusedidx */
3853  if( idx == intarray->minusedidx )
3854  {
3855  assert(intarray->maxusedidx >= 0);
3856  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3857  do
3858  {
3859  intarray->minusedidx++;
3860  }
3861  while( intarray->minusedidx <= intarray->maxusedidx
3862  && intarray->vals[intarray->minusedidx - intarray->firstidx] == 0 );
3863  if( intarray->minusedidx > intarray->maxusedidx )
3864  {
3865  intarray->minusedidx = INT_MAX;
3866  intarray->maxusedidx = INT_MIN;
3867  }
3868  }
3869  else if( idx == intarray->maxusedidx )
3870  {
3871  assert(intarray->minusedidx >= 0);
3872  assert(intarray->minusedidx < intarray->maxusedidx);
3873  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
3874  do
3875  {
3876  intarray->maxusedidx--;
3877  assert(intarray->minusedidx <= intarray->maxusedidx);
3878  }
3879  while( intarray->vals[intarray->maxusedidx - intarray->firstidx] == 0 );
3880  }
3881  }
3882 
3883  return SCIP_OKAY;
3884 }
3885 
3886 /** increases value of entry in dynamic array */
3888  SCIP_INTARRAY* intarray, /**< dynamic int array */
3889  int arraygrowinit, /**< initial size of array */
3890  SCIP_Real arraygrowfac, /**< growing factor of array */
3891  int idx, /**< array index to increase value for */
3892  int incval /**< value to increase array index */
3893  )
3894 {
3895  return SCIPintarraySetVal(intarray, arraygrowinit, arraygrowfac, idx, SCIPintarrayGetVal(intarray, idx) + incval);
3896 }
3897 
3898 /** returns the minimal index of all stored non-zero elements */
3900  SCIP_INTARRAY* intarray /**< dynamic int array */
3901  )
3902 {
3903  assert(intarray != NULL);
3904 
3905  return intarray->minusedidx;
3906 }
3907 
3908 /** returns the maximal index of all stored non-zero elements */
3910  SCIP_INTARRAY* intarray /**< dynamic int array */
3911  )
3912 {
3913  assert(intarray != NULL);
3914 
3915  return intarray->maxusedidx;
3916 }
3917 
3918 
3919 /** creates a dynamic array of bool values */
3921  SCIP_BOOLARRAY** boolarray, /**< pointer to store the bool array */
3922  BMS_BLKMEM* blkmem /**< block memory */
3923  )
3924 {
3925  assert(boolarray != NULL);
3926  assert(blkmem != NULL);
3927 
3928  SCIP_ALLOC( BMSallocBlockMemory(blkmem, boolarray) );
3929  (*boolarray)->blkmem = blkmem;
3930  (*boolarray)->vals = NULL;
3931  (*boolarray)->valssize = 0;
3932  (*boolarray)->firstidx = -1;
3933  (*boolarray)->minusedidx = INT_MAX;
3934  (*boolarray)->maxusedidx = INT_MIN;
3935 
3936  return SCIP_OKAY;
3937 }
3938 
3939 /** creates a copy of a dynamic array of bool values */
3941  SCIP_BOOLARRAY** boolarray, /**< pointer to store the copied bool array */
3942  BMS_BLKMEM* blkmem, /**< block memory */
3943  SCIP_BOOLARRAY* sourceboolarray /**< dynamic bool array to copy */
3944  )
3945 {
3946  assert(boolarray != NULL);
3947  assert(sourceboolarray != NULL);
3948 
3949  SCIP_CALL( SCIPboolarrayCreate(boolarray, blkmem) );
3950  if( sourceboolarray->valssize > 0 )
3951  {
3952  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*boolarray)->vals, sourceboolarray->vals,
3953  sourceboolarray->valssize) );
3954  }
3955  (*boolarray)->valssize = sourceboolarray->valssize;
3956  (*boolarray)->firstidx = sourceboolarray->firstidx;
3957  (*boolarray)->minusedidx = sourceboolarray->minusedidx;
3958  (*boolarray)->maxusedidx = sourceboolarray->maxusedidx;
3959 
3960  return SCIP_OKAY;
3961 }
3962 
3963 /** frees a dynamic array of bool values */
3965  SCIP_BOOLARRAY** boolarray /**< pointer to the bool array */
3966  )
3967 {
3968  assert(boolarray != NULL);
3969  assert(*boolarray != NULL);
3970 
3971  BMSfreeBlockMemoryArrayNull((*boolarray)->blkmem, &(*boolarray)->vals, (*boolarray)->valssize);
3972  BMSfreeBlockMemory((*boolarray)->blkmem, boolarray);
3973 
3974  return SCIP_OKAY;
3975 }
3976 
3977 /** extends dynamic array to be able to store indices from minidx to maxidx */
3979  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
3980  int arraygrowinit, /**< initial size of array */
3981  SCIP_Real arraygrowfac, /**< growing factor of array */
3982  int minidx, /**< smallest index to allocate storage for */
3983  int maxidx /**< largest index to allocate storage for */
3984  )
3985 {
3986  int nused;
3987  int nfree;
3988  int newfirstidx;
3989  int i;
3990 
3991  assert(boolarray != NULL);
3992  assert(boolarray->minusedidx == INT_MAX || boolarray->firstidx >= 0);
3993  assert(boolarray->maxusedidx == INT_MIN || boolarray->firstidx >= 0);
3994  assert(boolarray->minusedidx == INT_MAX || boolarray->minusedidx >= boolarray->firstidx);
3995  assert(boolarray->maxusedidx == INT_MIN || boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
3996  assert(0 <= minidx);
3997  assert(minidx <= maxidx);
3998 
3999  minidx = MIN(minidx, boolarray->minusedidx);
4000  maxidx = MAX(maxidx, boolarray->maxusedidx);
4001  assert(0 <= minidx);
4002  assert(minidx <= maxidx);
4003 
4004  SCIPdebugMessage("extending boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4005  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, minidx, maxidx);
4006 
4007  /* check, whether we have to allocate additional memory, or shift the array */
4008  nused = maxidx - minidx + 1;
4009  if( nused > boolarray->valssize )
4010  {
4011  SCIP_Bool* newvals;
4012  int newvalssize;
4013 
4014  /* allocate new memory storage */
4015  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4016  SCIP_ALLOC( BMSallocBlockMemoryArray(boolarray->blkmem, &newvals, newvalssize) );
4017  nfree = newvalssize - nused;
4018  newfirstidx = minidx - nfree/2;
4019  newfirstidx = MAX(newfirstidx, 0);
4020  assert(newfirstidx <= minidx);
4021  assert(maxidx < newfirstidx + newvalssize);
4022 
4023  /* initialize memory array by copying old values and setting new values to zero */
4024  if( boolarray->firstidx != -1 )
4025  {
4026  for( i = 0; i < boolarray->minusedidx - newfirstidx; ++i )
4027  newvals[i] = FALSE;
4028 
4029  /* check for possible overflow or negative value */
4030  assert(boolarray->maxusedidx - boolarray->minusedidx + 1 > 0);
4031 
4032  BMScopyMemoryArray(&newvals[boolarray->minusedidx - newfirstidx],
4033  &boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4034  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866 !e776*/
4035  for( i = boolarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4036  newvals[i] = FALSE;
4037  }
4038  else
4039  {
4040  for( i = 0; i < newvalssize; ++i )
4041  newvals[i] = FALSE;
4042  }
4043 
4044  /* free old memory storage, and set the new array parameters */
4045  BMSfreeBlockMemoryArrayNull(boolarray->blkmem, &boolarray->vals, boolarray->valssize);
4046  boolarray->vals = newvals;
4047  boolarray->valssize = newvalssize;
4048  boolarray->firstidx = newfirstidx;
4049  }
4050  else if( boolarray->firstidx == -1 )
4051  {
4052  /* a sufficiently large memory storage exists, but it was cleared */
4053  nfree = boolarray->valssize - nused;
4054  assert(nfree >= 0);
4055  boolarray->firstidx = minidx - nfree/2;
4056  assert(boolarray->firstidx <= minidx);
4057  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4058 #ifndef NDEBUG
4059  for( i = 0; i < boolarray->valssize; ++i )
4060  assert(boolarray->vals[i] == FALSE);
4061 #endif
4062  }
4063  else if( minidx < boolarray->firstidx )
4064  {
4065  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4066  nfree = boolarray->valssize - nused;
4067  assert(nfree >= 0);
4068  newfirstidx = minidx - nfree/2;
4069  newfirstidx = MAX(newfirstidx, 0);
4070  assert(newfirstidx <= minidx);
4071  assert(maxidx < newfirstidx + boolarray->valssize);
4072 
4073  if( boolarray->minusedidx <= boolarray->maxusedidx )
4074  {
4075  int shift;
4076 
4077  assert(boolarray->firstidx <= boolarray->minusedidx);
4078  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4079 
4080  /* shift used part of array to the right */
4081  shift = boolarray->firstidx - newfirstidx;
4082  assert(shift > 0);
4083  for( i = boolarray->maxusedidx - boolarray->firstidx; i >= boolarray->minusedidx - boolarray->firstidx; --i )
4084  {
4085  assert(0 <= i + shift && i + shift < boolarray->valssize);
4086  boolarray->vals[i + shift] = boolarray->vals[i];
4087  }
4088  /* clear the formerly used head of the array */
4089  for( i = 0; i < shift; ++i )
4090  boolarray->vals[boolarray->minusedidx - boolarray->firstidx + i] = FALSE;
4091  }
4092  boolarray->firstidx = newfirstidx;
4093  }
4094  else if( maxidx >= boolarray->firstidx + boolarray->valssize )
4095  {
4096  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4097  nfree = boolarray->valssize - nused;
4098  assert(nfree >= 0);
4099  newfirstidx = minidx - nfree/2;
4100  newfirstidx = MAX(newfirstidx, 0);
4101  assert(newfirstidx <= minidx);
4102  assert(maxidx < newfirstidx + boolarray->valssize);
4103 
4104  if( boolarray->minusedidx <= boolarray->maxusedidx )
4105  {
4106  int shift;
4107 
4108  assert(boolarray->firstidx <= boolarray->minusedidx);
4109  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4110 
4111  /* shift used part of array to the left */
4112  shift = newfirstidx - boolarray->firstidx;
4113  assert(shift > 0);
4114 
4115  assert(0 <= boolarray->minusedidx - boolarray->firstidx - shift);
4116  assert(boolarray->maxusedidx - boolarray->firstidx - shift < boolarray->valssize);
4117  BMSmoveMemoryArray(&(boolarray->vals[boolarray->minusedidx - boolarray->firstidx - shift]),
4118  &(boolarray->vals[boolarray->minusedidx - boolarray->firstidx]),
4119  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4120 
4121  /* clear the formerly used tail of the array */
4122  for( i = 0; i < shift; ++i )
4123  boolarray->vals[boolarray->maxusedidx - boolarray->firstidx - i] = FALSE;
4124  }
4125  boolarray->firstidx = newfirstidx;
4126  }
4127 
4128  assert(minidx >= boolarray->firstidx);
4129  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4130 
4131  return SCIP_OKAY;
4132 }
4133 
4134 /** clears a dynamic bool array */
4136  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4137  )
4138 {
4139  assert(boolarray != NULL);
4140 
4141  SCIPdebugMessage("clearing boolarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4142  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx);
4143 
4144  if( boolarray->minusedidx <= boolarray->maxusedidx )
4145  {
4146  assert(boolarray->firstidx <= boolarray->minusedidx);
4147  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4148  assert(boolarray->firstidx != -1);
4149  assert(boolarray->valssize > 0);
4150 
4151  /* clear the used part of array */
4152  BMSclearMemoryArray(&boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4153  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4154 
4155  /* mark the array cleared */
4156  boolarray->minusedidx = INT_MAX;
4157  boolarray->maxusedidx = INT_MIN;
4158  }
4159  assert(boolarray->minusedidx == INT_MAX);
4160  assert(boolarray->maxusedidx == INT_MIN);
4161 
4162  return SCIP_OKAY;
4163 }
4164 
4165 /** gets value of entry in dynamic array */
4167  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4168  int idx /**< array index to get value for */
4169  )
4170 {
4171  assert(boolarray != NULL);
4172  assert(idx >= 0);
4173 
4174  if( idx < boolarray->minusedidx || idx > boolarray->maxusedidx )
4175  return FALSE;
4176  else
4177  {
4178  assert(boolarray->vals != NULL);
4179  assert(idx - boolarray->firstidx >= 0);
4180  assert(idx - boolarray->firstidx < boolarray->valssize);
4181 
4182  return boolarray->vals[idx - boolarray->firstidx];
4183  }
4184 }
4185 
4186 /** sets value of entry in dynamic array */
4188  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4189  int arraygrowinit, /**< initial size of array */
4190  SCIP_Real arraygrowfac, /**< growing factor of array */
4191  int idx, /**< array index to set value for */
4192  SCIP_Bool val /**< value to set array index to */
4193  )
4194 {
4195  assert(boolarray != NULL);
4196  assert(idx >= 0);
4197 
4198  SCIPdebugMessage("setting boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %u\n",
4199  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, idx, val);
4200 
4201  if( val != FALSE )
4202  {
4203  /* extend array to be able to store the index */
4204  SCIP_CALL( SCIPboolarrayExtend(boolarray, arraygrowinit, arraygrowfac, idx, idx) );
4205  assert(idx >= boolarray->firstidx);
4206  assert(idx < boolarray->firstidx + boolarray->valssize);
4207 
4208  /* set the array value of the index */
4209  boolarray->vals[idx - boolarray->firstidx] = val;
4210 
4211  /* update min/maxusedidx */
4212  boolarray->minusedidx = MIN(boolarray->minusedidx, idx);
4213  boolarray->maxusedidx = MAX(boolarray->maxusedidx, idx);
4214  }
4215  else if( idx >= boolarray->firstidx && idx < boolarray->firstidx + boolarray->valssize )
4216  {
4217  /* set the array value of the index to zero */
4218  boolarray->vals[idx - boolarray->firstidx] = FALSE;
4219 
4220  /* check, if we can tighten the min/maxusedidx */
4221  if( idx == boolarray->minusedidx )
4222  {
4223  assert(boolarray->maxusedidx >= 0);
4224  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4225  do
4226  {
4227  boolarray->minusedidx++;
4228  }
4229  while( boolarray->minusedidx <= boolarray->maxusedidx
4230  && boolarray->vals[boolarray->minusedidx - boolarray->firstidx] == FALSE );
4231  if( boolarray->minusedidx > boolarray->maxusedidx )
4232  {
4233  boolarray->minusedidx = INT_MAX;
4234  boolarray->maxusedidx = INT_MIN;
4235  }
4236  }
4237  else if( idx == boolarray->maxusedidx )
4238  {
4239  assert(boolarray->minusedidx >= 0);
4240  assert(boolarray->minusedidx < boolarray->maxusedidx);
4241  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4242  do
4243  {
4244  boolarray->maxusedidx--;
4245  assert(boolarray->minusedidx <= boolarray->maxusedidx);
4246  }
4247  while( boolarray->vals[boolarray->maxusedidx - boolarray->firstidx] == FALSE );
4248  }
4249  }
4250 
4251  return SCIP_OKAY;
4252 }
4253 
4254 /** returns the minimal index of all stored non-zero elements */
4256  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4257  )
4258 {
4259  assert(boolarray != NULL);
4260 
4261  return boolarray->minusedidx;
4262 }
4263 
4264 /** returns the maximal index of all stored non-zero elements */
4266  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4267  )
4268 {
4269  assert(boolarray != NULL);
4270 
4271  return boolarray->maxusedidx;
4272 }
4273 
4274 
4275 /** creates a dynamic array of pointer values */
4277  SCIP_PTRARRAY** ptrarray, /**< pointer to store the ptr array */
4278  BMS_BLKMEM* blkmem /**< block memory */
4279  )
4280 {
4281  assert(ptrarray != NULL);
4282  assert(blkmem != NULL);
4283 
4284  SCIP_ALLOC( BMSallocBlockMemory(blkmem, ptrarray) );
4285  (*ptrarray)->blkmem = blkmem;
4286  (*ptrarray)->vals = NULL;
4287  (*ptrarray)->valssize = 0;
4288  (*ptrarray)->firstidx = -1;
4289  (*ptrarray)->minusedidx = INT_MAX;
4290  (*ptrarray)->maxusedidx = INT_MIN;
4291 
4292  return SCIP_OKAY;
4293 }
4294 
4295 /** creates a copy of a dynamic array of pointer values */
4297  SCIP_PTRARRAY** ptrarray, /**< pointer to store the copied ptr array */
4298  BMS_BLKMEM* blkmem, /**< block memory */
4299  SCIP_PTRARRAY* sourceptrarray /**< dynamic ptr array to copy */
4300  )
4301 {
4302  assert(ptrarray != NULL);
4303  assert(sourceptrarray != NULL);
4304 
4305  SCIP_CALL( SCIPptrarrayCreate(ptrarray, blkmem) );
4306  if( sourceptrarray->valssize > 0 )
4307  {
4308  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*ptrarray)->vals, sourceptrarray->vals, sourceptrarray->valssize) );
4309  }
4310  (*ptrarray)->valssize = sourceptrarray->valssize;
4311  (*ptrarray)->firstidx = sourceptrarray->firstidx;
4312  (*ptrarray)->minusedidx = sourceptrarray->minusedidx;
4313  (*ptrarray)->maxusedidx = sourceptrarray->maxusedidx;
4314 
4315  return SCIP_OKAY;
4316 }
4317 
4318 /** frees a dynamic array of pointer values */
4320  SCIP_PTRARRAY** ptrarray /**< pointer to the ptr array */
4321  )
4322 {
4323  assert(ptrarray != NULL);
4324  assert(*ptrarray != NULL);
4325 
4326  BMSfreeBlockMemoryArrayNull((*ptrarray)->blkmem, &(*ptrarray)->vals, (*ptrarray)->valssize);
4327  BMSfreeBlockMemory((*ptrarray)->blkmem, ptrarray);
4328 
4329  return SCIP_OKAY;
4330 }
4331 
4332 /** extends dynamic array to be able to store indices from minidx to maxidx */
4334  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
4335  int arraygrowinit, /**< initial size of array */
4336  SCIP_Real arraygrowfac, /**< growing factor of array */
4337  int minidx, /**< smallest index to allocate storage for */
4338  int maxidx /**< largest index to allocate storage for */
4339  )
4340 {
4341  int nused;
4342  int nfree;
4343  int newfirstidx;
4344  int i;
4345 
4346  assert(ptrarray != NULL);
4347  assert(ptrarray->minusedidx == INT_MAX || ptrarray->firstidx >= 0);
4348  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->firstidx >= 0);
4349  assert(ptrarray->minusedidx == INT_MAX || ptrarray->minusedidx >= ptrarray->firstidx);
4350  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4351  assert(0 <= minidx);
4352  assert(minidx <= maxidx);
4353 
4354  minidx = MIN(minidx, ptrarray->minusedidx);
4355  maxidx = MAX(maxidx, ptrarray->maxusedidx);
4356  assert(0 <= minidx);
4357  assert(minidx <= maxidx);
4358 
4359  SCIPdebugMessage("extending ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4360  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, minidx, maxidx);
4361 
4362  /* check, whether we have to allocate additional memory, or shift the array */
4363  nused = maxidx - minidx + 1;
4364  if( nused > ptrarray->valssize )
4365  {
4366  void** newvals;
4367  int newvalssize;
4368 
4369  /* allocate new memory storage */
4370  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4371  SCIP_ALLOC( BMSallocBlockMemoryArray(ptrarray->blkmem, &newvals, newvalssize) );
4372  nfree = newvalssize - nused;
4373  newfirstidx = minidx - nfree/2;
4374  newfirstidx = MAX(newfirstidx, 0);
4375  assert(newfirstidx <= minidx);
4376  assert(maxidx < newfirstidx + newvalssize);
4377 
4378  /* initialize memory array by copying old values and setting new values to zero */
4379  if( ptrarray->firstidx != -1 )
4380  {
4381  for( i = 0; i < ptrarray->minusedidx - newfirstidx; ++i )
4382  newvals[i] = NULL;
4383 
4384  /* check for possible overflow or negative value */
4385  assert(ptrarray->maxusedidx - ptrarray->minusedidx + 1 > 0);
4386 
4387  BMScopyMemoryArray(&newvals[ptrarray->minusedidx - newfirstidx],
4388  &(ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx]),
4389  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866 !e776*/
4390  for( i = ptrarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4391  newvals[i] = NULL;
4392  }
4393  else
4394  {
4395  for( i = 0; i < newvalssize; ++i )
4396  newvals[i] = NULL;
4397  }
4398 
4399  /* free old memory storage, and set the new array parameters */
4400  BMSfreeBlockMemoryArrayNull(ptrarray->blkmem, &ptrarray->vals, ptrarray->valssize);
4401  ptrarray->vals = newvals;
4402  ptrarray->valssize = newvalssize;
4403  ptrarray->firstidx = newfirstidx;
4404  }
4405  else if( ptrarray->firstidx == -1 )
4406  {
4407  /* a sufficiently large memory storage exists, but it was cleared */
4408  nfree = ptrarray->valssize - nused;
4409  assert(nfree >= 0);
4410  ptrarray->firstidx = minidx - nfree/2;
4411  assert(ptrarray->firstidx <= minidx);
4412  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
4413 #ifndef NDEBUG
4414  for( i = 0; i < ptrarray->valssize; ++i )
4415  assert(ptrarray->vals[i] == NULL);
4416 #endif
4417  }
4418  else if( minidx < ptrarray->firstidx )
4419  {
4420  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4421  nfree = ptrarray->valssize - nused;
4422  assert(nfree >= 0);
4423  newfirstidx = minidx - nfree/2;
4424  newfirstidx = MAX(newfirstidx, 0);
4425  assert(newfirstidx <= minidx);
4426  assert(maxidx < newfirstidx + ptrarray->valssize);
4427 
4428  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
4429  {
4430  int shift;
4431 
4432  assert(ptrarray->firstidx <= ptrarray->minusedidx);
4433  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4434 
4435  /* shift used part of array to the right */
4436  shift = ptrarray->firstidx - newfirstidx;
4437  assert(shift > 0);
4438  for( i = ptrarray->maxusedidx - ptrarray->firstidx; i >= ptrarray->minusedidx - ptrarray->firstidx; --i )
4439  {
4440  assert(0 <= i + shift && i + shift < ptrarray->valssize);
4441  ptrarray->vals[i + shift] = ptrarray->vals[i];
4442  }
4443  /* clear the formerly used head of the array */
4444  for( i = 0; i < shift; ++i )
4445  ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx + i] = NULL;
4446  }
4447  ptrarray->firstidx = newfirstidx;
4448  }
4449  else if( maxidx >= ptrarray->firstidx + ptrarray->valssize )
4450  {
4451  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4452  nfree = ptrarray->valssize - nused;
4453  assert(nfree >= 0);
4454  newfirstidx = minidx - nfree/2;
4455  newfirstidx = MAX(newfirstidx, 0);
4456  assert(newfirstidx <= minidx);
4457  assert(maxidx < newfirstidx + ptrarray->valssize);
4458 
4459  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
4460  {
4461  int shift;
4462 
4463  assert(ptrarray->firstidx <= ptrarray->minusedidx);
4464  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4465 
4466  /* shift used part of array to the left */
4467  shift = newfirstidx - ptrarray->firstidx;
4468  assert(shift > 0);
4469  for( i = ptrarray->minusedidx - ptrarray->firstidx; i <= ptrarray->maxusedidx - ptrarray->firstidx; ++i )
4470  {
4471  assert(0 <= i - shift && i - shift < ptrarray->valssize);
4472  ptrarray->vals[i - shift] = ptrarray->vals[i];
4473  }
4474  /* clear the formerly used tail of the array */
4475  for( i = 0; i < shift; ++i )
4476  ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx - i] = NULL;
4477  }
4478  ptrarray->firstidx = newfirstidx;
4479  }
4480 
4481  assert(minidx >= ptrarray->firstidx);
4482  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
4483 
4484  return SCIP_OKAY;
4485 }
4486 
4487 /** clears a dynamic pointer array */
4489  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
4490  )
4491 {
4492  assert(ptrarray != NULL);
4493 
4494  SCIPdebugMessage("clearing ptrarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4495  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx);
4496 
4497  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
4498  {
4499  assert(ptrarray->firstidx <= ptrarray->minusedidx);
4500  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4501  assert(ptrarray->firstidx != -1);
4502  assert(ptrarray->valssize > 0);
4503 
4504  /* clear the used part of array */
4505  BMSclearMemoryArray(&ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx],
4506  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866*/
4507 
4508  /* mark the array cleared */
4509  ptrarray->minusedidx = INT_MAX;
4510  ptrarray->maxusedidx = INT_MIN;
4511  }
4512  assert(ptrarray->minusedidx == INT_MAX);
4513  assert(ptrarray->maxusedidx == INT_MIN);
4514 
4515  return SCIP_OKAY;
4516 }
4517 
4518 /** gets value of entry in dynamic array */
4520  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
4521  int idx /**< array index to get value for */
4522  )
4523 {
4524  assert(ptrarray != NULL);
4525  assert(idx >= 0);
4526 
4527  if( idx < ptrarray->minusedidx || idx > ptrarray->maxusedidx )
4528  return NULL;
4529  else
4530  {
4531  assert(ptrarray->vals != NULL);
4532  assert(idx - ptrarray->firstidx >= 0);
4533  assert(idx - ptrarray->firstidx < ptrarray->valssize);
4534 
4535  return ptrarray->vals[idx - ptrarray->firstidx];
4536  }
4537 }
4538 
4539 /** sets value of entry in dynamic array */
4541  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
4542  int arraygrowinit, /**< initial size of array */
4543  SCIP_Real arraygrowfac, /**< growing factor of array */
4544  int idx, /**< array index to set value for */
4545  void* val /**< value to set array index to */
4546  )
4547 {
4548  assert(ptrarray != NULL);
4549  assert(idx >= 0);
4550 
4551  SCIPdebugMessage("setting ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %p\n",
4552  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, idx, val);
4553 
4554  if( val != NULL )
4555  {
4556  /* extend array to be able to store the index */
4557  SCIP_CALL( SCIPptrarrayExtend(ptrarray, arraygrowinit, arraygrowfac, idx, idx) );
4558  assert(idx >= ptrarray->firstidx);
4559  assert(idx < ptrarray->firstidx + ptrarray->valssize);
4560 
4561  /* set the array value of the index */
4562  ptrarray->vals[idx - ptrarray->firstidx] = val;
4563 
4564  /* update min/maxusedidx */
4565  ptrarray->minusedidx = MIN(ptrarray->minusedidx, idx);
4566  ptrarray->maxusedidx = MAX(ptrarray->maxusedidx, idx);
4567  }
4568  else if( idx >= ptrarray->firstidx && idx < ptrarray->firstidx + ptrarray->valssize )
4569  {
4570  /* set the array value of the index to zero */
4571  ptrarray->vals[idx - ptrarray->firstidx] = NULL;
4572 
4573  /* check, if we can tighten the min/maxusedidx */
4574  if( idx == ptrarray->minusedidx )
4575  {
4576  assert(ptrarray->maxusedidx >= 0);
4577  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4578  do
4579  {
4580  ptrarray->minusedidx++;
4581  }
4582  while( ptrarray->minusedidx <= ptrarray->maxusedidx
4583  && ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx] == NULL );
4584  if( ptrarray->minusedidx > ptrarray->maxusedidx )
4585  {
4586  ptrarray->minusedidx = INT_MAX;
4587  ptrarray->maxusedidx = INT_MIN;
4588  }
4589  }
4590  else if( idx == ptrarray->maxusedidx )
4591  {
4592  assert(ptrarray->minusedidx >= 0);
4593  assert(ptrarray->minusedidx < ptrarray->maxusedidx);
4594  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
4595  do
4596  {
4597  ptrarray->maxusedidx--;
4598  assert(ptrarray->minusedidx <= ptrarray->maxusedidx);
4599  }
4600  while( ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx] == NULL );
4601  }
4602  }
4603 
4604  return SCIP_OKAY;
4605 }
4606 
4607 /** returns the minimal index of all stored non-zero elements */
4609  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
4610  )
4611 {
4612  assert(ptrarray != NULL);
4613 
4614  return ptrarray->minusedidx;
4615 }
4616 
4617 /** returns the maximal index of all stored non-zero elements */
4619  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
4620  )
4621 {
4622  assert(ptrarray != NULL);
4623 
4624  return ptrarray->maxusedidx;
4625 }
4626 
4627 
4628 /*
4629  * Sorting algorithms
4630  */
4631 
4632 /** default comparer for integers */
4633 SCIP_DECL_SORTPTRCOMP(SCIPsortCompInt)
4634 {
4635  int value1;
4636  int value2;
4637 
4638  value1 = (int)(size_t)elem1;
4639  value2 = (int)(size_t)elem2;
4640 
4641  if( value1 < value2 )
4642  return -1;
4643 
4644  if( value2 < value1 )
4645  return 1;
4646 
4647  return 0;
4648 }
4649 
4650 /* first all upwards-sorting methods */
4651 
4652 /** sort an indexed element set in non-decreasing order, resulting in a permutation index array */
4654  int* perm, /**< pointer to store the resulting permutation */
4655  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
4656  void* dataptr, /**< pointer to data field that is given to the external compare method */
4657  int len /**< number of elements to be sorted (valid index range) */
4658  )
4659 {
4660  int pos;
4661 
4662  assert(indcomp != NULL);
4663  assert(len == 0 || perm != NULL);
4664 
4665  /* create identity permutation */
4666  for( pos = 0; pos < len; ++pos )
4667  perm[pos] = pos;
4668 
4669  SCIPsortInd(perm, indcomp, dataptr, len);
4670 }
4671 
4672 /* SCIPsortInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4673 #define SORTTPL_NAMEEXT Ind
4674 #define SORTTPL_KEYTYPE int
4675 #define SORTTPL_INDCOMP
4676 #include "scip/sorttpl.c" /*lint !e451*/
4677 
4678 
4679 /* SCIPsortPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4680 #define SORTTPL_NAMEEXT Ptr
4681 #define SORTTPL_KEYTYPE void*
4682 #define SORTTPL_PTRCOMP
4683 #include "scip/sorttpl.c" /*lint !e451*/
4684 
4685 
4686 /* SCIPsortPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4687 #define SORTTPL_NAMEEXT PtrPtr
4688 #define SORTTPL_KEYTYPE void*
4689 #define SORTTPL_FIELD1TYPE void*
4690 #define SORTTPL_PTRCOMP
4691 #include "scip/sorttpl.c" /*lint !e451*/
4692 
4693 
4694 /* SCIPsortPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4695 #define SORTTPL_NAMEEXT PtrReal
4696 #define SORTTPL_KEYTYPE void*
4697 #define SORTTPL_FIELD1TYPE SCIP_Real
4698 #define SORTTPL_PTRCOMP
4699 #include "scip/sorttpl.c" /*lint !e451*/
4700 
4701 
4702 /* SCIPsortPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4703 #define SORTTPL_NAMEEXT PtrInt
4704 #define SORTTPL_KEYTYPE void*
4705 #define SORTTPL_FIELD1TYPE int
4706 #define SORTTPL_PTRCOMP
4707 #include "scip/sorttpl.c" /*lint !e451*/
4708 
4709 
4710 /* SCIPsortPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4711 #define SORTTPL_NAMEEXT PtrBool
4712 #define SORTTPL_KEYTYPE void*
4713 #define SORTTPL_FIELD1TYPE SCIP_Bool
4714 #define SORTTPL_PTRCOMP
4715 #include "scip/sorttpl.c" /*lint !e451*/
4716 
4717 
4718 /* SCIPsortPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4719 #define SORTTPL_NAMEEXT PtrIntInt
4720 #define SORTTPL_KEYTYPE void*
4721 #define SORTTPL_FIELD1TYPE int
4722 #define SORTTPL_FIELD2TYPE int
4723 #define SORTTPL_PTRCOMP
4724 #include "scip/sorttpl.c" /*lint !e451*/
4725 
4726 
4727 /* SCIPsortPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4728 #define SORTTPL_NAMEEXT PtrRealInt
4729 #define SORTTPL_KEYTYPE void*
4730 #define SORTTPL_FIELD1TYPE SCIP_Real
4731 #define SORTTPL_FIELD2TYPE int
4732 #define SORTTPL_PTRCOMP
4733 #include "scip/sorttpl.c" /*lint !e451*/
4734 
4735 
4736 /* SCIPsortPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4737 #define SORTTPL_NAMEEXT PtrRealBool
4738 #define SORTTPL_KEYTYPE void*
4739 #define SORTTPL_FIELD1TYPE SCIP_Real
4740 #define SORTTPL_FIELD2TYPE SCIP_Bool
4741 #define SORTTPL_PTRCOMP
4742 #include "scip/sorttpl.c" /*lint !e451*/
4743 
4744 
4745 /* SCIPsortPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4746 #define SORTTPL_NAMEEXT PtrPtrInt
4747 #define SORTTPL_KEYTYPE void*
4748 #define SORTTPL_FIELD1TYPE void*
4749 #define SORTTPL_FIELD2TYPE int
4750 #define SORTTPL_PTRCOMP
4751 #include "scip/sorttpl.c" /*lint !e451*/
4752 
4753 
4754 /* SCIPsortPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4755 #define SORTTPL_NAMEEXT PtrPtrReal
4756 #define SORTTPL_KEYTYPE void*
4757 #define SORTTPL_FIELD1TYPE void*
4758 #define SORTTPL_FIELD2TYPE SCIP_Real
4759 #define SORTTPL_PTRCOMP
4760 #include "scip/sorttpl.c" /*lint !e451*/
4761 
4762 
4763 /* SCIPsortPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4764 #define SORTTPL_NAMEEXT PtrRealIntInt
4765 #define SORTTPL_KEYTYPE void*
4766 #define SORTTPL_FIELD1TYPE SCIP_Real
4767 #define SORTTPL_FIELD2TYPE int
4768 #define SORTTPL_FIELD3TYPE int
4769 #define SORTTPL_PTRCOMP
4770 #include "scip/sorttpl.c" /*lint !e451*/
4771 
4772 
4773 /* SCIPsortPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4774 #define SORTTPL_NAMEEXT PtrPtrIntInt
4775 #define SORTTPL_KEYTYPE void*
4776 #define SORTTPL_FIELD1TYPE void*
4777 #define SORTTPL_FIELD2TYPE int
4778 #define SORTTPL_FIELD3TYPE int
4779 #define SORTTPL_PTRCOMP
4780 #include "scip/sorttpl.c" /*lint !e451*/
4781 
4782 
4783 /* SCIPsortPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4784 #define SORTTPL_NAMEEXT PtrPtrRealInt
4785 #define SORTTPL_KEYTYPE void*
4786 #define SORTTPL_FIELD1TYPE void*
4787 #define SORTTPL_FIELD2TYPE SCIP_Real
4788 #define SORTTPL_FIELD3TYPE int
4789 #define SORTTPL_PTRCOMP
4790 #include "scip/sorttpl.c" /*lint !e451*/
4791 
4792 
4793 /* SCIPsortPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4794 #define SORTTPL_NAMEEXT PtrPtrRealBool
4795 #define SORTTPL_KEYTYPE void*
4796 #define SORTTPL_FIELD1TYPE void*
4797 #define SORTTPL_FIELD2TYPE SCIP_Real
4798 #define SORTTPL_FIELD3TYPE SCIP_Bool
4799 #define SORTTPL_PTRCOMP
4800 #include "scip/sorttpl.c" /*lint !e451*/
4801 
4802 
4803 /* SCIPsortPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4804 #define SORTTPL_NAMEEXT PtrPtrLongInt
4805 #define SORTTPL_KEYTYPE void*
4806 #define SORTTPL_FIELD1TYPE void*
4807 #define SORTTPL_FIELD2TYPE SCIP_Longint
4808 #define SORTTPL_FIELD3TYPE int
4809 #define SORTTPL_PTRCOMP
4810 #include "scip/sorttpl.c" /*lint !e451*/
4811 
4812 
4813 /* SCIPsortPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4814 #define SORTTPL_NAMEEXT PtrPtrLongIntInt
4815 #define SORTTPL_KEYTYPE void*
4816 #define SORTTPL_FIELD1TYPE void*
4817 #define SORTTPL_FIELD2TYPE SCIP_Longint
4818 #define SORTTPL_FIELD3TYPE int
4819 #define SORTTPL_FIELD4TYPE int
4820 #define SORTTPL_PTRCOMP
4821 #include "scip/sorttpl.c" /*lint !e451*/
4822 
4823 
4824 /* SCIPsortReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4825 #define SORTTPL_NAMEEXT Real
4826 #define SORTTPL_KEYTYPE SCIP_Real
4827 #include "scip/sorttpl.c" /*lint !e451*/
4828 
4829 
4830 /* SCIPsortRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4831 #define SORTTPL_NAMEEXT RealBoolPtr
4832 #define SORTTPL_KEYTYPE SCIP_Real
4833 #define SORTTPL_FIELD1TYPE SCIP_Bool
4834 #define SORTTPL_FIELD2TYPE void*
4835 #include "scip/sorttpl.c" /*lint !e451*/
4836 
4837 
4838 /* SCIPsortRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4839 #define SORTTPL_NAMEEXT RealPtr
4840 #define SORTTPL_KEYTYPE SCIP_Real
4841 #define SORTTPL_FIELD1TYPE void*
4842 #include "scip/sorttpl.c" /*lint !e451*/
4843 
4844 
4845 /* SCIPsortRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4846 #define SORTTPL_NAMEEXT RealInt
4847 #define SORTTPL_KEYTYPE SCIP_Real
4848 #define SORTTPL_FIELD1TYPE int
4849 #include "scip/sorttpl.c" /*lint !e451*/
4850 
4851 
4852 /* SCIPsortRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4853 #define SORTTPL_NAMEEXT RealIntInt
4854 #define SORTTPL_KEYTYPE SCIP_Real
4855 #define SORTTPL_FIELD1TYPE int
4856 #define SORTTPL_FIELD2TYPE int
4857 #include "scip/sorttpl.c" /*lint !e451*/
4858 
4859 
4860 /* SCIPsortRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4861 #define SORTTPL_NAMEEXT RealIntLong
4862 #define SORTTPL_KEYTYPE SCIP_Real
4863 #define SORTTPL_FIELD1TYPE int
4864 #define SORTTPL_FIELD2TYPE SCIP_Longint
4865 #include "scip/sorttpl.c" /*lint !e451*/
4866 
4867 
4868 /* SCIPsortRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4869 #define SORTTPL_NAMEEXT RealIntPtr
4870 #define SORTTPL_KEYTYPE SCIP_Real
4871 #define SORTTPL_FIELD1TYPE int
4872 #define SORTTPL_FIELD2TYPE void*
4873 #include "scip/sorttpl.c" /*lint !e451*/
4874 
4875 
4876 /* SCIPsortRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4877 #define SORTTPL_NAMEEXT RealRealPtr
4878 #define SORTTPL_KEYTYPE SCIP_Real
4879 #define SORTTPL_FIELD1TYPE SCIP_Real
4880 #define SORTTPL_FIELD2TYPE void*
4881 #include "scip/sorttpl.c" /*lint !e451*/
4882 
4883 
4884 /* SCIPsortRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4885 #define SORTTPL_NAMEEXT RealLongRealInt
4886 #define SORTTPL_KEYTYPE SCIP_Real
4887 #define SORTTPL_FIELD1TYPE SCIP_Longint
4888 #define SORTTPL_FIELD2TYPE SCIP_Real
4889 #define SORTTPL_FIELD3TYPE int
4890 #include "scip/sorttpl.c" /*lint !e451*/
4891 
4892 /* SCIPsortRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4893 #define SORTTPL_NAMEEXT RealRealIntInt
4894 #define SORTTPL_KEYTYPE SCIP_Real
4895 #define SORTTPL_FIELD1TYPE SCIP_Real
4896 #define SORTTPL_FIELD2TYPE int
4897 #define SORTTPL_FIELD3TYPE int
4898 #include "scip/sorttpl.c" /*lint !e451*/
4899 
4900 
4901 /* SCIPsortRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4902 #define SORTTPL_NAMEEXT RealRealRealInt
4903 #define SORTTPL_KEYTYPE SCIP_Real
4904 #define SORTTPL_FIELD1TYPE SCIP_Real
4905 #define SORTTPL_FIELD2TYPE SCIP_Real
4906 #define SORTTPL_FIELD3TYPE int
4907 #include "scip/sorttpl.c" /*lint !e451*/
4908 
4909 
4910 /* SCIPsortRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4911 #define SORTTPL_NAMEEXT RealRealRealPtr
4912 #define SORTTPL_KEYTYPE SCIP_Real
4913 #define SORTTPL_FIELD1TYPE SCIP_Real
4914 #define SORTTPL_FIELD2TYPE SCIP_Real
4915 #define SORTTPL_FIELD3TYPE void*
4916 #include "scip/sorttpl.c" /*lint !e451*/
4917 
4918 
4919 /* SCIPsortRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4920 #define SORTTPL_NAMEEXT RealPtrPtrInt
4921 #define SORTTPL_KEYTYPE SCIP_Real
4922 #define SORTTPL_FIELD1TYPE void*
4923 #define SORTTPL_FIELD2TYPE void*
4924 #define SORTTPL_FIELD3TYPE int
4925 #include "scip/sorttpl.c" /*lint !e451*/
4926 
4927 
4928 /* SCIPsortRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4929 #define SORTTPL_NAMEEXT RealPtrPtrIntInt
4930 #define SORTTPL_KEYTYPE SCIP_Real
4931 #define SORTTPL_FIELD1TYPE void*
4932 #define SORTTPL_FIELD2TYPE void*
4933 #define SORTTPL_FIELD3TYPE int
4934 #define SORTTPL_FIELD4TYPE int
4935 #include "scip/sorttpl.c" /*lint !e451*/
4936 
4937 
4938 /* SCIPsortRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4939 #define SORTTPL_NAMEEXT RealRealRealBoolPtr
4940 #define SORTTPL_KEYTYPE SCIP_Real
4941 #define SORTTPL_FIELD1TYPE SCIP_Real
4942 #define SORTTPL_FIELD2TYPE SCIP_Real
4943 #define SORTTPL_FIELD3TYPE SCIP_Bool
4944 #define SORTTPL_FIELD4TYPE void*
4945 #include "scip/sorttpl.c" /*lint !e451*/
4946 
4947 
4948 /* SCIPsortRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4949 #define SORTTPL_NAMEEXT RealRealRealBoolBoolPtr
4950 #define SORTTPL_KEYTYPE SCIP_Real
4951 #define SORTTPL_FIELD1TYPE SCIP_Real
4952 #define SORTTPL_FIELD2TYPE SCIP_Real
4953 #define SORTTPL_FIELD3TYPE SCIP_Bool
4954 #define SORTTPL_FIELD4TYPE SCIP_Bool
4955 #define SORTTPL_FIELD5TYPE void*
4956 #include "scip/sorttpl.c" /*lint !e451*/
4957 
4958 
4959 /* SCIPsortInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4960 #define SORTTPL_NAMEEXT Int
4961 #define SORTTPL_KEYTYPE int
4962 #include "scip/sorttpl.c" /*lint !e451*/
4963 
4964 
4965 /* SCIPsortIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4966 #define SORTTPL_NAMEEXT IntInt
4967 #define SORTTPL_KEYTYPE int
4968 #define SORTTPL_FIELD1TYPE int
4969 #include "scip/sorttpl.c" /*lint !e451*/
4970 
4971 
4972 /* SCIPsortIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4973 #define SORTTPL_NAMEEXT IntReal
4974 #define SORTTPL_KEYTYPE int
4975 #define SORTTPL_FIELD1TYPE SCIP_Real
4976 #include "scip/sorttpl.c" /*lint !e451*/
4977 
4978 
4979 /* SCIPsortIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4980 #define SORTTPL_NAMEEXT IntPtr
4981 #define SORTTPL_KEYTYPE int
4982 #define SORTTPL_FIELD1TYPE void*
4983 #include "scip/sorttpl.c" /*lint !e451*/
4984 
4985 
4986 /* SCIPsortIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4987 #define SORTTPL_NAMEEXT IntIntInt
4988 #define SORTTPL_KEYTYPE int
4989 #define SORTTPL_FIELD1TYPE int
4990 #define SORTTPL_FIELD2TYPE int
4991 #include "scip/sorttpl.c" /*lint !e451*/
4992 
4993 
4994 /* SCIPsortIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
4995 #define SORTTPL_NAMEEXT IntIntLong
4996 #define SORTTPL_KEYTYPE int
4997 #define SORTTPL_FIELD1TYPE int
4998 #define SORTTPL_FIELD2TYPE SCIP_Longint
4999 #include "scip/sorttpl.c" /*lint !e451*/
5000 
5001 /* SCIPsortIntRealLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5002 #define SORTTPL_NAMEEXT IntRealLong
5003 #define SORTTPL_KEYTYPE int
5004 #define SORTTPL_FIELD1TYPE SCIP_Real
5005 #define SORTTPL_FIELD2TYPE SCIP_Longint
5006 #include "scip/sorttpl.c" /*lint !e451*/
5007 
5008 
5009 /* SCIPsortIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5010 #define SORTTPL_NAMEEXT IntIntPtr
5011 #define SORTTPL_KEYTYPE int
5012 #define SORTTPL_FIELD1TYPE int
5013 #define SORTTPL_FIELD2TYPE void*
5014 #include "scip/sorttpl.c" /*lint !e451*/
5015 
5016 
5017 /* SCIPsortIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5018 #define SORTTPL_NAMEEXT IntIntReal
5019 #define SORTTPL_KEYTYPE int
5020 #define SORTTPL_FIELD1TYPE int
5021 #define SORTTPL_FIELD2TYPE SCIP_Real
5022 #include "scip/sorttpl.c" /*lint !e451*/
5023 
5024 
5025 /* SCIPsortIntPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5026 #define SORTTPL_NAMEEXT IntPtrReal
5027 #define SORTTPL_KEYTYPE int
5028 #define SORTTPL_FIELD1TYPE void*
5029 #define SORTTPL_FIELD2TYPE SCIP_Real
5030 #include "scip/sorttpl.c" /*lint !e451*/
5031 
5032 
5033 /* SCIPsortIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5034 #define SORTTPL_NAMEEXT IntIntIntPtr
5035 #define SORTTPL_KEYTYPE int
5036 #define SORTTPL_FIELD1TYPE int
5037 #define SORTTPL_FIELD2TYPE int
5038 #define SORTTPL_FIELD3TYPE void*
5039 #include "scip/sorttpl.c" /*lint !e451*/
5040 
5041 /* SCIPsortIntIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5042 #define SORTTPL_NAMEEXT IntIntIntReal
5043 #define SORTTPL_KEYTYPE int
5044 #define SORTTPL_FIELD1TYPE int
5045 #define SORTTPL_FIELD2TYPE int
5046 #define SORTTPL_FIELD3TYPE SCIP_Real
5047 #include "scip/sorttpl.c" /*lint !e451*/
5048 
5049 /* SCIPsortIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5050 #define SORTTPL_NAMEEXT IntPtrIntReal
5051 #define SORTTPL_KEYTYPE int
5052 #define SORTTPL_FIELD1TYPE void*
5053 #define SORTTPL_FIELD2TYPE int
5054 #define SORTTPL_FIELD3TYPE SCIP_Real
5055 #include "scip/sorttpl.c" /*lint !e451*/
5056 
5057 
5058 /* SCIPsortLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5059 #define SORTTPL_NAMEEXT Long
5060 #define SORTTPL_KEYTYPE SCIP_Longint
5061 #include "scip/sorttpl.c" /*lint !e451*/
5062 
5063 
5064 /* SCIPsortLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5065 #define SORTTPL_NAMEEXT LongPtr
5066 #define SORTTPL_KEYTYPE SCIP_Longint
5067 #define SORTTPL_FIELD1TYPE void*
5068 #include "scip/sorttpl.c" /*lint !e451*/
5069 
5070 
5071 /* SCIPsortLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5072 #define SORTTPL_NAMEEXT LongPtrInt
5073 #define SORTTPL_KEYTYPE SCIP_Longint
5074 #define SORTTPL_FIELD1TYPE void*
5075 #define SORTTPL_FIELD2TYPE int
5076 #include "scip/sorttpl.c" /*lint !e451*/
5077 
5078 
5079 /* SCIPsortLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5080 #define SORTTPL_NAMEEXT LongPtrRealBool
5081 #define SORTTPL_KEYTYPE SCIP_Longint
5082 #define SORTTPL_FIELD1TYPE void*
5083 #define SORTTPL_FIELD2TYPE SCIP_Real
5084 #define SORTTPL_FIELD3TYPE SCIP_Bool
5085 #include "scip/sorttpl.c" /*lint !e451*/
5086 
5087 
5088 /* SCIPsortLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5089 #define SORTTPL_NAMEEXT LongPtrRealRealBool
5090 #define SORTTPL_KEYTYPE SCIP_Longint
5091 #define SORTTPL_FIELD1TYPE void*
5092 #define SORTTPL_FIELD2TYPE SCIP_Real
5093 #define SORTTPL_FIELD3TYPE SCIP_Real
5094 #define SORTTPL_FIELD4TYPE SCIP_Bool
5095 #include "scip/sorttpl.c" /*lint !e451*/
5096 
5097 
5098 /* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5099 #define SORTTPL_NAMEEXT LongPtrRealRealIntBool
5100 #define SORTTPL_KEYTYPE SCIP_Longint
5101 #define SORTTPL_FIELD1TYPE void*
5102 #define SORTTPL_FIELD2TYPE SCIP_Real
5103 #define SORTTPL_FIELD3TYPE SCIP_Real
5104 #define SORTTPL_FIELD4TYPE int
5105 #define SORTTPL_FIELD5TYPE SCIP_Bool
5106 #include "scip/sorttpl.c" /*lint !e451*/
5107 
5108 
5109 /* SCIPsortLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5110 #define SORTTPL_NAMEEXT LongPtrPtrInt
5111 #define SORTTPL_KEYTYPE SCIP_Longint
5112 #define SORTTPL_FIELD1TYPE void*
5113 #define SORTTPL_FIELD2TYPE void*
5114 #define SORTTPL_FIELD3TYPE int
5115 #include "scip/sorttpl.c" /*lint !e451*/
5116 
5117 
5118 /* SCIPsortLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5119 #define SORTTPL_NAMEEXT LongPtrPtrIntInt
5120 #define SORTTPL_KEYTYPE SCIP_Longint
5121 #define SORTTPL_FIELD1TYPE void*
5122 #define SORTTPL_FIELD2TYPE void*
5123 #define SORTTPL_FIELD3TYPE int
5124 #define SORTTPL_FIELD4TYPE int
5125 #include "scip/sorttpl.c" /*lint !e451*/
5126 
5127 
5128 /* SCIPsortLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5129 #define SORTTPL_NAMEEXT LongPtrPtrBoolInt
5130 #define SORTTPL_KEYTYPE SCIP_Longint
5131 #define SORTTPL_FIELD1TYPE void*
5132 #define SORTTPL_FIELD2TYPE void*
5133 #define SORTTPL_FIELD3TYPE SCIP_Bool
5134 #define SORTTPL_FIELD4TYPE int
5135 #include "scip/sorttpl.c" /*lint !e451*/
5136 
5137 
5138 /* SCIPsortPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5139 #define SORTTPL_NAMEEXT PtrIntIntBoolBool
5140 #define SORTTPL_KEYTYPE void*
5141 #define SORTTPL_FIELD1TYPE int
5142 #define SORTTPL_FIELD2TYPE int
5143 #define SORTTPL_FIELD3TYPE SCIP_Bool
5144 #define SORTTPL_FIELD4TYPE SCIP_Bool
5145 #define SORTTPL_PTRCOMP
5146 #include "scip/sorttpl.c" /*lint !e451*/
5147 
5148 
5149 /* SCIPsortIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5150 #define SORTTPL_NAMEEXT IntPtrIntIntBoolBool
5151 #define SORTTPL_KEYTYPE int
5152 #define SORTTPL_FIELD1TYPE void*
5153 #define SORTTPL_FIELD2TYPE int
5154 #define SORTTPL_FIELD3TYPE int
5155 #define SORTTPL_FIELD4TYPE SCIP_Bool
5156 #define SORTTPL_FIELD5TYPE SCIP_Bool
5157 #include "scip/sorttpl.c" /*lint !e451*/
5158 
5159 
5160 /* now all downwards-sorting methods */
5161 
5162 
5163 /** sort an indexed element set in non-increasing order, resulting in a permutation index array */
5165  int* perm, /**< pointer to store the resulting permutation */
5166  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
5167  void* dataptr, /**< pointer to data field that is given to the external compare method */
5168  int len /**< number of elements to be sorted (valid index range) */
5169  )
5170 {
5171  int pos;
5172 
5173  assert(indcomp != NULL);
5174  assert(len == 0 || perm != NULL);
5175 
5176  /* create identity permutation */
5177  for( pos = 0; pos < len; ++pos )
5178  perm[pos] = pos;
5179 
5180  SCIPsortDownInd(perm, indcomp, dataptr, len);
5181 }
5182 
5183 
5184 /* SCIPsortDownInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5185 #define SORTTPL_NAMEEXT DownInd
5186 #define SORTTPL_KEYTYPE int
5187 #define SORTTPL_INDCOMP
5188 #define SORTTPL_BACKWARDS
5189 #include "scip/sorttpl.c" /*lint !e451*/
5190 
5191 
5192 /* SCIPsortDownPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5193 #define SORTTPL_NAMEEXT DownPtr
5194 #define SORTTPL_KEYTYPE void*
5195 #define SORTTPL_PTRCOMP
5196 #define SORTTPL_BACKWARDS
5197 #include "scip/sorttpl.c" /*lint !e451*/
5198 
5199 
5200 /* SCIPsortDownPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5201 #define SORTTPL_NAMEEXT DownPtrPtr
5202 #define SORTTPL_KEYTYPE void*
5203 #define SORTTPL_FIELD1TYPE void*
5204 #define SORTTPL_PTRCOMP
5205 #define SORTTPL_BACKWARDS
5206 #include "scip/sorttpl.c" /*lint !e451*/
5207 
5208 
5209 /* SCIPsortDownPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5210 #define SORTTPL_NAMEEXT DownPtrReal
5211 #define SORTTPL_KEYTYPE void*
5212 #define SORTTPL_FIELD1TYPE SCIP_Real
5213 #define SORTTPL_PTRCOMP
5214 #define SORTTPL_BACKWARDS
5215 #include "scip/sorttpl.c" /*lint !e451*/
5216 
5217 
5218 /* SCIPsortDownPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5219 #define SORTTPL_NAMEEXT DownPtrInt
5220 #define SORTTPL_KEYTYPE void*
5221 #define SORTTPL_FIELD1TYPE int
5222 #define SORTTPL_PTRCOMP
5223 #define SORTTPL_BACKWARDS
5224 #include "scip/sorttpl.c" /*lint !e451*/
5225 
5226 /* SCIPsortDownPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5227 #define SORTTPL_NAMEEXT DownPtrBool
5228 #define SORTTPL_KEYTYPE void*
5229 #define SORTTPL_FIELD1TYPE SCIP_Bool
5230 #define SORTTPL_PTRCOMP
5231 #define SORTTPL_BACKWARDS
5232 #include "scip/sorttpl.c" /*lint !e451*/
5233 
5234 /* SCIPsortDownPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5235 #define SORTTPL_NAMEEXT DownPtrIntInt
5236 #define SORTTPL_KEYTYPE void*
5237 #define SORTTPL_FIELD1TYPE int
5238 #define SORTTPL_FIELD2TYPE int
5239 #define SORTTPL_PTRCOMP
5240 #define SORTTPL_BACKWARDS
5241 #include "scip/sorttpl.c" /*lint !e451*/
5242 
5243 
5244 /* SCIPsortDownPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5245 #define SORTTPL_NAMEEXT DownPtrRealInt
5246 #define SORTTPL_KEYTYPE void*
5247 #define SORTTPL_FIELD1TYPE SCIP_Real
5248 #define SORTTPL_FIELD2TYPE int
5249 #define SORTTPL_PTRCOMP
5250 #define SORTTPL_BACKWARDS
5251 #include "scip/sorttpl.c" /*lint !e451*/
5252 
5253 
5254 /* SCIPsortDownPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5255 #define SORTTPL_NAMEEXT DownPtrRealBool
5256 #define SORTTPL_KEYTYPE void*
5257 #define SORTTPL_FIELD1TYPE SCIP_Real
5258 #define SORTTPL_FIELD2TYPE SCIP_Bool
5259 #define SORTTPL_PTRCOMP
5260 #define SORTTPL_BACKWARDS
5261 #include "scip/sorttpl.c" /*lint !e451*/
5262 
5263 
5264 /* SCIPsortDownPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5265 #define SORTTPL_NAMEEXT DownPtrPtrInt
5266 #define SORTTPL_KEYTYPE void*
5267 #define SORTTPL_FIELD1TYPE void*
5268 #define SORTTPL_FIELD2TYPE int
5269 #define SORTTPL_PTRCOMP
5270 #define SORTTPL_BACKWARDS
5271 #include "scip/sorttpl.c" /*lint !e451*/
5272 
5273 
5274 /* SCIPsortDownPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5275 #define SORTTPL_NAMEEXT DownPtrPtrReal
5276 #define SORTTPL_KEYTYPE void*
5277 #define SORTTPL_FIELD1TYPE void*
5278 #define SORTTPL_FIELD2TYPE SCIP_Real
5279 #define SORTTPL_PTRCOMP
5280 #define SORTTPL_BACKWARDS
5281 #include "scip/sorttpl.c" /*lint !e451*/
5282 
5283 
5284 /* SCIPsortDownPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5285 #define SORTTPL_NAMEEXT DownPtrRealIntInt
5286 #define SORTTPL_KEYTYPE void*
5287 #define SORTTPL_FIELD1TYPE SCIP_Real
5288 #define SORTTPL_FIELD2TYPE int
5289 #define SORTTPL_FIELD3TYPE int
5290 #define SORTTPL_PTRCOMP
5291 #define SORTTPL_BACKWARDS
5292 #include "scip/sorttpl.c" /*lint !e451*/
5293 
5294 
5295 /* SCIPsortDownPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5296 #define SORTTPL_NAMEEXT DownPtrPtrIntInt
5297 #define SORTTPL_KEYTYPE void*
5298 #define SORTTPL_FIELD1TYPE void*
5299 #define SORTTPL_FIELD2TYPE int
5300 #define SORTTPL_FIELD3TYPE int
5301 #define SORTTPL_PTRCOMP
5302 #define SORTTPL_BACKWARDS
5303 #include "scip/sorttpl.c" /*lint !e451*/
5304 
5305 
5306 /* SCIPsortDownPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5307 #define SORTTPL_NAMEEXT DownPtrPtrRealInt
5308 #define SORTTPL_KEYTYPE void*
5309 #define SORTTPL_FIELD1TYPE void*
5310 #define SORTTPL_FIELD2TYPE SCIP_Real
5311 #define SORTTPL_FIELD3TYPE int
5312 #define SORTTPL_PTRCOMP
5313 #define SORTTPL_BACKWARDS
5314 #include "scip/sorttpl.c" /*lint !e451*/
5315 
5316 
5317 /* SCIPsortDownPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5318 #define SORTTPL_NAMEEXT DownPtrPtrRealBool
5319 #define SORTTPL_KEYTYPE void*
5320 #define SORTTPL_FIELD1TYPE void*
5321 #define SORTTPL_FIELD2TYPE SCIP_Real
5322 #define SORTTPL_FIELD3TYPE SCIP_Bool
5323 #define SORTTPL_PTRCOMP
5324 #define SORTTPL_BACKWARDS
5325 #include "scip/sorttpl.c" /*lint !e451*/
5326 
5327 
5328 /* SCIPsortDownPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5329 #define SORTTPL_NAMEEXT DownPtrPtrLongInt
5330 #define SORTTPL_KEYTYPE void*
5331 #define SORTTPL_FIELD1TYPE void*
5332 #define SORTTPL_FIELD2TYPE SCIP_Longint
5333 #define SORTTPL_FIELD3TYPE int
5334 #define SORTTPL_PTRCOMP
5335 #define SORTTPL_BACKWARDS
5336 #include "scip/sorttpl.c" /*lint !e451*/
5337 
5338 
5339 /* SCIPsortDownPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5340 #define SORTTPL_NAMEEXT DownPtrPtrLongIntInt
5341 #define SORTTPL_KEYTYPE void*
5342 #define SORTTPL_FIELD1TYPE void*
5343 #define SORTTPL_FIELD2TYPE SCIP_Longint
5344 #define SORTTPL_FIELD3TYPE int
5345 #define SORTTPL_FIELD4TYPE int
5346 #define SORTTPL_PTRCOMP
5347 #define SORTTPL_BACKWARDS
5348 #include "scip/sorttpl.c" /*lint !e451*/
5349 
5350 
5351 /* SCIPsortDownReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5352 #define SORTTPL_NAMEEXT DownReal
5353 #define SORTTPL_KEYTYPE SCIP_Real
5354 #define SORTTPL_BACKWARDS
5355 #include "scip/sorttpl.c" /*lint !e451*/
5356 
5357 
5358 /* SCIPsortDownRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5359 #define SORTTPL_NAMEEXT DownRealBoolPtr
5360 #define SORTTPL_KEYTYPE SCIP_Real
5361 #define SORTTPL_FIELD1TYPE SCIP_Bool
5362 #define SORTTPL_FIELD2TYPE void*
5363 #define SORTTPL_BACKWARDS
5364 #include "scip/sorttpl.c" /*lint !e451*/
5365 
5366 
5367 /* SCIPsortDownRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5368 #define SORTTPL_NAMEEXT DownRealPtr
5369 #define SORTTPL_KEYTYPE SCIP_Real
5370 #define SORTTPL_FIELD1TYPE void*
5371 #define SORTTPL_BACKWARDS
5372 #include "scip/sorttpl.c" /*lint !e451*/
5373 
5374 
5375 /* SCIPsortDownRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5376 #define SORTTPL_NAMEEXT DownRealInt
5377 #define SORTTPL_KEYTYPE SCIP_Real
5378 #define SORTTPL_FIELD1TYPE int
5379 #define SORTTPL_BACKWARDS
5380 #include "scip/sorttpl.c" /*lint !e451*/
5381 
5382 
5383 /* SCIPsortDownRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5384 #define SORTTPL_NAMEEXT DownRealIntLong
5385 #define SORTTPL_KEYTYPE SCIP_Real
5386 #define SORTTPL_FIELD1TYPE int
5387 #define SORTTPL_FIELD2TYPE SCIP_Longint
5388 #define SORTTPL_BACKWARDS
5389 #include "scip/sorttpl.c" /*lint !e451*/
5390 
5391 
5392 /* SCIPsortDownRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5393 #define SORTTPL_NAMEEXT DownRealIntPtr
5394 #define SORTTPL_KEYTYPE SCIP_Real
5395 #define SORTTPL_FIELD1TYPE int
5396 #define SORTTPL_FIELD2TYPE void*
5397 #define SORTTPL_BACKWARDS
5398 #include "scip/sorttpl.c" /*lint !e451*/
5399 
5400 
5401 /* SCIPsortDownRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5402 #define SORTTPL_NAMEEXT DownRealPtrPtr
5403 #define SORTTPL_KEYTYPE SCIP_Real
5404 #define SORTTPL_FIELD1TYPE void*
5405 #define SORTTPL_FIELD2TYPE void*
5406 #define SORTTPL_BACKWARDS
5407 #include "scip/sorttpl.c" /*lint !e451*/
5408 
5409 /* SCIPsortDownRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5410 #define SORTTPL_NAMEEXT DownRealRealInt
5411 #define SORTTPL_KEYTYPE SCIP_Real
5412 #define SORTTPL_FIELD1TYPE SCIP_Real
5413 #define SORTTPL_FIELD2TYPE int
5414 #define SORTTPL_BACKWARDS
5415 #include "scip/sorttpl.c" /*lint !e451*/
5416 
5417 /* SCIPsortDownRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5418 #define SORTTPL_NAMEEXT DownRealRealPtr
5419 #define SORTTPL_KEYTYPE SCIP_Real
5420 #define SORTTPL_FIELD1TYPE SCIP_Real
5421 #define SORTTPL_FIELD2TYPE void*
5422 #define SORTTPL_BACKWARDS
5423 #include "scip/sorttpl.c" /*lint !e451*/
5424 
5425 /* SCIPsortDownRealRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5426 #define SORTTPL_NAMEEXT DownRealRealPtrPtr
5427 #define SORTTPL_KEYTYPE SCIP_Real
5428 #define SORTTPL_FIELD1TYPE SCIP_Real
5429 #define SORTTPL_FIELD2TYPE void*
5430 #define SORTTPL_FIELD3TYPE void*
5431 #define SORTTPL_BACKWARDS
5432 #include "scip/sorttpl.c" /*lint !e451*/
5433 
5434 
5435 /* SCIPsortDownRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5436 #define SORTTPL_NAMEEXT DownRealLongRealInt
5437 #define SORTTPL_KEYTYPE SCIP_Real
5438 #define SORTTPL_FIELD1TYPE SCIP_Longint
5439 #define SORTTPL_FIELD2TYPE SCIP_Real
5440 #define SORTTPL_FIELD3TYPE int
5441 #define SORTTPL_BACKWARDS
5442 #include "scip/sorttpl.c" /*lint !e451*/
5443 
5444 
5445 /* SCIPsortDownRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5446 #define SORTTPL_NAMEEXT DownRealRealIntInt
5447 #define SORTTPL_KEYTYPE SCIP_Real
5448 #define SORTTPL_FIELD1TYPE SCIP_Real
5449 #define SORTTPL_FIELD2TYPE int
5450 #define SORTTPL_FIELD3TYPE int
5451 #define SORTTPL_BACKWARDS
5452 #include "scip/sorttpl.c" /*lint !e451*/
5453 
5454 
5455 /* SCIPsortDownRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5456 #define SORTTPL_NAMEEXT DownRealRealRealInt
5457 #define SORTTPL_KEYTYPE SCIP_Real
5458 #define SORTTPL_FIELD1TYPE SCIP_Real
5459 #define SORTTPL_FIELD2TYPE SCIP_Real
5460 #define SORTTPL_FIELD3TYPE int
5461 #define SORTTPL_BACKWARDS
5462 #include "scip/sorttpl.c" /*lint !e451*/
5463 
5464 
5465 /* SCIPsortDownRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5466 #define SORTTPL_NAMEEXT DownRealRealRealPtr
5467 #define SORTTPL_KEYTYPE SCIP_Real
5468 #define SORTTPL_FIELD1TYPE SCIP_Real
5469 #define SORTTPL_FIELD2TYPE SCIP_Real
5470 #define SORTTPL_FIELD3TYPE void*
5471 #define SORTTPL_BACKWARDS
5472 #include "scip/sorttpl.c" /*lint !e451*/
5473 
5474 
5475 /* SCIPsortDownRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5476 #define SORTTPL_NAMEEXT DownRealPtrPtrInt
5477 #define SORTTPL_KEYTYPE SCIP_Real
5478 #define SORTTPL_FIELD1TYPE void*
5479 #define SORTTPL_FIELD2TYPE void*
5480 #define SORTTPL_FIELD3TYPE int
5481 #define SORTTPL_BACKWARDS
5482 #include "scip/sorttpl.c" /*lint !e451*/
5483 
5484 /* SCIPsortDownRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5485 #define SORTTPL_NAMEEXT DownRealPtrPtrIntInt
5486 #define SORTTPL_KEYTYPE SCIP_Real
5487 #define SORTTPL_FIELD1TYPE void*
5488 #define SORTTPL_FIELD2TYPE void*
5489 #define SORTTPL_FIELD3TYPE int
5490 #define SORTTPL_FIELD4TYPE int
5491 #define SORTTPL_BACKWARDS
5492 #include "scip/sorttpl.c" /*lint !e451*/
5493 
5494 
5495 /* SCIPsortDownRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5496 #define SORTTPL_NAMEEXT DownRealRealRealBoolPtr
5497 #define SORTTPL_KEYTYPE SCIP_Real
5498 #define SORTTPL_FIELD1TYPE SCIP_Real
5499 #define SORTTPL_FIELD2TYPE SCIP_Real
5500 #define SORTTPL_FIELD3TYPE SCIP_Bool
5501 #define SORTTPL_FIELD4TYPE void*
5502 #define SORTTPL_BACKWARDS
5503 #include "scip/sorttpl.c" /*lint !e451*/
5504 
5505 
5506 /* SCIPsortDownRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5507 #define SORTTPL_NAMEEXT DownRealRealRealBoolBoolPtr
5508 #define SORTTPL_KEYTYPE SCIP_Real
5509 #define SORTTPL_FIELD1TYPE SCIP_Real
5510 #define SORTTPL_FIELD2TYPE SCIP_Real
5511 #define SORTTPL_FIELD3TYPE SCIP_Bool
5512 #define SORTTPL_FIELD4TYPE SCIP_Bool
5513 #define SORTTPL_FIELD5TYPE void*
5514 #include "scip/sorttpl.c" /*lint !e451*/
5515 
5516 
5517 /* SCIPsortDownInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5518 #define SORTTPL_NAMEEXT DownInt
5519 #define SORTTPL_KEYTYPE int
5520 #define SORTTPL_BACKWARDS
5521 #include "scip/sorttpl.c" /*lint !e451*/
5522 
5523 
5524 /* SCIPsortDownIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5525 #define SORTTPL_NAMEEXT DownIntInt
5526 #define SORTTPL_KEYTYPE int
5527 #define SORTTPL_FIELD1TYPE int
5528 #define SORTTPL_BACKWARDS
5529 #include "scip/sorttpl.c" /*lint !e451*/
5530 
5531 
5532 /* SCIPsortDownIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5533 #define SORTTPL_NAMEEXT DownIntIntReal
5534 #define SORTTPL_KEYTYPE int
5535 #define SORTTPL_FIELD1TYPE int
5536 #define SORTTPL_FIELD2TYPE SCIP_Real
5537 #define SORTTPL_BACKWARDS
5538 #include "scip/sorttpl.c" /*lint !e451*/
5539 
5540 
5541 /* SCIPsortDownIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5542 #define SORTTPL_NAMEEXT DownIntReal
5543 #define SORTTPL_KEYTYPE int
5544 #define SORTTPL_FIELD1TYPE SCIP_Real
5545 #define SORTTPL_BACKWARDS
5546 #include "scip/sorttpl.c" /*lint !e451*/
5547 
5548 
5549 /* SCIPsortDownIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5550 #define SORTTPL_NAMEEXT DownIntPtr
5551 #define SORTTPL_KEYTYPE int
5552 #define SORTTPL_FIELD1TYPE void*
5553 #define SORTTPL_BACKWARDS
5554 #include "scip/sorttpl.c" /*lint !e451*/
5555 
5556 
5557 /* SCIPsortDownIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5558 #define SORTTPL_NAMEEXT DownIntIntInt
5559 #define SORTTPL_KEYTYPE int
5560 #define SORTTPL_FIELD1TYPE int
5561 #define SORTTPL_FIELD2TYPE int
5562 #define SORTTPL_BACKWARDS
5563 #include "scip/sorttpl.c" /*lint !e451*/
5564 
5565 
5566 /* SCIPsortDownIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5567 #define SORTTPL_NAMEEXT DownIntIntLong
5568 #define SORTTPL_KEYTYPE int
5569 #define SORTTPL_FIELD1TYPE int
5570 #define SORTTPL_FIELD2TYPE SCIP_Longint
5571 #define SORTTPL_BACKWARDS
5572 #include "scip/sorttpl.c" /*lint !e451*/
5573 
5574 
5575 /* SCIPsortDownIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5576 #define SORTTPL_NAMEEXT DownIntIntPtr
5577 #define SORTTPL_KEYTYPE int
5578 #define SORTTPL_FIELD1TYPE int
5579 #define SORTTPL_FIELD2TYPE void*
5580 #define SORTTPL_BACKWARDS
5581 #include "scip/sorttpl.c" /*lint !e451*/
5582 
5583 
5584 /* SCIPsortDownIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5585 #define SORTTPL_NAMEEXT DownIntIntIntPtr
5586 #define SORTTPL_KEYTYPE int
5587 #define SORTTPL_FIELD1TYPE int
5588 #define SORTTPL_FIELD2TYPE int
5589 #define SORTTPL_FIELD3TYPE void*
5590 #define SORTTPL_BACKWARDS
5591 #include "scip/sorttpl.c" /*lint !e451*/
5592 
5593 
5594 /* SCIPsortDownIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5595 #define SORTTPL_NAMEEXT DownIntPtrIntReal
5596 #define SORTTPL_KEYTYPE int
5597 #define SORTTPL_FIELD1TYPE void*
5598 #define SORTTPL_FIELD2TYPE int
5599 #define SORTTPL_FIELD3TYPE SCIP_Real
5600 #define SORTTPL_BACKWARDS
5601 #include "scip/sorttpl.c" /*lint !e451*/
5602 
5603 
5604 /* SCIPsortDownLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5605 #define SORTTPL_NAMEEXT DownLong
5606 #define SORTTPL_KEYTYPE SCIP_Longint
5607 #define SORTTPL_BACKWARDS
5608 #include "scip/sorttpl.c" /*lint !e451*/
5609 
5610 
5611 /* SCIPsortDownLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5612 #define SORTTPL_NAMEEXT DownLongPtr
5613 #define SORTTPL_KEYTYPE SCIP_Longint
5614 #define SORTTPL_FIELD1TYPE void*
5615 #define SORTTPL_BACKWARDS
5616 #include "scip/sorttpl.c" /*lint !e451*/
5617 
5618 
5619 /* SCIPsortDownLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5620 #define SORTTPL_NAMEEXT DownLongPtrInt
5621 #define SORTTPL_KEYTYPE SCIP_Longint
5622 #define SORTTPL_FIELD1TYPE void*
5623 #define SORTTPL_FIELD2TYPE int
5624 #define SORTTPL_BACKWARDS
5625 #include "scip/sorttpl.c" /*lint !e451*/
5626 
5627 
5628 /* SCIPsortDownLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5629 #define SORTTPL_NAMEEXT DownLongPtrRealBool
5630 #define SORTTPL_KEYTYPE SCIP_Longint
5631 #define SORTTPL_FIELD1TYPE void*
5632 #define SORTTPL_FIELD2TYPE SCIP_Real
5633 #define SORTTPL_FIELD3TYPE SCIP_Bool
5634 #define SORTTPL_BACKWARDS
5635 #include "scip/sorttpl.c" /*lint !e451*/
5636 
5637 
5638 /* SCIPsortDownLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5639 #define SORTTPL_NAMEEXT DownLongPtrRealRealBool
5640 #define SORTTPL_KEYTYPE SCIP_Longint
5641 #define SORTTPL_FIELD1TYPE void*
5642 #define SORTTPL_FIELD2TYPE SCIP_Real
5643 #define SORTTPL_FIELD3TYPE SCIP_Real
5644 #define SORTTPL_FIELD4TYPE SCIP_Bool
5645 #define SORTTPL_BACKWARDS
5646 #include "scip/sorttpl.c" /*lint !e451*/
5647 
5648 
5649 /* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5650 #define SORTTPL_NAMEEXT DownLongPtrRealRealIntBool
5651 #define SORTTPL_KEYTYPE SCIP_Longint
5652 #define SORTTPL_FIELD1TYPE void*
5653 #define SORTTPL_FIELD2TYPE SCIP_Real
5654 #define SORTTPL_FIELD3TYPE SCIP_Real
5655 #define SORTTPL_FIELD4TYPE int
5656 #define SORTTPL_FIELD5TYPE SCIP_Bool
5657 #define SORTTPL_BACKWARDS
5658 #include "scip/sorttpl.c" /*lint !e451*/
5659 
5660 
5661 /* SCIPsortDownLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5662 #define SORTTPL_NAMEEXT DownLongPtrPtrInt
5663 #define SORTTPL_KEYTYPE SCIP_Longint
5664 #define SORTTPL_FIELD1TYPE void*
5665 #define SORTTPL_FIELD2TYPE void*
5666 #define SORTTPL_FIELD3TYPE int
5667 #define SORTTPL_BACKWARDS
5668 #include "scip/sorttpl.c" /*lint !e451*/
5669 
5670 
5671 /* SCIPsortDownLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5672 #define SORTTPL_NAMEEXT DownLongPtrPtrIntInt
5673 #define SORTTPL_KEYTYPE SCIP_Longint
5674 #define SORTTPL_FIELD1TYPE void*
5675 #define SORTTPL_FIELD2TYPE void*
5676 #define SORTTPL_FIELD3TYPE int
5677 #define SORTTPL_FIELD4TYPE int
5678 #define SORTTPL_BACKWARDS
5679 #include "scip/sorttpl.c" /*lint !e451*/
5680 
5681 
5682 /* SCIPsortDownLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5683 #define SORTTPL_NAMEEXT DownLongPtrPtrBoolInt
5684 #define SORTTPL_KEYTYPE SCIP_Longint
5685 #define SORTTPL_FIELD1TYPE void*
5686 #define SORTTPL_FIELD2TYPE void*
5687 #define SORTTPL_FIELD3TYPE SCIP_Bool
5688 #define SORTTPL_FIELD4TYPE int
5689 #define SORTTPL_BACKWARDS
5690 #include "scip/sorttpl.c" /*lint !e451*/
5691 
5692 
5693 /* SCIPsortDownPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5694 #define SORTTPL_NAMEEXT DownPtrIntIntBoolBool
5695 #define SORTTPL_KEYTYPE void*
5696 #define SORTTPL_FIELD1TYPE int
5697 #define SORTTPL_FIELD2TYPE int
5698 #define SORTTPL_FIELD3TYPE SCIP_Bool
5699 #define SORTTPL_FIELD4TYPE SCIP_Bool
5700 #define SORTTPL_PTRCOMP
5701 #define SORTTPL_BACKWARDS
5702 #include "scip/sorttpl.c" /*lint !e451*/
5703 
5704 
5705 /* SCIPsortDownIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5706 #define SORTTPL_NAMEEXT DownIntPtrIntIntBoolBool
5707 #define SORTTPL_KEYTYPE int
5708 #define SORTTPL_FIELD1TYPE void*
5709 #define SORTTPL_FIELD2TYPE int
5710 #define SORTTPL_FIELD3TYPE int
5711 #define SORTTPL_FIELD4TYPE SCIP_Bool
5712 #define SORTTPL_FIELD5TYPE SCIP_Bool
5713 #define SORTTPL_BACKWARDS
5714 #include "scip/sorttpl.c" /*lint !e451*/
5715 
5716 /*
5717  * Resulting activity
5718  */
5719 
5720 /** create a resource activity */
5722  SCIP_RESOURCEACTIVITY** activity, /**< pointer to store the resource activity */
5723  SCIP_VAR* var, /**< start time variable of the activity */
5724  int duration, /**< duration of the activity */
5725  int demand /**< demand of the activity */
5726  )
5727 {
5728  assert(activity != NULL);
5729 
5730  SCIP_ALLOC( BMSallocMemory(activity) );
5731 
5732  (*activity)->var = var;
5733  (*activity)->duration = duration;
5734  (*activity)->demand = demand;
5735 
5736  return SCIP_OKAY;
5737 }
5738 
5739 /** frees a resource activity */
5741  SCIP_RESOURCEACTIVITY** activity /**< pointer to the resource activity */
5742  )
5743 {
5744  assert(activity != NULL);
5745  assert(*activity != NULL);
5746 
5747  BMSfreeMemory(activity);
5748 }
5749 
5750 /* some simple variable functions implemented as defines */
5751 
5752 #ifndef NDEBUG
5753 
5754 /* In debug mode, the following methods are implemented as function calls to ensure
5755  * type validity.
5756  * In optimized mode, the methods are implemented as defines to improve performance.
5757  * However, we want to have them in the library anyways, so we have to undef the defines.
5758  */
5759 
5760 #undef SCIPactivityGetVar
5761 #undef SCIPactivityGetDuration
5762 #undef SCIPactivityGetDemand
5763 #undef SCIPactivityGetEnergy
5764 
5765 /** returns the start time variable of the resource activity */
5767  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
5768  )
5769 {
5770  assert(activity != NULL);
5771 
5772  return activity->var;
5773 }
5774 
5775 /** returns the duration of the resource activity */
5777  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
5778  )
5779 {
5780  assert(activity != NULL);
5781 
5782  return activity->duration;
5783 }
5784 
5785 /** returns the demand of the resource activity */
5787  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
5788  )
5789 {
5790  assert(activity != NULL);
5791 
5792  return activity->demand;
5793 }
5794 
5795 /** returns the energy of the resource activity */
5797  SCIP_RESOURCEACTIVITY* activity /**< resource activity */
5798  )
5799 {
5800  assert(activity != NULL);
5801 
5802  return activity->duration * activity->demand ;
5803 }
5804 
5805 #endif
5806 
5807 /*
5808  * Resource Profile
5809  */
5810 
5811 /** creates resource profile */
5813  SCIP_PROFILE** profile, /**< pointer to store the resource profile */
5814  int capacity /**< resource capacity */
5815  )
5816 {
5817  assert(profile != NULL);
5818  assert(capacity > 0);
5819 
5820  SCIP_ALLOC( BMSallocMemory(profile) );
5821 
5822  (*profile)->arraysize = 10;
5823  SCIP_ALLOC( BMSallocMemoryArray(&(*profile)->timepoints, (*profile)->arraysize) );
5824  SCIP_ALLOC( BMSallocMemoryArray(&(*profile)->loads, (*profile)->arraysize) );
5825 
5826  /* setup resource profile for use */
5827  (*profile)->ntimepoints = 1;
5828  (*profile)->timepoints[0] = 0;
5829  (*profile)->loads[0] = 0;
5830  (*profile)->capacity = capacity;
5831 
5832  return SCIP_OKAY;
5833 }
5834 
5835 /** frees given resource profile */
5837  SCIP_PROFILE** profile /**< pointer to the resource profile */
5838  )
5839 {
5840  assert(profile != NULL);
5841  assert(*profile != NULL);
5842 
5843  /* free main hash map data structure */
5844  BMSfreeMemoryArray(&(*profile)->loads);
5845  BMSfreeMemoryArray(&(*profile)->timepoints);
5846  BMSfreeMemory(profile);
5847 }
5848 
5849 /** output of the given resource profile */
5851  SCIP_PROFILE* profile, /**< resource profile to output */
5852  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
5853  FILE* file /**< output file (or NULL for standard output) */
5854  )
5855 {
5856  int t;
5857 
5858  SCIPmessageFPrintInfo(messagehdlr, file, "Profile <%p> (capacity %d) --> ", profile, profile->capacity);
5859 
5860  for( t = 0; t < profile->ntimepoints; ++t )
5861  {
5862  if( t == 0 )
5863  SCIPmessageFPrintInfo(messagehdlr, file, "%d:(%d,%d)", t, profile->timepoints[t], profile->loads[t]);
5864  else
5865  SCIPmessageFPrintInfo(messagehdlr, file, ", %d:(%d,%d)", t, profile->timepoints[t], profile->loads[t]);
5866  }
5867 
5868  SCIPmessageFPrintInfo(messagehdlr, file,"\n");
5869 }
5870 
5871 /** returns the capacity of the resource profile */
5873  SCIP_PROFILE* profile /**< resource profile to use */
5874  )
5875 {
5876  assert(profile != NULL);
5877 
5878  return profile->capacity;
5879 }
5880 
5881 /** returns the number time points of the resource profile */
5883  SCIP_PROFILE* profile /**< resource profile to use */
5884  )
5885 {
5886  assert(profile != NULL);
5887 
5888  return profile->ntimepoints;
5889 }
5890 
5891 /** returns the time points of the resource profile */
5893  SCIP_PROFILE* profile /**< resource profile to use */
5894  )
5895 {
5896  assert(profile != NULL);
5897 
5898  return profile->timepoints;
5899 }
5900 
5901 /** returns the loads of the resource profile */
5903  SCIP_PROFILE* profile /**< resource profile to use */
5904  )
5905 {
5906  assert(profile != NULL);
5907 
5908  return profile->loads;
5909 }
5910 
5911 /** returns the time point for given position of the resource profile */
5913  SCIP_PROFILE* profile, /**< resource profile to use */
5914  int pos /**< position */
5915  )
5916 {
5917  assert(profile != NULL);
5918  assert(pos >= 0 && pos < profile->ntimepoints);
5919 
5920  return profile->timepoints[pos];
5921 }
5922 
5923 /** returns the loads of the resource profile at the given position */
5925  SCIP_PROFILE* profile, /**< resource profile */
5926  int pos /**< position */
5927  )
5928 {
5929  assert(profile != NULL);
5930  assert(pos >= 0 && pos < profile->ntimepoints);
5931 
5932  return profile->loads[pos];
5933 }
5934 
5935 /** returns if the given time point exists in the resource profile and stores the position of the given time point if it
5936  * exists; otherwise the position of the next smaller existing time point is stored
5937  */
5939  SCIP_PROFILE* profile, /**< resource profile to search */
5940  int timepoint, /**< time point to search for */
5941  int* pos /**< pointer to store the position */
5942  )
5943 {
5944  assert(profile != NULL);
5945  assert(timepoint >= 0);
5946  assert(profile->ntimepoints > 0);
5947  assert(profile->timepoints[0] == 0);
5948 
5949  /* find the position of time point in the time points array via binary search */
5950  if( SCIPsortedvecFindInt(profile->timepoints, timepoint, profile->ntimepoints, pos) )
5951  return TRUE;
5952 
5953  assert(*pos > 0);
5954  (*pos)--;
5955 
5956  return FALSE;
5957 }
5958 
5959 /* ensures that resource profile arrays is big enough */
5960 static
5962  SCIP_PROFILE* profile, /**< resource profile to insert the time point */
5963  int neededsize /**< needed size */
5964  )
5965 {
5966  assert(profile->arraysize > 0);
5967 
5968  /* check whether the arrays are big enough */
5969  if( neededsize <= profile->arraysize )
5970  return SCIP_OKAY;
5971 
5972  profile->arraysize *= 2;
5973 
5974  SCIP_ALLOC( BMSreallocMemoryArray(&profile->timepoints, profile->arraysize) );
5975  SCIP_ALLOC( BMSreallocMemoryArray(&profile->loads, profile->arraysize) );
5976 
5977  return SCIP_OKAY;
5978 }
5979 
5980 /** inserts the given time point into the resource profile if it this time point does not exists yet; returns its
5981  * position in the time point array
5982  */
5983 static
5985  SCIP_PROFILE* profile, /**< resource profile to insert the time point */
5986  int timepoint, /**< time point to insert */
5987  int* pos /**< pointer to store the insert position */
5988  )
5989 {
5990  assert(profile != NULL);
5991  assert(timepoint >= 0);
5992  assert(profile->arraysize >= profile->ntimepoints);
5993 
5994  /* get the position of the given time point in the resource profile array if it exists; otherwise the position of the
5995  * next smaller existing time point
5996  */
5997  if( !SCIPprofileFindLeft(profile, timepoint, pos) )
5998  {
5999  assert(*pos >= 0 && *pos < profile->ntimepoints);
6000  assert(timepoint >= profile->timepoints[*pos]);
6001 
6002  /* ensure that the arrays are big enough */
6003  SCIP_CALL( ensureProfileSize(profile, profile->ntimepoints + 1) );
6004  assert(profile->arraysize > profile->ntimepoints);
6005 
6006  /* insert new time point into the (sorted) resource profile */
6007  SCIPsortedvecInsertIntInt(profile->timepoints, profile->loads, timepoint, profile->loads[*pos],
6008  &profile->ntimepoints, pos);
6009  }
6010 
6011 #ifndef NDEBUG
6012  /* check if the time points are sorted */
6013  {
6014  int i;
6015  for( i = 1; i < profile->ntimepoints; ++i )
6016  assert(profile->timepoints[i-1] < profile->timepoints[i]);
6017  }
6018 #endif
6019 
6020  return SCIP_OKAY;
6021 }
6022 
6023 /** updates the resource profile due to inserting of a core */
6024 static
6026  SCIP_PROFILE* profile, /**< resource profile to update */
6027  int left, /**< left side of core interval */
6028  int right, /**< right side of core interval */
6029  int demand, /**< demand of the core */
6030  int* pos, /**< pointer to store the first position were it gets infeasible */
6031  SCIP_Bool* infeasible /**< pointer to store if the update is infeasible */
6032  )
6033 {
6034  int startpos;
6035  int endpos;
6036  int i;
6037 
6038  assert(profile != NULL);
6039  assert(profile->arraysize >= profile->ntimepoints);
6040  assert(left >= 0);
6041  assert(left < right);
6042  assert(infeasible != NULL);
6043 
6044  (*infeasible) = FALSE;
6045  (*pos) = -1;
6046 
6047  /* get position of the starttime in profile */
6048  SCIP_CALL( profileInsertTimepoint(profile, left, &startpos) );
6049  assert(profile->timepoints[startpos] == left);
6050 
6051  /* get position of the endtime in profile */
6052  SCIP_CALL( profileInsertTimepoint(profile, right, &endpos) );
6053  assert(profile->timepoints[endpos] == right);
6054 
6055  assert(startpos < endpos);
6056  assert(profile->arraysize >= profile->ntimepoints);
6057 
6058  /* remove/add the given demand from the core */
6059  for( i = startpos; i < endpos; ++i )
6060  {
6061  profile->loads[i] += demand;
6062 
6063  /* check if the core fits */
6064  if( profile->loads[i] > profile->capacity )
6065  {
6066  SCIPdebugMessage("core insertion detected infeasibility (pos %d)\n", i);
6067 
6068  (*infeasible) = TRUE;
6069  (*pos) = i;
6070 
6071  /* remove the partly inserted core since it does fit completely */
6072  for( ; i >= startpos; --i ) /*lint !e445*/
6073  profile->loads[i] -= demand;
6074 
6075  break;
6076  }
6077  }
6078 
6079  return SCIP_OKAY;
6080 }
6081 
6082 /** insert a core into resource profile; if the core is non-empty the resource profile will be updated otherwise nothing
6083  * happens
6084  */
6086  SCIP_PROFILE* profile, /**< resource profile */
6087  int left, /**< left side of the core */
6088  int right, /**< right side of the core */
6089  int demand, /**< demand of the core */
6090  int* pos, /**< pointer to store the first position were it gets infeasible */
6091  SCIP_Bool* infeasible /**< pointer to store if the core does not fit due to capacity */
6092  )
6093 {
6094  assert(profile != NULL);
6095  assert(left < right);
6096  assert(demand >= 0);
6097  assert(infeasible != NULL);
6098 
6099  (*infeasible) = FALSE;
6100  (*pos) = -1;
6101 
6102  /* insert core into the resource profile */
6103  SCIPdebugMessage("insert core [%d,%d] with demand %d\n", left, right, demand);
6104 
6105  if( demand > 0 )
6106  {
6107  /* try to insert core into the resource profile */
6108  SCIP_CALL( profileUpdate(profile, left, right, demand, pos, infeasible) );
6109  }
6110 
6111  return SCIP_OKAY;
6112 }
6113 
6114 /** subtracts the demand from the resource profile during core time */
6116  SCIP_PROFILE* profile, /**< resource profile to use */
6117  int left, /**< left side of the core */
6118  int right, /**< right side of the core */
6119  int demand /**< demand of the core */
6120  )
6121 {
6122  SCIP_Bool infeasible;
6123  int pos;
6124 
6125  assert(left < right);
6126 #ifndef NDEBUG
6127  {
6128  /* check if the left and right time points of the core correspond to a time point in the resource profile; this
6129  * should be the case since we added the core before to the resource profile
6130  */
6131  assert(SCIPprofileFindLeft(profile, left, &pos));
6132  assert(SCIPprofileFindLeft(profile, right, &pos));
6133  }
6134 #endif
6135 
6136  /* remove the core from the resource profile */
6137  SCIPdebugMessage("delete core [%d,%d] with demand %d\n", left, right, demand);
6138 
6139  SCIP_CALL( profileUpdate(profile, left, right, -demand, &pos, &infeasible) );
6140  assert(!infeasible);
6141 
6142  return SCIP_OKAY;
6143 }
6144 
6145 /** returns TRUE if the core (given by its demand and during) can be inserted at the given time point; otherwise FALSE */
6146 static
6148  SCIP_PROFILE* profile, /**< resource profile to use */
6149  int pos, /**< pointer to store the position in the profile to start the serch */
6150  int lst, /**< latest start time */
6151  int duration, /**< duration of the core */
6152  int demand, /**< demand of the core */
6153  SCIP_Bool* infeasible /**< pointer store if the corer cannot be inserted */
6154  )
6155 {
6156  int remainingduration;
6157  int startpos;
6158 
6159  assert(profile != NULL);
6160  assert(pos >= 0);
6161  assert(pos < profile->ntimepoints);
6162  assert(duration > 0);
6163  assert(demand > 0);
6164  assert(profile->loads[profile->ntimepoints-1] == 0);
6165 
6166  remainingduration = duration;
6167  startpos = pos;
6168  (*infeasible) = FALSE;
6169 
6170  if( profile->timepoints[startpos] > lst )
6171  {
6172  (*infeasible) = TRUE;
6173  return pos;
6174  }
6175 
6176  while( pos < profile->ntimepoints - 1 )
6177  {
6178  if( profile->loads[pos] + demand > profile->capacity )
6179  {
6180  SCIPdebugMessage("profile <%p>: core does not fit at time point %d (pos %d)\n", (void*)profile, profile->timepoints[pos], pos);
6181  startpos = pos + 1;
6182  remainingduration = duration;
6183 
6184  if( profile->timepoints[startpos] > lst )
6185  {
6186  (*infeasible) = TRUE;
6187  return pos;
6188  }
6189  }
6190  else
6191  remainingduration -= profile->timepoints[pos+1] - profile->timepoints[pos];
6192 
6193  if( remainingduration <= 0 )
6194  break;
6195 
6196  pos++;
6197  }
6198 
6199  return startpos;
6200 }
6201 
6202 /** return the earliest possible starting point within the time interval [lb,ub] for a given core (given by its demand
6203  * and duration)
6204  */
6206  SCIP_PROFILE* profile, /**< resource profile to use */
6207  int est, /**< earliest starting time of the given core */
6208  int lst, /**< latest starting time of the given core */
6209  int duration, /**< duration of the core */
6210  int demand, /**< demand of the core */
6211  SCIP_Bool* infeasible /**< pointer store if the corer cannot be inserted */
6212  )
6213 {
6214  SCIP_Bool found;
6215  int pos;
6216 
6217  assert(profile != NULL);
6218  assert(est >= 0);
6219  assert(est <= lst);
6220  assert(duration >= 0);
6221  assert(demand >= 0);
6222  assert(infeasible != NULL);
6223  assert(profile->ntimepoints > 0);
6224  assert(profile->loads[profile->ntimepoints-1] == 0);
6225 
6226  SCIPdebugMessage("profile <%p>: find earliest start time (demad %d, duration %d) [%d,%d]\n", (void*)profile, demand, duration, est, lst);
6227 
6228  if( duration == 0 || demand == 0 )
6229  {
6230  *infeasible = FALSE;
6231  return est;
6232  }
6233 
6234  found = SCIPprofileFindLeft(profile, est, &pos);
6235  SCIPdebugMessage("profile <%p>: earliest start time does %s exist as time point (pos %d)\n", (void*)profile, found ? "" : "not", pos);
6236 
6237  /* if the position is the last time point in the profile, the core can be inserted at its earliest start time */
6238  if( pos == profile->ntimepoints - 1 )
6239  {
6240  (*infeasible) = FALSE;
6241  return est;
6242  }
6243 
6244  if( found )
6245  {
6246  /* if the start time matches a time point in the profile we can just search */
6247  assert(profile->timepoints[pos] == est);
6248  pos = profileFindFeasibleStart(profile, pos, lst, duration, demand, infeasible);
6249 
6250  assert(pos < profile->ntimepoints);
6251  est = profile->timepoints[pos];
6252  }
6253  else if( profile->loads[pos] + demand > profile->capacity )
6254  {
6255  /* if the the time point left to the start time has not enough free capacity we can just search the profile
6256  * starting from the next time point
6257  */
6258  assert(profile->timepoints[pos] <= est);
6259  pos = profileFindFeasibleStart(profile, pos+1, lst, duration, demand, infeasible);
6260 
6261  assert(pos < profile->ntimepoints);
6262  est = profile->timepoints[pos];
6263  }
6264  else
6265  {
6266  int remainingduration;
6267 
6268  /* check if the core can be placed at its earliest start time */
6269 
6270  assert(pos < profile->ntimepoints - 1);
6271 
6272  remainingduration = duration - (profile->timepoints[pos+1] - est);
6273  SCIPdebugMessage("remaining duration %d\n", remainingduration);
6274 
6275 
6276  if( remainingduration <= 0 )
6277  (*infeasible) = FALSE;
6278  else
6279  {
6280  pos = profileFindFeasibleStart(profile, pos+1, prof