main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Feb 8 2021 00:00:00 for Gecode by
doxygen
1.8.20
test
int
sorted.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5
*
6
* Contributing authors:
7
* Christian Schulte <schulte@gecode.org>
8
*
9
* Copyright:
10
* Patrick Pekczynski, 2005
11
* Christian Schulte, 2007
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include "
test/int.hh
"
39
40
namespace
Test
{
namespace
Int {
41
43
namespace
Sorted {
44
50
52
class
SortIntMin
{
53
public
:
55
bool
operator()
(
const
int
x
,
const
int
y
) {
56
return
x
<
y
;
57
}
58
};
59
61
class
NoVar
:
public
Test
{
62
protected
:
64
static
const
int
n
= 3;
65
public
:
67
NoVar
(
void
) :
Test
(
"Sorted::NoVar"
,2*
n
,0,3) {}
69
virtual
bool
solution
(
const
Assignment
& xy)
const
{
70
int
x
[
n
],
y
[
n
];
71
for
(
int
i
=0;
i
<3;
i
++) {
72
x
[
i
]=xy[
i
];
y
[
i
]=xy[
n
+
i
];
73
}
74
75
for
(
int
i
=0;
i
<
n
-1;
i
++)
76
if
(
y
[
i
]>
y
[
i
+1])
77
return
false
;
78
79
SortIntMin
sim;
80
Gecode::Support::quicksort<int,SortIntMin>(
x
,
n
,sim);
81
82
for
(
int
i
=0;
i
<
n
;
i
++)
83
if
(
x
[
i
] !=
y
[
i
])
84
return
false
;
85
return
true
;
86
}
88
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
& xy) {
89
Gecode::IntVarArgs
x
(
n
),
y
(
n
);
90
for
(
int
i
=0;
i
<
n
;
i
++) {
91
x
[
i
]=xy[
i
];
y
[
i
]=xy[
n
+
i
];
92
}
93
Gecode::sorted
(home,
x
,
y
);
94
}
95
};
96
97
99
class
PermVar
:
public
Test
{
100
protected
:
102
static
const
int
n
= 3;
103
public
:
105
PermVar
(
void
) :
Test
(
"Sorted::PermVar"
,3*
n
,0,2) {}
107
virtual
bool
solution
(
const
Assignment
& xyz)
const
{
108
int
x
[
n
],
y
[
n
],
z
[
n
];
109
for
(
int
i
=0;
i
<
n
;
i
++) {
110
x
[
i
]=xyz[
i
];
y
[
i
]=xyz[
n
+
i
];
z
[
i
]=xyz[2*
n
+
i
];
111
}
112
// check for permutation
113
for
(
int
i
=0;
i
<
n
;
i
++)
114
for
(
int
j=
i
+1; j<
n
; j++)
115
if
(
z
[
i
]==
z
[j])
116
return
false
;
117
118
// y must to be sorted
119
for
(
int
i
=0;
i
<
n
-1;
i
++)
120
if
(
y
[
i
]>
y
[
i
+1])
121
return
false
;
122
123
// check whether permutation is in range
124
for
(
int
i
=0;
i
<
n
;
i
++)
125
if
((
z
[
i
] < 0) || (
z
[
i
] >=
n
))
126
return
false
;
127
128
// check whether permutation info is correct
129
for
(
int
i
=0;
i
<
n
;
i
++)
130
if
(
x
[
i
] !=
y
[
z
[
i
]])
131
return
false
;
132
133
// check for sorting
134
SortIntMin
sim;
135
Gecode::Support::quicksort<int,SortIntMin>(
x
,
n
,sim);
136
for
(
int
i
=0;
i
<
n
;
i
++)
137
if
(
x
[
i
] !=
y
[
i
])
138
return
false
;
139
140
return
true
;
141
}
143
virtual
void
post
(
Gecode::Space
& home,
Gecode::IntVarArray
& xyz) {
144
Gecode::IntVarArgs
x
(
n
),
y
(
n
),
z
(
n
);
145
for
(
int
i
=0;
i
<
n
;
i
++) {
146
x
[
i
]=xyz[
i
];
y
[
i
]=xyz[
n
+
i
];
z
[
i
]=xyz[2*
n
+
i
];
147
}
148
Gecode::sorted
(home,
x
,
y
,
z
);
149
}
150
};
151
152
153
NoVar
novar
;
154
PermVar
permvar
;
156
157
}
158
}}
159
160
// STATISTICS: test-int
161
Test::Int::Sorted::SortIntMin
Relation for sorting integers in increasing order.
Definition:
sorted.cpp:52
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:767
Test::Int::Sorted::SortIntMin::operator()
bool operator()(const int x, const int y)
Test whether x is less than y
Definition:
sorted.cpp:55
Test::Int::Sorted::PermVar::n
static const int n
Number of variables to be sorted.
Definition:
sorted.cpp:102
Test::Int::Sorted::NoVar
Test sorted without permutation variables
Definition:
sorted.cpp:61
Gecode::IntVarArgs
Passing integer variables.
Definition:
int.hh:656
Test::Int::Sorted::NoVar::n
static const int n
Number of variables to be sorted.
Definition:
sorted.cpp:64
Gecode::z
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition:
set.hh:767
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Test::Int::Sorted::permvar
PermVar permvar
Definition:
sorted.cpp:154
int.hh
Test::Int::Sorted::NoVar::solution
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition:
sorted.cpp:69
Test::Int::Sorted::PermVar::PermVar
PermVar(void)
Create and register test.
Definition:
sorted.cpp:105
Test::Int::Sorted::NoVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition:
sorted.cpp:88
Gecode::IntVarArray
Integer variable array.
Definition:
int.hh:763
Test::Int::Sorted::novar
NoVar novar
Definition:
sorted.cpp:153
Test::Int::Sorted::NoVar::NoVar
NoVar(void)
Create and register test.
Definition:
sorted.cpp:67
x
Node * x
Pointer to corresponding Boolean expression node.
Definition:
bool-expr.cpp:249
Test::Int::Sorted::PermVar
Test sorted with permutation variables
Definition:
sorted.cpp:99
Test::Int::Assignment
Base class for assignments
Definition:
int.hh:59
Test
General test support.
Definition:
afc.cpp:39
Test::Int::Sorted::PermVar::solution
virtual bool solution(const Assignment &xyz) const
Test whether xyz is solution
Definition:
sorted.cpp:107
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::sorted
void sorted(Home home, const IntVarArgs &x, const IntVarArgs &y, const IntVarArgs &z, IntPropLevel)
Post propagator that y is x sorted in increasing order.
Definition:
sorted.cpp:39
Test::Int::Sorted::PermVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyz)
Post constraint on xyz.
Definition:
sorted.cpp:143