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-2017 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 email to 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 /** (circular) Queue data structure */
46 struct SCIP_Queue
47 {
48  SCIP_Real sizefac; /**< memory growing factor */
49  void** slots; /**< array of element slots */
50  int firstfree; /**< first free slot */
51  int firstused; /**< first used slot */
52  int size; /**< total number of available element slots */
53 };
54 
55 /** priority queue data structure
56  * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
57  * The ordering is done through a pointer comparison function.
58  * The array is organized as follows. The root element (that is the "best" element $r$ with $r <= x$ for all $x$)
59  * is stored in position 0. The children of an element at position $p$ are stored at positions $q_1 = 2*p+1$ and
60  * $q_2 = 2*p+2$. That means, the parent of the element at position $q$ is at position $p = (q-1)/2$.
61  * At any time, the condition holds that $p <= q$ for each parent $p$ and its children $q$.
62  * Insertion and removal of single elements needs time $O(log n)$.
63  */
65 {
66  SCIP_Real sizefac; /**< memory growing factor */
67  SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */
68  void** slots; /**< array of element slots */
69  int len; /**< number of used element slots */
70  int size; /**< total number of available element slots */
71 };
72 
73 /** hash table data structure */
75 {
76  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
77  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
78  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
79  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
80  void* userptr; /**< user pointer */
81  void** slots; /**< slots of the hash table */
82  uint32_t* hashes; /**< hash values of elements stored in slots */
83  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
84  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
85  uint32_t nelements; /**< number of elements in the hashtable */
86 };
87 
88 /** element list to store single elements of a hash table */
90 {
91  void* element; /**< this element */
92  SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */
93 };
94 
95 /** multihash table data structure */
97 {
98  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
99  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
100  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
101  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
102  SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */
103  int nlists; /**< number of lists stored in the hash table */
104  void* userptr; /**< user pointer */
105  SCIP_Longint nelements; /**< number of elements in the hashtable */
106 };
107 
108 typedef union {
109  void* ptr; /**< pointer image */
110  SCIP_Real real; /**< real image */
112 
113 /** hash map entry */
115 {
116  void* origin; /**< origin of element */
117  SCIP_HASHMAPIMAGE image; /**< image of element */
118 };
119 
120 /** hash map data structure to map pointers on pointers */
122 {
123  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
124  SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */
125  uint32_t* hashes; /**< hashes of elements */
126  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
127  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
128  uint32_t nelements; /**< number of elements in the hashtable */
129 };
130 
131 /** lightweight hash set data structure to map pointers on pointers */
133 {
134  void** slots; /**< buffer for hashmap entries */
135  uint32_t shift; /**< power such that 2^(64-shift) == nslots */
136  uint32_t nelements; /**< number of elements in the hashtable */
137 };
138 
139 /** dynamic array for storing real values */
141 {
142  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
143  SCIP_Real* vals; /**< array values */
144  int valssize; /**< size of vals array */
145  int firstidx; /**< index of first element in vals array */
146  int minusedidx; /**< index of first non zero element in vals array */
147  int maxusedidx; /**< index of last non zero element in vals array */
148 };
149 
150 /** dynamic array for storing int values */
152 {
153  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
154  int* vals; /**< array values */
155  int valssize; /**< size of vals array */
156  int firstidx; /**< index of first element in vals array */
157  int minusedidx; /**< index of first non zero element in vals array */
158  int maxusedidx; /**< index of last non zero element in vals array */
159 };
160 
161 /** dynamic array for storing bool values */
163 {
164  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
165  SCIP_Bool* vals; /**< array values */
166  int valssize; /**< size of vals array */
167  int firstidx; /**< index of first element in vals array */
168  int minusedidx; /**< index of first non zero element in vals array */
169  int maxusedidx; /**< index of last non zero element in vals array */
170 };
171 
172 /** dynamic array for storing pointers */
174 {
175  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
176  void** vals; /**< array values */
177  int valssize; /**< size of vals array */
178  int firstidx; /**< index of first element in vals array */
179  int minusedidx; /**< index of first non zero element in vals array */
180  int maxusedidx; /**< index of last non zero element in vals array */
181 };
182 
183 /** resource activity */
185 {
186  SCIP_VAR* var; /**< start time variable of the activity */
187  int duration; /**< duration of the activity */
188  int demand; /**< demand of the activity */
189 };
190 
191 /** resource profile */
193 {
194  int* timepoints; /**< time point array */
195  int* loads; /**< array holding the load for each time point */
196  int capacity; /**< capacity of the resource profile */
197  int ntimepoints; /**< current number of entries */
198  int arraysize; /**< current array size */
199 };
200 
201 /** digraph structure to store and handle graphs */
203 {
204  BMS_BLKMEM* blkmem; /**< block memory pointer to store the data */
205  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
206  void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */
207  void** nodedata; /**< data for each node of graph */
208  int* successorssize; /**< sizes of the successor lists for the nodes */
209  int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */
210  int* components; /**< array to store the node indices of the components, one component after the other */
211  int* componentstarts; /**< array to store the start indices of the components in the components array */
212  int ncomponents; /**< number of undirected components stored */
213  int componentstartsize; /**< size of array componentstarts */
214  int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
215 };
216 
217 /** binary node data structure for binary tree */
219 {
220  SCIP_BTNODE* parent; /**< pointer to the parent node */
221  SCIP_BTNODE* left; /**< pointer to the left child node */
222  SCIP_BTNODE* right; /**< pointer to the right child node */
223  void* dataptr; /**< user pointer */
224 };
225 
226 /** binary search tree data structure */
227 struct SCIP_Bt
228 {
229  SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */
230  BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */
231 };
232 
233 /** data structure for incremental linear regression of data points (X_i, Y_i) */
235 {
236  SCIP_Real intercept; /**< the current axis intercept of the regression */
237  SCIP_Real slope; /**< the current slope of the regression */
238  SCIP_Real meanx; /**< mean of all X observations */
239  SCIP_Real meany; /**< mean of all Y observations */
240  SCIP_Real sumxy; /**< accumulated sum of all products X * Y */
241  SCIP_Real variancesumx; /**< incremental variance term for X observations */
242  SCIP_Real variancesumy; /**< incremental variance term for Y observations */
243  SCIP_Real corrcoef; /**< correlation coefficient of X and Y */
244  int nobservations; /**< number of observations so far */
245 };
246 
247 /** random number generator data */
249 {
250  uint32_t seed; /**< start seed */
251  uint32_t xor_seed; /**< Xorshift seed */
252  uint32_t mwc_seed; /**< Multiply-with-carry seed */
253  uint32_t cst_seed; /**< constant seed */
254 };
255 
256 /** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */
258 {
259  int* parents; /**< array to store the parent node index for every vertex */
260  int* sizes; /**< array to store the size of the subtree rooted at each vertex */
261  int size; /**< the number of vertices in the graph */
262  int componentcount; /**< counter for the number of connected components of the graph */
263 };
264 
265 #ifdef __cplusplus
266 }
267 #endif
268 
269 #endif
uint32_t * hashes
Definition: struct_misc.h:125
SCIP_BTNODE * parent
Definition: struct_misc.h:220
void ** slots
Definition: struct_misc.h:81
SCIP_Real * vals
Definition: struct_misc.h:143
BMS_BLKMEM * blkmem
Definition: struct_misc.h:79
void *** arcdata
Definition: struct_misc.h:206
BMS_BLKMEM * blkmem
Definition: struct_misc.h:204
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:172
type definitions for miscellaneous datastructures
uint32_t shift
Definition: struct_misc.h:126
BMS_BLKMEM * blkmem
Definition: struct_misc.h:230
SCIP_Real intercept
Definition: struct_misc.h:236
void ** nodedata
Definition: struct_misc.h:207
int firstfree
Definition: struct_misc.h:50
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:166
int * componentstarts
Definition: struct_misc.h:211
uint32_t * hashes
Definition: struct_misc.h:82
uint32_t shift
Definition: struct_misc.h:135
uint32_t mwc_seed
Definition: struct_misc.h:252
uint32_t mask
Definition: struct_misc.h:84
void ** slots
Definition: struct_misc.h:134
uint32_t cst_seed
Definition: struct_misc.h:253
uint32_t nelements
Definition: struct_misc.h:85
SCIP_VAR ** vars
Definition: struct_misc.h:39
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:102
void * dataptr
Definition: struct_misc.h:223
SCIP_Real corrcoef
Definition: struct_misc.h:243
BMS_BLKMEM * blkmem
Definition: struct_misc.h:123
void * userptr
Definition: struct_misc.h:80
SCIP_BTNODE * root
Definition: struct_misc.h:229
int ** successors
Definition: struct_misc.h:205
void ** slots
Definition: struct_misc.h:68
SCIP_Real meany
Definition: struct_misc.h:239
BMS_BLKMEM * blkmem
Definition: struct_misc.h:142
BMS_BLKMEM * blkmem
Definition: struct_misc.h:153
SCIP_BTNODE * left
Definition: struct_misc.h:221
int * timepoints
Definition: struct_misc.h:194
uint32_t mask
Definition: struct_misc.h:127
SCIP_Real variancesumx
Definition: struct_misc.h:241
SCIP_Real sizefac
Definition: struct_misc.h:66
SCIP_Longint * lbvalues
Definition: struct_misc.h:40
uint32_t shift
Definition: struct_misc.h:83
SCIP_Real slope
Definition: struct_misc.h:237
uint32_t xor_seed
Definition: struct_misc.h:251
SCIP_Bool * vals
Definition: struct_misc.h:165
int * components
Definition: struct_misc.h:210
#define SCIP_Bool
Definition: def.h:61
SCIP_Real variancesumy
Definition: struct_misc.h:242
void ** slots
Definition: struct_misc.h:49
int * successorssize
Definition: struct_misc.h:208
SCIP_Longint * ubvalues
Definition: struct_misc.h:41
SCIP_Real sumxy
Definition: struct_misc.h:240
uint32_t nelements
Definition: struct_misc.h:136
SCIP_Real meanx
Definition: struct_misc.h:238
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:163
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:124
SCIP_BTNODE * right
Definition: struct_misc.h:222
#define SCIP_Real
Definition: def.h:149
int componentstartsize
Definition: struct_misc.h:213
uint32_t nelements
Definition: struct_misc.h:128
BMS_BLKMEM * blkmem
Definition: struct_misc.h:101
BMS_BLKMEM * blkmem
Definition: struct_misc.h:164
#define SCIP_Longint
Definition: def.h:134
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:169
void ** vals
Definition: struct_misc.h:176
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:92
BMS_BLKMEM * blkmem
Definition: struct_misc.h:175
int * nsuccessors
Definition: struct_misc.h:209
SCIP_Longint nelements
Definition: struct_misc.h:105
SCIP_Real sizefac
Definition: struct_misc.h:48
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:117
int firstused
Definition: struct_misc.h:51
memory allocation routines