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   misc.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  internal miscellaneous methods
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_MISC_H__
34   	#define __SCIP_MISC_H__
35   	
36   	
37   	#include "scip/def.h"
38   	#include "blockmemshell/memory.h"
39   	#include "scip/type_retcode.h"
40   	#include "scip/type_set.h"
41   	#include "scip/type_misc.h"
42   	#include "scip/pub_misc.h"
43   	
44   	#ifdef __cplusplus
45   	extern "C" {
46   	#endif
47   	
48   	/*
49   	 * Dynamic Arrays
50   	 */
51   	
52   	/** creates a dynamic array of real values */
53   	SCIP_RETCODE SCIPrealarrayCreate(
54   	   SCIP_REALARRAY**      realarray,          /**< pointer to store the real array */
55   	   BMS_BLKMEM*           blkmem              /**< block memory */
56   	   );
57   	
58   	/** creates a copy of a dynamic array of real values */
59   	SCIP_RETCODE SCIPrealarrayCopy(
60   	   SCIP_REALARRAY**      realarray,          /**< pointer to store the copied real array */
61   	   BMS_BLKMEM*           blkmem,             /**< block memory */
62   	   SCIP_REALARRAY*       sourcerealarray     /**< dynamic real array to copy */
63   	   );
64   	
65   	/** frees a dynamic array of real values */
66   	SCIP_RETCODE SCIPrealarrayFree(
67   	   SCIP_REALARRAY**      realarray           /**< pointer to the real array */
68   	   );
69   	
70   	/** extends dynamic array to be able to store indices from minidx to maxidx */
71   	SCIP_RETCODE SCIPrealarrayExtend(
72   	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
73   	   int                   arraygrowinit,      /**< initial size of array */
74   	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
75   	   int                   minidx,             /**< smallest index to allocate storage for */
76   	   int                   maxidx              /**< largest index to allocate storage for */
77   	   );
78   	
79   	/** clears a dynamic real array */
80   	SCIP_RETCODE SCIPrealarrayClear(
81   	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
82   	   );
83   	
84   	/** gets value of entry in dynamic array */
85   	SCIP_Real SCIPrealarrayGetVal(
86   	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
87   	   int                   idx                 /**< array index to get value for */
88   	   );
89   	
90   	/** sets value of entry in dynamic array */
91   	SCIP_RETCODE SCIPrealarraySetVal(
92   	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
93   	   int                   arraygrowinit,      /**< initial size of array */
94   	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
95   	   int                   idx,                /**< array index to set value for */
96   	   SCIP_Real             val                 /**< value to set array index to */
97   	   );
98   	
99   	/** increases value of entry in dynamic array */
100  	SCIP_RETCODE SCIPrealarrayIncVal(
101  	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
102  	   int                   arraygrowinit,      /**< initial size of array */
103  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
104  	   int                   idx,                /**< array index to increase value for */
105  	   SCIP_Real             incval              /**< value to increase array index */
106  	   );
107  	
108  	/** returns the minimal index of all stored non-zero elements */
109  	int SCIPrealarrayGetMinIdx(
110  	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
111  	   );
112  	
113  	/** returns the maximal index of all stored non-zero elements */
114  	int SCIPrealarrayGetMaxIdx(
115  	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
116  	   );
117  	
118  	/** creates a dynamic array of int values */
119  	SCIP_RETCODE SCIPintarrayCreate(
120  	   SCIP_INTARRAY**       intarray,           /**< pointer to store the int array */
121  	   BMS_BLKMEM*           blkmem              /**< block memory */
122  	   );
123  	
124  	/** creates a copy of a dynamic array of int values */
125  	SCIP_RETCODE SCIPintarrayCopy(
126  	   SCIP_INTARRAY**       intarray,           /**< pointer to store the copied int array */
127  	   BMS_BLKMEM*           blkmem,             /**< block memory */
128  	   SCIP_INTARRAY*        sourceintarray      /**< dynamic int array to copy */
129  	   );
130  	
131  	/** frees a dynamic array of int values */
132  	SCIP_RETCODE SCIPintarrayFree(
133  	   SCIP_INTARRAY**       intarray            /**< pointer to the int array */
134  	   );
135  	
136  	/** extends dynamic array to be able to store indices from minidx to maxidx */
137  	SCIP_RETCODE SCIPintarrayExtend(
138  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
139  	   int                   arraygrowinit,      /**< initial size of array */
140  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
141  	   int                   minidx,             /**< smallest index to allocate storage for */
142  	   int                   maxidx              /**< largest index to allocate storage for */
143  	   );
144  	
145  	/** clears a dynamic int array */
146  	SCIP_RETCODE SCIPintarrayClear(
147  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
148  	   );
149  	
150  	/** gets value of entry in dynamic array */
151  	int SCIPintarrayGetVal(
152  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
153  	   int                   idx                 /**< array index to get value for */
154  	   );
155  	
156  	/** sets value of entry in dynamic array */
157  	SCIP_RETCODE SCIPintarraySetVal(
158  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
159  	   int                   arraygrowinit,      /**< initial size of array */
160  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
161  	   int                   idx,                /**< array index to set value for */
162  	   int                   val                 /**< value to set array index to */
163  	   );
164  	
165  	/** increases value of entry in dynamic array */
166  	SCIP_RETCODE SCIPintarrayIncVal(
167  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
168  	   int                   arraygrowinit,      /**< initial size of array */
169  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
170  	   int                   idx,                /**< array index to increase value for */
171  	   int                   incval              /**< value to increase array index */
172  	   );
173  	
174  	/** returns the minimal index of all stored non-zero elements */
175  	int SCIPintarrayGetMinIdx(
176  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
177  	   );
178  	
179  	/** returns the maximal index of all stored non-zero elements */
180  	int SCIPintarrayGetMaxIdx(
181  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
182  	   );
183  	
184  	/** creates a dynamic array of bool values */
185  	SCIP_RETCODE SCIPboolarrayCreate(
186  	   SCIP_BOOLARRAY**      boolarray,          /**< pointer to store the bool array */
187  	   BMS_BLKMEM*           blkmem              /**< block memory */
188  	   );
189  	
190  	/** creates a copy of a dynamic array of bool values */
191  	SCIP_RETCODE SCIPboolarrayCopy(
192  	   SCIP_BOOLARRAY**      boolarray,          /**< pointer to store the copied bool array */
193  	   BMS_BLKMEM*           blkmem,             /**< block memory */
194  	   SCIP_BOOLARRAY*       sourceboolarray     /**< dynamic bool array to copy */
195  	   );
196  	
197  	/** frees a dynamic array of bool values */
198  	SCIP_RETCODE SCIPboolarrayFree(
199  	   SCIP_BOOLARRAY**      boolarray           /**< pointer to the bool array */
200  	   );
201  	
202  	/** extends dynamic array to be able to store indices from minidx to maxidx */
203  	SCIP_RETCODE SCIPboolarrayExtend(
204  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
205  	   int                   arraygrowinit,      /**< initial size of array */
206  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
207  	   int                   minidx,             /**< smallest index to allocate storage for */
208  	   int                   maxidx              /**< largest index to allocate storage for */
209  	   );
210  	
211  	/** clears a dynamic bool array */
212  	SCIP_RETCODE SCIPboolarrayClear(
213  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
214  	   );
215  	
216  	/** gets value of entry in dynamic array */
217  	SCIP_Bool SCIPboolarrayGetVal(
218  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
219  	   int                   idx                 /**< array index to get value for */
220  	   );
221  	
222  	/** sets value of entry in dynamic array */
223  	SCIP_RETCODE SCIPboolarraySetVal(
224  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
225  	   int                   arraygrowinit,      /**< initial size of array */
226  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
227  	   int                   idx,                /**< array index to set value for */
228  	   SCIP_Bool             val                 /**< value to set array index to */
229  	   );
230  	
231  	/** returns the minimal index of all stored non-zero elements */
232  	int SCIPboolarrayGetMinIdx(
233  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
234  	   );
235  	
236  	/** returns the maximal index of all stored non-zero elements */
237  	int SCIPboolarrayGetMaxIdx(
238  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
239  	   );
240  	
241  	/** creates a dynamic array of pointer values */
242  	SCIP_RETCODE SCIPptrarrayCreate(
243  	   SCIP_PTRARRAY**       ptrarray,           /**< pointer to store the ptr array */
244  	   BMS_BLKMEM*           blkmem              /**< block memory */
245  	   );
246  	
247  	/** creates a copy of a dynamic array of pointer values */
248  	SCIP_RETCODE SCIPptrarrayCopy(
249  	   SCIP_PTRARRAY**       ptrarray,           /**< pointer to store the copied ptr array */
250  	   BMS_BLKMEM*           blkmem,             /**< block memory */
251  	   SCIP_PTRARRAY*        sourceptrarray      /**< dynamic ptr array to copy */
252  	   );
253  	
254  	/** frees a dynamic array of pointer values */
255  	SCIP_RETCODE SCIPptrarrayFree(
256  	   SCIP_PTRARRAY**       ptrarray            /**< pointer to the ptr array */
257  	   );
258  	
259  	/** extends dynamic array to be able to store indices from minidx to maxidx */
260  	SCIP_RETCODE SCIPptrarrayExtend(
261  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
262  	   int                   arraygrowinit,      /**< initial size of array */
263  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
264  	   int                   minidx,             /**< smallest index to allocate storage for */
265  	   int                   maxidx              /**< largest index to allocate storage for */
266  	   );
267  	
268  	/** clears a dynamic pointer array */
269  	SCIP_RETCODE SCIPptrarrayClear(
270  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
271  	   );
272  	
273  	/** gets value of entry in dynamic array */
274  	void* SCIPptrarrayGetVal(
275  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
276  	   int                   idx                 /**< array index to get value for */
277  	   );
278  	
279  	/** sets value of entry in dynamic array */
280  	SCIP_RETCODE SCIPptrarraySetVal(
281  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic ptr array */
282  	   int                   arraygrowinit,      /**< initial size of array */
283  	   SCIP_Real             arraygrowfac,       /**< growing factor of array */
284  	   int                   idx,                /**< array index to set value for */
285  	   void*                 val                 /**< value to set array index to */
286  	   );
287  	
288  	/** returns the minimal index of all stored non-zero elements */
289  	int SCIPptrarrayGetMinIdx(
290  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
291  	   );
292  	
293  	/** returns the maximal index of all stored non-zero elements */
294  	int SCIPptrarrayGetMaxIdx(
295  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
296  	   );
297  	
298  	
299  	/* SCIP disjoint set data structure
300  	 *
301  	 * internal disjoint set functions (see \ref DisjointSet for public methods)
302  	 */
303  	
304  	/** creates a disjoint set (union find) structure \p djset for \p ncomponents many components (of size one) */
305  	SCIP_RETCODE SCIPdisjointsetCreate(
306  	   SCIP_DISJOINTSET**    djset,              /**< disjoint set (union find) data structure */
307  	   BMS_BLKMEM*           blkmem,             /**< block memory */
308  	   int                   ncomponents         /**< number of components */
309  	   );
310  	
311  	/** frees the disjoint set (union find) data structure */
312  	void SCIPdisjointsetFree(
313  	   SCIP_DISJOINTSET**    djset,              /**< pointer to disjoint set (union find) data structure */
314  	   BMS_BLKMEM*           blkmem              /**< block memory */
315  	   );
316  	
317  	
318  	/** SCIP digraph functions
319  	 *
320  	 * internal digraph functions (see \ref DirectedGraph for public digraph methods)
321  	 */
322  	
323  	/** creates directed graph structure */
324  	SCIP_RETCODE SCIPdigraphCreate(
325  	   SCIP_DIGRAPH**        digraph,            /**< pointer to store the created directed graph */
326  	   BMS_BLKMEM*           blkmem,             /**< block memory to store the data */
327  	   int                   nnodes              /**< number of nodes */
328  	   );
329  	
330  	/** copies directed graph structure
331  	 *
332  	 *  @note The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
333  	 */
334  	SCIP_RETCODE SCIPdigraphCopy(
335  	   SCIP_DIGRAPH**        targetdigraph,      /**< pointer to store the copied directed graph */
336  	   SCIP_DIGRAPH*         sourcedigraph,      /**< source directed graph */
337  	   BMS_BLKMEM*           targetblkmem        /**< block memory to store the target block memory, or NULL to use the same
338  	                                              *  the same block memory as used for the \p sourcedigraph */
339  	   );
340  	
341  	/*
342  	 * Additional math functions
343  	 */
344  	
345  	/** negates a number
346  	 *
347  	 * negation of a number that can be used to avoid that a negation is optimized away by a compiler
348  	 */
349  	SCIP_Real SCIPnegateReal(
350  	   SCIP_Real             x                   /**< value to negate */
351  	   );
352  	
353  	/** internal random number generator methods
354  	 *
355  	 * see \ref RandomNumbers for public random number generator methods
356  	 */
357  	
358  	/** creates and initializes a random number generator */
359  	SCIP_EXPORT
360  	SCIP_RETCODE SCIPrandomCreate(
361  	   SCIP_RANDNUMGEN**     randnumgen,         /**< random number generator */
362  	   BMS_BLKMEM*           blkmem,             /**< block memory */
363  	   unsigned int          initialseed         /**< initial random seed */
364  	   );
365  	
366  	/** frees a random number generator */
367  	SCIP_EXPORT
368  	void SCIPrandomFree(
369  	   SCIP_RANDNUMGEN**     randnumgen,         /**< random number generator */
370  	   BMS_BLKMEM*           blkmem              /**< block memory */
371  	   );
372  	
373  	/** initializes a random number generator with a given start seed */
374  	SCIP_EXPORT
375  	void SCIPrandomSetSeed(
376  	   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator */
377  	   unsigned int          initseed            /**< initial random seed */
378  	   );
379  	
380  	#ifdef __cplusplus
381  	}
382  	#endif
383  	
384  	#endif
385