/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */ /* fuer Informationstechnik Berlin */ /* */ /* SCIP is distributed under the terms of the ZIB Academic License. */ /* */ /* You should have received a copy of the ZIB Academic License */ /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file struct_misc.h * @ingroup INTERNALAPI * @brief miscellaneous datastructures * @author Tobias Achterberg */ /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #ifndef __SCIP_STRUCT_MISC_H__ #define __SCIP_STRUCT_MISC_H__ #include "scip/def.h" #include "blockmemshell/memory.h" #include "scip/type_misc.h" #ifdef __cplusplus extern "C" { #endif /** data structure for sparse solutions */ struct SCIP_SparseSol { SCIP_VAR** vars; /**< variables */ SCIP_Longint* lbvalues; /**< array of lower bounds */ SCIP_Longint* ubvalues; /**< array of upper bounds */ int nvars; /**< number of variables */ }; typedef union { void* ptr; /**< pointer element */ unsigned int uinteger; /**< unsigned integer element */ } SCIP_QUEUEELEMENT; /** (circular) Queue data structure */ struct SCIP_Queue { SCIP_Real sizefac; /**< memory growing factor */ SCIP_QUEUEELEMENT* slots; /**< array of element slots */ int firstfree; /**< first free slot */ int firstused; /**< first used slot */ int size; /**< total number of available element slots */ }; /** priority queue data structure * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue. * The ordering is done through a pointer comparison function. * 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$ ) * 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 * \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$ . * At any time, the condition holds that \f$ p \leq q \f$ for each parent \f$ p \f$ and its children \f$ q \f$ . * Insertion and removal of single elements needs time \f$ O(log n) \f$ . */ struct SCIP_PQueue { SCIP_Real sizefac; /**< memory growing factor */ SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */ SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos));/**< callback to act on position change of elem in priority queue, or NULL */ void** slots; /**< array of element slots */ int len; /**< number of used element slots */ int size; /**< total number of available element slots */ }; /** hash table data structure */ struct SCIP_HashTable { SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */ SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */ SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */ BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ void* userptr; /**< user pointer */ void** slots; /**< slots of the hash table */ uint32_t* hashes; /**< hash values of elements stored in slots */ uint32_t shift; /**< power such that 2^(32-shift) == nslots */ uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */ uint32_t nelements; /**< number of elements in the hashtable */ }; /** element list to store single elements of a hash table */ struct SCIP_MultiHashList { void* element; /**< this element */ SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */ }; /** multihash table data structure */ struct SCIP_MultiHash { SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */ SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */ SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */ BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */ int nlists; /**< number of lists stored in the hash table */ void* userptr; /**< user pointer */ SCIP_Longint nelements; /**< number of elements in the hashtable */ }; typedef union { void* ptr; /**< pointer image */ int integer; /**< integer image */ SCIP_Real real; /**< real image */ } SCIP_HASHMAPIMAGE; /** hash map entry */ struct SCIP_HashMapEntry { void* origin; /**< origin of element */ SCIP_HASHMAPIMAGE image; /**< image of element */ }; /** hash map data structure to map pointers on pointers */ struct SCIP_HashMap { BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */ uint32_t* hashes; /**< hashes of elements */ uint32_t shift; /**< power such that 2^(32-shift) == nslots */ uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */ uint32_t nelements; /**< number of elements in the hashtable */ SCIP_HASHMAPTYPE hashmaptype; /**< type of entries */ }; /** lightweight hash set data structure to map pointers on pointers */ struct SCIP_HashSet { void** slots; /**< buffer for hashmap entries */ uint32_t shift; /**< power such that 2^(64-shift) == nslots */ uint32_t nelements; /**< number of elements in the hashtable */ }; /** dynamic array for storing real values */ struct SCIP_RealArray { BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ SCIP_Real* vals; /**< array values */ int valssize; /**< size of vals array */ int firstidx; /**< index of first element in vals array */ int minusedidx; /**< index of first non zero element in vals array */ int maxusedidx; /**< index of last non zero element in vals array */ }; /** dynamic array for storing int values */ struct SCIP_IntArray { BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ int* vals; /**< array values */ int valssize; /**< size of vals array */ int firstidx; /**< index of first element in vals array */ int minusedidx; /**< index of first non zero element in vals array */ int maxusedidx; /**< index of last non zero element in vals array */ }; /** dynamic array for storing bool values */ struct SCIP_BoolArray { BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ SCIP_Bool* vals; /**< array values */ int valssize; /**< size of vals array */ int firstidx; /**< index of first element in vals array */ int minusedidx; /**< index of first non zero element in vals array */ int maxusedidx; /**< index of last non zero element in vals array */ }; /** dynamic array for storing pointers */ struct SCIP_PtrArray { BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ void** vals; /**< array values */ int valssize; /**< size of vals array */ int firstidx; /**< index of first element in vals array */ int minusedidx; /**< index of first non zero element in vals array */ int maxusedidx; /**< index of last non zero element in vals array */ }; /** resource activity */ struct SCIP_ResourceActivity { SCIP_VAR* var; /**< start time variable of the activity */ int duration; /**< duration of the activity */ int demand; /**< demand of the activity */ }; /** resource profile */ struct SCIP_Profile { int* timepoints; /**< time point array */ int* loads; /**< array holding the load for each time point */ int capacity; /**< capacity of the resource profile */ int ntimepoints; /**< current number of entries */ int arraysize; /**< current array size */ }; /** digraph structure to store and handle graphs */ struct SCIP_Digraph { BMS_BLKMEM* blkmem; /**< block memory pointer to store the data */ int** successors; /**< adjacency list: for each node (first dimension) list of all successors */ void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */ void** nodedata; /**< data for each node of graph */ int* successorssize; /**< sizes of the successor lists for the nodes */ int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */ int* components; /**< array to store the node indices of the components, one component after the other */ int* componentstarts; /**< array to store the start indices of the components in the components array */ int* articulations; /**< array of size narticulations to store the node indices of the articulation points */ int ncomponents; /**< number of undirected components stored */ int componentstartsize; /**< size of array componentstarts */ int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */ int narticulations; /**< number of articulation points among the graph nodes */ SCIP_Bool articulationscheck; /**< TRUE if the (computed) articulation nodes are up-to-date and FALSE otherwise */ }; /** binary node data structure for binary tree */ struct SCIP_BtNode { SCIP_BTNODE* parent; /**< pointer to the parent node */ SCIP_BTNODE* left; /**< pointer to the left child node */ SCIP_BTNODE* right; /**< pointer to the right child node */ void* dataptr; /**< user pointer */ }; /** binary search tree data structure */ struct SCIP_Bt { SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */ BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */ }; /** data structure for incremental linear regression of data points (X_i, Y_i) */ struct SCIP_Regression { SCIP_Real intercept; /**< the current axis intercept of the regression */ SCIP_Real slope; /**< the current slope of the regression */ SCIP_Real meanx; /**< mean of all X observations */ SCIP_Real meany; /**< mean of all Y observations */ SCIP_Real sumxy; /**< accumulated sum of all products X * Y */ SCIP_Real variancesumx; /**< incremental variance term for X observations */ SCIP_Real variancesumy; /**< incremental variance term for Y observations */ SCIP_Real corrcoef; /**< correlation coefficient of X and Y */ int nobservations; /**< number of observations so far */ }; /** random number generator data */ struct SCIP_RandNumGen { uint32_t seed; /**< start seed */ uint32_t xor_seed; /**< Xorshift seed */ uint32_t mwc_seed; /**< Multiply-with-carry seed */ uint32_t cst_seed; /**< constant seed */ }; /** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */ struct SCIP_DisjointSet { int* parents; /**< array to store the parent node index for every vertex */ int* sizes; /**< array to store the size of the subtree rooted at each vertex */ int size; /**< the number of vertices in the graph */ int componentcount; /**< counter for the number of connected components of the graph */ }; #ifdef __cplusplus } #endif #endif