misc.c

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   misc.c
 * @ingroup OTHER_CFILES
 * @brief  miscellaneous methods
 * @author Tobias Achterberg
 * @author Gerald Gamrath
 * @author Stefan Heinz
 * @author Michael Winkler
 * @author Kati Wolter
 * @author Gregor Hendel
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
#define _USE_MATH_DEFINES   /* to get M_SQRT2 on Windows */  /*lint !750 */
 
#include <assert.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <ctype.h>
#include <math.h>
 
#include "scip/def.h"
#include "scip/pub_message.h"
#include "scip/misc.h"
#include "scip/intervalarith.h"
#include "scip/pub_misc.h"
 
#ifndef NDEBUG
#include "scip/struct_misc.h"
#endif
 
/*
 * methods for statistical tests
 */
 
/**< contains all critical values for a one-sided two sample t-test up to 15 degrees of freedom
 *   a critical value represents a threshold for rejecting the null-hypothesis in hypothesis testing at
 *   a certain confidence level;
 *
 *   access through method SCIPstudentTGetCriticalValue()
 *
 *  source: German Wikipedia
 *
 *  for confidence levels
 *  c =
 *  0.75    0.875     0.90      0.95      0.975 (one-sided)
 *  0.50    0.750     0.80      0.90      0.950 (two-sided)
 *
 */
static const SCIP_Real studentt_quartiles[] = {      /* df:*/
   1.000,    2.414,    3.078,    6.314,    12.706,   /*  1 */
   0.816,    1.604,    1.886,    2.920,    4.303,    /*  2 */
   0.765,    1.423,    1.638,    2.353,    3.182,    /*  3 */
   0.741,    1.344,    1.533,    2.132,    2.776,    /*  4 */
   0.727,    1.301,    1.476,    2.015,    2.571,    /*  5 */
   0.718,    1.273,    1.440,    1.943,    2.447,    /*  6 */
   0.711,    1.254,    1.415,    1.895,    2.365,    /*  7 */
   0.706,    1.240,    1.397,    1.860,    2.306,    /*  8 */
   0.703,    1.230,    1.383,    1.833,    2.262,    /*  9 */
   0.700,    1.221,    1.372,    1.812,    2.228,    /* 10 */
   0.697,    1.214,    1.363,    1.796,    2.201,    /* 11 */
   0.695,    1.209,    1.356,    1.782,    2.179,    /* 12 */
   0.694,    1.204,    1.350,    1.771,    2.160,    /* 13 */
   0.692,    1.200,    1.345,    1.761,    2.145,    /* 14 */
   0.691,    1.197,    1.341,    1.753,    2.131     /* 15 */
};
 
/**< critical values for higher degrees of freedom of Student-T distribution for the same error probabilities; infact,
 *   these are critical values of the standard normal distribution with mean 0 and variance 1
 */
static const SCIP_Real studentt_quartilesabove[] = {
   0.674,    1.150,    1.282,    1.645,    1.960
};
 
/** the maximum degrees of freedom represented before switching to normal approximation */
static const int studentt_maxdf = sizeof(studentt_quartiles)/(5 * sizeof(SCIP_Real));
 
/** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */
SCIP_Real SCIPstudentTGetCriticalValue(
   SCIP_CONFIDENCELEVEL  clevel,             /**< (one-sided) confidence level */
   int                   df                  /**< degrees of freedom */
   )
{
   if( df > studentt_maxdf )
      return studentt_quartilesabove[(int)clevel];
   else
      return studentt_quartiles[(int)clevel + 5 * (df - 1)];
}
 
/** compute a t-value for the hypothesis that x and y are from the same population; Assuming that
 *  x and y represent normally distributed random samples with equal variance, the returned value
 *  comes from a Student-T distribution with countx + county - 2 degrees of freedom; this
 *  value can be compared with a critical value (see also SCIPstudentTGetCriticalValue()) at
 *  a predefined confidence level for checking if x and y significantly differ in location
 */
SCIP_Real SCIPcomputeTwoSampleTTestValue(
   SCIP_Real             meanx,              /**< the mean of the first distribution */
   SCIP_Real             meany,              /**< the mean of the second distribution */
   SCIP_Real             variancex,          /**< the variance of the x-distribution */
   SCIP_Real             variancey,          /**< the variance of the y-distribution */
   SCIP_Real             countx,             /**< number of samples of x */
   SCIP_Real             county              /**< number of samples of y */
   )
{
   SCIP_Real pooledvariance;
   SCIP_Real tresult;
 
   /* too few samples */
   if( countx < 1.9 || county < 1.9 )
      return SCIP_INVALID;
 
   /* pooled variance is the weighted average of the two variances */
   pooledvariance = (countx - 1) * variancex + (county - 1) * variancey;
   pooledvariance /= (countx + county - 2);
 
   /* a variance close to zero means the distributions are basically constant */
   pooledvariance = MAX(pooledvariance, 1e-9);
 
   /* tresult can be understood as realization of a Student-T distributed variable with
    * countx + county - 2 degrees of freedom
    */
   tresult = (meanx - meany) / sqrt(pooledvariance);
   tresult *= sqrt(countx * county / (countx + county));
 
   return tresult;
}
 
/** returns the value of the Gauss error function evaluated at a given point */
SCIP_Real SCIPerf(
   SCIP_Real             x                   /**< value to evaluate */
   )
{
#if defined(_WIN32) || defined(_WIN64)
   SCIP_Real a1, a2, a3, a4, a5, p, t, y;
   int sign;
 
   a1 =  0.254829592;
   a2 = -0.284496736;
   a3 =  1.421413741;
   a4 = -1.453152027;
   a5 =  1.061405429;
   p  =  0.3275911;
 
   sign = (x >= 0) ? 1 : -1;
   x = REALABS(x);
 
   t = 1.0/(1.0 + p*x);
   y = 1.0 - (((((a5*t + a4)*t) + a3)*t + a2)*t + a1)*t*exp(-x*x);
   return sign * y;
#else
   return erf(x);
#endif
}
 
/** get critical value of a standard normal distribution  at a given confidence level */
SCIP_Real SCIPnormalGetCriticalValue(
   SCIP_CONFIDENCELEVEL  clevel              /**< (one-sided) confidence level */
   )
{
   return studentt_quartilesabove[(int)clevel];
}
 
/** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
 *  random variable x takes a value between -infinity and parameter \p value.
 *
 *  The distribution is given by the respective mean and deviation. This implementation
 *  uses the error function SCIPerf().
 */
SCIP_Real SCIPnormalCDF(
   SCIP_Real             mean,               /**< the mean value of the distribution */
   SCIP_Real             variance,           /**< the square of the deviation of the distribution */
   SCIP_Real             value               /**< the upper limit of the calculated distribution integral */
   )
{
   SCIP_Real normvalue;
   SCIP_Real std;
 
   /* we need to calculate the standard deviation from the variance */
   assert(variance >= -1e-9);
   if( variance < 1e-9 )
      std = 0.0;
   else
      std = sqrt(variance);
 
   /* special treatment for zero variance */
   if( std < 1e-9 )
   {
      if( value < mean + 1e-9 )
         return 1.0;
      else
         return 0.0;
   }
   assert( std != 0.0 ); /* for lint */
 
   /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
   normvalue = (value - mean)/(std * M_SQRT2);
 
   SCIPdebugMessage(" Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
 
   /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate the normvalue and
    * use the oddness of the SCIPerf()-function; special treatment for values close to zero.
    */
   if( normvalue < 1e-9 && normvalue > -1e-9 )
      return .5;
   else if( normvalue > 0 )
   {
      SCIP_Real erfresult;
 
      erfresult = SCIPerf(normvalue);
      return  erfresult / 2.0 + 0.5;
   }
   else
   {
      SCIP_Real erfresult;
 
      erfresult = SCIPerf(-normvalue);
 
      return 0.5 - erfresult / 2.0;
   }
}
 
/*
 * SCIP regression methods
 */
 
/** returns the number of observations of this regression */
int SCIPregressionGetNObservations(
   SCIP_REGRESSION*      regression          /**< regression data structure */
   )
{
   assert(regression != NULL);
 
   return regression->nobservations;
}
 
/** return the current slope of the regression */
SCIP_Real SCIPregressionGetSlope(
   SCIP_REGRESSION*      regression          /**< regression data structure */
   )
{
   assert(regression != NULL);
 
   return regression->slope;
}
 
/** get the current y-intercept of the regression */
SCIP_Real SCIPregressionGetIntercept(
   SCIP_REGRESSION*      regression          /**< regression data structure */
   )
{
   assert(regression != NULL);
 
   return regression->intercept;
}
 
/** recomputes regression coefficients from available observation data */
static
void regressionRecompute(
   SCIP_REGRESSION*      regression          /**< regression data structure */
   )
{
   /* regression coefficients require two or more observations and variance in x */
   if( regression->nobservations <= 1 || EPSZ(regression->variancesumx, 1e-9) )
   {
      regression->slope = SCIP_INVALID;
      regression->intercept = SCIP_INVALID;
      regression->corrcoef = SCIP_INVALID;
   }
   else if( EPSZ(regression->variancesumy, 1e-9) )
   {
      /* 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 */
      regression->slope = 0.0;
      regression->corrcoef = 0.0;
      regression->intercept = regression->meany;
   }
   else
   {
      /* we ruled this case out already, but to please some compilers... */
      assert(regression->variancesumx > 0.0);
      assert(regression->variancesumy > 0.0);
 
      /* compute slope */
      regression->slope = (regression->sumxy  - regression->nobservations * regression->meanx * regression->meany) / regression->variancesumx;
 
      /* compute y-intercept */
      regression->intercept = regression->meany - regression->slope * regression->meanx;
 
      /* compute empirical correlation coefficient */
      regression->corrcoef = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) /
         sqrt(regression->variancesumx * regression->variancesumy);
   }
}
 
/* incremental update of statistics describing mean and variance */
static
void incrementalStatsUpdate(
   SCIP_Real             value,              /**< current value to be added to incremental statistics */
   SCIP_Real*            meanptr,            /**< pointer to value of current mean */
   SCIP_Real*            sumvarptr,          /**< pointer to the value of the current variance sum term */
   int                   nobservations,      /**< total number of observations */
   SCIP_Bool             add                 /**< TRUE if the value should be added, FALSE for removing it */
   )
{
   SCIP_Real oldmean;
   SCIP_Real addfactor;
   assert(meanptr != NULL);
   assert(sumvarptr != NULL);
   assert(nobservations > 0 || add);
 
   addfactor = add ? 1.0 : -1.0;
 
   oldmean = *meanptr;
   *meanptr = oldmean + addfactor * (value - oldmean)/(SCIP_Real)nobservations;
   *sumvarptr += addfactor * (value - oldmean) * (value - (*meanptr));
 
   /* it may happen that *sumvarptr is slightly negative, especially after a series of add/removal operations */
   assert(*sumvarptr >= -1e-4);
   *sumvarptr = MAX(0.0, *sumvarptr);
}
 
/** removes an observation (x,y) from the regression */
void SCIPregressionRemoveObservation(
   SCIP_REGRESSION*      regression,         /**< regression data structure */
   SCIP_Real             x,                  /**< X of observation */
   SCIP_Real             y                   /**< Y of the observation */
   )
{
   assert(regression != NULL);
   assert(regression->nobservations > 0);
 
   /* simply call the reset function in the case of a single remaining observation to avoid numerical troubles */
   if( regression->nobservations == 1 )
   {
      SCIPregressionReset(regression);
   }
   else
   {
      SCIP_Bool add = FALSE;
      --regression->nobservations;
 
      /* decrement individual means and variances */
      incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
      incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
 
      /* decrement product sum */
      regression->sumxy -= (x * y);
   }
 
   /* recompute regression parameters */
   regressionRecompute(regression);
}
 
/** update regression by a new observation (x,y) */
void SCIPregressionAddObservation(
   SCIP_REGRESSION*      regression,         /**< regression data structure */
   SCIP_Real             x,                  /**< X of observation */
   SCIP_Real             y                   /**< Y of the observation */
   )
{
   SCIP_Bool add = TRUE;
   assert(regression != NULL);
 
   ++(regression->nobservations);
   incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
   incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
 
   regression->sumxy += x * y;
 
   regressionRecompute(regression);
}
 
/** reset regression data structure */
void SCIPregressionReset(
   SCIP_REGRESSION*      regression          /**< regression data structure */
   )
{
   regression->intercept = SCIP_INVALID;
   regression->slope = SCIP_INVALID;
   regression->corrcoef = SCIP_INVALID;
   regression->meanx = 0;
   regression->variancesumx = 0;
   regression->sumxy = 0;
   regression->meany = 0;
   regression->variancesumy = 0;
   regression->nobservations = 0;
}
 
/** creates and resets a regression */
SCIP_RETCODE SCIPregressionCreate(
   SCIP_REGRESSION**     regression          /**< regression data structure */
   )
{
   assert(regression != NULL);
 
   /* allocate necessary memory */
   SCIP_ALLOC (BMSallocMemory(regression) );
 
   /* reset the regression */
   SCIPregressionReset(*regression);
 
   return SCIP_OKAY;
}
 
/** creates and resets a regression */
void SCIPregressionFree(
   SCIP_REGRESSION**     regression          /**< regression data structure */
   )
{
   BMSfreeMemory(regression);
}
 
/** calculate memory size for dynamically allocated arrays (copied from scip/set.c) */
static
int calcGrowSize(
   int                   initsize,           /**< initial size of array */
   SCIP_Real             growfac,            /**< growing factor of array */
   int                   num                 /**< minimum number of entries to store */
   )
{
   int size;
 
   assert(initsize >= 0);
   assert(growfac >= 1.0);
   assert(num >= 0);
 
   if( growfac == 1.0 )
      size = MAX(initsize, num);
   else
   {
      int oldsize;
 
      /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
      initsize = MAX(initsize, 4);
      size = initsize;
      oldsize = size - 1;
 
      /* second condition checks against overflow */
      while( size < num && size > oldsize )
      {
         oldsize = size;
         size = (int)(growfac * size + initsize);
      }
 
      /* if an overflow happened, set the correct value */
      if( size <= oldsize )
         size = num;
   }
 
   assert(size >= initsize);
   assert(size >= num);
 
   return size;
}
 
/*
 * GML graphical printing methods
 * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html
 */
 
#define GMLNODEWIDTH 120.0
#define GMLNODEHEIGTH 30.0
#define GMLFONTSIZE 13
#define GMLNODETYPE "rectangle"
#define GMLNODEFILLCOLOR "#ff0000"
#define GMLEDGECOLOR "black"
#define GMLNODEBORDERCOLOR "#000000"
 
 
/** writes a node section to the given graph file */
void SCIPgmlWriteNode(
   FILE*                 file,               /**< file to write to */
   unsigned int          id,                 /**< id of the node */
   const char*           label,              /**< label of the node */
   const char*           nodetype,           /**< type of the node, or NULL */
   const char*           fillcolor,          /**< color of the node's interior, or NULL */
   const char*           bordercolor         /**< color of the node's border, or NULL */
   )
{
   assert(file != NULL);
   assert(label != NULL);
 
   fprintf(file, "  node\n");
   fprintf(file, "  [\n");
   fprintf(file, "    id      %u\n", id);
   fprintf(file, "    label   \"%s\"\n", label);
   fprintf(file, "    graphics\n");
   fprintf(file, "    [\n");
   fprintf(file, "      w       %g\n", GMLNODEWIDTH);
   fprintf(file, "      h       %g\n", GMLNODEHEIGTH);
 
   if( nodetype != NULL )
      fprintf(file, "      type    \"%s\"\n", nodetype);
   else
      fprintf(file, "      type    \"%s\"\n", GMLNODETYPE);
 
   if( fillcolor != NULL )
      fprintf(file, "      fill    \"%s\"\n", fillcolor);
   else
      fprintf(file, "      fill    \"%s\"\n", GMLNODEFILLCOLOR);
 
   if( bordercolor != NULL )
      fprintf(file, "      outline \"%s\"\n", bordercolor);
   else
      fprintf(file, "      outline \"%s\"\n", GMLNODEBORDERCOLOR);
 
   fprintf(file, "    ]\n");
   fprintf(file, "    LabelGraphics\n");
   fprintf(file, "    [\n");
   fprintf(file, "      text      \"%s\"\n", label);
   fprintf(file, "      fontSize  %d\n", GMLFONTSIZE);
   fprintf(file, "      fontName  \"Dialog\"\n");
   fprintf(file, "      anchor    \"c\"\n");
   fprintf(file, "    ]\n");
   fprintf(file, "  ]\n");
}
 
/** writes a node section including weight to the given graph file */
void SCIPgmlWriteNodeWeight(
   FILE*                 file,               /**< file to write to */
   unsigned int          id,                 /**< id of the node */
   const char*           label,              /**< label of the node */
   const char*           nodetype,           /**< type of the node, or NULL */
   const char*           fillcolor,          /**< color of the node's interior, or NULL */
   const char*           bordercolor,        /**< color of the node's border, or NULL */
   SCIP_Real             weight              /**< weight of node */
   )
{
   assert(file != NULL);
   assert(label != NULL);
 
   fprintf(file, "  node\n");
   fprintf(file, "  [\n");
   fprintf(file, "    id      %u\n", id);
   fprintf(file, "    label   \"%s\"\n", label);
   fprintf(file, "    weight  %g\n", weight);
   fprintf(file, "    graphics\n");
   fprintf(file, "    [\n");
   fprintf(file, "      w       %g\n", GMLNODEWIDTH);
   fprintf(file, "      h       %g\n", GMLNODEHEIGTH);
 
   if( nodetype != NULL )
      fprintf(file, "      type    \"%s\"\n", nodetype);
   else
      fprintf(file, "      type    \"%s\"\n", GMLNODETYPE);
 
   if( fillcolor != NULL )
      fprintf(file, "      fill    \"%s\"\n", fillcolor);
   else
      fprintf(file, "      fill    \"%s\"\n", GMLNODEFILLCOLOR);
 
   if( bordercolor != NULL )
      fprintf(file, "      outline \"%s\"\n", bordercolor);
   else
      fprintf(file, "      outline \"%s\"\n", GMLNODEBORDERCOLOR);
 
   fprintf(file, "    ]\n");
   fprintf(file, "    LabelGraphics\n");
   fprintf(file, "    [\n");
   fprintf(file, "      text      \"%s\"\n", label);
   fprintf(file, "      fontSize  %d\n", GMLFONTSIZE);
   fprintf(file, "      fontName  \"Dialog\"\n");
   fprintf(file, "      anchor    \"c\"\n");
   fprintf(file, "    ]\n");
   fprintf(file, "  ]\n");
}
 
/** writes an edge section to the given graph file */
void SCIPgmlWriteEdge(
   FILE*                 file,               /**< file to write to */
   unsigned int          source,             /**< source node id of the node */
   unsigned int          target,             /**< target node id of the edge */
   const char*           label,              /**< label of the edge, or NULL */
   const char*           color               /**< color of the edge, or NULL */
   )
{
   assert(file != NULL);
 
   fprintf(file, "  edge\n");
   fprintf(file, "  [\n");
   fprintf(file, "    source  %u\n", source);
   fprintf(file, "    target  %u\n", target);
 
   if( label != NULL)
      fprintf(file, "    label   \"%s\"\n", label);
 
   fprintf(file, "    graphics\n");
   fprintf(file, "    [\n");
 
   if( color != NULL )
      fprintf(file, "      fill    \"%s\"\n", color);
   else
      fprintf(file, "      fill    \"%s\"\n", GMLEDGECOLOR);
 
   /* fprintf(file, "      arrow     \"both\"\n"); */
   fprintf(file, "    ]\n");
 
   if( label != NULL)
   {
      fprintf(file, "    LabelGraphics\n");
      fprintf(file, "    [\n");
      fprintf(file, "      text      \"%s\"\n", label);
      fprintf(file, "      fontSize  %d\n", GMLFONTSIZE);
      fprintf(file, "      fontName  \"Dialog\"\n");
      fprintf(file, "      anchor    \"c\"\n");
      fprintf(file, "    ]\n");
   }
 
   fprintf(file, "  ]\n");
}
 
/** writes an arc section to the given graph file */
void SCIPgmlWriteArc(
   FILE*                 file,               /**< file to write to */
   unsigned int          source,             /**< source node id of the node */
   unsigned int          target,             /**< target node id of the edge */
   const char*           label,              /**< label of the edge, or NULL */
   const char*           color               /**< color of the edge, or NULL */
   )
{
   assert(file != NULL);
 
   fprintf(file, "  edge\n");
   fprintf(file, "  [\n");
   fprintf(file, "    source  %u\n", source);
   fprintf(file, "    target  %u\n", target);
 
   if( label != NULL)
      fprintf(file, "    label   \"%s\"\n", label);
 
   fprintf(file, "    graphics\n");
   fprintf(file, "    [\n");
 
   if( color != NULL )
      fprintf(file, "      fill    \"%s\"\n", color);
   else
      fprintf(file, "      fill    \"%s\"\n", GMLEDGECOLOR);
 
   fprintf(file, "      targetArrow     \"standard\"\n");
   fprintf(file, "    ]\n");
 
   if( label != NULL)
   {
      fprintf(file, "    LabelGraphics\n");
      fprintf(file, "    [\n");
      fprintf(file, "      text      \"%s\"\n", label);
      fprintf(file, "      fontSize  %d\n", GMLFONTSIZE);
      fprintf(file, "      fontName  \"Dialog\"\n");
      fprintf(file, "      anchor    \"c\"\n");
      fprintf(file, "    ]\n");
   }
 
   fprintf(file, "  ]\n");
}
 
/** writes the starting line to a GML graph file, does not open a file */
void SCIPgmlWriteOpening(
   FILE*                 file,               /**< file to write to */
   SCIP_Bool             directed            /**< is the graph directed */
   )
{
   assert(file != NULL);
 
   fprintf(file, "graph\n");
   fprintf(file, "[\n");
   fprintf(file, "  hierarchic      1\n");
 
   if( directed )
      fprintf(file, "  directed        1\n");
}
 
/** writes the ending lines to a GML graph file, does not close a file */
void SCIPgmlWriteClosing(
   FILE*                 file                /**< file to close */
   )
{
   assert(file != NULL);
 
   fprintf(file, "]\n");
}
 
/**
 * writes the opening line to a dot graph file, does not open a file
 */
void SCIPdotWriteOpening(
   FILE*                 file                /**< file to write to */
   )
{
   assert(file != NULL);
 
   fprintf(file, "digraph G {\n");
}
 
/** adds a node to the dot graph */
void SCIPdotWriteNode(
   FILE*                 file,               /**< file to write to */
   int                   node,               /**< node id */
   const char*           label,              /**< node label */
   const char*           nodetype,           /**< type of the node, or NULL */
   const char*           fillcolor,          /**< color of the node's interior, or NULL */
   const char*           bordercolor         /**< color of the node's border, or NULL */
   )
{
   assert(file != NULL);
 
   fprintf(file, "\t%d [shape=\"%s\", label=\"%s\", style=\"filled\", fillcolor=\"%s\", color=\"%s\"];\n", node, nodetype, label, fillcolor, bordercolor);
}
 
/** adds an arc (edge) between two nodes in the dot graph */
void SCIPdotWriteArc(
   FILE*                 file,               /**< file to write to */
   int                   source,             /**< source node id of the node */
   int                   target,             /**< target node id of the edge */
   const char*           color               /**< color of the edge, or NULL */
   )
{
   assert(file != NULL);
 
   fprintf(file, "\t%d -> %d [color=\"%s\"];\n", source, target, color);
}
 
/** writes the closing line to a dot graph file, does not close a file */
void SCIPdotWriteClosing(
   FILE*                 file                /**< file to write to */
   )
{
   assert(file != NULL);
 
   fprintf(file, "}\n");
}
 
/*
 * Sparse solution
 */
 
/** creates a sparse solution */
SCIP_RETCODE SCIPsparseSolCreate(
   SCIP_SPARSESOL**      sparsesol,          /**< pointer to store the created sparse solution */
   SCIP_VAR**            vars,               /**< variables in the sparse solution, must not contain continuous
                                              *   variables
                                              */
   int                   nvars,              /**< number of variables to store, size of the lower and upper bound
                                              *   arrays
                                              */
   SCIP_Bool             cleared             /**< should the lower and upper bound arrays be cleared (entries set to
                                              *   0)
                                              */
   )
{
   assert(sparsesol != NULL);
   assert(vars != NULL);
   assert(nvars >= 0);
 
   SCIP_ALLOC( BMSallocMemory(sparsesol) );
 
#ifndef NDEBUG
   {
      int v;
 
      for( v = nvars - 1; v >= 0; --v )
      {
         assert(vars[v] != NULL);
         /* assert(SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS); */
      }
   }
#endif
 
   /* copy variables */
   SCIP_ALLOC( BMSduplicateMemoryArray(&((*sparsesol)->vars), vars, nvars) );
 
   /* create bound arrays */
   if( cleared )
   {
      SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->lbvalues), nvars) );
      SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->ubvalues), nvars) );
   }
   else
   {
      SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->lbvalues), nvars) );
      SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->ubvalues), nvars) );
   }
 
   (*sparsesol)->nvars = nvars;
 
   return SCIP_OKAY;
}
 
/** frees sparse solution */
void SCIPsparseSolFree(
   SCIP_SPARSESOL**      sparsesol           /**< pointer to a sparse solution */
   )
{
   assert(sparsesol != NULL);
   assert(*sparsesol != NULL);
 
   BMSfreeMemoryArray(&((*sparsesol)->vars));
   BMSfreeMemoryArray(&((*sparsesol)->ubvalues));
   BMSfreeMemoryArray(&((*sparsesol)->lbvalues));
   BMSfreeMemory(sparsesol);
}
 
/** returns the variables stored in the given sparse solution */
SCIP_VAR** SCIPsparseSolGetVars(
   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
   )
{
   assert(sparsesol != NULL);
 
   return sparsesol->vars;
}
 
/** returns the number of variables stored in the given sparse solution */
int SCIPsparseSolGetNVars(
   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
   )
{
   assert(sparsesol != NULL);
 
   return sparsesol->nvars;
}
 
/** returns the lower bound array for all variables for a given sparse solution */
SCIP_Longint* SCIPsparseSolGetLbs(
   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
   )
{
   assert(sparsesol != NULL);
 
   return sparsesol->lbvalues;
}
 
/** returns the upper bound array for all variables for a given sparse solution */
SCIP_Longint* SCIPsparseSolGetUbs(
   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
   )
{
   assert(sparsesol != NULL);
 
   return sparsesol->ubvalues;
}
 
/** constructs the first solution of sparse solution (all variables are set to their lower bound value */
void SCIPsparseSolGetFirstSol(
   SCIP_SPARSESOL*       sparsesol,          /**< sparse solutions */
   SCIP_Longint*         sol,                /**< array to store the first solution */
   int                   nvars               /**< number of variables */
   )
{
   SCIP_Longint* lbvalues;
   int v;
 
   assert(sparsesol != NULL);
   assert(sol != NULL);
   assert(nvars == SCIPsparseSolGetNVars(sparsesol));
 
   lbvalues = SCIPsparseSolGetLbs(sparsesol);
   assert(lbvalues != NULL);
 
   /* copy the lower bounds */
   for( v = 0; v < nvars; ++v )
      sol[v] = lbvalues[v];
}
 
 
/** constructs the next solution of the sparse solution and return whether there was one more or not */
SCIP_Bool SCIPsparseSolGetNextSol(
   SCIP_SPARSESOL*       sparsesol,          /**< sparse solutions */
   SCIP_Longint*         sol,                /**< current solution array which get changed to the next solution */
   int                   nvars               /**< number of variables */
   )
{
   SCIP_Longint* lbvalues;
   SCIP_Longint* ubvalues;
   SCIP_Longint lbvalue;
   SCIP_Longint ubvalue;
   SCIP_Bool singular;
   SCIP_Bool carryflag;
   int v;
 
   assert(sparsesol != NULL);
   assert(sol != NULL);
 
   if( nvars == 0 )
      return FALSE;
 
   assert(nvars > 0);
   assert(nvars == SCIPsparseSolGetNVars(sparsesol));
 
   lbvalues = SCIPsparseSolGetLbs(sparsesol);
   ubvalues = SCIPsparseSolGetUbs(sparsesol);
   assert(lbvalues != NULL);
   assert(ubvalues != NULL);
 
   singular = TRUE;
   carryflag = FALSE;
 
   for( v = 0; v < nvars; ++v )
   {
      lbvalue = lbvalues[v];
      ubvalue = ubvalues[v];
 
      if( lbvalue < ubvalue )
      {
         singular = FALSE;
 
         if( carryflag == FALSE )
         {
            if( sol[v] < ubvalue )
            {
               sol[v]++;
               break;
            }
            else
            {
               /* in the last solution the variables v was set to its upper bound value */
               assert(sol[v] == ubvalue);
               sol[v] = lbvalue;
               carryflag = TRUE;
            }
         }
         else
         {
            if( sol[v] < ubvalue )
            {
               sol[v]++;
               carryflag = FALSE;
               break;
            }
            else
            {
               assert(sol[v] == ubvalue);
               sol[v] = lbvalue;
            }
         }
      }
   }
 
   return (!carryflag && !singular);
}
 
 
/*
 * Queue
 */
 
/** resizes element memory to hold at least the given number of elements */
static
SCIP_RETCODE queueResize(
   SCIP_QUEUE*           queue,              /**< pointer to a queue */
   int                   minsize             /**< minimal number of storable elements */
   )
{
   assert(queue != NULL);
   assert(minsize > 0);
 
   if( minsize <= queue->size )
      return SCIP_OKAY;
 
   queue->size = MAX(minsize, (int)(queue->size * queue->sizefac));
   SCIP_ALLOC( BMSreallocMemoryArray(&queue->slots, queue->size) );
 
   return SCIP_OKAY;
}
 
 
/** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */
SCIP_RETCODE SCIPqueueCreate(
   SCIP_QUEUE**          queue,              /**< pointer to the new queue */
   int                   initsize,           /**< initial number of available element slots */
   SCIP_Real             sizefac             /**< memory growing factor applied, if more element slots are needed */
   )
{
   assert(queue != NULL);
 
   initsize = MAX(1, initsize);
   sizefac = MAX(1.0, sizefac);
 
   SCIP_ALLOC( BMSallocMemory(queue) );
   (*queue)->firstfree = 0;
   (*queue)->firstused = -1;
   (*queue)->size = 0;
   (*queue)->sizefac = sizefac;
   (*queue)->slots = NULL;
 
   SCIP_CALL( queueResize(*queue, initsize) );
 
   return SCIP_OKAY;
}
 
/** frees queue, but not the data elements themselves */
void SCIPqueueFree(
   SCIP_QUEUE**          queue               /**< pointer to a queue */
   )
{
   assert(queue != NULL);
 
   BMSfreeMemoryArray(&(*queue)->slots);
   BMSfreeMemory(queue);
}
 
/** clears the queue, but doesn't free the data elements themselves */
void SCIPqueueClear(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   assert(queue != NULL);
 
   queue->firstfree = 0;
   queue->firstused = -1;
}
 
/** reallocates slots if queue is necessary */
static
SCIP_RETCODE queueCheckSize(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   if( queue->firstfree == queue->firstused )
   {
      int sizediff;
      int oldsize = queue->size;
 
      SCIP_CALL( queueResize(queue, queue->size+1) );
      assert(oldsize < queue->size);
 
      sizediff = queue->size - oldsize;
 
      /* move the used memory at the slots to the end */
      BMSmoveMemoryArray(&(queue->slots[queue->firstused + sizediff]), &(queue->slots[queue->firstused]), oldsize - queue->firstused); /*lint !e866*/
      queue->firstused += sizediff;
   }
   assert(queue->firstfree != queue->firstused);
 
   return SCIP_OKAY;
}
 
/** checks and adjusts marker of first free and first used slot */
static
void queueCheckMarker(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   /* if we saved the value at the last position we need to reset the firstfree position */
   if( queue->firstfree == queue->size )
      queue->firstfree = 0;
 
   /* if a first element was added, we need to update the firstused counter */
   if( queue->firstused == -1 )
      queue->firstused = 0;
}
 
/** inserts pointer element at the end of the queue */
SCIP_RETCODE SCIPqueueInsert(
   SCIP_QUEUE*           queue,              /**< queue */
   void*                 elem                /**< element to be inserted */
   )
{
   assert(queue != NULL);
   assert(queue->slots != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
   assert(elem != NULL);
 
   /* check allocated memory */
   SCIP_CALL( queueCheckSize(queue) );
 
   /* insert element at the first free slot */
   queue->slots[queue->firstfree].ptr = elem;
   ++(queue->firstfree);
 
   /* check and adjust marker */
   queueCheckMarker(queue);
 
   return SCIP_OKAY;
}
 
/** inserts unsigned integer element at the end of the queue */
SCIP_RETCODE SCIPqueueInsertUInt(
   SCIP_QUEUE*           queue,              /**< queue */
   unsigned int          elem                /**< element to be inserted */
   )
{
   assert(queue != NULL);
   assert(queue->slots != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   /* check allocated memory */
   SCIP_CALL( queueCheckSize(queue) );
 
   /* insert element at the first free slot */
   queue->slots[queue->firstfree].uinteger = elem;
   ++(queue->firstfree);
 
   /* check and adjust marker */
   queueCheckMarker(queue);
 
   return SCIP_OKAY;
}
 
/** removes and returns the first pointer element of the queue, or NULL if no element exists */
void* SCIPqueueRemove(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   int pos;
 
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   if( queue->firstused == -1 )
      return NULL;
 
   assert(queue->slots != NULL);
 
   pos = queue->firstused;
   ++(queue->firstused);
 
   /* if we removed the value at the last position we need to reset the firstused position */
   if( queue->firstused == queue->size )
      queue->firstused = 0;
 
   /* if we reached the first free position we can reset both, firstused and firstused, positions */
   if( queue->firstused == queue->firstfree )
   {
      queue->firstused = -1;
      queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
   }
 
   return (queue->slots[pos].ptr);
}
 
/** removes and returns the first unsigned integer element of the queue, or UINT_MAX if no element exists */
unsigned int SCIPqueueRemoveUInt(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   int pos;
 
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   if( queue->firstused == -1 )
      return UINT_MAX;
 
   assert(queue->slots != NULL);
 
   pos = queue->firstused;
   ++(queue->firstused);
 
   /* if we removed the value at the last position we need to reset the firstused position */
   if( queue->firstused == queue->size )
      queue->firstused = 0;
 
   /* if we reached the first free position we can reset both, firstused and firstused, positions */
   if( queue->firstused == queue->firstfree )
   {
      queue->firstused = -1;
      queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
   }
 
   return (queue->slots[pos].uinteger);
}
 
/** returns the first element of the queue without removing it, or NULL if no element exists */
void* SCIPqueueFirst(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   if( queue->firstused == -1 )
      return NULL;
 
   assert(queue->slots != NULL);
 
   return queue->slots[queue->firstused].ptr;
}
 
/** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */
unsigned int SCIPqueueFirstUInt(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   if( queue->firstused == -1 )
      return UINT_MAX;
 
   assert(queue->slots != NULL);
 
   return queue->slots[queue->firstused].uinteger;
}
 
/** returns whether the queue is empty */
SCIP_Bool SCIPqueueIsEmpty(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   return (queue->firstused == -1);
}
 
/** returns the number of elements in the queue */
int SCIPqueueNElems(
   SCIP_QUEUE*           queue               /**< queue */
   )
{
   assert(queue != NULL);
   assert(queue->firstused >= -1 && queue->firstused < queue->size);
   assert(queue->firstfree >= 0 && queue->firstused < queue->size);
   assert(queue->firstused > -1 || queue->firstfree == 0);
 
   if( queue->firstused == -1 )
      return 0;
   else if( queue->firstused < queue->firstfree )
      return queue->firstfree - queue->firstused;
   else if( queue->firstused == queue->firstfree )
      return queue->size;
   else
      return queue->firstfree + (queue->size - queue->firstused);
}
 
 
/*
 * Priority Queue
 */
 
#define PQ_PARENT(q) (((q)+1)/2-1)
#define PQ_LEFTCHILD(p) (2*(p)+1)
#define PQ_RIGHTCHILD(p) (2*(p)+2)
 
 
/** resizes element memory to hold at least the given number of elements */
static
SCIP_RETCODE pqueueResize(
   SCIP_PQUEUE*          pqueue,             /**< pointer to a priority queue */
   int                   minsize             /**< minimal number of storable elements */
   )
{
   assert(pqueue != NULL);
 
   if( minsize <= pqueue->size )
      return SCIP_OKAY;
 
   pqueue->size = MAX(minsize, (int)(pqueue->size * pqueue->sizefac));
   SCIP_ALLOC( BMSreallocMemoryArray(&pqueue->slots, pqueue->size) );
 
   return SCIP_OKAY;
}
 
/** creates priority queue */
SCIP_RETCODE SCIPpqueueCreate(
   SCIP_PQUEUE**         pqueue,             /**< pointer to a priority queue */
   int                   initsize,           /**< initial number of available element slots */
   SCIP_Real             sizefac,            /**< memory growing factor applied, if more element slots are needed */
   SCIP_DECL_SORTPTRCOMP((*ptrcomp)),        /**< data element comparator */
   SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) /**< callback to act on position change of elem in priority queue, or NULL */
   )
{
   assert(pqueue != NULL);
   assert(ptrcomp != NULL);
 
   initsize = MAX(1, initsize);
   sizefac = MAX(1.0, sizefac);
 
   SCIP_ALLOC( BMSallocMemory(pqueue) );
   (*pqueue)->len = 0;
   (*pqueue)->size = 0;
   (*pqueue)->sizefac = sizefac;
   (*pqueue)->slots = NULL;
   (*pqueue)->ptrcomp = ptrcomp;
   (*pqueue)->elemchgpos = elemchgpos;
   SCIP_CALL( pqueueResize(*pqueue, initsize) );
 
   return SCIP_OKAY;
}
 
/** frees priority queue, but not the data elements themselves */
void SCIPpqueueFree(
   SCIP_PQUEUE**         pqueue              /**< pointer to a priority queue */
   )
{
   assert(pqueue != NULL);
 
   BMSfreeMemoryArray(&(*pqueue)->slots);
   BMSfreeMemory(pqueue);
}
 
/** clears the priority queue, but doesn't free the data elements themselves */
void SCIPpqueueClear(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   assert(pqueue != NULL);
 
   pqueue->len = 0;
}
 
/** assign element to new slot in priority queue */
static
void pqueueElemChgPos(
   SCIP_PQUEUE*          pqueue,             /**< priority queue */
   void*                 elem,               /**< element whose position changes */
   int                   oldpos,             /**< old position or -1 if elem is newly inserted */
   int                   newpos              /**< new position */
   )
{
   pqueue->slots[newpos] = elem;
 
   /* act on position change */
   if( pqueue->elemchgpos != NULL )
   {
      pqueue->elemchgpos(elem, oldpos, newpos);
   }
}
 
#ifdef SCIP_MORE_DEBUG
/** ensure that the priority queue still has the heap property */
static
SCIP_Bool pqueueHasHeapProperty(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   int i;
 
   if( SCIPpqueueNElems(pqueue) == 0 )
      return TRUE;
 
   /* check local heap property between parents and children */
   for( i = 0; i < SCIPpqueueNElems(pqueue); ++i )
   {
      if( i > 0 && pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[PQ_PARENT(i)]) < 0 )
         return FALSE;
      if( i < PQ_PARENT(SCIPpqueueNElems(pqueue)) )
      {
         int leftchild = PQ_LEFTCHILD(i);
         int rightchild = PQ_RIGHTCHILD(i);
         assert(leftchild < SCIPpqueueNElems(pqueue));
         assert(rightchild <= SCIPpqueueNElems(pqueue));
         if( pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[leftchild]) > 0 )
            return FALSE;
         if( rightchild < SCIPpqueueNElems(pqueue) && pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[rightchild]) > 0)
            return FALSE;
      }
   }
   return TRUE;
}
#endif
 
/** inserts element into priority queue */
SCIP_RETCODE SCIPpqueueInsert(
   SCIP_PQUEUE*          pqueue,             /**< priority queue */
   void*                 elem                /**< element to be inserted */
   )
{
   int pos;
   int parentpos;
 
   assert(pqueue != NULL);
   assert(pqueue->len >= 0);
   assert(elem != NULL);
 
   SCIP_CALL( pqueueResize(pqueue, pqueue->len+1) );
 
   /* insert element as leaf in the tree, move it towards the root as long it is better than its parent */
   pos = pqueue->len;
   pqueue->len++;
   parentpos = PQ_PARENT(pos);
   while( pos > 0 && (*pqueue->ptrcomp)(elem, pqueue->slots[parentpos]) < 0 )
   {
      assert((*pqueue->ptrcomp)(pqueue->slots[parentpos], elem) >= 0);
      pqueueElemChgPos(pqueue, pqueue->slots[parentpos], parentpos, pos);
 
      pos = parentpos;
      parentpos = PQ_PARENT(pos);
   }
 
   /* insert element at the found position */
   pqueueElemChgPos(pqueue, elem, -1, pos);
 
#ifdef SCIP_MORE_DEBUG
   assert(pqueueHasHeapProperty(pqueue));
#endif
 
   return SCIP_OKAY;
}
 
 
/** delete element at specified position, maintaining the heap property */
void SCIPpqueueDelPos(
   SCIP_PQUEUE*          pqueue,             /**< priority queue */
   int                   pos                 /**< position of element that should be deleted */
   )
{
   void* last;
 
   assert(pqueue != NULL);
   assert(pos >= 0);
   assert(pos < SCIPpqueueNElems(pqueue));
 
   /* remove element at specified position of the tree, move the better child to its parents position until the last element
    * of the queue could be placed in the empty slot
    */
   pqueue->len--;
 
   /* everything in place */
   if( pos == pqueue->len )
      return;
 
   last = pqueue->slots[pqueue->len];
 
   /* last element is brought to pos. it may now violate the heap property compared to its parent, or to its children.
    * In the first case, move it up, otherwise, move it down.
    */
   while( pos > 0 && (*pqueue->ptrcomp)(last, pqueue->slots[PQ_PARENT(pos)]) < 0 )
   {
      pqueueElemChgPos(pqueue, pqueue->slots[PQ_PARENT(pos)], PQ_PARENT(pos), pos);
      pos = PQ_PARENT(pos);
   }
 
   while( pos <= PQ_PARENT(pqueue->len-1) )
   {
      int childpos = PQ_LEFTCHILD(pos);
      int brotherpos = PQ_RIGHTCHILD(pos);
 
      /* determine better of the two children */
      if( brotherpos < pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
         childpos = brotherpos;
 
      if( (*pqueue->ptrcomp)(last, pqueue->slots[childpos]) <= 0 )
         break;
 
      /* move better element from childpos to pos */
      pqueueElemChgPos(pqueue, pqueue->slots[childpos], childpos, pos);
 
      pos = childpos;
   }
 
   /* pos must point into a valid position */
   assert(pos <= pqueue->len - 1);
 
   pqueueElemChgPos(pqueue, last, pqueue->len, pos);
 
#ifdef SCIP_MORE_DEBUG
   assert(pqueueHasHeapProperty(pqueue));
#endif
}
 
/** removes and returns best element from the priority queue */
void* SCIPpqueueRemove(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   void* root;
 
   assert(pqueue != NULL);
   assert(pqueue->len >= 0);
 
   if( pqueue->len == 0 )
      return NULL;
 
   root = pqueue->slots[0];
 
   SCIPpqueueDelPos(pqueue, 0);
 
   return root;
}
 
/** returns the best element of the queue without removing it */
void* SCIPpqueueFirst(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   assert(pqueue != NULL);
   assert(pqueue->len >= 0);
 
   if( pqueue->len == 0 )
      return NULL;
 
   return pqueue->slots[0];
}
 
/** returns the number of elements in the queue */
int SCIPpqueueNElems(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   assert(pqueue != NULL);
   assert(pqueue->len >= 0);
 
   return pqueue->len;
}
 
/** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */
void** SCIPpqueueElems(
   SCIP_PQUEUE*          pqueue              /**< priority queue */
   )
{
   assert(pqueue != NULL);
   assert(pqueue->len >= 0);
 
   return pqueue->slots;
}
 
/** return the position of @p elem in the priority queue, or -1 if element is not found */
int SCIPpqueueFind(
   SCIP_PQUEUE*          pqueue,             /**< priority queue */
   void*                 elem                /**< element to be inserted */
   )
{
   int pos = -1;
 
   while( ++pos < SCIPpqueueNElems(pqueue) )
   {
      if( pqueue->slots[pos] == elem )
         return pos;
   }
 
   return -1;
}
 
 
 
 
/*
 * Hash Table
 */
 
/** table of some prime numbers */
static int primetable[] = {
   2,
   7,
   19,
   31,
   59,
   227,
   617,
   1523,
   3547,
   8011,
   17707,
   38723,
   83833,
   180317,
   385897,
   821411,
   1742369,
   3680893,
   5693959,
   7753849,
   9849703,
   11973277,
   14121853,
   17643961,
   24273817,
   32452843,
   49979687,
   67867967,
   86028121,
   104395301,
   122949823,
   141650939,
   160481183,
   179424673,
   198491317,
   217645177,
   256203161,
   314606869,
   373587883,
   433024223,
   492876847,
   553105243,
   613651349,
   694847533,
   756065159,
   817504243,
   879190747,
   941083981,
   982451653,
   INT_MAX
};
static const int primetablesize = sizeof(primetable)/sizeof(int);
 
/** simple and fast 2-universal hash function using multiply and shift */
static
uint32_t hashvalue(
   uint64_t              input               /**< key value */
   )
{
   return ( (uint32_t) ((UINT64_C(0x9e3779b97f4a7c15) * input)>>32) ) | 1u;
}
 
/** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
int SCIPcalcMultihashSize(
   int                   minsize             /**< minimal size of the hash table */
   )
{
   int pos;
 
   (void) SCIPsortedvecFindInt(primetable, minsize, primetablesize, &pos);
   assert(0 <= pos && pos < primetablesize);
 
   return primetable[pos];
}
 
/** appends element to the multihash list */
static
SCIP_RETCODE multihashlistAppend(
   SCIP_MULTIHASHLIST**  multihashlist,      /**< pointer to hash list */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   void*                 element             /**< element to append to the list */
   )
{
   SCIP_MULTIHASHLIST* newlist;
 
   assert(multihashlist != NULL);
   assert(blkmem != NULL);
   assert(element != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, &newlist) );
   newlist->element = element;
   newlist->next = *multihashlist;
   *multihashlist = newlist;
 
   return SCIP_OKAY;
}
 
/** frees a multihash list entry and all its successors */
static
void multihashlistFree(
   SCIP_MULTIHASHLIST**  multihashlist,      /**< pointer to multihash list to free */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   SCIP_MULTIHASHLIST* list;
   SCIP_MULTIHASHLIST* nextlist;
 
   assert(multihashlist != NULL);
   assert(blkmem != NULL);
 
   list = *multihashlist;
   while( list != NULL )
   {
      nextlist = list->next;
      BMSfreeBlockMemory(blkmem, &list);
      list = nextlist;
   }
 
   *multihashlist = NULL;
}
 
/** finds multihash list entry pointing to element with given key in the multihash list, returns NULL if not found */
static
SCIP_MULTIHASHLIST* multihashlistFind(
   SCIP_MULTIHASHLIST*   multihashlist,      /**< multihash list */
   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
   void*                 userptr,            /**< user pointer */
   uint64_t              keyval,             /**< hash value of key */
   void*                 key                 /**< key to retrieve */
   )
{
   uint64_t currentkeyval;
   void* currentkey;
 
   assert(hashkeyeq != NULL);
   assert(key != NULL);
 
   while( multihashlist != NULL )
   {
      currentkey = hashgetkey(userptr, multihashlist->element);
      currentkeyval = hashkeyval(userptr, currentkey);
      if( currentkeyval == keyval && hashkeyeq(userptr, currentkey, key) )
         return multihashlist;
 
      multihashlist = multihashlist->next;
   }
 
   return NULL;
}
 
/** retrieves element with given key from the multihash list, or NULL */
static
void* multihashlistRetrieve(
   SCIP_MULTIHASHLIST*   multihashlist,      /**< hash list */
   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
   void*                 userptr,            /**< user pointer */
   uint64_t              keyval,             /**< hash value of key */
   void*                 key                 /**< key to retrieve */
   )
{
   SCIP_MULTIHASHLIST* h;
 
   /* find hash list entry */
   h = multihashlistFind(multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
 
   /* return element */
   if( h != NULL )
   {
#ifndef NDEBUG
      SCIP_MULTIHASHLIST* h2;
 
      h2 = multihashlistFind(h->next, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
 
      if( h2 != NULL )
      {
         void* key1;
         void* key2;
 
         key1 = hashgetkey(userptr, h->element);
         key2 = hashgetkey(userptr, h2->element);
         assert(hashkeyval(userptr, key1) == hashkeyval(userptr, key2));
 
         if( hashkeyeq(userptr, key1, key2) )
         {
            SCIPerrorMessage("WARNING: hashkey with same value exists multiple times (e.g. duplicate constraint/variable names), so the return value is maybe not correct\n");
         }
      }
#endif
 
      return h->element;
   }
   else
      return NULL;
}
 
 
/** retrieves element with given key from the multihash list, or NULL
 *  returns pointer to multihash table list entry
 */
static
void* multihashlistRetrieveNext(
   SCIP_MULTIHASHLIST**  multihashlist,      /**< on input: hash list to search; on exit: hash list entry corresponding
                                              *   to element after retrieved one, or NULL */
   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
   void*                 userptr,            /**< user pointer */
   uint64_t              keyval,             /**< hash value of key */
   void*                 key                 /**< key to retrieve */
   )
{
   SCIP_MULTIHASHLIST* h;
 
   assert(multihashlist != NULL);
 
   /* find hash list entry */
   h = multihashlistFind(*multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
 
   /* return element */
   if( h != NULL )
   {
      *multihashlist = h->next;
 
      return h->element;
   }
 
   *multihashlist = NULL;
 
   return NULL;
}
 
/** removes element from the multihash list */
static
SCIP_Bool multihashlistRemove(
   SCIP_MULTIHASHLIST**  multihashlist,      /**< pointer to hash list */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   void*                 element             /**< element to remove from the list */
   )
{
   SCIP_MULTIHASHLIST* nextlist;
 
   assert(multihashlist != NULL);
   assert(blkmem != NULL);
   assert(element != NULL);
 
   while( *multihashlist != NULL && (*multihashlist)->element != element )
      multihashlist = &(*multihashlist)->next;
 
   if( *multihashlist != NULL )
   {
      nextlist = (*multihashlist)->next;
      BMSfreeBlockMemory(blkmem, multihashlist);
      *multihashlist = nextlist;
 
      return TRUE;
   }
 
   return FALSE;
}
 
#define SCIP_MULTIHASH_MAXSIZE 33554431 /* 2^25 - 1*/
#define SCIP_MULTIHASH_RESIZE_PERCENTAGE 65
#define SCIP_MULTIHASH_GROW_FACTOR 1.31
 
/** resizing(increasing) the given multihash */
static
SCIP_RETCODE multihashResize(
   SCIP_MULTIHASH*       multihash           /**< hash table */
   )
{
   SCIP_MULTIHASHLIST** newlists;
   SCIP_MULTIHASHLIST* multihashlist;
   SCIP_Longint nelements;
   int nnewlists;
   int l;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
 
   /* get new memeory for hash table lists */
   nnewlists = (int) MIN((unsigned int)(multihash->nlists * SCIP_MULTIHASH_GROW_FACTOR), SCIP_MULTIHASH_MAXSIZE);
   nnewlists = MAX(nnewlists, multihash->nlists);
 
   SCIPdebugMessage("load = %g, nelements = %" SCIP_LONGINT_FORMAT ", nlists = %d, nnewlist = %d\n", SCIPmultihashGetLoad(multihash), multihash->nelements, multihash->nlists, nnewlists);
 
   if( nnewlists > multihash->nlists )
   {
      SCIP_Bool onlyone;
      void* key;
      uint64_t keyval;
      unsigned int hashval;
 
      SCIP_ALLOC( BMSallocClearBlockMemoryArray(multihash->blkmem, &newlists, nnewlists) );
 
      /* move all lists */
      for( l = multihash->nlists - 1; l >= 0; --l )
      {
         multihashlist = multihash->lists[l];
         onlyone = TRUE;
 
         /* move all elements frmm the old lists into the new lists */
         while( multihashlist != NULL )
         {
            /* get the hash key and its hash value */
            key = multihash->hashgetkey(multihash->userptr, multihashlist->element);
            keyval = multihash->hashkeyval(multihash->userptr, key);
            hashval = (unsigned int) (keyval % (unsigned) nnewlists); /*lint !e573*/
 
            /* if the old hash table list consists of only one entry, we still can use this old memory block instead
             * of creating a new one
             */
            if( multihashlist->next == NULL && onlyone )
            {
               /* the new list is also empty, we can directly copy the entry */
               if( newlists[hashval] == NULL )
                  newlists[hashval] = multihashlist;
               /* the new list is not empty, so we need to find the first empty spot */
               else
               {
                  SCIP_MULTIHASHLIST* lastnext = newlists[hashval];
                  SCIP_MULTIHASHLIST* next = lastnext->next;
 
                  while( next != NULL )
                  {
                     lastnext = next;
                     next = next->next;
                  }
 
                  lastnext->next = multihashlist;
               }
 
               multihash->lists[l] = NULL;
            }
            else
            {
               /* append old element to the list at the hash position */
               SCIP_CALL( multihashlistAppend(&(newlists[hashval]), multihash->blkmem, multihashlist->element) );
            }
 
            onlyone = FALSE;
            multihashlist = multihashlist->next;
         }
      }
 
      /* remember number of elements */
      nelements = multihash->nelements;
      /* clear old lists */
      SCIPmultihashRemoveAll(multihash);
      /* free old lists */
      BMSfreeBlockMemoryArray(multihash->blkmem, &(multihash->lists), multihash->nlists);
 
      /* set new data */
      multihash->lists = newlists;
      multihash->nlists = nnewlists;
      multihash->nelements = nelements;
 
#ifdef SCIP_MORE_DEBUG
      {
         SCIP_Longint sumslotsize = 0;
 
         for( l = 0; l < multihash->nlists; ++l )
         {
            multihashlist = multihash->lists[l];
            while( multihashlist != NULL )
            {
               sumslotsize++;
               multihashlist = multihashlist->next;
            }
         }
         assert(sumslotsize == multihash->nelements);
      }
#endif
   }
 
   return SCIP_OKAY;
}
 
/** creates a multihash table */
SCIP_RETCODE SCIPmultihashCreate(
   SCIP_MULTIHASH**      multihash,          /**< pointer to store the created multihash table */
   BMS_BLKMEM*           blkmem,             /**< block memory used to store multihash table entries */
   int                   tablesize,          /**< size of the hash table */
   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
   void*                 userptr             /**< user pointer */
   )
{
   /* only assert non negative to catch overflow errors
    * but not zeros due to integer divison
    */
   assert(tablesize >= 0);
   assert(multihash != NULL);
   assert(hashgetkey != NULL);
   assert(hashkeyeq != NULL);
   assert(hashkeyval != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, multihash) );
   SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*multihash)->lists, tablesize) );
   (*multihash)->blkmem = blkmem;
   (*multihash)->nlists = tablesize;
   (*multihash)->hashgetkey = hashgetkey;
   (*multihash)->hashkeyeq = hashkeyeq;
   (*multihash)->hashkeyval = hashkeyval;
   (*multihash)->userptr = userptr;
   (*multihash)->nelements = 0;
 
   return SCIP_OKAY;
}
 
/** frees the multihash table */
void SCIPmultihashFree(
   SCIP_MULTIHASH**      multihash           /**< pointer to the multihash table */
   )
{
   int i;
   SCIP_MULTIHASH* table;
   BMS_BLKMEM* blkmem;
   SCIP_MULTIHASHLIST** lists;
 
   assert(multihash != NULL);
   assert(*multihash != NULL);
 
   table = (*multihash);
   blkmem = table->blkmem;
   lists = table->lists;
 
   /* free hash lists */
   for( i = table->nlists - 1; i >= 0; --i )
      multihashlistFree(&lists[i], blkmem);
 
   /* free main hash table data structure */
   BMSfreeBlockMemoryArray(blkmem, &table->lists, table->nlists);
   BMSfreeBlockMemory(blkmem, multihash);
}
 
 
/** inserts element in multihash table (multiple inserts of same element possible)
 *
 *  @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
 *        to the hash table, due to dynamic resizing.
 */
SCIP_RETCODE SCIPmultihashInsert(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   void*                 element             /**< element to insert into the table */
   )
{
   void* key;
   uint64_t keyval;
   unsigned int hashval;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
   assert(element != NULL);
 
   /* dynamically resizing the hashtables */
   if( SCIPmultihashGetLoad(multihash) > SCIP_MULTIHASH_RESIZE_PERCENTAGE )
   {
      SCIP_CALL( multihashResize(multihash) );
   }
 
   /* get the hash key and its hash value */
   key = multihash->hashgetkey(multihash->userptr, element);
   keyval = multihash->hashkeyval(multihash->userptr, key);
   hashval = (unsigned int) (keyval % (unsigned) multihash->nlists); /*lint !e573*/
 
   /* append element to the list at the hash position */
   SCIP_CALL( multihashlistAppend(&multihash->lists[hashval], multihash->blkmem, element) );
 
   ++(multihash->nelements);
 
   return SCIP_OKAY;
}
 
/** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
 *
 *  @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
 *        element to the multihash table, due to dynamic resizing.
 */
SCIP_RETCODE SCIPmultihashSafeInsert(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   void*                 element             /**< element to insert into the table */
   )
{
   assert(multihash != NULL);
   assert(multihash->hashgetkey != NULL);
 
   /* check, if key is already existing */
   if( SCIPmultihashRetrieve(multihash, multihash->hashgetkey(multihash->userptr, element)) != NULL )
      return SCIP_KEYALREADYEXISTING;
 
   /* insert element in hash table */
   SCIP_CALL( SCIPmultihashInsert(multihash, element) );
 
   return SCIP_OKAY;
}
 
/** retrieve element with key from multihash table, returns NULL if not existing */
void* SCIPmultihashRetrieve(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   void*                 key                 /**< key to retrieve */
   )
{
   uint64_t keyval;
   unsigned int hashval;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
   assert(key != NULL);
 
   /* get the hash value of the key */
   keyval = multihash->hashkeyval(multihash->userptr, key);
   hashval = (unsigned int) (keyval % (unsigned) multihash->nlists); /*lint !e573*/
 
   return multihashlistRetrieve(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
      multihash->hashkeyval, multihash->userptr, keyval, key);
}
 
/** retrieve element with key from multihash table, returns NULL if not existing
 *  can be used to retrieve all entries with the same key (one-by-one)
 *
 *  @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
 */
void* SCIPmultihashRetrieveNext(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   SCIP_MULTIHASHLIST**  multihashlist,      /**< input: entry in hash table list from which to start searching, or NULL
                                              *   output: entry in hash table list corresponding to element after
                                              *           retrieved one, or NULL */
   void*                 key                 /**< key to retrieve */
   )
{
   uint64_t keyval;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
   assert(multihashlist != NULL);
   assert(key != NULL);
 
   keyval = multihash->hashkeyval(multihash->userptr, key);
 
   if( *multihashlist == NULL )
   {
      unsigned int hashval;
 
      /* get the hash value of the key */
      hashval = (unsigned int) (keyval % (unsigned) multihash->nlists); /*lint !e573*/
 
      *multihashlist = multihash->lists[hashval];
   }
 
   return multihashlistRetrieveNext(multihashlist, multihash->hashgetkey, multihash->hashkeyeq,
      multihash->hashkeyval, multihash->userptr, keyval, key);
}
 
/** returns whether the given element exists in the multihash table */
SCIP_Bool SCIPmultihashExists(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   void*                 element             /**< element to search in the table */
   )
{
   void* key;
   uint64_t keyval;
   unsigned int hashval;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
   assert(element != NULL);
 
   /* get the hash key and its hash value */
   key = multihash->hashgetkey(multihash->userptr, element);
   keyval = multihash->hashkeyval(multihash->userptr, key);
   hashval = (unsigned int) (keyval % (unsigned) multihash->nlists); /*lint !e573*/
 
   return (multihashlistFind(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
         multihash->hashkeyval, multihash->userptr, keyval, key) != NULL);
}
 
/** removes element from the multihash table, if it exists */
SCIP_RETCODE SCIPmultihashRemove(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   void*                 element             /**< element to remove from the table */
   )
{
   void* key;
   uint64_t keyval;
   unsigned int hashval;
 
   assert(multihash != NULL);
   assert(multihash->lists != NULL);
   assert(multihash->nlists > 0);
   assert(multihash->hashgetkey != NULL);
   assert(multihash->hashkeyeq != NULL);
   assert(multihash->hashkeyval != NULL);
   assert(element != NULL);
 
   /* get the hash key and its hash value */
   key = multihash->hashgetkey(multihash->userptr, element);
   keyval = multihash->hashkeyval(multihash->userptr, key);
   hashval = (unsigned int) (keyval % (unsigned) multihash->nlists); /*lint !e573*/
 
   /* remove element from the list at the hash position */
   if( multihashlistRemove(&multihash->lists[hashval], multihash->blkmem, element) )
      --(multihash->nelements);
 
   return SCIP_OKAY;
}
 
/** removes all elements of the multihash table
 *
 *  @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
 *        be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
 */
void SCIPmultihashRemoveAll(
   SCIP_MULTIHASH*       multihash           /**< multihash table */
   )
{
   BMS_BLKMEM* blkmem;
   SCIP_MULTIHASHLIST** lists;
   int i;
 
   assert(multihash != NULL);
 
   blkmem = multihash->blkmem;
   lists = multihash->lists;
 
   /* free hash lists */
   for( i = multihash->nlists - 1; i >= 0; --i )
      multihashlistFree(&lists[i], blkmem);
 
   multihash->nelements = 0;
}
 
/** returns number of multihash table elements */
SCIP_Longint SCIPmultihashGetNElements(
   SCIP_MULTIHASH*       multihash           /**< multihash table */
   )
{
   assert(multihash != NULL);
 
   return multihash->nelements;
}
 
/** returns the load of the given multihash table in percentage */
SCIP_Real SCIPmultihashGetLoad(
   SCIP_MULTIHASH*       multihash           /**< multihash table */
   )
{
   assert(multihash != NULL);
 
   return ((SCIP_Real)(multihash->nelements) / (multihash->nlists) * 100.0);
}
 
/** prints statistics about multihash table usage */
void SCIPmultihashPrintStatistics(
   SCIP_MULTIHASH*       multihash,          /**< multihash table */
   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
   )
{
   SCIP_MULTIHASHLIST* multihashlist;
   int usedslots;
   int maxslotsize;
   int sumslotsize;
   int slotsize;
   int i;
 
   assert(multihash != NULL);
 
   usedslots = 0;
   maxslotsize = 0;
   sumslotsize = 0;
   for( i = 0; i < multihash->nlists; ++i )
   {
      multihashlist = multihash->lists[i];
      if( multihashlist != NULL )
      {
         usedslots++;
         slotsize = 0;
         while( multihashlist != NULL )
         {
            slotsize++;
            multihashlist = multihashlist->next;
         }
         maxslotsize = MAX(maxslotsize, slotsize);
         sumslotsize += slotsize;
      }
   }
   assert(sumslotsize == multihash->nelements);
   SCIP_UNUSED(sumslotsize);
 
   SCIPmessagePrintInfo(messagehdlr, "%" SCIP_LONGINT_FORMAT " multihash entries, used %d/%d slots (%.1f%%)",
      multihash->nelements, usedslots, multihash->nlists, 100.0*(SCIP_Real)usedslots/(SCIP_Real)(multihash->nlists));
   if( usedslots > 0 )
      SCIPmessagePrintInfo(messagehdlr, ", avg. %.1f entries/used slot, max. %d entries in slot",
         (SCIP_Real)(multihash->nelements)/(SCIP_Real)usedslots, maxslotsize);
   SCIPmessagePrintInfo(messagehdlr, "\n");
}
 
/** creates a hash table */
SCIP_RETCODE SCIPhashtableCreate(
   SCIP_HASHTABLE**      hashtable,          /**< pointer to store the created hash table */
   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash table entries */
   int                   tablesize,          /**< size of the hash table */
   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
   void*                 userptr             /**< user pointer */
   )
{
   unsigned int nslots;
 
   /* only assert non negative to catch overflow errors
    * but not zeros due to integer divison
    */
   assert(tablesize >= 0);
   assert(hashtable != NULL);
   assert(hashgetkey != NULL);
   assert(hashkeyeq != NULL);
   assert(hashkeyval != NULL);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashtable) );
 
   /* dont create too small hashtables, i.e. at least size 32, and increase
    * the given size by divinding it by 0.9, since then no rebuilding will
    * be necessary if the given number of elements are inserted. Finally round
    * to the next power of two.
    */
   (*hashtable)->shift = 32;
   (*hashtable)->shift -= (unsigned int)ceil(LOG2(MAX(32.0, tablesize / 0.9)));
 
   /* compute size from shift */
   nslots = 1u << (32 - (*hashtable)->shift);
 
   /* compute mask to do a fast modulo by nslots using bitwise and */
   (*hashtable)->mask = nslots - 1;
   SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*hashtable)->slots, nslots) );
   SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashtable)->hashes, nslots) );
   (*hashtable)->blkmem = blkmem;
   (*hashtable)->hashgetkey = hashgetkey;
   (*hashtable)->hashkeyeq = hashkeyeq;
   (*hashtable)->hashkeyval = hashkeyval;
   (*hashtable)->userptr = userptr;
   (*hashtable)->nelements = 0;
 
   return SCIP_OKAY;
}
 
/** frees the hash table */
void SCIPhashtableFree(
   SCIP_HASHTABLE**      hashtable           /**< pointer to the hash table */
   )
{
   uint32_t nslots;
   SCIP_HASHTABLE* table;
 
   assert(hashtable != NULL);
   assert(*hashtable != NULL);
   table = *hashtable;
   nslots = (*hashtable)->mask + 1;
#ifdef SCIP_DEBUG
   {
      uint32_t maxprobelen = 0;
      uint64_t probelensum = 0;
      uint32_t i;
 
      assert(table != NULL);
 
      for( i = 0; i < nslots; ++i )
      {
         if( table->hashes[i] != 0 )
         {
            uint32_t probelen = ((i + table->mask + 1 - (table->hashes[i]>>(table->shift))) & table->mask) + 1;
            probelensum += probelen;
            maxprobelen = MAX(probelen, maxprobelen);
         }
      }
 
      SCIPdebugMessage("%u hash table entries, used %u/%u slots (%.1f%%)",
                       (unsigned int)table->nelements, (unsigned int)table->nelements, (unsigned int)nslots,
                       100.0*(SCIP_Real)table->nelements/(SCIP_Real)(nslots));
      if( table->nelements > 0 )
         SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
                              (SCIP_Real)(probelensum)/(SCIP_Real)table->nelements, (unsigned int)maxprobelen);
      SCIPdebugMessage("\n");
   }
#endif
 
   /* free main hash table data structure */
   BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->hashes, nslots);
   BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->slots, nslots);
   BMSfreeBlockMemory((*hashtable)->blkmem, hashtable);
}
 
/** removes all elements of the hash table
 *
 *  @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
 *        be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
 *
 *  @deprecated Please use SCIPhashtableRemoveAll()
 */
void SCIPhashtableClear(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   SCIPhashtableRemoveAll(hashtable);
}
 
/* computes the distance from it's desired position for the element stored at pos */
#define ELEM_DISTANCE(pos) (((pos) + hashtable->mask + 1 - (hashtable->hashes[(pos)]>>(hashtable->shift))) & hashtable->mask)
 
/** inserts element in hash table (multiple inserts of same element overrides previous one) */
static
SCIP_RETCODE hashtableInsert(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 element,            /**< element to insert into the table */
   void*                 key,                /**< key of element */
   uint32_t              hashval,            /**< hash value of element */
   SCIP_Bool             override            /**< should element be overridden or an error be returned if already existing */
   )
{
   uint32_t elemdistance;
   uint32_t pos;
#ifndef NDEBUG
   SCIP_Bool swapped = FALSE;
#endif
 
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(element != NULL);
 
   pos = hashval>>(hashtable->shift);
   elemdistance = 0;
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* if position is empty or key equal insert element */
      if( hashtable->hashes[pos] == 0 )
      {
         hashtable->slots[pos] = element;
         hashtable->hashes[pos] = hashval;
         ++hashtable->nelements;
         return SCIP_OKAY;
      }
 
      if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
             hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
      {
         if( override )
         {
#ifndef NDEBUG
            assert(! swapped);
#endif
            hashtable->slots[pos] = element;
            hashtable->hashes[pos] = hashval;
            return SCIP_OKAY;
         }
         else
         {
            return SCIP_KEYALREADYEXISTING;
         }
      }
 
      /* otherwise check if the current element at this position is closer to its hashvalue */
      distance = ELEM_DISTANCE(pos);
      if( distance < elemdistance )
      {
         uint32_t tmp;
 
         /* if this is the case we insert the new element here and find a new position for the old one */
         elemdistance = distance;
         SCIPswapPointers(&hashtable->slots[pos], &element);
         tmp = hashval;
         hashval = hashtable->hashes[pos];
         hashtable->hashes[pos] = tmp;
         key = hashtable->hashgetkey(hashtable->userptr, element);
 
         /* after doing a swap the case that other elements are replaced must not happen anymore */
#ifndef NDEBUG
         swapped = TRUE;
#endif
      }
 
      /* continue until we have found an empty position */
      pos = (pos + 1) & hashtable->mask;
      ++elemdistance;
   }
}
 
/** check if the load factor of the hashtable is too high and rebuild if necessary */
static
SCIP_RETCODE hashtableCheckLoad(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   assert(hashtable != NULL);
   assert(hashtable->shift < 32);
 
   /* use integer arithmetic to approximately check if load factor is above 90% */
   if( ((((uint64_t)hashtable->nelements)<<10)>>(32-hashtable->shift) > 921) )
   {
      void** slots;
      uint32_t* hashes;
      uint32_t nslots;
      uint32_t newnslots;
      uint32_t i;
 
      /* calculate new size (always power of two) */
      nslots = hashtable->mask + 1;
      newnslots = 2*nslots;
      hashtable->mask = newnslots-1;
      --hashtable->shift;
 
      /* reallocate array */
      SCIP_ALLOC( BMSallocBlockMemoryArray(hashtable->blkmem, &slots, newnslots) );
      SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashtable->blkmem, &hashes, newnslots) );
 
      SCIPswapPointers((void**) &slots, (void**) &hashtable->slots);
      SCIPswapPointers((void**) &hashes, (void**) &hashtable->hashes);
      hashtable->nelements = 0;
 
      /* reinsert all elements */
      for( i = 0; i < nslots; ++i )
      {
         /* using SCIP_CALL_ABORT since there are no allocations or duplicates
          * and thus no bad return codes when inserting the elements
          */
         if( hashes[i] != 0 )
         {
            SCIP_CALL_ABORT( hashtableInsert(hashtable, slots[i], hashtable->hashgetkey(hashtable->userptr, slots[i]), hashes[i], FALSE) );
         }
      }
      BMSfreeBlockMemoryArray(hashtable->blkmem, &hashes, nslots);
      BMSfreeBlockMemoryArray(hashtable->blkmem, &slots, nslots);
   }
 
   return SCIP_OKAY;
}
 
 
/** inserts element in hash table
 *
 *  @note multiple inserts of same element overrides previous one
 */
SCIP_RETCODE SCIPhashtableInsert(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 element             /**< element to insert into the table */
   )
{
   void* key;
   uint64_t keyval;
   uint32_t hashval;
 
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(element != NULL);
 
   SCIP_CALL( hashtableCheckLoad(hashtable) );
 
   /* get the hash key and its hash value */
   key = hashtable->hashgetkey(hashtable->userptr, element);
   keyval = hashtable->hashkeyval(hashtable->userptr, key);
   hashval = hashvalue(keyval);
 
   return hashtableInsert(hashtable, element, key, hashval, TRUE);
}
 
/** inserts element in hash table
 *
 *  @note multiple insertion of same element is checked and results in an error
 */
SCIP_RETCODE SCIPhashtableSafeInsert(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 element             /**< element to insert into the table */
   )
{
   void* key;
   uint64_t keyval;
   uint32_t hashval;
 
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(element != NULL);
 
   SCIP_CALL( hashtableCheckLoad(hashtable) );
 
   /* get the hash key and its hash value */
   key = hashtable->hashgetkey(hashtable->userptr, element);
   keyval = hashtable->hashkeyval(hashtable->userptr, key);
   hashval = hashvalue(keyval);
 
   return hashtableInsert(hashtable, element, key, hashval, FALSE);
}
 
/** retrieve element with key from hash table, returns NULL if not existing */
void* SCIPhashtableRetrieve(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 key                 /**< key to retrieve */
   )
{
   uint64_t keyval;
   uint32_t hashval;
   uint32_t pos;
   uint32_t elemdistance;
 
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(key != NULL);
 
   /* get the hash value of the key */
   keyval = hashtable->hashkeyval(hashtable->userptr, key);
   hashval = hashvalue(keyval);
 
   pos = hashval>>(hashtable->shift);
   elemdistance = 0;
 
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* slots is empty so element cannot be contained */
      if( hashtable->hashes[pos] == 0 )
         return NULL;
 
      distance = ELEM_DISTANCE(pos);
 
      /* element cannot be contained since otherwise we would have swapped it with this one during insert */
      if( elemdistance > distance )
         return NULL;
 
      /* found element */
      if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
             hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
         return hashtable->slots[pos];
 
      pos = (pos + 1) & hashtable->mask;
      ++elemdistance;
   }
}
 
/** returns whether the given element exists in the table */
SCIP_Bool SCIPhashtableExists(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 element             /**< element to search in the table */
   )
{
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(element != NULL);
 
   return (SCIPhashtableRetrieve(hashtable, hashtable->hashgetkey(hashtable->userptr, element)) != NULL);
}
 
/** removes element from the hash table, if it exists */
SCIP_RETCODE SCIPhashtableRemove(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   void*                 element             /**< element to remove from the table */
   )
{
   void* key;
   uint64_t keyval;
   uint32_t hashval;
   uint32_t elemdistance;
   uint32_t distance;
   uint32_t pos;
 
   assert(hashtable != NULL);
   assert(hashtable->slots != NULL);
   assert(hashtable->hashes != NULL);
   assert(hashtable->mask > 0);
   assert(hashtable->hashgetkey != NULL);
   assert(hashtable->hashkeyeq != NULL);
   assert(hashtable->hashkeyval != NULL);
   assert(element != NULL);
 
   /* get the hash key and its hash value */
   key = hashtable->hashgetkey(hashtable->userptr, element);
   keyval = hashtable->hashkeyval(hashtable->userptr, key);
   hashval = hashvalue(keyval);
 
   elemdistance = 0;
   pos = hashval>>(hashtable->shift);
   while( TRUE ) /*lint !e716*/
   {
      /* slots empty so element not contained */
      if( hashtable->hashes[pos] == 0 )
         return SCIP_OKAY;
 
      distance = ELEM_DISTANCE(pos);
 
      /* element can not be contained since otherwise we would have swapped it with this one */
      if( elemdistance > distance )
         return SCIP_OKAY;
 
      if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
             hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
      {
         /* element exists at pos so break out of loop */
         break;
      }
 
      pos = (pos + 1) & hashtable->mask;
      ++elemdistance;
   }
 
   /* remove element */
   hashtable->hashes[pos] = 0;
   --hashtable->nelements;
   while( TRUE ) /*lint !e716*/
   {
      uint32_t nextpos = (pos + 1) & hashtable->mask;
 
      /* nothing to do since there is no chain that needs to be moved */
      if( hashtable->hashes[nextpos] == 0 )
         break;
 
      /* check if the element is the start of a new chain and return if that is the case */
      if( (hashtable->hashes[nextpos]>>(hashtable->shift)) == nextpos )
         break;
 
      /* element should be moved to the left and next element needs to be checked */
      hashtable->slots[pos] = hashtable->slots[nextpos];
      hashtable->hashes[pos] = hashtable->hashes[nextpos];
      hashtable->hashes[nextpos] = 0;
 
      pos = nextpos;
   }
 
   return SCIP_OKAY;
}
 
/** removes all elements of the hash table */
void SCIPhashtableRemoveAll(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   assert(hashtable != NULL);
 
   BMSclearMemoryArray(hashtable->hashes, hashtable->mask + 1);
 
   hashtable->nelements = 0;
}
 
/** returns number of hash table elements */
SCIP_Longint SCIPhashtableGetNElements(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   assert(hashtable != NULL);
 
   return hashtable->nelements;
}
 
/** gives the number of entries in the internal arrays of a hash table */
int SCIPhashtableGetNEntries(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   return (int) hashtable->mask + 1;
}
 
/** gives the element at the given index or NULL if entry at that index has no element */
void* SCIPhashtableGetEntry(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   int                   entryidx            /**< index of hash table entry */
   )
{
   return hashtable->hashes[entryidx] == 0 ? NULL : hashtable->slots[entryidx];
}
 
/** returns the load of the given hash table in percentage */
SCIP_Real SCIPhashtableGetLoad(
   SCIP_HASHTABLE*       hashtable           /**< hash table */
   )
{
   assert(hashtable != NULL);
 
   return ((SCIP_Real)(hashtable->nelements) / (hashtable->mask + 1) * 100.0);
}
 
/** prints statistics about hash table usage */
void SCIPhashtablePrintStatistics(
   SCIP_HASHTABLE*       hashtable,          /**< hash table */
   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
   )
{
   uint32_t maxprobelen = 0;
   uint64_t probelensum = 0;
   uint32_t nslots;
   uint32_t i;
 
   assert(hashtable != NULL);
 
   nslots = hashtable->mask + 1;
 
   /* compute the maximum and average probe length */
   for( i = 0; i < nslots; ++i )
   {
      if( hashtable->hashes[i] != 0 )
      {
         uint32_t probelen = ELEM_DISTANCE(i) + 1;
         probelensum += probelen;
         maxprobelen = MAX(probelen, maxprobelen);
      }
   }
 
   /* print general hash table statistics */
   SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
                        (unsigned int)hashtable->nelements, (unsigned int)hashtable->nelements,
                        (unsigned int)nslots, 100.0*(SCIP_Real)hashtable->nelements/(SCIP_Real)(nslots));
 
   /* if not empty print average and maximum probe length */
   if( hashtable->nelements > 0 )
      SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
         (SCIP_Real)(probelensum)/(SCIP_Real)hashtable->nelements, (unsigned int)maxprobelen);
   SCIPmessagePrintInfo(messagehdlr, "\n");
}
 
/** returns TRUE iff both keys (i.e. strings) are equal */
SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString)
{  /*lint --e{715}*/
   const char* string1 = (const char*)key1;
   const char* string2 = (const char*)key2;
 
   return (strcmp(string1, string2) == 0);
}
 
/** returns the hash value of the key (i.e. string) */
SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString)
{  /*lint --e{715}*/
   const char* str;
   uint64_t hash;
 
   str = (const char*)key;
   hash = 37;
   while( *str != '\0' )
   {
      hash *= 11;
      hash += (unsigned int)(*str); /*lint !e571*/
      str++;
   }
 
   return hash;
}
 
 
/** gets the element as the key */
SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard)
{  /*lint --e{715}*/
   /* the key is the element itself */
   return elem;
}
 
/** returns TRUE iff both keys(pointer) are equal */
SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr)
{  /*lint --e{715}*/
   return (key1 == key2);
}
 
/** returns the hash value of the key */
SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr)
{  /*lint --e{715}*/
   /* the key is used as the keyvalue too */
   return (uint64_t) (uintptr_t) key;
}
 
 
 
/*
 * Hash Map
 */
 
/* redefine ELEM_DISTANCE macro for hashmap */
#undef ELEM_DISTANCE
/* computes the distance from it's desired position for the element stored at pos */
#define ELEM_DISTANCE(pos) (((pos) + hashmap->mask + 1 - (hashmap->hashes[(pos)]>>(hashmap->shift))) & hashmap->mask)
 
/** inserts element in hash table */
static
SCIP_RETCODE hashmapInsert(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< element to insert into the table */
   SCIP_HASHMAPIMAGE     image,              /**< key of element */
   uint32_t              hashval,            /**< hash value of element */
   SCIP_Bool             override            /**< should element be overridden or error be returned if already existing */
   )
{
   uint32_t elemdistance;
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashval != 0);
 
   pos = hashval>>(hashmap->shift);
   elemdistance = 0;
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* if position is empty or key equal insert element */
      if( hashmap->hashes[pos] == 0 )
      {
         hashmap->slots[pos].origin = origin;
         hashmap->slots[pos].image = image;
         hashmap->hashes[pos] = hashval;
         ++hashmap->nelements;
         return SCIP_OKAY;
      }
 
      if( hashval == hashmap->hashes[pos] && origin == hashmap->slots[pos].origin )
      {
         if( override )
         {
            hashmap->slots[pos].origin = origin;
            hashmap->slots[pos].image = image;
            hashmap->hashes[pos] = hashval;
            return SCIP_OKAY;
         }
         else
         {
            return SCIP_KEYALREADYEXISTING;
         }
      }
 
      /* otherwise check if the current element at this position is closer to its hashvalue */
      distance = ELEM_DISTANCE(pos);
      if( distance < elemdistance )
      {
         SCIP_HASHMAPIMAGE tmp;
         uint32_t tmphash;
 
         /* if this is the case we insert the new element here and find a new position for the old one */
         elemdistance = distance;
         tmphash = hashval;
         hashval = hashmap->hashes[pos];
         hashmap->hashes[pos] = tmphash;
         SCIPswapPointers(&hashmap->slots[pos].origin, &origin);
         tmp = image;
         image = hashmap->slots[pos].image;
         hashmap->slots[pos].image = tmp;
      }
 
      /* continue until we have found an empty position */
      pos = (pos + 1) & hashmap->mask;
      ++elemdistance;
   }
}
 
/** lookup origin in the hashmap. If element is found returns true and the position of the element,
 *  otherwise returns FALSE.
 */
static
SCIP_Bool hashmapLookup(
   SCIP_HASHMAP*         hashmap,            /**< hash table */
   void*                 origin,             /**< origin to lookup */
   uint32_t*             pos                 /**< pointer to store position of element, if exists */
   )
{
   uint32_t hashval;
   uint32_t elemdistance;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
   assert(hashval != 0);
 
   *pos = hashval>>(hashmap->shift);
   elemdistance = 0;
 
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* slots is empty so element cannot be contained */
      if( hashmap->hashes[*pos] == 0 )
         return FALSE;
 
      distance = ELEM_DISTANCE(*pos);
      /* element can not be contained since otherwise we would have swapped it with this one during insert */
      if( elemdistance > distance )
         return FALSE;
 
      /* found element */
      if( hashmap->hashes[*pos] == hashval && hashmap->slots[*pos].origin == origin )
         return TRUE;
 
      *pos = (*pos + 1) & hashmap->mask;
      ++elemdistance;
   }
}
 
/** check if the load factor of the hashmap is too high and rebuild if necessary */
static
SCIP_RETCODE hashmapCheckLoad(
   SCIP_HASHMAP*         hashmap             /**< hash table */
   )
{
   assert(hashmap != NULL);
   assert(hashmap->shift < 32);
 
   /* use integer arithmetic to approximately check if load factor is above 90% */
   if( ((((uint64_t)hashmap->nelements)<<10)>>(32-hashmap->shift) > 921) )
   {
      SCIP_HASHMAPENTRY* slots;
      uint32_t* hashes;
      uint32_t nslots;
      uint32_t newnslots;
      uint32_t i;
 
      /* calculate new size (always power of two) */
      nslots = hashmap->mask + 1;
      --hashmap->shift;
      newnslots = 2*nslots;
      hashmap->mask = newnslots-1;
 
      /* reallocate array */
      SCIP_ALLOC( BMSallocBlockMemoryArray(hashmap->blkmem, &slots, newnslots) );
      SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashmap->blkmem, &hashes, newnslots) );
 
      SCIPswapPointers((void**) &slots, (void**) &hashmap->slots);
      SCIPswapPointers((void**) &hashes, (void**) &hashmap->hashes);
      hashmap->nelements = 0;
 
      /* reinsert all elements */
      for( i = 0; i < nslots; ++i )
      {
         /* using SCIP_CALL_ABORT since there are no allocations or duplicates
          * and thus no bad return codes when inserting the elements
          */
         if( hashes[i] != 0 )
         {
            SCIP_CALL_ABORT( hashmapInsert(hashmap, slots[i].origin, slots[i].image, hashes[i], FALSE) );
         }
      }
 
      /* free old arrays */
      BMSfreeBlockMemoryArray(hashmap->blkmem, &hashes, nslots);
      BMSfreeBlockMemoryArray(hashmap->blkmem, &slots, nslots);
   }
 
   return SCIP_OKAY;
}
 
/** creates a hash map mapping pointers to pointers */
SCIP_RETCODE SCIPhashmapCreate(
   SCIP_HASHMAP**        hashmap,            /**< pointer to store the created hash map */
   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash map entries */
   int                   mapsize             /**< size of the hash map */
   )
{
   uint32_t nslots;
 
   assert(hashmap != NULL);
   assert(mapsize >= 0);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashmap) );
 
   /* dont create too small hashtables, i.e. at least size 32, and increase
    * the given size by divinding it by 0.9, since then no rebuilding will
    * be necessary if the given number of elements are inserted. Finally round
    * to the next power of two.
    */
   (*hashmap)->shift = 32;
   (*hashmap)->shift -= (unsigned int)ceil(log(MAX(32, mapsize / 0.9)) / log(2.0));
   nslots = 1u << (32 - (*hashmap)->shift);
   (*hashmap)->mask = nslots - 1;
   (*hashmap)->blkmem = blkmem;
   (*hashmap)->nelements = 0;
   (*hashmap)->hashmaptype = SCIP_HASHMAPTYPE_UNKNOWN;
 
   SCIP_ALLOC( BMSallocBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots) );
   SCIP_ALLOC( BMSallocClearBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots) );
 
   return SCIP_OKAY;
}
 
/** frees the hash map */
void SCIPhashmapFree(
   SCIP_HASHMAP**        hashmap             /**< pointer to the hash map */
   )
{
   uint32_t nslots;
 
   assert(hashmap != NULL);
   assert(*hashmap != NULL);
 
   nslots = (*hashmap)->mask + 1;
#ifdef SCIP_DEBUG
   {
      uint32_t maxprobelen = 0;
      uint64_t probelensum = 0;
      uint32_t i;
 
      assert(hashmap != NULL);
 
      for( i = 0; i < nslots; ++i )
      {
         if( (*hashmap)->hashes[i] != 0 )
         {
            uint32_t probelen = ((i + (*hashmap)->mask + 1 - ((*hashmap)->hashes[i]>>((*hashmap)->shift))) & (*hashmap)->mask) + 1;
            probelensum += probelen;
            maxprobelen = MAX(probelen, maxprobelen);
         }
      }
 
      SCIPdebugMessage("%u hash map entries, used %u/%u slots (%.1f%%)",
                       (unsigned int)(*hashmap)->nelements, (unsigned int)(*hashmap)->nelements, (unsigned int)nslots,
                       100.0*(SCIP_Real)(*hashmap)->nelements/(SCIP_Real)(nslots));
      if( (*hashmap)->nelements > 0 )
         SCIPdebugPrintf(", avg. probe length is %.1f, max. probe length is %u",
                          (SCIP_Real)(probelensum)/(SCIP_Real)(*hashmap)->nelements, (unsigned int)maxprobelen);
      SCIPdebugPrintf("\n");
   }
#endif
 
   /* free main hash map data structure */
   BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots);
   BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots);
   BMSfreeBlockMemory((*hashmap)->blkmem, hashmap);
}
 
/** inserts new origin->image pair in hash map
 *
 *  @note multiple insertion of same element is checked and results in an error
 */
SCIP_RETCODE SCIPhashmapInsert(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   void*                 image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_POINTER;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.ptr = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
 
   return SCIP_OKAY;
}
 
/** inserts new origin->image pair in hash map
 *
 *  @note multiple insertion of same element is checked and results in an error
 */
SCIP_RETCODE SCIPhashmapInsertInt(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   int                   image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.integer = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
 
   return SCIP_OKAY;
}
 
/** inserts new origin->image pair in hash map
 *
 *  @note multiple insertion of same element is checked and results in an error
 */
SCIP_RETCODE SCIPhashmapInsertReal(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   SCIP_Real             image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_REAL;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.real = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
 
   return SCIP_OKAY;
}
 
/** retrieves image of given origin from the hash map, or NULL if no image exists */
void* SCIPhashmapGetImage(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin              /**< origin to retrieve image for */
   )
{
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
 
   if( hashmapLookup(hashmap, origin, &pos) )
      return hashmap->slots[pos].image.ptr;
 
   return NULL;
}
 
/** retrieves image of given origin from the hash map, or INT_MAX if no image exists */
int SCIPhashmapGetImageInt(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin              /**< origin to retrieve image for */
   )
{
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
 
   if( hashmapLookup(hashmap, origin, &pos) )
      return hashmap->slots[pos].image.integer;
 
   return INT_MAX;
}
 
/** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */
SCIP_Real SCIPhashmapGetImageReal(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin              /**< origin to retrieve image for */
   )
{
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
 
   if( hashmapLookup(hashmap, origin, &pos) )
      return hashmap->slots[pos].image.real;
 
   return SCIP_INVALID;
}
 
/** sets image for given origin in the hash map, either by modifying existing origin->image pair
 *  or by appending a new origin->image pair
 */
SCIP_RETCODE SCIPhashmapSetImage(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   void*                 image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_POINTER;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.ptr = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
 
   return SCIP_OKAY;
}
 
/** sets image for given origin in the hash map, either by modifying existing origin->image pair
 *  or by appending a new origin->image pair
 */
SCIP_RETCODE SCIPhashmapSetImageInt(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   int                   image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.integer = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
 
   return SCIP_OKAY;
}
 
/** sets image for given origin in the hash map, either by modifying existing origin->image pair
 *  or by appending a new origin->image pair
 */
SCIP_RETCODE SCIPhashmapSetImageReal(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin,             /**< origin to set image for */
   SCIP_Real             image               /**< new image for origin */
   )
{
   uint32_t hashval;
   SCIP_HASHMAPIMAGE img;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->mask > 0);
   assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
 
#ifndef NDEBUG
   if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
      hashmap->hashmaptype = SCIP_HASHMAPTYPE_REAL;
#endif
 
   SCIP_CALL( hashmapCheckLoad(hashmap) );
 
   /* get the hash value */
   hashval = hashvalue((size_t)origin);
 
   /* append origin->image pair to hash map */
   img.real = image;
   SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
 
   return SCIP_OKAY;
}
 
/** checks whether an image to the given origin exists in the hash map */
SCIP_Bool SCIPhashmapExists(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin              /**< origin to search for */
   )
{
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->hashes != NULL);
   assert(hashmap->mask > 0);
 
   return hashmapLookup(hashmap, origin, &pos);
}
 
/** removes origin->image pair from the hash map, if it exists */
SCIP_RETCODE SCIPhashmapRemove(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   void*                 origin              /**< origin to remove from the list */
   )
{
   uint32_t pos;
 
   assert(hashmap != NULL);
   assert(hashmap->slots != NULL);
   assert(hashmap->mask > 0);
 
   assert(origin != NULL);
 
   if( hashmapLookup(hashmap, origin, &pos) )
   {
      /* remove element */
      hashmap->hashes[pos] = 0;
      --hashmap->nelements;
 
      /* move other elements if necessary */
      while( TRUE ) /*lint !e716*/
      {
         uint32_t nextpos = (pos + 1) & hashmap->mask;
 
         /* nothing to do since there is no chain that needs to be moved */
         if( hashmap->hashes[nextpos] == 0 )
            return SCIP_OKAY;
 
         /* check if the element is the start of a new chain and return if that is the case */
         if( (hashmap->hashes[nextpos]>>(hashmap->shift)) == nextpos )
            return SCIP_OKAY;
 
         /* element should be moved to the left and next element needs to be checked */
         hashmap->slots[pos].origin = hashmap->slots[nextpos].origin;
         hashmap->slots[pos].image = hashmap->slots[nextpos].image;
         hashmap->hashes[pos] = hashmap->hashes[nextpos];
         hashmap->hashes[nextpos] = 0;
 
         pos = nextpos;
      }
   }
 
   return SCIP_OKAY;
}
 
/** prints statistics about hash map usage */
void SCIPhashmapPrintStatistics(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
   )
{
   uint32_t maxprobelen = 0;
   uint64_t probelensum = 0;
   uint32_t nslots;
   uint32_t i;
 
   assert(hashmap != NULL);
 
   nslots = hashmap->mask + 1;
 
   /* compute the maximum and average probe length */
   for( i = 0; i < nslots; ++i )
   {
      if( hashmap->hashes[i] != 0 )
      {
         uint32_t probelen = ELEM_DISTANCE(i) + 1;
         probelensum += probelen;
         maxprobelen = MAX(probelen, maxprobelen);
      }
   }
 
   /* print general hash map statistics */
   SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
                        (unsigned int)hashmap->nelements, (unsigned int)hashmap->nelements,
                        (unsigned int)nslots, 100.0*(SCIP_Real)hashmap->nelements/(SCIP_Real)(nslots));
 
   /* if not empty print average and maximum probe length */
   if( hashmap->nelements > 0 )
      SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
         (SCIP_Real)(probelensum)/(SCIP_Real)hashmap->nelements, (unsigned int)maxprobelen);
   SCIPmessagePrintInfo(messagehdlr, "\n");
}
 
/** indicates whether a hash map has no entries */
SCIP_Bool SCIPhashmapIsEmpty(
   SCIP_HASHMAP*         hashmap             /**< hash map */
   )
{
   assert(hashmap != NULL);
 
   return hashmap->nelements == 0;
}
 
/** gives the number of elements in a hash map */
int SCIPhashmapGetNElements(
   SCIP_HASHMAP*         hashmap             /**< hash map */
   )
{
   return (int) hashmap->nelements;
}
 
/** gives the number of entries in the internal arrays of a hash map */
int SCIPhashmapGetNEntries(
   SCIP_HASHMAP*         hashmap             /**< hash map */
   )
{
   return (int) hashmap->mask + 1;
}
 
/** gives the hashmap entry at the given index or NULL if entry is empty */
SCIP_HASHMAPENTRY* SCIPhashmapGetEntry(
   SCIP_HASHMAP*         hashmap,            /**< hash map */
   int                   entryidx            /**< index of hash map entry */
   )
{
   assert(hashmap != NULL);
 
   return hashmap->hashes[entryidx] == 0 ? NULL : &hashmap->slots[entryidx];
}
 
/** gives the origin of the hashmap entry */
void* SCIPhashmapEntryGetOrigin(
   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
   )
{
   assert(entry != NULL);
 
   return entry->origin;
}
 
/** gives the image of the hashmap entry */
void* SCIPhashmapEntryGetImage(
   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
   )
{
   assert(entry != NULL);
 
   return entry->image.ptr;
}
 
/** gives the image of the hashmap entry */
int SCIPhashmapEntryGetImageInt(
   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
   )
{
   assert(entry != NULL);
 
   return entry->image.integer;
}
 
/** gives the image of the hashmap entry */
SCIP_Real SCIPhashmapEntryGetImageReal(
   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
   )
{
   assert(entry != NULL);
 
   return entry->image.real;
}
 
/** sets pointer image of a hashmap entry */
void SCIPhashmapEntrySetImage(
   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
   void*                 image               /**< new image */
   )
{
   assert(entry != NULL);
 
   entry->image.ptr = image;
}
 
/** sets integer image of a hashmap entry */
void SCIPhashmapEntrySetImageInt(
   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
   int                   image               /**< new image */
   )
{
   assert(entry != NULL);
 
   entry->image.integer = image;
}
 
/** sets real image of a hashmap entry */
void SCIPhashmapEntrySetImageReal(
   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
   SCIP_Real             image               /**< new image */
   )
{
   assert(entry != NULL);
 
   entry->image.real = image;
}
 
/** removes all entries in a hash map. */
SCIP_RETCODE SCIPhashmapRemoveAll(
   SCIP_HASHMAP*         hashmap             /**< hash map */
   )
{
   assert(hashmap != NULL);
 
   BMSclearMemoryArray(hashmap->hashes, hashmap->mask + 1);
 
   hashmap->nelements = 0;
 
   return SCIP_OKAY;
}
 
 
/*
 * Hash Set
 */
 
/* redefine ELEM_DISTANCE macro for hashset */
#undef ELEM_DISTANCE
/* computes the distance from it's desired position for the element stored at pos */
#define ELEM_DISTANCE(pos) (((pos) + nslots - hashSetDesiredPos(hashset, hashset->slots[(pos)])) & mask)
 
/* calculate desired position of element in hash set */
static
uint32_t hashSetDesiredPos(
   SCIP_HASHSET*         hashset,            /**< the hash set */
   void*                 element             /**< element to calculate position for */
   )
{
   return (uint32_t)((UINT64_C(0x9e3779b97f4a7c15) * (uintptr_t)element)>>(hashset->shift));
}
 
static
void hashsetInsert(
   SCIP_HASHSET*         hashset,            /**< hash set */
   void*                 element             /**< element to insert */
   )
{
   uint32_t elemdistance;
   uint32_t pos;
   uint32_t nslots;
   uint32_t mask;
 
   assert(hashset != NULL);
   assert(hashset->slots != NULL);
   assert(element != NULL);
 
   pos = hashSetDesiredPos(hashset, element);
   nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
   mask = nslots - 1;
 
   elemdistance = 0;
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* if position is empty or key equal insert element */
      if( hashset->slots[pos] == NULL )
      {
         hashset->slots[pos] = element;
         ++hashset->nelements;
         return;
      }
 
      if( hashset->slots[pos] == element )
         return;
 
      /* otherwise check if the current element at this position is closer to its hashvalue */
      distance = ELEM_DISTANCE(pos);
      if( distance < elemdistance )
      {
         /* if this is the case we insert the new element here and find a new position for the old one */
         elemdistance = distance;
         SCIPswapPointers(&hashset->slots[pos], &element);
      }
 
      /* continue until we have found an empty position */
      pos = (pos + 1) & mask;
      ++elemdistance;
   }
}
 
/** check if the load factor of the hash set is too high and rebuild if necessary */
static
SCIP_RETCODE hashsetCheckLoad(
   SCIP_HASHSET*         hashset,            /**< hash set */
   BMS_BLKMEM*           blkmem              /**< block memory used to store hash set entries */
   )
{
   assert(hashset != NULL);
   assert(hashset->shift < 64);
 
   /* use integer arithmetic to approximately check if load factor is above 90% */
   if( ((((uint64_t)hashset->nelements)<<10)>>(64-hashset->shift) > 921) )
   {
      void** slots;
      uint32_t nslots;
      uint32_t newnslots;
      uint32_t i;
 
      /* calculate new size (always power of two) */
      nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
      newnslots = 2*nslots;
      --hashset->shift;
 
      /* reallocate array */
      SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &slots, newnslots) );
 
      SCIPswapPointers((void**) &slots, (void**) &hashset->slots);
      hashset->nelements = 0;
 
      /* reinsert all elements */
      for( i = 0; i < nslots; ++i )
      {
         if( slots[i] != NULL )
            hashsetInsert(hashset, slots[i]);
      }
 
      BMSfreeBlockMemoryArray(blkmem, &slots, nslots);
   }
 
   return SCIP_OKAY;
}
 
/** creates a hash set of pointers */
SCIP_RETCODE SCIPhashsetCreate(
   SCIP_HASHSET**        hashset,            /**< pointer to store the created hash set */
   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash set entries */
   int                   size                /**< initial size of the hash set; it is guaranteed that the set is not
                                              *   resized if at most that many elements are inserted */
   )
{
   uint32_t nslots;
 
   assert(hashset != NULL);
   assert(size >= 0);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashset) );
 
   /* do not create too small hashtables, i.e. at least size 32, and increase
    * the given size by dividing it by 0.9, since then no rebuilding will
    * be necessary if the given number of elements are inserted. Finally round
    * to the next power of two.
    */
   (*hashset)->shift = 64;
   (*hashset)->shift -= (unsigned int)ceil(log(MAX(8.0, size / 0.9)) / log(2.0));
   nslots = (uint32_t)SCIPhashsetGetNSlots(*hashset);
   (*hashset)->nelements = 0;
 
   SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashset)->slots, nslots) );
 
   return SCIP_OKAY;
}
 
/** frees the hash set */
void SCIPhashsetFree(
   SCIP_HASHSET**        hashset,            /**< pointer to the hash set */
   BMS_BLKMEM*           blkmem              /**< block memory used to store hash set entries */
   )
{
   BMSfreeBlockMemoryArray(blkmem, &(*hashset)->slots, SCIPhashsetGetNSlots(*hashset));
   BMSfreeBlockMemory(blkmem, hashset);
}
 
/** inserts new element into the hash set */
SCIP_RETCODE SCIPhashsetInsert(
   SCIP_HASHSET*         hashset,            /**< hash set */
   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash set entries */
   void*                 element             /**< element to insert */
   )
{
   assert(hashset != NULL);
   assert(hashset->slots != NULL);
 
   SCIP_CALL( hashsetCheckLoad(hashset, blkmem) );
 
   hashsetInsert(hashset, element);
 
   return SCIP_OKAY;
}
 
/** checks whether an element exists in the hash set */
SCIP_Bool SCIPhashsetExists(
   SCIP_HASHSET*         hashset,            /**< hash set */
   void*                 element             /**< element to search for */
   )
{
   uint32_t pos;
   uint32_t nslots;
   uint32_t mask;
   uint32_t elemdistance;
 
   assert(hashset != NULL);
   assert(hashset->slots != NULL);
 
   pos = hashSetDesiredPos(hashset, element);
   nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
   mask = nslots - 1;
   elemdistance = 0;
 
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* found element */
      if( hashset->slots[pos] == element )
         return TRUE;
 
      /* slots is empty so element cannot be contained */
      if( hashset->slots[pos] == NULL )
         return FALSE;
 
      distance = ELEM_DISTANCE(pos);
      /* element can not be contained since otherwise we would have swapped it with this one during insert */
      if( elemdistance > distance )
         return FALSE;
 
      pos = (pos + 1) & mask;
      ++elemdistance;
   }
}
 
/** removes an element from the hash set, if it exists */
SCIP_RETCODE SCIPhashsetRemove(
   SCIP_HASHSET*         hashset,            /**< hash set */
   void*                 element             /**< origin to remove from the list */
   )
{
   uint32_t pos;
   uint32_t nslots;
   uint32_t mask;
   uint32_t elemdistance;
 
   assert(hashset != NULL);
   assert(hashset->slots != NULL);
   assert(element != NULL);
 
   pos = hashSetDesiredPos(hashset, element);
   nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
   mask = nslots - 1;
   elemdistance = 0;
 
   while( TRUE ) /*lint !e716*/
   {
      uint32_t distance;
 
      /* found element */
      if( hashset->slots[pos] == element )
         break;
 
      /* slots is empty so element cannot be contained */
      if( hashset->slots[pos] == NULL )
         return SCIP_OKAY;
 
      distance = ELEM_DISTANCE(pos);
      /* element can not be contained since otherwise we would have swapped it with this one during insert */
      if( elemdistance > distance )
         return SCIP_OKAY;
 
      pos = (pos + 1) & mask;
      ++elemdistance;
   }
 
   assert(hashset->slots[pos] == element);
   assert(SCIPhashsetExists(hashset, element));
 
   /* remove element */
   --hashset->nelements;
 
   /* move other elements if necessary */
   while( TRUE ) /*lint !e716*/
   {
      uint32_t nextpos = (pos + 1) & mask;
 
      /* nothing to do since there is no chain that needs to be moved */
      if( hashset->slots[nextpos] == NULL )
      {
         hashset->slots[pos] = NULL;
         assert(!SCIPhashsetExists(hashset, element));
         return SCIP_OKAY;
      }
 
      /* check if the element is the start of a new chain and return if that is the case */
      if( hashSetDesiredPos(hashset, hashset->slots[nextpos]) == nextpos )
      {
         hashset->slots[pos] = NULL;
         assert(!SCIPhashsetExists(hashset, element));
         return SCIP_OKAY;
      }
 
      /* element should be moved to the left and next element needs to be checked */
      hashset->slots[pos] = hashset->slots[nextpos];
 
      pos = nextpos;
   }
}
 
/** prints statistics about hash set usage */
void SCIPhashsetPrintStatistics(
   SCIP_HASHSET*         hashset,            /**< hash set */
   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
   )
{
   uint32_t maxprobelen = 0;
   uint64_t probelensum = 0;
   uint32_t nslots;
   uint32_t mask;
   uint32_t i;
 
   assert(hashset != NULL);
 
   nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
   mask = nslots - 1;
 
   /* compute the maximum and average probe length */
   for( i = 0; i < nslots; ++i )
   {
      if( hashset->slots[i] != NULL )
      {
         uint32_t probelen = ((hashSetDesiredPos(hashset, hashset->slots[i]) + nslots - i) & mask) + 1;
         probelensum += probelen;
         maxprobelen = MAX(probelen, maxprobelen);
      }
   }
 
   /* print general hash set statistics */
   SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
                        (unsigned int)hashset->nelements, (unsigned int)hashset->nelements,
                        (unsigned int)nslots, 100.0*(SCIP_Real)hashset->nelements/(SCIP_Real)(nslots));
 
   /* if not empty print average and maximum probe length */
   if( hashset->nelements > 0 )
      SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
         (SCIP_Real)(probelensum)/(SCIP_Real)hashset->nelements, (unsigned int)maxprobelen);
   SCIPmessagePrintInfo(messagehdlr, "\n");
}
 
/* In debug mode, the following methods are implemented as function calls to ensure
 * type validity.
 * In optimized mode, the methods are implemented as defines to improve performance.
 * However, we want to have them in the library anyways, so we have to undef the defines.
 */
 
#undef SCIPhashsetIsEmpty
#undef SCIPhashsetGetNElements
#undef SCIPhashsetGetNSlots
#undef SCIPhashsetGetSlots
 
/** indicates whether a hash set has no entries */
SCIP_Bool SCIPhashsetIsEmpty(
   SCIP_HASHSET*         hashset             /**< hash set */
   )
{
   return hashset->nelements == 0;
}
 
/** gives the number of elements in a hash set */
int SCIPhashsetGetNElements(
   SCIP_HASHSET*         hashset             /**< hash set */
   )
{
   return (int)hashset->nelements;
}
 
/** gives the number of slots of a hash set */
int SCIPhashsetGetNSlots(
   SCIP_HASHSET*         hashset             /**< hash set */
   )
{
   return (int) (1u << (64 - hashset->shift));
}
 
/** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
void** SCIPhashsetGetSlots(
   SCIP_HASHSET*         hashset             /**< hash set */
   )
{
   return hashset->slots;
}
 
/** removes all entries in a hash set. */
void SCIPhashsetRemoveAll(
   SCIP_HASHSET*         hashset             /**< hash set */
   )
{
   BMSclearMemoryArray(hashset->slots, SCIPhashsetGetNSlots(hashset));
 
   hashset->nelements = 0;
}
 
/*
 * Dynamic Arrays
 */
 
/** creates a dynamic array of real values */
SCIP_RETCODE SCIPrealarrayCreate(
   SCIP_REALARRAY**      realarray,          /**< pointer to store the real array */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   assert(realarray != NULL);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, realarray) );
   (*realarray)->blkmem = blkmem;
   (*realarray)->vals = NULL;
   (*realarray)->valssize = 0;
   (*realarray)->firstidx = -1;
   (*realarray)->minusedidx = INT_MAX;
   (*realarray)->maxusedidx = INT_MIN;
 
   return SCIP_OKAY;
}
 
/** creates a copy of a dynamic array of real values */
SCIP_RETCODE SCIPrealarrayCopy(
   SCIP_REALARRAY**      realarray,          /**< pointer to store the copied real array */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_REALARRAY*       sourcerealarray     /**< dynamic real array to copy */
   )
{
   assert(realarray != NULL);
   assert(sourcerealarray != NULL);
 
   SCIP_CALL( SCIPrealarrayCreate(realarray, blkmem) );
   if( sourcerealarray->valssize > 0 )
   {
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*realarray)->vals, sourcerealarray->vals, \
                     sourcerealarray->valssize) );
   }
   (*realarray)->valssize = sourcerealarray->valssize;
   (*realarray)->firstidx = sourcerealarray->firstidx;
   (*realarray)->minusedidx = sourcerealarray->minusedidx;
   (*realarray)->maxusedidx = sourcerealarray->maxusedidx;
 
   return SCIP_OKAY;
}
 
/** frees a dynamic array of real values */
SCIP_RETCODE SCIPrealarrayFree(
   SCIP_REALARRAY**      realarray           /**< pointer to the real array */
   )
{
   assert(realarray != NULL);
   assert(*realarray != NULL);
 
   BMSfreeBlockMemoryArrayNull((*realarray)->blkmem, &(*realarray)->vals, (*realarray)->valssize);
   BMSfreeBlockMemory((*realarray)->blkmem, realarray);
 
   return SCIP_OKAY;
}
 
/** extends dynamic array to be able to store indices from minidx to maxidx */
SCIP_RETCODE SCIPrealarrayExtend(
   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   minidx,             /**< smallest index to allocate storage for */
   int                   maxidx              /**< largest index to allocate storage for */
   )
{
   int nused;
   int nfree;
   int newfirstidx;
   int i;
 
   assert(realarray != NULL);
   assert(realarray->minusedidx == INT_MAX || realarray->firstidx >= 0);
   assert(realarray->maxusedidx == INT_MIN || realarray->firstidx >= 0);
   assert(realarray->minusedidx == INT_MAX || realarray->minusedidx >= realarray->firstidx);
   assert(realarray->maxusedidx == INT_MIN || realarray->maxusedidx < realarray->firstidx + realarray->valssize);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   minidx = MIN(minidx, realarray->minusedidx);
   maxidx = MAX(maxidx, realarray->maxusedidx);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   SCIPdebugMessage("extending realarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
      (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, minidx, maxidx);
 
   /* check, whether we have to allocate additional memory, or shift the array */
   nused = maxidx - minidx + 1;
   if( nused > realarray->valssize )
   {
      SCIP_Real* newvals;
      int newvalssize;
 
      /* allocate new memory storage */
      newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
      SCIP_ALLOC( BMSallocBlockMemoryArray(realarray->blkmem, &newvals, newvalssize) );
      nfree = newvalssize - nused;
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + newvalssize);
 
      /* initialize memory array by copying old values and setting new values to zero */
      if( realarray->firstidx != -1 )
      {
         for( i = 0; i < realarray->minusedidx - newfirstidx; ++i )
            newvals[i] = 0.0;
 
         /* check for possible overflow or negative value */
         assert(realarray->maxusedidx - realarray->minusedidx + 1 > 0);
 
         BMScopyMemoryArray(&newvals[realarray->minusedidx - newfirstidx],
            &(realarray->vals[realarray->minusedidx - realarray->firstidx]),
            realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866 !e776*/
         for( i = realarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
            newvals[i] = 0.0;
      }
      else
      {
         for( i = 0; i < newvalssize; ++i )
            newvals[i] = 0.0;
      }
 
      /* free old memory storage, and set the new array parameters */
      BMSfreeBlockMemoryArrayNull(realarray->blkmem, &realarray->vals, realarray->valssize);
      realarray->vals = newvals;
      realarray->valssize = newvalssize;
      realarray->firstidx = newfirstidx;
   }
   else if( realarray->firstidx == -1 )
   {
      /* a sufficiently large memory storage exists, but it was cleared */
      nfree = realarray->valssize - nused;
      assert(nfree >= 0);
      realarray->firstidx = minidx - nfree/2;
      assert(realarray->firstidx <= minidx);
      assert(maxidx < realarray->firstidx + realarray->valssize);
#ifndef NDEBUG
      for( i = 0; i < realarray->valssize; ++i )
         assert(realarray->vals[i] == 0.0);
#endif
   }
   else if( minidx < realarray->firstidx )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the right */
      nfree = realarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + realarray->valssize);
 
      if( realarray->minusedidx <= realarray->maxusedidx )
      {
         int shift;
 
         assert(realarray->firstidx <= realarray->minusedidx);
         assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
 
         /* shift used part of array to the right */
         shift = realarray->firstidx - newfirstidx;
         assert(shift > 0);
         for( i = realarray->maxusedidx - realarray->firstidx; i >= realarray->minusedidx - realarray->firstidx; --i )
         {
            assert(0 <= i + shift && i + shift < realarray->valssize);
            realarray->vals[i + shift] = realarray->vals[i];
         }
         /* clear the formerly used head of the array */
         for( i = 0; i < shift; ++i )
            realarray->vals[realarray->minusedidx - realarray->firstidx + i] = 0.0;
      }
      realarray->firstidx = newfirstidx;
   }
   else if( maxidx >= realarray->firstidx + realarray->valssize )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the left */
      nfree = realarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + realarray->valssize);
 
      if( realarray->minusedidx <= realarray->maxusedidx )
      {
         int shift;
 
         assert(realarray->firstidx <= realarray->minusedidx);
         assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
 
         /* shift used part of array to the left */
         shift = newfirstidx - realarray->firstidx;
         assert(shift > 0);
         for( i = realarray->minusedidx - realarray->firstidx; i <= realarray->maxusedidx - realarray->firstidx; ++i )
         {
            assert(0 <= i - shift && i - shift < realarray->valssize);
            realarray->vals[i - shift] = realarray->vals[i];
         }
         /* clear the formerly used tail of the array */
         for( i = 0; i < shift; ++i )
            realarray->vals[realarray->maxusedidx - realarray->firstidx - i] = 0.0;
      }
      realarray->firstidx = newfirstidx;
   }
 
   assert(minidx >= realarray->firstidx);
   assert(maxidx < realarray->firstidx + realarray->valssize);
 
   return SCIP_OKAY;
}
 
/** clears a dynamic real array */
SCIP_RETCODE SCIPrealarrayClear(
   SCIP_REALARRAY*       realarray           /**< dynamic real array */
   )
{
   assert(realarray != NULL);
 
   SCIPdebugMessage("clearing realarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
      (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx);
 
   if( realarray->minusedidx <= realarray->maxusedidx )
   {
      assert(realarray->firstidx <= realarray->minusedidx);
      assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
      assert(realarray->firstidx != -1);
      assert(realarray->valssize > 0);
 
      /* clear the used part of array */
      BMSclearMemoryArray(&realarray->vals[realarray->minusedidx - realarray->firstidx],
         realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866*/
 
      /* mark the array cleared */
      realarray->minusedidx = INT_MAX;
      realarray->maxusedidx = INT_MIN;
   }
   assert(realarray->minusedidx == INT_MAX);
   assert(realarray->maxusedidx == INT_MIN);
 
   return SCIP_OKAY;
}
 
/** gets value of entry in dynamic array */
SCIP_Real SCIPrealarrayGetVal(
   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
   int                   idx                 /**< array index to get value for */
   )
{
   assert(realarray != NULL);
   assert(idx >= 0);
 
   if( idx < realarray->minusedidx || idx > realarray->maxusedidx )
      return 0.0;
   else
   {
      assert(realarray->vals != NULL);
      assert(idx - realarray->firstidx >= 0);
      assert(idx - realarray->firstidx < realarray->valssize);
 
      return realarray->vals[idx - realarray->firstidx];
   }
}
 
/** sets value of entry in dynamic array */
SCIP_RETCODE SCIPrealarraySetVal(
   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to set value for */
   SCIP_Real             val                 /**< value to set array index to */
   )
{
   assert(realarray != NULL);
   assert(idx >= 0);
 
   SCIPdebugMessage("setting realarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %g\n",
      (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, idx, val);
 
   if( val != 0.0 )
   {
      /* extend array to be able to store the index */
      SCIP_CALL( SCIPrealarrayExtend(realarray, arraygrowinit, arraygrowfac, idx, idx) );
      assert(idx >= realarray->firstidx);
      assert(idx < realarray->firstidx + realarray->valssize);
 
      /* set the array value of the index */
      realarray->vals[idx - realarray->firstidx] = val;
 
      /* update min/maxusedidx */
      realarray->minusedidx = MIN(realarray->minusedidx, idx);
      realarray->maxusedidx = MAX(realarray->maxusedidx, idx);
   }
   else if( idx >= realarray->firstidx && idx < realarray->firstidx + realarray->valssize )
   {
      /* set the array value of the index to zero */
      realarray->vals[idx - realarray->firstidx] = 0.0;
 
      /* check, if we can tighten the min/maxusedidx */
      if( idx == realarray->minusedidx )
      {
         assert(realarray->maxusedidx >= 0);
         assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
         do
         {
            realarray->minusedidx++;
         }
         while( realarray->minusedidx <= realarray->maxusedidx
            && realarray->vals[realarray->minusedidx - realarray->firstidx] == 0.0 );
 
         if( realarray->minusedidx > realarray->maxusedidx )
         {
            realarray->minusedidx = INT_MAX;
            realarray->maxusedidx = INT_MIN;
         }
      }
      else if( idx == realarray->maxusedidx )
      {
         assert(realarray->minusedidx >= 0);
         assert(realarray->minusedidx < realarray->maxusedidx);
         assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
         do
         {
            realarray->maxusedidx--;
            assert(realarray->minusedidx <= realarray->maxusedidx);
         }
         while( realarray->vals[realarray->maxusedidx - realarray->firstidx] == 0.0 );
      }
   }
 
   return SCIP_OKAY;
}
 
/** increases value of entry in dynamic array */
SCIP_RETCODE SCIPrealarrayIncVal(
   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to increase value for */
   SCIP_Real             incval              /**< value to increase array index */
   )
{
   SCIP_Real oldval;
 
   oldval = SCIPrealarrayGetVal(realarray, idx);
   if( oldval != SCIP_INVALID ) /*lint !e777*/
      return SCIPrealarraySetVal(realarray, arraygrowinit, arraygrowfac, idx, oldval + incval);
   else
      return SCIP_OKAY;
}
 
/** returns the minimal index of all stored non-zero elements */
int SCIPrealarrayGetMinIdx(
   SCIP_REALARRAY*       realarray           /**< dynamic real array */
   )
{
   assert(realarray != NULL);
 
   return realarray->minusedidx;
}
 
/** returns the maximal index of all stored non-zero elements */
int SCIPrealarrayGetMaxIdx(
   SCIP_REALARRAY*       realarray           /**< dynamic real array */
   )
{
   assert(realarray != NULL);
 
   return realarray->maxusedidx;
}
 
/** creates a dynamic array of int values */
SCIP_RETCODE SCIPintarrayCreate(
   SCIP_INTARRAY**       intarray,           /**< pointer to store the int array */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   assert(intarray != NULL);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, intarray) );
   (*intarray)->blkmem = blkmem;
   (*intarray)->vals = NULL;
   (*intarray)->valssize = 0;
   (*intarray)->firstidx = -1;
   (*intarray)->minusedidx = INT_MAX;
   (*intarray)->maxusedidx = INT_MIN;
 
   return SCIP_OKAY;
}
 
/** creates a copy of a dynamic array of int values */
SCIP_RETCODE SCIPintarrayCopy(
   SCIP_INTARRAY**       intarray,           /**< pointer to store the copied int array */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_INTARRAY*        sourceintarray      /**< dynamic int array to copy */
   )
{
   assert(intarray != NULL);
   assert(sourceintarray != NULL);
 
   SCIP_CALL( SCIPintarrayCreate(intarray, blkmem) );
   if( sourceintarray->valssize > 0 )
   {
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*intarray)->vals, sourceintarray->vals, sourceintarray->valssize) );
   }
   (*intarray)->valssize = sourceintarray->valssize;
   (*intarray)->firstidx = sourceintarray->firstidx;
   (*intarray)->minusedidx = sourceintarray->minusedidx;
   (*intarray)->maxusedidx = sourceintarray->maxusedidx;
 
   return SCIP_OKAY;
}
 
/** frees a dynamic array of int values */
SCIP_RETCODE SCIPintarrayFree(
   SCIP_INTARRAY**       intarray            /**< pointer to the int array */
   )
{
   assert(intarray != NULL);
   assert(*intarray != NULL);
 
   BMSfreeBlockMemoryArrayNull((*intarray)->blkmem, &(*intarray)->vals, (*intarray)->valssize);
   BMSfreeBlockMemory((*intarray)->blkmem, intarray);
 
   return SCIP_OKAY;
}
 
/** extends dynamic array to be able to store indices from minidx to maxidx */
SCIP_RETCODE SCIPintarrayExtend(
   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   minidx,             /**< smallest index to allocate storage for */
   int                   maxidx              /**< largest index to allocate storage for */
   )
{
   int nused;
   int nfree;
   int newfirstidx;
   int i;
 
   assert(intarray != NULL);
   assert(intarray->minusedidx == INT_MAX || intarray->firstidx >= 0);
   assert(intarray->maxusedidx == INT_MIN || intarray->firstidx >= 0);
   assert(intarray->minusedidx == INT_MAX || intarray->minusedidx >= intarray->firstidx);
   assert(intarray->maxusedidx == INT_MIN || intarray->maxusedidx < intarray->firstidx + intarray->valssize);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   minidx = MIN(minidx, intarray->minusedidx);
   maxidx = MAX(maxidx, intarray->maxusedidx);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   SCIPdebugMessage("extending intarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
      (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, minidx, maxidx);
 
   /* check, whether we have to allocate additional memory, or shift the array */
   nused = maxidx - minidx + 1;
   if( nused > intarray->valssize )
   {
      int* newvals;
      int newvalssize;
 
      /* allocate new memory storage */
      newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
      SCIP_ALLOC( BMSallocBlockMemoryArray(intarray->blkmem, &newvals, newvalssize) );
      nfree = newvalssize - nused;
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + newvalssize);
 
      /* initialize memory array by copying old values and setting new values to zero */
      if( intarray->firstidx != -1 )
      {
         for( i = 0; i < intarray->minusedidx - newfirstidx; ++i )
            newvals[i] = 0;
 
         /* check for possible overflow or negative value */
         assert(intarray->maxusedidx - intarray->minusedidx + 1 > 0);
 
         BMScopyMemoryArray(&newvals[intarray->minusedidx - newfirstidx],
            &intarray->vals[intarray->minusedidx - intarray->firstidx],
            intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866 !e776*/
         for( i = intarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
            newvals[i] = 0;
      }
      else
      {
         for( i = 0; i < newvalssize; ++i )
            newvals[i] = 0;
      }
 
      /* free old memory storage, and set the new array parameters */
      BMSfreeBlockMemoryArrayNull(intarray->blkmem, &intarray->vals, intarray->valssize);
      intarray->vals = newvals;
      intarray->valssize = newvalssize;
      intarray->firstidx = newfirstidx;
   }
   else if( intarray->firstidx == -1 )
   {
      /* a sufficiently large memory storage exists, but it was cleared */
      nfree = intarray->valssize - nused;
      assert(nfree >= 0);
      intarray->firstidx = minidx - nfree/2;
      assert(intarray->firstidx <= minidx);
      assert(maxidx < intarray->firstidx + intarray->valssize);
#ifndef NDEBUG
      for( i = 0; i < intarray->valssize; ++i )
         assert(intarray->vals[i] == 0);
#endif
   }
   else if( minidx < intarray->firstidx )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the right */
      nfree = intarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + intarray->valssize);
 
      if( intarray->minusedidx <= intarray->maxusedidx )
      {
         int shift;
 
         assert(intarray->firstidx <= intarray->minusedidx);
         assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
 
         /* shift used part of array to the right */
         shift = intarray->firstidx - newfirstidx;
         assert(shift > 0);
         for( i = intarray->maxusedidx - intarray->firstidx; i >= intarray->minusedidx - intarray->firstidx; --i )
         {
            assert(0 <= i + shift && i + shift < intarray->valssize);
            intarray->vals[i + shift] = intarray->vals[i];
         }
         /* clear the formerly used head of the array */
         for( i = 0; i < shift; ++i )
            intarray->vals[intarray->minusedidx - intarray->firstidx + i] = 0;
      }
      intarray->firstidx = newfirstidx;
   }
   else if( maxidx >= intarray->firstidx + intarray->valssize )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the left */
      nfree = intarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + intarray->valssize);
 
      if( intarray->minusedidx <= intarray->maxusedidx )
      {
         int shift;
 
         assert(intarray->firstidx <= intarray->minusedidx);
         assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
 
         /* shift used part of array to the left */
         shift = newfirstidx - intarray->firstidx;
         assert(shift > 0);
         for( i = intarray->minusedidx - intarray->firstidx; i <= intarray->maxusedidx - intarray->firstidx; ++i )
         {
            assert(0 <= i - shift && i - shift < intarray->valssize);
            intarray->vals[i - shift] = intarray->vals[i];
         }
         /* clear the formerly used tail of the array */
         for( i = 0; i < shift; ++i )
            intarray->vals[intarray->maxusedidx - intarray->firstidx - i] = 0;
      }
      intarray->firstidx = newfirstidx;
   }
 
   assert(minidx >= intarray->firstidx);
   assert(maxidx < intarray->firstidx + intarray->valssize);
 
   return SCIP_OKAY;
}
 
/** clears a dynamic int array */
SCIP_RETCODE SCIPintarrayClear(
   SCIP_INTARRAY*        intarray            /**< dynamic int array */
   )
{
   assert(intarray != NULL);
 
   SCIPdebugMessage("clearing intarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
      (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx);
 
   if( intarray->minusedidx <= intarray->maxusedidx )
   {
      assert(intarray->firstidx <= intarray->minusedidx);
      assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
      assert(intarray->firstidx != -1);
      assert(intarray->valssize > 0);
 
      /* clear the used part of array */
      BMSclearMemoryArray(&intarray->vals[intarray->minusedidx - intarray->firstidx],
         intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866*/
 
      /* mark the array cleared */
      intarray->minusedidx = INT_MAX;
      intarray->maxusedidx = INT_MIN;
   }
   assert(intarray->minusedidx == INT_MAX);
   assert(intarray->maxusedidx == INT_MIN);
 
   return SCIP_OKAY;
}
 
/** gets value of entry in dynamic array */
int SCIPintarrayGetVal(
   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
   int                   idx                 /**< array index to get value for */
   )
{
   assert(intarray != NULL);
   assert(idx >= 0);
 
   if( idx < intarray->minusedidx || idx > intarray->maxusedidx )
      return 0;
   else
   {
      assert(intarray->vals != NULL);
      assert(idx - intarray->firstidx >= 0);
      assert(idx - intarray->firstidx < intarray->valssize);
 
      return intarray->vals[idx - intarray->firstidx];
   }
}
 
/** sets value of entry in dynamic array */
SCIP_RETCODE SCIPintarraySetVal(
   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to set value for */
   int                   val                 /**< value to set array index to */
   )
{
   assert(intarray != NULL);
   assert(idx >= 0);
 
   SCIPdebugMessage("setting intarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %d\n",
      (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, idx, val);
 
   if( val != 0 )
   {
      /* extend array to be able to store the index */
      SCIP_CALL( SCIPintarrayExtend(intarray, arraygrowinit, arraygrowfac, idx, idx) );
      assert(idx >= intarray->firstidx);
      assert(idx < intarray->firstidx + intarray->valssize);
 
      /* set the array value of the index */
      intarray->vals[idx - intarray->firstidx] = val;
 
      /* update min/maxusedidx */
      intarray->minusedidx = MIN(intarray->minusedidx, idx);
      intarray->maxusedidx = MAX(intarray->maxusedidx, idx);
   }
   else if( idx >= intarray->firstidx && idx < intarray->firstidx + intarray->valssize )
   {
      /* set the array value of the index to zero */
      intarray->vals[idx - intarray->firstidx] = 0;
 
      /* check, if we can tighten the min/maxusedidx */
      if( idx == intarray->minusedidx )
      {
         assert(intarray->maxusedidx >= 0);
         assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
         do
         {
            intarray->minusedidx++;
         }
         while( intarray->minusedidx <= intarray->maxusedidx
            && intarray->vals[intarray->minusedidx - intarray->firstidx] == 0 );
         if( intarray->minusedidx > intarray->maxusedidx )
         {
            intarray->minusedidx = INT_MAX;
            intarray->maxusedidx = INT_MIN;
         }
      }
      else if( idx == intarray->maxusedidx )
      {
         assert(intarray->minusedidx >= 0);
         assert(intarray->minusedidx < intarray->maxusedidx);
         assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
         do
         {
            intarray->maxusedidx--;
            assert(intarray->minusedidx <= intarray->maxusedidx);
         }
         while( intarray->vals[intarray->maxusedidx - intarray->firstidx] == 0 );
      }
   }
 
   return SCIP_OKAY;
}
 
/** increases value of entry in dynamic array */
SCIP_RETCODE SCIPintarrayIncVal(
   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to increase value for */
   int                   incval              /**< value to increase array index */
   )
{
   return SCIPintarraySetVal(intarray, arraygrowinit, arraygrowfac, idx, SCIPintarrayGetVal(intarray, idx) + incval);
}
 
/** returns the minimal index of all stored non-zero elements */
int SCIPintarrayGetMinIdx(
   SCIP_INTARRAY*        intarray            /**< dynamic int array */
   )
{
   assert(intarray != NULL);
 
   return intarray->minusedidx;
}
 
/** returns the maximal index of all stored non-zero elements */
int SCIPintarrayGetMaxIdx(
   SCIP_INTARRAY*        intarray            /**< dynamic int array */
   )
{
   assert(intarray != NULL);
 
   return intarray->maxusedidx;
}
 
 
/** creates a dynamic array of bool values */
SCIP_RETCODE SCIPboolarrayCreate(
   SCIP_BOOLARRAY**      boolarray,          /**< pointer to store the bool array */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   assert(boolarray != NULL);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, boolarray) );
   (*boolarray)->blkmem = blkmem;
   (*boolarray)->vals = NULL;
   (*boolarray)->valssize = 0;
   (*boolarray)->firstidx = -1;
   (*boolarray)->minusedidx = INT_MAX;
   (*boolarray)->maxusedidx = INT_MIN;
 
   return SCIP_OKAY;
}
 
/** creates a copy of a dynamic array of bool values */
SCIP_RETCODE SCIPboolarrayCopy(
   SCIP_BOOLARRAY**      boolarray,          /**< pointer to store the copied bool array */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_BOOLARRAY*       sourceboolarray     /**< dynamic bool array to copy */
   )
{
   assert(boolarray != NULL);
   assert(sourceboolarray != NULL);
 
   SCIP_CALL( SCIPboolarrayCreate(boolarray, blkmem) );
   if( sourceboolarray->valssize > 0 )
   {
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*boolarray)->vals, sourceboolarray->vals, \
                     sourceboolarray->valssize) );
   }
   (*boolarray)->valssize = sourceboolarray->valssize;
   (*boolarray)->firstidx = sourceboolarray->firstidx;
   (*boolarray)->minusedidx = sourceboolarray->minusedidx;
   (*boolarray)->maxusedidx = sourceboolarray->maxusedidx;
 
   return SCIP_OKAY;
}
 
/** frees a dynamic array of bool values */
SCIP_RETCODE SCIPboolarrayFree(
   SCIP_BOOLARRAY**      boolarray           /**< pointer to the bool array */
   )
{
   assert(boolarray != NULL);
   assert(*boolarray != NULL);
 
   BMSfreeBlockMemoryArrayNull((*boolarray)->blkmem, &(*boolarray)->vals, (*boolarray)->valssize);
   BMSfreeBlockMemory((*boolarray)->blkmem, boolarray);
 
   return SCIP_OKAY;
}
 
/** extends dynamic array to be able to store indices from minidx to maxidx */
SCIP_RETCODE SCIPboolarrayExtend(
   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   minidx,             /**< smallest index to allocate storage for */
   int                   maxidx              /**< largest index to allocate storage for */
   )
{
   int nused;
   int nfree;
   int newfirstidx;
   int i;
 
   assert(boolarray != NULL);
   assert(boolarray->minusedidx == INT_MAX || boolarray->firstidx >= 0);
   assert(boolarray->maxusedidx == INT_MIN || boolarray->firstidx >= 0);
   assert(boolarray->minusedidx == INT_MAX || boolarray->minusedidx >= boolarray->firstidx);
   assert(boolarray->maxusedidx == INT_MIN || boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   minidx = MIN(minidx, boolarray->minusedidx);
   maxidx = MAX(maxidx, boolarray->maxusedidx);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   SCIPdebugMessage("extending boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
      (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, minidx, maxidx);
 
   /* check, whether we have to allocate additional memory, or shift the array */
   nused = maxidx - minidx + 1;
   if( nused > boolarray->valssize )
   {
      SCIP_Bool* newvals;
      int newvalssize;
 
      /* allocate new memory storage */
      newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
      SCIP_ALLOC( BMSallocBlockMemoryArray(boolarray->blkmem, &newvals, newvalssize) );
      nfree = newvalssize - nused;
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + newvalssize);
 
      /* initialize memory array by copying old values and setting new values to zero */
      if( boolarray->firstidx != -1 )
      {
         for( i = 0; i < boolarray->minusedidx - newfirstidx; ++i )
            newvals[i] = FALSE;
 
         /* check for possible overflow or negative value */
         assert(boolarray->maxusedidx - boolarray->minusedidx + 1 > 0);
 
         BMScopyMemoryArray(&newvals[boolarray->minusedidx - newfirstidx],
            &boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
            boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866 !e776*/
         for( i = boolarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
            newvals[i] = FALSE;
      }
      else
      {
         for( i = 0; i < newvalssize; ++i )
            newvals[i] = FALSE;
      }
 
      /* free old memory storage, and set the new array parameters */
      BMSfreeBlockMemoryArrayNull(boolarray->blkmem, &boolarray->vals, boolarray->valssize);
      boolarray->vals = newvals;
      boolarray->valssize = newvalssize;
      boolarray->firstidx = newfirstidx;
   }
   else if( boolarray->firstidx == -1 )
   {
      /* a sufficiently large memory storage exists, but it was cleared */
      nfree = boolarray->valssize - nused;
      assert(nfree >= 0);
      boolarray->firstidx = minidx - nfree/2;
      assert(boolarray->firstidx <= minidx);
      assert(maxidx < boolarray->firstidx + boolarray->valssize);
#ifndef NDEBUG
      for( i = 0; i < boolarray->valssize; ++i )
         assert(boolarray->vals[i] == FALSE);
#endif
   }
   else if( minidx < boolarray->firstidx )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the right */
      nfree = boolarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + boolarray->valssize);
 
      if( boolarray->minusedidx <= boolarray->maxusedidx )
      {
         int shift;
 
         assert(boolarray->firstidx <= boolarray->minusedidx);
         assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
 
         /* shift used part of array to the right */
         shift = boolarray->firstidx - newfirstidx;
         assert(shift > 0);
         for( i = boolarray->maxusedidx - boolarray->firstidx; i >= boolarray->minusedidx - boolarray->firstidx; --i )
         {
            assert(0 <= i + shift && i + shift < boolarray->valssize);
            boolarray->vals[i + shift] = boolarray->vals[i];
         }
         /* clear the formerly used head of the array */
         for( i = 0; i < shift; ++i )
            boolarray->vals[boolarray->minusedidx - boolarray->firstidx + i] = FALSE;
      }
      boolarray->firstidx = newfirstidx;
   }
   else if( maxidx >= boolarray->firstidx + boolarray->valssize )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the left */
      nfree = boolarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + boolarray->valssize);
 
      if( boolarray->minusedidx <= boolarray->maxusedidx )
      {
         int shift;
 
         assert(boolarray->firstidx <= boolarray->minusedidx);
         assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
 
         /* shift used part of array to the left */
         shift = newfirstidx - boolarray->firstidx;
         assert(shift > 0);
 
         assert(0 <= boolarray->minusedidx - boolarray->firstidx - shift);
         assert(boolarray->maxusedidx - boolarray->firstidx - shift < boolarray->valssize);
         BMSmoveMemoryArray(&(boolarray->vals[boolarray->minusedidx - boolarray->firstidx - shift]),
            &(boolarray->vals[boolarray->minusedidx - boolarray->firstidx]),
            boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
 
         /* clear the formerly used tail of the array */
         for( i = 0; i < shift; ++i )
            boolarray->vals[boolarray->maxusedidx - boolarray->firstidx - i] = FALSE;
      }
      boolarray->firstidx = newfirstidx;
   }
 
   assert(minidx >= boolarray->firstidx);
   assert(maxidx < boolarray->firstidx + boolarray->valssize);
 
   return SCIP_OKAY;
}
 
/** clears a dynamic bool array */
SCIP_RETCODE SCIPboolarrayClear(
   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
   )
{
   assert(boolarray != NULL);
 
   SCIPdebugMessage("clearing boolarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
      (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx);
 
   if( boolarray->minusedidx <= boolarray->maxusedidx )
   {
      assert(boolarray->firstidx <= boolarray->minusedidx);
      assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
      assert(boolarray->firstidx != -1);
      assert(boolarray->valssize > 0);
 
      /* clear the used part of array */
      BMSclearMemoryArray(&boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
         boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
 
      /* mark the array cleared */
      boolarray->minusedidx = INT_MAX;
      boolarray->maxusedidx = INT_MIN;
   }
   assert(boolarray->minusedidx == INT_MAX);
   assert(boolarray->maxusedidx == INT_MIN);
 
   return SCIP_OKAY;
}
 
/** gets value of entry in dynamic array */
SCIP_Bool SCIPboolarrayGetVal(
   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
   int                   idx                 /**< array index to get value for */
   )
{
   assert(boolarray != NULL);
   assert(idx >= 0);
 
   if( idx < boolarray->minusedidx || idx > boolarray->maxusedidx )
      return FALSE;
   else
   {
      assert(boolarray->vals != NULL);
      assert(idx - boolarray->firstidx >= 0);
      assert(idx - boolarray->firstidx < boolarray->valssize);
 
      return boolarray->vals[idx - boolarray->firstidx];
   }
}
 
/** sets value of entry in dynamic array */
SCIP_RETCODE SCIPboolarraySetVal(
   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to set value for */
   SCIP_Bool             val                 /**< value to set array index to */
   )
{
   assert(boolarray != NULL);
   assert(idx >= 0);
 
   SCIPdebugMessage("setting boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %u\n",
      (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, idx, val);
 
   if( val != FALSE )
   {
      /* extend array to be able to store the index */
      SCIP_CALL( SCIPboolarrayExtend(boolarray, arraygrowinit, arraygrowfac, idx, idx) );
      assert(idx >= boolarray->firstidx);
      assert(idx < boolarray->firstidx + boolarray->valssize);
 
      /* set the array value of the index */
      boolarray->vals[idx - boolarray->firstidx] = val;
 
      /* update min/maxusedidx */
      boolarray->minusedidx = MIN(boolarray->minusedidx, idx);
      boolarray->maxusedidx = MAX(boolarray->maxusedidx, idx);
   }
   else if( idx >= boolarray->firstidx && idx < boolarray->firstidx + boolarray->valssize )
   {
      /* set the array value of the index to zero */
      boolarray->vals[idx - boolarray->firstidx] = FALSE;
 
      /* check, if we can tighten the min/maxusedidx */
      if( idx == boolarray->minusedidx )
      {
         assert(boolarray->maxusedidx >= 0);
         assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
         do
         {
            boolarray->minusedidx++;
         }
         while( boolarray->minusedidx <= boolarray->maxusedidx
            && boolarray->vals[boolarray->minusedidx - boolarray->firstidx] == FALSE );
         if( boolarray->minusedidx > boolarray->maxusedidx )
         {
            boolarray->minusedidx = INT_MAX;
            boolarray->maxusedidx = INT_MIN;
         }
      }
      else if( idx == boolarray->maxusedidx )
      {
         assert(boolarray->minusedidx >= 0);
         assert(boolarray->minusedidx < boolarray->maxusedidx);
         assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
         do
         {
            boolarray->maxusedidx--;
            assert(boolarray->minusedidx <= boolarray->maxusedidx);
         }
         while( boolarray->vals[boolarray->maxusedidx - boolarray->firstidx] == FALSE );
      }
   }
 
   return SCIP_OKAY;
}
 
/** returns the minimal index of all stored non-zero elements */
int SCIPboolarrayGetMinIdx(
   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
   )
{
   assert(boolarray != NULL);
 
   return boolarray->minusedidx;
}
 
/** returns the maximal index of all stored non-zero elements */
int SCIPboolarrayGetMaxIdx(
   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
   )
{
   assert(boolarray != NULL);
 
   return boolarray->maxusedidx;
}
 
 
/** creates a dynamic array of pointer values */
SCIP_RETCODE SCIPptrarrayCreate(
   SCIP_PTRARRAY**       ptrarray,           /**< pointer to store the ptr array */
   BMS_BLKMEM*           blkmem              /**< block memory */
   )
{
   assert(ptrarray != NULL);
   assert(blkmem != NULL);
 
   SCIP_ALLOC( BMSallocBlockMemory(blkmem, ptrarray) );
   (*ptrarray)->blkmem = blkmem;
   (*ptrarray)->vals = NULL;
   (*ptrarray)->valssize = 0;
   (*ptrarray)->firstidx = -1;
   (*ptrarray)->minusedidx = INT_MAX;
   (*ptrarray)->maxusedidx = INT_MIN;
 
   return SCIP_OKAY;
}
 
/** creates a copy of a dynamic array of pointer values */
SCIP_RETCODE SCIPptrarrayCopy(
   SCIP_PTRARRAY**       ptrarray,           /**< pointer to store the copied ptr array */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_PTRARRAY*        sourceptrarray      /**< dynamic ptr array to copy */
   )
{
   assert(ptrarray != NULL);
   assert(sourceptrarray != NULL);
 
   SCIP_CALL( SCIPptrarrayCreate(ptrarray, blkmem) );
   if( sourceptrarray->valssize > 0 )
   {
      SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*ptrarray)->vals, sourceptrarray->vals, sourceptrarray->valssize) );
   }
   (*ptrarray)->valssize = sourceptrarray->valssize;
   (*ptrarray)->firstidx = sourceptrarray->firstidx;
   (*ptrarray)->minusedidx = sourceptrarray->minusedidx;
   (*ptrarray)->maxusedidx = sourceptrarray->maxusedidx;
 
   return SCIP_OKAY;
}
 
/** frees a dynamic array of pointer values */
SCIP_RETCODE SCIPptrarrayFree(
   SCIP_PTRARRAY**       ptrarray            /**< pointer to the ptr array */
   )
{
   assert(ptrarray != NULL);
   assert(*ptrarray != NULL);
 
   BMSfreeBlockMemoryArrayNull((*ptrarray)->blkmem, &(*ptrarray)->vals, (*ptrarray)->valssize);
   BMSfreeBlockMemory((*ptrarray)->blkmem, ptrarray);
 
   return SCIP_OKAY;
}
 
/** extends dynamic array to be able to store indices from minidx to maxidx */
SCIP_RETCODE SCIPptrarrayExtend(
   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   minidx,             /**< smallest index to allocate storage for */
   int                   maxidx              /**< largest index to allocate storage for */
   )
{
   int nused;
   int nfree;
   int newfirstidx;
   int i;
 
   assert(ptrarray != NULL);
   assert(ptrarray->minusedidx == INT_MAX || ptrarray->firstidx >= 0);
   assert(ptrarray->maxusedidx == INT_MIN || ptrarray->firstidx >= 0);
   assert(ptrarray->minusedidx == INT_MAX || ptrarray->minusedidx >= ptrarray->firstidx);
   assert(ptrarray->maxusedidx == INT_MIN || ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   minidx = MIN(minidx, ptrarray->minusedidx);
   maxidx = MAX(maxidx, ptrarray->maxusedidx);
   assert(0 <= minidx);
   assert(minidx <= maxidx);
 
   SCIPdebugMessage("extending ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
      (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, minidx, maxidx);
 
   /* check, whether we have to allocate additional memory, or shift the array */
   nused = maxidx - minidx + 1;
   if( nused > ptrarray->valssize )
   {
      void** newvals;
      int newvalssize;
 
      /* allocate new memory storage */
      newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
      SCIP_ALLOC( BMSallocBlockMemoryArray(ptrarray->blkmem, &newvals, newvalssize) );
      nfree = newvalssize - nused;
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + newvalssize);
 
      /* initialize memory array by copying old values and setting new values to zero */
      if( ptrarray->firstidx != -1 )
      {
         for( i = 0; i < ptrarray->minusedidx - newfirstidx; ++i )
            newvals[i] = NULL;
 
         /* check for possible overflow or negative value */
         assert(ptrarray->maxusedidx - ptrarray->minusedidx + 1 > 0);
 
         BMScopyMemoryArray(&newvals[ptrarray->minusedidx - newfirstidx],
            &(ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx]),
            ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866 !e776*/
         for( i = ptrarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
            newvals[i] = NULL;
      }
      else
      {
         for( i = 0; i < newvalssize; ++i )
            newvals[i] = NULL;
      }
 
      /* free old memory storage, and set the new array parameters */
      BMSfreeBlockMemoryArrayNull(ptrarray->blkmem, &ptrarray->vals, ptrarray->valssize);
      ptrarray->vals = newvals;
      ptrarray->valssize = newvalssize;
      ptrarray->firstidx = newfirstidx;
   }
   else if( ptrarray->firstidx == -1 )
   {
      /* a sufficiently large memory storage exists, but it was cleared */
      nfree = ptrarray->valssize - nused;
      assert(nfree >= 0);
      ptrarray->firstidx = minidx - nfree/2;
      assert(ptrarray->firstidx <= minidx);
      assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
#ifndef NDEBUG
      for( i = 0; i < ptrarray->valssize; ++i )
         assert(ptrarray->vals[i] == NULL);
#endif
   }
   else if( minidx < ptrarray->firstidx )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the right */
      nfree = ptrarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + ptrarray->valssize);
 
      if( ptrarray->minusedidx <= ptrarray->maxusedidx )
      {
         int shift;
 
         assert(ptrarray->firstidx <= ptrarray->minusedidx);
         assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
 
         /* shift used part of array to the right */
         shift = ptrarray->firstidx - newfirstidx;
         assert(shift > 0);
         for( i = ptrarray->maxusedidx - ptrarray->firstidx; i >= ptrarray->minusedidx - ptrarray->firstidx; --i )
         {
            assert(0 <= i + shift && i + shift < ptrarray->valssize);
            ptrarray->vals[i + shift] = ptrarray->vals[i];
         }
         /* clear the formerly used head of the array */
         for( i = 0; i < shift; ++i )
            ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx + i] = NULL;
      }
      ptrarray->firstidx = newfirstidx;
   }
   else if( maxidx >= ptrarray->firstidx + ptrarray->valssize )
   {
      /* a sufficiently large memory storage exists, but it has to be shifted to the left */
      nfree = ptrarray->valssize - nused;
      assert(nfree >= 0);
      newfirstidx = minidx - nfree/2;
      newfirstidx = MAX(newfirstidx, 0);
      assert(newfirstidx <= minidx);
      assert(maxidx < newfirstidx + ptrarray->valssize);
 
      if( ptrarray->minusedidx <= ptrarray->maxusedidx )
      {
         int shift;
 
         assert(ptrarray->firstidx <= ptrarray->minusedidx);
         assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
 
         /* shift used part of array to the left */
         shift = newfirstidx - ptrarray->firstidx;
         assert(shift > 0);
         for( i = ptrarray->minusedidx - ptrarray->firstidx; i <= ptrarray->maxusedidx - ptrarray->firstidx; ++i )
         {
            assert(0 <= i - shift && i - shift < ptrarray->valssize);
            ptrarray->vals[i - shift] = ptrarray->vals[i];
         }
         /* clear the formerly used tail of the array */
         for( i = 0; i < shift; ++i )
            ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx - i] = NULL;
      }
      ptrarray->firstidx = newfirstidx;
   }
 
   assert(minidx >= ptrarray->firstidx);
   assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
 
   return SCIP_OKAY;
}
 
/** clears a dynamic pointer array */
SCIP_RETCODE SCIPptrarrayClear(
   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
   )
{
   assert(ptrarray != NULL);
 
   SCIPdebugMessage("clearing ptrarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
      (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx);
 
   if( ptrarray->minusedidx <= ptrarray->maxusedidx )
   {
      assert(ptrarray->firstidx <= ptrarray->minusedidx);
      assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
      assert(ptrarray->firstidx != -1);
      assert(ptrarray->valssize > 0);
 
      /* clear the used part of array */
      BMSclearMemoryArray(&ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx],
         ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866*/
 
      /* mark the array cleared */
      ptrarray->minusedidx = INT_MAX;
      ptrarray->maxusedidx = INT_MIN;
   }
   assert(ptrarray->minusedidx == INT_MAX);
   assert(ptrarray->maxusedidx == INT_MIN);
 
   return SCIP_OKAY;
}
 
/** gets value of entry in dynamic array */
void* SCIPptrarrayGetVal(
   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
   int                   idx                 /**< array index to get value for */
   )
{
   assert(ptrarray != NULL);
   assert(idx >= 0);
 
   if( idx < ptrarray->minusedidx || idx > ptrarray->maxusedidx )
      return NULL;
   else
   {
      assert(ptrarray->vals != NULL);
      assert(idx - ptrarray->firstidx >= 0);
      assert(idx - ptrarray->firstidx < ptrarray->valssize);
 
      return ptrarray->vals[idx - ptrarray->firstidx];
   }
}
 
/** sets value of entry in dynamic array */
SCIP_RETCODE SCIPptrarraySetVal(
   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
   int                   arraygrowinit,      /**< initial size of array */
   SCIP_Real             arraygrowfac,       /**< growing factor of array */
   int                   idx,                /**< array index to set value for */
   void*                 val                 /**< value to set array index to */
   )
{
   assert(ptrarray != NULL);
   assert(idx >= 0);
 
   SCIPdebugMessage("setting ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %p\n",
      (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, idx, val);
 
   if( val != NULL )
   {
      /* extend array to be able to store the index */
      SCIP_CALL( SCIPptrarrayExtend(ptrarray, arraygrowinit, arraygrowfac, idx, idx) );
      assert(idx >= ptrarray->firstidx);
      assert(idx < ptrarray->firstidx + ptrarray->valssize);
 
      /* set the array value of the index */
      ptrarray->vals[idx - ptrarray->firstidx] = val;
 
      /* update min/maxusedidx */
      ptrarray->minusedidx = MIN(ptrarray->minusedidx, idx);
      ptrarray->maxusedidx = MAX(ptrarray->maxusedidx, idx);
   }
   else if( idx >= ptrarray->firstidx && idx < ptrarray->firstidx + ptrarray->valssize )
   {
      /* set the array value of the index to zero */
      ptrarray->vals[idx - ptrarray->firstidx] = NULL;
 
      /* check, if we can tighten the min/maxusedidx */
      if( idx == ptrarray->minusedidx )
      {
         assert(ptrarray->maxusedidx >= 0);
         assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
         do
         {
            ptrarray->minusedidx++;
         }
         while( ptrarray->minusedidx <= ptrarray->maxusedidx
            && ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx] == NULL );
         if( ptrarray->minusedidx > ptrarray->maxusedidx )
         {
            ptrarray->minusedidx = INT_MAX;
            ptrarray->maxusedidx = INT_MIN;
         }
      }
      else if( idx == ptrarray->maxusedidx )