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