1 /** 2 This module contains a genrelaized 1-D masking algorithm. 3 4 Copyright: © 2018 Arne Ludwig <arne.ludwig@posteo.de> 5 License: Subject to the terms of the MIT license, as written in the 6 included LICENSE file. 7 Authors: Arne Ludwig <arne.ludwig@posteo.de> 8 */ 9 module dalicious.algorithm.masker; 10 11 import std.algorithm; 12 import std.array; 13 import std.exception; 14 import std.functional; 15 import std.math; 16 import std.range; 17 import std.range.primitives; 18 import std.traits; 19 import std.typecons; 20 21 22 debug version(unittest) 23 { 24 import std.format; 25 26 string investigateMask(M)(M mask, lazy string err = null) 27 { 28 if (err == null) 29 return format!"-- BEGIN\n%(%s,\n%)\n-- END"(mask); 30 else 31 return format!"%s:\n-- BEGIN\n%(%s,\n%)\n-- END"(err, mask); 32 } 33 } 34 35 36 auto masker( 37 alias begin, 38 alias end, 39 alias category, 40 alias acc, 41 acc_t, 42 R1, 43 R2 = R1, 44 )(R1 intervals, R2 boundaries = R2.init) @safe 45 if (isInputRange!R1 && isInputRange!R2 && is(ElementType!R1 == ElementType!R2)) 46 { 47 alias E = ElementType!R1; 48 alias _begin = unaryFun!begin; 49 alias _end = unaryFun!end; 50 51 // Trigger compilation for better debugging 52 alias __debugHelper = () => 53 { 54 cast(void) _begin(E.init); 55 cast(void) _end(E.init); 56 }; 57 static assert( 58 is(typeof(_begin(E.init)) == typeof(_end(E.init))), 59 "`begin` and `end` must have same type", 60 ); 61 62 alias pos_t = typeof(_begin(E.init)); 63 64 auto changeEvents = intervals.toChangeEvents!(_begin, _end, No.boundaries); 65 auto boundaryEvents = boundaries.toChangeEvents!(_begin, _end, Yes.boundaries); 66 67 alias MEvent = ElementType!(typeof(changeEvents)); 68 69 auto eventsAcc = appender!(MEvent[]); 70 71 static if (hasLength!R1) 72 eventsAcc.reserve(2 * intervals.length); 73 static if (hasLength!R2) 74 eventsAcc.reserve(2 * boundaries.length); 75 76 () @trusted { 77 chain(changeEvents, boundaryEvents).copy(eventsAcc); 78 }(); 79 80 eventsAcc.data.sort(); 81 82 return MaskerImpl!( 83 MEvent, 84 _begin, 85 _end, 86 category, 87 isPointer!E, 88 acc, 89 acc_t, 90 )(eventsAcc.data); 91 } 92 93 /// ditto 94 auto masker( 95 alias begin, 96 alias end, 97 alias category, 98 R1, 99 R2 = R1, 100 )(R1 intervals, R2 boundaries = R2.init) @safe 101 if (isInputRange!R1 && isInputRange!R2 && is(ElementType!R1 == ElementType!R2)) 102 { 103 return masker!(begin, end, category, null, void)(intervals, boundaries); 104 } 105 106 /// ditto 107 auto masker( 108 alias begin, 109 alias end, 110 R1, 111 R2 = R1, 112 )(R1 intervals, R2 boundaries = R2.init) @safe 113 if (isInputRange!R1 && isInputRange!R2 && is(ElementType!R1 == ElementType!R2)) 114 { 115 return masker!(begin, end, sgn)(intervals, boundaries); 116 } 117 118 /// 119 unittest 120 { 121 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 122 123 auto mask = masker!( 124 "a.begin", 125 "a.end", 126 )( 127 [ 128 Interval(1, 5), 129 Interval(2, 6), 130 Interval(3, 6), 131 Interval(2, 4), 132 Interval(8, 9), 133 ], 134 [Interval(0, 10)], 135 ); 136 137 alias I = mask.FrontType; 138 assert(equal(mask, [ 139 I(0, 1, 0), 140 I(1, 6, 1), 141 I(6, 8, 0), 142 I(8, 9, 1), 143 I(9, 10, 0), 144 ]), investigateMask(mask, "mask does not match")); 145 } 146 147 /// Custom `category` function: 148 unittest 149 { 150 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 151 152 enum Coverage 153 { 154 zero, 155 normal, 156 high, 157 } 158 auto mask = masker!( 159 "a.begin", 160 "a.end", 161 level => level >= 3 162 ? Coverage.high 163 : (level > 0 164 ? Coverage.normal 165 : Coverage.zero 166 ) 167 )( 168 [ 169 Interval(1, 5), 170 Interval(2, 6), 171 Interval(3, 6), 172 Interval(2, 4), 173 Interval(8, 9), 174 ], 175 [Interval(0, 10)], 176 ); 177 178 alias I = mask.FrontType; 179 assert(equal(mask, [ 180 I(0, 1, Coverage.zero), 181 I(1, 2, Coverage.normal), 182 I(2, 5, Coverage.high), 183 I(5, 6, Coverage.normal), 184 I(6, 8, Coverage.zero), 185 I(8, 9, Coverage.normal), 186 I(9, 10, Coverage.zero), 187 ]), investigateMask(mask, "mask does not match")); 188 } 189 190 /// The `acc` function is called once for every opening interval: 191 unittest 192 { 193 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 194 195 auto mask = masker!( 196 "a.begin", 197 "a.end", 198 sgn, 199 "++a", 200 size_t 201 )( 202 [ 203 Interval(1, 5), 204 Interval(2, 6), 205 Interval(3, 6), 206 Interval(2, 4), 207 Interval(8, 9), 208 ], 209 [Interval(0, 10)], 210 ); 211 212 alias I = mask.FrontType; 213 assert(equal(mask, [ 214 I(0, 1, 0, 0), 215 I(1, 6, 1, 4), 216 I(6, 8, 0, 0), 217 I(8, 9, 1, 1), 218 I(9, 10, 0, 0), 219 ]), investigateMask(mask, "mask does not match")); 220 } 221 222 /// If the intervals range has pointer type elements then the accumulator may 223 /// access them:payloadSum 224 unittest 225 { 226 alias Interval = Tuple!(size_t, "begin", size_t, "end", int, "payload"); 227 228 int payloadSum(int acc, const Interval* interval) 229 { 230 return acc + interval.payload; 231 } 232 233 auto mask = masker!( 234 "a.begin", 235 "a.end", 236 sgn, 237 payloadSum, 238 int, 239 )( 240 [ 241 new Interval(1, 5, 1), 242 new Interval(2, 6, -2), 243 new Interval(3, 6, 3), 244 new Interval(2, 4, -4), 245 new Interval(8, 9, 5), 246 ], 247 [new Interval(0, 10, 0)], 248 ); 249 250 alias I = mask.FrontType; 251 assert(equal(mask, [ 252 I(0, 1, 0, 0), 253 I(1, 6, 1, -2), 254 I(6, 8, 0, 0), 255 I(8, 9, 1, 5), 256 I(9, 10, 0, 0), 257 ]), investigateMask(mask, "mask does not match")); 258 } 259 260 unittest 261 { 262 // c1 c2 c3 263 // 0 5 10 15 20 25 30 0 5 10 15 0 5 10 15 264 // ref: [-----------------------------) [--------------) [--------------) 265 // reads: . . . . . . . . . . . . . . . 266 // . #1 [------------) . . . #12 [--) . . . #23 .[--). . . 267 // . #2 [------------) . . . #13 [--) . . . #24 . [--) . . 268 // . #3 [--------------) . . #14 [----) . . #25 . [--) . . 269 // . . #4 [---------) . . #15 [----) . . #26 . [--) . . 270 // . . #5 [-------------------) #16 [--------------) #27 . [--) . . 271 // . . #6 [-------------------) #17 [--------------) #28 . .[--). . 272 // . . #7 [----------------) #18 [--------------) #29 . . [--) . 273 // . . . . #8 [---------) .#19 [---------) #30 . . [--) . 274 // . . . . #9 [---------) .#20 [---------) #31 . . [--) . 275 // . . . .#10 [---------) .#21 [---------) #32 . . [--) . 276 // . . . . #11 [-----) . #22 [-----) #33 . . .[--). 277 // . . . . . . . . . . . . . . . 278 // mask: [====) [=======) [=========) [==) [=========) [==) . . [==) 279 // . . . . . . . . . . . . . . . 280 // cov: ^ . . . . . . . . . . . . . . 281 // | . . . . . . . . . . . . . . 282 // | . . +----+ . +----+. +-+ . +----+. . . . . 283 // | . +--+####| +---+####|. |#| +---+####|. . . . . 284 // 5 |.........|#######+-+########|. |#+--+########|. . . . . 285 // | . |##################|. |#############|. . . . . 286 // | +----+##################|. |#############|. . +-------+ . 287 // | |#######################|. |#############|. . ++#######++ . 288 // | |#######################|. |#############|. .++#########++ . 289 // 0 +----+-----------------------+--------+-------------+--------+-----------+----> 290 291 alias ReferenceInterval = Tuple!( 292 size_t, "contigId", 293 size_t, "begin", 294 size_t, "end", 295 ); 296 297 auto alignments = [ 298 ReferenceInterval(1, 5, 18), // #1 299 ReferenceInterval(1, 5, 18), // #2 300 ReferenceInterval(1, 5, 20), // #3 301 ReferenceInterval(1, 10, 20), // #4 302 ReferenceInterval(1, 10, 30), // #5 303 ReferenceInterval(1, 10, 30), // #6 304 ReferenceInterval(1, 13, 30), // #7 305 ReferenceInterval(1, 20, 30), // #8 306 ReferenceInterval(1, 20, 30), // #9 307 ReferenceInterval(1, 20, 30), // #10 308 ReferenceInterval(1, 24, 30), // #11 309 ReferenceInterval(2, 0, 3), // #12 310 ReferenceInterval(2, 0, 3), // #13 311 ReferenceInterval(2, 0, 5), // #14 312 ReferenceInterval(2, 0, 5), // #15 313 ReferenceInterval(2, 0, 15), // #16 314 ReferenceInterval(2, 0, 15), // #17 315 ReferenceInterval(2, 0, 15), // #18 316 ReferenceInterval(2, 5, 15), // #19 317 ReferenceInterval(2, 5, 15), // #20 318 ReferenceInterval(2, 5, 15), // #21 319 ReferenceInterval(2, 9, 15), // #22 320 ReferenceInterval(3, 1, 4), // #23 321 ReferenceInterval(3, 2, 5), // #24 322 ReferenceInterval(3, 3, 6), // #25 323 ReferenceInterval(3, 4, 7), // #26 324 ReferenceInterval(3, 5, 8), // #27 325 ReferenceInterval(3, 6, 9), // #28 326 ReferenceInterval(3, 7, 10), // #29 327 ReferenceInterval(3, 8, 11), // #30 328 ReferenceInterval(3, 9, 12), // #31 329 ReferenceInterval(3, 10, 13), // #32 330 ReferenceInterval(3, 11, 14), // #33 331 ]; 332 auto contigs = [ 333 ReferenceInterval(1, 0, 30), 334 ReferenceInterval(2, 0, 15), 335 ReferenceInterval(3, 0, 15), 336 ]; 337 338 alias pos_t = Tuple!(size_t, size_t); 339 alias beginPos = (refInt) => pos_t(refInt.contigId, refInt.begin); 340 alias endPos = (refInt) => pos_t(refInt.contigId, refInt.end); 341 342 enum CoverageZone : ubyte 343 { 344 low, 345 ok, 346 high, 347 } 348 349 enum lowerLimit = 3; 350 enum upperLimit = 5; 351 alias coverageZone = (coverage) => coverage < lowerLimit 352 ? CoverageZone.low 353 : coverage > upperLimit 354 ? CoverageZone.high 355 : CoverageZone.ok; 356 357 auto mask = masker!( 358 beginPos, 359 endPos, 360 coverageZone, 361 )(alignments, contigs); 362 363 alias I = mask.FrontType; 364 assert(equal(mask, [ 365 I( 366 pos_t(1, 0), 367 pos_t(1, 5), 368 CoverageZone.low, 369 ), 370 I( 371 pos_t(1, 5), 372 pos_t(1, 10), 373 CoverageZone.ok, 374 ), 375 I( 376 pos_t(1, 10), 377 pos_t(1, 18), 378 CoverageZone.high, 379 ), 380 I( 381 pos_t(1, 18), 382 pos_t(1, 20), 383 CoverageZone.ok, 384 ), 385 I( 386 pos_t(1, 20), 387 pos_t(1, 30), 388 CoverageZone.high, 389 ), 390 I( 391 pos_t(2, 0), 392 pos_t(2, 3), 393 CoverageZone.high, 394 ), 395 I( 396 pos_t(2, 3), 397 pos_t(2, 5), 398 CoverageZone.ok, 399 ), 400 I( 401 pos_t(2, 5), 402 pos_t(2, 15), 403 CoverageZone.high, 404 ), 405 I( 406 pos_t(3, 0), 407 pos_t(3, 3), 408 CoverageZone.low, 409 ), 410 I( 411 pos_t(3, 3), 412 pos_t(3, 12), 413 CoverageZone.ok, 414 ), 415 I( 416 pos_t(3, 12), 417 pos_t(3, 15), 418 CoverageZone.low, 419 ), 420 ]), investigateMask(mask, "mask does not match")); 421 } 422 423 unittest 424 { 425 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 426 427 auto mask = masker!( 428 "a.begin", 429 "a.end", 430 sgn, 431 "++a", 432 size_t, 433 )( 434 [ 435 Interval(0, 5), 436 Interval(0, 5), 437 Interval(0, 5), 438 Interval(0, 5), 439 Interval(0, 5), 440 Interval(6, 10), 441 Interval(6, 10), 442 Interval(6, 10), 443 Interval(6, 10), 444 ], 445 [Interval(0, 10)], 446 ); 447 448 alias I = mask.FrontType; 449 assert(equal(mask, [ 450 I(0, 5, 1, 5), 451 I(5, 6, 0, 0), 452 I(6, 10, 1, 4), 453 ]), investigateMask(mask, "mask does not match")); 454 } 455 456 unittest 457 { 458 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 459 460 auto mask = masker!("a.begin", "a.end")( 461 cast(Interval[]) [], 462 [ 463 Interval(0, 10), 464 Interval(20, 30), 465 ], 466 ); 467 468 alias I = mask.FrontType; 469 assert(equal(mask, [ 470 I(0, 10, 0), 471 I(20, 30, 0), 472 ]), investigateMask(mask, "mask does not match")); 473 } 474 475 unittest 476 { 477 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 478 479 auto mask = masker!("a.begin", "a.end")([ 480 Interval(0, 10), 481 Interval(20, 30), 482 ]); 483 484 alias I = mask.FrontType; 485 assert(equal(mask, [ 486 I(0, 10, 1), 487 I(10, 20, 0), 488 I(20, 30, 1), 489 ]), investigateMask(mask, "mask does not match")); 490 } 491 492 493 /// Add more intervals to masker without memory allocation for the original 494 /// intervals. 495 Masker withAdditionalIntervals(Masker, R1, R2 = R1)( 496 Masker mask, 497 R1 intervals, 498 R2 boundaries = R2.init, 499 ) if ( 500 isInputRange!R1 && isInputRange!R2 && is(ElementType!R1 == ElementType!R2) && 501 __traits(isSame, TemplateOf!Masker, MaskerImpl) 502 ) 503 { 504 auto changeEvents = intervals.toChangeEvents!(Masker._begin, Masker._end, No.boundaries); 505 auto boundaryEvents = boundaries.toChangeEvents!(Masker._begin, Masker._end, Yes.boundaries); 506 auto eventsAcc = appender!(Masker.MEvent[]); 507 508 static if (hasLength!R1) 509 eventsAcc.reserve(2 * intervals.length); 510 static if (hasLength!R2) 511 eventsAcc.reserve(2 * boundaries.length); 512 513 chain(changeEvents, boundaryEvents).copy(eventsAcc); 514 515 eventsAcc.data.sort(); 516 517 mask.addEvents(eventsAcc.data); 518 519 return mask; 520 } 521 522 /// Masker can be used to compute the intersection of two masks. 523 unittest 524 { 525 alias Interval = Tuple!(size_t, "begin", size_t, "end"); 526 527 auto mask = masker!( 528 "a.begin", 529 "a.end", 530 level => level >= 2 ? 1 : 0, 531 )( 532 [ 533 Interval(1, 5), 534 Interval(6, 7), 535 Interval(9, 10), 536 ], 537 [Interval(0, 10)] 538 ); 539 540 alias I = mask.FrontType; 541 assert(equal(mask.save, [I(0, 10, 0)])); 542 543 auto intersection1 = mask.withAdditionalIntervals([Interval(4, 7)]); 544 assert(equal( 545 intersection1, 546 [ 547 I(0, 4, 0), 548 I(4, 5, 1), 549 I(5, 6, 0), 550 I(6, 7, 1), 551 I(7, 10, 0), 552 ] 553 ), investigateMask(mask, "mask does not match")); 554 555 auto intersection2 = mask.withAdditionalIntervals([Interval(8, 10)]); 556 assert(equal( 557 intersection2, 558 [ 559 I(0, 9, 0), 560 I(9, 10, 1), 561 ] 562 ), investigateMask(mask, "mask does not match")); 563 } 564 565 unittest 566 { 567 alias Interval = Tuple!(size_t, "begin", size_t, "end", size_t, "tag"); 568 569 auto mask = masker!( 570 "a.begin", 571 "a.end", 572 level => level >= 2 ? 1 : 0, 573 (a, b) => b.tag > 0 ? b.tag : a, 574 size_t, 575 )( 576 [ 577 new Interval(1, 5, 0), 578 new Interval(6, 7, 0), 579 new Interval(9, 10, 0), 580 ], 581 [new Interval(0, 10, 0)] 582 ); 583 584 alias I = mask.FrontType; 585 assert(equal(mask.save, [I(0, 10, 0, 0)]), investigateMask(mask, "mask does not match")); 586 587 auto intersection = mask.withAdditionalIntervals([ 588 new Interval(4, 7, 1), 589 new Interval(8, 10, 2), 590 ]); 591 assert(equal( 592 intersection, 593 [ 594 I(0, 4, 0, 0), 595 I(4, 5, 1, 1), 596 I(5, 6, 0, 1), 597 I(6, 7, 1, 1), 598 I(7, 9, 0, 2), 599 I(9, 10, 1, 2), 600 ] 601 ), investigateMask(intersection, "mask does not match")); 602 } 603 604 605 /// Exchange `category` function reusing the precalculated data. 606 Masker withCategory(alias category, Masker)(Masker mask) 607 if (__traits(isSame, TemplateOf!Masker, MaskerImpl)) 608 { 609 return MaskerImpl!( 610 Masker.MEvent, 611 Masker._begin, 612 Masker._end, 613 category, 614 Masker.hasRefElements, 615 Masker.acc, 616 Masker.acc_t, 617 )(mask.originalEvents); 618 } 619 620 621 /// Exchange `acc` function reusing the precalculated data. 622 Masker withAcc(alias acc, acc_t, Masker)(Masker mask) 623 if (__traits(isSame, TemplateOf!Masker, MaskerImpl)) 624 { 625 return MaskerImpl!( 626 Masker.MEvent, 627 Masker._begin, 628 Masker._end, 629 Masker._category, 630 Masker.hasRefElements, 631 acc, 632 acc_t, 633 )(mask.originalEvents); 634 } 635 636 637 private auto toChangeEvents(alias _begin, alias _end, Flag!"boundaries" boundaries, R)(R range) @trusted 638 { 639 return range 640 .map!(makeEvents!(_begin, _end, boundaries, ElementType!R)) 641 .joiner 642 .filter!(event => event.type != event_t.ignore); 643 } 644 645 646 auto makeEvents(alias _begin, alias _end, Flag!"boundaries" boundaries, E)(E element) @safe 647 { 648 alias pos_t = typeof(_begin(E.init)); 649 650 static if (isPointer!E) 651 { 652 alias MEvent = MaskerEvent!(pos_t, E); 653 alias _ref = (element) => element; 654 } 655 else 656 { 657 alias MEvent = MaskerEvent!(pos_t, void*); 658 alias _ref = (element) => null; 659 } 660 661 static if (boundaries) 662 { 663 static enum openEventType = event_t.boundaryOpen; 664 static enum closeEventType = event_t.boundaryClose; 665 } 666 else 667 { 668 static enum openEventType = event_t.open; 669 static enum closeEventType = event_t.close; 670 } 671 672 auto begin = _begin(element); 673 auto end = _end(element); 674 675 enforce(begin <= end, "interval must not end before it begins"); 676 677 if (begin < end) 678 return only( 679 MEvent(begin, openEventType, _ref(element)), 680 MEvent(end, closeEventType, _ref(element)), 681 ); 682 else 683 return only(MEvent(), MEvent()); 684 } 685 686 687 private enum event_t : byte 688 { 689 ignore = 0, 690 boundaryOpen = 1, 691 open = 2, 692 close = -2, 693 boundaryClose = -1, 694 } 695 static assert(event_t.init == event_t.ignore); 696 697 698 private alias MaskerEvent(pos_t, E) = Tuple!( 699 pos_t, "pos", 700 event_t, "type", 701 E, "elementPtr", 702 ); 703 704 705 private struct MaskerImpl( 706 _MEvent, 707 alias __begin, 708 alias __end, 709 alias __category, 710 bool _hasRefElements, 711 alias _acc, 712 _acc_t, 713 ) 714 { 715 alias MEvent = _MEvent; 716 alias _begin = __begin; 717 alias _end = __end; 718 alias hasRefElements = _hasRefElements; 719 alias acc = _acc; 720 alias acc_t = _acc_t; 721 alias _category = unaryFun!__category; 722 alias category_t = typeof(_category(size_t.init)); 723 alias pos_t = typeof(MEvent.init.pos); 724 alias ElementRef = typeof(MEvent.init.elementPtr); 725 enum hasAcc = !is(typeof(acc) == typeof(null)); 726 727 static struct FrontType 728 { 729 pos_t begin; 730 pos_t end; 731 category_t category; 732 733 static if (hasAcc) 734 acc_t acc; 735 } 736 737 alias Events = typeof(merge(MEvent[].init, MEvent[].init)); 738 739 MEvent[] originalEvents; 740 Events events; 741 private FrontType _front; 742 private size_t _level; 743 private bool _empty; 744 745 746 this(MEvent[] events, MEvent[] additionalEvents = []) 747 { 748 this.originalEvents = events; 749 this.events = merge(events, additionalEvents); 750 popFront(); 751 } 752 753 754 private void addEvents(MEvent[] additionalEvents) 755 { 756 auto originalEvents = this.originalEvents; 757 this = typeof(this)(originalEvents, additionalEvents); 758 } 759 760 761 void popFront() 762 { 763 assert(!empty, "Attempting to popFront an empty " ~ typeof(this).stringof); 764 765 if (events.empty) 766 return setEmpty(); 767 768 _front.begin = currentEvent.type == event_t.boundaryOpen 769 ? currentEvent.pos 770 : _front.end; 771 772 static if (hasAcc) 773 _front.acc = acc_t.init; 774 775 _front.category = currentCategory; 776 777 auto endEvent = popUntilNextCategory(); 778 _front.end = endEvent.pos; 779 780 // skip empty mask intervals 781 if (_front.begin == _front.end) 782 popFront(); 783 } 784 785 786 private MEvent popUntilNextCategory() 787 { 788 auto _currentCategory = currentCategory; 789 MEvent event; 790 static if (hasAcc) 791 auto accLevel = size_t.max; 792 793 while (!events.empty) 794 { 795 event = events.front; 796 797 final switch (event.type) 798 { 799 case event_t.boundaryOpen: 800 assert(_level == 0, "level must be zero at boundary begin"); 801 break; 802 case event_t.open: 803 static if (hasAcc) 804 setAccumulate(event.elementPtr); 805 ++_level; 806 break; 807 case event_t.close: 808 assert(_level > 0, "level must not drop below zero"); 809 --_level; 810 static if (hasAcc) 811 accumulateClosedInterval(event.elementPtr); 812 break; 813 case event_t.boundaryClose: 814 assert(_level == 0, "level must drop to zero at boundary end"); 815 break; 816 case event_t.ignore: 817 assert(0); 818 } 819 820 821 static if (hasAcc) 822 { 823 if (accLevel < size_t.max && _category(_level) == _currentCategory) 824 accLevel = size_t.max; 825 else if ( 826 accLevel == size_t.max && 827 event.type == event_t.open && 828 _category(_level) != _currentCategory 829 ) 830 accLevel = _level - 1; 831 } 832 833 events.popFront(); 834 835 if ( 836 event.type == event_t.boundaryClose || 837 ( 838 _category(_level) != _currentCategory && 839 (events.empty || event.pos != events.front.pos) 840 ) 841 ) 842 break; 843 } 844 845 static if (hasAcc) 846 accumulateStillOpenIntervals(min(accLevel, _level)); 847 848 assert( 849 !events.empty || _level == 0, 850 "premature end of events", 851 ); 852 853 return event; 854 } 855 856 857 private @property MEvent currentEvent() 858 { 859 return events.front; 860 } 861 862 863 private @property category_t currentCategory() const 864 { 865 return _category(_level); 866 } 867 868 869 static if (hasAcc) 870 { 871 private Appender!(ElementRef[]) _accElements; 872 873 874 private void setAccumulate(ElementRef elementPtr) pure nothrow @safe 875 { 876 _accElements ~= elementPtr; 877 } 878 879 880 private void accumulateStillOpenIntervals(size_t level) 881 { 882 foreach_reverse (accElementPtr; _accElements.data[0 .. level]) 883 accumulate(accElementPtr); 884 } 885 886 887 private void accumulateClosedInterval(ElementRef elementPtr) 888 { 889 auto elementIdx = _accElements.data.countUntil(elementPtr); 890 assert(elementIdx >= 0); 891 892 accumulate(elementPtr); 893 894 _accElements.data.swapAt(elementIdx, _accElements.data.length - 1); 895 _accElements.shrinkTo(_accElements.data.length - 1); 896 897 assert( 898 _accElements.data.length == _level, 899 "number of accumulated elements must match current level", 900 ); 901 } 902 903 904 private void accumulateClosedIntervals() 905 { 906 foreach_reverse (accElementPtr; _accElements.data[_level .. $]) 907 accumulate(accElementPtr); 908 909 _accElements.shrinkTo(_level); 910 } 911 912 913 private void discardClosedIntervals() 914 { 915 _accElements.shrinkTo(_level); 916 } 917 918 919 private void accumulate(ElementRef accElementPtr) 920 { 921 static if (hasRefElements) 922 alias callAcc = () => binaryFun!acc(_front.acc, accElementPtr); 923 else 924 alias callAcc = () => unaryFun!acc(_front.acc); 925 926 if (is(ReturnType!callAcc == void)) 927 callAcc(); 928 else 929 _front.acc = callAcc(); 930 } 931 } 932 933 934 private void setEmpty() pure nothrow @safe 935 { 936 _empty = true; 937 } 938 939 940 @property bool empty() const pure nothrow @safe 941 { 942 return _empty; 943 } 944 945 946 @property auto front() pure nothrow @safe 947 { 948 assert(!empty, "Attempting to fetch the front of an empty " ~ typeof(this).stringof); 949 950 return _front; 951 } 952 953 954 @property typeof(this) save() 955 { 956 return this; 957 } 958 959 960 this(this) 961 { 962 this.events = this.events.save; 963 static if (hasAcc) 964 this._accElements = appender(this._accElements.data.dup); 965 } 966 } 967 968 969 /// Returns a range of all points where the coverage level changes. 970 auto coverageChanges(Masker)(Masker mask) if (__traits(isSame, TemplateOf!Masker, MaskerImpl)) 971 { 972 return CoverageChangesImpl!(Masker.MEvent)(mask.originalEvents); 973 } 974 975 976 private struct CoverageChangesImpl(MEvent) 977 { 978 alias pos_t = typeof(MEvent.init.pos); 979 980 static struct FrontType 981 { 982 pos_t pos; 983 size_t level; 984 } 985 986 MEvent[] events; 987 private FrontType _front; 988 989 990 this(MEvent[] events) 991 { 992 this.events = events; 993 994 popFront(); 995 } 996 997 998 void popFront() 999 { 1000 assert(!empty, "Attempting to popFront an empty " ~ typeof(this).stringof); 1001 1002 if (events.empty) 1003 return setEmpty(); 1004 1005 _front.pos = events.front.pos; 1006 1007 while (!events.empty) 1008 { 1009 auto event = events.front; 1010 1011 final switch (event.type) 1012 { 1013 case event_t.boundaryOpen: 1014 assert(_front.level == 0, "level must be zero at boundary begin"); 1015 break; 1016 case event_t.open: 1017 ++_front.level; 1018 break; 1019 case event_t.close: 1020 assert(_front.level > 0, "level must not drop below zero"); 1021 --_front.level; 1022 break; 1023 case event_t.boundaryClose: 1024 assert(_front.level == 0, "level must drop to zero at boundary end"); 1025 break; 1026 case event_t.ignore: 1027 assert(0); 1028 } 1029 1030 events.popFront(); 1031 1032 if ( 1033 event.type == event_t.boundaryClose || 1034 events.empty || 1035 event.pos != events.front.pos 1036 ) 1037 { 1038 break; 1039 } 1040 } 1041 1042 assert(!events.empty || _front.level == 0, "level must drop to zero eventually"); 1043 } 1044 1045 1046 private void setEmpty() pure nothrow @safe 1047 { 1048 _front.level = size_t.max; 1049 } 1050 1051 1052 @property bool empty() const pure nothrow @safe 1053 { 1054 return _front.level == size_t.max; 1055 } 1056 1057 1058 @property auto front() pure nothrow @safe 1059 { 1060 assert(!empty, "Attempting to fetch the front of an empty " ~ typeof(this).stringof); 1061 1062 return _front; 1063 } 1064 1065 1066 @property typeof(this) save() 1067 { 1068 return this; 1069 } 1070 }