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   scip_datastructures.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public methods for data structures
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Thorsten Koch
31   	 * @author Alexander Martin
32   	 * @author Marc Pfetsch
33   	 * @author Kati Wolter
34   	 * @author Gregor Hendel
35   	 * @author Leona Gottwald
36   	 */
37   	
38   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39   	
40   	#ifndef __SCIP_SCIP_DATASTRUCTURES_H__
41   	#define __SCIP_SCIP_DATASTRUCTURES_H__
42   	
43   	
44   	#include "scip/def.h"
45   	#include "scip/type_misc.h"
46   	#include "scip/type_retcode.h"
47   	#include "scip/type_scip.h"
48   	
49   	#ifdef __cplusplus
50   	extern "C" {
51   	#endif
52   	
53   	/**@addtogroup PublicDynamicArrayMethods
54   	 *
55   	 * @{
56   	 */
57   	
58   	/** creates a dynamic array of real values
59   	 *
60   	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
61   	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
62   	 */
63   	SCIP_EXPORT
64   	SCIP_RETCODE SCIPcreateRealarray(
65   	   SCIP*                 scip,               /**< SCIP data structure */
66   	   SCIP_REALARRAY**      realarray           /**< pointer to store the real array */
67   	   );
68   	
69   	/** frees a dynamic array of real values
70   	 *
71   	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
72   	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
73   	 */
74   	SCIP_EXPORT
75   	SCIP_RETCODE SCIPfreeRealarray(
76   	   SCIP*                 scip,               /**< SCIP data structure */
77   	   SCIP_REALARRAY**      realarray           /**< pointer to the real array */
78   	   );
79   	
80   	/** extends dynamic array to be able to store indices from minidx to maxidx
81   	 *
82   	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
83   	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
84   	 */
85   	SCIP_EXPORT
86   	SCIP_RETCODE SCIPextendRealarray(
87   	   SCIP*                 scip,               /**< SCIP data structure */
88   	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
89   	   int                   minidx,             /**< smallest index to allocate storage for */
90   	   int                   maxidx              /**< largest index to allocate storage for */
91   	   );
92   	
93   	/** clears a dynamic real array
94   	 *
95   	 *  @return clears a dynamic real array
96   	 */
97   	SCIP_EXPORT
98   	SCIP_RETCODE SCIPclearRealarray(
99   	   SCIP*                 scip,               /**< SCIP data structure */
100  	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
101  	   );
102  	
103  	/** gets value of entry in dynamic array */
104  	SCIP_EXPORT
105  	SCIP_Real SCIPgetRealarrayVal(
106  	   SCIP*                 scip,               /**< SCIP data structure */
107  	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
108  	   int                   idx                 /**< array index to get value for */
109  	   );
110  	
111  	/** sets value of entry in dynamic array
112  	 *
113  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
114  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
115  	 */
116  	SCIP_EXPORT
117  	SCIP_RETCODE SCIPsetRealarrayVal(
118  	   SCIP*                 scip,               /**< SCIP data structure */
119  	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
120  	   int                   idx,                /**< array index to set value for */
121  	   SCIP_Real             val                 /**< value to set array index to */
122  	   );
123  	
124  	/** increases value of entry in dynamic array
125  	 *
126  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
127  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
128  	 */
129  	SCIP_EXPORT
130  	SCIP_RETCODE SCIPincRealarrayVal(
131  	   SCIP*                 scip,               /**< SCIP data structure */
132  	   SCIP_REALARRAY*       realarray,          /**< dynamic real array */
133  	   int                   idx,                /**< array index to increase value for */
134  	   SCIP_Real             incval              /**< value to increase array index */
135  	   );
136  	
137  	/** returns the minimal index of all stored non-zero elements
138  	 *
139  	 *  @return the minimal index of all stored non-zero elements
140  	 */
141  	SCIP_EXPORT
142  	int SCIPgetRealarrayMinIdx(
143  	   SCIP*                 scip,               /**< SCIP data structure */
144  	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
145  	   );
146  	
147  	/** returns the maximal index of all stored non-zero elements
148  	 *
149  	 *  @return the maximal index of all stored non-zero elements
150  	 */
151  	SCIP_EXPORT
152  	int SCIPgetRealarrayMaxIdx(
153  	   SCIP*                 scip,               /**< SCIP data structure */
154  	   SCIP_REALARRAY*       realarray           /**< dynamic real array */
155  	   );
156  	
157  	/** creates a dynamic array of int values
158  	 *
159  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
160  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
161  	 */
162  	SCIP_EXPORT
163  	SCIP_RETCODE SCIPcreateIntarray(
164  	   SCIP*                 scip,               /**< SCIP data structure */
165  	   SCIP_INTARRAY**       intarray            /**< pointer to store the int array */
166  	   );
167  	
168  	/** frees a dynamic array of int values
169  	 *
170  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
171  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
172  	 */
173  	SCIP_EXPORT
174  	SCIP_RETCODE SCIPfreeIntarray(
175  	   SCIP*                 scip,               /**< SCIP data structure */
176  	   SCIP_INTARRAY**       intarray            /**< pointer to the int array */
177  	   );
178  	
179  	/** extends dynamic array to be able to store indices from minidx to maxidx
180  	 *
181  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
182  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
183  	 */
184  	SCIP_EXPORT
185  	SCIP_RETCODE SCIPextendIntarray(
186  	   SCIP*                 scip,               /**< SCIP data structure */
187  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
188  	   int                   minidx,             /**< smallest index to allocate storage for */
189  	   int                   maxidx              /**< largest index to allocate storage for */
190  	   );
191  	
192  	/** clears a dynamic int array
193  	 *
194  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
195  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
196  	 */
197  	SCIP_EXPORT
198  	SCIP_RETCODE SCIPclearIntarray(
199  	   SCIP*                 scip,               /**< SCIP data structure */
200  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
201  	   );
202  	
203  	/** gets value of entry in dynamic array
204  	 *
205  	 *  @return value of entry in dynamic array
206  	 */
207  	SCIP_EXPORT
208  	int SCIPgetIntarrayVal(
209  	   SCIP*                 scip,               /**< SCIP data structure */
210  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
211  	   int                   idx                 /**< array index to get value for */
212  	   );
213  	
214  	/** sets value of entry in dynamic array
215  	 *
216  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
217  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
218  	 */
219  	SCIP_EXPORT
220  	SCIP_RETCODE SCIPsetIntarrayVal(
221  	   SCIP*                 scip,               /**< SCIP data structure */
222  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
223  	   int                   idx,                /**< array index to set value for */
224  	   int                   val                 /**< value to set array index to */
225  	   );
226  	
227  	/** increases value of entry in dynamic array
228  	 *
229  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
230  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
231  	 */
232  	SCIP_EXPORT
233  	SCIP_RETCODE SCIPincIntarrayVal(
234  	   SCIP*                 scip,               /**< SCIP data structure */
235  	   SCIP_INTARRAY*        intarray,           /**< dynamic int array */
236  	   int                   idx,                /**< array index to increase value for */
237  	   int                   incval              /**< value to increase array index */
238  	   );
239  	
240  	/** returns the minimal index of all stored non-zero elements
241  	 *
242  	 *  @return the minimal index of all stored non-zero elements
243  	 */
244  	SCIP_EXPORT
245  	int SCIPgetIntarrayMinIdx(
246  	   SCIP*                 scip,               /**< SCIP data structure */
247  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
248  	   );
249  	
250  	/** returns the maximal index of all stored non-zero elements
251  	 *
252  	 *  @return the maximal index of all stored non-zero elements
253  	 */
254  	SCIP_EXPORT
255  	int SCIPgetIntarrayMaxIdx(
256  	   SCIP*                 scip,               /**< SCIP data structure */
257  	   SCIP_INTARRAY*        intarray            /**< dynamic int array */
258  	   );
259  	
260  	/** creates a dynamic array of bool values
261  	 *
262  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
263  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
264  	 */
265  	SCIP_EXPORT
266  	SCIP_RETCODE SCIPcreateBoolarray(
267  	   SCIP*                 scip,               /**< SCIP data structure */
268  	   SCIP_BOOLARRAY**      boolarray           /**< pointer to store the bool array */
269  	   );
270  	
271  	/** frees a dynamic array of bool values
272  	 *
273  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
274  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
275  	 */
276  	SCIP_EXPORT
277  	SCIP_RETCODE SCIPfreeBoolarray(
278  	   SCIP*                 scip,               /**< SCIP data structure */
279  	   SCIP_BOOLARRAY**      boolarray           /**< pointer to the bool array */
280  	   );
281  	
282  	/** extends dynamic array to be able to store indices from minidx to maxidx
283  	 *
284  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
285  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
286  	 */
287  	SCIP_EXPORT
288  	SCIP_RETCODE SCIPextendBoolarray(
289  	   SCIP*                 scip,               /**< SCIP data structure */
290  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
291  	   int                   minidx,             /**< smallest index to allocate storage for */
292  	   int                   maxidx              /**< largest index to allocate storage for */
293  	   );
294  	
295  	/** clears a dynamic bool array
296  	 *
297  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
298  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
299  	 */
300  	SCIP_EXPORT
301  	SCIP_RETCODE SCIPclearBoolarray(
302  	   SCIP*                 scip,               /**< SCIP data structure */
303  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
304  	   );
305  	
306  	/** gets value of entry in dynamic array
307  	 *
308  	 *  @return value of entry in dynamic array at position idx
309  	 */
310  	SCIP_EXPORT
311  	SCIP_Bool SCIPgetBoolarrayVal(
312  	   SCIP*                 scip,               /**< SCIP data structure */
313  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
314  	   int                   idx                 /**< array index to get value for */
315  	   );
316  	
317  	/** sets value of entry in dynamic array
318  	 *
319  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
320  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
321  	 */
322  	SCIP_EXPORT
323  	SCIP_RETCODE SCIPsetBoolarrayVal(
324  	   SCIP*                 scip,               /**< SCIP data structure */
325  	   SCIP_BOOLARRAY*       boolarray,          /**< dynamic bool array */
326  	   int                   idx,                /**< array index to set value for */
327  	   SCIP_Bool             val                 /**< value to set array index to */
328  	   );
329  	
330  	/** returns the minimal index of all stored non-zero elements
331  	 *
332  	 *  @return the minimal index of all stored non-zero elements
333  	 */
334  	SCIP_EXPORT
335  	int SCIPgetBoolarrayMinIdx(
336  	   SCIP*                 scip,               /**< SCIP data structure */
337  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
338  	   );
339  	
340  	/** returns the maximal index of all stored non-zero elements
341  	 *
342  	 *  @return the maximal index of all stored non-zero elements
343  	 */
344  	SCIP_EXPORT
345  	int SCIPgetBoolarrayMaxIdx(
346  	   SCIP*                 scip,               /**< SCIP data structure */
347  	   SCIP_BOOLARRAY*       boolarray           /**< dynamic bool array */
348  	   );
349  	
350  	/** creates a dynamic array of pointers
351  	 *
352  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
353  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
354  	 */
355  	SCIP_EXPORT
356  	SCIP_RETCODE SCIPcreatePtrarray(
357  	   SCIP*                 scip,               /**< SCIP data structure */
358  	   SCIP_PTRARRAY**       ptrarray            /**< pointer to store the int array */
359  	   );
360  	
361  	/** frees a dynamic array of pointers
362  	 *
363  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
364  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
365  	 */
366  	SCIP_EXPORT
367  	SCIP_RETCODE SCIPfreePtrarray(
368  	   SCIP*                 scip,               /**< SCIP data structure */
369  	   SCIP_PTRARRAY**       ptrarray            /**< pointer to the int array */
370  	   );
371  	
372  	/** extends dynamic array to be able to store indices from minidx to maxidx
373  	 *
374  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
375  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
376  	 */
377  	SCIP_EXPORT
378  	SCIP_RETCODE SCIPextendPtrarray(
379  	   SCIP*                 scip,               /**< SCIP data structure */
380  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic int array */
381  	   int                   minidx,             /**< smallest index to allocate storage for */
382  	   int                   maxidx              /**< largest index to allocate storage for */
383  	   );
384  	
385  	/** clears a dynamic pointer array
386  	 *
387  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
388  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
389  	 */
390  	SCIP_EXPORT
391  	SCIP_RETCODE SCIPclearPtrarray(
392  	   SCIP*                 scip,               /**< SCIP data structure */
393  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic int array */
394  	   );
395  	
396  	/** gets value of entry in dynamic array */
397  	SCIP_EXPORT
398  	void* SCIPgetPtrarrayVal(
399  	   SCIP*                 scip,               /**< SCIP data structure */
400  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic int array */
401  	   int                   idx                 /**< array index to get value for */
402  	   );
403  	
404  	/** sets value of entry in dynamic array
405  	 *
406  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
407  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
408  	 */
409  	SCIP_EXPORT
410  	SCIP_RETCODE SCIPsetPtrarrayVal(
411  	   SCIP*                 scip,               /**< SCIP data structure */
412  	   SCIP_PTRARRAY*        ptrarray,           /**< dynamic int array */
413  	   int                   idx,                /**< array index to set value for */
414  	   void*                 val                 /**< value to set array index to */
415  	   );
416  	
417  	/** returns the minimal index of all stored non-zero elements
418  	 *
419  	 *  @return the minimal index of all stored non-zero elements
420  	 */
421  	SCIP_EXPORT
422  	int SCIPgetPtrarrayMinIdx(
423  	   SCIP*                 scip,               /**< SCIP data structure */
424  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
425  	   );
426  	
427  	/** returns the maximal index of all stored non-zero elements
428  	 *
429  	 *  @return the maximal index of all stored non-zero elements
430  	 */
431  	SCIP_EXPORT
432  	int SCIPgetPtrarrayMaxIdx(
433  	   SCIP*                 scip,               /**< SCIP data structure */
434  	   SCIP_PTRARRAY*        ptrarray            /**< dynamic ptr array */
435  	   );
436  	
437  	/**@} */
438  	
439  	/**@addtogroup DisjointSet
440  	 *
441  	 * @{
442  	 */
443  	
444  	/** creates a disjoint set (union find) structure \p djset for \p ncomponents many components (of size one) */
445  	SCIP_EXPORT
446  	SCIP_RETCODE SCIPcreateDisjointset(
447  	   SCIP*                 scip,               /**< SCIP data structure */
448  	   SCIP_DISJOINTSET**    djset,              /**< disjoint set (union find) data structure */
449  	   int                   ncomponents         /**< number of components */
450  	   );
451  	
452  	/** frees the disjoint set (union find) data structure */
453  	SCIP_EXPORT
454  	void SCIPfreeDisjointset(
455  	   SCIP*                 scip,               /**< SCIP data structure */
456  	   SCIP_DISJOINTSET**    djset               /**< pointer to disjoint set (union find) data structure */
457  	   );
458  	
459  	/** @} */
460  	
461  	/**@addtogroup DirectedGraph
462  	 *
463  	 * @{
464  	 */
465  	
466  	/** creates directed graph structure */
467  	SCIP_EXPORT
468  	SCIP_RETCODE SCIPcreateDigraph(
469  	   SCIP*                 scip,               /**< SCIP data structure */
470  	   SCIP_DIGRAPH**        digraph,            /**< pointer to store the created directed graph */
471  	   int                   nnodes              /**< number of nodes */
472  	   );
473  	
474  	/**! [SnippetCodeStyleComment] */
475  	
476  	/** copies directed graph structure
477  	 *
478  	 *  The copying procedure uses the memory of the passed SCIP instance. The user must ensure that the digraph lives
479  	 *  as most as long as the SCIP instance.
480  	 *
481  	 *  @note The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
482  	 */
483  	SCIP_EXPORT
484  	SCIP_RETCODE SCIPcopyDigraph(
485  	   SCIP*                 scip,               /**< SCIP data structure */
486  	   SCIP_DIGRAPH**        targetdigraph,      /**< pointer to store the copied directed graph */
487  	   SCIP_DIGRAPH*         sourcedigraph       /**< source directed graph */
488  	   );
489  	
490  	/**! [SnippetCodeStyleComment] */
491  	/**@} */
492  	
493  	#ifdef __cplusplus
494  	}
495  	#endif
496  	
497  	#endif
498