1// This file is part of the ustl library, an STL implementation. 2// 3// Copyright (C) 2005 by Mike Sharov <msharov@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 20namespace 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/// 30template <typename Container, typename OutputIterator> 31inline 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/// 40template <typename Container, typename OutputIterator, typename Predicate> 41inline 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/// 52template <typename Container, typename UnaryFunction> 53inline 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/// 64template <typename Container, typename UnaryFunction> 65inline 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/// 74template <typename Container, typename EqualityComparable> 75inline typename Container::const_iterator find (const Container& ctr, const EqualityComparable& value) 76{ 77 return (find (ctr.begin(), ctr.end(), value)); 78} 79template <typename Container, typename EqualityComparable> 80inline 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/// 89template <typename Container, typename Predicate> 90inline typename Container::const_iterator find_if (const Container& ctr, Predicate pred) 91{ 92 return (find_if (ctr.begin(), ctr.end(), pred)); 93} 94template <typename Container, typename Predicate> 95inline 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/// 105template <typename Container, typename EqualityComparable> 106inline 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/// 116template <typename Container, typename Predicate> 117inline 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/// 130template <typename Container, typename UnaryFunction> 131inline 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/// 144template <typename Container, typename OutputIterator, typename UnaryFunction> 145inline 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/// 160template <typename Container, typename InputIterator, typename OutputIterator, typename BinaryFunction> 161inline 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/// 171template <typename Container, typename T> 172inline 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/// 182template <typename Container, typename Predicate, typename T> 183inline 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/// 196template <typename Container, typename OutputIterator, typename T> 197inline 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/// 210template <typename Container, typename OutputIterator, typename Predicate, typename T> 211inline 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/// 221template <typename Container, typename T> 222inline 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/// 231template <typename Container, typename Generator> 232inline 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/// 240template <typename Container> 241inline 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/// 253template <typename Container, typename OutputIterator, typename T> 254inline 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/// 266template <typename Container, typename OutputIterator, typename Predicate> 267inline 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/// 279template <typename Container, typename T> 280inline 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/// 293template <typename Container, typename ForwardIterator> 294inline 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/// 308template <typename Container, typename Predicate> 309inline 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/// 321template <typename Container, typename OutputIterator> 322inline 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/// 337template <typename Container> 338inline 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/// 353template <typename Container, typename BinaryPredicate> 354inline 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/// 364template <typename Container> 365inline 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/// 373template <typename Container> 374inline 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/// 388template <typename Container, typename LessThanComparable> 389inline typename Container::const_iterator lower_bound (const Container& ctr, const LessThanComparable& value) 390{ 391 return (lower_bound (ctr.begin(), ctr.end(), value)); 392} 393template <typename Container, typename LessThanComparable> 394inline 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/// 403template <typename Container, typename LessThanComparable> 404inline typename Container::const_iterator upper_bound (const Container& ctr, const LessThanComparable& value) 405{ 406 return (upper_bound (ctr.begin(), ctr.end(), value)); 407} 408template <typename Container, typename LessThanComparable> 409inline 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/// 418template <typename Container> 419inline 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} 423template <typename Container> 424inline 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/// 432template <typename Container, typename LessThanComparable> 433inline 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} 437template <typename Container, typename LessThanComparable> 438inline 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/// 446template <typename Container> 447inline void sort (Container& ctr) 448{ 449 sort (ctr.begin(), ctr.end()); 450} 451 452/// Sorts the container 453/// \ingroup SortingAlgorithms 454/// 455template <typename Container, typename Compare> 456inline void sort (Container& ctr, Compare comp) 457{ 458 sort (ctr.begin(), ctr.end(), comp); 459} 460 461/// Sorts the container 462/// \ingroup SortingAlgorithms 463/// 464template <typename Container> 465inline void stable_sort (Container& ctr) 466{ 467 stable_sort (ctr.begin(), ctr.end()); 468} 469 470/// Sorts the container 471/// \ingroup SortingAlgorithms 472/// 473template <typename Container, typename Compare> 474inline 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