1 /// This module handels the rim selector used in the DART modify function
2 module tagion.dart.RimKeyRange;
3 
4 import std.algorithm;
5 import std.container.array;
6 import std.range;
7 import std.traits;
8 import std.typecons : Flag, No, Yes;
9 import tagion.basic.Debug;
10 import tagion.basic.Types : Buffer, isBufferType;
11 import tagion.dart.Recorder : Archive, Flip, GetType, Neutral, RecordFactory;
12 
13 /**
14  * Gets the rim key from a buffer
15  *
16  * Returns;
17  *     fingerprint[rim]
18  */
19 @safe
20 ubyte rim_key(F)(F rim_keys, const uint rim) pure if (isBufferType!F) {
21     return rim_keys[rim];
22 }
23 
24 /**
25  * Creates a rim selector from a range
26  * Params:
27  *   range = range to be used
28  *   undo = Yes if the range should be undone
29  * Returns: 
30  */
31 @safe
32 RimKeyRange!Range rimKeyRange(Range)(Range range, const Flag!"undo" undo = No.undo, const GetType get_type = null)
33         if (isInputRange!Range && is(ElementType!Range : const(Archive))) {
34     return RimKeyRange!Range(range, undo, get_type);
35 }
36 
37 /**
38  * Creates a rim selector range from a Recorder
39  * Params:
40  *   rec = recorder 
41  *   undo = Yes of the recorder should be undone
42  */
43 @safe
44 auto rimKeyRange(Flag!"undo" undo = No.undo)(const(RecordFactory.Recorder) rec) {
45     static if (undo) {
46         return rimKeyRange(rec[].retro, undo, Flip);
47     }
48     else {
49         return rimKeyRange(rec[], undo);
50     }
51 }
52 
53 /// Range over a Range with the same key in the a specific rim
54 @safe
55 struct RimKeyRange(Range) if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, const(Archive))) {
56     alias archive_less = RecordFactory.Recorder.archive_sorted;
57     @safe
58     final class RangeContext {
59         Range range;
60         const(Archive)[] _added_archives;
61         AdderRange added_range;
62         const GetType get_type;
63         pure nothrow {
64             this(Range range, const GetType _get_type = null) {
65                 this.range = range;
66                 added_range = new AdderRange(0);
67                 get_type = (_get_type) ? _get_type : Neutral;
68             }
69 
70             protected this(RangeContext rhs, const GetType _get_type = null) {
71                 _added_archives = rhs._added_archives;
72                 range = rhs.range;
73                 added_range = new AdderRange(rhs.added_range.index);
74                 get_type = (_get_type) ? _get_type : rhs.get_type;
75             }
76 
77             /**
78              * Checks if the range is empty
79              * Returns: true if empty
80              */
81             bool empty() @nogc {
82                 return range.empty && added_range.empty;
83             }
84 
85             /**
86              *  Progress one archive
87              */
88             void popFront() {
89                 if (!added_range.empty && !range.empty) {
90                     if (archive_less(added_range.front, range.front)) {
91                         added_range.popFront;
92                     }
93                     else {
94                         range.popFront;
95                     }
96                 }
97                 else if (!range.empty) {
98                     range.popFront;
99                 }
100                 else if (!added_range.empty) {
101                     added_range.popFront;
102                 }
103             }
104             /**
105              * Gets the current archive in the range
106              * Returns: current archive and return null if the range is empty
107              */
108             const(Archive) front()
109             out (archive) {
110                 assert(!archive.dart_index.empty);
111             }
112             do {
113                 if (!added_range.empty && !range.empty) {
114                     if (archive_less(added_range.front, range.front)) {
115                         return added_range.front;
116                     }
117                     return range.front;
118                 }
119                 if (!range.empty) {
120                     return range.front;
121                 }
122                 else if (!added_range.empty) {
123                     return added_range.front;
124                 }
125                 return Archive.init;
126             }
127 
128             RangeContext save() {
129                 return new RangeContext(this);
130             }
131 
132             Archive.Type type() {
133                 if (!added_range.empty && !range.empty) {
134                     if (archive_less(added_range.front, range.front)) {
135                         return added_range.front.type;
136                     }
137                     return get_type(range.front);
138                 }
139                 if (!range.empty) {
140                     return get_type(range.front);
141                 }
142                 else if (!added_range.empty) {
143                     return get_type(added_range.front);
144                 }
145                 return Archive.Type.NONE;
146 
147             }
148         }
149         @safe @nogc
150         final class AdderRange {
151             size_t index;
152             pure nothrow {
153                 this(size_t index) {
154                     this.index = index;
155                 }
156 
157                 bool empty() {
158                     return index >= _added_archives.length;
159                 }
160 
161                 const(Archive) front() {
162                     return _added_archives[index];
163                 }
164 
165                 void popFront() {
166                     if (!empty) {
167                         index++;
168                     }
169                 }
170             }
171         }
172     }
173 
174     @disable this();
175     protected RangeContext ctx;
176     const Buffer rim_keys;
177     const int rim;
178     const Flag!"undo" undo;
179 
180     pure nothrow {
181         /**
182          * Construct an copy of an existing range
183          * Params:
184          *   rhs = Range to be copied
185          *   rim = Sets the rim for the new copy
186          */
187         private this(RimKeyRange rhs, const uint rim) {
188             ctx = rhs.ctx;
189             if (rim + 1 > rhs.front.dart_index.length) {
190                 __write("rim=%d  size=%d %(%02X %)", rim, rhs.front.dart_index.length, rhs.front.dart_index);
191             }
192             rim_keys = (rhs.empty) ? Buffer.init : rhs.front.dart_index[0 .. rim + 1];
193             this.rim = rim & int.max;
194             undo = rhs.undo;
195         }
196 
197         /**
198          * Construct an copy of an existing range
199          * Params:
200          *   rhs = Range to be copied
201          */
202         private this(RimKeyRange rhs) {
203             ctx = rhs.ctx.save;
204             rim_keys = rhs.rim_keys;
205             rim = rhs.rim;
206             undo = rhs.undo;
207         }
208         /**
209          * 
210          * Params:
211          *   range = Range to be selected from 
212          *   undo = if Yes it will revert the range
213          *   get_type = set the archive type set function
214          */
215         private this(Range range, const Flag!"undo" undo, const GetType get_type = null) {
216             this.undo = undo;
217             rim = -1;
218             //auto range_save=_range.save;
219             ctx = new RangeContext(range, get_type);
220             rim_keys = null;
221         }
222 
223         /**
224          * Checks if only one archives are left in the range
225          * Returns: 
226          */
227         bool oneLeft() {
228             if (rim < 0 || ctx.empty) {
229                 return false;
230             }
231             const _index = ctx.added_range.index;
232             auto _range = ctx.range;
233             scope (exit) {
234                 ctx.added_range.index = _index;
235                 ctx.range = _range;
236             }
237 
238             return this.take(2).walkLength == 1;
239         }
240 
241         /**
242          * Adds an archive to the current range
243          * The archives should be in the same rim
244          * Params:
245          *   archive = the added element
246          */
247         void add(const(Archive) archive)
248         in ((rim < 0) || (rim_keys == archive.dart_index[0 .. rim + 1]))
249         do 
250         {
251             ctx._added_archives ~= archive;
252         }
253 
254         /**
255          * Create a new range from this range at the rim
256          * Params:
257          *   rim = the rim to be use in the new range
258          * Returns: Range for the selected rim 
259          */
260         RimKeyRange selectRim(const uint rim) {
261             return RimKeyRange(this, rim);
262         }
263 
264         /**
265          * Create a new range from this range at the next rim 
266          * 
267          * Returns: Next range an the rim+1 
268          */
269         RimKeyRange nextRim() {
270             return RimKeyRange(this, rim + 1);
271         }
272 
273         /**
274          * Checks if the range is empty
275          * Returns: true if empty
276          */
277         bool empty() @nogc {
278             return ctx.empty || (rim >= 0) && (rim_keys != ctx.front.dart_index[0 .. rim + 1]);
279         }
280 
281         /**
282          * Progress to the next archive in the list 
283          */
284         void popFront() {
285             if (!empty) {
286                 ctx.popFront;
287             }
288         }
289 
290         /**
291          * 
292          * Returns: first archive in the range
293          */
294         const(Archive) front() {
295             return ctx.front;
296         }
297 
298         /**
299          * 
300          * Returns: first archive in the range
301          */
302         const(Archive.Type) type() {
303             return ctx.type;
304         }
305 
306         /**
307          * Creates new range at the current position
308          * Returns: copy of this range
309          */
310         RimKeyRange save() {
311             return RimKeyRange(this);
312         }
313     }
314     static assert(isInputRange!RimKeyRange);
315     static assert(isForwardRange!RimKeyRange);
316 
317 }
318 
319 version (unittest) {
320     import std.typecons : Tuple;
321     import tagion.dart.DARTBasic : DARTIndex;
322 
323     alias TraverseData = Tuple!(DARTIndex, "dart_index", Archive.Type, "type");
324     @safe
325     TraverseData[] traverse(
326             const(RecordFactory.Recorder) recorder,
327             const Flag!"undo" undo = No.undo) {
328         TraverseData[] result;
329 
330         void inner_traverse(RimRange)(RimRange rim_key_range) {
331             while (!rim_key_range.empty) {
332                 if (rim_key_range.oneLeft) {
333                     result ~= TraverseData(rim_key_range.front.dart_index, rim_key_range.type);
334                     rim_key_range.popFront;
335                 }
336                 else if (rim_key_range.front.type == Archive.Type.REMOVE) {
337                     result ~= TraverseData(rim_key_range.front.dart_index, rim_key_range.type);
338                     rim_key_range.popFront;
339                 }
340                 else {
341                     inner_traverse(rim_key_range.nextRim);
342                 }
343             }
344         }
345 
346         if (undo) {
347             inner_traverse(rimKeyRange!(Yes.undo)(recorder));
348         }
349         else {
350             inner_traverse(rimKeyRange(recorder));
351 
352         }
353         return result;
354     }
355 }
356 
357 @safe
358 unittest {
359     import std.algorithm.searching : until;
360     import std.typecons;
361     import tagion.dart.DARTFakeNet;
362 
363     const net = new DARTFakeNet;
364     auto factory = RecordFactory(net);
365 
366     { // Test with ADD's only in the RimKeyRange root (rim == -1)
367         const table = [
368 
369             0xABCD_1334_5678_9ABCUL,
370             0xABCD_1335_5678_9ABCUL,
371             0xABCD_1336_5678_9ABCUL, // Archives which add added in to the RimKeyRange
372             0xABCD_1334_AAAA_AAAAUL,
373             0xABCD_1335_5678_AAAAUL,
374 
375         ];
376         const documents = table
377             .map!(t => DARTFakeNet.fake_doc(t))
378             .array;
379 
380         // Create a recorder from the first 9 documents 
381         auto rec = factory.recorder(documents.take(3), Archive.Type.ADD);
382         { // Check the the rim-key range is the same as the recorder
383             /*
384             Archive abcd133456789abc ADD
385             Archive abcd133556789abc ADD
386             Archive abcd133656789abc ADD
387             */
388             auto rim_key_range = rimKeyRange(rec);
389             auto rim_key_range_saved = rim_key_range.save;
390             assert(equal(rec[].map!q{a.dart_index}, rim_key_range.map!q{a.dart_index}));
391             // Check save in forward-range
392             assert(equal(rec[].map!q{a.dart_index}, rim_key_range_saved.map!q{a.dart_index}));
393         }
394 
395         { // Add one to the rim_key range and check if it is range is ordered correctly
396             auto rim_key_range = rimKeyRange(rec);
397             auto rec_copy = rec.dup;
398             rec_copy.insert(documents[3], Archive.Type.ADD);
399 
400             rim_key_range.add(rec.archive(documents[3], Archive.Type.ADD));
401             /*
402             Archive abcd133456789abc ADD
403             Archive abcd1334aaaaaaaa ADD <- This has been added in between
404             Archive abcd133556789abc ADD
405             Archive abcd133656789abc ADD
406             */
407             auto rim_key_range_saved = rim_key_range.save;
408             assert(equal(rec_copy[].map!q{a.dart_index}, rim_key_range.map!q{a.dart_index}));
409             // Check save in forward-range
410             assert(equal(rec_copy[].map!q{a.dart_index}, rim_key_range_saved.map!q{a.dart_index}));
411 
412         }
413 
414         { // Add two to the rim_key range and check if it is range is ordered correctly
415             auto rim_key_range = rimKeyRange(rec);
416             auto rec_copy = rec.dup;
417             rim_key_range.add(rec.archive(documents[3], Archive.Type.ADD));
418             rim_key_range.add(rec.archive(documents[4], Archive.Type.ADD));
419             /*
420             Archive abcd133456789abc ADD 
421             Archive abcd1334aaaaaaaa ADD <- This has beend added
422             Archive abcd133556789abc ADD 
423             Archive abcd13355678aaaa ADD <- This has been added
424             Archive abcd133656789abc ADD 
425             */
426             rec_copy.insert(documents[3 .. 5], Archive.Type.ADD);
427 
428             auto rim_key_range_saved = rim_key_range.save;
429             assert(equal(rec_copy[].map!q{a.dart_index}, rim_key_range.map!q{a.dart_index}));
430             // Check save in forward-range
431             assert(equal(rec_copy[].map!q{a.dart_index}, rim_key_range_saved.map!q{a.dart_index}));
432 
433         }
434     }
435     {
436         const table = [
437 
438             ulong.min, // 0                      |00|..
439             //00 01 02  03   ........
440             0xAB_CC_13_34_56789ABCUL, // 1    |AB|CC|..
441             0xAB_CD_13_35_56789ABCUL, // 2    |AB|CD|13|..
442             0xAB_CD_13_36_56789ABCUL, // 3    |AB|CD|14|..
443             //00 01 02 03  04  ........           00 01 02 03 04  
444             0xAB_CD_13_37_56_789ABCUL, // 4    |AB|CD|13|37|56|..
445             0xAB_CD_13_37_58_789ABCUL, // 5    |AB|CD|13|37|58|..
446             0xAB_CD_13_37_60_789ABCUL, // 6    |AB|CD|13|37|60|..
447             //00 01 02 03 04 05  06  ...          00 01 02 03 04 05 06  
448             0xAB_CD_13_37_69_78_9B_BCUL, // 7  |AB|CD|13|37|69|78|9B|..
449             0xAB_CD_13_37_69_78_9C_BEUL, // 8  |AB|CD|13|37|69|78|9C|.. 
450             0xAB_CD_13_37_69_78_9D_BFUL, // 9  |AB|CD|13|37|69|78|9D|.. 
451 
452             ulong.max, // 11 |FF|..
453             // Archives which add added in to the RimKeyRange
454             0xAB_CD_1334_AAAA_AAAAUL,
455             0xAB_CD_1335_5678_AAAAUL,
456 
457         ];
458         const documents = table
459             .map!(t => DARTFakeNet.fake_doc(t))
460             .array;
461 
462         auto rec = factory.recorder(
463                 documents
464                 .until!(doc => doc == DARTFakeNet.fake_doc(ulong.max))(No.openRight),
465                 Archive.Type.ADD);
466 
467         { /// Check selectRim
468             auto rim_key_range = rimKeyRange(rec);
469             { // Check the range lengths of rim = 00 
470                 auto rim_key_copy = rim_key_range.save;
471                 const rim = 00;
472                 assert(rim_key_copy.selectRim(rim).walkLength == 1);
473                 assert(rim_key_copy.selectRim(rim).walkLength == 9);
474                 assert(rim_key_copy.selectRim(rim).walkLength == 1);
475             }
476 
477             { // Check the range lengths of rim = 01 
478                 auto rim_key_copy = rim_key_range.save;
479                 const rim = 01;
480                 assert(rim_key_copy.selectRim(rim).walkLength == 1);
481                 assert(rim_key_copy.selectRim(rim).walkLength == 1);
482                 assert(rim_key_copy.selectRim(rim).walkLength == 8);
483                 assert(rim_key_copy.selectRim(rim).walkLength == 1);
484             }
485 
486         }
487         const rec_len = rec.length;
488         // Checks that the 
489         rec.insert(documents[rec_len], Archive.Type.REMOVE);
490         rec.insert(documents[rec_len + 1], Archive.Type.REMOVE);
491 
492         { // Check that the order of the archives are the same in the rim-key-range
493             const result = traverse(rec);
494             assert(equal(rec[].map!q{a.dart_index}, result.map!q{a.dart_index}));
495             assert(equal(rec[].map!q{a.type}, result.map!q{a.type}));
496 
497         }
498 
499         { // Checks the undo
500             // The order should be reversed and the type should be flipped ADD<->REMOVE
501             const result = traverse(rec, Yes.undo);
502             assert(equal(rec[].retro.map!q{a.dart_index}, result.map!q{a.dart_index}));
503             assert(equal(rec[].retro.map!(a => Flip(a)), result.map!q{a.type}));
504         }
505 
506     }
507 
508 }