1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Andreas Gogol-Döring <andreas.doering@mdc-berlin.de>
33 // ==========================================================================
34 // Math-related utility routines.
35 // ==========================================================================
36
37 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_MATH_FUNCTIONS_H_
38 #define SEQAN_INCLUDE_SEQAN_BASIC_MATH_FUNCTIONS_H_
39
40 namespace seqan {
41
42 // ============================================================================
43 // Forwards
44 // ============================================================================
45
46 // ============================================================================
47 // Tags, Classes, Enums
48 // ============================================================================
49
50 // ============================================================================
51 // Metafunctions
52 // ============================================================================
53
54 // ============================================================================
55 // Functions
56 // ============================================================================
57
58 // ----------------------------------------------------------------------------
59 // Function _intPow()
60 // ----------------------------------------------------------------------------
61
62 // TODO(holtgrew): Document and make public.
63
64 template <typename TValue, typename TExponent>
_intPow(TValue a,TExponent b)65 inline TValue _intPow(TValue a, TExponent b)
66 {
67 TValue ret = 1;
68 while (b != 0) {
69 if (b & 1) ret *= a;
70 a *= a;
71 b >>= 1;
72 }
73 return ret;
74 }
75
76 // ----------------------------------------------------------------------------
77 // Function log2()
78 // ----------------------------------------------------------------------------
79
80 /*!
81 * @fn log2
82 * @headerfile <seqan/basic.h>
83 * @brief Computes floored logarithm of base 2 for integer types
84 *
85 * @signature unsigned log2(i);
86 *
87 * @param[in] i An integer type.
88 *
89 * @return unsigned The largest integer smaller or equal than the logarithm of <tt>i</tt>.
90 */
91
92 // TODO(holtgrew): Should this maybe called log2floor for consistency with Log2Floor<>::VALUE?
93
94 template <int BITS_MAX>
95 struct Log2Impl_
96 {
97 template <typename T>
98 static inline unsigned int
log2Log2Impl_99 log2(T val, unsigned int offset)
100 {
101 unsigned int val2 = val >> (BITS_MAX / 2);
102 if (val2)
103 {
104 val = val2;
105 offset += BITS_MAX / 2;
106 }
107 return Log2Impl_<BITS_MAX / 2>::log2(val, offset);
108 }
109 };
110
111 template <>
112 struct Log2Impl_<1>
113 {
114 template <typename T>
115 static inline unsigned int
116 log2(T /*val*/, unsigned int offset)
117 {
118 return offset;
119 }
120 };
121
122 template <typename T>
123 inline unsigned int
124 log2(T val)
125 {
126 enum
127 {
128 // BITS_PER_VALUE = BitsPerValue<T>::VALUE // TODO(holtgrew): portable bits-per-char!
129 BITS_PER_VALUE = sizeof(T) * 8
130 };
131
132 return Log2Impl_<BITS_PER_VALUE>::log2(val, 0);
133 }
134
135 // ----------------------------------------------------------------------------
136 // Function _min()
137 // ----------------------------------------------------------------------------
138
139 // TODO(holtgrew): Subject to removal. http://trac.mi.fu-berlin.de/seqan/ticket/855
140
141 // to avoid conflicts with non-standard macros and namespaces
142 // we define our own Min/Max functions
143
144 template<typename Tx_>
145 inline
146 const Tx_& _min(const Tx_& _Left, const Tx_& Right_)
147 { // return smaller of _Left and Right_
148 if (_Left < Right_)
149 return _Left;
150 else
151 return Right_;
152 }
153
154 template<typename Tx_, typename Ty_>
155 inline
156 Tx_ _min(const Tx_& _Left, const Ty_& Right_)
157 { // return smaller of _Left and Right_
158 return (Right_ < _Left ? Right_ : _Left);
159 }
160
161 // ----------------------------------------------------------------------------
162 // Function _max()
163 // ----------------------------------------------------------------------------
164
165 // TODO(holtgrew): Subject to removal. http://trac.mi.fu-berlin.de/seqan/ticket/855
166
167 // to avoid conflicts with non-standard macros and namespaces
168 // we define our own Min/Max functions
169
170 template<typename Ty_>
171 inline Ty_ const &
172 _max(const Ty_& _Left, const Ty_& Right_)
173 { // return larger of _Left and Right_
174 if (_Left < Right_)
175 return Right_;
176 else
177 return _Left;
178 }
179
180 template<typename Tx_, typename Ty_>
181 inline Tx_
182 _max(const Tx_& _Left, const Ty_& Right_)
183 { // return smaller of _Left and Right_
184 return (Right_ < _Left ? _Left : Right_);
185 }
186
187 // ----------------------------------------------------------------------------
188 // Function _abs()
189 // ----------------------------------------------------------------------------
190
191 // TODO(holtgrew): Make public, document. This is here since cmath's abs is only defined for floats/doubles.
192
193 template <typename T>
194 inline
195 T _abs(T const & x)
196 {
197 if (x < static_cast<T>(0))
198 return -x;
199 else
200 return x;
201 }
202
203 } // namespace seqan
204
205 #endif // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_MATH_FUNCTIONS_H_
206
207