1// -*- C++ -*-
2//
3// Copyright (C) 2010 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 terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 2, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31/** @file profile/impl/profiler_algos.h
32 *  @brief Algorithms used by the profile extension.
33 *
34 *  This file is needed to avoid including <algorithm> or <bits/stl_algo.h>.
35 *  Including those files would result in recursive includes.
36 *  These implementations are oversimplified.  In general, efficiency may be
37 *  sacrificed to minimize maintenance overhead.
38 */
39
40#ifndef _GLIBCXX_PROFILE_PROFILER_ALGOS_H
41#define _GLIBCXX_PROFILE_PROFILER_ALGOS_H 1
42
43namespace __gnu_profile
44{
45  /* Helper for __top_n.  Insert in sorted vector, but not beyond Nth elem.  */
46  template<typename _Container>
47    void
48    __insert_top_n(_Container& __output,
49		   const typename _Container::value_type& __value,
50		   typename _Container::size_type __n)
51    {
52      typename _Container::iterator __it = __output.begin();
53      typename _Container::size_type __count = 0;
54
55      // Skip up to N - 1 elements larger than VALUE.
56      // XXX: Could do binary search for random iterators.
57      while (true)
58	{
59	  if (__count >= __n)
60	    // VALUE is not in top N.
61	    return;
62
63	  if (__it == __output.end())
64	    break;
65
66	  if (*__it < __value)
67	    break;
68
69	  ++__it;
70	  ++__count;
71	}
72
73      __output.insert(__it, __value);
74    }
75
76  /* Copy the top N elements in INPUT, sorted in reverse order, to OUTPUT.  */
77  template<typename _Container>
78    void
79    __top_n(const _Container& __input, _Container& __output,
80	    typename _Container::size_type __n)
81    {
82      __output.clear();
83      typename _Container::const_iterator __it;
84      for (__it = __input.begin(); __it != __input.end(); ++__it)
85	__insert_top_n(__output, *__it, __n);
86    }
87
88  /* Simplified clone of std::for_each.  */
89  template<typename _InputIterator, typename _Function>
90    _Function
91    __for_each(_InputIterator __first, _InputIterator __last, _Function __f)
92    {
93      for (; __first != __last; ++__first)
94	__f(*__first);
95      return __f;
96    }
97
98  /* Simplified clone of std::remove.  */
99  template<typename _ForwardIterator, typename _Tp>
100    _ForwardIterator
101    __remove(_ForwardIterator __first, _ForwardIterator __last,
102	     const _Tp& __value)
103    {
104      if(__first == __last)
105	return __first;
106      _ForwardIterator __result = __first;
107      ++__first;
108      for(; __first != __last; ++__first)
109	if(!(*__first == __value))
110	  {
111	    *__result = *__first;
112	    ++__result;
113	  }
114      return __result;
115    }
116} // namespace __gnu_profile
117
118#endif /* _GLIBCXX_PROFILE_PROFILER_ALGOS_H */
119