1*e4b17023SJohn Marino // -*- C++ -*- 2*e4b17023SJohn Marino // 3*e4b17023SJohn Marino // Copyright (C) 2010 Free Software Foundation, Inc. 4*e4b17023SJohn Marino // 5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free 6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the 7*e4b17023SJohn Marino // terms of the GNU General Public License as published by the 8*e4b17023SJohn Marino // Free Software Foundation; either version 3, or (at your option) 9*e4b17023SJohn Marino // any later version. 10*e4b17023SJohn Marino // 11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, 12*e4b17023SJohn Marino // but WITHOUT ANY WARRANTY; without even the implied warranty of 13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14*e4b17023SJohn Marino // GNU General Public License for more details. 15*e4b17023SJohn Marino 16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional 17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version 18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation. 19*e4b17023SJohn Marino 20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License along 21*e4b17023SJohn Marino // with this library; see the file COPYING3. If not see 22*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>. 23*e4b17023SJohn Marino 24*e4b17023SJohn Marino /** @file profile/impl/profiler_algos.h 25*e4b17023SJohn Marino * @brief Algorithms used by the profile extension. 26*e4b17023SJohn Marino * 27*e4b17023SJohn Marino * This file is needed to avoid including <algorithm> or <bits/stl_algo.h>. 28*e4b17023SJohn Marino * Including those files would result in recursive includes. 29*e4b17023SJohn Marino * These implementations are oversimplified. In general, efficiency may be 30*e4b17023SJohn Marino * sacrificed to minimize maintenance overhead. 31*e4b17023SJohn Marino */ 32*e4b17023SJohn Marino 33*e4b17023SJohn Marino #ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H 34*e4b17023SJohn Marino #define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1 35*e4b17023SJohn Marino 36*e4b17023SJohn Marino namespace __gnu_profile 37*e4b17023SJohn Marino { 38*e4b17023SJohn Marino /* Helper for __top_n. Insert in sorted vector, but not beyond Nth elem. */ 39*e4b17023SJohn Marino template<typename _Container> 40*e4b17023SJohn Marino void __insert_top_n(_Container & __output,const typename _Container::value_type & __value,typename _Container::size_type __n)41*e4b17023SJohn Marino __insert_top_n(_Container& __output, 42*e4b17023SJohn Marino const typename _Container::value_type& __value, 43*e4b17023SJohn Marino typename _Container::size_type __n) 44*e4b17023SJohn Marino { 45*e4b17023SJohn Marino typename _Container::iterator __it = __output.begin(); 46*e4b17023SJohn Marino typename _Container::size_type __count = 0; 47*e4b17023SJohn Marino 48*e4b17023SJohn Marino // Skip up to N - 1 elements larger than VALUE. 49*e4b17023SJohn Marino // XXX: Could do binary search for random iterators. 50*e4b17023SJohn Marino while (true) 51*e4b17023SJohn Marino { 52*e4b17023SJohn Marino if (__count >= __n) 53*e4b17023SJohn Marino // VALUE is not in top N. 54*e4b17023SJohn Marino return; 55*e4b17023SJohn Marino 56*e4b17023SJohn Marino if (__it == __output.end()) 57*e4b17023SJohn Marino break; 58*e4b17023SJohn Marino 59*e4b17023SJohn Marino if (*__it < __value) 60*e4b17023SJohn Marino break; 61*e4b17023SJohn Marino 62*e4b17023SJohn Marino ++__it; 63*e4b17023SJohn Marino ++__count; 64*e4b17023SJohn Marino } 65*e4b17023SJohn Marino 66*e4b17023SJohn Marino __output.insert(__it, __value); 67*e4b17023SJohn Marino } 68*e4b17023SJohn Marino 69*e4b17023SJohn Marino /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT. */ 70*e4b17023SJohn Marino template<typename _Container> 71*e4b17023SJohn Marino void __top_n(const _Container & __input,_Container & __output,typename _Container::size_type __n)72*e4b17023SJohn Marino __top_n(const _Container& __input, _Container& __output, 73*e4b17023SJohn Marino typename _Container::size_type __n) 74*e4b17023SJohn Marino { 75*e4b17023SJohn Marino __output.clear(); 76*e4b17023SJohn Marino typename _Container::const_iterator __it; 77*e4b17023SJohn Marino for (__it = __input.begin(); __it != __input.end(); ++__it) 78*e4b17023SJohn Marino __insert_top_n(__output, *__it, __n); 79*e4b17023SJohn Marino } 80*e4b17023SJohn Marino 81*e4b17023SJohn Marino /* Simplified clone of std::for_each. */ 82*e4b17023SJohn Marino template<typename _InputIterator, typename _Function> 83*e4b17023SJohn Marino _Function __for_each(_InputIterator __first,_InputIterator __last,_Function __f)84*e4b17023SJohn Marino __for_each(_InputIterator __first, _InputIterator __last, _Function __f) 85*e4b17023SJohn Marino { 86*e4b17023SJohn Marino for (; __first != __last; ++__first) 87*e4b17023SJohn Marino __f(*__first); 88*e4b17023SJohn Marino return __f; 89*e4b17023SJohn Marino } 90*e4b17023SJohn Marino 91*e4b17023SJohn Marino /* Simplified clone of std::remove. */ 92*e4b17023SJohn Marino template<typename _ForwardIterator, typename _Tp> 93*e4b17023SJohn Marino _ForwardIterator __remove(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value)94*e4b17023SJohn Marino __remove(_ForwardIterator __first, _ForwardIterator __last, 95*e4b17023SJohn Marino const _Tp& __value) 96*e4b17023SJohn Marino { 97*e4b17023SJohn Marino if(__first == __last) 98*e4b17023SJohn Marino return __first; 99*e4b17023SJohn Marino _ForwardIterator __result = __first; 100*e4b17023SJohn Marino ++__first; 101*e4b17023SJohn Marino for(; __first != __last; ++__first) 102*e4b17023SJohn Marino if(!(*__first == __value)) 103*e4b17023SJohn Marino { 104*e4b17023SJohn Marino *__result = *__first; 105*e4b17023SJohn Marino ++__result; 106*e4b17023SJohn Marino } 107*e4b17023SJohn Marino return __result; 108*e4b17023SJohn Marino } 109*e4b17023SJohn Marino } // namespace __gnu_profile 110*e4b17023SJohn Marino 111*e4b17023SJohn Marino #endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */ 112