main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:44 for Gecode by
doxygen
1.8.3.1
gecode
int
view-val-graph.hh
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
* Guido Tack <tack@gecode.org>
6
*
7
* Copyright:
8
* Christian Schulte, 2002
9
* Guido Tack, 2004
10
*
11
* Last modified:
12
* $Date: 2011-09-08 22:34:40 +1000 (Thu, 08 Sep 2011) $ by $Author: schulte $
13
* $Revision: 12395 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
#ifndef __GECODE_INT_VIEW_VAL_GRAPH_HH__
41
#define __GECODE_INT_VIEW_VAL_GRAPH_HH__
42
43
#include <
gecode/int.hh
>
44
49
namespace
Gecode {
namespace
Int {
namespace
ViewValGraph {
50
57
template
<
class
T>
58
class
CombPtrFlag
{
59
private
:
61
ptrdiff_t cpf;
62
public
:
64
CombPtrFlag
(T*
p1
, T*
p2
);
66
void
init
(T* p1, T* p2);
68
T*
ptr
(T* p)
const
;
70
int
is_set
(
void
)
const
;
72
void
set
(void);
74
void
unset
(
void
);
75
};
76
78
class
BiLink
{
79
private
:
81
BiLink
* _prev;
83
BiLink
* _next;
84
public
:
86
BiLink
(
void
);
88
BiLink
*
prev
(
void
)
const
;
90
BiLink
*
next
(
void
)
const
;
92
void
prev
(
BiLink
* l);
94
void
next
(
BiLink
* l);
96
void
add
(
BiLink
* l);
98
void
unlink
(
void
);
100
void
mark
(
void
);
102
bool
marked
(
void
)
const
;
104
bool
empty
(
void
)
const
;
105
};
106
107
108
template
<
class
View>
class
Edge
;
109
119
template
<
class
View>
120
class
Node
:
public
BiLink
{
121
public
:
123
Edge<View>
*
iter
;
125
unsigned
int
low
,
min
,
comp
;
127
Node
(
void
);
129
Edge<View>
*
edge_fst
(
void
)
const
;
131
Edge<View>
*
edge_lst
(
void
)
const
;
132
134
static
void
*
operator
new
(size_t,
Space
&);
136
static
void
operator
delete
(
void
*, size_t);
138
static
void
operator
delete
(
void
*,
Space
&);
139
};
140
145
template
<
class
View>
146
class
ValNode
:
public
Node
<View> {
147
protected
:
149
const
int
_val
;
151
Edge<View>
*
_matching
;
153
ValNode<View>
*
_next_val
;
154
public
:
156
ValNode
(
int
v
);
158
ValNode
(
int
v
,
ValNode<View>
* n);
160
int
val
(
void
)
const
;
162
void
matching
(
Edge<View>
*
m
);
164
Edge<View>
*
matching
(
void
)
const
;
166
ValNode<View>
**
next_val_ref
(
void
);
168
ValNode<View>
*
next_val
(
void
)
const
;
170
void
next_val
(
ValNode<View>
*
v
);
171
};
172
177
template
<
class
View>
178
class
ViewNode
:
public
Node
<View> {
179
protected
:
181
unsigned
int
_size
;
183
View
_view
;
185
Edge<View>
*
_val_edges
;
186
public
:
188
ViewNode
(
void
);
190
ViewNode
(View x);
192
Edge<View>
*
val_edges
(
void
)
const
;
194
Edge<View>
**
val_edges_ref
(
void
);
196
bool
fake
(
void
)
const
;
198
View
view
(
void
)
const
;
200
void
update
(
void
);
202
bool
changed
(
void
)
const
;
204
bool
matched
(
void
)
const
;
205
};
206
211
template
<
class
View>
212
class
Edge
:
public
BiLink
{
213
protected
:
215
Edge<View>
*
_next_edge
;
217
CombPtrFlag<Node<View>
>
sd
;
218
public
:
220
Edge
(
ValNode<View>
*
v
,
ViewNode<View>
* x);
222
Edge
(
ValNode<View>
*
v
,
ViewNode<View>
* x,
Edge<View>
* n);
224
Node<View>
*
dst
(
Node<View>
* s)
const
;
225
227
ViewNode<View>
*
view
(
ValNode<View>
*
v
)
const
;
229
ValNode<View>
*
val
(
ViewNode<View>
* x)
const
;
230
232
bool
used
(
Node<View>
*
v
)
const
;
234
void
use
(
void
);
236
void
free
(
void
);
237
239
void
revert
(
Node<View>
*
d
);
240
242
Edge<View>
*
next_edge
(
void
)
const
;
244
Edge<View>
**
next_edge_ref
(
void
);
246
Edge<View>
*
next
(
void
)
const
;
247
249
static
void
*
operator
new
(size_t,
Space
&);
251
static
void
operator
delete
(
void
*, size_t);
253
static
void
operator
delete
(
void
*,
Space
&);
254
};
255
257
template
<
class
View>
258
class
IterPruneVal
{
259
protected
:
261
ViewNode<View>
*
x
;
263
Edge<View>
*
e
;
264
public
:
266
267
268
IterPruneVal
(
ViewNode<View>
*
x
);
270
272
273
274
bool
operator ()
(
void
)
const
;
276
void
operator ++
(
void
);
278
280
281
282
int
val
(
void
)
const
;
284
};
285
286
}}}
287
288
#include <
gecode/int/view-val-graph/comb-ptr-flag.hpp
>
289
#include <
gecode/int/view-val-graph/bi-link.hpp
>
290
#include <
gecode/int/view-val-graph/edge.hpp
>
291
#include <
gecode/int/view-val-graph/node.hpp
>
292
#include <
gecode/int/view-val-graph/iter-prune-val.hpp
>
293
294
namespace
Gecode {
namespace
Int {
namespace
ViewValGraph {
295
297
template
<
class
View>
298
class
Graph
{
299
protected
:
301
ViewNode<View>
**
view
;
303
ValNode<View>
*
val
;
305
int
n_view
;
307
int
n_val
;
309
unsigned
int
count
;
311
typedef
Support::StaticStack<ViewNode<View>
*,
Region
>
ViewNodeStack
;
313
void
init
(
Space
& home,
ViewNode<View>
* x);
315
bool
match
(
ViewNodeStack
&
m
,
ViewNode<View>
* x);
317
void
scc
(
Space
& home);
318
public
:
320
Graph
(
void
);
322
bool
initialized
(
void
)
const
;
324
void
purge
(
void
);
325
};
326
327
}}}
328
329
#include <
gecode/int/view-val-graph/graph.hpp
>
330
331
#endif
332
333
// STATISTICS: int-prop
334