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-2014 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 */
36 struct SCIP_SparseSol
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  */
63 struct SCIP_PQueue
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 */
73 struct SCIP_HashTableList
74 {
75  void* element; /**< this element */
76  SCIP_HASHTABLELIST* next; /**< rest of the hash table list */
77 };
78 
79 /** hash table data structure */
80 struct SCIP_HashTable
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 */
93 struct SCIP_HashMapList
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 */
101 struct SCIP_HashMap
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 */
109 struct SCIP_RealArray
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 */
120 struct SCIP_IntArray
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 */
131 struct SCIP_BoolArray
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 */
142 struct SCIP_PtrArray
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 */
153 struct SCIP_ResourceActivity
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 */
161 struct SCIP_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 */
171 struct SCIP_Digraph
172 {
173  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
174  void*** arcdatas; /**< arc datas corresponding to the arcs to successors given by the successors array */
175  void** nodedatas; /**< arc datas corresponding to the arcs to successors given by the successors array */
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 */
186 struct SCIP_BtNode
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
206