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   struct_misc.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  miscellaneous datastructures
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_STRUCT_MISC_H__
34   	#define __SCIP_STRUCT_MISC_H__
35   	
36   	
37   	#include "scip/def.h"
38   	#include "blockmemshell/memory.h"
39   	#include "scip/type_misc.h"
40   	
41   	#ifdef __cplusplus
42   	extern "C" {
43   	#endif
44   	
45   	/** data structure for sparse solutions */
46   	struct SCIP_SparseSol
47   	{
48   	   SCIP_VAR**            vars;               /**< variables */
49   	   SCIP_Longint*         lbvalues;           /**< array of lower bounds */
50   	   SCIP_Longint*         ubvalues;           /**< array of upper bounds */
51   	   int                   nvars;              /**< number of variables */
52   	};
53   	
54   	typedef union {
55   	   void*                 ptr;                /**< pointer element */
56   	   unsigned int          uinteger;           /**< unsigned integer element */
57   	} SCIP_QUEUEELEMENT;
58   	
59   	/** (circular) Queue data structure */
60   	struct SCIP_Queue
61   	{
62   	   SCIP_Real             sizefac;            /**< memory growing factor */
63   	   SCIP_QUEUEELEMENT*    slots;              /**< array of element slots */
64   	   int                   firstfree;          /**< first free slot */
65   	   int                   firstused;          /**< first used slot */
66   	   int                   size;               /**< total number of available element slots */
67   	};
68   	
69   	/** priority queue data structure
70   	 *  Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
71   	 *  The ordering is done through a pointer comparison function.
72   	 *  The array is organized as follows. The root element (that is the "best" element \f$ r \f$ with \f$ r \leq x \f$ for all \f$ x \f$ )
73   	 *  is stored in position 0. The children of an element at position \f$ p \f$ are stored at positions \f$ q_1 = 2*p+1 \f$ and
74   	 *  \f$ q_2 = 2*p+2 \f$ . That means, the parent of the element at position \f$ q \f$ is at position \f$ p = (q-1)/2 \f$ .
75   	 *  At any time, the condition holds that \f$ p \leq q \f$ for each parent \f$ p \f$ and its children \f$ q \f$ .
76   	 *  Insertion and removal of single elements needs time \f$ O(log n) \f$ .
77   	 */
78   	struct SCIP_PQueue
79   	{
80   	   SCIP_Real             sizefac;            /**< memory growing factor */
81   	   SCIP_DECL_SORTPTRCOMP((*ptrcomp));        /**< compares two data elements */
82   	   SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos));/**< callback to act on position change of elem in priority queue, or NULL */
83   	   void**                slots;              /**< array of element slots */
84   	   int                   len;                /**< number of used element slots */
85   	   int                   size;               /**< total number of available element slots */
86   	};
87   	
88   	/** hash table data structure */
89   	struct SCIP_HashTable
90   	{
91   	   SCIP_DECL_HASHGETKEY((*hashgetkey));      /**< gets the key of the given element */
92   	   SCIP_DECL_HASHKEYEQ ((*hashkeyeq));       /**< returns TRUE iff both keys are equal */
93   	   SCIP_DECL_HASHKEYVAL((*hashkeyval));      /**< returns the hash value of the key */
94   	   BMS_BLKMEM*           blkmem;             /**< block memory used to store hash map entries */
95   	   void*                 userptr;            /**< user pointer */
96   	   void**                slots;              /**< slots of the hash table */
97   	   uint32_t*             hashes;             /**< hash values of elements stored in slots */
98   	   uint32_t              shift;              /**< power such that 2^(32-shift) == nslots */
99   	   uint32_t              mask;               /**< mask used for fast modulo, i.e. nslots - 1 */
100  	   uint32_t              nelements;          /**< number of elements in the hashtable */
101  	};
102  	
103  	/** element list to store single elements of a hash table */
104  	struct SCIP_MultiHashList
105  	{
106  	   void*                 element;            /**< this element */
107  	   SCIP_MULTIHASHLIST*   next;               /**< rest of the hash table list */
108  	};
109  	
110  	/** multihash table data structure */
111  	struct SCIP_MultiHash
112  	{
113  	   SCIP_DECL_HASHGETKEY((*hashgetkey));      /**< gets the key of the given element */
114  	   SCIP_DECL_HASHKEYEQ ((*hashkeyeq));       /**< returns TRUE iff both keys are equal */
115  	   SCIP_DECL_HASHKEYVAL((*hashkeyval));      /**< returns the hash value of the key */
116  	   BMS_BLKMEM*           blkmem;             /**< block memory used to store hash map entries */
117  	   SCIP_MULTIHASHLIST**  lists;              /**< multihash table lists of the hash table */
118  	   int                   nlists;             /**< number of lists stored in the hash table */
119  	   void*                 userptr;            /**< user pointer */
120  	   SCIP_Longint          nelements;          /**< number of elements in the hashtable */
121  	};
122  	
123  	typedef union {
124  	   void*                 ptr;                /**< pointer image */
125  	   int                   integer;            /**< integer image */
126  	   SCIP_Real             real;               /**< real image */
127  	} SCIP_HASHMAPIMAGE;
128  	
129  	/** hash map entry */
130  	struct SCIP_HashMapEntry
131  	{
132  	   void*                 origin;             /**< origin of element */
133  	   SCIP_HASHMAPIMAGE     image;              /**< image of element */
134  	};
135  	
136  	/** hash map data structure to map pointers on pointers */
137  	struct SCIP_HashMap
138  	{
139  	   BMS_BLKMEM*           blkmem;             /**< block memory used to store hash map entries */
140  	   SCIP_HASHMAPENTRY*    slots;              /**< buffer for hashmap entries */
141  	   uint32_t*             hashes;             /**< hashes of elements */
142  	   uint32_t              shift;              /**< power such that 2^(32-shift) == nslots */
143  	   uint32_t              mask;               /**< mask used for fast modulo, i.e. nslots - 1 */
144  	   uint32_t              nelements;          /**< number of elements in the hashtable */
145  	   SCIP_HASHMAPTYPE      hashmaptype;        /**< type of entries */
146  	};
147  	
148  	/** lightweight hash set data structure to map pointers on pointers */
149  	struct SCIP_HashSet
150  	{
151  	   void**                slots;              /**< buffer for hashmap entries */
152  	   uint32_t              shift;              /**< power such that 2^(64-shift) == nslots */
153  	   uint32_t              nelements;          /**< number of elements in the hashtable */
154  	};
155  	
156  	/** dynamic array for storing real values */
157  	struct SCIP_RealArray
158  	{
159  	   BMS_BLKMEM*           blkmem;             /**< block memory that stores the vals array */
160  	   SCIP_Real*            vals;               /**< array values */
161  	   int                   valssize;           /**< size of vals array */
162  	   int                   firstidx;           /**< index of first element in vals array */
163  	   int                   minusedidx;         /**< index of first non zero element in vals array */
164  	   int                   maxusedidx;         /**< index of last non zero element in vals array */
165  	};
166  	
167  	/** dynamic array for storing int values */
168  	struct SCIP_IntArray
169  	{
170  	   BMS_BLKMEM*           blkmem;             /**< block memory that stores the vals array */
171  	   int*                  vals;               /**< array values */
172  	   int                   valssize;           /**< size of vals array */
173  	   int                   firstidx;           /**< index of first element in vals array */
174  	   int                   minusedidx;         /**< index of first non zero element in vals array */
175  	   int                   maxusedidx;         /**< index of last non zero element in vals array */
176  	};
177  	
178  	/** dynamic array for storing bool values */
179  	struct SCIP_BoolArray
180  	{
181  	   BMS_BLKMEM*           blkmem;             /**< block memory that stores the vals array */
182  	   SCIP_Bool*            vals;               /**< array values */
183  	   int                   valssize;           /**< size of vals array */
184  	   int                   firstidx;           /**< index of first element in vals array */
185  	   int                   minusedidx;         /**< index of first non zero element in vals array */
186  	   int                   maxusedidx;         /**< index of last non zero element in vals array */
187  	};
188  	
189  	/** dynamic array for storing pointers */
190  	struct SCIP_PtrArray
191  	{
192  	   BMS_BLKMEM*           blkmem;             /**< block memory that stores the vals array */
193  	   void**                vals;               /**< array values */
194  	   int                   valssize;           /**< size of vals array */
195  	   int                   firstidx;           /**< index of first element in vals array */
196  	   int                   minusedidx;         /**< index of first non zero element in vals array */
197  	   int                   maxusedidx;         /**< index of last non zero element in vals array */
198  	};
199  	
200  	/** resource activity */
201  	struct SCIP_ResourceActivity
202  	{
203  	   SCIP_VAR*             var;                /**< start time variable of the activity */
204  	   int                   duration;           /**< duration of the activity */
205  	   int                   demand;             /**< demand of the activity */
206  	};
207  	
208  	/** resource profile */
209  	struct SCIP_Profile
210  	{
211  	   int*                  timepoints;         /**< time point array */
212  	   int*                  loads;              /**< array holding the load for each time point */
213  	   int                   capacity;           /**< capacity of the resource profile */
214  	   int                   ntimepoints;        /**< current number of entries */
215  	   int                   arraysize;          /**< current array size */
216  	};
217  	
218  	/** digraph structure to store and handle graphs */
219  	struct SCIP_Digraph
220  	{
221  	   BMS_BLKMEM*           blkmem;             /**< block memory pointer to store the data */
222  	   int**                 successors;         /**< adjacency list: for each node (first dimension) list of all successors */
223  	   void***               arcdata;            /**< arc data corresponding to the arcs to successors given by the successors array  */
224  	   void**                nodedata;           /**< data for each node of graph */
225  	   int*                  successorssize;     /**< sizes of the successor lists for the nodes */
226  	   int*                  nsuccessors;        /**< number of successors stored in the adjacency lists of the nodes */
227  	   int*                  components;         /**< array to store the node indices of the components, one component after the other */
228  	   int*                  componentstarts;    /**< array to store the start indices of the components in the components array */
229  	   int*                  articulations;      /**< array  of size narticulations to store the node indices of the articulation points */
230  	   int                   ncomponents;        /**< number of undirected components stored */
231  	   int                   componentstartsize; /**< size of array componentstarts */
232  	   int                   nnodes;             /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
233  	   int                   narticulations;     /**< number of articulation points among the graph nodes */
234  	   SCIP_Bool             articulationscheck; /**< TRUE if the (computed) articulation nodes are up-to-date and FALSE otherwise */
235  	};
236  	
237  	/** binary node data structure for binary tree */
238  	struct SCIP_BtNode
239  	{
240  	   SCIP_BTNODE*          parent;             /**< pointer to the parent node */
241  	   SCIP_BTNODE*          left;               /**< pointer to the left child node */
242  	   SCIP_BTNODE*          right;              /**< pointer to the right child node */
243  	   void*                 dataptr;            /**< user pointer */
244  	};
245  	
246  	/** binary search tree data structure */
247  	struct SCIP_Bt
248  	{
249  	   SCIP_BTNODE*          root;               /**< pointer to the dummy root node; root is left child */
250  	   BMS_BLKMEM*           blkmem;             /**< block memory used to store tree nodes */
251  	};
252  	
253  	/** data structure for incremental linear regression of data points (X_i, Y_i)  */
254  	struct SCIP_Regression
255  	{
256  	   SCIP_Real             intercept;          /**< the current axis intercept of the regression */
257  	   SCIP_Real             slope;              /**< the current slope of the regression */
258  	   SCIP_Real             meanx;              /**< mean of all X observations */
259  	   SCIP_Real             meany;              /**< mean of all Y observations */
260  	   SCIP_Real             sumxy;              /**< accumulated sum of all products X * Y */
261  	   SCIP_Real             variancesumx;       /**< incremental variance term for X observations  */
262  	   SCIP_Real             variancesumy;       /**< incremental variance term for Y observations */
263  	   SCIP_Real             corrcoef;           /**< correlation coefficient of X and Y */
264  	   int                   nobservations;      /**< number of observations so far */
265  	};
266  	
267  	/** random number generator data */
268  	struct SCIP_RandNumGen
269  	{
270  	   uint32_t              seed;               /**< start seed */
271  	   uint32_t              xor_seed;           /**< Xorshift seed */
272  	   uint32_t              mwc_seed;           /**< Multiply-with-carry seed */
273  	   uint32_t              cst_seed;           /**< constant seed */
274  	};
275  	
276  	/** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */
277  	struct SCIP_DisjointSet
278  	{
279  	   int*                  parents;            /**< array to store the parent node index for every vertex */
280  	   int*                  sizes;              /**< array to store the size of the subtree rooted at each vertex */
281  	   int                   size;               /**< the number of vertices in the graph */
282  	   int                   componentcount;     /**< counter for the number of connected components of the graph */
283  	};
284  	
285  	/** a linear inequality row in preparation to become a SCIP_ROW */
286  	struct SCIP_RowPrep
287  	{
288  	   SCIP_VAR**            vars;               /**< variables */
289  	   SCIP_Real*            coefs;              /**< coefficients of variables */
290  	   int                   nvars;              /**< number of variables (= number of coefficients) */
291  	   int                   varssize;           /**< length of variables array (= lengths of coefficients array) */
292  	   SCIP_Real             side;               /**< side */
293  	   SCIP_SIDETYPE         sidetype;           /**< type of side */
294  	   SCIP_Bool             local;              /**< whether the row is only locally valid (i.e., for the current node) */
295  	   char                  name[SCIP_MAXSTRLEN]; /**< row name */
296  	
297  	   SCIP_Bool             recordmodifications;/**< whether to remember variables which coefficients were modified during cleanup */
298  	   SCIP_VAR**            modifiedvars;       /**< variables which coefficient were modified by cleanup */
299  	   int                   nmodifiedvars;      /**< number of variables which coefficient was modified */
300  	   int                   modifiedvarssize;   /**< length of `modifiedvars` array */
301  	   SCIP_Bool             modifiedside;       /**< whether the side was modified (relaxed) by cleanup */
302  	};
303  	
304  	#ifdef __cplusplus
305  	}
306  	#endif
307  	
308  	#endif
309