Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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) {
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 
156 
157  }
158 }}
159 
160 // STATISTICS: test-int
161 
Relation for sorting integers in increasing order.
Definition: sorted.cpp:52
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
bool operator()(const int x, const int y)
Test whether x is less than y
Definition: sorted.cpp:55
static const int n
Number of variables to be sorted.
Definition: sorted.cpp:102
Test sorted without permutation variables
Definition: sorted.cpp:61
Passing integer variables.
Definition: int.hh:656
static const int n
Number of variables to be sorted.
Definition: sorted.cpp:64
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Computation spaces.
Definition: core.hpp:1742
PermVar permvar
Definition: sorted.cpp:154
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition: sorted.cpp:69
PermVar(void)
Create and register test.
Definition: sorted.cpp:105
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: sorted.cpp:88
Integer variable array.
Definition: int.hh:763
NoVar novar
Definition: sorted.cpp:153
NoVar(void)
Create and register test.
Definition: sorted.cpp:67
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Test sorted with permutation variables
Definition: sorted.cpp:99
Base class for assignments
Definition: int.hh:59
General test support.
Definition: afc.cpp:39
virtual bool solution(const Assignment &xyz) const
Test whether xyz is solution
Definition: sorted.cpp:107
Gecode::IntArgs i({1, 2, 3, 4})
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
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyz)
Post constraint on xyz.
Definition: sorted.cpp:143