Scippy

SCIP

Solving Constraint Integer Programs

pattern.c
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-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file pattern.c
17  * @brief pattern data for Ringpacking Problem
18  * @author Benjamin Mueller
19  *
20  *
21  * This file implements the handling of patterns. Each pattern has a <code>SCIP_PATTERNTYPE</code>, accessible by
22  * <code>SCIPpatternGetPatternType()</code>, which indicates whether it is a circular or rectangular pattern.
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include "pattern.h"
28 #include "probdata_rpa.h"
29 
30 /*
31  * local methods
32  */
33 
34 /** ensures that there is enough memory to store elements */
35 static
37  SCIP_PATTERN* pattern, /**< pattern */
38  int size /**< required size */
39  )
40 {
41  assert(pattern != NULL);
42 
43  if( size > pattern->size )
44  {
45  int newsize = MAX(4, 2*size);
46  assert(newsize > size);
47 
48  SCIP_ALLOC( BMSreallocBlockMemoryArray(pattern->blkmem, &pattern->types, pattern->size, newsize) );
49  SCIP_ALLOC( BMSreallocBlockMemoryArray(pattern->blkmem, &pattern->xs, pattern->size, newsize) );
50  SCIP_ALLOC( BMSreallocBlockMemoryArray(pattern->blkmem, &pattern->ys, pattern->size, newsize) );
51  pattern->size = newsize;
52  }
53 
54  return SCIP_OKAY;
55 }
56 
57 /** auxiliary function to create a pattern */
58 static
60  SCIP* scip, /**< SCIP data structure */
61  SCIP_PATTERN** pattern, /**< pointer to store pattern */
62  SCIP_PATTERNTYPE patterntype, /**< pattern type */
63  int type /**< circle type (not needed for rectangular patterns) */
64  )
65 {
66  assert(scip != NULL);
67  assert(pattern != NULL);
68 
69  SCIP_CALL( SCIPallocBlockMemory(scip, pattern) );
70  BMSclearMemory(*pattern);
71 
72  (*pattern)->blkmem = SCIPblkmem(scip);
73  (*pattern)->type = type;
74  SCIPpatternCapture(*pattern);
75 
76  (*pattern)->packable = SCIP_PACKABLE_UNKNOWN;
77  (*pattern)->patterntype = patterntype;
78  (*pattern)->type = type;
79 
80  return SCIP_OKAY;
81 }
82 
83 /*
84  * interface methods
85  */
86 
87 /** creates an empty circular pattern */
89  SCIP* scip, /**< SCIP data structure */
90  SCIP_PATTERN** pattern, /**< pointer to store pattern */
91  int type /**< circle type (not needed for rectangular patterns) */
92  )
93 {
94  return createPattern(scip, pattern, SCIP_PATTERNTYPE_CIRCULAR, type);
95 }
96 
97 /** creates an empty rectangular pattern */
99  SCIP* scip, /**< SCIP data structure */
100  SCIP_PATTERN** pattern /**< pointer to store pattern */
101  )
102 {
103  return createPattern(scip, pattern, SCIP_PATTERNTYPE_RECTANGULAR, -1);
104 }
105 
106 /** captures a pattern */
108  SCIP_PATTERN* pattern /**< pattern */
109  )
110 {
111  assert(pattern != NULL);
112  assert(pattern->nlocks >= 0);
113  ++(pattern->nlocks);
114 }
115 
116 /* frees a pattern */
118  SCIP* scip, /**< SCIP data structure */
119  SCIP_PATTERN** pattern /**< pointer to free pattern */
120  )
121 {
122  assert(scip != NULL);
123  assert(pattern != NULL);
124  assert(*pattern != NULL);
125  assert((*pattern)->nlocks > 0);
126 
127  /* reduce locks */
128  --((*pattern)->nlocks);
129 
130  /* free memory if the pattern is not used anymore */
131  if( (*pattern)->nlocks == 0 )
132  {
133  SCIPfreeBlockMemoryArrayNull(scip, &(*pattern)->ys, (*pattern)->size);
134  SCIPfreeBlockMemoryArrayNull(scip, &(*pattern)->xs, (*pattern)->size);
135  SCIPfreeBlockMemoryArrayNull(scip, &(*pattern)->types, (*pattern)->size);
136  SCIPfreeBlockMemory(scip, pattern);
137  }
138  else
139  *pattern = NULL;
140 }
141 
142 /** copies a pattern */
144  SCIP* scip, /**< SCIP data structure */
145  SCIP_PATTERN* pattern, /**< pattern to copy */
146  SCIP_PATTERN** copy /**< pointer to store the copy */
147  )
148 {
149  int i;
150 
151  assert(pattern != NULL);
152  assert(copy != NULL);
153 
154  SCIP_CALL( createPattern(scip, copy, pattern->patterntype, pattern->type) );
155  assert(*copy != NULL);
156 
157  /* ensure that we can store all elements */
158  SCIP_CALL( ensureElemSize(*copy, pattern->nelems) );
159 
160  /* add elements */
161  for( i = 0; i < pattern->nelems; ++i )
162  {
163  SCIP_CALL( SCIPpatternAddElement(*copy, pattern->types[i], pattern->xs[i], pattern->ys[i]) );
164  }
165 
166  /* copy packable status */
167  (*copy)->packable = pattern->packable;
168 
169  return SCIP_OKAY;
170 }
171 
172 /** adds an element of a given type to a pattern; packable status does not change */
174  SCIP_PATTERN* pattern, /**< pattern */
175  int type, /**< element of a given type */
176  SCIP_Real x, /**< x-coordinate (SCIP_INVALID: unknown) */
177  SCIP_Real y /**< y-coordinate (SCIP_INVALID: unknown) */
178  )
179 {
180  assert(pattern != NULL);
181  assert(type >= 0);
182 
183  SCIP_CALL( ensureElemSize(pattern, pattern->nelems + 1) );
184  pattern->types[pattern->nelems] = type;
185  pattern->xs[pattern->nelems] = x;
186  pattern->ys[pattern->nelems] = y;
187 
188  ++(pattern->nelems);
189 
190  return SCIP_OKAY;
191 }
192 
193 /** removes the last k elements */
195  SCIP_PATTERN* pattern, /**< pattern */
196  int k /**< number of elements to remove */
197  )
198 {
199  assert(pattern != NULL);
200  assert(pattern->nelems >= k);
201 
202  pattern->nelems -= k;
203 }
204 
205 /** returns the total number of elements */
207  SCIP_PATTERN* pattern /**< pattern */
208  )
209 {
210  assert(pattern != NULL);
211 
212  return pattern->nelems;
213 }
214 
215 /** returns the type of the i-th element */
217  SCIP_PATTERN* pattern, /**< pattern */
218  int i /**< index */
219  )
220 {
221  assert(pattern != NULL);
222  assert(i >= 0 && i < pattern->nelems);
223 
224  return pattern->types[i];
225 }
226 
227 /** returns the total number of elements of a given type */
229  SCIP_PATTERN* pattern, /**< pattern */
230  int type /**< type */
231  )
232 {
233  int counter = 0;
234  int i;
235 
236  assert(pattern != NULL);
237 
238  for( i = 0; i < pattern->nelems; ++i )
239  {
240  if( pattern->types[i] == type )
241  ++(counter);
242  }
243 
244  return counter;
245 }
246 
247 /** returns the x-coordinate of an element */
249  SCIP_PATTERN* pattern, /**< pattern */
250  int elem /**< index of the element */
251  )
252 {
253  assert(pattern != NULL);
254  assert(elem >= 0 && elem < pattern->nelems);
255 
256  return pattern->xs[elem];
257 }
258 
259 /** returns the y-coordinate of an element */
261  SCIP_PATTERN* pattern, /**< pattern */
262  int elem /**< index of the element */
263  )
264 {
265  assert(pattern != NULL);
266  assert(elem >= 0 && elem < pattern->nelems);
267 
268  return pattern->ys[elem];
269 }
270 
271 /** sets the (x,y) position of an element */
273  SCIP_PATTERN* pattern, /**< pattern */
274  int elem, /**< index of the element */
275  SCIP_Real x, /**< x-coordinate */
276  SCIP_Real y /**< y-coordinate */
277  )
278 {
279  assert(pattern != NULL);
280  assert(elem >= 0 && elem < pattern->nelems);
281 
282  pattern->xs[elem] = x;
283  pattern->ys[elem] = y;
284 }
285 
286 /** returns the type of a pattern */
288  SCIP_PATTERN* pattern /**< pattern */
289  )
290 {
291  assert(pattern != NULL);
292 
293  return pattern->patterntype;
294 }
295 
296 /** returns the type of the boundary circle
297  *
298  * @note this function can only be called for circular patterns
299  */
301  SCIP_PATTERN *pattern /**< pattern */
302 )
303 {
304  assert(pattern != NULL);
305  assert(pattern->patterntype == SCIP_PATTERNTYPE_CIRCULAR);
306 
307  return pattern->type;
308 }
309 
310 /** sets the type of the boundary circle
311  *
312  * @note this function can only be called for circular patterns
313  */
315  SCIP_PATTERN* pattern, /**< pattern */
316  int type /**< type */
317  )
318 {
319  assert(pattern != NULL);
320  assert(pattern->patterntype == SCIP_PATTERNTYPE_CIRCULAR);
321 
322  pattern->type = type;
323 }
324 
325 /** returns the packable status of a pattern */
327  SCIP_PATTERN* pattern /**< pattern */
328  )
329 {
330  assert(pattern != NULL);
331 
332  return pattern->packable;
333 }
334 
335 /** sets the packable status of a pattern */
337  SCIP_PATTERN* pattern, /**< pattern */
338  SCIP_PACKABLE packable /**< packable status */
339  )
340 {
341  assert(pattern != NULL);
342 
343  pattern->packable = packable;
344 }
SCIP_RETCODE SCIPpatternAddElement(SCIP_PATTERN *pattern, int type, SCIP_Real x, SCIP_Real y)
Definition: pattern.c:173
SCIP_RETCODE SCIPpatternCopy(SCIP *scip, SCIP_PATTERN *pattern, SCIP_PATTERN **copy)
Definition: pattern.c:143
SCIP_PACKABLE packable
Definition: pattern.h:51
static SCIP_RETCODE ensureElemSize(SCIP_PATTERN *pattern, int size)
Definition: pattern.c:36
Problem data for ringpacking problem.
enum SCIP_Packable SCIP_PACKABLE
Definition: pattern.h:38
enum SCIP_Patterntype SCIP_PATTERNTYPE
Definition: pattern.h:45
int type
Definition: pattern.h:58
SCIP_PATTERNTYPE patterntype
Definition: pattern.h:50
int SCIPpatternGetCircleType(SCIP_PATTERN *pattern)
Definition: pattern.c:300
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Real * xs
Definition: pattern.h:52
int nlocks
Definition: pattern.h:57
int SCIPpatternGetNElemens(SCIP_PATTERN *pattern)
Definition: pattern.c:206
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_VAR ** x
Definition: circlepacking.c:54
void SCIPpatternCapture(SCIP_PATTERN *pattern)
Definition: pattern.c:107
int SCIPpatternCountElements(SCIP_PATTERN *pattern, int type)
Definition: pattern.c:228
SCIP_Real * ys
Definition: pattern.h:53
void SCIPpatternRemoveLastElements(SCIP_PATTERN *pattern, int k)
Definition: pattern.c:194
SCIP_PACKABLE SCIPpatternGetPackableStatus(SCIP_PATTERN *pattern)
Definition: pattern.c:326
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
pattern data for ringpacking problem
int * types
Definition: pattern.h:54
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:370
int SCIPpatternGetElementType(SCIP_PATTERN *pattern, int i)
Definition: pattern.c:216
void SCIPpatternSetElementPos(SCIP_PATTERN *pattern, int elem, SCIP_Real x, SCIP_Real y)
Definition: pattern.c:272
SCIP_Real SCIPpatternGetElementPosX(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:248
static SCIP_RETCODE createPattern(SCIP *scip, SCIP_PATTERN **pattern, SCIP_PATTERNTYPE patterntype, int type)
Definition: pattern.c:59
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPpatternCreateRectangular(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:98
#define BMSclearMemory(ptr)
Definition: memory.h:121
SCIP_PATTERNTYPE SCIPpatternGetPatternType(SCIP_PATTERN *pattern)
Definition: pattern.c:287
SCIP_Real SCIPpatternGetElementPosY(SCIP_PATTERN *pattern, int elem)
Definition: pattern.c:260
void SCIPpatternRelease(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:117
SCIP_RETCODE SCIPpatternCreateCircular(SCIP *scip, SCIP_PATTERN **pattern, int type)
Definition: pattern.c:88
#define SCIP_Real
Definition: def.h:163
SCIP_VAR ** y
Definition: circlepacking.c:55
void SCIPpatternSetPackableStatus(SCIP_PATTERN *pattern, SCIP_PACKABLE packable)
Definition: pattern.c:336
void SCIPpatternSetType(SCIP_PATTERN *pattern, int type)
Definition: pattern.c:314
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
#define SCIP_ALLOC(x)
Definition: def.h:381
int size
Definition: pattern.h:55
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:449
BMS_BLKMEM * blkmem
Definition: pattern.h:49
int nelems
Definition: pattern.h:56