Sierra Toolkit Version of the Day
algorithm_eastl.h
00001 /*
00002 Copyright (C) 2005,2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/algorithm.h
00031 //
00032 // Written and maintained by Paul Pedriana - 2005.
00034 
00036 // This file implements some of the primary algorithms from the C++ STL
00037 // algorithm library. These versions are just like that STL versions and so
00038 // are redundant. They are provided solely for the purpose of projects that
00039 // either cannot use standard C++ STL or want algorithms that have guaranteed
00040 // identical behaviour across platforms.
00042 
00043 
00045 // Definitions
00046 //
00047 // You will notice that we are very particular about the templated typenames
00048 // we use here. You will notice that we follow the C++ standard closely in
00049 // these respects. Each of these typenames have a specific meaning;
00050 // this is why we don't just label templated arguments with just letters
00051 // such as T, U, V, A, B. Here we provide a quick reference for the typenames
00052 // we use. See the C++ standard, section 25-8 for more details.
00053 //    --------------------------------------------------------------
00054 //    typename                     Meaning
00055 //    --------------------------------------------------------------
00056 //    T                            The value type.
00057 //    Compare                      A function which takes two arguments and returns the lesser of the two.
00058 //    Predicate                    A function which takes one argument returns true if the argument meets some criteria.
00059 //    BinaryPredicate              A function which takes two arguments and returns true if some criteria is met (e.g. they are equal).
00060 //    StrickWeakOrdering           A BinaryPredicate that compares two objects, returning true if the first precedes the second. Like Compare but has additional requirements. Used for sorting routines.
00061 //    Function                     A function which takes one argument and applies some operation to the target.
00062 //    Size                         A count or size.
00063 //    Generator                    A function which takes no arguments and returns a value (which will usually be assigned to an object).
00064 //    UnaryOperation               A function which takes one argument and returns a value (which will usually be assigned to second object).
00065 //    BinaryOperation              A function which takes two arguments and returns a value (which will usually be assigned to a third object).
00066 //    InputIterator                An input iterator (iterator you read from) which allows reading each element only once and only in a forward direction.
00067 //    ForwardIterator              An input iterator which is like InputIterator except it can be reset back to the beginning.
00068 //    BidirectionalIterator        An input iterator which is like ForwardIterator except it can be read in a backward direction as well.
00069 //    RandomAccessIterator         An input iterator which can be addressed like an array. It is a superset of all other input iterators.
00070 //    OutputIterator               An output iterator (iterator you write to) which allows writing each element only once in only in a forward direction.
00071 //
00072 // Note that with iterators that a function which takes an InputIterator will
00073 // also work with a ForwardIterator, BidirectionalIterator, or RandomAccessIterator.
00074 // The given iterator type is merely the -minimum- supported functionality the
00075 // iterator must support.
00077 
00078 
00080 // Optimizations
00081 //
00082 // There are a number of opportunities for opptimizations that we take here
00083 // in this library. The most obvious kinds are those that subsitute memcpy
00084 // in the place of a conventional loop for data types with which this is
00085 // possible. The algorithms here are optimized to a higher level than currently
00086 // available C++ STL algorithms from vendors. This is especially
00087 // so for game programming on console devices, as we do things such as reduce
00088 // branching relative to other STL algorithm implementations. However, the
00089 // proper implementation of these algorithm optimizations is a fairly tricky
00090 // thing.
00091 //
00092 // The various things we look to take advantage of in order to implement
00093 // optimizations include:
00094 //    - Taking advantage of random access iterators.
00095 //    - Taking advantage of POD (plain old data) data types.
00096 //    - Taking advantage of type_traits in general.
00097 //    - Reducing branching and taking advantage of likely branch predictions.
00098 //    - Taking advantage of issues related to pointer and reference aliasing.
00099 //    - Improving cache coherency during memory accesses.
00100 //    - Making code more likely to be inlinable by the compiler.
00101 //
00103 
00104 #ifndef EASTL_ALGORITHM_H
00105 #define EASTL_ALGORITHM_H
00106 
00107 
00108 #include <stk_util/util/config_eastl.h>
00109 #include <stk_util/util/utility_eastl.h>
00110 #include <stk_util/util/iterator_eastl.h>
00111 #include <stk_util/util/functional_eastl.h>
00112 #include <stk_util/util/generic_iterator_eastl.h>
00113 #include <stk_util/util/type_traits_eastl.h>
00114 
00115 #ifdef _MSC_VER
00116     #pragma warning(push, 0)
00117 #endif
00118 #include <stddef.h>
00119 #ifdef __MWERKS__
00120     #include <../Include/string.h> // Force the compiler to use the std lib header.
00121 #else
00122     #include <string.h> // memcpy, memcmp, memmove
00123 #endif
00124 #ifdef _MSC_VER
00125     #pragma warning(pop)
00126 #endif
00127 
00128 
00130 // min/max workaround
00131 //
00132 // MSVC++ has #defines for min/max which collide with the min/max algorithm
00133 // declarations. The following may still not completely resolve some kinds of
00134 // problems with MSVC++ #defines, though it deals with most cases in production
00135 // game code.
00136 //
00137 #if EASTL_NOMINMAX
00138     #ifdef min
00139         #undef min
00140     #endif
00141     #ifdef max
00142         #undef max
00143     #endif
00144 #endif
00145 
00146 
00147 
00148 
00149 namespace eastl
00150 {
00151     #if EASTL_MINMAX_ENABLED
00152 
00167         template <typename T>
00168         inline const T&
00169         min(const T& a, const T& b)
00170         {
00171             return b < a ? b : a;
00172         }
00173     #endif // EASTL_MINMAX_ENABLED
00174 
00175 
00183     template <typename T>
00184     inline const T&
00185     min_alt(const T& a, const T& b)
00186     {
00187         return b < a ? b : a;
00188     }
00189 
00190     #if EASTL_MINMAX_ENABLED
00191 
00192 
00193 
00194 
00195 
00196 
00197 
00198 
00199 
00200 
00201 
00202 
00203 
00204 
00205 
00206 
00207 
00208 
00209 
00210 
00211 
00212 
00213 
00214 
00215         template <typename T, typename Compare>
00216         inline const T&
00217         min(const T& a, const T& b, Compare compare)
00218         {
00219             return compare(b, a) ? b : a;
00220         }
00221 
00222     #endif // EASTL_MINMAX_ENABLED
00223 
00224 
00232     template <typename T, typename Compare>
00233     inline const T&
00234     min_alt(const T& a, const T& b, Compare compare)
00235     {
00236         return compare(b, a) ? b : a;
00237     }
00238 
00239 
00240     #if EASTL_MINMAX_ENABLED
00241 
00242 
00243 
00244 
00245 
00246 
00247 
00248 
00249 
00250 
00251 
00252 
00253 
00254 
00255         template <typename T>
00256         inline const T&
00257         max(const T& a, const T& b)
00258         {
00259             return a < b ? b : a;
00260         }
00261     #endif // EASTL_MINMAX_ENABLED
00262 
00263 
00269     template <typename T>
00270     inline const T&
00271     max_alt(const T& a, const T& b)
00272     {
00273         return a < b ? b : a;
00274     }
00275 
00276     #if EASTL_MINMAX_ENABLED
00277 
00278 
00279 
00280 
00281 
00282 
00283 
00284 
00285         template <typename T, typename Compare>
00286         inline const T&
00287         max(const T& a, const T& b, Compare compare)
00288         {
00289             return compare(a, b) ? b : a;
00290         }
00291 
00292     #endif
00293 
00294 
00300     template <typename T, typename Compare>
00301     inline const T&
00302     max_alt(const T& a, const T& b, Compare compare)
00303     {
00304         return compare(a, b) ? b : a;
00305     }
00306 
00307 
00308 
00323     template <typename ForwardIterator>
00324     ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
00325     {
00326         if(first != last)
00327         {
00328             ForwardIterator currentMin = first;
00329 
00330             while(++first != last)
00331             {
00332                 if(*first < *currentMin)
00333                     currentMin = first;
00334             }
00335             return currentMin;
00336         }
00337         return first;
00338     }
00339 
00340 
00355     template <typename ForwardIterator, typename Compare>
00356     ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare compare)
00357     {
00358         if(first != last)
00359         {
00360             ForwardIterator currentMin = first;
00361 
00362             while(++first != last)
00363             {
00364                 if(compare(*first, *currentMin))
00365                     currentMin = first;
00366             }
00367             return currentMin;
00368         }
00369         return first;
00370     }
00371 
00372 
00387     template <typename ForwardIterator>
00388     ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
00389     {
00390         if(first != last)
00391         {
00392             ForwardIterator currentMax = first;
00393 
00394             while(++first != last)
00395             {
00396                 if(*currentMax < *first)
00397                     currentMax = first;
00398             }
00399             return currentMax;
00400         }
00401         return first;
00402     }
00403 
00404 
00419     template <typename ForwardIterator, typename Compare>
00420     ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare compare)
00421     {
00422         if(first != last)
00423         {
00424             ForwardIterator currentMax = first;
00425 
00426             while(++first != last)
00427             {
00428                 if(compare(*currentMax, *first))
00429                     currentMax = first;
00430             }
00431             return currentMax;
00432         }
00433         return first;
00434     }
00435 
00436 
00445     template <typename T>
00446     inline const T& median(const T& a, const T& b, const T& c)
00447     {
00448         if(a < b)
00449         {
00450             if(b < c)
00451                 return b;
00452             else if(a < c)
00453                 return c;
00454             else
00455                 return a;
00456         }
00457         else if(a < c)
00458             return a;
00459         else if(b < c)
00460             return c;
00461         return b;
00462     }
00463 
00464 
00473     template <typename T, typename Compare>
00474     inline const T& median(const T& a, const T& b, const T& c, Compare compare)
00475     {
00476         if(compare(a, b))
00477         {
00478             if(compare(b, c))
00479                 return b;
00480             else if(compare(a, c))
00481                 return c;
00482             else
00483                 return a;
00484         }
00485         else if(compare(a, c))
00486             return a;
00487         else if(compare(b, c))
00488             return c;
00489         return b;
00490     }
00491 
00492 
00493 
00505     template <typename T>
00506     inline void swap(T& a, T& b)
00507     {
00508         T temp(a);
00509         a = b;
00510         b = temp;
00511     }
00512 
00513 
00514 
00515     // iter_swap helper functions
00516     //
00517     template <bool bTypesAreEqual>
00518     struct iter_swap_impl
00519     {
00520         template <typename ForwardIterator1, typename ForwardIterator2>
00521         static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
00522         {
00523             typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
00524 
00525             value_type_a temp(*a);
00526             *a = *b;
00527             *b = temp;
00528         }
00529     };
00530 
00531     template <>
00532     struct iter_swap_impl<true>
00533     {
00534         template <typename ForwardIterator1, typename ForwardIterator2>
00535         static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
00536         {
00537             eastl::swap(*a, *b);
00538         }
00539     };
00540 
00551     template <typename ForwardIterator1, typename ForwardIterator2>
00552     inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
00553     {
00554         typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
00555         typedef typename eastl::iterator_traits<ForwardIterator2>::value_type value_type_b;
00556         typedef typename eastl::iterator_traits<ForwardIterator1>::reference  reference_a;
00557         typedef typename eastl::iterator_traits<ForwardIterator2>::reference  reference_b;
00558 
00559         iter_swap_impl<type_and<is_same<value_type_a, value_type_b>::value, is_same<value_type_a&, reference_a>::value, is_same<value_type_b&, reference_b>::value >::value >::iter_swap(a, b);
00560     }
00561 
00562 
00563 
00579     template <typename ForwardIterator1, typename ForwardIterator2>
00580     inline ForwardIterator2
00581     swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
00582     {
00583         for(; first1 != last1; ++first1, ++first2)
00584             iter_swap(first1, first2);
00585         return first2;
00586     }
00587 
00588 
00589 
00598     template <typename ForwardIterator>
00599     inline ForwardIterator
00600     adjacent_find(ForwardIterator first, ForwardIterator last)
00601     {
00602         if(first != last)
00603         {
00604             ForwardIterator i = first;
00605 
00606             for(++i; i != last; ++i)
00607             {
00608                 if(*first == *i)
00609                     return first;
00610                 first = i;
00611             }
00612         }
00613         return last;
00614     }
00615 
00616 
00617 
00626     template <typename ForwardIterator, typename BinaryPredicate>
00627     inline ForwardIterator
00628     adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
00629     {
00630         if(first != last)
00631         {
00632             ForwardIterator i = first;
00633 
00634             for(++i; i != last; ++i)
00635             {
00636                 if(predicate(*first, *i))
00637                     return first;
00638                 first = i;
00639             }
00640         }
00641         return last;
00642     }
00643 
00644 
00645 
00646 
00647     // copy
00648     //
00649     // We implement copy via some helper functions whose purpose is to
00650     // try to use memcpy when possible. We need to use type_traits and
00651     // iterator categories to do this.
00652     //
00653     template <bool bHasTrivialCopy, typename IteratorTag>
00654     struct copy_impl
00655     {
00656         template <typename InputIterator, typename OutputIterator>
00657         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00658         {
00659             for(; first != last; ++result, ++first)
00660                 *result = *first;
00661             return result;
00662         }
00663     };
00664 
00665     template <>
00666     struct copy_impl<true, EASTL_ITC_NS::random_access_iterator_tag> // If we have a trivally copyable random access array, use memcpy
00667     {
00668         template <typename T>
00669         static T* do_copy(const T* first, const T* last, T* result)
00670         {
00671             // We cannot use memcpy because memcpy requires the entire source and dest ranges to be
00672             // non-overlapping, whereas the copy algorithm requires only that 'result' not be within
00673             // the range from first to last.
00674             return (T*)memmove(result, first, (size_t)((uintptr_t)last - (uintptr_t)first)) + (last - first);
00675         }
00676     };
00677 
00678     // copy_chooser
00679     // Calls one of the above copy_impl functions.
00680     template <typename InputIterator, typename OutputIterator>
00681     inline OutputIterator
00682     copy_chooser(InputIterator first, InputIterator last, OutputIterator result)
00683     {
00684         typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
00685         typedef typename eastl::iterator_traits<InputIterator>::value_type        value_type_input;
00686         typedef typename eastl::iterator_traits<OutputIterator>::value_type       value_type_output;
00687 
00688         const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
00689                                               is_pointer<InputIterator>::value,
00690                                               is_pointer<OutputIterator>::value,
00691                                               is_same<value_type_input, value_type_output>::value>::value;
00692 
00693         return eastl::copy_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
00694     }
00695 
00696     // copy_generic_iterator
00697     // Converts a copy call via a generic_iterator to a copy call via the iterator type the
00698     // generic_iterator holds. We do this because generic_iterator's purpose is to hold
00699     // iterators that are simply pointers, and if we want the functions above to be fast,
00700     // we need them to see the pointers and not an iterator that wraps the pointers as
00701     // does generic_iterator. We are forced into using a templated struct with a templated
00702     // do_copy member function because C++ doesn't allow specializations for standalone functions.
00703     template <bool bInputIsGenericIterator, bool bOutputIsGenericIterator>
00704     struct copy_generic_iterator
00705     {
00706         template <typename InputIterator, typename OutputIterator>
00707         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00708         {
00709             return eastl::copy_chooser(first, last, result);
00710         }
00711     };
00712 
00713     template <>
00714     struct copy_generic_iterator<true, false>
00715     {
00716         template <typename InputIterator, typename OutputIterator>
00717         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00718         {
00719             return eastl::copy_chooser(first.base(), last.base(), result); // first.base(), last.base() will resolve to a pointer (e.g. T*).
00720         }
00721     };
00722 
00723     template <>
00724     struct copy_generic_iterator<false, true>
00725     {
00726         template <typename InputIterator, typename OutputIterator>
00727         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00728         {
00729             return OutputIterator(eastl::copy_chooser(first, last, result.base())); // Have to convert to OutputIterator because result.base() is a T*
00730         }
00731     };
00732 
00733     template <>
00734     struct copy_generic_iterator<true, true>
00735     {
00736         template <typename InputIterator, typename OutputIterator>
00737         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00738         {
00739             return OutputIterator(eastl::copy_chooser(first.base(), last.base(), result.base())); // Have to convert to OutputIterator because result.base() is a T*
00740         }
00741     };
00742 
00759     template <typename InputIterator, typename OutputIterator>
00760     inline OutputIterator
00761     copy(InputIterator first, InputIterator last, OutputIterator result)
00762     {
00763         //#ifdef __GNUC__ // GCC has template depth problems and this shortcut may need to be enabled.
00764         //    return eastl::copy_chooser(first, last, result);
00765         //#else
00766             const bool bInputIsGenericIterator  = is_generic_iterator<InputIterator>::value;
00767             const bool bOutputIsGenericIterator = is_generic_iterator<OutputIterator>::value;
00768             return eastl::copy_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
00769         //#endif
00770     }
00771 
00772 
00773 
00774 
00775     // copy_backward
00776     //
00777     // We implement copy_backward via some helper functions whose purpose is
00778     // to try to use memcpy when possible. We need to use type_traits and
00779     // iterator categories to do this.
00780     //
00781     template <bool bHasTrivialCopy, typename IteratorTag>
00782     struct copy_backward_impl
00783     {
00784         template <typename BidirectionalIterator1, typename BidirectionalIterator2>
00785         static BidirectionalIterator2 do_copy(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
00786         {
00787             while(last != first)
00788                 *--result = *--last;
00789             return result;
00790         }
00791     };
00792 
00793     template <>
00794     struct copy_backward_impl<true, EASTL_ITC_NS::random_access_iterator_tag> // If we have a trivally copyable random access array, use memcpy
00795     {
00796         template <typename T>
00797         static T* do_copy(const T* first, const T* last, T* result)
00798         {
00799             return (T*)memmove(result - (last - first), first, (size_t)((uintptr_t)last - (uintptr_t)first));
00800         }
00801     };
00802 
00803     // copy_backward_chooser
00804     // Calls one of the above copy_backward_impl functions.
00805     template <typename InputIterator, typename OutputIterator>
00806     inline OutputIterator
00807     copy_backward_chooser(InputIterator first, InputIterator last, OutputIterator result)
00808     {
00809         typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
00810         typedef typename eastl::iterator_traits<InputIterator>::value_type        value_type_input;
00811         typedef typename eastl::iterator_traits<OutputIterator>::value_type       value_type_output;
00812 
00813         const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
00814                                               is_pointer<InputIterator>::value,
00815                                               is_pointer<OutputIterator>::value,
00816                                               is_same<value_type_input, value_type_output>::value>::value;
00817 
00818         return eastl::copy_backward_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
00819     }
00820 
00821     // copy_backward_generic_iterator
00822     // Converts a copy call via a generic_iterator to a copy call via the iterator type the
00823     // generic_iterator holds. We do this because generic_iterator's purpose is to hold
00824     // iterators that are simply pointers, and if we want the functions above to be fast,
00825     // we need them to see the pointers and not an iterator that wraps the pointers as
00826     // does generic_iterator. We are forced into using a templated struct with a templated
00827     // do_copy member function because C++ doesn't allow specializations for standalone functions.
00828     template <bool bInputIsGenericIterator, bool bOutputIsGenericIterator>
00829     struct copy_backward_generic_iterator
00830     {
00831         template <typename InputIterator, typename OutputIterator>
00832         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00833         {
00834             return eastl::copy_backward_chooser(first, last, result);
00835         }
00836     };
00837 
00838     template <>
00839     struct copy_backward_generic_iterator<true, false>
00840     {
00841         template <typename InputIterator, typename OutputIterator>
00842         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00843         {
00844             return eastl::copy_backward_chooser(first.base(), last.base(), result); // first.base(), last.base() will resolve to a pointer (e.g. T*).
00845         }
00846     };
00847 
00848     template <>
00849     struct copy_backward_generic_iterator<false, true>
00850     {
00851         template <typename InputIterator, typename OutputIterator>
00852         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00853         {
00854             return OutputIterator(eastl::copy_backward_chooser(first, last, result.base())); // Have to convert to OutputIterator because result.base() is a T*
00855         }
00856     };
00857 
00858     template <>
00859     struct copy_backward_generic_iterator<true, true>
00860     {
00861         template <typename InputIterator, typename OutputIterator>
00862         static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
00863         {
00864             return OutputIterator(eastl::copy_backward_chooser(first.base(), last.base(), result.base())); // Have to convert to OutputIterator because result.base() is a T*
00865         }
00866     };
00867 
00882     template <typename BidirectionalIterator1, typename BidirectionalIterator2>
00883     inline BidirectionalIterator2
00884     copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
00885     {
00886         const bool bInputIsGenericIterator  = is_generic_iterator<BidirectionalIterator1>::value;
00887         const bool bOutputIsGenericIterator = is_generic_iterator<BidirectionalIterator2>::value;
00888 
00889         return eastl::copy_backward_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
00890     }
00891 
00892 
00893 
00906     template <typename InputIterator, typename T>
00907     inline typename eastl::iterator_traits<InputIterator>::difference_type
00908     count(InputIterator first, InputIterator last, const T& value)
00909     {
00910         typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
00911 
00912         for(; first != last; ++first)
00913         {
00914             if(*first == value)
00915                 ++result;
00916         }
00917         return result;
00918     }
00919 
00920 
00934     template <typename InputIterator, typename Predicate>
00935     inline typename eastl::iterator_traits<InputIterator>::difference_type
00936     count_if(InputIterator first, InputIterator last, Predicate predicate)
00937     {
00938         typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
00939 
00940         for(; first != last; ++first)
00941         {
00942             if(predicate(*first))
00943                 ++result;
00944         }
00945         return result;
00946     }
00947 
00948 
00949 
00950     // fill
00951     //
00952     // We implement some fill helper functions in order to allow us to optimize it
00953     // where possible.
00954     //
00955     template <bool bIsScalar>
00956     struct fill_imp
00957     {
00958         template <typename ForwardIterator, typename T>
00959         static void do_fill(ForwardIterator first, ForwardIterator last, const T& value)
00960         {
00961             // The C++ standard doesn't specify whether we need to create a temporary
00962             // or not, but all std STL implementations are written like what we have here.
00963             for(; first != last; ++first)
00964                 *first = value;
00965         }
00966     };
00967 
00968     template <>
00969     struct fill_imp<true>
00970     {
00971         template <typename ForwardIterator, typename T>
00972         static void do_fill(ForwardIterator first, ForwardIterator last, const T& value)
00973         {
00974             // We create a temp and fill from that because value might alias to the
00975             // destination range and so the compiler would be forced into generating
00976             // less efficient code.
00977             for(const T temp(value); first != last; ++first)
00978                 *first = temp;
00979         }
00980     };
00981 
00998     template <typename ForwardIterator, typename T>
00999     inline void fill(ForwardIterator first, ForwardIterator last, const T& value)
01000     {
01001         eastl::fill_imp< is_scalar<T>::value >::do_fill(first, last, value);
01002 
01003         // Possibly better implementation, as it will deal with small PODs as well as scalars:
01004         // bEasyCopy is true if the type has a trivial constructor (e.g. is a POD) and if
01005         // it is small. Thus any built-in type or any small user-defined struct will qualify.
01006         //const bool bEasyCopy = eastl::type_and<eastl::has_trivial_constructor<T>::value,
01007         //                                       eastl::integral_constant<bool, (sizeof(T) <= 16)>::value;
01008         //eastl::fill_imp<bEasyCopy>::do_fill(first, last, value);
01009 
01010     }
01011 
01012     inline void fill(char* first, char* last, const char& c) // It's debateable whether we should use 'char& c' or 'char c' here.
01013     {
01014         memset(first, (unsigned char)c, (size_t)(last - first));
01015     }
01016 
01017     inline void fill(char* first, char* last, const int c) // This is used for cases like 'fill(first, last, 0)'.
01018     {
01019         memset(first, (unsigned char)c, (size_t)(last - first));
01020     }
01021 
01022     inline void fill(unsigned char* first, unsigned char* last, const unsigned char& c)
01023     {
01024         memset(first, (unsigned char)c, (size_t)(last - first));
01025     }
01026 
01027     inline void fill(unsigned char* first, unsigned char* last, const int c)
01028     {
01029         memset(first, (unsigned char)c, (size_t)(last - first));
01030     }
01031 
01032     inline void fill(signed char* first, signed char* last, const signed char& c)
01033     {
01034         memset(first, (unsigned char)c, (size_t)(last - first));
01035     }
01036 
01037     inline void fill(signed char* first, signed char* last, const int c)
01038     {
01039         memset(first, (unsigned char)c, (size_t)(last - first));
01040     }
01041 
01042     #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PPU == PS3 processor, SPU = PS3 cell processor
01043         inline void fill(bool* first, bool* last, const bool& b)
01044         {
01045             memset(first, (char)b, (size_t)(last - first));
01046         }
01047     #endif
01048 
01049 
01050 
01051 
01052     // fill_n
01053     //
01054     // We implement some fill helper functions in order to allow us to optimize it
01055     // where possible.
01056     //
01057     template <bool bIsScalar>
01058     struct fill_n_imp
01059     {
01060         template <typename OutputIterator, typename Size, typename T>
01061         static OutputIterator do_fill(OutputIterator first, Size n, const T& value)
01062         {
01063             for(; n-- > 0; ++first)
01064                 *first = value;
01065             return first;
01066         }
01067     };
01068 
01069     template <>
01070     struct fill_n_imp<true>
01071     {
01072         template <typename OutputIterator, typename Size, typename T>
01073         static OutputIterator do_fill(OutputIterator first, Size n, const T& value)
01074         {
01075             // We create a temp and fill from that because value might alias to
01076             // the destination range and so the compiler would be forced into
01077             // generating less efficient code.
01078             for(const T temp = value; n-- > 0; ++first)
01079                 *first = temp;
01080             return first;
01081         }
01082     };
01083 
01094     template <typename OutputIterator, typename Size, typename T>
01095     OutputIterator fill_n(OutputIterator first, Size n, const T& value)
01096     {
01097         #ifdef _MSC_VER // VC++ up to and including VC8 blow up when you pass a 64 bit scalar to the do_fill function.
01098             return eastl::fill_n_imp< is_scalar<T>::value && (sizeof(T) <= sizeof(uint32_t)) >::do_fill(first, n, value);
01099         #else
01100             return eastl::fill_n_imp< is_scalar<T>::value >::do_fill(first, n, value);
01101         #endif
01102     }
01103 
01104     template <typename Size>
01105     inline char* fill_n(char* first, Size n, const char& c)
01106     {
01107         return (char*)memset(first, (char)c, (size_t)n) + n;
01108     }
01109 
01110     template <typename Size>
01111     inline unsigned char* fill_n(unsigned char* first, Size n, const unsigned char& c)
01112     {
01113         return (unsigned char*)memset(first, (unsigned char)c, (size_t)n) + n;
01114     }
01115 
01116     template <typename Size>
01117     inline signed char* fill_n(signed char* first, Size n, const signed char& c)
01118     {
01119         return (signed char*)memset(first, (signed char)c, n) + (size_t)n;
01120     }
01121 
01122     #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PU == PS3 processor, SPU = PS3 cell processor
01123         template <typename Size>
01124         inline bool* fill_n(bool* first, Size n, const bool& b)
01125         {
01126             return (bool*)memset(first, (char)b, n) + (size_t)n;
01127         }
01128     #endif
01129 
01130 
01131 
01146     template <typename InputIterator, typename T>
01147     inline InputIterator
01148     find(InputIterator first, InputIterator last, const T& value)
01149     {
01150         while((first != last) && !(*first == value)) // Note that we always express value comparisons in terms of < or ==.
01151             ++first;
01152         return first;
01153     }
01154 
01155 
01156 
01172     template <typename InputIterator, typename Predicate>
01173     inline InputIterator
01174     find_if(InputIterator first, InputIterator last, Predicate predicate)
01175     {
01176         while((first != last) && !predicate(*first))
01177             ++first;
01178         return first;
01179     }
01180 
01181 
01182 
01203     template <typename ForwardIterator1, typename ForwardIterator2>
01204     ForwardIterator1
01205     find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
01206                   ForwardIterator2 first2, ForwardIterator2 last2)
01207     {
01208         for(; first1 != last1; ++first1)
01209         {
01210             for(ForwardIterator2 i = first2; i != last2; ++i)
01211             {
01212                 if(*first1 == *i)
01213                     return first1;
01214             }
01215         }
01216         return last1;
01217     }
01218 
01219 
01238     template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
01239     ForwardIterator1
01240     find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
01241                   ForwardIterator2 first2, ForwardIterator2 last2,
01242                   BinaryPredicate predicate)
01243     {
01244         for(; first1 != last1; ++first1)
01245         {
01246             for(ForwardIterator2 i = first2; i != last2; ++i)
01247             {
01248                 if(predicate(*first1, *i))
01249                     return first1;
01250             }
01251         }
01252         return last1;
01253     }
01254 
01255 
01268     template<class ForwardIterator1, class ForwardIterator2>
01269     ForwardIterator1
01270     find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1,
01271                       ForwardIterator2 first2, ForwardIterator2 last2)
01272     {
01273         for(; first1 != last1; ++first1)
01274         {
01275             if(eastl::find(first2, last2, *first1) == last2)
01276                 break;
01277         }
01278 
01279         return first1;
01280     }
01281 
01282 
01283 
01296     template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
01297     inline ForwardIterator1
01298     find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1,
01299                       ForwardIterator2 first2, ForwardIterator2 last2,
01300                       BinaryPredicate predicate)
01301     {
01302         typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type;
01303 
01304         for(; first1 != last1; ++first1)
01305         {
01306             if(eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *first1)) == last2)
01307                 break;
01308         }
01309 
01310         return first1;
01311     }
01312 
01313 
01314     template<class BidirectionalIterator1, class ForwardIterator2>
01315     inline BidirectionalIterator1
01316     find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
01317                  ForwardIterator2 first2, ForwardIterator2 last2)
01318     {
01319         if((first1 != last1) && (first2 != last2))
01320         {
01321             BidirectionalIterator1 it1(last1);
01322 
01323             while((--it1 != first1) && (eastl::find(first2, last2, *it1) == last2))
01324                 ; // Do nothing
01325 
01326             if((it1 != first1) || (eastl::find(first2, last2, *it1) != last2))
01327                 return it1;
01328         }
01329 
01330         return last1;
01331     }
01332 
01333 
01334     template<class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
01335     BidirectionalIterator1
01336     find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
01337                  ForwardIterator2 first2, ForwardIterator2 last2,
01338                  BinaryPredicate predicate)
01339     {
01340         typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
01341 
01342         if((first1 != last1) && (first2 != last2))
01343         {
01344             BidirectionalIterator1 it1(last1);
01345 
01346             while((--it1 != first1) && (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) == last2))
01347                 ; // Do nothing
01348 
01349             if((it1 != first1) || (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
01350                 return it1;
01351         }
01352 
01353         return last1;
01354     }
01355 
01356 
01357     template<class BidirectionalIterator1, class ForwardIterator2>
01358     inline BidirectionalIterator1
01359     find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
01360                      ForwardIterator2 first2, ForwardIterator2 last2)
01361     {
01362         if((first1 != last1) && (first2 != last2))
01363         {
01364             BidirectionalIterator1 it1(last1);
01365 
01366             while((--it1 != first1) && (eastl::find(first2, last2, *it1) != last2))
01367                 ; // Do nothing
01368 
01369             if((it1 != first1) || (eastl::find( first2, last2, *it1) == last2))
01370                 return it1;
01371         }
01372 
01373         return last1;
01374     }
01375 
01376 
01377     template<class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
01378     inline BidirectionalIterator1
01379     find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
01380                      ForwardIterator2 first2, ForwardIterator2 last2,
01381                      BinaryPredicate predicate)
01382     {
01383         typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
01384 
01385         if((first1 != last1) && (first2 != last2))
01386         {
01387             BidirectionalIterator1 it1(last1);
01388 
01389             while((--it1 != first1) && (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
01390                 ; // Do nothing
01391 
01392             if((it1 != first1) || (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1))) != last2)
01393                 return it1;
01394         }
01395 
01396         return last1;
01397     }
01398 
01399 
01400 
01401 
01416     template <typename InputIterator, typename Function>
01417     inline Function
01418     for_each(InputIterator first, InputIterator last, Function function)
01419     {
01420         for(; first != last; ++first)
01421             function(*first);
01422         return function;
01423     }
01424 
01425 
01434     template <typename ForwardIterator, typename Generator>
01435     inline void
01436     generate(ForwardIterator first, ForwardIterator last, Generator generator)
01437     {
01438         for(; first != last; ++first) // We cannot call generate_n(first, last-first, generator)
01439             *first = generator();     // because the 'last-first' might not be supported by the
01440     }                                 // given iterator.
01441 
01442 
01451     template <typename OutputIterator, typename Size, typename Generator>
01452     inline OutputIterator
01453     generate_n(OutputIterator first, Size n, Generator generator)
01454     {
01455         for(; n > 0; --n, ++first)
01456             *first = generator();
01457         return first;
01458     }
01459 
01460 
01477     template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
01478     inline OutputIterator
01479     transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
01480     {
01481         for(; first != last; ++first, ++result)
01482             *result = unaryOperation(*first);
01483         return result;
01484     }
01485 
01486 
01503     template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
01504     inline OutputIterator
01505     transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binaryOperation)
01506     {
01507         for(; first1 != last1; ++first1, ++first2, ++result)
01508             *result = binaryOperation(*first1, *first2);
01509         return result;
01510     }
01511 
01512 
01525     template <typename InputIterator1, typename InputIterator2>
01526     inline bool
01527     equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
01528     {
01529         for(; first1 != last1; ++first1, ++first2)
01530         {
01531             if(!(*first1 == *first2)) // Note that we always express value comparisons in terms of < or ==.
01532                 return false;
01533         }
01534         return true;
01535     }
01536 
01545     template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
01546     inline bool
01547     equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate predicate)
01548     {
01549         for(; first1 != last1; ++first1, ++first2)
01550         {
01551             if(!predicate(*first1, *first2))
01552                 return false;
01553         }
01554         return true;
01555     }
01556 
01557 
01558 
01578     template <typename InputIterator1, typename InputIterator2>
01579     bool identical(InputIterator1 first1, InputIterator1 last1,
01580                    InputIterator2 first2, InputIterator2 last2)
01581     {
01582         while((first1 != last1) && (first2 != last2) && (*first1 == *first2))
01583         {
01584             ++first1;
01585             ++first2;
01586         }
01587         return (first1 == last1) && (first2 == last2);
01588     }
01589 
01590 
01593     template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
01594     bool identical(InputIterator1 first1, InputIterator1 last1,
01595                    InputIterator2 first2, InputIterator2 last2, BinaryPredicate predicate)
01596     {
01597         while((first1 != last1) && (first2 != last2) && predicate(*first1, *first2))
01598         {
01599             ++first1;
01600             ++first2;
01601         }
01602         return (first1 == last1) && (first2 == last2);
01603     }
01604 
01605 
01623     template <typename InputIterator1, typename InputIterator2>
01624     inline bool
01625     lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
01626     {
01627         for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
01628         {
01629             if(*first1 < *first2)
01630                 return true;
01631             if(*first2 < *first1)
01632                 return false;
01633         }
01634         return (first1 == last1) && (first2 != last2);
01635     }
01636 
01637     inline bool     // Specialization for const char*.
01638     lexicographical_compare(const char* first1, const char* last1, const char* first2, const char* last2)
01639     {
01640         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01641         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01642         return result ? (result < 0) : (n1 < n2);
01643     }
01644 
01645     inline bool     // Specialization for char*.
01646     lexicographical_compare(char* first1, char* last1, char* first2, char* last2)
01647     {
01648         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01649         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01650         return result ? (result < 0) : (n1 < n2);
01651     }
01652 
01653     inline bool     // Specialization for const unsigned char*.
01654     lexicographical_compare(const unsigned char* first1, const unsigned char* last1, const unsigned char* first2, const unsigned char* last2)
01655     {
01656         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01657         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01658         return result ? (result < 0) : (n1 < n2);
01659     }
01660 
01661     inline bool     // Specialization for unsigned char*.
01662     lexicographical_compare(unsigned char* first1, unsigned char* last1, unsigned char* first2, unsigned char* last2)
01663     {
01664         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01665         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01666         return result ? (result < 0) : (n1 < n2);
01667     }
01668 
01669     inline bool     // Specialization for const signed char*.
01670     lexicographical_compare(const signed char* first1, const signed char* last1, const signed char* first2, const signed char* last2)
01671     {
01672         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01673         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01674         return result ? (result < 0) : (n1 < n2);
01675     }
01676 
01677     inline bool     // Specialization for signed char*.
01678     lexicographical_compare(signed char* first1, signed char* last1, signed char* first2, signed char* last2)
01679     {
01680         const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01681         const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01682         return result ? (result < 0) : (n1 < n2);
01683     }
01684 
01685     #if defined(_MSC_VER) // If using the VC++ compiler (and thus bool is known to be a single byte)...
01686         //Not sure if this is a good idea.
01687         //inline bool     // Specialization for const bool*.
01688         //lexicographical_compare(const bool* first1, const bool* last1, const bool* first2, const bool* last2)
01689         //{
01690         //    const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01691         //    const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01692         //    return result ? (result < 0) : (n1 < n2);
01693         //}
01694         //
01695         //inline bool     // Specialization for bool*.
01696         //lexicographical_compare(bool* first1, bool* last1, bool* first2, bool* last2)
01697         //{
01698         //    const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
01699         //    const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
01700         //    return result ? (result < 0) : (n1 < n2);
01701         //}
01702     #endif
01703 
01704 
01705 
01729     template <typename InputIterator1, typename InputIterator2, typename Compare>
01730     inline bool
01731     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
01732                             InputIterator2 first2, InputIterator2 last2, Compare compare)
01733     {
01734         for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
01735         {
01736             if(compare(*first1, *first2))
01737                 return true;
01738             if(compare(*first2, *first1))
01739                 return false;
01740         }
01741         return (first1 == last1) && (first2 != last2);
01742     }
01743 
01744 
01745 
01764     template <typename ForwardIterator, typename T>
01765     ForwardIterator
01766     lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
01767     {
01768         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01769 
01770         DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.
01771 
01772         while(d > 0)
01773         {
01774             ForwardIterator i  = first;
01775             DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
01776 
01777             eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.
01778 
01779             if(*i < value)
01780             {
01781                 // Disabled because std::lower_bound doesn't specify (23.3.3.3, p3) this can be done: EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
01782                 first = ++i;
01783                 d    -= d2 + 1;
01784             }
01785             else
01786                 d = d2;
01787         }
01788         return first;
01789     }
01790 
01791 
01812     template <typename ForwardIterator, typename T, typename Compare>
01813     ForwardIterator
01814     lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
01815     {
01816         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01817 
01818         DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.
01819 
01820         while(d > 0)
01821         {
01822             ForwardIterator i  = first;
01823             DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
01824 
01825             eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.
01826 
01827             if(compare(*i, value))
01828             {
01829                 // Disabled because std::lower_bound doesn't specify (23.3.3.1, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
01830                 first = ++i;
01831                 d    -= d2 + 1;
01832             }
01833             else
01834                 d = d2;
01835         }
01836         return first;
01837     }
01838 
01839 
01840 
01855     template <typename ForwardIterator, typename T>
01856     ForwardIterator
01857     upper_bound(ForwardIterator first, ForwardIterator last, const T& value)
01858     {
01859         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01860 
01861         DifferenceType len = eastl::distance(first, last);
01862 
01863         while(len > 0)
01864         {
01865             ForwardIterator i    = first;
01866             DifferenceType  len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
01867 
01868             eastl::advance(i, len2);
01869 
01870             if(!(value < *i)) // Note that we always express value comparisons in terms of < or ==.
01871             {
01872                 first = ++i;
01873                 len -= len2 + 1;
01874             }
01875             else
01876             {
01877                 // Disabled because std::upper_bound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
01878                 len = len2;
01879             }
01880         }
01881         return first;
01882     }
01883 
01884 
01901     template <typename ForwardIterator, typename T, typename Compare>
01902     ForwardIterator
01903     upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
01904     {
01905         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01906 
01907         DifferenceType len = eastl::distance(first, last);
01908 
01909         while(len > 0)
01910         {
01911             ForwardIterator i    = first;
01912             DifferenceType  len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
01913 
01914             eastl::advance(i, len2);
01915 
01916             if(!compare(value, *i))
01917             {
01918                 first = ++i;
01919                 len -= len2 + 1;
01920             }
01921             else
01922             {
01923                 // Disabled because std::upper_bound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
01924                 len = len2;
01925             }
01926         }
01927         return first;
01928     }
01929 
01930 
01939     template <typename ForwardIterator, typename T>
01940     pair<ForwardIterator, ForwardIterator>
01941     equal_range(ForwardIterator first, ForwardIterator last, const T& value)
01942     {
01943         typedef pair<ForwardIterator, ForwardIterator> ResultType;
01944         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01945 
01946         DifferenceType d = eastl::distance(first, last);
01947 
01948         while(d > 0)
01949         {
01950             ForwardIterator i(first);
01951             DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
01952 
01953             eastl::advance(i, d2);
01954 
01955             if(*i < value)
01956             {
01957                 EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
01958                 first = ++i;
01959                 d    -= d2 + 1;
01960             }
01961             else if(value < *i)
01962             {
01963                 EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
01964                 d    = d2;
01965                 last = i;
01966             }
01967             else
01968             {
01969                 ForwardIterator j(i);
01970 
01971                 return ResultType(eastl::lower_bound(first, i, value),
01972                                   eastl::upper_bound(++j, last, value));
01973             }
01974         }
01975         return ResultType(first, first);
01976     }
01977 
01978 
01987     template <typename ForwardIterator, typename T, typename Compare>
01988     pair<ForwardIterator, ForwardIterator>
01989     equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
01990     {
01991         typedef pair<ForwardIterator, ForwardIterator> ResultType;
01992         typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
01993 
01994         DifferenceType d = eastl::distance(first, last);
01995 
01996         while(d > 0)
01997         {
01998             ForwardIterator i(first);
01999             DifferenceType  d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
02000 
02001             eastl::advance(i, d2);
02002 
02003             if(compare(*i, value))
02004             {
02005                 EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
02006                 first = ++i;
02007                 d    -= d2 + 1;
02008             }
02009             else if(compare(value, *i))
02010             {
02011                 EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
02012                 d    = d2;
02013                 last = i;
02014             }
02015             else
02016             {
02017                 ForwardIterator j(i);
02018 
02019                 return ResultType(eastl::lower_bound(first, i, value, compare),
02020                                   eastl::upper_bound(++j, last, value, compare));
02021             }
02022         }
02023         return ResultType(first, first);
02024     }
02025 
02026 
02037     template <typename ForwardIterator, typename T>
02038     inline void
02039     replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
02040     {
02041         for(; first != last; ++first)
02042         {
02043             if(*first == old_value)
02044                 *first = new_value;
02045         }
02046     }
02047 
02048 
02059     template <typename ForwardIterator, typename Predicate, typename T>
02060     inline void
02061     replace_if(ForwardIterator first, ForwardIterator last, Predicate predicate, const T& new_value)
02062     {
02063         for(; first != last; ++first)
02064         {
02065             if(predicate(*first))
02066                 *first = new_value;
02067         }
02068     }
02069 
02070 
02083     template <typename InputIterator, typename OutputIterator, typename T>
02084     inline OutputIterator
02085     remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value)
02086     {
02087         for(; first != last; ++first)
02088         {
02089             if(!(*first == value)) // Note that we always express value comparisons in terms of < or ==.
02090             {
02091                 *result = *first;
02092                 ++result;
02093             }
02094         }
02095         return result;
02096     }
02097 
02098 
02111     template <typename InputIterator, typename OutputIterator, typename Predicate>
02112     inline OutputIterator
02113     remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
02114     {
02115         for(; first != last; ++first)
02116         {
02117             if(!predicate(*first))
02118             {
02119                 *result = *first;
02120                 ++result;
02121             }
02122         }
02123         return result;
02124     }
02125 
02126 
02150     template <typename ForwardIterator, typename T>
02151     inline ForwardIterator
02152     remove(ForwardIterator first, ForwardIterator last, const T& value)
02153     {
02154         first = eastl::find(first, last, value);
02155         if(first != last)
02156         {
02157             ForwardIterator i(first);
02158             return eastl::remove_copy(++i, last, first, value);
02159         }
02160         return first;
02161     }
02162 
02163 
02187     template <typename ForwardIterator, typename Predicate>
02188     inline ForwardIterator
02189     remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
02190     {
02191         first = eastl::find_if(first, last, predicate);
02192         if(first != last)
02193         {
02194             ForwardIterator i(first);
02195             return eastl::remove_copy_if<ForwardIterator, ForwardIterator, Predicate>(++i, last, first, predicate);
02196         }
02197         return first;
02198     }
02199 
02200 
02216     template <typename InputIterator, typename OutputIterator, typename T>
02217     inline OutputIterator
02218     replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)
02219     {
02220         for(; first != last; ++first, ++result)
02221             *result = (*first == old_value) ? new_value : *first;
02222         return result;
02223     }
02224 
02225 
02241     template <typename InputIterator, typename OutputIterator, typename Predicate, typename T>
02242     inline OutputIterator
02243     replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate, const T& new_value)
02244     {
02245         for(; first != last; ++first, ++result)
02246             *result = predicate(*first) ? new_value : *first;
02247         return result;
02248     }
02249 
02250 
02251 
02252 
02253     // reverse
02254     //
02255     // We provide helper functions which allow reverse to be implemented more
02256     // efficiently for some types of iterators and types.
02257     //
02258     template <typename BidirectionalIterator>
02259     inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, EASTL_ITC_NS::bidirectional_iterator_tag)
02260     {
02261         for(; (first != last) && (first != --last); ++first) // We are not allowed to use operator <, <=, >, >= with a
02262             eastl::iter_swap(first, last);                   // generic (bidirectional or otherwise) iterator.
02263     }
02264 
02265     template <typename RandomAccessIterator>
02266     inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
02267     {
02268         for(; first < --last; ++first)      // With a random access iterator, we can use operator < to more efficiently implement
02269             eastl::iter_swap(first, last);  // this algorithm. A generic iterator doesn't necessarily have an operator < defined.
02270     }
02271 
02281     template <typename BidirectionalIterator>
02282     inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
02283     {
02284         typedef typename eastl::iterator_traits<BidirectionalIterator>::iterator_category IC;
02285         eastl::reverse_impl(first, last, IC());
02286     }
02287 
02288 
02289 
02306     template <typename BidirectionalIterator, typename OutputIterator>
02307     inline OutputIterator
02308     reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
02309     {
02310         for(; first != last; ++result)
02311             *result = *--last;
02312         return result;
02313     }
02314 
02315 
02316 
02331     template <typename ForwardIterator1, typename ForwardIterator2>
02332     ForwardIterator1
02333     search(ForwardIterator1 first1, ForwardIterator1 last1,
02334            ForwardIterator2 first2, ForwardIterator2 last2)
02335     {
02336         if(first2 != last2) // If there is anything to search for...
02337         {
02338             // We need to make a special case for a pattern of one element,
02339             // as the logic below prevents one element patterns from working.
02340             ForwardIterator2 temp2(first2);
02341             ++temp2;
02342 
02343             if(temp2 != last2) // If what we are searching for has a length > 1...
02344             {
02345                 ForwardIterator1 cur1(first1);
02346                 ForwardIterator2 p2;
02347 
02348                 while(first1 != last1)
02349                 {
02350                     // The following loop is the equivalent of eastl::find(first1, last1, *first2)
02351                     while((first1 != last1) && !(*first1 == *first2))
02352                         ++first1;
02353 
02354                     if(first1 != last1)
02355                     {
02356                         p2   = temp2;
02357                         cur1 = first1;
02358 
02359                         if(++cur1 != last1)
02360                         {
02361                             while(*cur1 == *p2)
02362                             {
02363                                 if(++p2 == last2)
02364                                     return first1;
02365 
02366                                 if(++cur1 == last1)
02367                                     return last1;
02368                             }
02369 
02370                             ++first1;
02371                             continue;
02372                         }
02373                     }
02374                     return last1;
02375                 }
02376 
02377                 // Fall through to the end.
02378             }
02379             else
02380                 return eastl::find(first1, last1, *first2);
02381         }
02382 
02383         return first1;
02384 
02385 
02386         #if 0
02387         /*  Another implementation which is a little more simpler but executes a little slower on average.
02388             typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
02389             typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;
02390 
02391             const difference_type_2 d2 = eastl::distance(first2, last2);
02392 
02393             for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; ++first1, --d1)
02394             {
02395                 ForwardIterator1 temp1 = first1;
02396 
02397                 for(ForwardIterator2 temp2 = first2; ; ++temp1, ++temp2)
02398                 {
02399                     if(temp2 == last2)
02400                         return first1;
02401                     if(!(*temp1 == *temp2))
02402                         break;
02403                 }
02404             }
02405 
02406             return last1;
02407         */
02408         #endif
02409     }
02410 
02411 
02426     template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
02427     ForwardIterator1
02428     search(ForwardIterator1 first1, ForwardIterator1 last1,
02429            ForwardIterator2 first2, ForwardIterator2 last2,
02430            BinaryPredicate predicate)
02431     {
02432         typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
02433         typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;
02434 
02435         difference_type_2 d2 = eastl::distance(first2, last2);
02436 
02437         if(d2 != 0)
02438         {
02439             ForwardIterator1 i(first1);
02440             eastl::advance(i, d2);
02441 
02442             for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; --d1)
02443             {
02444                 if(eastl::equal<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, i, first2, predicate))
02445                     return first1;
02446                 if(d1 > d2) // To do: Find a way to make the algorithm more elegant.
02447                 {
02448                     ++first1;
02449                     ++i;
02450                 }
02451             }
02452             return last1;
02453         }
02454         return first1; // Just like with strstr, we return first1 if the match string is empty.
02455     }
02456 
02457 
02458 
02459     // search_n helper functions
02460     //
02461     template <typename ForwardIterator, typename Size, typename T>
02462     ForwardIterator     // Generic implementation.
02463     search_n_impl(ForwardIterator first, ForwardIterator last, Size count, const T& value, EASTL_ITC_NS::forward_iterator_tag)
02464     {
02465         if(count <= 0)
02466             return first;
02467 
02468         Size d1 = (Size)eastl::distance(first, last); // Should d1 be of type Size, ptrdiff_t, or iterator_traits<ForwardIterator>::difference_type?
02469                                                       // The problem with using iterator_traits<ForwardIterator>::difference_type is that
02470         if(count > d1)                                // ForwardIterator may not be a true iterator but instead something like a pointer.
02471             return last;
02472 
02473         for(; d1 >= count; ++first, --d1)
02474         {
02475             ForwardIterator i(first);
02476 
02477             for(Size n = 0; n < count; ++n, ++i, --d1)
02478             {
02479                 if(!(*i == value)) // Note that we always express value comparisons in terms of < or ==.
02480                     goto not_found;
02481             }
02482             return first;
02483 
02484             not_found:
02485             first = i;
02486         }
02487         return last;
02488     }
02489 
02490     template <typename RandomAccessIterator, typename Size, typename T> inline
02491     RandomAccessIterator    // Random access iterator implementation. Much faster than generic implementation.
02492     search_n_impl(RandomAccessIterator first, RandomAccessIterator last, Size count, const T& value, EASTL_ITC_NS::random_access_iterator_tag)
02493     {
02494         if(count <= 0)
02495             return first;
02496         else if(count == 1)
02497             return find(first, last, value);
02498         else if(last > first)
02499         {
02500             RandomAccessIterator lookAhead;
02501             RandomAccessIterator backTrack;
02502 
02503             Size skipOffset = (count - 1);
02504             Size tailSize = (Size)(last - first);
02505             Size remainder;
02506             Size prevRemainder;
02507 
02508             for(lookAhead = first + skipOffset; tailSize >= count; lookAhead += count)
02509             {
02510                 tailSize -= count;
02511 
02512                 if(*lookAhead == value)
02513                 {
02514                     remainder = skipOffset;
02515 
02516                     for(backTrack = lookAhead - 1; *backTrack == value; --backTrack)
02517                     {
02518                         if(--remainder == 0)
02519                             return (lookAhead - skipOffset); // success
02520                     }
02521 
02522                     if(remainder <= tailSize)
02523                     {
02524                         prevRemainder = remainder;
02525 
02526                         while(*(++lookAhead) == value)
02527                         {
02528                             if(--remainder == 0)
02529                                 return (backTrack + 1); // success
02530                         }
02531                         tailSize -= (prevRemainder - remainder);
02532                     }
02533                     else
02534                         return last; // failure
02535                 }
02536 
02537                 // lookAhead here is always pointing to the element of the last mismatch.
02538             }
02539         }
02540 
02541         return last; // failure
02542     }
02543 
02544 
02554     template <typename ForwardIterator, typename Size, typename T>
02555     ForwardIterator
02556     search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
02557     {
02558         typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
02559         return eastl::search_n_impl(first, last, count, value, IC());
02560     }
02561 
02562 
02584     template <typename ForwardIterator, typename T>
02585     inline bool
02586     binary_search(ForwardIterator first, ForwardIterator last, const T& value)
02587     {
02588         // To do: This can be made slightly faster by not using lower_bound.
02589         ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
02590         return ((i != last) && !(value < *i)); // Note that we always express value comparisons in terms of < or ==.
02591     }
02592 
02593 
02604     template <typename ForwardIterator, typename T, typename Compare>
02605     inline bool
02606     binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
02607     {
02608         // To do: This can be made slightly faster by not using lower_bound.
02609         ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
02610         return ((i != last) && !compare(value, *i));
02611     }
02612 
02613 
02622     template <typename ForwardIterator, typename T>
02623     inline ForwardIterator
02624     binary_search_i(ForwardIterator first, ForwardIterator last, const T& value)
02625     {
02626         // To do: This can be made slightly faster by not using lower_bound.
02627         ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
02628         if((i != last) && !(value < *i)) // Note that we always express value comparisons in terms of < or ==.
02629             return i;
02630         return last;
02631     }
02632 
02633 
02642     template <typename ForwardIterator, typename T, typename Compare>
02643     inline ForwardIterator
02644     binary_search_i(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
02645     {
02646         // To do: This can be made slightly faster by not using lower_bound.
02647         ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
02648         if((i != last) && !compare(value, *i))
02649             return i;
02650         return last;
02651     }
02652 
02653 
02676     template <typename ForwardIterator>
02677     ForwardIterator unique(ForwardIterator first, ForwardIterator last)
02678     {
02679         first = eastl::adjacent_find<ForwardIterator>(first, last);
02680 
02681         if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
02682         {
02683             ForwardIterator dest(first);
02684 
02685             for(++first; first != last; ++first)
02686             {
02687                 if(!(*dest == *first)) // Note that we always express value comparisons in terms of < or ==.
02688                     *++dest = *first;
02689             }
02690             return ++dest;
02691         }
02692         return last;
02693     }
02694 
02695 
02713     template <typename ForwardIterator, typename BinaryPredicate>
02714     ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
02715     {
02716         first = eastl::adjacent_find<ForwardIterator, BinaryPredicate>(first, last, predicate);
02717 
02718         if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
02719         {
02720             ForwardIterator dest(first);
02721 
02722             for(++first; first != last; ++first)
02723             {
02724                 if(!predicate(*dest, *first))
02725                     *++dest = *first;
02726             }
02727             return ++dest;
02728         }
02729         return last;
02730     }
02731 
02732 
02733 
02734     // find_end
02735     //
02736     // We provide two versions here, one for a bidirectional iterators and one for
02737     // regular forward iterators. Given that we are searching backward, it's a bit
02738     // more efficient if we can use backwards iteration to implement our search,
02739     // though this requires an iterator that can be reversed.
02740     //
02741     template <typename ForwardIterator1, typename ForwardIterator2>
02742     ForwardIterator1
02743     find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
02744                   ForwardIterator2 first2, ForwardIterator2 last2,
02745                   EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
02746     {
02747         if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
02748         {
02749             for(ForwardIterator1 result(last1); ; )
02750             {
02751                 const ForwardIterator1 resultNext(eastl::search(first1, last1, first2, last2));
02752 
02753                 if(resultNext != last1) // If another sequence was found...
02754                 {
02755                     first1 = result = resultNext;
02756                     ++first1;
02757                 }
02758                 else
02759                     return result;
02760             }
02761         }
02762         return last1;
02763     }
02764 
02765     template <typename BidirectionalIterator1, typename BidirectionalIterator2>
02766     BidirectionalIterator1
02767     find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
02768                   BidirectionalIterator2 first2, BidirectionalIterator2 last2,
02769                   EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
02770     {
02771         typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
02772         typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;
02773 
02774         reverse_iterator1 rresult(eastl::search(reverse_iterator1(last1), reverse_iterator1(first1),
02775                                                 reverse_iterator2(last2), reverse_iterator2(first2)));
02776         if(rresult.base() != first1) // If we found something...
02777         {
02778             BidirectionalIterator1 result(rresult.base());
02779 
02780             eastl::advance(result, -eastl::distance(first2, last2)); // We have an opportunity to optimize this, as the
02781             return result;                                           // search function already calculates this distance.
02782         }
02783         return last1;
02784     }
02785 
02797     template <typename ForwardIterator1, typename ForwardIterator2>
02798     inline ForwardIterator1
02799     find_end(ForwardIterator1 first1, ForwardIterator1 last1,
02800              ForwardIterator2 first2, ForwardIterator2 last2)
02801     {
02802         typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
02803         typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
02804 
02805         return eastl::find_end_impl(first1, last1, first2, last2, IC1(), IC2());
02806     }
02807 
02808 
02809 
02810 
02811     // To consider: Fold the predicate and non-predicate versions of
02812     //              this algorithm into a single function.
02813     template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
02814     ForwardIterator1
02815     find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
02816                   ForwardIterator2 first2, ForwardIterator2 last2,
02817                   BinaryPredicate predicate,
02818                   EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
02819     {
02820         if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
02821         {
02822             for(ForwardIterator1 result = last1; ; )
02823             {
02824                 const ForwardIterator1 resultNext(eastl::search<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, last1, first2, last2, predicate));
02825 
02826                 if(resultNext != last1) // If another sequence was found...
02827                 {
02828                     first1 = result = resultNext;
02829                     ++first1;
02830                 }
02831                 else
02832                     return result;
02833             }
02834         }
02835         return last1;
02836     }
02837 
02838     template <typename BidirectionalIterator1, typename BidirectionalIterator2, typename BinaryPredicate>
02839     BidirectionalIterator1
02840     find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
02841                   BidirectionalIterator2 first2, BidirectionalIterator2 last2,
02842                   BinaryPredicate predicate,
02843                   EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
02844     {
02845         typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
02846         typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;
02847 
02848         reverse_iterator1 rresult(eastl::search<reverse_iterator1, reverse_iterator2, BinaryPredicate>
02849                                                (reverse_iterator1(last1), reverse_iterator1(first1),
02850                                                 reverse_iterator2(last2), reverse_iterator2(first2),
02851                                                 predicate));
02852         if(rresult.base() != first1) // If we found something...
02853         {
02854             BidirectionalIterator1 result(rresult.base());
02855             eastl::advance(result, -eastl::distance(first2, last2));
02856             return result;
02857         }
02858         return last1;
02859     }
02860 
02861 
02874     template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
02875     inline ForwardIterator1
02876     find_end(ForwardIterator1 first1, ForwardIterator1 last1,
02877              ForwardIterator2 first2, ForwardIterator2 last2,
02878              BinaryPredicate predicate)
02879     {
02880         typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
02881         typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
02882 
02883         return eastl::find_end_impl<ForwardIterator1, ForwardIterator2, BinaryPredicate>
02884                                    (first1, last1, first2, last2, predicate, IC1(), IC2());
02885     }
02886 
02887 
02888 
02905     template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
02906     OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
02907                                   InputIterator2 first2, InputIterator2 last2,
02908                                   OutputIterator result)
02909     {
02910         while((first1 != last1) && (first2 != last2))
02911         {
02912             if(*first1 < *first2)
02913             {
02914                 *result = *first1;
02915                 ++first1;
02916                 ++result;
02917             }
02918             else if(*first2 < *first1)
02919                 ++first2;
02920             else
02921             {
02922                 ++first1;
02923                 ++first2;
02924             }
02925         }
02926 
02927         return eastl::copy(first1, last1, result);
02928     }
02929 
02930 
02931     template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
02932     OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
02933                                   InputIterator2 first2, InputIterator2 last2,
02934                                   OutputIterator result, Compare compare)
02935     {
02936         while((first1 != last1) && (first2 != last2))
02937         {
02938             if(compare(*first1, *first2))
02939             {
02940                 EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
02941                 *result = *first1;
02942                 ++first1;
02943                 ++result;
02944             }
02945             else if(compare(*first2, *first1))
02946             {
02947                 EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
02948                 ++first2;
02949             }
02950             else
02951             {
02952                 ++first1;
02953                 ++first2;
02954             }
02955         }
02956 
02957         return eastl::copy(first1, last1, result);
02958     }
02959 
02960 } // namespace eastl
02961 
02962 
02963 
02964 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends