1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // <algorithm> 11 12 // template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred> 13 // requires ShuffleIterator<Iter> 14 // && CopyConstructible<Pred> 15 // Iter 16 // stable_partition(Iter first, Iter last, Pred pred); 17 18 #include <algorithm> 19 #include <cassert> 20 #include <memory> 21 22 #include "test_macros.h" 23 #include "test_iterators.h" 24 25 struct is_odd 26 { 27 bool operator()(const int& i) const {return i & 1;} 28 }; 29 30 struct odd_first 31 { 32 bool operator()(const std::pair<int,int>& p) const 33 {return p.first & 1;} 34 }; 35 36 template <class Iter> 37 void 38 test() 39 { 40 { // check mixed 41 typedef std::pair<int,int> P; 42 P array[] = 43 { 44 P(0, 1), 45 P(0, 2), 46 P(1, 1), 47 P(1, 2), 48 P(2, 1), 49 P(2, 2), 50 P(3, 1), 51 P(3, 2), 52 P(4, 1), 53 P(4, 2) 54 }; 55 const unsigned size = sizeof(array)/sizeof(array[0]); 56 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 57 assert(base(r) == array + 4); 58 assert(array[0] == P(1, 1)); 59 assert(array[1] == P(1, 2)); 60 assert(array[2] == P(3, 1)); 61 assert(array[3] == P(3, 2)); 62 assert(array[4] == P(0, 1)); 63 assert(array[5] == P(0, 2)); 64 assert(array[6] == P(2, 1)); 65 assert(array[7] == P(2, 2)); 66 assert(array[8] == P(4, 1)); 67 assert(array[9] == P(4, 2)); 68 } 69 { 70 typedef std::pair<int,int> P; 71 P array[] = 72 { 73 P(0, 1), 74 P(0, 2), 75 P(1, 1), 76 P(1, 2), 77 P(2, 1), 78 P(2, 2), 79 P(3, 1), 80 P(3, 2), 81 P(4, 1), 82 P(4, 2) 83 }; 84 const unsigned size = sizeof(array)/sizeof(array[0]); 85 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 86 assert(base(r) == array + 4); 87 assert(array[0] == P(1, 1)); 88 assert(array[1] == P(1, 2)); 89 assert(array[2] == P(3, 1)); 90 assert(array[3] == P(3, 2)); 91 assert(array[4] == P(0, 1)); 92 assert(array[5] == P(0, 2)); 93 assert(array[6] == P(2, 1)); 94 assert(array[7] == P(2, 2)); 95 assert(array[8] == P(4, 1)); 96 assert(array[9] == P(4, 2)); 97 // check empty 98 r = std::stable_partition(Iter(array), Iter(array), odd_first()); 99 assert(base(r) == array); 100 // check one true 101 r = std::stable_partition(Iter(array), Iter(array+1), odd_first()); 102 assert(base(r) == array+1); 103 assert(array[0] == P(1, 1)); 104 // check one false 105 r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first()); 106 assert(base(r) == array+4); 107 assert(array[4] == P(0, 1)); 108 } 109 { // check all false 110 typedef std::pair<int,int> P; 111 P array[] = 112 { 113 P(0, 1), 114 P(0, 2), 115 P(2, 1), 116 P(2, 2), 117 P(4, 1), 118 P(4, 2), 119 P(6, 1), 120 P(6, 2), 121 P(8, 1), 122 P(8, 2) 123 }; 124 const unsigned size = sizeof(array)/sizeof(array[0]); 125 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 126 assert(base(r) == array); 127 assert(array[0] == P(0, 1)); 128 assert(array[1] == P(0, 2)); 129 assert(array[2] == P(2, 1)); 130 assert(array[3] == P(2, 2)); 131 assert(array[4] == P(4, 1)); 132 assert(array[5] == P(4, 2)); 133 assert(array[6] == P(6, 1)); 134 assert(array[7] == P(6, 2)); 135 assert(array[8] == P(8, 1)); 136 assert(array[9] == P(8, 2)); 137 } 138 { // check all true 139 typedef std::pair<int,int> P; 140 P array[] = 141 { 142 P(1, 1), 143 P(1, 2), 144 P(3, 1), 145 P(3, 2), 146 P(5, 1), 147 P(5, 2), 148 P(7, 1), 149 P(7, 2), 150 P(9, 1), 151 P(9, 2) 152 }; 153 const unsigned size = sizeof(array)/sizeof(array[0]); 154 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 155 assert(base(r) == array + size); 156 assert(array[0] == P(1, 1)); 157 assert(array[1] == P(1, 2)); 158 assert(array[2] == P(3, 1)); 159 assert(array[3] == P(3, 2)); 160 assert(array[4] == P(5, 1)); 161 assert(array[5] == P(5, 2)); 162 assert(array[6] == P(7, 1)); 163 assert(array[7] == P(7, 2)); 164 assert(array[8] == P(9, 1)); 165 assert(array[9] == P(9, 2)); 166 } 167 { // check all false but first true 168 typedef std::pair<int,int> P; 169 P array[] = 170 { 171 P(1, 1), 172 P(0, 2), 173 P(2, 1), 174 P(2, 2), 175 P(4, 1), 176 P(4, 2), 177 P(6, 1), 178 P(6, 2), 179 P(8, 1), 180 P(8, 2) 181 }; 182 const unsigned size = sizeof(array)/sizeof(array[0]); 183 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 184 assert(base(r) == array + 1); 185 assert(array[0] == P(1, 1)); 186 assert(array[1] == P(0, 2)); 187 assert(array[2] == P(2, 1)); 188 assert(array[3] == P(2, 2)); 189 assert(array[4] == P(4, 1)); 190 assert(array[5] == P(4, 2)); 191 assert(array[6] == P(6, 1)); 192 assert(array[7] == P(6, 2)); 193 assert(array[8] == P(8, 1)); 194 assert(array[9] == P(8, 2)); 195 } 196 { // check all false but last true 197 typedef std::pair<int,int> P; 198 P array[] = 199 { 200 P(0, 1), 201 P(0, 2), 202 P(2, 1), 203 P(2, 2), 204 P(4, 1), 205 P(4, 2), 206 P(6, 1), 207 P(6, 2), 208 P(8, 1), 209 P(1, 2) 210 }; 211 const unsigned size = sizeof(array)/sizeof(array[0]); 212 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 213 assert(base(r) == array + 1); 214 assert(array[0] == P(1, 2)); 215 assert(array[1] == P(0, 1)); 216 assert(array[2] == P(0, 2)); 217 assert(array[3] == P(2, 1)); 218 assert(array[4] == P(2, 2)); 219 assert(array[5] == P(4, 1)); 220 assert(array[6] == P(4, 2)); 221 assert(array[7] == P(6, 1)); 222 assert(array[8] == P(6, 2)); 223 assert(array[9] == P(8, 1)); 224 } 225 { // check all true but first false 226 typedef std::pair<int,int> P; 227 P array[] = 228 { 229 P(0, 1), 230 P(1, 2), 231 P(3, 1), 232 P(3, 2), 233 P(5, 1), 234 P(5, 2), 235 P(7, 1), 236 P(7, 2), 237 P(9, 1), 238 P(9, 2) 239 }; 240 const unsigned size = sizeof(array)/sizeof(array[0]); 241 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 242 assert(base(r) == array + size-1); 243 assert(array[0] == P(1, 2)); 244 assert(array[1] == P(3, 1)); 245 assert(array[2] == P(3, 2)); 246 assert(array[3] == P(5, 1)); 247 assert(array[4] == P(5, 2)); 248 assert(array[5] == P(7, 1)); 249 assert(array[6] == P(7, 2)); 250 assert(array[7] == P(9, 1)); 251 assert(array[8] == P(9, 2)); 252 assert(array[9] == P(0, 1)); 253 } 254 { // check all true but last false 255 typedef std::pair<int,int> P; 256 P array[] = 257 { 258 P(1, 1), 259 P(1, 2), 260 P(3, 1), 261 P(3, 2), 262 P(5, 1), 263 P(5, 2), 264 P(7, 1), 265 P(7, 2), 266 P(9, 1), 267 P(0, 2) 268 }; 269 const unsigned size = sizeof(array)/sizeof(array[0]); 270 Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first()); 271 assert(base(r) == array + size-1); 272 assert(array[0] == P(1, 1)); 273 assert(array[1] == P(1, 2)); 274 assert(array[2] == P(3, 1)); 275 assert(array[3] == P(3, 2)); 276 assert(array[4] == P(5, 1)); 277 assert(array[5] == P(5, 2)); 278 assert(array[6] == P(7, 1)); 279 assert(array[7] == P(7, 2)); 280 assert(array[8] == P(9, 1)); 281 assert(array[9] == P(0, 2)); 282 } 283 } 284 285 #if TEST_STD_VER >= 11 286 287 struct is_null 288 { 289 template <class P> 290 bool operator()(const P& p) {return p == 0;} 291 }; 292 293 template <class Iter> 294 void 295 test1() 296 { 297 const unsigned size = 5; 298 std::unique_ptr<int> array[size]; 299 Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null()); 300 assert(r == Iter(array+size)); 301 } 302 303 #endif // TEST_STD_VER >= 11 304 305 int main() 306 { 307 test<bidirectional_iterator<std::pair<int,int>*> >(); 308 test<random_access_iterator<std::pair<int,int>*> >(); 309 test<std::pair<int,int>*>(); 310 311 #if TEST_STD_VER >= 11 312 test1<bidirectional_iterator<std::unique_ptr<int>*> >(); 313 #endif 314 } 315
