1// Numeric extensions -*- C++ -*-
2
3// Copyright (C) 2002, 2004, 2005 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 2, 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// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30/*
31 *
32 * Copyright (c) 1994
33 * Hewlett-Packard Company
34 *
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation.  Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose.  It is provided "as is" without express or implied warranty.
42 *
43 *
44 * Copyright (c) 1996
45 * Silicon Graphics Computer Systems, Inc.
46 *
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation.  Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose.  It is provided "as is" without express or implied warranty.
54 */
55
56/** @file ext/numeric
57 *  This file is a GNU extension to the Standard C++ Library (possibly
58 *  containing extensions from the HP/SGI STL subset). 
59 */
60
61#ifndef _EXT_NUMERIC
62#define _EXT_NUMERIC 1
63
64#pragma GCC system_header
65
66#include <bits/concept_check.h>
67#include <numeric>
68
69#include <ext/functional> // For identity_element
70
71_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
72
73  // Returns __x ** __n, where __n >= 0.  _Note that "multiplication"
74  // is required to be associative, but not necessarily commutative.
75  template<typename _Tp, typename _Integer, typename _MonoidOperation>
76    _Tp
77    __power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
78    {
79      if (__n == 0)
80	return identity_element(__monoid_op);
81      else
82	{
83	  while ((__n & 1) == 0)
84	    {
85	      __n >>= 1;
86	      __x = __monoid_op(__x, __x);
87	    }
88
89	  _Tp __result = __x;
90	  __n >>= 1;
91	  while (__n != 0)
92	    {
93	      __x = __monoid_op(__x, __x);
94	      if ((__n & 1) != 0)
95		__result = __monoid_op(__result, __x);
96	      __n >>= 1;
97	    }
98	  return __result;
99	}
100    }
101
102  template<typename _Tp, typename _Integer>
103    inline _Tp
104    __power(_Tp __x, _Integer __n)
105    { return __power(__x, __n, std::multiplies<_Tp>()); }
106
107  /**
108   *  This is an SGI extension.
109   *  @ingroup SGIextensions
110   *  @doctodo
111  */
112  // Alias for the internal name __power.  Note that power is an extension,
113  // not part of the C++ standard.
114  template<typename _Tp, typename _Integer, typename _MonoidOperation>
115    inline _Tp
116    power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
117    { return __power(__x, __n, __monoid_op); }
118
119  /**
120   *  This is an SGI extension.
121   *  @ingroup SGIextensions
122   *  @doctodo
123  */
124  template<typename _Tp, typename _Integer>
125    inline _Tp
126    power(_Tp __x, _Integer __n)
127    { return __power(__x, __n); }
128
129  /**
130   *  This is an SGI extension.
131   *  @ingroup SGIextensions
132   *  @doctodo
133  */
134  // iota is not part of the C++ standard.  It is an extension.
135  template<typename _ForwardIter, typename _Tp>
136    void
137    iota(_ForwardIter __first, _ForwardIter __last, _Tp __value)
138    {
139      // concept requirements
140      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
141      __glibcxx_function_requires(_ConvertibleConcept<_Tp,
142	    typename std::iterator_traits<_ForwardIter>::value_type>)
143
144      while (__first != __last)
145	*__first++ = __value++;
146    }
147
148_GLIBCXX_END_NAMESPACE
149
150#endif
151
152