Scippy

SCIP

Solving Constraint Integer Programs

struct_misc.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_misc.h
17  * @ingroup INTERNALAPI
18  * @brief miscellaneous datastructures
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_MISC_H__
25 #define __SCIP_STRUCT_MISC_H__
26 
27 
28 #include "scip/def.h"
29 #include "blockmemshell/memory.h"
30 #include "scip/type_misc.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 /** data structure for sparse solutions */
38 {
39  SCIP_VAR** vars; /**< variables */
40  SCIP_Longint* lbvalues; /**< array of lower bounds */
41  SCIP_Longint* ubvalues; /**< array of upper bounds */
42  int nvars; /**< number of variables */
43 };
44 
45 typedef union {
46  void* ptr; /**< pointer element */
47  unsigned int uinteger; /**< unsigned integer element */
49 
50 /** (circular) Queue data structure */
51 struct SCIP_Queue
52 {
53  SCIP_Real sizefac; /**< memory growing factor */
54  SCIP_QUEUEELEMENT* slots; /**< array of element slots */
55  int firstfree; /**< first free slot */
56  int firstused; /**< first used slot */
57  int size; /**< total number of available element slots */
58 };
59 
60 /** priority queue data structure
61  * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
62  * The ordering is done through a pointer comparison function.
63  * The array is organized as follows. The root element (that is the "best" element $r$ with $r <= x$ for all $x$)
64  * is stored in position 0. The children of an element at position $p$ are stored at positions $q_1 = 2*p+1$ and
65  * $q_2 = 2*p+2$. That means, the parent of the element at position $q$ is at position $p = (q-1)/2$.
66  * At any time, the condition holds that $p <= q$ for each parent $p$ and its children $q$.
67  * Insertion and removal of single elements needs time $O(log n)$.
68  */
70 {
71  SCIP_Real sizefac; /**< memory growing factor */
72  SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */
73  void** slots; /**< array of element slots */
74  int len; /**< number of used element slots */
75  int size; /**< total number of available element slots */
76 };
77 
78 /** hash table data structure */
80 {
81  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
82  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
83  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
84  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
85  void* userptr; /**< user pointer */
86  void** slots; /**< slots of the hash table */
87  uint32_t* hashes; /**< hash values of elements stored in slots */
88  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
89  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
90  uint32_t nelements; /**< number of elements in the hashtable */
91 };
92 
93 /** element list to store single elements of a hash table */
95 {
96  void* element; /**< this element */
97  SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */
98 };
99 
100 /** multihash table data structure */
102 {
103  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
104  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
105  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
106  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
107  SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */
108  int nlists; /**< number of lists stored in the hash table */
109  void* userptr; /**< user pointer */
110  SCIP_Longint nelements; /**< number of elements in the hashtable */
111 };
112 
113 typedef union {
114  void* ptr; /**< pointer image */
115  int integer; /**< integer image */
116  SCIP_Real real; /**< real image */
118 
119 /** hash map entry */
121 {
122  void* origin; /**< origin of element */
123  SCIP_HASHMAPIMAGE image; /**< image of element */
124 };
125 
126 /** hash map data structure to map pointers on pointers */
128 {
129  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
130  SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */
131  uint32_t* hashes; /**< hashes of elements */
132  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
133  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
134  uint32_t nelements; /**< number of elements in the hashtable */
135  SCIP_HASHMAPTYPE hashmaptype; /**< type of entries */
136 };
137 
138 /** lightweight hash set data structure to map pointers on pointers */
140 {
141  void** slots; /**< buffer for hashmap entries */
142  uint32_t shift; /**< power such that 2^(64-shift) == nslots */
143  uint32_t nelements; /**< number of elements in the hashtable */
144 };
145 
146 /** dynamic array for storing real values */
148 {
149  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
150  SCIP_Real* vals; /**< array values */
151  int valssize; /**< size of vals array */
152  int firstidx; /**< index of first element in vals array */
153  int minusedidx; /**< index of first non zero element in vals array */
154  int maxusedidx; /**< index of last non zero element in vals array */
155 };
156 
157 /** dynamic array for storing int values */
159 {
160  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
161  int* vals; /**< array values */
162  int valssize; /**< size of vals array */
163  int firstidx; /**< index of first element in vals array */
164  int minusedidx; /**< index of first non zero element in vals array */
165  int maxusedidx; /**< index of last non zero element in vals array */
166 };
167 
168 /** dynamic array for storing bool values */
170 {
171  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
172  SCIP_Bool* vals; /**< array values */
173  int valssize; /**< size of vals array */
174  int firstidx; /**< index of first element in vals array */
175  int minusedidx; /**< index of first non zero element in vals array */
176  int maxusedidx; /**< index of last non zero element in vals array */
177 };
178 
179 /** dynamic array for storing pointers */
181 {
182  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
183  void** vals; /**< array values */
184  int valssize; /**< size of vals array */
185  int firstidx; /**< index of first element in vals array */
186  int minusedidx; /**< index of first non zero element in vals array */
187  int maxusedidx; /**< index of last non zero element in vals array */
188 };
189 
190 /** resource activity */
192 {
193  SCIP_VAR* var; /**< start time variable of the activity */
194  int duration; /**< duration of the activity */
195  int demand; /**< demand of the activity */
196 };
197 
198 /** resource profile */
200 {
201  int* timepoints; /**< time point array */
202  int* loads; /**< array holding the load for each time point */
203  int capacity; /**< capacity of the resource profile */
204  int ntimepoints; /**< current number of entries */
205  int arraysize; /**< current array size */
206 };
207 
208 /** digraph structure to store and handle graphs */
210 {
211  BMS_BLKMEM* blkmem; /**< block memory pointer to store the data */
212  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
213  void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */
214  void** nodedata; /**< data for each node of graph */
215  int* successorssize; /**< sizes of the successor lists for the nodes */
216  int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */
217  int* components; /**< array to store the node indices of the components, one component after the other */
218  int* componentstarts; /**< array to store the start indices of the components in the components array */
219  int ncomponents; /**< number of undirected components stored */
220  int componentstartsize; /**< size of array componentstarts */
221  int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
222 };
223 
224 /** binary node data structure for binary tree */
226 {
227  SCIP_BTNODE* parent; /**< pointer to the parent node */
228  SCIP_BTNODE* left; /**< pointer to the left child node */
229  SCIP_BTNODE* right; /**< pointer to the right child node */
230  void* dataptr; /**< user pointer */
231 };
232 
233 /** binary search tree data structure */
234 struct SCIP_Bt
235 {
236  SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */
237  BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */
238 };
239 
240 /** data structure for incremental linear regression of data points (X_i, Y_i) */
242 {
243  SCIP_Real intercept; /**< the current axis intercept of the regression */
244  SCIP_Real slope; /**< the current slope of the regression */
245  SCIP_Real meanx; /**< mean of all X observations */
246  SCIP_Real meany; /**< mean of all Y observations */
247  SCIP_Real sumxy; /**< accumulated sum of all products X * Y */
248  SCIP_Real variancesumx; /**< incremental variance term for X observations */
249  SCIP_Real variancesumy; /**< incremental variance term for Y observations */
250  SCIP_Real corrcoef; /**< correlation coefficient of X and Y */
251  int nobservations; /**< number of observations so far */
252 };
253 
254 /** random number generator data */
256 {
257  uint32_t seed; /**< start seed */
258  uint32_t xor_seed; /**< Xorshift seed */
259  uint32_t mwc_seed; /**< Multiply-with-carry seed */
260  uint32_t cst_seed; /**< constant seed */
261 };
262 
263 /** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */
265 {
266  int* parents; /**< array to store the parent node index for every vertex */
267  int* sizes; /**< array to store the size of the subtree rooted at each vertex */
268  int size; /**< the number of vertices in the graph */
269  int componentcount; /**< counter for the number of connected components of the graph */
270 };
271 
272 #ifdef __cplusplus
273 }
274 #endif
275 
276 #endif
uint32_t * hashes
Definition: struct_misc.h:131
SCIP_BTNODE * parent
Definition: struct_misc.h:227
void ** slots
Definition: struct_misc.h:86
SCIP_Real * vals
Definition: struct_misc.h:150
BMS_BLKMEM * blkmem
Definition: struct_misc.h:84
SCIP_QUEUEELEMENT * slots
Definition: struct_misc.h:54
void *** arcdata
Definition: struct_misc.h:213
BMS_BLKMEM * blkmem
Definition: struct_misc.h:211
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:181
type definitions for miscellaneous datastructures
uint32_t shift
Definition: struct_misc.h:132
BMS_BLKMEM * blkmem
Definition: struct_misc.h:237
SCIP_Real intercept
Definition: struct_misc.h:243
void ** nodedata
Definition: struct_misc.h:214
int firstfree
Definition: struct_misc.h:55
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:175
int * componentstarts
Definition: struct_misc.h:218
uint32_t * hashes
Definition: struct_misc.h:87
uint32_t shift
Definition: struct_misc.h:142
uint32_t mwc_seed
Definition: struct_misc.h:259
uint32_t mask
Definition: struct_misc.h:89
void ** slots
Definition: struct_misc.h:141
uint32_t cst_seed
Definition: struct_misc.h:260
uint32_t nelements
Definition: struct_misc.h:90
SCIP_VAR ** vars
Definition: struct_misc.h:39
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:107
void * dataptr
Definition: struct_misc.h:230
unsigned int uinteger
Definition: struct_misc.h:47
SCIP_Real corrcoef
Definition: struct_misc.h:250
BMS_BLKMEM * blkmem
Definition: struct_misc.h:129
void * userptr
Definition: struct_misc.h:85
SCIP_BTNODE * root
Definition: struct_misc.h:236
int ** successors
Definition: struct_misc.h:212
void ** slots
Definition: struct_misc.h:73
SCIP_Real meany
Definition: struct_misc.h:246
BMS_BLKMEM * blkmem
Definition: struct_misc.h:149
BMS_BLKMEM * blkmem
Definition: struct_misc.h:160
SCIP_BTNODE * left
Definition: struct_misc.h:228
int * timepoints
Definition: struct_misc.h:201
uint32_t mask
Definition: struct_misc.h:133
SCIP_Real variancesumx
Definition: struct_misc.h:248
SCIP_Real sizefac
Definition: struct_misc.h:71
SCIP_Longint * lbvalues
Definition: struct_misc.h:40
uint32_t shift
Definition: struct_misc.h:88
SCIP_Real slope
Definition: struct_misc.h:244
enum SCIP_Hashmaptype SCIP_HASHMAPTYPE
Definition: type_misc.h:54
uint32_t xor_seed
Definition: struct_misc.h:258
SCIP_Bool * vals
Definition: struct_misc.h:172
int * components
Definition: struct_misc.h:217
#define SCIP_Bool
Definition: def.h:69
SCIP_Real variancesumy
Definition: struct_misc.h:249
int * successorssize
Definition: struct_misc.h:215
SCIP_Longint * ubvalues
Definition: struct_misc.h:41
SCIP_Real sumxy
Definition: struct_misc.h:247
uint32_t nelements
Definition: struct_misc.h:143
SCIP_Real meanx
Definition: struct_misc.h:245
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:172
SCIP_HASHMAPTYPE hashmaptype
Definition: struct_misc.h:135
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:130
SCIP_BTNODE * right
Definition: struct_misc.h:229
#define SCIP_Real
Definition: def.h:157
int componentstartsize
Definition: struct_misc.h:220
uint32_t nelements
Definition: struct_misc.h:134
BMS_BLKMEM * blkmem
Definition: struct_misc.h:106
BMS_BLKMEM * blkmem
Definition: struct_misc.h:171
#define SCIP_Longint
Definition: def.h:142
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:178
void ** vals
Definition: struct_misc.h:183
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:97
BMS_BLKMEM * blkmem
Definition: struct_misc.h:182
int * nsuccessors
Definition: struct_misc.h:216
SCIP_Longint nelements
Definition: struct_misc.h:110
SCIP_Real sizefac
Definition: struct_misc.h:53
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:426
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:123
int firstused
Definition: struct_misc.h:56
memory allocation routines