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