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 }