sorted.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * 00009 * Copyright: 00010 * Patrick Pekczynski, 2005 00011 * Christian Schulte, 2007 00012 * 00013 * Last modified: 00014 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00015 * $Revision: 10684 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include "test/int.hh" 00043 00044 namespace Test { namespace Int { 00045 00047 namespace Sorted { 00048 00054 00056 class SortIntMin { 00057 public: 00059 bool operator()(const int x, const int y) { 00060 return x<y; 00061 } 00062 }; 00063 00065 class NoVar : public Test { 00066 protected: 00068 static const int n = 3; 00069 public: 00071 NoVar(void) : Test("Sorted::NoVar",2*n,0,3) {} 00073 virtual bool solution(const Assignment& xy) const { 00074 int x[n], y[n]; 00075 for (int i=0;i<3; i++) { 00076 x[i]=xy[i]; y[i]=xy[n+i]; 00077 } 00078 00079 for (int i=0; i<n-1; i++) 00080 if (y[i]>y[i+1]) 00081 return false; 00082 00083 SortIntMin sim; 00084 Gecode::Support::quicksort<int,SortIntMin>(x,n,sim); 00085 00086 for (int i=0; i<n; i++) 00087 if (x[i] != y[i]) 00088 return false; 00089 return true; 00090 } 00092 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) { 00093 Gecode::IntVarArgs x(n), y(n); 00094 for (int i=0; i<n; i++) { 00095 x[i]=xy[i]; y[i]=xy[n+i]; 00096 } 00097 Gecode::sorted(home,x,y); 00098 } 00099 }; 00100 00101 00103 class PermVar : public Test { 00104 protected: 00106 static const int n = 3; 00107 public: 00109 PermVar(void) : Test("Sorted::PermVar",3*n,0,2) {} 00111 virtual bool solution(const Assignment& xyz) const { 00112 int x[n], y[n], z[n]; 00113 for (int i=0; i<n; i++) { 00114 x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i]; 00115 } 00116 // check for permutation 00117 for (int i=0; i<n; i++) 00118 for (int j=i+1; j<n; j++) 00119 if (z[i]==z[j]) 00120 return false; 00121 00122 // y must to be sorted 00123 for (int i=0; i<n-1; i++) 00124 if (y[i]>y[i+1]) 00125 return false; 00126 00127 // check whether permutation is in range 00128 for (int i=0; i<n; i++) 00129 if ((z[i] < 0) || (z[i] >= n)) 00130 return false; 00131 00132 // check whether permutation info is correct 00133 for (int i=0; i<n; i++) 00134 if (x[i] != y[z[i]]) 00135 return false; 00136 00137 // check for sorting 00138 SortIntMin sim; 00139 Gecode::Support::quicksort<int,SortIntMin>(x,n,sim); 00140 for (int i=0; i<n; i++) 00141 if (x[i] != y[i]) 00142 return false; 00143 00144 return true; 00145 } 00147 virtual void post(Gecode::Space& home, Gecode::IntVarArray& xyz) { 00148 Gecode::IntVarArgs x(n), y(n), z(n); 00149 for (int i=0; i<n; i++) { 00150 x[i]=xyz[i]; y[i]=xyz[n+i]; z[i]=xyz[2*n+i]; 00151 } 00152 Gecode::sorted(home,x,y,z); 00153 } 00154 }; 00155 00156 00157 NoVar novar; 00158 PermVar permvar; 00160 00161 } 00162 }} 00163 00164 // STATISTICS: test-int 00165