1 /**
2  * Number stuff
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <ae@cy.md>
12  */
13 
14 module ae.utils.math;
15 
16 /// Return `b` bound by `a` and `c` (i.e., `min(max(a, b), c)`).
17 typeof(Ta+Tb+Tc) bound(Ta, Tb, Tc)(Ta a, Tb b, Tc c) { return a<b?b:a>c?c:a; }
18 
19 /// Return true if `a <= point <= b`.
20 bool between(T)(T point, T a, T b) { return a <= point && point <= b; }
21 
22 /// Return `x*x`.
23 auto sqr(T)(T x) { return x*x; }
24 
25 /// If `x > y`, swaps `x` and `y`.
26 void sort2(T)(ref T x, ref T y) { if (x > y) { T z=x; x=y; y=z; } }
27 
28 /// Performs linear interpolation.
29 /// Returns the point between `low` and `high` corresponding to the point where `r` is between `rLow` and `rHigh`.
30 T itpl(T, U)(T low, T high, U r, U rLow, U rHigh)
31 {
32 	import std.traits : Signed;
33 	return cast(T)(low + (cast(Signed!T)high-cast(Signed!T)low) * (cast(Signed!U)r - cast(Signed!U)rLow) / (cast(Signed!U)rHigh - cast(Signed!U)rLow));
34 }
35 
36 /// Returns the sign of `x`, i.e,
37 /// `-1` if `x < 0`, `+1` if `x > 0`,, or `0` if `x == 0`.
38 byte sign(T)(T x) { return x<0 ? -1 : x>0 ? 1 : 0; }
39 
40 /// Returns the logical value of `sign(b - a)`
41 /// (but does not actually subtract to avoid overflow).
42 int compare(T)(T a, T b)
43 {
44 	return a<b ? -1 : a>b ? 1 : 0;
45 }
46 
47 /// Apply a binary operation consecutively to `args`.
48 auto op(string OP, T...)(T args)
49 {
50 	auto result = args[0];
51 	foreach (arg; args[1..$])
52 		mixin("result" ~ OP ~ "=arg;");
53 	return result;
54 }
55 
56 /// Sums `args`.
57 auto sum(T...)(T args) { return op!"+"(args); }
58 /// Averages `args`.
59 auto average(T...)(T args) { return sum(args) / args.length; }
60 
61 /// Wraps a D binary operator into a function.
62 template binary(string op)
63 {
64 	auto binary(A, B)(auto ref A a, auto ref B b) { return mixin(`a` ~ op ~ `b`); }
65 }
66 /// Aliases of D binary operators as functions. Usable in UFCS.
67 alias eq = binary!"==";
68 alias ne = binary!"!="; /// ditto
69 alias lt = binary!"<" ; /// ditto
70 alias gt = binary!">" ; /// ditto
71 alias le = binary!"<="; /// ditto
72 alias ge = binary!">="; /// ditto
73 
74 /// Length of intersection of two segments on a line,
75 /// or 0 if they do not intersect.
76 T rangeIntersection(T)(T a0, T a1, T b0, T b1)
77 {
78 	import std.algorithm.comparison : min, max;
79 
80 	auto x0 = max(a0, b0);
81 	auto x1 = min(a1, b1);
82 	return x0 < x1 ? x1 - x0 : 0;
83 }
84 
85 unittest
86 {
87 	assert(rangeIntersection(0, 2, 1, 3) == 1);
88 	assert(rangeIntersection(0, 1, 2, 3) == 0);
89 }
90 
91 /// Wraps a D unary operator into a function.
92 /// Does not do integer promotion.
93 template unary(char op)
94 {
95 	T unary(T)(T value)
96 	{
97 		// Silence DMD 2.078.0 warning about integer promotion rules
98 		// https://dlang.org/changelog/2.078.0.html#fix16997
99 		static if ((op == '-' || op == '+' || op == '~') && is(T : int))
100 			alias CastT = int;
101 		else
102 			alias CastT = T;
103 		return mixin(`cast(T)` ~ op ~ `cast(CastT)value`);
104 	}
105 }
106 
107 /// Like the ~ operator, but without int-promotion.
108 alias flipBits = unary!'~';
109 
110 unittest
111 {
112 	ubyte b = 0x80;
113 	auto b2 = b.flipBits;
114 	assert(b2 == 0x7F);
115 	static assert(is(typeof(b2) == ubyte));
116 }
117 
118 /// Swap the byte order in an integer value.
119 T swapBytes(T)(T b)
120 if (is(T : uint))
121 {
122 	import core.bitop : bswap;
123 	static if (b.sizeof == 1)
124 		return b;
125 	else
126 	static if (b.sizeof == 2)
127 		return cast(T)((b >> 8) | (b << 8));
128 	else
129 	static if (b.sizeof == 4)
130 		return bswap(b);
131 	else
132 		static assert(false, "Don't know how to bswap " ~ T.stringof);
133 }
134 
135 /// True if `x` is some power of two, including `1`.
136 bool isPowerOfTwo(T)(T x) { return (x & (x-1)) == 0; }
137 
138 /// Round up `x` to the next power of two.
139 /// If `x` is already a power of two, returns `x`.
140 T roundUpToPowerOfTwo(T)(T x) { return nextPowerOfTwo(x-1); }
141 
142 /// Return the next power of two after `x`, not including it.
143 T nextPowerOfTwo(T)(T x)
144 {
145 	x |= x >>  1;
146 	x |= x >>  2;
147 	x |= x >>  4;
148 	static if (T.sizeof > 1)
149 		x |= x >>  8;
150 	static if (T.sizeof > 2)
151 		x |= x >> 16;
152 	static if (T.sizeof > 4)
153 		x |= x >> 32;
154 	return x + 1;
155 }
156 
157 /// Integer log2.
158 ubyte ilog2(T)(T n)
159 {
160 	ubyte result = 0;
161 	while (n >>= 1)
162 		result++;
163 	return result;
164 }
165 
166 unittest
167 {
168 	assert(ilog2(0) == 0);
169 	assert(ilog2(1) == 0);
170 	assert(ilog2(2) == 1);
171 	assert(ilog2(3) == 1);
172 	assert(ilog2(4) == 2);
173 }
174 
175 /// Returns the number of bits needed to
176 /// store a number up to n (inclusive).
177 ubyte bitsFor(T)(T n)
178 {
179 	return cast(ubyte)(ilog2(n)+1);
180 }
181 
182 unittest
183 {
184 	assert(bitsFor( int.max) == 31);
185 	assert(bitsFor(uint.max) == 32);
186 }
187 
188 /// Get the smallest built-in unsigned integer type
189 /// that can store this many bits of data.
190 template TypeForBits(uint bits)
191 {
192 	///
193 	static if (bits <= 8)
194 		alias TypeForBits = ubyte;
195 	else
196 	static if (bits <= 16)
197 		alias TypeForBits = ushort;
198 	else
199 	static if (bits <= 32)
200 		alias TypeForBits = uint;
201 	else
202 	static if (bits <= 64)
203 		alias TypeForBits = ulong;
204 	else
205 		static assert(false, "No integer type big enough for " ~ bits.stringof ~ " bits");
206 }
207 
208 static assert(is(TypeForBits!7 == ubyte));
209 static assert(is(TypeForBits!8 == ubyte));
210 static assert(is(TypeForBits!9 == ushort));
211 static assert(is(TypeForBits!64 == ulong));
212 static assert(!is(TypeForBits!65));
213 
214 /// Saturate `v` to be the smallest value between itself and `args`.
215 void minimize(T, Args...)(ref T v, Args args)
216 if (is(typeof({ import std.algorithm.comparison : min; v = min(v, args); })))
217 {
218 	import std.algorithm.comparison : min;
219 	v = min(v, args);
220 }
221 
222 /// Saturate `v` to be the largest value between itself and `args`.
223 void maximize(T, Args...)(ref T v, Args args)
224 if (is(typeof({ import std.algorithm.comparison : max; v = max(v, args); })))
225 {
226 	import std.algorithm.comparison : max;
227 	v = max(v, args);
228 }
229 
230 unittest
231 {
232 	int i = 5;
233 	i.minimize(2); assert(i == 2);
234 	i.minimize(5); assert(i == 2);
235 	i.maximize(5); assert(i == 5);
236 	i.maximize(2); assert(i == 5);
237 }