1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   pub_misc.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public data structures and miscellaneous methods
28   	 * @author Tobias Achterberg
29   	 * @author Gerald Gamrath
30   	 * @author Stefan Heinz
31   	 * @author Gregor Hendel
32   	 * @author Michael Winkler
33   	 * @author Kati Wolter
34   	 *
35   	 * This file contains a bunch of data structures and miscellaneous methods:
36   	 *
37   	 * - \ref DataStructures "Data structures"
38   	 * - \ref MiscellaneousMethods "Miscellaneous Methods"
39   	 */
40   	
41   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42   	
43   	#ifndef __SCIP_PUB_MISC_H__
44   	#define __SCIP_PUB_MISC_H__
45   	
46   	/* on SunOS, the function finite(a) (for the SCIPisFinite macro below) is declared in ieeefp.h */
47   	#ifdef __sun
48   	#include <ieeefp.h>
49   	#endif
50   	#include <math.h>
51   	
52   	#include "scip/def.h"
53   	#include "blockmemshell/memory.h"
54   	#include "scip/type_retcode.h"
55   	#include "scip/type_misc.h"
56   	#include "scip/type_message.h"
57   	#include "scip/type_var.h"
58   	#include "scip/pub_misc_select.h"
59   	#include "scip/pub_misc_sort.h"
60   	#include "scip/pub_misc_linear.h"
61   	#include "scip/pub_misc_rowprep.h"
62   	
63   	/* in optimized mode some of the function are handled via defines, for that the structs are needed */
64   	#ifdef NDEBUG
65   	#include "scip/struct_misc.h"
66   	#endif
67   	
68   	#ifdef __cplusplus
69   	extern "C" {
70   	#endif
71   	
72   	/*
73   	 * methods for statistical tests
74   	 */
75   	
76   	/**@defgroup STATISTICALTESTS Statistical tests
77   	 * @ingroup MiscellaneousMethods
78   	 * @brief public methods for statistical tests
79   	 *
80   	 * Below are the public methods for statistical tests inside of \SCIP
81   	 *
82   	 * @{
83   	 */
84   	
85   	/** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */
86   	SCIP_EXPORT
87   	SCIP_Real SCIPstudentTGetCriticalValue(
88   	   SCIP_CONFIDENCELEVEL  clevel,             /**< (one-sided) confidence level */
89   	   int                   df                  /**< degrees of freedom */
90   	   );
91   	
92   	/** compute a t-value for the hypothesis that x and y are from the same population; Assuming that
93   	 *  x and y represent normally distributed random samples with equal variance, the returned value
94   	 *  comes from a Student-T distribution with countx + county - 2 degrees of freedom; this
95   	 *  value can be compared with a critical value (see also SCIPstudentTGetCriticalValue()) at
96   	 *  a predefined confidence level for checking if x and y significantly differ in location
97   	 */
98   	SCIP_EXPORT
99   	SCIP_Real SCIPcomputeTwoSampleTTestValue(
100  	   SCIP_Real             meanx,              /**< the mean of the first distribution */
101  	   SCIP_Real             meany,              /**< the mean of the second distribution */
102  	   SCIP_Real             variancex,          /**< the variance of the x-distribution */
103  	   SCIP_Real             variancey,          /**< the variance of the y-distribution */
104  	   SCIP_Real             countx,             /**< number of samples of x */
105  	   SCIP_Real             county              /**< number of samples of y */
106  	   );
107  	
108  	/** returns the value of the Gauss error function evaluated at a given point */
109  	SCIP_EXPORT
110  	SCIP_Real SCIPerf(
111  	   SCIP_Real             x                   /**< value to evaluate */
112  	   );
113  	
114  	/** get critical value of a standard normal distribution  at a given confidence level */
115  	SCIP_EXPORT
116  	SCIP_Real SCIPnormalGetCriticalValue(
117  	   SCIP_CONFIDENCELEVEL  clevel              /**< (one-sided) confidence level */
118  	   );
119  	
120  	/** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
121  	 *  random variable x takes a value between -infinity and parameter \p value.
122  	 *
123  	 *  The distribution is given by the respective mean and deviation. This implementation
124  	 *  uses the error function erf().
125  	 */
126  	SCIP_EXPORT
127  	SCIP_Real SCIPnormalCDF(
128  	   SCIP_Real             mean,               /**< the mean value of the distribution */
129  	   SCIP_Real             variance,           /**< the square of the deviation of the distribution */
130  	   SCIP_Real             value               /**< the upper limit of the calculated distribution integral */
131  	   );
132  	
133  	/**@} */
134  	
135  	/**@defgroup Regression Linear Regression
136  	 * @ingroup MiscellaneousMethods
137  	 * @brief methods for linear regression
138  	 *
139  	 * Below are the public methods for incremental linear regression of observations pairs \f$(X_i,Y_i), i=1\dots,n\f$
140  	 *
141  	 * @{
142  	 */
143  	
144  	/** returns the number of observations of this regression */
145  	SCIP_EXPORT
146  	int SCIPregressionGetNObservations(
147  	   SCIP_REGRESSION*      regression          /**< regression data structure */
148  	   );
149  	
150  	/** return the current slope of the regression */
151  	SCIP_EXPORT
152  	SCIP_Real SCIPregressionGetSlope(
153  	   SCIP_REGRESSION*      regression          /**< regression data structure */
154  	   );
155  	
156  	/** get the current y-intercept of the regression */
157  	SCIP_EXPORT
158  	SCIP_Real SCIPregressionGetIntercept(
159  	   SCIP_REGRESSION*      regression          /**< regression data structure */
160  	   );
161  	
162  	/** removes an observation (x,y) from the regression */
163  	SCIP_EXPORT
164  	void SCIPregressionRemoveObservation(
165  	   SCIP_REGRESSION*      regression,         /**< regression data structure */
166  	   SCIP_Real             x,                  /**< X of observation */
167  	   SCIP_Real             y                   /**< Y of the observation */
168  	   );
169  	
170  	/** update regression by a new observation (x,y) */
171  	SCIP_EXPORT
172  	void SCIPregressionAddObservation(
173  	   SCIP_REGRESSION*      regression,         /**< regression data structure */
174  	   SCIP_Real             x,                  /**< X of observation */
175  	   SCIP_Real             y                   /**< Y of the observation */
176  	   );
177  	
178  	/** reset regression data structure */
179  	SCIP_EXPORT
180  	void SCIPregressionReset(
181  	   SCIP_REGRESSION*      regression          /**< regression data structure */
182  	   );
183  	
184  	/** creates and resets a regression */
185  	SCIP_EXPORT
186  	SCIP_RETCODE SCIPregressionCreate(
187  	   SCIP_REGRESSION**     regression          /**< regression data structure */
188  	   );
189  	
190  	/** frees a regression */
191  	SCIP_EXPORT
192  	void SCIPregressionFree(
193  	   SCIP_REGRESSION**     regression          /**< regression data structure */
194  	   );
195  	
196  	/**@} */
197  	
198  	/*
199  	 */
200  	
201  	/**@defgroup GMLgraph GML Graphical Printing
202  	 * @ingroup MiscellaneousMethods
203  	 * @brief GML graph printing methods
204  	 *
205  	 * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html
206  	 *
207  	 * @{
208  	 */
209  	
210  	
211  	/** writes a node section to the given graph file */
212  	SCIP_EXPORT
213  	void SCIPgmlWriteNode(
214  	   FILE*                 file,               /**< file to write to */
215  	   unsigned int          id,                 /**< id of the node */
216  	   const char*           label,              /**< label of the node */
217  	   const char*           nodetype,           /**< type of the node, or NULL */
218  	   const char*           fillcolor,          /**< color of the node's interior, or NULL */
219  	   const char*           bordercolor         /**< color of the node's border, or NULL */
220  	   );
221  	
222  	/** writes a node section including weight to the given graph file */
223  	SCIP_EXPORT
224  	void SCIPgmlWriteNodeWeight(
225  	   FILE*                 file,               /**< file to write to */
226  	   unsigned int          id,                 /**< id of the node */
227  	   const char*           label,              /**< label of the node */
228  	   const char*           nodetype,           /**< type of the node, or NULL */
229  	   const char*           fillcolor,          /**< color of the node's interior, or NULL */
230  	   const char*           bordercolor,        /**< color of the node's border, or NULL */
231  	   SCIP_Real             weight              /**< weight of node */
232  	   );
233  	
234  	/** writes an edge section to the given graph file */
235  	SCIP_EXPORT
236  	void SCIPgmlWriteEdge(
237  	   FILE*                 file,               /**< file to write to */
238  	   unsigned int          source,             /**< source node id of the node */
239  	   unsigned int          target,             /**< target node id of the edge */
240  	   const char*           label,              /**< label of the edge, or NULL */
241  	   const char*           color               /**< color of the edge, or NULL */
242  	   );
243  	
244  	/** writes an arc section to the given graph file */
245  	SCIP_EXPORT
246  	void SCIPgmlWriteArc(
247  	   FILE*                 file,               /**< file to write to */
248  	   unsigned int          source,             /**< source node id of the node */
249  	   unsigned int          target,             /**< target node id of the edge */
250  	   const char*           label,              /**< label of the edge, or NULL */
251  	   const char*           color               /**< color of the edge, or NULL */
252  	   );
253  	
254  	/** writes the starting line to a GML graph file, does not open a file */
255  	SCIP_EXPORT
256  	void SCIPgmlWriteOpening(
257  	   FILE*                 file,               /**< file to write to */
258  	   SCIP_Bool             directed            /**< is the graph directed */
259  	   );
260  	
261  	/** writes the ending lines to a GML graph file, does not close a file */
262  	SCIP_EXPORT
263  	void SCIPgmlWriteClosing(
264  	   FILE*                 file                /**< file to close */
265  	   );
266  	
267  	/** writes the opening line to a dot graph file, does not open a file */
268  	SCIP_EXPORT
269  	void SCIPdotWriteOpening(
270  	   FILE*                 file                /**< file to write to */
271  	);
272  	
273  	/** adds a node to the dot graph */
274  	SCIP_EXPORT
275  	void SCIPdotWriteNode(
276  	   FILE*                 file,               /**< file to write to */
277  	   int                   node,               /**< node id */
278  	   const char*           label,              /**< node label */
279  	   const char*           nodetype,           /**< type of the node, or NULL */
280  	   const char*           fillcolor,          /**< color of the node's interior, or NULL */
281  	   const char*           bordercolor         /**< color of the node's border, or NULL */
282  	);
283  	
284  	/** adds an arc (edge) between two nodes in the dot graph */
285  	SCIP_EXPORT
286  	void SCIPdotWriteArc(
287  	   FILE*                 file,               /**< file to write to */
288  	   int                   source,             /**< source node id of the node */
289  	   int                   target,             /**< target node id of the edge */
290  	   const char*           color               /**< color of the edge, or NULL */
291  	);
292  	
293  	/** writes the closing line to a dot graph file, does not close a file */
294  	SCIP_EXPORT
295  	void SCIPdotWriteClosing(
296  	   FILE*                 file                /**< file to write to */
297  	);
298  	
299  	/**@} */
300  	
301  	/*
302  	 * Sparse solution
303  	 */
304  	
305  	/**@defgroup SparseSol Sparse Solution
306  	 * @ingroup DataStructures
307  	 * @brief sparse storage for multiple integer solutions
308  	 *
309  	 * @{
310  	 */
311  	
312  	/** creates a sparse solution */
313  	SCIP_EXPORT
314  	SCIP_RETCODE SCIPsparseSolCreate(
315  	   SCIP_SPARSESOL**      sparsesol,          /**< pointer to store the created sparse solution */
316  	   SCIP_VAR**            vars,               /**< variables in the sparse solution, must not contain continuous variables */
317  	   int                   nvars,              /**< number of variables to store, size of the lower and upper bound arrays */
318  	   SCIP_Bool             cleared             /**< should the lower and upper bound arrays be cleared (entries set to 0) */
319  	   );
320  	
321  	/** frees sparse solution */
322  	SCIP_EXPORT
323  	void SCIPsparseSolFree(
324  	   SCIP_SPARSESOL**      sparsesol           /**< pointer to a sparse solution */
325  	   );
326  	
327  	/** returns the variables in the given sparse solution */
328  	SCIP_EXPORT
329  	SCIP_VAR** SCIPsparseSolGetVars(
330  	   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
331  	   );
332  	
333  	/** returns the number of variables in the given sparse solution */
334  	SCIP_EXPORT
335  	int SCIPsparseSolGetNVars(
336  	   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
337  	   );
338  	
339  	/** returns the the lower bound array for all variables for a given sparse solution */
340  	SCIP_EXPORT
341  	SCIP_Longint* SCIPsparseSolGetLbs(
342  	   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
343  	   );
344  	
345  	/** returns the the upper bound array for all variables for a given sparse solution */
346  	SCIP_EXPORT
347  	SCIP_Longint* SCIPsparseSolGetUbs(
348  	   SCIP_SPARSESOL*       sparsesol           /**< a sparse solution */
349  	   );
350  	
351  	/** constructs the first solution of sparse solution (all variables are set to their lower bound value */
352  	SCIP_EXPORT
353  	void SCIPsparseSolGetFirstSol(
354  	   SCIP_SPARSESOL*       sparsesol,          /**< sparse solutions */
355  	   SCIP_Longint*         sol,                /**< array to store the first solution */
356  	   int                   nvars               /**< number of variables */
357  	   );
358  	
359  	/** constructs the next solution of the sparse solution and return whether there was one more or not */
360  	SCIP_EXPORT
361  	SCIP_Bool SCIPsparseSolGetNextSol(
362  	   SCIP_SPARSESOL*       sparsesol,          /**< sparse solutions */
363  	   SCIP_Longint*         sol,                /**< current solution array which get changed to the next solution */
364  	   int                   nvars               /**< number of variables */
365  	   );
366  	
367  	/**@} */
368  	
369  	
370  	/*
371  	 * Queue
372  	 */
373  	
374  	/**@defgroup Queue Queue
375  	 * @ingroup DataStructures
376  	 * @brief circular FIFO queue
377  	 *
378  	 * @{
379  	 */
380  	
381  	
382  	/** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */
383  	SCIP_EXPORT
384  	SCIP_RETCODE SCIPqueueCreate(
385  	   SCIP_QUEUE**          queue,              /**< pointer to the new queue */
386  	   int                   initsize,           /**< initial number of available element slots */
387  	   SCIP_Real             sizefac             /**< memory growing factor applied, if more element slots are needed */
388  	   );
389  	
390  	
391  	/** frees queue, but not the data elements themselves */
392  	SCIP_EXPORT
393  	void SCIPqueueFree(
394  	   SCIP_QUEUE**          queue               /**< pointer to a queue */
395  	   );
396  	
397  	/** clears the queue, but doesn't free the data elements themselves */
398  	SCIP_EXPORT
399  	void SCIPqueueClear(
400  	   SCIP_QUEUE*           queue               /**< queue */
401  	   );
402  	
403  	/** inserts pointer element at the end of the queue */
404  	SCIP_EXPORT
405  	SCIP_RETCODE SCIPqueueInsert(
406  	   SCIP_QUEUE*           queue,              /**< queue */
407  	   void*                 elem                /**< element to be inserted */
408  	   );
409  	
410  	/** inserts unsigned integer element at the end of the queue */
411  	SCIP_EXPORT
412  	SCIP_RETCODE SCIPqueueInsertUInt(
413  	   SCIP_QUEUE*           queue,              /**< queue */
414  	   unsigned int          elem                /**< element to be inserted */
415  	   );
416  	
417  	/** removes and returns the first element of the queue, or NULL if no element exists */
418  	SCIP_EXPORT
419  	void* SCIPqueueRemove(
420  	   SCIP_QUEUE*           queue               /**< queue */
421  	   );
422  	
423  	/** removes and returns the first unsigned integer element of the queue, or UNIT_MAX if no element exists */
424  	SCIP_EXPORT
425  	unsigned int SCIPqueueRemoveUInt(
426  	   SCIP_QUEUE*           queue               /**< queue */
427  	   );
428  	
429  	/** returns the first element of the queue without removing it, or NULL if no element exists */
430  	SCIP_EXPORT
431  	void* SCIPqueueFirst(
432  	   SCIP_QUEUE*           queue               /**< queue */
433  	   );
434  	
435  	/** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */
436  	SCIP_EXPORT
437  	unsigned int SCIPqueueFirstUInt(
438  	   SCIP_QUEUE*           queue               /**< queue */
439  	   );
440  	
441  	/** returns whether the queue is empty */
442  	SCIP_EXPORT
443  	SCIP_Bool SCIPqueueIsEmpty(
444  	   SCIP_QUEUE*           queue               /**< queue */
445  	   );
446  	
447  	/** returns the number of elements in the queue */
448  	SCIP_EXPORT
449  	int SCIPqueueNElems(
450  	   SCIP_QUEUE*           queue               /**< queue */
451  	   );
452  	
453  	/**@} */
454  	
455  	/*
456  	 * Priority Queue
457  	 */
458  	
459  	/**@defgroup PriorityQueue Priority Queue
460  	 * @ingroup DataStructures
461  	 * @brief priority queue with O(1) access to the minimum element
462  	 *
463  	 * @{
464  	 */
465  	
466  	/** creates priority queue */
467  	SCIP_EXPORT
468  	SCIP_RETCODE SCIPpqueueCreate(
469  	   SCIP_PQUEUE**         pqueue,             /**< pointer to a priority queue */
470  	   int                   initsize,           /**< initial number of available element slots */
471  	   SCIP_Real             sizefac,            /**< memory growing factor applied, if more element slots are needed */
472  	   SCIP_DECL_SORTPTRCOMP((*ptrcomp)),        /**< data element comparator */
473  	   SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) /**< callback to act on position change of elem in priority queue, or NULL */
474  	   );
475  	
476  	/** frees priority queue, but not the data elements themselves */
477  	SCIP_EXPORT
478  	void SCIPpqueueFree(
479  	   SCIP_PQUEUE**         pqueue              /**< pointer to a priority queue */
480  	   );
481  	
482  	/** clears the priority queue, but doesn't free the data elements themselves */
483  	SCIP_EXPORT
484  	void SCIPpqueueClear(
485  	   SCIP_PQUEUE*          pqueue              /**< priority queue */
486  	   );
487  	
488  	/** inserts element into priority queue */
489  	SCIP_EXPORT
490  	SCIP_RETCODE SCIPpqueueInsert(
491  	   SCIP_PQUEUE*          pqueue,             /**< priority queue */
492  	   void*                 elem                /**< element to be inserted */
493  	   );
494  	
495  	/** delete element at specified position, maintaining the heap property */
496  	SCIP_EXPORT
497  	void SCIPpqueueDelPos(
498  	   SCIP_PQUEUE*          pqueue,             /**< priority queue */
499  	   int                   pos                 /**< position of element that should be deleted */
500  	   );
501  	
502  	/** removes and returns best element from the priority queue */
503  	SCIP_EXPORT
504  	void* SCIPpqueueRemove(
505  	   SCIP_PQUEUE*          pqueue              /**< priority queue */
506  	   );
507  	
508  	/** returns the best element of the queue without removing it */
509  	SCIP_EXPORT
510  	void* SCIPpqueueFirst(
511  	   SCIP_PQUEUE*          pqueue              /**< priority queue */
512  	   );
513  	
514  	/** returns the number of elements in the queue */
515  	SCIP_EXPORT
516  	int SCIPpqueueNElems(
517  	   SCIP_PQUEUE*          pqueue              /**< priority queue */
518  	   );
519  	
520  	/** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */
521  	SCIP_EXPORT
522  	void** SCIPpqueueElems(
523  	   SCIP_PQUEUE*          pqueue              /**< priority queue */
524  	   );
525  	
526  	/** return the position of @p elem in the priority queue, or -1 if element is not found */
527  	SCIP_EXPORT
528  	int SCIPpqueueFind(
529  	   SCIP_PQUEUE*          pqueue,             /**< priority queue */
530  	   void*                 elem                /**< element to be inserted */
531  	   );
532  	
533  	/**@} */
534  	
535  	
536  	/*
537  	 * Hash Table
538  	 */
539  	
540  	/**@defgroup HashTable Hash Table
541  	 * @ingroup DataStructures
542  	 * @brief hash table that resolves conflicts by probing
543  	 *
544  	 *@{
545  	 */
546  	
547  	/* fast 2-universal hash functions for two to seven 32bit elements with 32bit output */
548  	
549  	#define SCIPhashSignature64(a)              (UINT64_C(0x8000000000000000)>>((UINT32_C(0x9e3779b9) * ((uint32_t)(a)))>>26))
550  	
551  	#define SCIPhashTwo(a, b)                   ((uint32_t)((((uint32_t)(a) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) )>>32))
552  	
553  	#define SCIPhashThree(a, b, c)            ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
554  	                                                        (uint32_t)(c) * 0xd37e9a1ce2148403ULL)>>32 ))
555  	
556  	#define SCIPhashFour(a, b, c, d)            ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
557  	                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL))>>32 ))
558  	
559  	#define SCIPhashFive(a, b, c, d, e)            ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
560  	                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
561  	                                                           (uint32_t)(e) * 0xf48d4cd331e14327ULL)>>32 ))
562  	
563  	#define SCIPhashSix(a, b, c, d, e, f)            ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
564  	                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
565  	                                                         ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL))>>32 ))
566  	
567  	#define SCIPhashSeven(a, b, c, d, e, f, g)            ((uint32_t)((((uint32_t)(a) + 0xbd5c89185f082658ULL) * ((uint32_t)(b) + 0xe5fcc163aef32782ULL) + \
568  	                                                         ((uint32_t)(c) + 0xd37e9a1ce2148403ULL) * ((uint32_t)(d) + 0x926f2d4dc4a67218ULL) + \
569  	                                                         ((uint32_t)(e) + 0xf48d4cd331e14327ULL) * ((uint32_t)(f) + 0x80791a4edfc44c75ULL) + \
570  	                                                         (uint32_t)(g) * 0x7f497d9ba3bd83c0ULL)>>32 ))
571  	
572  	/** computes a hashcode for double precision floating point values containing
573  	 *  15 significant bits, the sign and the exponent
574  	 */
575  	INLINE static
576  	uint32_t SCIPrealHashCode(double x)
577  	{
578  	   int theexp;
579  	   return (((uint32_t)(uint16_t)(int16_t)ldexp(frexp(x, &theexp), 15))<<16) | (uint32_t)(uint16_t)theexp;
580  	}
581  	
582  	/** creates a hash table */
583  	SCIP_EXPORT
584  	SCIP_RETCODE SCIPhashtableCreate(
585  	   SCIP_HASHTABLE**      hashtable,          /**< pointer to store the created hash table */
586  	   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash table entries */
587  	   int                   tablesize,          /**< size of the hash table */
588  	   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
589  	   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
590  	   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
591  	   void*                 userptr             /**< user pointer */
592  	   );
593  	
594  	/** frees the hash table */
595  	SCIP_EXPORT
596  	void SCIPhashtableFree(
597  	   SCIP_HASHTABLE**      hashtable           /**< pointer to the hash table */
598  	   );
599  	
600  	/** removes all elements of the hash table
601  	 *
602  	 *  @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
603  	 *        be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
604  	 *
605  	 *  @deprecated Please use SCIPhashtableRemoveAll()
606  	 */
607  	SCIP_EXPORT
608  	SCIP_DEPRECATED
609  	void SCIPhashtableClear(
610  	   SCIP_HASHTABLE*       hashtable           /**< hash table */
611  	   );
612  	
613  	/** inserts element in hash table (multiple inserts of same element override the previous entry) */
614  	SCIP_EXPORT
615  	SCIP_RETCODE SCIPhashtableInsert(
616  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
617  	   void*                 element             /**< element to insert into the table */
618  	   );
619  	
620  	/** inserts element in hash table (multiple insertion of same element is checked and results in an error) */
621  	SCIP_EXPORT
622  	SCIP_RETCODE SCIPhashtableSafeInsert(
623  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
624  	   void*                 element             /**< element to insert into the table */
625  	   );
626  	
627  	/** retrieve element with key from hash table, returns NULL if not existing */
628  	SCIP_EXPORT
629  	void* SCIPhashtableRetrieve(
630  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
631  	   void*                 key                 /**< key to retrieve */
632  	   );
633  	
634  	/** returns whether the given element exists in the table */
635  	SCIP_EXPORT
636  	SCIP_Bool SCIPhashtableExists(
637  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
638  	   void*                 element             /**< element to search in the table */
639  	   );
640  	
641  	/** removes element from the hash table, if it exists */
642  	SCIP_EXPORT
643  	SCIP_RETCODE SCIPhashtableRemove(
644  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
645  	   void*                 element             /**< element to remove from the table */
646  	   );
647  	
648  	/** removes all elements of the hash table */
649  	SCIP_EXPORT
650  	void SCIPhashtableRemoveAll(
651  	   SCIP_HASHTABLE*       hashtable           /**< hash table */
652  	   );
653  	
654  	/** returns number of hash table elements */
655  	SCIP_EXPORT
656  	SCIP_Longint SCIPhashtableGetNElements(
657  	   SCIP_HASHTABLE*       hashtable           /**< hash table */
658  	   );
659  	
660  	/** gives the number of entries in the internal arrays of a hash table */
661  	SCIP_EXPORT
662  	int SCIPhashtableGetNEntries(
663  	   SCIP_HASHTABLE*       hashtable           /**< hash table */
664  	   );
665  	
666  	/** gives the element at the given index or NULL if entry at that index has no element */
667  	SCIP_EXPORT
668  	void* SCIPhashtableGetEntry(
669  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
670  	   int                   entryidx            /**< index of hash table entry */
671  	   );
672  	
673  	/** returns the load of the given hash table in percentage */
674  	SCIP_EXPORT
675  	SCIP_Real SCIPhashtableGetLoad(
676  	   SCIP_HASHTABLE*       hashtable           /**< hash table */
677  	   );
678  	
679  	/** prints statistics about hash table usage */
680  	SCIP_EXPORT
681  	void SCIPhashtablePrintStatistics(
682  	   SCIP_HASHTABLE*       hashtable,          /**< hash table */
683  	   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
684  	   );
685  	
686  	/**@} */
687  	
688  	/*
689  	 * MultiHash Table
690  	 */
691  	
692  	/**@defgroup MultiHash Multi Hash table
693  	 * @ingroup DataStructures
694  	 * @brief hash table that resolves conflicts by queueing, thereby allowing for duplicate entries
695  	 *
696  	 *@{
697  	 */
698  	
699  	/** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
700  	SCIP_EXPORT
701  	int SCIPcalcMultihashSize(
702  	   int                   minsize             /**< minimal size of the hash table */
703  	   );
704  	
705  	/** creates a multihash table */
706  	SCIP_EXPORT
707  	SCIP_RETCODE SCIPmultihashCreate(
708  	   SCIP_MULTIHASH**      multihash,          /**< pointer to store the created multihash table */
709  	   BMS_BLKMEM*           blkmem,             /**< block memory used to store multihash table entries */
710  	   int                   tablesize,          /**< size of the hash table */
711  	   SCIP_DECL_HASHGETKEY((*hashgetkey)),      /**< gets the key of the given element */
712  	   SCIP_DECL_HASHKEYEQ ((*hashkeyeq)),       /**< returns TRUE iff both keys are equal */
713  	   SCIP_DECL_HASHKEYVAL((*hashkeyval)),      /**< returns the hash value of the key */
714  	   void*                 userptr             /**< user pointer */
715  	   );
716  	
717  	/** frees the multihash table */
718  	SCIP_EXPORT
719  	void SCIPmultihashFree(
720  	   SCIP_MULTIHASH**      multihash           /**< pointer to the multihash table */
721  	   );
722  	
723  	/** inserts element in multihash table (multiple inserts of same element possible)
724  	 *
725  	 *  @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
726  	 *        to the hash table, due to dynamic resizing.
727  	 */
728  	SCIP_EXPORT
729  	SCIP_RETCODE SCIPmultihashInsert(
730  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
731  	   void*                 element             /**< element to insert into the table */
732  	   );
733  	
734  	/** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
735  	 *
736  	 *  @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
737  	 *        element to the multihash table, due to dynamic resizing.
738  	 */
739  	SCIP_EXPORT
740  	SCIP_RETCODE SCIPmultihashSafeInsert(
741  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
742  	   void*                 element             /**< element to insert into the table */
743  	   );
744  	
745  	/** retrieve element with key from multihash table, returns NULL if not existing */
746  	SCIP_EXPORT
747  	void* SCIPmultihashRetrieve(
748  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
749  	   void*                 key                 /**< key to retrieve */
750  	   );
751  	
752  	/** retrieve element with key from multihash table, returns NULL if not existing
753  	 *  can be used to retrieve all entries with the same key (one-by-one)
754  	 *
755  	 *  @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
756  	 */
757  	SCIP_EXPORT
758  	void* SCIPmultihashRetrieveNext(
759  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
760  	   SCIP_MULTIHASHLIST**  multihashlist,      /**< input: entry in hash table list from which to start searching, or NULL
761  	                                              *   output: entry in hash table list corresponding to element after
762  	                                              *           retrieved one, or NULL */
763  	   void*                 key                 /**< key to retrieve */
764  	   );
765  	
766  	/** returns whether the given element exists in the multihash table */
767  	SCIP_EXPORT
768  	SCIP_Bool SCIPmultihashExists(
769  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
770  	   void*                 element             /**< element to search in the table */
771  	   );
772  	
773  	/** removes element from the multihash table, if it exists */
774  	SCIP_EXPORT
775  	SCIP_RETCODE SCIPmultihashRemove(
776  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
777  	   void*                 element             /**< element to remove from the table */
778  	   );
779  	
780  	/** removes all elements of the multihash table
781  	 *
782  	 *  @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
783  	 *        be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
784  	 */
785  	SCIP_EXPORT
786  	void SCIPmultihashRemoveAll(
787  	   SCIP_MULTIHASH*       multihash           /**< multihash table */
788  	   );
789  	
790  	/** returns number of multihash table elements */
791  	SCIP_EXPORT
792  	SCIP_Longint SCIPmultihashGetNElements(
793  	   SCIP_MULTIHASH*       multihash           /**< multihash table */
794  	   );
795  	
796  	/** returns the load of the given multihash table in percentage */
797  	SCIP_EXPORT
798  	SCIP_Real SCIPmultihashGetLoad(
799  	   SCIP_MULTIHASH*       multihash           /**< multihash table */
800  	   );
801  	
802  	/** prints statistics about multihash table usage */
803  	SCIP_EXPORT
804  	void SCIPmultihashPrintStatistics(
805  	   SCIP_MULTIHASH*       multihash,          /**< multihash table */
806  	   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
807  	   );
808  	
809  	/** standard hash key comparator for string keys */
810  	SCIP_EXPORT
811  	SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString);
812  	
813  	/** standard hashing function for string keys */
814  	SCIP_EXPORT
815  	SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString);
816  	
817  	/** gets the element as the key */
818  	SCIP_EXPORT
819  	SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard);
820  	
821  	/** returns TRUE iff both keys(pointer) are equal */
822  	SCIP_EXPORT
823  	SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr);
824  	
825  	/** returns the hash value of the key */
826  	SCIP_EXPORT
827  	SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr);
828  	
829  	/**@} */
830  	
831  	
832  	/*
833  	 * Hash Map
834  	 */
835  	
836  	/**@defgroup HashMap Hash Map
837  	 * @ingroup DataStructures
838  	 * @brief hash map to store key-value pairs (called \p origin and \p image)
839  	 *
840  	 * @{
841  	 */
842  	
843  	/** creates a hash map mapping pointers to pointers */
844  	SCIP_EXPORT
845  	SCIP_RETCODE SCIPhashmapCreate(
846  	   SCIP_HASHMAP**        hashmap,            /**< pointer to store the created hash map */
847  	   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash map entries */
848  	   int                   mapsize             /**< size of the hash map */
849  	   );
850  	
851  	/** frees the hash map */
852  	SCIP_EXPORT
853  	void SCIPhashmapFree(
854  	   SCIP_HASHMAP**        hashmap             /**< pointer to the hash map */
855  	   );
856  	
857  	/** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
858  	SCIP_EXPORT
859  	SCIP_RETCODE SCIPhashmapInsert(
860  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
861  	   void*                 origin,             /**< origin to set image for */
862  	   void*                 image               /**< new image for origin */
863  	   );
864  	
865  	/** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
866  	SCIP_EXPORT
867  	SCIP_RETCODE SCIPhashmapInsertInt(
868  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
869  	   void*                 origin,             /**< origin to set image for */
870  	   int                   image               /**< new image for origin */
871  	   );
872  	
873  	/** inserts new origin->image pair in hash map (must not be called for already existing origins!) */
874  	SCIP_EXPORT
875  	SCIP_RETCODE SCIPhashmapInsertReal(
876  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
877  	   void*                 origin,             /**< origin to set image for */
878  	   SCIP_Real             image               /**< new image for origin */
879  	   );
880  	
881  	/** retrieves image of given origin from the hash map, or NULL if no image exists */
882  	SCIP_EXPORT
883  	void* SCIPhashmapGetImage(
884  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
885  	   void*                 origin              /**< origin to retrieve image for */
886  	   );
887  	
888  	/** retrieves image of given origin from the hash map, or INT_MAX if no image exists */
889  	SCIP_EXPORT
890  	int SCIPhashmapGetImageInt(
891  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
892  	   void*                 origin              /**< origin to retrieve image for */
893  	   );
894  	
895  	/** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */
896  	SCIP_EXPORT
897  	SCIP_Real SCIPhashmapGetImageReal(
898  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
899  	   void*                 origin              /**< origin to retrieve image for */
900  	   );
901  	
902  	/** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
903  	 *  new origin->image pair
904  	 */
905  	SCIP_EXPORT
906  	SCIP_RETCODE SCIPhashmapSetImage(
907  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
908  	   void*                 origin,             /**< origin to set image for */
909  	   void*                 image               /**< new image for origin */
910  	   );
911  	
912  	/** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
913  	 *  new origin->image pair
914  	 */
915  	SCIP_EXPORT
916  	SCIP_RETCODE SCIPhashmapSetImageInt(
917  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
918  	   void*                 origin,             /**< origin to set image for */
919  	   int                   image               /**< new image for origin */
920  	   );
921  	
922  	/** sets image for given origin in the hash map, either by modifying existing origin->image pair or by appending a
923  	 *  new origin->image pair
924  	 */
925  	SCIP_EXPORT
926  	SCIP_RETCODE SCIPhashmapSetImageReal(
927  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
928  	   void*                 origin,             /**< origin to set image for */
929  	   SCIP_Real             image               /**< new image for origin */
930  	   );
931  	
932  	/** checks whether an image to the given origin exists in the hash map */
933  	SCIP_EXPORT
934  	SCIP_Bool SCIPhashmapExists(
935  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
936  	   void*                 origin              /**< origin to search for */
937  	   );
938  	
939  	/** removes origin->image pair from the hash map, if it exists */
940  	SCIP_EXPORT
941  	SCIP_RETCODE SCIPhashmapRemove(
942  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
943  	   void*                 origin              /**< origin to remove from the list */
944  	   );
945  	
946  	/** prints statistics about hash map usage */
947  	SCIP_EXPORT
948  	void SCIPhashmapPrintStatistics(
949  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
950  	   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
951  	   );
952  	
953  	/** indicates whether a hash map has no entries */
954  	SCIP_EXPORT
955  	SCIP_Bool SCIPhashmapIsEmpty(
956  	   SCIP_HASHMAP*         hashmap             /**< hash map */
957  	   );
958  	
959  	/** gives the number of elements in a hash map */
960  	SCIP_EXPORT
961  	int SCIPhashmapGetNElements(
962  	   SCIP_HASHMAP*         hashmap             /**< hash map */
963  	   );
964  	
965  	/** gives the number of entries in the internal arrays of a hash map */
966  	SCIP_EXPORT
967  	int SCIPhashmapGetNEntries(
968  	   SCIP_HASHMAP*         hashmap             /**< hash map */
969  	   );
970  	
971  	/** gives the hashmap entry at the given index or NULL if entry has no element */
972  	SCIP_EXPORT
973  	SCIP_HASHMAPENTRY* SCIPhashmapGetEntry(
974  	   SCIP_HASHMAP*         hashmap,            /**< hash map */
975  	   int                   entryidx            /**< index of hash map entry */
976  	   );
977  	
978  	/** gives the origin of the hashmap entry */
979  	SCIP_EXPORT
980  	void* SCIPhashmapEntryGetOrigin(
981  	   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
982  	   );
983  	
984  	/** gives the image of the hashmap entry */
985  	SCIP_EXPORT
986  	void* SCIPhashmapEntryGetImage(
987  	   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
988  	   );
989  	
990  	/** gives the image of the hashmap entry */
991  	SCIP_EXPORT
992  	int SCIPhashmapEntryGetImageInt(
993  	   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
994  	   );
995  	
996  	/** gives the image of the hashmap entry */
997  	SCIP_EXPORT
998  	SCIP_Real SCIPhashmapEntryGetImageReal(
999  	   SCIP_HASHMAPENTRY*    entry               /**< hash map entry */
1000 	   );
1001 	
1002 	/** sets pointer image of a hashmap entry */
1003 	SCIP_EXPORT
1004 	void SCIPhashmapEntrySetImage(
1005 	   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
1006 	   void*                 image               /**< new image */
1007 	   );
1008 	
1009 	/** sets integer image of a hashmap entry */
1010 	SCIP_EXPORT
1011 	void SCIPhashmapEntrySetImageInt(
1012 	   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
1013 	   int                   image               /**< new image */
1014 	   );
1015 	
1016 	/** sets real image of a hashmap entry */
1017 	SCIP_EXPORT
1018 	void SCIPhashmapEntrySetImageReal(
1019 	   SCIP_HASHMAPENTRY*    entry,              /**< hash map entry */
1020 	   SCIP_Real             image               /**< new image */
1021 	   );
1022 	
1023 	/** removes all entries in a hash map. */
1024 	SCIP_EXPORT
1025 	SCIP_RETCODE SCIPhashmapRemoveAll(
1026 	   SCIP_HASHMAP*         hashmap             /**< hash map */
1027 	   );
1028 	
1029 	/**@} */
1030 	
1031 	
1032 	/*
1033 	 * Hash Set
1034 	 */
1035 	
1036 	/**@defgroup HashSet Hash Set
1037 	 * @ingroup DataStructures
1038 	 * @brief very lightweight hash set of pointers
1039 	 *
1040 	 * @{
1041 	 */
1042 	
1043 	/** creates a hash set of pointers */
1044 	SCIP_EXPORT
1045 	SCIP_RETCODE SCIPhashsetCreate(
1046 	   SCIP_HASHSET**        hashset,            /**< pointer to store the created hash set */
1047 	   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash set entries */
1048 	   int                   size                /**< initial size of the hash set; it is guaranteed that the set is not
1049 	                                              *   resized if at most that many elements are inserted */
1050 	   );
1051 	
1052 	/** frees the hash set */
1053 	SCIP_EXPORT
1054 	void SCIPhashsetFree(
1055 	   SCIP_HASHSET**        hashset,            /**< pointer to the hash set */
1056 	   BMS_BLKMEM*           blkmem              /**< block memory used to store hash set entries */
1057 	   );
1058 	
1059 	/** inserts new element into the hash set */
1060 	SCIP_EXPORT
1061 	SCIP_RETCODE SCIPhashsetInsert(
1062 	   SCIP_HASHSET*         hashset,            /**< hash set */
1063 	   BMS_BLKMEM*           blkmem,             /**< block memory used to store hash set entries */
1064 	   void*                 element             /**< element to insert */
1065 	   );
1066 	
1067 	/** checks whether an element exists in the hash set */
1068 	SCIP_EXPORT
1069 	SCIP_Bool SCIPhashsetExists(
1070 	   SCIP_HASHSET*         hashset,            /**< hash set */
1071 	   void*                 element             /**< element to search for */
1072 	   );
1073 	
1074 	/** removes an element from the hash set, if it exists */
1075 	SCIP_EXPORT
1076 	SCIP_RETCODE SCIPhashsetRemove(
1077 	   SCIP_HASHSET*         hashset,            /**< hash set */
1078 	   void*                 element             /**< origin to remove from the list */
1079 	   );
1080 	
1081 	/** prints statistics about hash set usage */
1082 	SCIP_EXPORT
1083 	void SCIPhashsetPrintStatistics(
1084 	   SCIP_HASHSET*         hashset,            /**< hash set */
1085 	   SCIP_MESSAGEHDLR*     messagehdlr         /**< message handler */
1086 	   );
1087 	
1088 	/** indicates whether a hash set has no entries */
1089 	SCIP_EXPORT
1090 	SCIP_Bool SCIPhashsetIsEmpty(
1091 	   SCIP_HASHSET*         hashset             /**< hash set */
1092 	   );
1093 	
1094 	/** gives the number of elements in a hash set */
1095 	SCIP_EXPORT
1096 	int SCIPhashsetGetNElements(
1097 	   SCIP_HASHSET*         hashset             /**< hash set */
1098 	   );
1099 	
1100 	/** gives the number of slots of a hash set */
1101 	SCIP_EXPORT
1102 	int SCIPhashsetGetNSlots(
1103 	   SCIP_HASHSET*         hashset             /**< hash set */
1104 	   );
1105 	
1106 	/** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
1107 	SCIP_EXPORT
1108 	void** SCIPhashsetGetSlots(
1109 	   SCIP_HASHSET*         hashset             /**< hash set */
1110 	   );
1111 	
1112 	/** removes all entries in a hash set. */
1113 	SCIP_EXPORT
1114 	void SCIPhashsetRemoveAll(
1115 	   SCIP_HASHSET*         hashset             /**< hash set */
1116 	   );
1117 	
1118 	#ifdef NDEBUG
1119 	
1120 	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1121 	 * speed up the algorithms.
1122 	 */
1123 	
1124 	#define SCIPhashsetIsEmpty(hashset)        ((hashset)->nelements == 0)
1125 	#define SCIPhashsetGetNElements(hashset)   ((hashset)->nelements)
1126 	#define SCIPhashsetGetNSlots(hashset)      (1u << (64 - (hashset)->shift))
1127 	#define SCIPhashsetGetSlots(hashset)       ((hashset)->slots)
1128 	
1129 	#endif
1130 	
1131 	/**@} */
1132 	
1133 	
1134 	/*
1135 	 * Activity
1136 	 */
1137 	
1138 	/**@defgroup ResourceActivity Resource Activity
1139 	 * @ingroup DataStructures
1140 	 * @brief ressource activity data structure
1141 	 *
1142 	 * @{
1143 	 */
1144 	
1145 	/** create a resource activity */
1146 	SCIP_EXPORT
1147 	SCIP_RETCODE SCIPactivityCreate(
1148 	   SCIP_RESOURCEACTIVITY** activity,         /**< pointer to store the resource activity */
1149 	   SCIP_VAR*             var,                /**< start time variable of the activity */
1150 	   int                   duration,           /**< duration of the activity */
1151 	   int                   demand              /**< demand of the activity */
1152 	   );
1153 	
1154 	/** frees a resource activity */
1155 	SCIP_EXPORT
1156 	void SCIPactivityFree(
1157 	   SCIP_RESOURCEACTIVITY** activity          /**< pointer to the resource activity */
1158 	   );
1159 	
1160 	#ifndef NDEBUG
1161 	
1162 	/** returns the start time variable of the resource activity */
1163 	SCIP_EXPORT
1164 	SCIP_VAR* SCIPactivityGetVar(
1165 	   SCIP_RESOURCEACTIVITY* activity           /**< resource activity */
1166 	   );
1167 	
1168 	/** returns the duration of the resource activity */
1169 	SCIP_EXPORT
1170 	int SCIPactivityGetDuration(
1171 	   SCIP_RESOURCEACTIVITY* activity           /**< resource activity */
1172 	   );
1173 	
1174 	/** returns the demand of the resource activity */
1175 	SCIP_EXPORT
1176 	int SCIPactivityGetDemand(
1177 	   SCIP_RESOURCEACTIVITY* activity           /**< resource activity */
1178 	   );
1179 	
1180 	/** returns the energy of the resource activity */
1181 	SCIP_EXPORT
1182 	int SCIPactivityGetEnergy(
1183 	   SCIP_RESOURCEACTIVITY* activity           /**< resource activity */
1184 	   );
1185 	
1186 	#else
1187 	
1188 	#define SCIPactivityGetVar(activity)         ((activity)->var)
1189 	#define SCIPactivityGetDuration(activity)    ((activity)->duration)
1190 	#define SCIPactivityGetDemand(activity)      ((activity)->demand)
1191 	#define SCIPactivityGetEnergy(activity)      ((activity)->duration * (activity)->demand)
1192 	
1193 	#endif
1194 	
1195 	/**@} */
1196 	
1197 	
1198 	/*
1199 	 * Resource Profile
1200 	 */
1201 	
1202 	/**@defgroup ResourceProfile Resource Profile
1203 	 * @ingroup DataStructures
1204 	 * @brief ressource profile data structure
1205 	 *
1206 	 * @{
1207 	 */
1208 	
1209 	/** creates resource profile */
1210 	SCIP_EXPORT
1211 	SCIP_RETCODE SCIPprofileCreate(
1212 	   SCIP_PROFILE**        profile,            /**< pointer to store the resource profile */
1213 	   int                   capacity            /**< resource capacity */
1214 	   );
1215 	
1216 	/** frees given resource profile */
1217 	SCIP_EXPORT
1218 	void SCIPprofileFree(
1219 	   SCIP_PROFILE**        profile             /**< pointer to the resource profile */
1220 	   );
1221 	
1222 	/** output of the given resource profile */
1223 	SCIP_EXPORT
1224 	void SCIPprofilePrint(
1225 	   SCIP_PROFILE*         profile,            /**< resource profile to output */
1226 	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
1227 	   FILE*                 file                /**< output file (or NULL for standard output) */
1228 	   );
1229 	
1230 	/** returns the capacity of the resource profile */
1231 	SCIP_EXPORT
1232 	int SCIPprofileGetCapacity(
1233 	   SCIP_PROFILE*         profile             /**< resource profile to use */
1234 	   );
1235 	
1236 	/** returns the number time points of the resource profile */
1237 	SCIP_EXPORT
1238 	int SCIPprofileGetNTimepoints(
1239 	   SCIP_PROFILE*         profile             /**< resource profile to use */
1240 	   );
1241 	
1242 	/** returns the time points of the resource profile */
1243 	SCIP_EXPORT
1244 	int* SCIPprofileGetTimepoints(
1245 	   SCIP_PROFILE*         profile             /**< resource profile to use */
1246 	   );
1247 	
1248 	/** returns the loads of the resource profile */
1249 	SCIP_EXPORT
1250 	int* SCIPprofileGetLoads(
1251 	   SCIP_PROFILE*         profile             /**< resource profile to use */
1252 	   );
1253 	
1254 	/** returns the time point for given position of the resource profile */
1255 	SCIP_EXPORT
1256 	int SCIPprofileGetTime(
1257 	   SCIP_PROFILE*         profile,            /**< resource profile to use */
1258 	   int                   pos                 /**< position */
1259 	   );
1260 	
1261 	/** returns the loads of the resource profile at the given position */
1262 	SCIP_EXPORT
1263 	int SCIPprofileGetLoad(
1264 	   SCIP_PROFILE*         profile,            /**< resource profile */
1265 	   int                   pos                 /**< position */
1266 	   );
1267 	
1268 	/** returns if the given time point exists in the resource profile and stores the position of the given time point if it
1269 	 *  exists; otherwise the position of the next smaller existing time point is stored
1270 	 */
1271 	SCIP_EXPORT
1272 	SCIP_Bool SCIPprofileFindLeft(
1273 	   SCIP_PROFILE*         profile,            /**< resource profile to search */
1274 	   int                   timepoint,          /**< time point to search for */
1275 	   int*                  pos                 /**< pointer to store the position */
1276 	   );
1277 	
1278 	/** insert a core into resource profile; if the core is non-empty the resource profile will be updated otherwise nothing
1279 	 *  happens
1280 	 */
1281 	SCIP_EXPORT
1282 	SCIP_RETCODE SCIPprofileInsertCore(
1283 	   SCIP_PROFILE*         profile,            /**< resource profile to use */
1284 	   int                   left,               /**< left side of the core  */
1285 	   int                   right,              /**< right side of the core */
1286 	   int                   height,             /**< height of the core */
1287 	   int*                  pos,                /**< pointer to store the first position were it gets infeasible */
1288 	   SCIP_Bool*            infeasible          /**< pointer to store if the core does not fit due to capacity */
1289 	   );
1290 	
1291 	/** subtracts the height from the resource profile during core time */
1292 	SCIP_EXPORT
1293 	SCIP_RETCODE SCIPprofileDeleteCore(
1294 	   SCIP_PROFILE*         profile,            /**< resource profile to use */
1295 	   int                   left,               /**< left side of the core  */
1296 	   int                   right,              /**< right side of the core */
1297 	   int                   height              /**< height of the core */
1298 	   );
1299 	
1300 	/** return the earliest possible starting point within the time interval [lb,ub] for a given core (given by its height
1301 	 *  and duration)
1302 	 */
1303 	SCIP_EXPORT
1304 	int SCIPprofileGetEarliestFeasibleStart(
1305 	   SCIP_PROFILE*         profile,            /**< resource profile to use */
1306 	   int                   est,                /**< earliest starting time of the given core */
1307 	   int                   lst,                /**< latest starting time of the given core */
1308 	   int                   duration,           /**< duration of the core */
1309 	   int                   height,             /**< height of the core */
1310 	   SCIP_Bool*            infeasible          /**< pointer store if the corer cannot be inserted */
1311 	   );
1312 	
1313 	/** return the latest possible starting point within the time interval [lb,ub] for a given core (given by its height and
1314 	 *  duration)
1315 	 */
1316 	SCIP_EXPORT
1317 	int SCIPprofileGetLatestFeasibleStart(
1318 	   SCIP_PROFILE*         profile,            /**< resource profile to use */
1319 	   int                   lb,                 /**< earliest possible start point */
1320 	   int                   ub,                 /**< latest possible start point */
1321 	   int                   duration,           /**< duration of the core */
1322 	   int                   height,             /**< height of the core */
1323 	   SCIP_Bool*            infeasible          /**< pointer store if the core cannot be inserted */
1324 	   );
1325 	
1326 	/**@} */
1327 	
1328 	/*
1329 	 * Directed graph
1330 	 */
1331 	
1332 	/**@addtogroup DirectedGraph
1333 	 *
1334 	 * @{
1335 	 */
1336 	
1337 	/** resize directed graph structure */
1338 	SCIP_EXPORT
1339 	SCIP_RETCODE SCIPdigraphResize(
1340 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1341 	   int                   nnodes              /**< new number of nodes */
1342 	   );
1343 	
1344 	/** sets the sizes of the successor lists for the nodes in a directed graph and allocates memory for the lists */
1345 	SCIP_EXPORT
1346 	SCIP_RETCODE SCIPdigraphSetSizes(
1347 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1348 	   int*                  sizes               /**< sizes of the successor lists */
1349 	   );
1350 	
1351 	/** frees given directed graph structure */
1352 	SCIP_EXPORT
1353 	void SCIPdigraphFree(
1354 	   SCIP_DIGRAPH**        digraph             /**< pointer to the directed graph */
1355 	   );
1356 	
1357 	/** add (directed) arc and a related data to the directed graph structure
1358 	 *
1359 	 *  @note if the arc is already contained, it is added a second time
1360 	 */
1361 	SCIP_EXPORT
1362 	SCIP_RETCODE SCIPdigraphAddArc(
1363 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1364 	   int                   startnode,          /**< start node of the arc */
1365 	   int                   endnode,            /**< start node of the arc */
1366 	   void*                 data                /**< data that should be stored for the arc; or NULL */
1367 	   );
1368 	
1369 	/** add (directed) arc to the directed graph structure, if it is not contained, yet
1370 	 *
1371 	 * @note if there already exists an arc from startnode to endnode, the new arc is not added,
1372 	 *       even if its data is different
1373 	 */
1374 	SCIP_EXPORT
1375 	SCIP_RETCODE SCIPdigraphAddArcSafe(
1376 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1377 	   int                   startnode,          /**< start node of the arc */
1378 	   int                   endnode,            /**< start node of the arc */
1379 	   void*                 data                /**< data that should be stored for the arc; or NULL */
1380 	   );
1381 	
1382 	/** sets the number of successors to a given value */
1383 	SCIP_EXPORT
1384 	SCIP_RETCODE SCIPdigraphSetNSuccessors(
1385 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1386 	   int                   node,               /**< node for which the number of successors has to be changed */
1387 	   int                   nsuccessors         /**< new number of successors */
1388 	   );
1389 	
1390 	/** returns the number of nodes of the given digraph */
1391 	SCIP_EXPORT
1392 	int SCIPdigraphGetNNodes(
1393 	   SCIP_DIGRAPH*         digraph             /**< directed graph */
1394 	   );
1395 	
1396 	/** returns the node data, or NULL if no data exist */
1397 	SCIP_EXPORT
1398 	void* SCIPdigraphGetNodeData(
1399 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1400 	   int                   node                /**< node for which the node data is returned */
1401 	   );
1402 	
1403 	/** sets the node data */
1404 	SCIP_EXPORT
1405 	void SCIPdigraphSetNodeData(
1406 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1407 	   void*                 dataptr,            /**< user node data pointer, or NULL */
1408 	   int                   node                /**< node for which the node data is returned */
1409 	   );
1410 	
1411 	/** returns the total number of arcs in the given digraph */
1412 	SCIP_EXPORT
1413 	int SCIPdigraphGetNArcs(
1414 	   SCIP_DIGRAPH*         digraph             /**< directed graph */
1415 	   );
1416 	
1417 	/** returns the number of successor nodes of the given node */
1418 	SCIP_EXPORT
1419 	int SCIPdigraphGetNSuccessors(
1420 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1421 	   int                   node                /**< node for which the number of outgoing arcs is returned */
1422 	   );
1423 	
1424 	/** returns the array of indices of the successor nodes; this array must not be changed from outside */
1425 	SCIP_EXPORT
1426 	int* SCIPdigraphGetSuccessors(
1427 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1428 	   int                   node                /**< node for which the array of outgoing arcs is returned */
1429 	   );
1430 	
1431 	/** returns the array of data corresponding to the arcs originating at the given node, or NULL if no data exist; this
1432 	 *  array must not be changed from outside
1433 	 */
1434 	SCIP_EXPORT
1435 	void** SCIPdigraphGetSuccessorsData(
1436 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1437 	   int                   node                /**< node for which the data corresponding to the outgoing arcs is returned */
1438 	   );
1439 	
1440 	/** identifies the articulation points in a given directed graph
1441 	 *  uses the helper recursive function findArticulationPointsUtil
1442 	 */
1443 	SCIP_EXPORT
1444 	SCIP_RETCODE SCIPdigraphGetArticulationPoints(
1445 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1446 	   int**                 articulations,      /**< array to store the sorted node indices of the computed articulation points, or NULL */
1447 	   int*                  narticulations      /**< number of the computed articulation points, or NULL */
1448 	   );
1449 	
1450 	/** Compute undirected connected components on the given graph.
1451 	 *
1452 	 *  @note For each arc, its reverse is added, so the graph does not need to be the directed representation of an
1453 	 *        undirected graph.
1454 	 */
1455 	SCIP_EXPORT
1456 	SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(
1457 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1458 	   int                   minsize,            /**< all components with less nodes are ignored */
1459 	   int*                  components,         /**< array with as many slots as there are nodes in the directed graph
1460 	                                              *   to store for each node the component to which it belongs
1461 	                                              *   (components are numbered 0 to ncomponents - 1); or NULL, if components
1462 	                                              *   are accessed one-by-one using SCIPdigraphGetComponent() */
1463 	   int*                  ncomponents         /**< pointer to store the number of components; or NULL, if the
1464 	                                              *   number of components is accessed by SCIPdigraphGetNComponents() */
1465 	   );
1466 	
1467 	/** Computes all strongly connected components of an undirected connected component with Tarjan's Algorithm.
1468 	 *  The resulting strongly connected components are sorted topologically (starting from the end of the
1469 	 *  strongcomponents array).
1470 	 *
1471 	 *  @note In general a topological sort of the strongly connected components is not unique.
1472 	 */
1473 	SCIP_EXPORT
1474 	SCIP_RETCODE SCIPdigraphComputeDirectedComponents(
1475 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1476 	   int                   compidx,            /**< number of the undirected connected component */
1477 	   int*                  strongcomponents,   /**< array to store the strongly connected components
1478 	                                              *   (length >= size of the component) */
1479 	   int*                  strongcompstartidx, /**< array to store the start indices of the strongly connected
1480 	                                              *   components (length >= size of the component) */
1481 	   int*                  nstrongcomponents   /**< pointer to store the number of strongly connected
1482 	                                              *   components */
1483 	   );
1484 	
1485 	/** Performes an (almost) topological sort on the undirected components of the given directed graph. The undirected
1486 	 *  components should be computed before using SCIPdigraphComputeUndirectedComponents().
1487 	 *
1488 	 *  @note In general a topological sort is not unique.  Note, that there might be directed cycles, that are randomly
1489 	 *        broken, which is the reason for having only almost topologically sorted arrays.
1490 	 */
1491 	SCIP_EXPORT
1492 	SCIP_RETCODE SCIPdigraphTopoSortComponents(
1493 	   SCIP_DIGRAPH*         digraph             /**< directed graph */
1494 	   );
1495 	
1496 	/** returns the number of previously computed undirected components for the given directed graph */
1497 	SCIP_EXPORT
1498 	int SCIPdigraphGetNComponents(
1499 	   SCIP_DIGRAPH*         digraph             /**< directed graph */
1500 	   );
1501 	
1502 	/** Returns the previously computed undirected component of the given number for the given directed graph.
1503 	 *  If the components were sorted using SCIPdigraphTopoSortComponents(), the component is (almost) topologically sorted.
1504 	 */
1505 	SCIP_EXPORT
1506 	void SCIPdigraphGetComponent(
1507 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1508 	   int                   compidx,            /**< number of the component to return */
1509 	   int**                 nodes,              /**< pointer to store the nodes in the component; or NULL, if not needed */
1510 	   int*                  nnodes              /**< pointer to store the number of nodes in the component;
1511 	                                              *   or NULL, if not needed */
1512 	   );
1513 	
1514 	/** frees the component information for the given directed graph */
1515 	SCIP_EXPORT
1516 	void SCIPdigraphFreeComponents(
1517 	   SCIP_DIGRAPH*         digraph             /**< directed graph */
1518 	   );
1519 	
1520 	/** output of the given directed graph via the given message handler */
1521 	SCIP_EXPORT
1522 	void SCIPdigraphPrint(
1523 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1524 	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
1525 	   FILE*                 file                /**< output file (or NULL for standard output) */
1526 	   );
1527 	
1528 	/** prints the given directed graph structure in GML format into the given file */
1529 	SCIP_EXPORT
1530 	void SCIPdigraphPrintGml(
1531 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1532 	   FILE*                 file                /**< file to write to */
1533 	   );
1534 	
1535 	
1536 	/** output of the given directed graph via the given message handler */
1537 	SCIP_EXPORT
1538 	void SCIPdigraphPrintComponents(
1539 	   SCIP_DIGRAPH*         digraph,            /**< directed graph */
1540 	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
1541 	   FILE*                 file                /**< output file (or NULL for standard output) */
1542 	   );
1543 	
1544 	/**@} */
1545 	
1546 	/*
1547 	 * Binary search tree
1548 	 */
1549 	
1550 	/**@defgroup BinaryTree Binary Search Tree
1551 	 * @ingroup DataStructures
1552 	 * @brief binary search tree data structure
1553 	 *@{
1554 	 */
1555 	
1556 	/** creates a binary tree node with sorting value and user data */
1557 	SCIP_EXPORT
1558 	SCIP_RETCODE SCIPbtnodeCreate(
1559 	   SCIP_BT*              tree,               /**< binary search tree */
1560 	   SCIP_BTNODE**         node,               /**< pointer to store the created search node */
1561 	   void*                 dataptr             /**< user node data pointer, or NULL */
1562 	   );
1563 	
1564 	/** frees the binary node including the rooted subtree
1565 	 *
1566 	 *  @note The user pointer (object) is not freed. If needed, it has to be done by the user.
1567 	 */
1568 	SCIP_EXPORT
1569 	void SCIPbtnodeFree(
1570 	   SCIP_BT*              tree,               /**< binary tree */
1571 	   SCIP_BTNODE**         node                /**< node to be freed */
1572 	   );
1573 	
1574 	/** returns the user data pointer stored in that node */
1575 	SCIP_EXPORT
1576 	void* SCIPbtnodeGetData(
1577 	   SCIP_BTNODE*          node                /**< node */
1578 	   );
1579 	
1580 	/** returns the parent which can be NULL if the given node is the root */
1581 	SCIP_EXPORT
1582 	SCIP_BTNODE* SCIPbtnodeGetParent(
1583 	   SCIP_BTNODE*          node                /**< node */
1584 	   );
1585 	
1586 	/** returns left child which can be NULL if the given node is a leaf */
1587 	SCIP_EXPORT
1588 	SCIP_BTNODE* SCIPbtnodeGetLeftchild(
1589 	   SCIP_BTNODE*          node                /**< node */
1590 	   );
1591 	
1592 	/** returns right child which can be NULL if the given node is a leaf */
1593 	SCIP_EXPORT
1594 	SCIP_BTNODE* SCIPbtnodeGetRightchild(
1595 	   SCIP_BTNODE*          node                /**< node */
1596 	   );
1597 	
1598 	/** returns the sibling of the node or NULL if does not exist */
1599 	SCIP_EXPORT
1600 	SCIP_BTNODE* SCIPbtnodeGetSibling(
1601 	   SCIP_BTNODE*          node                /**< node */
1602 	   );
1603 	
1604 	/** returns whether the node is a root node */
1605 	SCIP_EXPORT
1606 	SCIP_Bool SCIPbtnodeIsRoot(
1607 	   SCIP_BTNODE*          node                /**< node */
1608 	   );
1609 	
1610 	/** returns whether the node is a leaf */
1611 	SCIP_EXPORT
1612 	SCIP_Bool SCIPbtnodeIsLeaf(
1613 	   SCIP_BTNODE*          node                /**< node */
1614 	   );
1615 	
1616 	/** returns TRUE if the given node is left child */
1617 	SCIP_EXPORT
1618 	SCIP_Bool SCIPbtnodeIsLeftchild(
1619 	   SCIP_BTNODE*          node                /**< node */
1620 	   );
1621 	
1622 	/** returns TRUE if the given node is right child */
1623 	SCIP_EXPORT
1624 	SCIP_Bool SCIPbtnodeIsRightchild(
1625 	   SCIP_BTNODE*          node                /**< node */
1626 	   );
1627 	
1628 	#ifdef NDEBUG
1629 	
1630 	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1631 	 * speed up the algorithms.
1632 	 */
1633 	
1634 	#define SCIPbtnodeGetData(node)               ((node)->dataptr)
1635 	#define SCIPbtnodeGetParent(node)             ((node)->parent)
1636 	#define SCIPbtnodeGetLeftchild(node)          ((node)->left)
1637 	#define SCIPbtnodeGetRightchild(node)         ((node)->right)
1638 	#define SCIPbtnodeGetSibling(node)            ((node)->parent == NULL ? NULL : \
1639 	                                               (node)->parent->left == (node) ? (node)->parent->right : (node)->parent->left)
1640 	#define SCIPbtnodeIsRoot(node)                ((node)->parent == NULL)
1641 	#define SCIPbtnodeIsLeaf(node)                ((node)->left == NULL && (node)->right == NULL)
1642 	#define SCIPbtnodeIsLeftchild(node)           ((node)->parent == NULL ? FALSE : (node)->parent->left == (node) ? TRUE : FALSE)
1643 	#define SCIPbtnodeIsRightchild(node)          ((node)->parent == NULL ? FALSE : (node)->parent->right == (node) ? TRUE : FALSE)
1644 	
1645 	#endif
1646 	
1647 	/** sets the give node data
1648 	 *
1649 	 *  @note The old user pointer is not freed.
1650 	 */
1651 	SCIP_EXPORT
1652 	void SCIPbtnodeSetData(
1653 	   SCIP_BTNODE*          node,               /**< node */
1654 	   void*                 dataptr             /**< node user data pointer */
1655 	   );
1656 	
1657 	/** sets parent node
1658 	 *
1659 	 *  @note The old parent including the rooted subtree is not delete.
1660 	 */
1661 	SCIP_EXPORT
1662 	void SCIPbtnodeSetParent(
1663 	   SCIP_BTNODE*          node,               /**< node */
1664 	   SCIP_BTNODE*          parent              /**< new parent node, or NULL */
1665 	   );
1666 	
1667 	/** sets left child
1668 	 *
1669 	 *  @note The old left child including the rooted subtree is not delete.
1670 	 */
1671 	SCIP_EXPORT
1672 	void SCIPbtnodeSetLeftchild(
1673 	   SCIP_BTNODE*          node,               /**< node */
1674 	   SCIP_BTNODE*          left                /**< new left child, or NULL */
1675 	   );
1676 	
1677 	/** sets right child
1678 	 *
1679 	 *  @note The old right child including the rooted subtree is not delete.
1680 	 */
1681 	SCIP_EXPORT
1682 	void SCIPbtnodeSetRightchild(
1683 	   SCIP_BTNODE*          node,               /**< node */
1684 	   SCIP_BTNODE*          right               /**< new right child, or NULL */
1685 	   );
1686 	
1687 	/** creates an binary tree */
1688 	SCIP_EXPORT
1689 	SCIP_RETCODE SCIPbtCreate(
1690 	   SCIP_BT**             tree,               /**< pointer to store the created binary tree */
1691 	   BMS_BLKMEM*           blkmem              /**< block memory used to create nodes */
1692 	   );
1693 	
1694 	/** frees binary tree
1695 	 *
1696 	 *  @note The user pointers (object) of the search nodes are not freed. If needed, it has to be done by the user.
1697 	 */
1698 	SCIP_EXPORT
1699 	void SCIPbtFree(
1700 	   SCIP_BT**             tree                /**< pointer to binary tree */
1701 	   );
1702 	
1703 	/** prints the binary tree in GML format into the given file */
1704 	SCIP_EXPORT
1705 	void SCIPbtPrintGml(
1706 	   SCIP_BT*              tree,               /**< binary tree */
1707 	   FILE*                 file                /**< file to write to */
1708 	   );
1709 	
1710 	/** returns whether the binary tree is empty (has no nodes) */
1711 	SCIP_EXPORT
1712 	SCIP_Bool SCIPbtIsEmpty(
1713 	   SCIP_BT *             tree                /**< binary tree */
1714 	   );
1715 	
1716 	/** returns the root node of the binary tree or NULL if the binary tree is empty */
1717 	SCIP_EXPORT
1718 	SCIP_BTNODE* SCIPbtGetRoot(
1719 	   SCIP_BT*              tree                /**< tree to be evaluated */
1720 	   );
1721 	
1722 	#ifdef NDEBUG
1723 	
1724 	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1725 	 * speed up the algorithms.
1726 	 */
1727 	
1728 	#define SCIPbtIsEmpty(tree) (tree->root == NULL)
1729 	#define SCIPbtGetRoot(tree) (tree->root)
1730 	
1731 	#endif
1732 	
1733 	/** sets root node
1734 	 *
1735 	 *  @note The old root including the rooted subtree is not delete.
1736 	 */
1737 	SCIP_EXPORT
1738 	void SCIPbtSetRoot(
1739 	   SCIP_BT*              tree,               /**< tree to be evaluated */
1740 	   SCIP_BTNODE*          root                /**< new root, or NULL */
1741 	   );
1742 	
1743 	/**@} */
1744 	
1745 	/**@addtogroup DisjointSet
1746 	 *
1747 	 * @{
1748 	 */
1749 	
1750 	/*
1751 	 * disjoint set data structure
1752 	 */
1753 	
1754 	/** clears the disjoint set (union find) structure \p djset */
1755 	SCIP_EXPORT
1756 	void SCIPdisjointsetClear(
1757 	   SCIP_DISJOINTSET*     djset               /**< disjoint set (union find) data structure */
1758 	   );
1759 	
1760 	/** finds and returns the component identifier of this \p element */
1761 	SCIP_EXPORT
1762 	int SCIPdisjointsetFind(
1763 	   SCIP_DISJOINTSET*     djset,              /**< disjoint set (union find) data structure */
1764 	   int                   element             /**< element to be found */
1765 	   );
1766 	
1767 	/** merges the components containing the elements \p p and \p q */
1768 	SCIP_EXPORT
1769 	void SCIPdisjointsetUnion(
1770 	   SCIP_DISJOINTSET*     djset,              /**< disjoint set (union find) data structure */
1771 	   int                   p,                  /**< first element */
1772 	   int                   q,                  /**< second element */
1773 	   SCIP_Bool             forcerepofp         /**< force representative of p to be new representative */
1774 	   );
1775 	
1776 	/** returns the number of independent components in this disjoint set (union find) data structure */
1777 	SCIP_EXPORT
1778 	int SCIPdisjointsetGetComponentCount(
1779 	   SCIP_DISJOINTSET*     djset               /**< disjoint set (union find) data structure */
1780 	   );
1781 	
1782 	/** returns the size (number of nodes) of this disjoint set (union find) data structure */
1783 	SCIP_EXPORT
1784 	int SCIPdisjointsetGetSize(
1785 	   SCIP_DISJOINTSET*     djset               /**< disjoint set (union find) data structure */
1786 	   );
1787 	
1788 	/** @} */
1789 	
1790 	/*
1791 	 * Numerical methods
1792 	 */
1793 	
1794 	/**@defgroup NumericalMethods Numerical Methods
1795 	 * @ingroup MiscellaneousMethods
1796 	 * @brief commonly used numerical methods
1797 	 *
1798 	 * @{
1799 	 */
1800 	
1801 	/** returns the machine epsilon: the smallest number eps > 0, for which 1.0 + eps > 1.0 */
1802 	SCIP_EXPORT
1803 	SCIP_Real SCIPcalcMachineEpsilon(
1804 	   void
1805 	   );
1806 	
1807 	/** returns the next representable value of from in the direction of to */
1808 	SCIP_EXPORT
1809 	SCIP_Real SCIPnextafter(
1810 	   SCIP_Real             from,               /**< value from which the next representable value should be returned */
1811 	   SCIP_Real             to                  /**< direction in which the next representable value should be returned */
1812 	   );
1813 	
1814 	/** calculates the greatest common divisor of the two given values */
1815 	SCIP_EXPORT
1816 	SCIP_Longint SCIPcalcGreComDiv(
1817 	   SCIP_Longint          val1,               /**< first value of greatest common devisor calculation */
1818 	   SCIP_Longint          val2                /**< second value of greatest common devisor calculation */
1819 	   );
1820 	
1821 	/** calculates the smallest common multiple of the two given values */
1822 	SCIP_EXPORT
1823 	SCIP_Longint SCIPcalcSmaComMul(
1824 	   SCIP_Longint          val1,               /**< first value of smallest common multiple calculation */
1825 	   SCIP_Longint          val2                /**< second value of smallest common multiple calculation */
1826 	   );
1827 	
1828 	/** calculates a binomial coefficient n over m, choose m elements out of n, maximal value will be 33 over 16 (because
1829 	 *  the n=33 is the last line in the Pascal's triangle where each entry fits in a 4 byte value), an error occurs due to
1830 	 *  big numbers or an negative value m (and m < n) and -1 will be returned
1831 	 */
1832 	SCIP_EXPORT
1833 	SCIP_Longint SCIPcalcBinomCoef(
1834 	   int                   n,                  /**< number of different elements */
1835 	   int                   m                   /**< number to choose out of the above */
1836 	   );
1837 	
1838 	/** calculates hash for floating-point number by using Fibonacci hashing */
1839 	SCIP_EXPORT
1840 	unsigned int SCIPcalcFibHash(
1841 	   SCIP_Real             v                   /**< number to hash */
1842 	   );
1843 	
1844 	#ifdef NDEBUG
1845 	
1846 	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1847 	 * speed up the algorithms.
1848 	 */
1849 	
1850 	#define SCIPcalcFibHash(v)   ((v) >= 0 ? ((unsigned long long)((v) * 2654435769)) % UINT_MAX : ((unsigned long long)(-(v) * 683565275)) % UINT_MAX )
1851 	
1852 	#endif
1853 	
1854 	/** converts a real number into a (approximate) rational representation, and returns TRUE iff the conversion was
1855 	 *  successful
1856 	 */
1857 	SCIP_EXPORT
1858 	SCIP_Bool SCIPrealToRational(
1859 	   SCIP_Real             val,                /**< real value r to convert into rational number */
1860 	   SCIP_Real             mindelta,           /**< minimal allowed difference r - q of real r and rational q = n/d */
1861 	   SCIP_Real             maxdelta,           /**< maximal allowed difference r - q of real r and rational q = n/d */
1862 	   SCIP_Longint          maxdnom,            /**< maximal denominator allowed */
1863 	   SCIP_Longint*         nominator,          /**< pointer to store the nominator n of the rational number */
1864 	   SCIP_Longint*         denominator         /**< pointer to store the denominator d of the rational number */
1865 	   );
1866 	
1867 	/** tries to find a value, such that all given values, if scaled with this value become integral in relative allowed
1868 	 *  difference in between mindelta and maxdelta
1869 	 */
1870 	SCIP_EXPORT
1871 	SCIP_RETCODE SCIPcalcIntegralScalar(
1872 	   SCIP_Real*            vals,               /**< values to scale */
1873 	   int                   nvals,              /**< number of values to scale */
1874 	   SCIP_Real             mindelta,           /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
1875 	   SCIP_Real             maxdelta,           /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
1876 	   SCIP_Longint          maxdnom,            /**< maximal denominator allowed in rational numbers */
1877 	   SCIP_Real             maxscale,           /**< maximal allowed scalar */
1878 	   SCIP_Real*            intscalar,          /**< pointer to store scalar that would make the coefficients integral, or NULL */
1879 	   SCIP_Bool*            success             /**< stores whether returned value is valid */
1880 	   );
1881 	
1882 	/** given a (usually very small) interval, tries to find a rational number with simple denominator (i.e. a small
1883 	 *  number, probably multiplied with powers of 10) out of this interval; returns TRUE iff a valid rational
1884 	 *  number inside the interval was found
1885 	 */
1886 	SCIP_EXPORT
1887 	SCIP_Bool SCIPfindSimpleRational(
1888 	   SCIP_Real             lb,                 /**< lower bound of the interval */
1889 	   SCIP_Real             ub,                 /**< upper bound of the interval */
1890 	   SCIP_Longint          maxdnom,            /**< maximal denominator allowed for resulting rational number */
1891 	   SCIP_Longint*         nominator,          /**< pointer to store the nominator n of the rational number */
1892 	   SCIP_Longint*         denominator         /**< pointer to store the denominator d of the rational number */
1893 	   );
1894 	
1895 	/** given a (usually very small) interval, selects a value inside this interval; it is tried to select a rational number
1896 	 *  with simple denominator (i.e. a small number, probably multiplied with powers of 10);
1897 	 *  if no valid rational number inside the interval was found, selects the central value of the interval
1898 	 */
1899 	SCIP_EXPORT
1900 	SCIP_Real SCIPselectSimpleValue(
1901 	   SCIP_Real             lb,                 /**< lower bound of the interval */
1902 	   SCIP_Real             ub,                 /**< upper bound of the interval */
1903 	   SCIP_Longint          maxdnom             /**< maximal denominator allowed for resulting rational number */
1904 	   );
1905 	
1906 	/** Performs the Newton Procedure from a given starting point to compute a root of the given function with
1907 	 *  specified precision and maximum number of iterations. If the procedure fails, SCIP_INVALID is returned.
1908 	 */
1909 	SCIP_EXPORT
1910 	SCIP_Real SCIPcalcRootNewton(
1911 	   SCIP_DECL_NEWTONEVAL((*function)),        /**< pointer to function for which roots are computed */
1912 	   SCIP_DECL_NEWTONEVAL((*derivative)),      /**< pointer to derivative of above function */
1913 	   SCIP_Real*            params,             /**< parameters needed for function (can be NULL) */
1914 	   int                   nparams,            /**< number of parameters (can be 0) */
1915 	   SCIP_Real             x,                  /**< starting point */
1916 	   SCIP_Real             eps,                /**< tolerance */
1917 	   int                   k                   /**< iteration limit */
1918 	   );
1919 	
1920 	/* The C99 standard defines the function (or macro) isfinite.
1921 	 * On MacOS X, isfinite is also available.
1922 	 * From the BSD world, there comes a function finite.
1923 	 * On SunOS, finite is also available.
1924 	 * In the MS compiler world, there is a function _finite.
1925 	 * As last resort, we check whether x == x does not hold, but this works only for NaN's, not for infinities!
1926 	 */
1927 	#if _XOPEN_SOURCE >= 600 || defined(_ISOC99_SOURCE) || _POSIX_C_SOURCE >= 200112L || defined(__APPLE__)
1928 	#define SCIPisFinite isfinite
1929 	#elif defined(_BSD_SOURCE) || defined(__sun)
1930 	#define SCIPisFinite finite
1931 	#elif defined(_MSC_VER)
1932 	#define SCIPisFinite _finite
1933 	#else
1934 	#define SCIPisFinite(x) ((x) == (x))
1935 	#endif
1936 	
1937 	/* In debug mode, the following methods are implemented as function calls to ensure
1938 	 * type validity.
1939 	 */
1940 	
1941 	/** returns the relative difference: (val1-val2)/max(|val1|,|val2|,1.0) */
1942 	SCIP_EXPORT
1943 	SCIP_Real SCIPrelDiff(
1944 	   SCIP_Real             val1,               /**< first value to be compared */
1945 	   SCIP_Real             val2                /**< second value to be compared */
1946 	   );
1947 	
1948 	#ifdef NDEBUG
1949 	
1950 	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1951 	 * speed up the algorithms.
1952 	 */
1953 	
1954 	#define SCIPrelDiff(val1, val2)         ( ((val1)-(val2))/(MAX3(1.0,REALABS(val1),REALABS(val2))) )
1955 	
1956 	#endif
1957 	
1958 	/** computes the gap from the primal and the dual bound */
1959 	SCIP_EXPORT
1960 	SCIP_Real SCIPcomputeGap(
1961 	   SCIP_Real             eps,                /**< the value treated as zero */
1962 	   SCIP_Real             inf,                /**< the value treated as infinity */
1963 	   SCIP_Real             primalbound,        /**< the primal bound */
1964 	   SCIP_Real             dualbound           /**< the dual bound */
1965 	   );
1966 	
1967 	/**@} */
1968 	
1969 	
1970 	/*
1971 	 * Random Numbers
1972 	 */
1973 	
1974 	/**@defgroup RandomNumbers Random Numbers
1975 	 * @ingroup MiscellaneousMethods
1976 	 * @brief structures and methods for pseudo random number generation
1977 	 *
1978 	 *@{
1979 	 */
1980 	
1981 	/** returns a random integer between minrandval and maxrandval
1982 	 *
1983 	 *  @deprecated Please use SCIPrandomGetInt() to request a random integer.
1984 	 */
1985 	SCIP_EXPORT
1986 	SCIP_DEPRECATED
1987 	int SCIPgetRandomInt(
1988 	   int                   minrandval,         /**< minimal value to return */
1989 	   int                   maxrandval,         /**< maximal value to return */
1990 	   unsigned int*         seedp               /**< pointer to seed value */
1991 	   );
1992 	
1993 	
1994 	/** returns a random integer between minrandval and maxrandval */
1995 	SCIP_EXPORT
1996 	int SCIPrandomGetInt(
1997 	   SCIP_RANDNUMGEN*      randgen,            /**< random number generator data */
1998 	   int                   minrandval,         /**< minimal value to return */
1999 	   int                   maxrandval          /**< maximal value to return */
2000 	   );
2001 	
2002 	/** draws a random subset of disjoint elements from a given set of disjoint elements;
2003 	 *  this implementation is suited for the case that nsubelems is considerably smaller then nelems
2004 	 */
2005 	SCIP_EXPORT
2006 	SCIP_RETCODE SCIPrandomGetSubset(
2007 	   SCIP_RANDNUMGEN*      randgen,            /**< random number generator */
2008 	   void**                set,                /**< original set, from which elements should be drawn */
2009 	   int                   nelems,             /**< number of elements in original set */
2010 	   void**                subset,             /**< subset in which drawn elements should be stored */
2011 	   int                   nsubelems           /**< number of elements that should be drawn and stored */
2012 	   );
2013 	
2014 	/** returns a random real between minrandval and maxrandval */
2015 	SCIP_EXPORT
2016 	SCIP_Real SCIPrandomGetReal(
2017 	   SCIP_RANDNUMGEN*      randgen,            /**< random number generator data */
2018 	   SCIP_Real             minrandval,         /**< minimal value to return */
2019 	   SCIP_Real             maxrandval          /**< maximal value to return */
2020 	   );
2021 	
2022 	/** returns a random real between minrandval and maxrandval
2023 	 *
2024 	 *  @deprecated Please use SCIPrandomGetReal() to request a random real.
2025 	 */
2026 	SCIP_EXPORT
2027 	SCIP_DEPRECATED
2028 	SCIP_Real SCIPgetRandomReal(
2029 	   SCIP_Real             minrandval,         /**< minimal value to return */
2030 	   SCIP_Real             maxrandval,         /**< maximal value to return */
2031 	   unsigned int*         seedp               /**< pointer to seed value */
2032 	   );
2033 	
2034 	/** draws a random subset of disjoint elements from a given set of disjoint elements;
2035 	 *  this implementation is suited for the case that nsubelems is considerably smaller then nelems
2036 	 *
2037 	 *  @deprecated Please use SCIPrandomGetSubset()
2038 	 */
2039 	SCIP_EXPORT
2040 	SCIP_DEPRECATED
2041 	SCIP_RETCODE SCIPgetRandomSubset(
2042 	   void**                set,                /**< original set, from which elements should be drawn */
2043 	   int                   nelems,             /**< number of elements in original set */
2044 	   void**                subset,             /**< subset in which drawn elements should be stored */
2045 	   int                   nsubelems,          /**< number of elements that should be drawn and stored */
2046 	   unsigned int          randseed            /**< seed value for random generator */
2047 	   );
2048 	
2049 	/**@} */
2050 	
2051 	/*
2052 	 * Permutations / Shuffling
2053 	 */
2054 	
2055 	/**@defgroup PermutationsShuffling Permutations Shuffling
2056 	 * @ingroup MiscellaneousMethods
2057 	 * @brief methods for shuffling arrays
2058 	 *
2059 	 * @{
2060 	 */
2061 	
2062 	/** swaps two ints */
2063 	SCIP_EXPORT
2064 	void SCIPswapInts(
2065 	   int*                  value1,             /**< pointer to first integer */
2066 	   int*                  value2              /**< pointer to second integer */
2067 	   );
2068 	
2069 	/** swaps two real values */
2070 	SCIP_EXPORT
2071 	void SCIPswapReals(
2072 	   SCIP_Real*            value1,             /**< pointer to first real value */
2073 	   SCIP_Real*            value2              /**< pointer to second real value */
2074 	);
2075 	
2076 	/** swaps the addresses of two pointers */
2077 	SCIP_EXPORT
2078 	void SCIPswapPointers(
2079 	   void**                pointer1,           /**< first pointer */
2080 	   void**                pointer2            /**< second pointer */
2081 	   );
2082 	
2083 	/** randomly shuffles parts of an integer array using the Fisher-Yates algorithm
2084 	 *
2085 	 *  @deprecated Please use SCIPrandomPermuteIntArray()
2086 	 */
2087 	SCIP_EXPORT
2088 	SCIP_DEPRECATED
2089 	void SCIPpermuteIntArray(
2090 	   int*                  array,              /**< array to be shuffled */
2091 	   int                   begin,              /**< first included index that should be subject to shuffling
2092 	                                              *   (0 for first array entry)
2093 	                                              */
2094 	   int                   end,                /**< first excluded index that should not be subject to shuffling
2095 	                                              *   (array size for last array entry)
2096 	                                              */
2097 	   unsigned int*         randseed            /**< seed value for the random generator */
2098 	   );
2099 	
2100 	/** randomly shuffles parts of an integer array using the Fisher-Yates algorithm */
2101 	SCIP_EXPORT
2102 	void SCIPrandomPermuteIntArray(
2103 	   SCIP_RANDNUMGEN*      randgen,            /**< random number generator */
2104 	   int*                  array,              /**< array to be shuffled */
2105 	   int                   begin,              /**< first included index that should be subject to shuffling
2106 	                                              *   (0 for first array entry)
2107 	                                              */
2108 	   int                   end                 /**< first excluded index that should not be subject to shuffling
2109 	                                              *   (array size for last array entry)
2110 	                                              */
2111 	   );
2112 	
2113 	/** randomly shuffles parts of an array using the Fisher-Yates algorithm */
2114 	SCIP_EXPORT
2115 	void SCIPrandomPermuteArray(
2116 	   SCIP_RANDNUMGEN*      randgen,            /**< random number generator */
2117 	   void**                array,              /**< array to be shuffled */
2118 	   int                   begin,              /**< first included index that should be subject to shuffling
2119 	                                              *   (0 for first array entry)
2120 	                                              */
2121 	   int                   end                 /**< first excluded index that should not be subject to shuffling
2122 	                                              *   (array size for last array entry)
2123 	                                              */
2124 	   );
2125 	
2126 	/** randomly shuffles parts of an array using the Fisher-Yates algorithm
2127 	 *
2128 	 *  @deprecated Please use SCIPrandomPermuteArray()
2129 	 */
2130 	SCIP_EXPORT
2131 	SCIP_DEPRECATED
2132 	void SCIPpermuteArray(
2133 	   void**                array,              /**< array to be shuffled */
2134 	   int                   begin,              /**< first included index that should be subject to shuffling
2135 	                                              *   (0 for first array entry)
2136 	                                              */
2137 	   int                   end,                /**< first excluded index that should not be subject to shuffling
2138 	                                              *   (array size for last array entry)
2139 	                                              */
2140 	   unsigned int*         randseed            /**< pointer to seed value for the random generator */
2141 	   );
2142 	
2143 	/**@} */
2144 	
2145 	
2146 	/*
2147 	 * Arrays
2148 	 */
2149 	
2150 	/**@defgroup Arrays Arrays
2151 	 * @ingroup MiscellaneousMethods
2152 	 * @brief miscellaneous methods for arrays
2153 	 *
2154 	 * @{
2155 	 */
2156 	
2157 	
2158 	/** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly
2159 	 *
2160 	 * @deprecated Switch to SCIPcomputeArraysIntersectionInt().
2161 	 */
2162 	SCIP_DEPRECATED
2163 	SCIP_EXPORT
2164 	SCIP_RETCODE SCIPcomputeArraysIntersection(
2165 	   int*                  array1,             /**< first array (in ascending order) */
2166 	   int                   narray1,            /**< number of entries of first array */
2167 	   int*                  array2,             /**< second array (in ascending order) */
2168 	   int                   narray2,            /**< number of entries of second array */
2169 	   int*                  intersectarray,     /**< intersection of array1 and array2
2170 	                                              *   (note: it is possible to use array1 for this input argument) */
2171 	   int*                  nintersectarray     /**< pointer to store number of entries of intersection array
2172 	                                              *   (note: it is possible to use narray1 for this input argument) */
2173 	   );
2174 	
2175 	/** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly */
2176 	SCIP_EXPORT
2177 	void SCIPcomputeArraysIntersectionInt(
2178 	   int*                  array1,             /**< first array (in ascending order) */
2179 	   int                   narray1,            /**< number of entries of first array */
2180 	   int*                  array2,             /**< second array (in ascending order) */
2181 	   int                   narray2,            /**< number of entries of second array */
2182 	   int*                  intersectarray,     /**< intersection of array1 and array2
2183 	                                              *   (note: it is possible to use array1 for this input argument) */
2184 	   int*                  nintersectarray     /**< pointer to store number of entries of intersection array
2185 	                                              *   (note: it is possible to use narray1 for this input argument) */
2186 	   );
2187 	
2188 	/** computes set intersection (duplicates removed) of two void-pointer arrays that are ordered ascendingly */
2189 	SCIP_EXPORT
2190 	void SCIPcomputeArraysIntersectionPtr(
2191 	   void**                array1,             /**< first array (in ascending order) */
2192 	   int                   narray1,            /**< number of entries of first array */
2193 	   void**                array2,             /**< second array (in ascending order) */
2194 	   int                   narray2,            /**< number of entries of second array */
2195 	   SCIP_DECL_SORTPTRCOMP((*ptrcomp)),        /**< data element comparator */
2196 	   void**                intersectarray,     /**< intersection of array1 and array2
2197 	                                              *   (note: it is possible to use array1 for this input argument) */
2198 	   int*                  nintersectarray     /**< pointer to store number of entries of intersection array
2199 	                                              *   (note: it is possible to use narray1 for this input argument) */
2200 	);
2201 	
2202 	/** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly
2203 	 *
2204 	 * @deprecated Switch to SCIPcomputeArraysSetminusInt().
2205 	 */
2206 	SCIP_DEPRECATED
2207 	SCIP_EXPORT
2208 	SCIP_RETCODE SCIPcomputeArraysSetminus(
2209 	   int*                  array1,             /**< first array (in ascending order) */
2210 	   int                   narray1,            /**< number of entries of first array */
2211 	   int*                  array2,             /**< second array (in ascending order) */
2212 	   int                   narray2,            /**< number of entries of second array */
2213 	   int*                  setminusarray,      /**< array to store entries of array1 that are not an entry of array2
2214 	                                              *   (note: it is possible to use array1 for this input argument) */
2215 	   int*                  nsetminusarray      /**< pointer to store number of entries of setminus array
2216 	                                              *   (note: it is possible to use narray1 for this input argument) */
2217 	   );
2218 	
2219 	/** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly */
2220 	SCIP_EXPORT
2221 	void SCIPcomputeArraysSetminusInt(
2222 	   int*                  array1,             /**< first array (in ascending order) */
2223 	   int                   narray1,            /**< number of entries of first array */
2224 	   int*                  array2,             /**< second array (in ascending order) */
2225 	   int                   narray2,            /**< number of entries of second array */
2226 	   int*                  setminusarray,      /**< array to store entries of array1 that are not an entry of array2
2227 	                                              *   (note: it is possible to use array1 for this input argument) */
2228 	   int*                  nsetminusarray      /**< pointer to store number of entries of setminus array
2229 	                                              *   (note: it is possible to use narray1 for this input argument) */
2230 	   );
2231 	
2232 	/**@} */
2233 	
2234 	
2235 	/*
2236 	 * Strings
2237 	 */
2238 	
2239 	/**@defgroup StringMethods String Methods
2240 	 * @ingroup MiscellaneousMethods
2241 	 * @brief commonly used methods for strings
2242 	 *
2243 	 *@{
2244 	 */
2245 	
2246 	/** copies characters from 'src' to 'dest', copying is stopped when either the 'stop' character is reached or after
2247 	 *  'cnt' characters have been copied, whichever comes first.
2248 	 *
2249 	 *  @note undefined behaviuor on overlapping arrays
2250 	 */
2251 	SCIP_EXPORT
2252 	int SCIPmemccpy(
2253 	   char*                 dest,               /**< destination pointer to copy to */
2254 	   const char*           src,                /**< source pointer to copy to */
2255 	   char                  stop,               /**< character when found stop copying */
2256 	   unsigned int          cnt                 /**< maximal number of characters to copy too */
2257 	   );
2258 	
2259 	/** prints an error message containing of the given string followed by a string describing the current system error;
2260 	 *  prefers to use the strerror_r method, which is threadsafe; on systems where this method does not exist,
2261 	 *  NO_STRERROR_R should be defined (see INSTALL), in this case, srerror is used which is not guaranteed to be
2262 	 *  threadsafe (on SUN-systems, it actually is)
2263 	 */
2264 	SCIP_EXPORT
2265 	void SCIPprintSysError(
2266 	   const char*           message             /**< first part of the error message, e.g. the filename */
2267 	   );
2268 	
2269 	/** extracts tokens from strings - wrapper method for strtok_r() */
2270 	SCIP_EXPORT
2271 	char* SCIPstrtok(
2272 	   char*                 s,                  /**< string to parse */
2273 	   const char*           delim,              /**< delimiters for parsing */
2274 	   char**                ptrptr              /**< pointer to working char pointer - must stay the same while parsing */
2275 	   );
2276 	
2277 	/** translates the given string into a string where symbols ", ', and spaces are escaped with a \ prefix */
2278 	SCIP_EXPORT
2279 	void SCIPescapeString(
2280 	   char*                 t,                  /**< target buffer to store escaped string */
2281 	   int                   bufsize,            /**< size of buffer t */
2282 	   const char*           s                   /**< string to transform into escaped string */
2283 	   );
2284 	
2285 	/** increases string pointer as long as it refers to a space character or an explicit space control sequence */
2286 	SCIP_EXPORT
2287 	SCIP_RETCODE SCIPskipSpace(
2288 	   char**                s                   /**< pointer to string pointer */
2289 	   );
2290 	
2291 	/** safe version of snprintf */
2292 	SCIP_EXPORT
2293 	int SCIPsnprintf(
2294 	   char*                 t,                  /**< target string */
2295 	   int                   len,                /**< length of the string to copy */
2296 	   const char*           s,                  /**< source string */
2297 	   ...                                       /**< further parameters */
2298 	   );
2299 	
2300 	/** safe version of strncpy
2301 	 *
2302 	 *  Copies string in s to t using at most @a size-1 nonzero characters (strncpy copies size characters). It always adds
2303 	 *  a terminating zero char. Does not pad the remaining string with zero characters (unlike strncpy). Returns the number
2304 	 *  of copied nonzero characters, if the length of s is at most size - 1, and returns size otherwise. Thus, the original
2305 	 *  string was truncated if the return value is size.
2306 	 */
2307 	SCIP_EXPORT
2308 	int SCIPstrncpy(
2309 	   char*                 t,                  /**< target string */
2310 	   const char*           s,                  /**< source string */
2311 	   int                   size                /**< maximal size of t */
2312 	   );
2313 	
2314 	/** extract the next token as a integer value if it is one; in case no value is parsed the endptr is set to @p str
2315 	 *
2316 	 *  @return Returns TRUE if a value could be extracted, otherwise FALSE
2317 	 */
2318 	SCIP_EXPORT
2319 	SCIP_Bool SCIPstrToIntValue(
2320 	   const char*           str,                /**< string to search */
2321 	   int*                  value,              /**< pointer to store the parsed value */
2322 	   char**                endptr              /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2323 	   );
2324 	
2325 	/** extract the next token as a double value if it is one; in case a value is parsed the endptr is set to @p str
2326 	 *
2327 	 *  @return Returns TRUE if a value could be extracted, otherwise FALSE
2328 	 */
2329 	SCIP_EXPORT
2330 	SCIP_Bool SCIPstrToRealValue(
2331 	   const char*           str,                /**< string to search */
2332 	   SCIP_Real*            value,              /**< pointer to store the parsed value */
2333 	   char**                endptr              /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2334 	   );
2335 	
2336 	/** copies the first size characters between a start and end character of str into token, if no error occurred endptr
2337 	 *  will point to the position after the read part, otherwise it will point to @p str
2338 	 */
2339 	SCIP_EXPORT
2340 	void SCIPstrCopySection(
2341 	   const char*           str,                /**< string to search */
2342 	   char                  startchar,          /**< character which defines the beginning */
2343 	   char                  endchar,            /**< character which defines the ending */
2344 	   char*                 token,              /**< string to store the copy */
2345 	   int                   size,               /**< size of the token char array */
2346 	   char**                endptr              /**< pointer to store the final string position if successfully parsed, otherwise @p str */
2347 	   );
2348 	
2349 	/** checks whether a given string t appears at the beginning of the string s (up to spaces at beginning) */
2350 	SCIP_EXPORT
2351 	SCIP_Bool SCIPstrAtStart(
2352 	   const char*           s,                  /**< string to search in */
2353 	   const char*           t,                  /**< string to search for */
2354 	   size_t                tlen                /**< length of t */
2355 	);
2356 	
2357 	/**@} */
2358 	
2359 	/*
2360 	 * File methods
2361 	 */
2362 	
2363 	/**@defgroup FileMethods File Methods
2364 	 * @ingroup MiscellaneousMethods
2365 	 * @brief commonly used file methods
2366 	 *
2367 	 * @{
2368 	 */
2369 	
2370 	/** returns, whether the given file exists */
2371 	SCIP_EXPORT
2372 	SCIP_Bool SCIPfileExists(
2373 	   const char*           filename            /**< file name */
2374 	   );
2375 	
2376 	/** splits filename into path, name, and extension */
2377 	SCIP_EXPORT
2378 	void SCIPsplitFilename(
2379 	   char*                 filename,           /**< filename to split; is destroyed (but not freed) during process */
2380 	   char**                path,               /**< pointer to store path, or NULL if not needed */
2381 	   char**                name,               /**< pointer to store name, or NULL if not needed */
2382 	   char**                extension,          /**< pointer to store extension, or NULL if not needed */
2383 	   char**                compression         /**< pointer to store compression extension, or NULL if not needed */
2384 	   );
2385 	
2386 	/**@} */
2387 	
2388 	#ifdef __cplusplus
2389 	}
2390 	#endif
2391 	
2392 	#endif
2393