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-2016 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  * @brief miscellaneous datastructures
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_STRUCT_MISC_H__
24 #define __SCIP_STRUCT_MISC_H__
25 
26 
27 #include "scip/def.h"
28 #include "blockmemshell/memory.h"
29 #include "scip/type_misc.h"
30 
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 
35 /** data structure for sparse solutions */
37 {
38  SCIP_VAR** vars; /**< variables */
39  SCIP_Longint* lbvalues; /**< array of lower bounds */
40  SCIP_Longint* ubvalues; /**< array of upper bounds */
41  int nvars; /**< number of variables */
42 };
43 
44 /** (circular) Queue data structure */
45 struct SCIP_Queue
46 {
47  SCIP_Real sizefac; /**< memory growing factor */
48  void** slots; /**< array of element slots */
49  int firstfree; /**< first free slot */
50  int firstused; /**< first used slot */
51  int size; /**< total number of available element slots */
52 };
53 
54 /** priority queue data structure
55  * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
56  * The ordering is done through a pointer comparison function.
57  * The array is organized as follows. The root element (that is the "best" element $r$ with $r <= x$ for all $x$)
58  * is stored in position 0. The children of an element at position $p$ are stored at positions $q_1 = 2*p+1$ and
59  * $q_2 = 2*p+2$. That means, the parent of the element at position $q$ is at position $p = (q-1)/2$.
60  * At any time, the condition holds that $p <= q$ for each parent $p$ and its children $q$.
61  * Insertion and removal of single elements needs time $O(log n)$.
62  */
64 {
65  SCIP_Real sizefac; /**< memory growing factor */
66  SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */
67  void** slots; /**< array of element slots */
68  int len; /**< number of used element slots */
69  int size; /**< total number of available element slots */
70 };
71 
72 /** element list to store single elements of a hash table */
74 {
75  void* element; /**< this element */
76  SCIP_HASHTABLELIST* next; /**< rest of the hash table list */
77 };
78 
79 /** hash table data structure */
81 {
82  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
83  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
84  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
85  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
86  SCIP_HASHTABLELIST** lists; /**< hash table lists of the hash table */
87  int nlists; /**< number of lists stored in the hash table */
88  void* userptr; /**< user pointer */
89  SCIP_Longint nelements; /**< number of elements in the hashtable */
90 };
91 
92 /** element list to store single mappings of a hash map */
94 {
95  void* origin; /**< origin of the mapping origin -> image */
96  void* image; /**< image of the mapping origin -> image */
97  SCIP_HASHMAPLIST* next; /**< rest of the hash map list */
98 };
99 
100 /** hash map data structure to map pointers on pointers */
102 {
103  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
104  SCIP_HASHMAPLIST** lists; /**< hash map lists of the hash map */
105  int nlists; /**< number of lists stored in the hash map */
106 };
107 
108 /** dynamic array for storing real values */
110 {
111  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
112  SCIP_Real* vals; /**< array values */
113  int valssize; /**< size of vals array */
114  int firstidx; /**< index of first element in vals array */
115  int minusedidx; /**< index of first non zero element in vals array */
116  int maxusedidx; /**< index of last non zero element in vals array */
117 };
118 
119 /** dynamic array for storing int values */
121 {
122  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
123  int* vals; /**< array values */
124  int valssize; /**< size of vals array */
125  int firstidx; /**< index of first element in vals array */
126  int minusedidx; /**< index of first non zero element in vals array */
127  int maxusedidx; /**< index of last non zero element in vals array */
128 };
129 
130 /** dynamic array for storing bool values */
132 {
133  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
134  SCIP_Bool* vals; /**< array values */
135  int valssize; /**< size of vals array */
136  int firstidx; /**< index of first element in vals array */
137  int minusedidx; /**< index of first non zero element in vals array */
138  int maxusedidx; /**< index of last non zero element in vals array */
139 };
140 
141 /** dynamic array for storing pointers */
143 {
144  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
145  void** vals; /**< array values */
146  int valssize; /**< size of vals array */
147  int firstidx; /**< index of first element in vals array */
148  int minusedidx; /**< index of first non zero element in vals array */
149  int maxusedidx; /**< index of last non zero element in vals array */
150 };
151 
152 /** resource activity */
154 {
155  SCIP_VAR* var; /**< start time variable of the activity */
156  int duration; /**< duration of the activity */
157  int demand; /**< demand of the activity */
158 };
159 
160 /** resource profile */
162 {
163  int* timepoints; /**< time point array */
164  int* loads; /**< array holding the load for each time point */
165  int capacity; /**< capacity of the resource profile */
166  int ntimepoints; /**< current number of entries */
167  int arraysize; /**< current array size */
168 };
169 
170 /** digraph structure to store and handle graphs */
172 {
173  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
174  void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */
175  void** nodedata; /**< data for each node of graph */
176  int* successorssize; /**< sizes of the successor lists for the nodes */
177  int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */
178  int* components; /**< array to store the node indices of the components, one component after the other */
179  int* componentstarts; /**< array to store the start indices of the components in the components array */
180  int ncomponents; /**< number of undirected components stored */
181  int componentstartsize; /**< size of array componentstarts */
182  int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
183 };
184 
185 /** binary node data structure for binary tree */
187 {
188  SCIP_BTNODE* parent; /**< pointer to the parent node */
189  SCIP_BTNODE* left; /**< pointer to the left child node */
190  SCIP_BTNODE* right; /**< pointer to the right child node */
191  void* dataptr; /**< user pointer */
192 };
193 
194 /** binary search tree data structure */
195 struct SCIP_Bt
196 {
197  SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */
198  BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */
199 };
200 
201 #ifdef __cplusplus
202 }
203 #endif
204 
205 #endif
SCIP_BTNODE * parent
Definition: struct_misc.h:188
SCIP_Real * vals
Definition: struct_misc.h:112
BMS_BLKMEM * blkmem
Definition: struct_misc.h:85
void *** arcdata
Definition: struct_misc.h:174
SCIP_HASHMAPLIST ** lists
Definition: struct_misc.h:104
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:145
type definitions for miscellaneous datastructures
BMS_BLKMEM * blkmem
Definition: struct_misc.h:198
void ** nodedata
Definition: struct_misc.h:175
SCIP_Longint nelements
Definition: struct_misc.h:89
int firstfree
Definition: struct_misc.h:49
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:139
int * componentstarts
Definition: struct_misc.h:179
SCIP_VAR ** vars
Definition: struct_misc.h:38
void * dataptr
Definition: struct_misc.h:191
BMS_BLKMEM * blkmem
Definition: struct_misc.h:103
void * userptr
Definition: struct_misc.h:88
SCIP_BTNODE * root
Definition: struct_misc.h:197
int ** successors
Definition: struct_misc.h:173
void ** slots
Definition: struct_misc.h:67
BMS_BLKMEM * blkmem
Definition: struct_misc.h:111
BMS_BLKMEM * blkmem
Definition: struct_misc.h:122
SCIP_BTNODE * left
Definition: struct_misc.h:189
int * timepoints
Definition: struct_misc.h:163
SCIP_Real sizefac
Definition: struct_misc.h:65
SCIP_HASHTABLELIST * next
Definition: struct_misc.h:76
SCIP_Longint * lbvalues
Definition: struct_misc.h:39
SCIP_Bool * vals
Definition: struct_misc.h:134
int * components
Definition: struct_misc.h:178
#define SCIP_Bool
Definition: def.h:53
void ** slots
Definition: struct_misc.h:48
int * successorssize
Definition: struct_misc.h:176
SCIP_Longint * ubvalues
Definition: struct_misc.h:40
SCIP_HASHMAPLIST * next
Definition: struct_misc.h:97
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:136
SCIP_BTNODE * right
Definition: struct_misc.h:190
#define SCIP_Real
Definition: def.h:127
int componentstartsize
Definition: struct_misc.h:181
BMS_BLKMEM * blkmem
Definition: struct_misc.h:133
#define SCIP_Longint
Definition: def.h:112
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:142
void ** vals
Definition: struct_misc.h:145
BMS_BLKMEM * blkmem
Definition: struct_misc.h:144
int * nsuccessors
Definition: struct_misc.h:177
SCIP_Real sizefac
Definition: struct_misc.h:47
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:392
SCIP_HASHTABLELIST ** lists
Definition: struct_misc.h:86
int firstused
Definition: struct_misc.h:50
memory allocation routines