sorted.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2005
* Christian Schulte, 2007
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include "test/int.hh"
namespace Test { namespace Int {
namespace Sorted {
class SortIntMin {
public:
bool operator()(const int x, const int y) {
return x<y;
}
};
class NoVar : public Test {
protected:
static const int n = 3;
public:
NoVar(void) : Test("Sorted::NoVar",2*n,0,3) {}
virtual bool solution(const Assignment& xy) const {
int x[n], y[n];
for (int i=0;i<3; i++) {
x[i]=xy[i]; y[i]=xy[n+i];
}
for (int i=0; i<n-1; i++)
if (y[i]>y[i+1])
return false;
SortIntMin sim;
Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
for (int i=0; i<n; i++)
if (x[i] != y[i])
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
Gecode::IntVarArgs x(n), y(n);
for (int i=0; i<n; i++) {
x[i]=xy[i]; y[i]=xy[n+i];
}
Gecode::sorted(home,x,y);
}
};
class PermVar : public Test {
protected:
static const int n = 3;
public:
PermVar(void) : Test("Sorted::PermVar",3*n,0,2) {}
virtual bool solution(const Assignment& xyz) const {
int x[n], y[n], z[n];
for (int i=0; i<n; i++) {
x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
}
// check for permutation
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
if (z[i]==z[j])
return false;
// y must to be sorted
for (int i=0; i<n-1; i++)
if (y[i]>y[i+1])
return false;
// check whether permutation is in range
for (int i=0; i<n; i++)
if ((z[i] < 0) || (z[i] >= n))
return false;
// check whether permutation info is correct
for (int i=0; i<n; i++)
if (x[i] != y[z[i]])
return false;
// check for sorting
SortIntMin sim;
Gecode::Support::quicksort<int,SortIntMin>(x,n,sim);
for (int i=0; i<n; i++)
if (x[i] != y[i])
return false;
return true;
}
virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyz) {
Gecode::IntVarArgs x(n), y(n), z(n);
for (int i=0; i<n; i++) {
x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i];
}
Gecode::sorted(home,x,y,z);
}
};
NoVar novar;
PermVar permvar;
}
}}
// STATISTICS: test-int
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Int::Assignment
Base class for assignments
Definition int.hh:59
Test::Int::Sorted::NoVar
Test sorted without permutation variables
Definition sorted.cpp:61
Test::Int::Sorted::NoVar::solution
virtual bool solution(const Assignment &xy) const
Test whether xy is solution
Definition sorted.cpp:69
Test::Int::Sorted::NoVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition sorted.cpp:88
Test::Int::Sorted::NoVar::NoVar
NoVar(void)
Create and register test.
Definition sorted.cpp:67
Test::Int::Sorted::NoVar::n
static const int n
Number of variables to be sorted.
Definition sorted.cpp:64
Test::Int::Sorted::PermVar
Test sorted with permutation variables
Definition sorted.cpp:99
Test::Int::Sorted::PermVar::post
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xyz)
Post constraint on xyz.
Definition sorted.cpp:143
Test::Int::Sorted::PermVar::n
static const int n
Number of variables to be sorted.
Definition sorted.cpp:102
Test::Int::Sorted::PermVar::solution
virtual bool solution(const Assignment &xyz) const
Test whether xyz is solution
Definition sorted.cpp:107
Test::Int::Sorted::PermVar::PermVar
PermVar(void)
Create and register test.
Definition sorted.cpp:105
Test::Int::Sorted::SortIntMin
Relation for sorting integers in increasing order.
Definition sorted.cpp:52
Test::Int::Sorted::SortIntMin::operator()
bool operator()(const int x, const int y)
Test whether x is less than y
Definition sorted.cpp:55
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode::sorted
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
Test::Int::Sorted
Tests for sorted constraints
Definition sorted.cpp:43
Test::Int::Sorted::permvar
PermVar permvar
Definition sorted.cpp:154
Test::Int::Sorted::novar
NoVar novar
Definition sorted.cpp:153
Test::Int
Testing finite domain integers.
Definition int.cpp:40
Test
General test support.
Definition afc.cpp:39
int.hh