1 // This file is part of the ustl library, an STL implementation. 2 // 3 // Copyright (C) 2005 by Mike Sharov <msharov (at) users.sourceforge.net> 4 // This file is free software, distributed under the MIT License. 5 // 6 // \file uctralgo.h 7 // 8 // \brief Implementation of STL algorithms with container shortcuts. 9 // 10 // The function prototypes are copied 11 // exactly from the SGI version of STL documentation along with comments about 12 // their use. The code is NOT the same, though the functionality usually is. 13 // 14 15 #ifndef UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0 16 #define UCTRALGO_H_0D1AEDFA74B09791489FE25B1EC644B0 17 18 #include "uassert.h" 19 20 namespace ustl { 21 22 /// Copy copies elements from the range [first, last) to the range 23 /// [result, result + (last - first)). That is, it performs the assignments 24 /// *result = *first, *(result + 1) = *(first + 1), and so on. [1] Generally, 25 /// for every integer n from 0 to last - first, copy performs the assignment 26 /// *(result + n) = *(first + n). Assignments are performed in forward order, 27 /// i.e. in order of increasing n. 28 /// \ingroup MutatingAlgorithms 29 /// 30 template <typename Container, typename OutputIterator> 31 inline OutputIterator copy (const Container& ctr, OutputIterator result) 32 { 33 return (copy (ctr.begin(), ctr.end(), result)); 34 } 35 36 /// Copy_if copies elements from the range [first, last) to the range 37 /// [result, result + (last - first)) if pred(*i) returns true. 38 /// \ingroup MutatingAlgorithms 39 /// 40 template <typename Container, typename OutputIterator, typename Predicate> 41 inline OutputIterator copy_if (Container& ctr, OutputIterator result, Predicate pred) 42 { 43 return (copy_if (ctr.begin(), ctr.end(), result, pred)); 44 } 45 46 /// For_each applies the function object f to each element in the range 47 /// [first, last); f's return value, if any, is ignored. Applications are 48 /// performed in forward order, i.e. from first to last. For_each returns 49 /// the function object after it has been applied to each element. 50 /// \ingroup MutatingAlgorithms 51 /// 52 template <typename Container, typename UnaryFunction> 53 inline UnaryFunction for_each (Container& ctr, UnaryFunction f) 54 { 55 return (for_each (ctr.begin(), ctr.end(), f)); 56 } 57 58 /// For_each applies the function object f to each element in the range 59 /// [first, last); f's return value, if any, is ignored. Applications are 60 /// performed in forward order, i.e. from first to last. For_each returns 61 /// the function object after it has been applied to each element. 62 /// \ingroup MutatingAlgorithms 63 /// 64 template <typename Container, typename UnaryFunction> 65 inline UnaryFunction for_each (const Container& ctr, UnaryFunction f) 66 { 67 return (for_each (ctr.begin(), ctr.end(), f)); 68 } 69 70 /// Returns the first iterator i in the range [first, last) such that 71 /// *i == value. Returns last if no such iterator exists. 72 /// \ingroup SearchingAlgorithms 73 /// 74 template <typename Container, typename EqualityComparable> 75 inline typename Container::const_iterator find (const Container& ctr, const EqualityComparable& value) 76 { 77 return (find (ctr.begin(), ctr.end(), value)); 78 } 79 template <typename Container, typename EqualityComparable> 80 inline typename Container::iterator find (Container& ctr, const EqualityComparable& value) 81 { 82 return (find (ctr.begin(), ctr.end(), value)); 83 } 84 85 /// Returns the first iterator i in the range [first, last) such that 86 /// pred(*i) is true. Returns last if no such iterator exists. 87 /// \ingroup SearchingAlgorithms 88 /// 89 template <typename Container, typename Predicate> 90 inline typename Container::const_iterator find_if (const Container& ctr, Predicate pred) 91 { 92 return (find_if (ctr.begin(), ctr.end(), pred)); 93 } 94 template <typename Container, typename Predicate> 95 inline typename Container::iterator find_if (Container& ctr, Predicate pred) 96 { 97 return (find_if (ctr.begin(), ctr.end(), pred)); 98 } 99 100 /// Count finds the number of elements in [first, last) that are equal 101 /// to value. More precisely, the first version of count returns the 102 /// number of iterators i in [first, last) such that *i == value. 103 /// \ingroup ConditionAlgorithms 104 /// 105 template <typename Container, typename EqualityComparable> 106 inline size_t count (const Container& ctr, const EqualityComparable& value) 107 { 108 return (count (ctr.begin(), ctr.end(), value)); 109 } 110 111 /// Count_if finds the number of elements in [first, last) that satisfy the 112 /// predicate pred. More precisely, the first version of count_if returns the 113 /// number of iterators i in [first, last) such that pred(*i) is true. 114 /// \ingroup ConditionAlgorithms 115 /// 116 template <typename Container, typename Predicate> 117 inline size_t count_if (const Container& ctr, Predicate pred) 118 { 119 return (count_if (ctr.begin(), ctr.end(), pred)); 120 } 121 122 /// The first version of transform performs the operation op(*i) for each 123 /// iterator i in the range [first, last), and assigns the result of that 124 /// operation to *o, where o is the corresponding output iterator. That is, 125 /// for each n such that 0 <= n < last - first, it performs the assignment 126 /// *(result + n) = op(*(first + n)). 127 /// The return value is result + (last - first). 128 /// \ingroup MutatingAlgorithms 129 /// 130 template <typename Container, typename UnaryFunction> 131 inline void transform (Container& ctr, UnaryFunction op) 132 { 133 transform (ctr.begin(), ctr.end(), ctr.begin(), op); 134 } 135 136 /// The first version of transform performs the operation op(*i) for each 137 /// iterator i in the range [first, last), and assigns the result of that 138 /// operation to *o, where o is the corresponding output iterator. That is, 139 /// for each n such that 0 <= n < last - first, it performs the assignment 140 /// *(result + n) = op(*(first + n)). 141 /// The return value is result + (last - first). 142 /// \ingroup MutatingAlgorithms 143 /// 144 template <typename Container, typename OutputIterator, typename UnaryFunction> 145 inline OutputIterator transform (Container& ctr, OutputIterator result, UnaryFunction op) 146 { 147 return (transform (ctr.begin(), ctr.end(), result, op)); 148 } 149 150 /// The second version of transform is very similar, except that it uses a 151 /// Binary Function instead of a Unary Function: it performs the operation 152 /// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns 153 /// the result to *o, where i2 is the corresponding iterator in the second 154 /// input range and where o is the corresponding output iterator. That is, 155 /// for each n such that 0 <= n < last1 - first1, it performs the assignment 156 /// *(result + n) = op(*(first1 + n), *(first2 + n). 157 /// The return value is result + (last1 - first1). 158 /// \ingroup MutatingAlgorithms 159 /// 160 template <typename Container, typename InputIterator, typename OutputIterator, typename BinaryFunction> 161 inline OutputIterator transform (Container& ctr, InputIterator first, OutputIterator result, BinaryFunction op) 162 { 163 return (transform (ctr.begin(), ctr.end(), first, result, op)); 164 } 165 166 /// Replace replaces every element in the range [first, last) equal to 167 /// old_value with new_value. That is: for every iterator i, 168 /// if *i == old_value then it performs the assignment *i = new_value. 169 /// \ingroup MutatingAlgorithms 170 /// 171 template <typename Container, typename T> 172 inline void replace (Container& ctr, const T& old_value, const T& new_value) 173 { 174 replace (ctr.begin(), ctr.end(), old_value, new_value); 175 } 176 177 /// Replace_if replaces every element in the range [first, last) for which 178 /// pred returns true with new_value. That is: for every iterator i, if 179 /// pred(*i) is true then it performs the assignment *i = new_value. 180 /// \ingroup MutatingAlgorithms 181 /// 182 template <typename Container, typename Predicate, typename T> 183 inline void replace_if (Container& ctr, Predicate pred, const T& new_value) 184 { 185 replace_if (ctr.begin(), ctr.end(), pred, new_value); 186 } 187 188 /// Replace_copy copies elements from the range [first, last) to the range 189 /// [result, result + (last-first)), except that any element equal to old_value 190 /// is not copied; new_value is copied instead. More precisely, for every 191 /// integer n such that 0 <= n < last-first, replace_copy performs the 192 /// assignment *(result+n) = new_value if *(first+n) == old_value, and 193 /// *(result+n) = *(first+n) otherwise. 194 /// \ingroup MutatingAlgorithms 195 /// 196 template <typename Container, typename OutputIterator, typename T> 197 inline OutputIterator replace_copy (const Container& ctr, OutputIterator result, const T& old_value, const T& new_value) 198 { 199 return (replace_copy (ctr.begin(), ctr.end(), result, old_value, new_value)); 200 } 201 202 /// Replace_copy_if copies elements from the range [first, last) to the range 203 /// [result, result + (last-first)), except that any element for which pred is 204 /// true is not copied; new_value is copied instead. More precisely, for every 205 /// integer n such that 0 <= n < last-first, replace_copy_if performs the 206 /// assignment *(result+n) = new_value if pred(*(first+n)), 207 /// and *(result+n) = *(first+n) otherwise. 208 /// \ingroup MutatingAlgorithms 209 /// 210 template <typename Container, typename OutputIterator, typename Predicate, typename T> 211 inline OutputIterator replace_copy_if (const Container& ctr, OutputIterator result, Predicate pred, const T& new_value) 212 { 213 return (replace_copy_if (ctr.begin(), ctr.end(), result, pred, new_value)); 214 } 215 216 /// Fill assigns the value value to every element in the range [first, last). 217 /// That is, for every iterator i in [first, last), 218 /// it performs the assignment *i = value. 219 /// \ingroup GeneratorAlgorithms 220 /// 221 template <typename Container, typename T> 222 inline void fill (Container& ctr, const T& value) 223 { 224 fill (ctr.begin(), ctr.end(), value); 225 } 226 227 /// Generate assigns the result of invoking gen, a function object that 228 /// takes no arguments, to each element in the range [first, last). 229 /// \ingroup GeneratorAlgorithms 230 /// 231 template <typename Container, typename Generator> 232 inline void generate (Container& ctr, Generator gen) 233 { 234 generate (ctr.begin(), ctr.end(), gen); 235 } 236 237 /// Randomly permute the elements of the container. 238 /// \ingroup GeneratorAlgorithms 239 /// 240 template <typename Container> 241 inline void random_shuffle (Container& ctr) 242 { 243 random_shuffle (ctr.begin(), ctr.end()); 244 } 245 246 /// Remove_copy copies elements that are not equal to value from the range 247 /// [first, last) to a range beginning at result. The return value is the 248 /// end of the resulting range. This operation is stable, meaning that the 249 /// relative order of the elements that are copied is the same as in the 250 /// range [first, last). 251 /// \ingroup MutatingAlgorithms 252 /// 253 template <typename Container, typename OutputIterator, typename T> 254 inline OutputIterator remove_copy (const Container& ctr, OutputIterator result, const T& value) 255 { 256 return (remove_copy (ctr.begin(), ctr.end(), result, value)); 257 } 258 259 /// Remove_copy_if copies elements from the range [first, last) to a range 260 /// beginning at result, except that elements for which pred is true are not 261 /// copied. The return value is the end of the resulting range. This operation 262 /// is stable, meaning that the relative order of the elements that are copied 263 /// is the same as in the range [first, last). 264 /// \ingroup MutatingAlgorithms 265 /// 266 template <typename Container, typename OutputIterator, typename Predicate> 267 inline OutputIterator remove_copy_if (const Container& ctr, OutputIterator result, Predicate pred) 268 { 269 return (remove_copy_if (ctr.begin(), ctr.end(), result, pred)); 270 } 271 272 /// Remove removes from the range [first, last) all elements that are equal to 273 /// value. That is, remove returns an iterator new_last such that the range 274 /// [first, new_last) contains no elements equal to value. Remove is stable, 275 /// meaning that the relative order of elements that are not equal to value is 276 /// unchanged. 277 /// \ingroup MutatingAlgorithms 278 /// 279 template <typename Container, typename T> 280 inline void remove (Container& ctr, const T& value) 281 { 282 ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), value), ctr.end()); 283 } 284 285 /// Remove removes from the range [first, last) all elements that have an iterator 286 /// in range [rfirst, rlast). The range is assumed to be sorted. That is, remove 287 /// returns an iterator new_last such that the range [first, new_last) contains 288 /// no elements whose iterators are in [rfirst, rlast). Remove is stable, 289 /// meaning that the relative order of elements that are not equal to value is 290 /// unchanged. This version of the algorithm is a uSTL extension. 291 /// \ingroup MutatingAlgorithms 292 /// 293 template <typename Container, typename ForwardIterator> 294 inline void remove (Container& ctr, ForwardIterator rfirst, ForwardIterator rlast) 295 { 296 ctr.erase (remove_copy (ctr.begin(), ctr.end(), ctr.begin(), rfirst, rlast), ctr.end()); 297 } 298 299 /// Remove_if removes from the range [first, last) every element x such that 300 /// pred(x) is true. That is, remove_if returns an iterator new_last such that 301 /// the range [first, new_last) contains no elements for which pred is true. 302 /// The iterators in the range [new_last, last) are all still dereferenceable, 303 /// but the elements that they point to are unspecified. Remove_if is stable, 304 /// meaning that the relative order of elements that are not removed is 305 /// unchanged. 306 /// \ingroup MutatingAlgorithms 307 /// 308 template <typename Container, typename Predicate> 309 inline void remove_if (Container& ctr, Predicate pred) 310 { 311 ctr.erase (remove_copy_if (ctr.begin(), ctr.end(), ctr.begin(), pred), ctr.end()); 312 } 313 314 /// Unique_copy copies elements from the range [first, last) to a range 315 /// beginning with result, except that in a consecutive group of duplicate 316 /// elements only the first one is copied. The return value is the end of 317 /// the range to which the elements are copied. This behavior is similar 318 /// to the Unix filter uniq. 319 /// \ingroup MutatingAlgorithms 320 /// 321 template <typename Container, typename OutputIterator> 322 inline OutputIterator unique_copy (const Container& ctr, OutputIterator result) 323 { 324 return (unique_copy (ctr.begin(), ctr.end(), result)); 325 } 326 327 /// Every time a consecutive group of duplicate elements appears in the range 328 /// [first, last), the algorithm unique removes all but the first element. 329 /// That is, unique returns an iterator new_last such that the range [first, 330 /// new_last) contains no two consecutive elements that are duplicates. 331 /// The iterators in the range [new_last, last) are all still dereferenceable, 332 /// but the elements that they point to are unspecified. Unique is stable, 333 /// meaning that the relative order of elements that are not removed is 334 /// unchanged. 335 /// \ingroup MutatingAlgorithms 336 /// 337 template <typename Container> 338 inline void unique (Container& ctr) 339 { 340 ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin()), ctr.end()); 341 } 342 343 /// Every time a consecutive group of duplicate elements appears in the range 344 /// [first, last), the algorithm unique removes all but the first element. 345 /// That is, unique returns an iterator new_last such that the range [first, 346 /// new_last) contains no two consecutive elements that are duplicates. 347 /// The iterators in the range [new_last, last) are all still dereferenceable, 348 /// but the elements that they point to are unspecified. Unique is stable, 349 /// meaning that the relative order of elements that are not removed is 350 /// unchanged. 351 /// \ingroup MutatingAlgorithms 352 /// 353 template <typename Container, typename BinaryPredicate> 354 inline void unique (Container& ctr, BinaryPredicate binary_pred) 355 { 356 ctr.erase (unique_copy (ctr.begin(), ctr.end(), ctr.begin(), binary_pred), ctr.end()); 357 } 358 359 /// Reverse reverses a range. 360 /// That is: for every i such that 0 <= i <= (last - first) / 2), 361 /// it exchanges *(first + i) and *(last - (i + 1)). 362 /// \ingroup MutatingAlgorithms 363 /// 364 template <typename Container> 365 inline void reverse (Container& ctr) 366 { 367 reverse (ctr.begin(), ctr.end()); 368 } 369 370 /// Exchanges ranges [first, middle) and [middle, last) 371 /// \ingroup MutatingAlgorithms 372 /// 373 template <typename Container> 374 inline void rotate (Container& ctr, off_t offset) 375 { 376 assert (size_t(offset > 0 ? offset : -offset) < ctr.size()); 377 if (offset > 0) 378 rotate (ctr.begin(), ctr.end() - offset, ctr.end()); 379 else 380 rotate (ctr.begin(), ctr.begin() - offset, ctr.end()); 381 } 382 383 /// Returns the furthermost iterator i in [first, last) such that, 384 /// for every iterator j in [first, i), *j < value 385 /// Assumes the range is sorted. 386 /// \ingroup SearchingAlgorithms 387 /// 388 template <typename Container, typename LessThanComparable> 389 inline typename Container::const_iterator lower_bound (const Container& ctr, const LessThanComparable& value) 390 { 391 return (lower_bound (ctr.begin(), ctr.end(), value)); 392 } 393 template <typename Container, typename LessThanComparable> 394 inline typename Container::iterator lower_bound (Container& ctr, const LessThanComparable& value) 395 { 396 return (lower_bound (ctr.begin(), ctr.end(), value)); 397 } 398 399 /// Returns the furthermost iterator i in [first,last) such that for 400 /// every iterator j in [first,i), value < *j is false. 401 /// \ingroup SearchingAlgorithms 402 /// 403 template <typename Container, typename LessThanComparable> 404 inline typename Container::const_iterator upper_bound (const Container& ctr, const LessThanComparable& value) 405 { 406 return (upper_bound (ctr.begin(), ctr.end(), value)); 407 } 408 template <typename Container, typename LessThanComparable> 409 inline typename Container::iterator upper_bound (Container& ctr, const LessThanComparable& value) 410 { 411 return (upper_bound (ctr.begin(), ctr.end(), value)); 412 } 413 414 /// Performs a binary search for \p value. 415 /// Assumes the range is sorted. 416 /// \ingroup SearchingAlgorithms 417 /// 418 template <typename Container> 419 inline typename Container::const_iterator binary_search (const Container& ctr, const typename Container::value_type& value) 420 { 421 return (binary_search (ctr.begin(), ctr.end(), value)); 422 } 423 template <typename Container> 424 inline typename Container::iterator binary_search (Container& ctr, const typename Container::value_type& value) 425 { 426 return (binary_search (ctr.begin(), ctr.end(), value)); 427 } 428 429 /// Returns pair<lower_bound,upper_bound> 430 /// \ingroup SearchingAlgorithms 431 /// 432 template <typename Container, typename LessThanComparable> 433 inline pair<typename Container::const_iterator,typename Container::const_iterator> equal_range (const Container& ctr, const LessThanComparable& value) 434 { 435 return (equal_range (ctr.begin(), ctr.end(), value)); 436 } 437 template <typename Container, typename LessThanComparable> 438 inline pair<typename Container::iterator,typename Container::iterator> equal_range (Container& ctr, const LessThanComparable& value) 439 { 440 return (equal_range (ctr.begin(), ctr.end(), value)); 441 } 442 443 /// Sorts the container 444 /// \ingroup SortingAlgorithms 445 /// 446 template <typename Container> 447 inline void sort (Container& ctr) 448 { 449 sort (ctr.begin(), ctr.end()); 450 } 451 452 /// Sorts the container 453 /// \ingroup SortingAlgorithms 454 /// 455 template <typename Container, typename Compare> 456 inline void sort (Container& ctr, Compare comp) 457 { 458 sort (ctr.begin(), ctr.end(), comp); 459 } 460 461 /// Sorts the container 462 /// \ingroup SortingAlgorithms 463 /// 464 template <typename Container> 465 inline void stable_sort (Container& ctr) 466 { 467 stable_sort (ctr.begin(), ctr.end()); 468 } 469 470 /// Sorts the container 471 /// \ingroup SortingAlgorithms 472 /// 473 template <typename Container, typename Compare> 474 inline void stable_sort (Container& ctr, Compare comp) 475 { 476 stable_sort (ctr.begin(), ctr.end(), comp); 477 } 478 479 } // namespace ustl 480 481 #endif 482 483
