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