algorithm.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2014 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_ALGORITHM__
00032 #define __ETL_ALGORITHM__
00033 
00034 ///\defgroup algorithm algorithm
00035 /// Reverse engineered algorithms from C++ 0x11
00036 /// Additional new variants of certain algorithms.
00037 ///\ingroup utilities
00038 
00039 #include <algorithm>
00040 #include <iterator>
00041 #include <utility>
00042 #include <functional>
00043 #include <iterator>
00044 #include <stdint.h>
00045 
00046 #include "platform.h "
00047 #include "iterator.h "
00048 #include "type_traits.h "
00049 
00050 namespace etl
00051 {
00052   //***************************************************************************
00053   /// Finds the greatest and the smallest element in the range (begin, end).<br>
00054   ///<a href="http://en.cppreference.com/w/cpp/algorithm/minmax_element"></a>
00055   ///\ingroup algorithm
00056   //***************************************************************************
00057   template <typename TIterator,
00058             typename TCompare>
00059   std::pair<TIterator, TIterator> minmax_element(TIterator begin,
00060                                                  TIterator end,
00061                                                  TCompare  compare)
00062   {
00063     TIterator minimum = begin;
00064     TIterator maximum = begin;
00065 
00066     while (begin != end)
00067     {
00068       if (compare(*begin, *minimum))
00069       {
00070         minimum = begin;
00071       }
00072 
00073       if (compare(*maximum, *begin))
00074       {
00075         maximum = begin;
00076       }
00077 
00078       ++begin;
00079     }
00080 
00081     return std::pair<TIterator, TIterator>(minimum, maximum);
00082   }
00083 
00084   //***************************************************************************
00085   /// minmax_element
00086   ///\ingroup algorithm
00087   ///<a href="http://en.cppreference.com/w/cpp/algorithm/minmax_element"></a>
00088   //***************************************************************************
00089   template <typename TIterator>
00090   std::pair<TIterator, TIterator> minmax_element(TIterator begin,
00091                                                  TIterator end)
00092   {
00093       typedef typename std::iterator_traits<TIterator>::value_type value_t;
00094 
00095       return etl::minmax_element(begin, end, std::less<value_t>());
00096   }
00097 
00098   //***************************************************************************
00099   /// minmax
00100   ///\ingroup algorithm
00101   ///<a href="http://en.cppreference.com/w/cpp/algorithm/minmax"></a>
00102   //***************************************************************************
00103   template <typename T>
00104   std::pair<const T&, const T&> minmax(const T& a,
00105                                        const T& b)
00106   {
00107     return (b < a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
00108   }
00109 
00110   //***************************************************************************
00111   /// minmax
00112   ///\ingroup algorithm
00113   ///<a href="http://en.cppreference.com/w/cpp/algorithm/minmax"></a>
00114   //***************************************************************************
00115   template <typename T,
00116             typename TCompare>
00117   std::pair<const T&, const T&> minmax(const T& a,
00118                                        const T& b,
00119                                        TCompare compare)
00120   {
00121     return compare(b, a) ? std::pair<const T&, const T&>(b, a) : std::pair<const T&, const T&>(a, b);
00122   }
00123 
00124   //***************************************************************************
00125   /// is_sorted_until
00126   ///\ingroup algorithm
00127   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_sorted_until"></a>
00128   //***************************************************************************
00129   template <typename TIterator>
00130   TIterator is_sorted_until(TIterator begin,
00131                             TIterator end)
00132   {
00133     if (begin != end)
00134     {
00135       TIterator next = begin;
00136 
00137       while (++next != end)
00138       {
00139         if (*next < *begin)
00140         {
00141           return next;
00142         }
00143 
00144         ++begin;
00145       }
00146     }
00147 
00148     return end;
00149   }
00150 
00151   //***************************************************************************
00152   /// is_sorted_until
00153   ///\ingroup algorithm
00154   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_sorted_until"></a>
00155   //***************************************************************************
00156   template <typename TIterator,
00157             typename TCompare>
00158   TIterator is_sorted_until(TIterator begin,
00159                             TIterator end,
00160                             TCompare  compare)
00161   {
00162     if (begin != end)
00163     {
00164       TIterator next = begin;
00165 
00166       while (++next != end)
00167       {
00168         if (compare(*next, *begin))
00169         {
00170           return next;
00171         }
00172 
00173         ++begin;
00174       }
00175     }
00176 
00177     return end;
00178   }
00179 
00180   //***************************************************************************
00181   /// is_sorted
00182   ///\ingroup algorithm
00183   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_sorted"></a>
00184   //***************************************************************************
00185   template<typename TIterator>
00186   bool is_sorted(TIterator begin,
00187                  TIterator end)
00188   {
00189     return etl::is_sorted_until(begin, end) == end;
00190   }
00191 
00192   //***************************************************************************
00193   /// is_sorted
00194   ///\ingroup algorithm
00195   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_sorted"></a>
00196   //***************************************************************************
00197   template<typename TIterator,
00198            typename TCompare>
00199   bool is_sorted(TIterator begin,
00200                  TIterator end,
00201                  TCompare  compare)
00202   {
00203     return etl::is_sorted_until(begin, end, compare) == end;
00204   }
00205 
00206   //***************************************************************************
00207   /// copy
00208   /// A form of copy where the smallest of the two ranges is used.
00209   /// There is currently no STL equivalent.
00210   /// Specialisation for random access iterators.
00211   ///\param i_begin Beginning of the input range.
00212   ///\param i_end   End of the input range.
00213   ///\param o_begin Beginning of the output range.
00214   ///\param o_end   End of the output range.
00215   ///\ingroup algorithm
00216   //***************************************************************************
00217   template <typename TInputIterator,
00218             typename TOutputIterator>
00219   typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value &&
00220                           etl::is_random_iterator<TOutputIterator>::value, TOutputIterator>::type
00221    copy(TInputIterator  i_begin,
00222         TInputIterator  i_end,
00223         TOutputIterator o_begin,
00224         TOutputIterator o_end)
00225   {
00226       size_t s_size = std::distance(i_begin, i_end);
00227       size_t d_size = std::distance(o_begin, o_end);
00228       size_t size   = (s_size < d_size) ? s_size : d_size;
00229 
00230       return std::copy(i_begin, i_begin + size, o_begin);
00231   }
00232 
00233   //***************************************************************************
00234   /// copy
00235   /// A form of copy where the smallest of the two ranges is used.
00236   /// There is currently no STL equivalent.
00237   /// Specialisation for non random access iterators.
00238   ///\param i_begin Beginning of the input range.
00239   ///\param i_end   End of the input range.
00240   ///\param o_begin Beginning of the output range.
00241   ///\param o_end   End of the output range.
00242   ///\ingroup algorithm
00243   //***************************************************************************
00244   template <typename TInputIterator,
00245             typename TOutputIterator>
00246   typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value ||
00247                           !etl::is_random_iterator<TOutputIterator>::value, TOutputIterator>::type
00248    copy(TInputIterator  i_begin,
00249         TInputIterator  i_end,
00250         TOutputIterator o_begin,
00251         TOutputIterator o_end)
00252   {
00253     while ((i_begin != i_end) && (o_begin != o_end))
00254     {
00255       *o_begin++ = *i_begin++;
00256     }
00257 
00258     return o_begin;
00259   }
00260 
00261   //***************************************************************************
00262   /// copy_n (Random input iterators)
00263   ///\ingroup algorithm
00264   ///<a href="http://en.cppreference.com/w/cpp/algorithm/copy_n"></a>
00265   //***************************************************************************
00266   template <typename TInputIterator,
00267             typename TSize,
00268             typename TOutputIterator>
00269   typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value, TOutputIterator>::type
00270    copy_n(TInputIterator  i_begin,
00271           TSize           n,
00272           TOutputIterator o_begin)
00273   {
00274     return std::copy(i_begin, i_begin + n, o_begin);
00275   }
00276 
00277   //***************************************************************************
00278   /// copy_n (Non-random input iterators)
00279   ///\ingroup algorithm
00280   ///<a href="http://en.cppreference.com/w/cpp/algorithm/copy_n"></a>
00281   //***************************************************************************
00282   template <typename TInputIterator,
00283             typename TSize,
00284             typename TOutputIterator>
00285   typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value, TOutputIterator>::type
00286    copy_n(TInputIterator  i_begin,
00287           TSize           n,
00288           TOutputIterator o_begin)
00289   {
00290     while (n-- > 0)
00291     {
00292       *o_begin++ = *i_begin++;
00293     }
00294 
00295     return o_begin;
00296   }
00297 
00298   //***************************************************************************
00299   /// copy_n
00300   /// A form of copy_n where the smallest of the two ranges is used.
00301   ///\ingroup algorithm
00302   //***************************************************************************
00303   template <typename TInputIterator,
00304             typename TSize,
00305             typename TOutputIterator>
00306   TOutputIterator copy_n(TInputIterator  i_begin,
00307                          TSize           n,
00308                          TOutputIterator o_begin,
00309                          TOutputIterator o_end)
00310   {
00311     while ((n-- > 0) && (o_begin != o_end))
00312     {
00313       *o_begin++ = *i_begin++;
00314     }
00315 
00316     return o_begin;
00317   }
00318 
00319   //***************************************************************************
00320   /// copy_n
00321   /// A form of copy_n where the smallest of the two ranges is used.
00322   ///\ingroup algorithm
00323   //***************************************************************************
00324   template <typename TInputIterator,
00325             typename TSize1,
00326             typename TOutputIterator,
00327             typename TSize2>
00328   TOutputIterator copy_n(TInputIterator  i_begin,
00329                          TSize1          n1,
00330                          TOutputIterator o_begin,
00331                          TSize2          n2)
00332   {
00333     while ((n1-- > 0) && (n2-- > 0))
00334     {
00335       *o_begin++ = *i_begin++;
00336     }
00337 
00338     return o_begin;
00339   }
00340 
00341   //***************************************************************************
00342   /// copy_if
00343   ///\ingroup algorithm
00344   ///<a href="http://en.cppreference.com/w/cpp/algorithm/copy"></a>
00345   //***************************************************************************
00346   template <typename TIterator,
00347             typename TOutputIterator,
00348             typename TUnaryPredicate>
00349   TOutputIterator copy_if(TIterator       begin,
00350                           TIterator       end,
00351                           TOutputIterator out,
00352                           TUnaryPredicate predicate)
00353   {
00354     while (begin != end)
00355     {
00356       if (predicate(*begin))
00357       {
00358         *out++ = *begin;
00359       }
00360 
00361       ++begin;
00362     }
00363 
00364     return out;
00365   }
00366 
00367   //***************************************************************************
00368   /// copy_if
00369   /// A form of copy_if where it terminates when the first end iterator is reached.
00370   /// There is currently no STL equivelent.
00371   ///\ingroup algorithm
00372   //***************************************************************************
00373   template <typename TInputIterator,
00374             typename TOutputIterator,
00375             typename TUnaryPredicate>
00376   TOutputIterator copy_if(TInputIterator  i_begin,
00377                           TInputIterator  i_end,
00378                           TOutputIterator o_begin,
00379                           TOutputIterator o_end,
00380                           TUnaryPredicate predicate)
00381   {
00382     while ((i_begin != i_end) && (o_begin != o_end))
00383     {
00384       if (predicate(*i_begin))
00385       {
00386         *o_begin++ = *i_begin;
00387       }
00388 
00389       ++i_begin;
00390     }
00391 
00392     return o_begin;
00393   }
00394 
00395   //***************************************************************************
00396   /// copy_n_if
00397   /// Combination of copy_n and copy_if.
00398   ///\ingroup algorithm
00399     //***************************************************************************
00400   template <typename TInputIterator,
00401             typename TSize,
00402             typename TOutputIterator,
00403             typename TUnaryPredicate>
00404   TOutputIterator copy_n_if(TInputIterator  i_begin,
00405                             TSize           n,
00406                             TOutputIterator o_begin,
00407                             TUnaryPredicate predicate)
00408   {
00409     while (n-- > 0)
00410     {
00411       if (predicate(*i_begin))
00412       {
00413         *o_begin++ = *i_begin;
00414       }
00415 
00416       ++i_begin;
00417     }
00418 
00419     return o_begin;
00420   }
00421 
00422   //***************************************************************************
00423   /// binary_find
00424   ///\ingroup algorithm
00425   /// Does a binary search and returns an iterator to the value or end if not found.
00426   //***************************************************************************
00427   template <typename TIterator,
00428             typename TValue>
00429     TIterator binary_find(TIterator     begin,
00430                           TIterator     end,
00431                           const TValue& value)
00432   {
00433     TIterator it = std::lower_bound(begin, end, value);
00434 
00435     if ((it == end) || (*it != value))
00436     {
00437       it = end;
00438     }
00439 
00440     return it;
00441   }
00442 
00443   //***************************************************************************
00444   /// binary_find
00445   ///\ingroup algorithm
00446   /// Does a binary search and returns an iterator to the value or end if not found.
00447   //***************************************************************************
00448   template <typename TIterator,
00449             typename TValue,
00450             typename TBinaryPredicate,
00451             typename TBinaryEquality>
00452     TIterator binary_find(TIterator        begin,
00453                           TIterator        end,
00454                           const TValue&    value,
00455                           TBinaryPredicate predicate,
00456                           TBinaryEquality  equality)
00457   {
00458     TIterator it = std::lower_bound(begin, end, value, predicate);
00459 
00460     if ((it == end) || !equality(*it, value))
00461     {
00462       it = end;
00463     }
00464 
00465     return it;
00466   }
00467 
00468   //***************************************************************************
00469   /// find_if_not
00470   ///\ingroup algorithm
00471   ///<a href="http://en.cppreference.com/w/cpp/algorithm/find"></a>
00472   //***************************************************************************
00473   template <typename TIterator,
00474             typename TUnaryPredicate>
00475   TIterator find_if_not(TIterator       begin,
00476                         TIterator       end,
00477                         TUnaryPredicate predicate)
00478   {
00479     while (begin != end)
00480     {
00481       if (!predicate(*begin))
00482       {
00483         return begin;
00484       }
00485 
00486       ++begin;
00487     }
00488 
00489     return end;
00490   }
00491 
00492   //***************************************************************************
00493   /// all_of
00494   ///\ingroup algorithm
00495   ///<a href="http://en.cppreference.com/w/cpp/algorithm/all_any_none_of"></a>
00496   //***************************************************************************
00497   template <typename TIterator,
00498             typename TUnaryPredicate>
00499   bool all_of(TIterator       begin,
00500               TIterator       end,
00501               TUnaryPredicate predicate)
00502   {
00503     return etl::find_if_not(begin, end, predicate) == end;
00504   }
00505 
00506   //***************************************************************************
00507   /// any_of
00508   ///\ingroup algorithm
00509   ///<a href="http://en.cppreference.com/w/cpp/algorithm/all_any_none_of"></a>
00510   //***************************************************************************
00511   template <typename TIterator,
00512             typename TUnaryPredicate>
00513   bool any_of(TIterator       begin,
00514               TIterator       end,
00515               TUnaryPredicate predicate)
00516   {
00517     return std::find_if(begin, end, predicate) != end;
00518   }
00519 
00520   //***************************************************************************
00521   /// none_of
00522   ///\ingroup algorithm
00523   ///<a href="http://en.cppreference.com/w/cpp/algorithm/all_any_none_of"></a>
00524   //***************************************************************************
00525   template <typename TIterator,
00526             typename TUnaryPredicate>
00527   bool none_of(TIterator       begin,
00528                TIterator       end,
00529                TUnaryPredicate predicate)
00530   {
00531     return std::find_if(begin, end, predicate) == end;
00532   }
00533 
00534   //***************************************************************************
00535   /// is_permutation
00536   ///\ingroup algorithm
00537   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_permutation"></a>
00538   //***************************************************************************
00539   template <typename TIterator1,
00540             typename TIterator2>
00541   bool is_permutation(TIterator1 begin1,
00542                       TIterator1 end1,
00543                       TIterator2 begin2)
00544   {
00545     if (begin1 != end1)
00546     {
00547       TIterator2 end2 = begin2;
00548 
00549       std::advance(end2, std::distance(begin1, end1));
00550 
00551       for (TIterator1 i = begin1; i != end1; ++i)
00552       {
00553         if (i == std::find(begin1, i, *i))
00554         {
00555           int32_t n = std::count(begin2, end2, *i);
00556 
00557           if (n == 0 || std::count(i, end1, *i) != n)
00558           {
00559             return false;
00560           }
00561         }
00562       }
00563     }
00564 
00565     return true;
00566   }
00567 
00568   //***************************************************************************
00569   /// is_permutation
00570   ///\ingroup algorithm
00571   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_permutation"></a>
00572   //***************************************************************************
00573   template <typename TIterator1,
00574             typename TIterator2>
00575   bool is_permutation(TIterator1 begin1,
00576                       TIterator1 end1,
00577                       TIterator2 begin2,
00578                       TIterator2 end2)
00579   {
00580     if (begin1 != end1)
00581     {
00582       for (TIterator1 i = begin1; i != end1; ++i)
00583       {
00584         if (i == std::find(begin1, i, *i))
00585         {
00586           int32_t n = std::count(begin2, end2, *i);
00587 
00588           if (n == 0 || std::count(i, end1, *i) != n)
00589           {
00590             return false;
00591           }
00592         }
00593       }
00594     }
00595 
00596     return true;
00597   }
00598 
00599   //***************************************************************************
00600   /// is_permutation
00601   ///\ingroup algorithm
00602   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_permutation"></a>
00603   //***************************************************************************
00604   template <typename TIterator1,
00605             typename TIterator2,
00606             typename TBinaryPredicate>
00607   bool is_permutation(TIterator1       begin1,
00608                       TIterator1       end1,
00609                       TIterator2       begin2,
00610                       TBinaryPredicate predicate)
00611   {
00612     if (begin1 != end1)
00613     {
00614       TIterator2 end2 = begin2;
00615 
00616       std::advance(end2, std::distance(begin1, end1));
00617 
00618       for (TIterator1 i = begin1; i != end1; ++i)
00619       {
00620         if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
00621         {
00622           int32_t n = std::count(begin2, end2, *i);
00623 
00624           if (n == 0 || std::count(i, end1, *i) != n)
00625           {
00626             return false;
00627           }
00628         }
00629       }
00630     }
00631 
00632     return true;
00633   }
00634 
00635   //***************************************************************************
00636   /// is_permutation
00637   ///\ingroup algorithm
00638   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_permutation"></a>
00639   //***************************************************************************
00640   template <typename TIterator1,
00641             typename TIterator2,
00642             typename TBinaryPredicate>
00643   bool is_permutation(TIterator1       begin1,
00644                       TIterator1       end1,
00645                       TIterator2       begin2,
00646                       TIterator2       end2,
00647                       TBinaryPredicate predicate)
00648   {
00649     if (begin1 != end1)
00650     {
00651       for (TIterator1 i = begin1; i != end1; ++i)
00652       {
00653         if (i == std::find_if(begin1, i, std::bind1st(predicate, *i)))
00654         {
00655           int32_t n = std::count(begin2, end2, *i);
00656 
00657           if (n == 0 || std::count(i, end1, *i) != n)
00658           {
00659             return false;
00660           }
00661         }
00662       }
00663     }
00664 
00665     return true;
00666   }
00667 
00668   //***************************************************************************
00669   /// is_partitioned
00670   ///\ingroup algorithm
00671   ///<a href="http://en.cppreference.com/w/cpp/algorithm/is_partitioned"></a>
00672   //***************************************************************************
00673   template <typename TIterator,
00674             typename TUnaryPredicate>
00675   bool is_partitioned(TIterator       begin,
00676                       TIterator       end,
00677                       TUnaryPredicate predicate)
00678   {
00679     while (begin != end)
00680     {
00681       if (!predicate(*begin++))
00682       {
00683         break;
00684       }
00685     }
00686 
00687     while (begin != end)
00688     {
00689       if (predicate(*begin++))
00690       {
00691         return false;
00692       }
00693     }
00694 
00695     return true;
00696   }
00697 
00698   //***************************************************************************
00699   /// partition_point
00700   ///<a href="http://en.cppreference.com/w/cpp/algorithm/partition_point"></a>
00701   ///\ingroup algorithm
00702   //***************************************************************************
00703   template <typename TIterator,
00704             typename TUnaryPredicate>
00705   TIterator partition_point(TIterator       begin,
00706                             TIterator       end,
00707                             TUnaryPredicate predicate)
00708   {
00709     while (begin != end)
00710     {
00711       if (!predicate(*begin))
00712       {
00713         return begin;
00714       }
00715 
00716       ++begin;
00717     }
00718 
00719     return begin;
00720   }
00721 
00722   //***************************************************************************
00723   /// Copies the elements from the range (begin, end) to two different ranges
00724   /// depending on the value returned by the predicate.<br>
00725   ///<a href="http://en.cppreference.com/w/cpp/algorithm/partition_copy"></a>
00726   ///\ingroup algorithm
00727   //***************************************************************************
00728   template <typename TSource,
00729             typename TDestinationTrue,
00730             typename TDestinationFalse,
00731             typename TUnaryPredicate>
00732   std::pair<TDestinationTrue, TDestinationFalse> partition_copy(TSource           begin,
00733                                                                 TSource           end,
00734                                                                 TDestinationTrue  destination_true,
00735                                                                 TDestinationFalse destination_false,
00736                                                                 TUnaryPredicate   predicate)
00737   {
00738     while (begin != end)
00739     {
00740       if (predicate(*begin))
00741       {
00742         *destination_true++ = *begin++;
00743       }
00744       else
00745       {
00746         *destination_false++ = *begin++;
00747       }
00748     }
00749 
00750     return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
00751   }
00752 
00753   //***************************************************************************
00754   /// Like std::for_each but applies a predicate before calling the function.
00755   ///\ingroup algorithm
00756   //***************************************************************************
00757   template <typename TIterator,
00758             typename TUnaryFunction,
00759             typename TUnaryPredicate>
00760   TUnaryFunction for_each_if(TIterator       begin,
00761                              const TIterator end,
00762                              TUnaryFunction  function,
00763                              TUnaryPredicate predicate)
00764   {
00765     while (begin != end)
00766     {
00767       if (predicate(*begin))
00768       {
00769         function(*begin);
00770       }
00771 
00772       ++begin;
00773     }
00774 
00775     return function;
00776   }
00777 
00778     //***************************************************************************
00779   /// Like std::for_each but for 'n' iterations.
00780   ///\ingroup algorithm
00781   //***************************************************************************
00782   template <typename TIterator,
00783             typename TSize,
00784             typename TUnaryFunction>
00785   TIterator for_each_n(TIterator       begin,
00786                        TSize           n,
00787                        TUnaryFunction  function)
00788   {
00789     while (n-- > 0)
00790     {
00791       function(*begin++);
00792     }
00793 
00794     return begin;
00795   }
00796 
00797   //***************************************************************************
00798   /// Like std::for_each but applies a predicate before calling the function, for 'n' iterations
00799   ///\ingroup algorithm
00800   //***************************************************************************
00801   template <typename TIterator,
00802             typename TSize,
00803             typename TUnaryFunction,
00804             typename TUnaryPredicate>
00805   TIterator for_each_n_if(TIterator       begin,
00806                           TSize           n,
00807                           TUnaryFunction  function,
00808                           TUnaryPredicate predicate)
00809   {
00810     while (n-- > 0)
00811     {
00812       if (predicate(*begin))
00813       {
00814         function(*begin);
00815       }
00816 
00817       ++begin;
00818     }
00819 
00820     return begin;
00821   }
00822 
00823   //***************************************************************************
00824   /// A form of std::transform where the transform returns when the first range
00825   /// end is reached.
00826   /// There is currently no STL equivalent.
00827   ///\ingroup algorithm
00828   //***************************************************************************
00829   template <typename TInputIterator,
00830             typename TOutputIterator,
00831             typename TUnaryFunction>
00832   void transform(TInputIterator  i_begin,
00833                  TInputIterator  i_end,
00834                  TOutputIterator o_begin,
00835                  TOutputIterator o_end,
00836                  TUnaryFunction  function)
00837   {
00838     while ((i_begin != i_end) && (o_begin != o_end))
00839     {
00840       *o_begin++ = function(*i_begin++);
00841     }
00842   }
00843 
00844   //***************************************************************************
00845   /// Transform 'n' items.
00846   /// Random iterators.
00847   /// There is currently no STL equivalent.
00848   ///\ingroup algorithm
00849   //***************************************************************************
00850   template <typename TInputIterator,
00851             typename TSize,
00852             typename TOutputIterator,
00853             typename TUnaryFunction>
00854   typename etl::enable_if<etl::is_random_iterator<TInputIterator>::value, void>::type
00855    transform_n(TInputIterator  i_begin,
00856                TSize           n,
00857                TOutputIterator o_begin,
00858                TUnaryFunction  function)
00859   {
00860     std::transform(i_begin, i_begin + n, o_begin, function);
00861   }
00862 
00863   //***************************************************************************
00864   /// Transform 'n' items from two ranges.
00865   /// Random iterators.
00866   /// There is currently no STL equivalent.
00867   ///\ingroup algorithm
00868   //***************************************************************************
00869   template <typename TInputIterator1,
00870             typename TInputIterator2,
00871             typename TSize,
00872             typename TOutputIterator,
00873             typename TBinaryFunction>
00874   typename etl::enable_if<etl::is_random_iterator<TInputIterator1>::value &&
00875                           etl::is_random_iterator<TInputIterator2>::value, void>::type
00876    transform_n(TInputIterator1 i_begin1,
00877                TInputIterator2 i_begin2,
00878                TSize           n,
00879                TOutputIterator o_begin,
00880                TBinaryFunction function)
00881   {
00882     std::transform(i_begin1, i_begin1 + n, i_begin2, o_begin, function);
00883   }
00884 
00885   //***************************************************************************
00886   /// Transform 'n' items.
00887   /// Non-random iterators.
00888   /// There is currently no STL equivalent.
00889   ///\ingroup algorithm
00890   //***************************************************************************
00891   template <typename TInputIterator,
00892             typename TSize,
00893             typename TOutputIterator,
00894             typename TUnaryFunction>
00895   typename etl::enable_if<!etl::is_random_iterator<TInputIterator>::value, void>::type
00896    transform_n(TInputIterator  i_begin,
00897                TSize           n,
00898                TOutputIterator o_begin,
00899                TUnaryFunction  function)
00900   {
00901     while (n > 0)
00902     {
00903       *o_begin++ = function(*i_begin++);
00904       --n;
00905     }
00906   }
00907 
00908   //***************************************************************************
00909   /// Transform 'n' items from two ranges.
00910   /// Non-random iterators.
00911   /// There is currently no STL equivalent.
00912   ///\ingroup algorithm
00913   //***************************************************************************
00914   template <typename TInputIterator1,
00915             typename TInputIterator2,
00916             typename TSize,
00917             typename TOutputIterator,
00918             typename TBinaryFunction>
00919   typename etl::enable_if<!etl::is_random_iterator<TInputIterator1>::value ||
00920                           !etl::is_random_iterator<TInputIterator2>::value, void>::type
00921    transform_n(TInputIterator1 i_begin1,
00922                TInputIterator2 i_begin2,
00923                TSize           n,
00924                TOutputIterator o_begin,
00925                TBinaryFunction function)
00926   {
00927     while (n > 0)
00928     {
00929       *o_begin++ = function(*i_begin1++, *i_begin2++);
00930       --n;
00931     }
00932   }
00933 
00934   //***************************************************************************
00935   /// Like std::transform but applies a predicate before calling the function.
00936   ///\ingroup algorithm
00937   //***************************************************************************
00938   template <typename TInputIterator,
00939             typename TOutputIterator,
00940             typename TUnaryFunction,
00941             typename TUnaryPredicate>
00942   TOutputIterator transform_if(TInputIterator       i_begin,
00943                                const TInputIterator i_end,
00944                                TOutputIterator      o_begin,
00945                                TUnaryFunction       function,
00946                                TUnaryPredicate      predicate)
00947   {
00948     while (i_begin != i_end)
00949     {
00950       if (predicate(*i_begin))
00951       {
00952         *o_begin++ = function(*i_begin);
00953       }
00954 
00955       ++i_begin;
00956     }
00957 
00958     return o_begin;
00959   }
00960 
00961   //***************************************************************************
00962   /// Like etl::transform_if but inputs from two ranges.
00963   ///\ingroup algorithm
00964   //***************************************************************************
00965   template <typename TInputIterator1,
00966             typename TInputIterator2,
00967             typename TOutputIterator,
00968             typename TBinaryFunction,
00969             typename TBinaryPredicate>
00970   TOutputIterator transform_if(TInputIterator1       i_begin1,
00971                                const TInputIterator1 i_end1,
00972                                TInputIterator2       i_begin2,
00973                                TOutputIterator       o_begin,
00974                                TBinaryFunction       function,
00975                                TBinaryPredicate      predicate)
00976   {
00977     while (i_begin1 != i_end1)
00978     {
00979       if (predicate(*i_begin1, *i_begin2))
00980       {
00981         *o_begin++ = function(*i_begin1, *i_begin2);
00982       }
00983 
00984       ++i_begin1;
00985       ++i_begin2;
00986     }
00987 
00988     return o_begin;
00989   }
00990 
00991   //***************************************************************************
00992   /// Like std::transform_if, for 'n' items.
00993   ///\ingroup algorithm
00994   //***************************************************************************
00995   template <typename TInputIterator,
00996             typename TSize,
00997             typename TOutputIterator,
00998             typename TUnaryFunction,
00999             typename TUnaryPredicate>
01000   TOutputIterator transform_n_if(TInputIterator  i_begin,
01001                                  TSize           n,
01002                                  TOutputIterator o_begin,
01003                                  TUnaryFunction  function,
01004                                  TUnaryPredicate predicate)
01005   {
01006     while (n-- > 0)
01007     {
01008       if (predicate(*i_begin))
01009       {
01010         *o_begin++ = function(*i_begin);
01011       }
01012 
01013       ++i_begin;
01014     }
01015 
01016     return o_begin;
01017   }
01018 
01019   //***************************************************************************
01020   /// Like etl::transform_if but inputs from two ranges for 'n' items.
01021   ///\ingroup algorithm
01022   //***************************************************************************
01023   template <typename TInputIterator1,
01024             typename TInputIterator2,
01025             typename TSize,
01026             typename TOutputIterator,
01027             typename TBinaryFunction,
01028             typename TBinaryPredicate>
01029   TOutputIterator transform_n_if(TInputIterator1  i_begin1,
01030                                  TInputIterator2  i_begin2,
01031                                  TSize            n,
01032                                  TOutputIterator  o_begin,
01033                                  TBinaryFunction  function,
01034                                  TBinaryPredicate predicate)
01035   {
01036     while (n-- > 0)
01037     {
01038       if (predicate(*i_begin1, *i_begin2))
01039       {
01040         *o_begin++ = function(*i_begin1, *i_begin2);
01041       }
01042 
01043       ++i_begin1;
01044       ++i_begin2;
01045     }
01046 
01047     return o_begin;
01048   }
01049 
01050   //***************************************************************************
01051   /// Transforms the elements from the range (begin, end) to two different ranges
01052   /// depending on the value returned by the predicate.<br>
01053   ///\ingroup algorithm
01054   //***************************************************************************
01055   template <typename TSource, typename TDestinationTrue, typename TDestinationFalse,
01056             typename TUnaryFunctionTrue, typename TUnaryFunctionFalse,
01057             typename TUnaryPredicate>
01058   std::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource             begin,
01059                                                                      TSource             end,
01060                                                                      TDestinationTrue    destination_true,
01061                                                                      TDestinationFalse   destination_false,
01062                                                                      TUnaryFunctionTrue  function_true,
01063                                                                      TUnaryFunctionFalse function_false,
01064                                                                      TUnaryPredicate     predicate)
01065   {
01066     while (begin != end)
01067     {
01068       if (predicate(*begin))
01069       {
01070         *destination_true++ = function_true(*begin++);
01071       }
01072       else
01073       {
01074         *destination_false++ = function_false(*begin++);
01075       }
01076     }
01077 
01078     return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
01079   }
01080 
01081   //***************************************************************************
01082   /// Transforms the elements from the ranges (begin1, end1) & (begin2)
01083   /// to two different ranges depending on the value returned by the predicate.
01084   ///\ingroup algorithm
01085   //***************************************************************************
01086   template <typename TSource1,
01087             typename TSource2,
01088             typename TDestinationTrue,
01089             typename TDestinationFalse,
01090             typename TBinaryFunctionTrue,
01091             typename TBinaryFunctionFalse,
01092             typename TBinaryPredicate>
01093   std::pair<TDestinationTrue, TDestinationFalse> partition_transform(TSource1             begin1,
01094                                                                      TSource1             end1,
01095                                                                      TSource2             begin2,
01096                                                                      TDestinationTrue     destination_true,
01097                                                                      TDestinationFalse    destination_false,
01098                                                                      TBinaryFunctionTrue  function_true,
01099                                                                      TBinaryFunctionFalse function_false,
01100                                                                      TBinaryPredicate     predicate)
01101   {
01102     while (begin1 != end1)
01103     {
01104       if (predicate(*begin1, *begin2))
01105       {
01106         *destination_true++ = function_true(*begin1++, *begin2++);
01107       }
01108       else
01109       {
01110         *destination_false++ = function_false(*begin1++, *begin2++);
01111       }
01112     }
01113 
01114     return std::pair<TDestinationTrue, TDestinationFalse>(destination_true, destination_false);
01115   }
01116 }
01117 
01118 #endif
01119 
01120