Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
40namespace 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;
81
82 for (int i=0; i<n; i++)
83 if (x[i] != y[i])
84 return false;
85 return true;
86 }
87
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;
136 for (int i=0; i<n; i++)
137 if (x[i] != y[i])
138 return false;
139
140 return true;
141 }
142
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
156
157 }
158}}
159
160// STATISTICS: test-int
161
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Computation spaces.
Definition core.hpp:1744
Base class for assignments
Definition int.hh:59
Test sorted without permutation variables
Definition sorted.cpp:61
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition sorted.cpp:69
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition sorted.cpp:88
NoVar(void)
Create and register test.
Definition sorted.cpp:67
static const int n
Number of variables to be sorted.
Definition sorted.cpp:64
Test sorted with permutation variables
Definition sorted.cpp:99
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyz)
Post constraint on xyz.
Definition sorted.cpp:143
static const int n
Number of variables to be sorted.
Definition sorted.cpp:102
virtual bool solution(const Assignment &xyz) const
Test whether xyz is solution
Definition sorted.cpp:107
PermVar(void)
Create and register test.
Definition sorted.cpp:105
Relation for sorting integers in increasing order.
Definition sorted.cpp:52
bool operator()(const int x, const int y)
Test whether x is less than y
Definition sorted.cpp:55
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
void sorted(Home home, const IntVarArgs &x, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post propagator that y is x sorted in increasing order.
Definition sorted.cpp:58
Tests for sorted constraints
Definition sorted.cpp:43
Testing finite domain integers.
Definition int.cpp:40
General test support.
Definition afc.cpp:39