Changeset 1211:1bafdbd2fc46 in lemon
 Timestamp:
 03/20/10 11:03:12 (10 years ago)
 Branch:
 default
 Children:
 1212:15d7c5eadaca, 1213:4e8787627db3, 1214:387483bf0a56, 1240:ee9bac10f58e
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/radix_sort_test.cc
r467 r1211 26 26 27 27 #include <vector> 28 #include <list> 28 29 #include <algorithm> 29 30 … … 40 41 int negate(int a) { return  a; } 41 42 42 43 void generateIntSequence(int n, std::vector<int>& data) { 43 template<class T> 44 bool isTheSame(T &a, T&b) 45 { 46 typename T::iterator ai=a.begin(); 47 typename T::iterator bi=b.begin(); 48 for(;ai!=a.end()bi!=b.end();++ai,++bi) 49 if(*ai!=*bi) return false; 50 return ai==a.end()&&bi==b.end(); 51 } 52 53 template<class T> 54 T listsort(typename T::iterator b, typename T::iterator e) 55 { 56 if(b==e) return T(); 57 typename T::iterator bn=b; 58 if(++bn==e) { 59 T l; 60 l.push_back(*b); 61 return l; 62 } 63 typename T::iterator m=b; 64 bool x=false; 65 for(typename T::iterator i=b;i!=e;++i,x=!x) 66 if(x) ++m; 67 T l1(listsort<T>(b,m)); 68 T l2(listsort<T>(m,e)); 69 T l; 70 while((!l1.empty())&&(!l2.empty())) 71 if(l1.front()<=l2.front()) 72 { 73 l.push_back(l1.front()); 74 l1.pop_front(); 75 } 76 else { 77 l.push_back(l2.front()); 78 l2.pop_front(); 79 } 80 while(!l1.empty()) 81 { 82 l.push_back(l1.front()); 83 l1.pop_front(); 84 } 85 while(!l2.empty()) 86 { 87 l.push_back(l2.front()); 88 l2.pop_front(); 89 } 90 return l; 91 } 92 93 template<class T> 94 void generateIntSequence(int n, T & data) { 44 95 int prime = 9973; 45 96 int root = 136, value = 1; … … 50 101 } 51 102 52 void generateCharSequence(int n, std::vector<unsigned char>& data) { 103 template<class T> 104 void generateCharSequence(int n, T & data) { 53 105 int prime = 251; 54 106 int root = 3, value = root; … … 72 124 } 73 125 74 radixSort(data2.begin(), data2.end(), Negate()); 126 // radixSort(data2.begin(), data2.end(), Negate()); 127 // for (int i = 0; i < n; ++i) { 128 // check(data1[i] == data2[n  1  i], "Test failed"); 129 // } 130 131 // radixSort(data2.begin(), data2.end(), negate); 132 // for (int i = 0; i < n; ++i) { 133 // check(data1[i] == data2[n  1  i], "Test failed"); 134 // } 135 136 } 137 138 { 139 std::vector<unsigned char> data1(n); 140 generateCharSequence(n, data1); 141 142 std::vector<unsigned char> data2(data1); 143 std::sort(data1.begin(), data1.end()); 144 145 radixSort(data2.begin(), data2.end()); 146 for (int i = 0; i < n; ++i) { 147 check(data1[i] == data2[i], "Test failed"); 148 } 149 150 } 151 { 152 std::list<int> data1; 153 generateIntSequence(n, data1); 154 155 std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end())); 156 157 radixSort(data1.begin(), data1.end()); 158 159 check(isTheSame(data1,data2), "Test failed"); 160 161 162 // radixSort(data2.begin(), data2.end(), Negate()); 163 // check(isTheSame(data1,data2), "Test failed"); 164 // for (int i = 0; i < n; ++i) { 165 // check(data1[i] == data2[n  1  i], "Test failed"); 166 // } 167 168 // radixSort(data2.begin(), data2.end(), negate); 169 // for (int i = 0; i < n; ++i) { 170 // check(data1[i] == data2[n  1  i], "Test failed"); 171 // } 172 173 } 174 175 { 176 std::list<unsigned char> data1(n); 177 generateCharSequence(n, data1); 178 179 std::list<unsigned char> data2(listsort<std::list<unsigned char> > 180 (data1.begin(), 181 data1.end())); 182 183 radixSort(data1.begin(), data1.end()); 184 check(isTheSame(data1,data2), "Test failed"); 185 186 } 187 } 188 189 190 void checkStableRadixSort() { 191 { 192 std::vector<int> data1; 193 generateIntSequence(n, data1); 194 195 std::vector<int> data2(data1); 196 std::sort(data1.begin(), data1.end()); 197 198 stableRadixSort(data2.begin(), data2.end()); 199 for (int i = 0; i < n; ++i) { 200 check(data1[i] == data2[i], "Test failed"); 201 } 202 203 stableRadixSort(data2.begin(), data2.end(), Negate()); 75 204 for (int i = 0; i < n; ++i) { 76 205 check(data1[i] == data2[n  1  i], "Test failed"); 77 206 } 78 207 79 radixSort(data2.begin(), data2.end(), negate);208 stableRadixSort(data2.begin(), data2.end(), negate); 80 209 for (int i = 0; i < n; ++i) { 81 210 check(data1[i] == data2[n  1  i], "Test failed"); 82 211 } 83 84 212 } 85 213 … … 97 225 98 226 } 99 } 100 101 102 void checkStableRadixSort() { 103 { 104 std::vector<int> data1; 105 generateIntSequence(n, data1); 106 107 std::vector<int> data2(data1); 108 std::sort(data1.begin(), data1.end()); 109 110 stableRadixSort(data2.begin(), data2.end()); 111 for (int i = 0; i < n; ++i) { 112 check(data1[i] == data2[i], "Test failed"); 113 } 114 115 stableRadixSort(data2.begin(), data2.end(), Negate()); 116 for (int i = 0; i < n; ++i) { 117 check(data1[i] == data2[n  1  i], "Test failed"); 118 } 119 120 stableRadixSort(data2.begin(), data2.end(), negate); 121 for (int i = 0; i < n; ++i) { 122 check(data1[i] == data2[n  1  i], "Test failed"); 123 } 124 } 125 126 { 127 std::vector<unsigned char> data1(n); 128 generateCharSequence(n, data1); 129 130 std::vector<unsigned char> data2(data1); 131 std::sort(data1.begin(), data1.end()); 132 133 radixSort(data2.begin(), data2.end()); 134 for (int i = 0; i < n; ++i) { 135 check(data1[i] == data2[i], "Test failed"); 136 } 227 { 228 std::list<int> data1; 229 generateIntSequence(n, data1); 230 231 std::list<int> data2(listsort<std::list<int> >(data1.begin(), 232 data1.end())); 233 stableRadixSort(data1.begin(), data1.end()); 234 check(isTheSame(data1,data2), "Test failed"); 235 236 // stableRadixSort(data2.begin(), data2.end(), Negate()); 237 // for (int i = 0; i < n; ++i) { 238 // check(data1[i] == data2[n  1  i], "Test failed"); 239 // } 240 241 // stableRadixSort(data2.begin(), data2.end(), negate); 242 // for (int i = 0; i < n; ++i) { 243 // check(data1[i] == data2[n  1  i], "Test failed"); 244 // } 245 } 246 247 { 248 std::list<unsigned char> data1(n); 249 generateCharSequence(n, data1); 250 251 std::list<unsigned char> data2(listsort<std::list<unsigned char> > 252 (data1.begin(), 253 data1.end())); 254 radixSort(data1.begin(), data1.end()); 255 check(isTheSame(data1,data2), "Test failed"); 137 256 138 257 }
Note: See TracChangeset
for help on using the changeset viewer.