nxt.modulo source code

1 module nxt.modulo;
2 
3 import std.traits : isIntegral, isSigned;
4 
5 /** Module type within inclusive value range (0 .. `m`-1).
6 
7     Similar to Ada's modulo type `0 mod m`.
8 
9     See_Also: https://forum.dlang.org/post/hmrpwyqfoxwtywbznbrr@forum.dlang.org
10     See_Also: http://codeforces.com/contest/628/submission/16212299
11 
12     TODO: reuse ideas from bound.d
13 
14     TODO: Add function limit()
15     static if (isPowerOf2!m)
16     {
17     return x & 2^^m - 1;
18     }
19     else
20     {
21     return x % m;
22     }
23 
24     invariant
25     {
26         assert (0 <= x && x < m);
27     }
28 
29     called after opBinary opUnary etc similar to what is done
30     http://codeforces.com/contest/628/submission/16212299
31 
32     TODO: Move to Phobos std.typecons
33  */
34 template Mod(size_t m, T = UnsignedOfModulo!m)
35 if (m >= 1 &&
36     isIntegral!T)
37 {
38     // smallest builtin unsigned integer type that can fit 2^^m
39     alias UI = UnsignedOfModulo!m;
40 
41     static assert(m - 1 <= 2^^(8*T.sizeof) - 1); // if so, check that it matches `s`
42 
43     // `this` uses exactly as many bits as storage type `T`
44     enum exactStorageTypeMatch = m == 2^^(T.sizeof);
45 
46     struct Mod
47     {
48         enum min = 0;
49         enum max = m - 1;
50 
51         /// Construct from `value` of unsigned integer type `UI`.
52         this(U)(U value)
53         if (isIntegral!U)
54         in
55         {
56             static if (m != 2^^(U.sizeof)) // dynamic check only modulo doesn't equal storage precision
57             {
58                 static if (isSigned!U)
59                 {
60                     assert(value >= 0, `value too small`);
61                 }
62                 assert(value < m, `value too large`);
63             }
64         }
65         do
66         {
67             this._value = cast(T)value;
68         }
69 
70         /// Construct from Mod!n, where `n <= m`.
71         this(size_t n, U)(Mod!(n, U) rhs)
72         if (n <= m && isIntegral!U)
73         {
74             this._value = cast(T)rhs._value; // cannot overflow
75         }
76 
77         /// Assign from `value` of unsigned integer type `UI`.
78         auto ref opAssign(U)(U value)
79         if (isIntegral!U)
80         in
81         {
82             static if (m != 2^^(U.sizeof)) // dynamic check only modulo doesn't equal storage precision
83             {
84                 static if (isSigned!U)
85                 {
86                     assert(value >= 0, `value too small`);
87                 }
88                 assert(value < m, `value too large`);
89             }
90         }
91         do
92         {
93             this._value = cast(T)value; // overflow checked in ctor
94         }
95 
96         /// Assign from Mod!n, where `n <= m`.
97         auto ref opAssign(size_t n, U)(Mod!(n, U) rhs)
98         if (n <= m && isIntegral!U)
99         {
100             this._value = cast(T)rhs._value; // cannot overflow
101         }
102 
103         auto ref opOpAssign(string op, U)(U rhs)
104         if ((op == `+` ||
105              op == `-` ||
106              op == `*`) &&
107             isIntegral!U)
108         {
109             mixin(`_value = cast(T)(_value ` ~ op ~ `rhs);`);
110             return this;
111         }
112 
113         auto opUnary(string op, string file = __FILE__, int line = __LINE__)()
114         {
115             static      if (op == `+`)
116             {
117                 return this;
118             }
119             else static if (op == `--`)
120             {
121                 import nxt.math_ex : isPowerOf2;
122                 static if (isPowerOf2(m))
123                 {
124                     _value = (_value - 1) & max; // more efficient
125                 }
126                 else
127                 {
128                     if (_value == min) _value = max; else --_value;
129                 }
130                 return this;
131             }
132             else static if (op == `++`)
133             {
134                 import nxt.math_ex : isPowerOf2;
135                 static if (isPowerOf2(m))
136                 {
137                     _value = (_value + 1) & max; // more efficient
138                 }
139                 else
140                 {
141                     if (_value == max) _value = min; else ++_value;
142                 }
143                 return this;
144             }
145             else
146             {
147                 static assert(`Unsupported unary operator `, op);
148             }
149         }
150 
151         @property size_t _prop() const @safe pure nothrow @nogc { return _value; } // read-only access
152         alias _prop this;
153 
154         private T _value;
155     }
156 }
157 
158 /// Instantiator for `Mod`.
159 auto mod(size_t m, T = UnsignedOfModulo!m)(T value)
160 if (m >= 1)
161 {
162     return Mod!(m)(value);
163 }
164 
165 /** Lookup type representing an unsigned integer in inclusive range (0 .. m - 1).
166  *
167  * TODO: Merge with similar logic in bound.d
168  */
169 private template UnsignedOfModulo(size_t m)
170 {
171     static      if (m - 1 <= ubyte.max)
172     {
173         alias UnsignedOfModulo = ubyte;
174     }
175     else static if (m - 1 <= ushort.max)
176     {
177         alias UnsignedOfModulo = ushort;
178     }
179     else static if (m - 1 <= uint.max)
180     {
181         alias UnsignedOfModulo = uint;
182     }
183     else
184     {
185         alias UnsignedOfModulo = ulong;
186     }
187     // TODO: ucent?
188 }
189 
190 ///
191 @safe pure nothrow @nogc unittest
192 {
193     enum m = 256;
194     Mod!(m, ubyte) ub = cast(ubyte)(m - 1);
195     Mod!(m, uint) ui = cast(ubyte)(m - 1);
196     assert(ub == ui);
197     --ub;
198     assert(ub != ui);
199     ui = ub;
200     assert(ub == ui);
201     --ui;
202     assert(ub != ui);
203     ub = ui;
204     assert(ub == ui);
205 }
206 
207 ///
208 @safe pure nothrow @nogc unittest
209 {
210     static assert(is(typeof(Mod!3(1)) ==
211                      typeof(1.mod!3)));
212 
213     // check size logic
214     static assert(Mod!(ubyte.max + 1).sizeof == 1);
215     static assert(Mod!(ubyte.max + 2).sizeof == 2);
216     static assert(Mod!(ushort.max + 1).sizeof == 2);
217     static assert(Mod!(ushort.max + 2).sizeof == 4);
218     static assert(Mod!(cast(size_t)uint.max + 1).sizeof == 4);
219     static assert(Mod!(cast(size_t)uint.max + 2).sizeof == 8);
220 
221     // assert that storage defaults to packed unsigned integer
222     static assert(is(Mod!(8, ubyte) == Mod!(8)));
223 
224     Mod!(8, ubyte) x = 6;
225     static assert(x.min == 0);
226     static assert(x.max == 7);
227     Mod!(8, ubyte) y = 7;
228     static assert(y.min == 0);
229     static assert(y.max == 7);
230 
231     assert(x < y);
232 
233     y = 5;
234     y = 5L;
235 
236     assert(y < x);
237 
238     assert(y == 5);
239     assert(y != 0);
240 
241     y++;
242     assert(y == 6);
243     assert(++y == y.max);
244     assert(y++ == y.max);
245     assert(y == y.min);
246     assert(--y == y.max);
247     assert(++y == y.min);
248 
249     Mod!(8, uint) ui8 = 7;
250     Mod!(256, ubyte) ub256 = 255;
251     ub256 = ui8;    // can assign to larger modulo from higher storage precision
252 
253     Mod!(258, ushort) ub258 = ub256;
254 
255     // copy construction to smaller modulo is disallowed
256     static assert(!__traits(compiles, { Mod!(255, ubyte) ub255 = ub258; }));
257 
258     auto a = 7.mod!10;
259     auto b = 8.mod!256;
260     auto c = 257.mod!1000;
261 
262     static assert(c.min == 0);
263     static assert(c.max == 999);
264 
265     assert(a < b);
266     assert(a < c);
267 
268     // assignment to larger modulo (super-type/set) is allowed
269     b = a;
270     c = a;
271     c = b;
272 
273     // assignment to smaller modulo (sub-type/set) is disallowed
274     static assert(!__traits(compiles, { a = b; }));
275     static assert(!__traits(compiles, { a = c; }));
276 }
277 
278 ///
279 @safe pure nothrow @nogc unittest
280 {
281     Mod!(256, ubyte) x = 55;
282 
283     x += 200;
284     assert(x == 255);
285 
286     x += 1;
287     assert(x == 0);
288 
289     x -= 4;
290     assert(x == 252);
291 }
292 
293 /// construct from other precision
294 @safe pure nothrow @nogc unittest
295 {
296     enum m = 256;
297     Mod!(m, ubyte) x = 55;
298     Mod!(m, uint) y = x;
299     Mod!(m, ubyte) z = y;
300 }