1 #!/usr/bin/env rdmd-unittest-module
2 
3 /** Lazy Substitution Algorithms.
4  *
5  * See_Also: http://forum.dlang.org/post/pymxzazxximtgixzbnpq@forum.dlang.org
6  */
7 module nxt.substitution;
8 
9 import std.range.primitives : isInputRange, ElementType;
10 import core.internal.traits : Unqual;
11 import std.typecons : Tuple;
12 import std.traits : isExpressionTuple;
13 import std.algorithm.searching : startsWith;
14 
15 import nxt.traits_ex : hasEvenLength, haveCommonType;
16 
17 import std.stdio;
18 
19 version(unittest)
20 {
21     import std.algorithm.comparison : equal;
22 }
23 
24 import std.traits : isExpressionTuple;
25 import nxt.traits_ex : haveCommonType;
26 
27 /** Similar to $(D among) but for set of replacements/substitutions $(D substs).
28  *
29  * Time-Complexity: O(1) thanks to D's $(D switch) guaranteeing O(1).
30  */
31 template substitute(substs...)
32 if ((substs.length & 1) == 0 && // need even number of elements (>= 1)
33     substs.length >= 2 && // and at least one replacement pair
34     isExpressionTuple!substs &&
35     haveCommonType!(substs))
36 {
37     Value substitute(Value)(Value value)
38     if (haveCommonType!(Value, substs)) // TODO need static map incorrect
39     {
40         switch (value)
41         {
42             static foreach (i; 0 .. substs.length / 2)
43             {
44             case substs[2*i]:
45                 return substs[2*i + 1];
46             }
47         default:
48             return value;
49         }
50     }
51 }
52 
53 @safe pure nothrow unittest
54 {
55     auto xyz_abc__(T)(T value)
56     {
57         immutable a = "a";
58         const b = "b";
59         auto c = "c";
60         return value.substitute!("x", a,
61                                  "y", b,
62                                  "z", c);
63     }
64     assert(xyz_abc__("x") == "a");
65     assert(xyz_abc__("y") == "b");
66     assert(xyz_abc__("z") == "c");
67     assert(xyz_abc__("w") == "w");
68 }
69 
70 /** Substitute in parallel all elements in $(D r) which equal (according to $(D
71  * pred)) $(D ss[2*n]) with $(D ss[2*n + 1]) for $(D n) = 0, 1, 2, ....
72  */
73 auto substitute(alias pred = (a, b) => a == b, R, Ss...)(R r, Ss ss)
74 if (isInputRange!(Unqual!R) &&
75     Ss.length >= 2 &&
76     hasEvenLength!Ss &&
77     haveCommonType!(ElementType!R, Ss))
78 {
79     import std.algorithm.iteration : map;
80     import std.functional : binaryFun;
81     enum n = Ss.length / 2;
82     auto replaceElement(E)(E e)
83     {
84         static foreach (i; 0 .. n)
85         {
86             if (binaryFun!pred(e, ss[2*i]))
87             {
88                 return ss[2*i + 1];
89             }
90         }
91         return e;
92     }
93     return r.map!(a => replaceElement(a));
94 }
95 
96 ///
97 @safe pure unittest
98 {
99     import std.conv : to;
100     import std.algorithm : map;
101     auto x = `42`.substitute('2', '3')
102                  .substitute('3', '1');
103     static assert(is(ElementType!(typeof(x)) == dchar));
104     assert(equal(x, `41`));
105 }
106 
107 ///
108 @safe pure unittest
109 {
110     assert(`do_it`.substitute('_', ' ')
111                   .equal(`do it`));
112     int[3] x = [1, 2, 3];
113     auto y = x[].substitute(1, 0.1)
114                 .substitute(0.1, 0.2);
115     static assert(is(typeof(y.front) == double));
116     assert(y.equal([0.2, 2, 3]));
117     assert(`do_it`.substitute('_', ' ',
118                               'd', 'g',
119                               'i', 't',
120                               't', 'o')
121                   .equal(`go to`));
122     import std.range : retro;
123     assert(equal([1, 2, 3].substitute(1, 0.1)
124                           .retro,
125                  [3, 2, 0.1]));
126 }
127 
128 /** Substitute in parallel all elements in $(D r) which equal (according to $(D
129     pred)) $(D ss[2*n]) with $(D ss[2*n + 1]) for $(D n) = 0, 1, 2, ....
130 
131     Because $(D ss) are known at compile time, time-complexity for each element
132     substitution is O(1).
133 */
134 template substitute(ss...)
135 if (isExpressionTuple!ss &&
136     ss.length >= 2 &&
137     hasEvenLength!ss)
138 {
139     auto substitute(R)(R r)
140         if (isInputRange!(Unqual!R) &&
141             haveCommonType!(ElementType!R, ss))
142     {
143         import std.algorithm.iteration : map;
144         enum n = ss.length / 2;
145         auto replaceElement(E)(E e)
146         {
147             switch (e)
148             {
149                 static foreach (i; 0 .. n)
150                 {
151                 case ss[2*i]: return ss[2*i + 1];
152                 }
153             default: return e;
154             }
155         }
156         return r.map!(a => replaceElement(a));
157     }
158 }
159 
160 ///
161 @safe pure unittest
162 {
163     assert(`do_it`.substitute!('_', ' ')
164                   .equal(`do it`));
165     int[3] x = [1, 2, 3];
166     auto y = x[].substitute!(1, 0.1);
167     assert(y.equal([0.1, 2, 3]));
168     static assert(is(typeof(y.front) == double));
169     assert(`do_it`.substitute!('_', ' ',
170                                'd', 'g',
171                                'i', 't',
172                                't', 'o')
173                   .equal(`go to`));
174     import std.range : retro;
175     assert(equal([1, 2, 3].substitute!(1, 0.1)
176                           .retro,
177                  [3, 2, 0.1]));
178 }
179 
180 /** Helper range for subsequence overload of $(D substitute).
181  */
182 private auto substituteSplitter(alias pred = `a == b`, R, Rs...)(R haystack, Rs needles)
183 if (Rs.length >= 1 &&
184     is(typeof(startsWith!pred(haystack, needles))))
185 {
186     static struct Result
187     {
188         alias Hit = size_t; // 0 iff no hit, otherwise hit in needles[index-1]
189         alias E = Tuple!(R, Hit);
190         this(R haystack, Rs needles)
191         {
192             this._rest = haystack;
193             this._needles = needles;
194             popFront();
195         }
196 
197         @property auto ref front()
198         {
199             import std.range.primitives : empty;
200             return !_skip.empty ? E(_skip, 0) : E(_hit, _hitNr);
201         }
202 
203         import std.range.primitives : isInfinite;
204         static if (isInfinite!R)
205             enum empty = false; // propagate infiniteness
206         else
207             @property bool empty() const
208             {
209                 import std.range.primitives : empty;
210                 return _skip.empty && _hit.empty && _rest.empty;
211             }
212 
213         void popFront() @trusted
214         {
215             import std.range.primitives : empty;
216             if (!_skip.empty)
217             {
218                 _skip = R.init; // jump over _skip
219             }
220             else
221             {
222                 import std.algorithm.searching : find;
223 
224                 static if (_needles.length >= 2) // if variadic version
225                 {
226                     auto match = _rest.find!pred(_needles);
227                     auto hitValue = match[0];
228                     _hitNr = match[1];
229                 }
230                 else
231                 {
232                     auto match = _rest.find!pred(_needles);
233                     auto hitValue = match;
234                     _hitNr = !match.empty ? 1 : 0;
235                 }
236 
237                 if (_hitNr == 0) // no more hits
238                 {
239                     _skip = _rest;
240                     _hit = R.init;
241                     _rest = R.init;
242                 }
243                 else
244                 {
245                     import std.traits : isSomeString;
246                     static if (isSomeString!R)
247                     {
248                         size_t hitLength = size_t.max;
249                         final switch (_hitNr - 1)
250                         {
251                             foreach (const i, Ri; Rs)
252                             {
253                             case i: hitLength = _needles[i].length; break;
254                             }
255                         }
256                         assert(hitLength != size_t.max); // not needed if match returned bounded!int
257 
258                         if (_rest.ptr == hitValue.ptr) // match at start of _rest
259                         {
260                             _hit = hitValue[0 .. hitLength];
261                             _rest = hitValue[hitLength .. $];
262                         }
263                         else
264                         {
265                             _skip = _rest[0 .. hitValue.ptr - _rest.ptr];
266                             _hit = hitValue[0 .. hitLength];
267                             _rest = hitValue[hitLength .. $];
268                         }
269                     }
270                     else
271                     {
272                         static assert(0, `Handle R without slicing ` ~ R.stringof);
273                     }
274                 }
275             }
276         }
277     private:
278         R _rest;
279         Rs _needles;
280         R _skip; // skip before next hit
281         R _hit; // most recent (last) hit if any
282         size_t _hitNr; // hit number: 0 means no hit, otherwise index+1 to needles that matched
283     }
284     return Result(haystack, needles);
285 }
286 
287 @safe pure unittest
288 {
289     auto h = `alpha.beta.gamma`;
290     auto fs = h.substituteSplitter(`alpha`, `beta`, `gamma`);
291     alias FS = typeof(fs);
292     alias E = ElementType!FS;
293     static assert(is(E == Tuple!(string, ulong)));
294     assert(equal(fs, [E(`alpha`, 1),
295                       E(`.`, 0),
296                       E(`beta`, 2),
297                       E(`.`, 0),
298                       E(`gamma`, 3)]));
299 }
300 
301 @safe pure unittest
302 {
303     auto h = `.alpha.beta.gamma`;
304     auto fs = h.substituteSplitter(`alpha`, `beta`, `gamma`);
305     alias FS = typeof(fs);
306     alias E = ElementType!FS;
307     static assert(is(E == Tuple!(string, ulong)));
308     assert(equal(fs, [E(`.`, 0),
309                       E(`alpha`, 1),
310                       E(`.`, 0),
311                       E(`beta`, 2),
312                       E(`.`, 0),
313                       E(`gamma`, 3)]));
314 }
315 
316 @safe pure unittest
317 {
318     auto h = `alpha.beta.gamma.`;
319     auto fs = h.substituteSplitter(`alpha`, `beta`, `gamma`);
320     alias FS = typeof(fs);
321     alias E = ElementType!FS;
322     static assert(is(E == Tuple!(string, ulong)));
323     assert(equal(fs, [E(`alpha`, 1),
324                       E(`.`, 0),
325                       E(`beta`, 2),
326                       E(`.`, 0),
327                       E(`gamma`, 3),
328                       E(`.`, 0)]));
329 }
330 
331 @safe pure unittest
332 {
333     auto h = `alpha.alpha.alpha.`;
334     auto fs = h.substituteSplitter(`alpha`);
335     alias FS = typeof(fs);
336     alias E = ElementType!FS;
337     static assert(is(E == Tuple!(string, ulong)));
338     assert(equal(fs, [E(`alpha`, 1),
339                       E(`.`, 0),
340                       E(`alpha`, 1),
341                       E(`.`, 0),
342                       E(`alpha`, 1),
343                       E(`.`, 0)]));
344 }
345 
346 template Stride(size_t stride, size_t offset, Args...)
347 if (stride > 0)
348 {
349     import std.meta : AliasSeq;
350     static if (offset >= Args.length)
351     {
352         alias Stride = AliasSeq!();
353     }
354     else static if (stride >= Args.length)
355     {
356         alias Stride = AliasSeq!(Args[offset]);
357     }
358     else
359     {
360         alias Stride = AliasSeq!(Args[offset],
361                                  Stride!(stride, offset, Args[stride .. $]));
362     }
363 }
364 
365 /** Substitute in parallel all subsequences in $(D r) which equal (according to
366     $(D pred)) $(D ss[2*n]) with $(D ss[2*n + 1]) for $(D n) = 0, 1, 2, ....
367 */
368 auto substitute(alias pred = (a, b) => a == b, R, Ss...)(R r, Ss ss)
369 if (isInputRange!(Unqual!R) &&
370     Ss.length >= 2 &&
371     hasEvenLength!Ss &&
372     haveCommonType!(ElementType!R,
373                     ElementType!(Ss[0])))
374 {
375     import std.algorithm.iteration : map;
376     import std.functional : binaryFun;
377 
378     enum n = Ss.length / 2;
379 
380     auto replaceElement(E)(E e)
381     {
382         auto value = e[0];
383         const hitNr = e[1];
384         if (hitNr == 0) // not hit
385         {
386             return value;
387         }
388         else
389         {
390             static foreach (i; 0 .. n)
391             {
392                 if (hitNr == i + 1)
393                 {
394                     return ss[2*i + 1]; // replacement
395                 }
396             }
397             assert(false);
398         }
399     }
400 
401     // extract inputs
402     alias Ins = Stride!(2, 0, Ss);
403     Ins ins;
404     static foreach (i; 0 .. n)
405     {
406         ins[i] = ss[2*i];
407     }
408 
409     import std.algorithm.iteration : map, joiner;
410     return r.substituteSplitter!pred(ins)
411             .map!(a => replaceElement(a))
412             .joiner;
413 }
414 
415 @safe pure unittest
416 {
417     assert(`do_it now, sir`.substitute(`_`, ` `,
418                                        `d`, `g`,
419                                        `i`, `t`,
420                                        `t`, `o`,
421                                        `now`, `work`,
422                                        `sir`, `please`)
423                   .equal(`go to work, please`));
424 }
425 
426 @safe pure unittest
427 {
428     assert((`abcDe`.substitute(`a`, `AA`,
429                                `b`, `DD`)
430                    .substitute('A', 'y',
431                                'D', 'x',
432                                'e', '1'))
433            .equal(`yyxxcx1`));
434 }