19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// This file is part of the ustl library, an STL implementation. 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// This file is free software, distributed under the MIT License. 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// ualgo.h 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// Implementation of STL algorithms. 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// The function prototypes are copied 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// exactly from the SGI version of STL documentation along with comments about 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// their use. The code is NOT the same, though the functionality usually is. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project// 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#ifndef UALGO_H_711AB4214D417A51166694D47A662D6E 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define UALGO_H_711AB4214D417A51166694D47A662D6E 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "upair.h" 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "ualgobase.h" 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "ufunction.h" 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "upredalgo.h" 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "umemory.h" 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include <stdlib.h> // for rand() 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectnamespace ustl { 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Swaps corresponding elements of [first, last) and [result,) 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SwapAlgorithms 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator1, typename ForwardIterator2> 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator2 swap_ranges (ForwardIterator1 first, ForwardIterator2 last, ForwardIterator2 result) 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first, ++result) 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iter_swap (first, result); 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the first iterator i in the range [first, last) such that 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// *i == value. Returns last if no such iterator exists. 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename EqualityComparable> 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline InputIterator find (InputIterator first, InputIterator last, const EqualityComparable& value) 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (first != last && !(*first == value)) 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ first; 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the first iterator such that *i == *(i + 1) 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last) 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (first != last) 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (ForwardIterator prev = first; ++first != last; ++ prev) 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (*prev == *first) 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (prev); 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (last); 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the pointer to the first pair of unequal elements. 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator> 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpair<InputIterator,InputIterator> 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectmismatch (InputIterator first1, InputIterator last1, InputIterator first2) 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (first1 != last1 && *first1 == *first2) 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ first1, ++ first2; 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (make_pair (first1, first2)); 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Returns true if two ranges are equal. 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// This is an extension, present in uSTL and SGI STL. 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator> 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool equal (InputIterator first1, InputIterator last1, InputIterator first2) 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (mismatch (first1, last1, first2).first == last1); 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Count finds the number of elements in [first, last) that are equal 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// to value. More precisely, the first version of count returns the 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// number of iterators i in [first, last) such that *i == value. 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename EqualityComparable> 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline size_t count (InputIterator first, InputIterator last, const EqualityComparable& value) 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project size_t total = 0; 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first) 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (*first == value) 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ total; 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (total); 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The first version of transform performs the operation op(*i) for each 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// iterator i in the range [first, last), and assigns the result of that 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// operation to *o, where o is the corresponding output iterator. That is, 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// for each n such that 0 <= n < last - first, it performs the assignment 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// *(result + n) = op(*(first + n)). 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The return value is result + (last - first). 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename OutputIterator, typename UnaryFunction> 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++result, ++first) 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = op (*first); 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The second version of transform is very similar, except that it uses a 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Binary Function instead of a Unary Function: it performs the operation 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// the result to *o, where i2 is the corresponding iterator in the second 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// input range and where o is the corresponding output iterator. That is, 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// for each n such that 0 <= n < last1 - first1, it performs the assignment 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// *(result + n) = op(*(first1 + n), *(first2 + n). 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The return value is result + (last1 - first1). 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryFunction> 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op) 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first1 != last1; ++result, ++first1, ++first2) 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = op (*first1, *first2); 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Replace replaces every element in the range [first, last) equal to 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// old_value with new_value. That is: for every iterator i, 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// if *i == old_value then it performs the assignment *i = new_value. 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename T> 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first) 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (*first == old_value) 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *first = new_value; 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Replace_copy copies elements from the range [first, last) to the range 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// [result, result + (last-first)), except that any element equal to old_value 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// is not copied; new_value is copied instead. More precisely, for every 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// integer n such that 0 <= n < last-first, replace_copy performs the 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// assignment *(result+n) = new_value if *(first+n) == old_value, and 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// *(result+n) = *(first+n) otherwise. 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename OutputIterator, typename T> 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value) 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++result, ++first) 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = (*first == old_value) ? new_value : *first; 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Generate assigns the result of invoking gen, a function object that 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// takes no arguments, to each element in the range [first, last). 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup GeneratorAlgorithms 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename Generator> 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void generate (ForwardIterator first, ForwardIterator last, Generator gen) 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first) 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *first = gen(); 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Generate_n assigns the result of invoking gen, a function object that 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// takes no arguments, to each element in the range [first, first+n). 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The return value is first + n. 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup GeneratorAlgorithms 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename OutputIterator, typename Generator> 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator generate_n (OutputIterator first, size_t n, Generator gen) 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (uoff_t i = 0; i != n; ++i, ++first) 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *first = gen(); 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Reverse reverses a range. 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// That is: for every i such that 0 <= i <= (last - first) / 2), 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// it exchanges *(first + i) and *(last - (i + 1)). 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename BidirectionalIterator> 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void reverse (BidirectionalIterator first, BidirectionalIterator last) 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; distance (first, --last) > 0; ++first) 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iter_swap (first, last); 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Reverses [first,last) and writes it to \p output. 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename BidirectionalIterator, typename OutputIterator> 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result) 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++result) 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *--last; 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Exchanges ranges [first, middle) and [middle, last) 2169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last) 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (first == middle || middle == last) 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse (first, middle); 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse (middle, last); 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (;first != middle && middle != last; ++first) 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iter_swap (first, --last); 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse (first, (first == middle ? last : middle)); 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Specialization for pointers, which can be treated identically. 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename T> 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline T* rotate (T* first, T* middle, T* last) 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rotate_fast (first, middle, last); 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Exchanges ranges [first, middle) and [middle, last) into \p result. 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename OutputIterator> 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result) 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (copy (first, middle, copy (middle, last, result))); 2479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Combines two sorted ranges. 2509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 2519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator> 2539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectOutputIterator merge (InputIterator1 first1, InputIterator1 last1, 2549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project InputIterator2 first2, InputIterator2 last2, OutputIterator result) 2559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first1 != last1 && first2 != last2; ++result) { 2579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (*first1 < *first2) 2589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *first1++; 2599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *first2++; 2619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (first1 < last1) 2639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (copy (first1, last1, result)); 2649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (copy (first2, last2, result)); 2669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Combines two sorted ranges from the same container. 2699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 2709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator> 2729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid inplace_merge (InputIterator first, InputIterator middle, InputIterator last) 2739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; middle != last; ++first) { 2759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (*first < *middle) 2769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ first; 2779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse (first, middle); 2789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project reverse (first, ++middle); 2799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 2819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Remove_copy copies elements that are not equal to value from the range 2839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// [first, last) to a range beginning at result. The return value is the 2849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// end of the resulting range. This operation is stable, meaning that the 2859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// relative order of the elements that are copied is the same as in the 2869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// range [first, last). 2879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 2889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 2899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename OutputIterator, typename T> 2909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectOutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& value) 2919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 2929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first) { 2939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!(*first == value)) { 2949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *first; 2959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ result; 2969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 2999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Remove_copy copies elements pointed to by iterators in [rfirst, rlast) 3029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// from the range [first, last) to a range beginning at result. The return 3039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// value is the end of the resulting range. This operation is stable, meaning 3049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// that the relative order of the elements that are copied is the same as in the 3059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// range [first, last). Range [rfirst, rlast) is assumed to be sorted. 3069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// This algorithm is a uSTL extension. 3079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 3089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename OutputIterator, typename RInputIterator> 3109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectOutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, RInputIterator rfirst, RInputIterator rlast) 3119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++first) { 3139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (rfirst != rlast && *rfirst < first) 3149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ rfirst; 3159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (rfirst == rlast || first != *rfirst) { 3169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *first; 3179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ result; 3189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 3219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Remove removes from the range [first, last) all elements that are equal to 3249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// value. That is, remove returns an iterator new_last such that the range 3259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// [first, new_last) contains no elements equal to value. [1] The iterators 3269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// in the range [new_last, last) are all still dereferenceable, but the 3279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// elements that they point to are unspecified. Remove is stable, meaning 3289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// that the relative order of elements that are not equal to value is 3299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// unchanged. 3309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 3319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename T> 3339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& value) 3349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (remove_copy (first, last, first, value)); 3369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Unique_copy copies elements from the range [first, last) to a range 3399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// beginning with result, except that in a consecutive group of duplicate 3409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// elements only the first one is copied. The return value is the end of 3419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// the range to which the elements are copied. This behavior is similar 3429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// to the Unix filter uniq. 3439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 3449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename OutputIterator> 3469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectOutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result) 3479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (first != last) { 3499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *result = *first; 3509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (++first != last) 3519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (!(*first == *result)) 3529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *++result = *first; 3539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ result; 3549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (result); 3569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Every time a consecutive group of duplicate elements appears in the range 3599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// [first, last), the algorithm unique removes all but the first element. 3609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// That is, unique returns an iterator new_last such that the range [first, 3619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// new_last) contains no two consecutive elements that are duplicates. 3629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// The iterators in the range [new_last, last) are all still dereferenceable, 3639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// but the elements that they point to are unspecified. Unique is stable, 3649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// meaning that the relative order of elements that are not removed is 3659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// unchanged. 3669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup MutatingAlgorithms 3679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 3699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator unique (ForwardIterator first, ForwardIterator last) 3709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (unique_copy (first, last, first)); 3729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the furthermost iterator i in [first, last) such that, 3759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// for every iterator j in [first, i), *j < value 3769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Assumes the range is sorted. 3779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 3789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename LessThanComparable> 3809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 3819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ForwardIterator mid; 3839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (first != last) { 3849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mid = advance (first, distance (first,last) / 2); 3859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (*mid < value) 3869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project first = mid + 1; 3879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 3889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project last = mid; 3899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 3909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (first); 3919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 3929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 3939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Performs a binary search inside the sorted range. 3949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 3959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 3969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename LessThanComparable> 3979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator binary_search (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 3989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 3999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ForwardIterator found = lower_bound (first, last, value); 4009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ((found == last || value < *found) ? last : found); 4019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns the furthermost iterator i in [first,last) such that for 4049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// every iterator j in [first,i), value < *j is false. 4059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 4069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename LessThanComparable> 4089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source ProjectForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 4099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ForwardIterator mid; 4119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (first != last) { 4129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mid = advance (first, distance (first,last) / 2); 4139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (value < *mid) 4149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project last = mid; 4159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 4169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project first = mid + 1; 4179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (last); 4199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns pair<lower_bound,upper_bound> 4229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 4239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator, typename LessThanComparable> 4259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 4269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project pair<ForwardIterator,ForwardIterator> rv; 4289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rv.second = rv.first = lower_bound (first, last, value); 4299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (rv.second != last && !(value < *(rv.second))) 4309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ++ rv.second; 4319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (rv); 4329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Randomly permute the elements of the container. 4359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup GeneratorAlgorithms 4369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator> 4389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid random_shuffle (RandomAccessIterator first, RandomAccessIterator last) 4399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (; first != last; ++ first) 4419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project iter_swap (first, first + (rand() % distance (first, last))); 4429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Generic compare function adaptor to pass to qsort 4459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup FunctorObjects 4469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ConstPointer, typename Compare> 4479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectint qsort_adapter (const void* p1, const void* p2) 4489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ConstPointer i1 = reinterpret_cast<ConstPointer>(p1); 4509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project ConstPointer i2 = reinterpret_cast<ConstPointer>(p2); 4519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Compare comp; 4529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (comp (*i1, *i2) ? -1 : (comp (*i2, *i1) ? 1 : 0)); 4539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Sorts the container 4569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 4579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 4589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator, typename Compare> 4609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid sort (RandomAccessIterator first, RandomAccessIterator last, Compare) 4619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 4639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<RandomAccessIterator>::const_pointer const_pointer; 4649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project qsort (first, distance (first, last), sizeof(value_type), 4659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project &qsort_adapter<const_pointer, Compare>); 4669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Sorts the container 4699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 4709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator> 4729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void sort (RandomAccessIterator first, RandomAccessIterator last) 4739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 4759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project sort (first, last, less<value_type>()); 4769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Sorts the container preserving order of equal elements. 4799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 4809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup PredicateAlgorithms 4819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator, typename Compare> 4839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp) 4849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (RandomAccessIterator j, i = first; ++i < last;) { // Insertion sort 4869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (j = i; j-- > first && !comp(*j, *i);); 4879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project rotate (++j, i, i + 1); 4889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 4899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 4909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Sorts the container 4929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 4939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 4949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator> 4959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void stable_sort (RandomAccessIterator first, RandomAccessIterator last) 4969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 4979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 4989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project stable_sort (first, last, less<value_type>()); 4999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Searches for the first subsequence [first2,last2) in [first1,last1) 5029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 5039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator1, typename ForwardIterator2> 5049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) 5059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<ForwardIterator1>::value_type value_type; 5079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (search (first1, last1, first2, last2, equal_to<value_type>())); 5089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Searches for the last subsequence [first2,last2) in [first1,last1) 5119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 5129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator1, typename ForwardIterator2> 5139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) 5149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<ForwardIterator1>::value_type value_type; 5169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (find_end (first1, last1, first2, last2, equal_to<value_type>())); 5179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Searches for the first occurence of \p count \p values in [first, last) 5209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 5219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename Iterator, typename T> 5229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline Iterator search_n (Iterator first, Iterator last, size_t count, const T& value) 5239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<Iterator>::value_type value_type; 5259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (search_n (first, last, count, value, equal_to<value_type>())); 5269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2) 5299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 5309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename ForwardIterator> 5319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2) 5329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator>::value_type value_type; 5349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (find_first_of (first1, last1, first2, last2, equal_to<value_type>())); 5359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Returns true if [first2,last2) is a subset of [first1,last1) 5389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup ConditionAlgorithms 5399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SetAlgorithms 5409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2> 5419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) 5429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 5449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (includes (first1, last1, first2, last2, less<value_type>())); 5459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Merges [first1,last1) with [first2,last2) 5489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 5499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Result will contain every element that is in either set. If duplicate 5509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// elements are present, max(n,m) is placed in the result. 5519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 5529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SetAlgorithms 5539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator> 5549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 5559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 5579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (set_union (first1, last1, first2, last2, result, less<value_type>())); 5589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Creates a set containing elements shared by the given ranges. 5619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SetAlgorithms 5629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator> 5639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 5649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 5669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (set_intersection (first1, last1, first2, last2, result, less<value_type>())); 5679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Removes from [first1,last1) elements present in [first2,last2) 5709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SetAlgorithms 5719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator> 5729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 5739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 5759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (set_difference (first1, last1, first2, last2, result, less<value_type>())); 5769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Performs union of sets A-B and B-A. 5799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SetAlgorithms 5809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2, typename OutputIterator> 5819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 5829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 5849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (set_symmetric_difference (first1, last1, first2, last2, result, less<value_type>())); 5859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Returns true if the given range is sorted. 5889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup ConditionAlgorithms 5899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 5909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool is_sorted (ForwardIterator first, ForwardIterator last) 5919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 5929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<ForwardIterator>::value_type value_type; 5939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (is_sorted (first, last, less<value_type>())); 5949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 5959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Compares two given containers like strcmp compares strings. 5979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup ConditionAlgorithms 5989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator1, typename InputIterator2> 5999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) 6009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator1>::value_type value_type; 6029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (lexicographical_compare (first1, last1, first2, last2, less<value_type>())); 6039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Creates the next lexicographical permutation of [first,last). 6069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns false if no further permutations can be created. 6079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup GeneratorAlgorithms 6089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename BidirectionalIterator> 6099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool next_permutation (BidirectionalIterator first, BidirectionalIterator last) 6109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; 6129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (next_permutation (first, last, less<value_type>())); 6139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Creates the previous lexicographical permutation of [first,last). 6169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Returns false if no further permutations can be created. 6179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup GeneratorAlgorithms 6189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename BidirectionalIterator> 6199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last) 6209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; 6229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (prev_permutation (first, last, less<value_type>())); 6239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Returns iterator to the max element in [first,last) 6269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 6279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 6289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator max_element (ForwardIterator first, ForwardIterator last) 6299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<ForwardIterator>::value_type value_type; 6319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (max_element (first, last, less<value_type>())); 6329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Returns iterator to the min element in [first,last) 6359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 6369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename ForwardIterator> 6379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline ForwardIterator min_element (ForwardIterator first, ForwardIterator last) 6389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<ForwardIterator>::value_type value_type; 6409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (min_element (first, last, less<value_type>())); 6419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Makes [first,middle) a part of the sorted array. 6449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// Contents of [middle,last) is undefined. This implementation just calls stable_sort. 6459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 6469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator> 6479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) 6489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 6509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project partial_sort (first, middle, last, less<value_type>()); 6519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Puts \p nth element into its sorted position. 6549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// In this implementation, the entire array is sorted. I can't think of any 6559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// use for it where the time gained would be useful. 6569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 6579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SearchingAlgorithms 6589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// 6599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename RandomAccessIterator> 6609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) 6619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project partial_sort (first, nth, last); 6639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \brief Like partial_sort, but outputs to [result_first,result_last) 6669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/// \ingroup SortingAlgorithms 6679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projecttemplate <typename InputIterator, typename RandomAccessIterator> 6689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectinline RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last) 6699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 6709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project typedef typename iterator_traits<InputIterator>::value_type value_type; 6719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return (partial_sort_copy (first, last, result_first, result_last, less<value_type>())); 6729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 6739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} // namespace ustl 6759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 6769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#endif 6779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 678