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