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) if (isIntegral!U)
53         in
54         {
55             static if (m != 2^^(U.sizeof)) // dynamic check only modulo doesn't equal storage precision
56             {
57                 static if (isSigned!U)
58                     assert(value >= 0, `value too small`);
59                 assert(value < m, `value too large`);
60             }
61         }
62         do
63         {
64             this._value = cast(T)value;
65         }
66 
67         /// Construct from Mod!n, where `n <= m`.
68         this(size_t n, U)(Mod!(n, U) rhs)
69         if (n <= m && isIntegral!U)
70         {
71             this._value = cast(T)rhs._value; // cannot overflow
72         }
73 
74         /// Assign from `value` of unsigned integer type `UI`.
75         auto ref opAssign(U)(U value) if (isIntegral!U)
76         in
77         {
78             static if (m != 2^^(U.sizeof)) // dynamic check only modulo doesn't equal storage precision
79             {
80                 static if (isSigned!U)
81                     assert(value >= 0, `value too small`);
82                 assert(value < m, `value too large`);
83             }
84         }
85         do
86         {
87             this._value = cast(T)value; // overflow checked in ctor
88         }
89 
90         /// Assign from Mod!n, where `n <= m`.
91         auto ref opAssign(size_t n, U)(Mod!(n, U) rhs)
92         if (n <= m && isIntegral!U)
93         {
94             this._value = cast(T)rhs._value; // cannot overflow
95         }
96 
97         auto ref opOpAssign(string op, U)(U rhs)
98         if ((op == `+` ||
99              op == `-` ||
100              op == `*`) &&
101             isIntegral!U)
102         {
103             mixin(`_value = cast(T)(_value ` ~ op ~ `rhs);`);
104             return this;
105         }
106 
107         auto opUnary(string op, string file = __FILE__, int line = __LINE__)()
108         {
109             static      if (op == `+`)
110             {
111                 return this;
112             }
113             else static if (op == `--`)
114             {
115                 import nxt.math_ex : isPowerOf2;
116                 static if (isPowerOf2(m))
117                     _value = (_value - 1) & max; // more efficient
118                 else
119                     if (_value == min) _value = max; else --_value;
120                 return this;
121             }
122             else static if (op == `++`)
123             {
124                 import nxt.math_ex : isPowerOf2;
125                 static if (isPowerOf2(m))
126                     _value = (_value + 1) & max; // more efficient
127                 else
128                     if (_value == max) _value = min; else ++_value;
129                 return this;
130             }
131             else
132                 static assert(`Unsupported unary operator `, op);
133         }
134 
135         @property size_t _prop() const @safe pure nothrow @nogc { return _value; } // read-only access
136         alias _prop this;
137 
138         private T _value;
139     }
140 }
141 
142 /// Instantiator for `Mod`.
143 auto mod(size_t m, T = UnsignedOfModulo!m)(T value)
144 if (m >= 1)
145 {
146     return Mod!(m)(value);
147 }
148 
149 /** Lookup type representing an unsigned integer in inclusive range (0 .. m - 1).
150  *
151  * TODO: Merge with similar logic in bound.d
152  */
153 private template UnsignedOfModulo(size_t m)
154 {
155     static      if (m - 1 <= ubyte.max)
156     {
157         alias UnsignedOfModulo = ubyte;
158     }
159     else static if (m - 1 <= ushort.max)
160     {
161         alias UnsignedOfModulo = ushort;
162     }
163     else static if (m - 1 <= uint.max)
164     {
165         alias UnsignedOfModulo = uint;
166     }
167     else
168     {
169         alias UnsignedOfModulo = ulong;
170     }
171     // TODO: ucent?
172 }
173 
174 ///
175 @safe pure nothrow @nogc unittest
176 {
177     enum m = 256;
178     Mod!(m, ubyte) ub = cast(ubyte)(m - 1);
179     Mod!(m, uint) ui = cast(ubyte)(m - 1);
180     assert(ub == ui);
181     --ub;
182     assert(ub != ui);
183     ui = ub;
184     assert(ub == ui);
185     --ui;
186     assert(ub != ui);
187     ub = ui;
188     assert(ub == ui);
189 }
190 
191 ///
192 @safe pure nothrow @nogc unittest
193 {
194     static assert(is(typeof(Mod!3(1)) ==
195                      typeof(1.mod!3)));
196 
197     // check size logic
198     static assert(Mod!(ubyte.max + 1).sizeof == 1);
199     static assert(Mod!(ubyte.max + 2).sizeof == 2);
200     static assert(Mod!(ushort.max + 1).sizeof == 2);
201     static assert(Mod!(ushort.max + 2).sizeof == 4);
202     static assert(Mod!(cast(size_t)uint.max + 1).sizeof == 4);
203     static assert(Mod!(cast(size_t)uint.max + 2).sizeof == 8);
204 
205     // assert that storage defaults to packed unsigned integer
206     static assert(is(Mod!(8, ubyte) == Mod!(8)));
207 
208     Mod!(8, ubyte) x = 6;
209     static assert(x.min == 0);
210     static assert(x.max == 7);
211     Mod!(8, ubyte) y = 7;
212     static assert(y.min == 0);
213     static assert(y.max == 7);
214 
215     assert(x < y);
216 
217     y = 5;
218     y = 5L;
219 
220     assert(y < x);
221 
222     assert(y == 5);
223     assert(y != 0);
224 
225     y++;
226     assert(y == 6);
227     assert(++y == y.max);
228     assert(y++ == y.max);
229     assert(y == y.min);
230     assert(--y == y.max);
231     assert(++y == y.min);
232 
233     Mod!(8, uint) ui8 = 7;
234     Mod!(256, ubyte) ub256 = 255;
235     ub256 = ui8;    // can assign to larger modulo from higher storage precision
236 
237     Mod!(258, ushort) ub258 = ub256;
238 
239     // copy construction to smaller modulo is disallowed
240     static assert(!__traits(compiles, { Mod!(255, ubyte) ub255 = ub258; }));
241 
242     auto a = 7.mod!10;
243     auto b = 8.mod!256;
244     auto c = 257.mod!1000;
245 
246     static assert(c.min == 0);
247     static assert(c.max == 999);
248 
249     assert(a < b);
250     assert(a < c);
251 
252     // assignment to larger modulo (super-type/set) is allowed
253     b = a;
254     c = a;
255     c = b;
256 
257     // assignment to smaller modulo (sub-type/set) is disallowed
258     static assert(!__traits(compiles, { a = b; }));
259     static assert(!__traits(compiles, { a = c; }));
260 }
261 
262 ///
263 @safe pure nothrow @nogc unittest
264 {
265     Mod!(256, ubyte) x = 55;
266 
267     x += 200;
268     assert(x == 255);
269 
270     x += 1;
271     assert(x == 0);
272 
273     x -= 4;
274     assert(x == 252);
275 }
276 
277 /// construct from other precision
278 @safe pure nothrow @nogc unittest
279 {
280     enum m = 256;
281     Mod!(m, ubyte) x = 55;
282     Mod!(m, uint) y = x;
283     Mod!(m, ubyte) z = y;
284 }