1 /******************************************************************************* 2 3 Simple integer range struct with various comparison functions. 4 5 Note that the range template currently only supports unsigned integer types. 6 It would be possible to extend it to also work with signed and/or floating 7 point types. 8 9 Copyright: 10 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 11 All rights reserved. 12 13 License: 14 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 15 Alternatively, this file may be distributed under the terms of the Tango 16 3-Clause BSD License (see LICENSE_BSD.txt for details). 17 18 *******************************************************************************/ 19 20 module ocean.math.Range; 21 22 23 24 25 import ocean.transition; 26 import ocean.core.Verify; 27 28 version ( UnitTest ) 29 { 30 import ocean.text.convert.Formatter; 31 import ocean.core.Test; 32 } 33 34 35 36 /******************************************************************************* 37 38 Range struct template 39 40 *******************************************************************************/ 41 42 public struct Range ( T ) 43 { 44 import ocean.meta.traits.Basic : isUnsignedIntegerType; 45 import ocean.core.Array; 46 47 static assert(isUnsignedIntegerType!(T), 48 "Range only works with unsigned integer types"); 49 50 import ocean.core.Enforce : enforce; 51 52 /*************************************************************************** 53 54 The `This` alias for the type of this struct 55 56 ***************************************************************************/ 57 58 import ocean.transition: TypeofThis, assumeUnique; 59 mixin TypeofThis!(); 60 61 /*************************************************************************** 62 63 Min & max values when range is empty (magic values). 64 65 ***************************************************************************/ 66 67 private enum T null_min = T.max; 68 private enum T null_max = T.min; 69 70 71 /*************************************************************************** 72 73 Min & max values, default to the empty range. 74 75 ***************************************************************************/ 76 77 private T min_ = null_min; 78 private T max_ = null_max; 79 80 81 /*************************************************************************** 82 83 Helper structure for sortEndpoints function. This is used to provide 84 detailed information about the relative positions of endpoints in a 85 sequence of ranges. 86 87 ***************************************************************************/ 88 89 private static struct RangeEndpoint 90 { 91 /*********************************************************************** 92 93 Value of the endpoint: may be either min or max of the underlying 94 range. 95 96 ***********************************************************************/ 97 98 T value; 99 100 /*********************************************************************** 101 102 Index of the owner range in the sequence of range arguments 103 provided to sortEndpoints. 104 105 ***********************************************************************/ 106 107 ubyte owner_index; 108 109 version ( UnitTest ) 110 { 111 // useful for test!("==") 112 public istring toString () 113 { 114 return format("<{}|{}>", (&this).value, cast(char)('A' + (&this).owner_index)); 115 } 116 } 117 } 118 119 120 /*************************************************************************** 121 122 Checks whether the specified range is empty. 123 124 Params: 125 min = minimum value 126 max = maximum value 127 128 Returns: 129 true if the range is empty (null) 130 131 ***************************************************************************/ 132 133 static public bool isEmpty ( T min, T max ) 134 { 135 return min == null_min && max == null_max; 136 } 137 138 unittest 139 { 140 test(This.isEmpty(null_min, null_max)); 141 test(!This.isEmpty(null_max, null_min)); 142 test(!This.isEmpty(1, null_max)); 143 test(!This.isEmpty(null_min, 1)); 144 test(!This.isEmpty(1, 1)); 145 test(!This.isEmpty(1, 2)); 146 test(!This.isEmpty(2, 1)); 147 } 148 149 150 /*************************************************************************** 151 152 Checks whether the specified range is the full range of T. 153 154 Params: 155 min = minimum value 156 max = maximum value 157 158 Returns: 159 true if the range is full, i.e. min == T.min and max == T.max. 160 161 ***************************************************************************/ 162 163 static public bool isFullRange ( T min, T max ) 164 { 165 return min == T.min && max == T.max; 166 } 167 168 unittest 169 { 170 test(This.isFullRange(T.min, T.max)); 171 test(!This.isFullRange(T.max, T.min)); 172 test(!This.isFullRange(1, T.max)); 173 test(!This.isFullRange(T.min, 1)); 174 test(!This.isFullRange(1, 1)); 175 test(!This.isFullRange(1, 2)); 176 test(!This.isFullRange(2, 1)); 177 } 178 179 180 /*************************************************************************** 181 182 Checks whether the specified range is valid. 183 184 Params: 185 min = minimum value 186 max = maximum value 187 188 Returns: 189 true if the range is valid (min <= max or empty) 190 191 ***************************************************************************/ 192 193 static public bool isValid ( T min, T max ) 194 { 195 return min <= max || This.isEmpty(min, max); 196 } 197 198 unittest 199 { 200 test(This.isValid(null_min, null_max)); 201 test(This.isValid(0, 0)); 202 test(This.isValid(0, 1)); 203 test(This.isValid(T.max, T.max)); 204 test(!This.isValid(1, 0)); 205 } 206 207 208 /*************************************************************************** 209 210 The range must always be valid. 211 212 ***************************************************************************/ 213 214 invariant() 215 { 216 assert(This.isValid((&this).min_, (&this).max_)); 217 } 218 219 version ( UnitTest ) 220 { 221 public istring toString() 222 { 223 auto msg = format("{}({}, {}", This.stringof, (&this).min_, (&this).max_); 224 225 if ((&this).is_empty) 226 { 227 msg ~= " empty"; 228 } 229 else if ((&this).is_full_range) 230 { 231 msg ~= " full"; 232 } 233 234 msg ~= ')'; 235 236 return assumeUnique(msg); 237 } 238 } 239 240 241 /*************************************************************************** 242 243 Static opCall. Disables the default "constructor", with the advantage 244 that the invariant is run after calling this method, making it 245 impossible to construct invalid instances. 246 247 Params: 248 min = minimum value of range 249 max = maximum value of range 250 251 Returns: 252 new Range instance 253 254 Throws: 255 if min and max do not describe a valid range (see isValid) 256 257 ***************************************************************************/ 258 259 public static This opCall ( T min, T max ) 260 out(result) 261 { 262 assert(&result); 263 } 264 body 265 { 266 enforce(This.isValid(min, max)); 267 268 This r; 269 r.min_ = min; 270 r.max_ = max; 271 return r; 272 } 273 274 275 /*************************************************************************** 276 277 Range factory which provides extended wrapper to opCall. It returns 278 empty range when min > max or when it is impossible to respect 279 the specified boundaries. 280 281 Params: 282 boundaries = string which denotes which kind of boundaries 283 will be provided. Square "[" bracket denotes inclusive 284 boundary, round "$(LPAREN)" one denotes exclusive boundary 285 min = minimum value of range 286 max = maximum value of range 287 288 Returns: 289 new Range instance 290 291 ***************************************************************************/ 292 293 public static This makeRange ( istring boundaries = "[]" ) ( T min, T max ) 294 out(result) 295 { 296 assert(&result); 297 } 298 body 299 { 300 static assert(boundaries == "[]" || boundaries == "[)" 301 || boundaries == "(]" || boundaries == "()", 302 "only four kinds of range are supported: [], [), (], ()"); 303 304 if ( min > max ) 305 return This.init; 306 307 static if (boundaries != "[]") 308 { 309 if (min == max) 310 { 311 return This.init; 312 } 313 } 314 315 static if (boundaries == "()") 316 { 317 if (min + 1 == max) 318 { 319 return This.init; 320 } 321 } 322 323 static if (boundaries[0] == '(') 324 { 325 verify(min < T.max); 326 ++min; 327 } 328 329 static if (boundaries[1] == ')') 330 { 331 verify(max > T.min); 332 --max; 333 } 334 335 assert(min <= max); 336 337 return This(min, max); 338 } 339 340 unittest 341 { 342 test!("==")(This(3, 7), This.makeRange!("[]")(3, 7)); 343 test!("==")(This(3, 7), This.makeRange(3, 7)); 344 test!("==")(This(5, 5), This.makeRange(5, 5)); 345 test!("==")(This.init, This.makeRange(7, 3)); 346 test!("==")(This(0, 0), This.makeRange(0, 0)); 347 test!("==")(This(T.max, T.max), This.makeRange(T.max, T.max)); 348 test!("==")(This(0, T.max), This.makeRange(0, T.max)); 349 test!("==")(This.init, This.makeRange(T.max, 0)); 350 351 test!("==")(This(3, 6), This.makeRange!("[)")(3, 7)); 352 test!("==")(This.init, This.makeRange!("[)")(5, 5)); 353 test!("==")(This(4, 4), This.makeRange!("[)")(4, 5)); 354 test!("==")(This.init, This.makeRange!("[)")(7, 3)); 355 test!("==")(This.init, This.makeRange!("[)")(0, 0)); 356 test!("==")(This.init, This.makeRange!("[)")(T.max, T.max)); 357 test!("==")(This(0, T.max - 1), This.makeRange!("[)")(0, T.max)); 358 test!("==")(This.init, This.makeRange!("[)")(T.max, 0)); 359 test!("==")(This(0, 0), This.makeRange!("[)")(0, 1)); 360 test!("==")(This(T.max - 1, T.max - 1), This.makeRange!("[)")(T.max - 1, T.max)); 361 362 test!("==")(This(4, 7), This.makeRange!("(]")(3, 7)); 363 test!("==")(This.init, This.makeRange!("(]")(5, 5)); 364 test!("==")(This(5, 5), This.makeRange!("(]")(4, 5)); 365 test!("==")(This.init, This.makeRange!("(]")(7, 3)); 366 test!("==")(This.init, This.makeRange!("(]")(0, 0)); 367 test!("==")(This.init, This.makeRange!("(]")(T.max, T.max)); 368 test!("==")(This(1, T.max), This.makeRange!("(]")(0, T.max)); 369 test!("==")(This.init, This.makeRange!("(]")(T.max, 0)); 370 test!("==")(This(1, 1), This.makeRange!("(]")(0, 1)); 371 test!("==")(This(T.max, T.max), This.makeRange!("(]")(T.max - 1, T.max)); 372 373 test!("==")(This(4, 6), This.makeRange!("()")(3, 7)); 374 test!("==")(This.init, This.makeRange!("()")(5, 5)); 375 test!("==")(This.init, This.makeRange!("()")(4, 5)); 376 test!("==")(This(5, 5), This.makeRange!("()")(4, 6)); 377 test!("==")(This.init, This.makeRange!("()")(7, 3)); 378 test!("==")(This.init, This.makeRange!("()")(0, 0)); 379 test!("==")(This.init, This.makeRange!("()")(T.max, T.max)); 380 test!("==")(This(1, T.max - 1), This.makeRange!("()")(0, T.max)); 381 test!("==")(This.init, This.makeRange!("()")(T.max, 0)); 382 test!("==")(This.init, This.makeRange!("()")(0, 1)); 383 test!("==")(This.init, This.makeRange!("()")(T.max - 1, T.max)); 384 test!("==")(This(1, 1), This.makeRange!("()")(0, 2)); 385 test!("==")(This(T.max - 1, T.max - 1), This.makeRange!("()")(T.max - 2, T.max)); 386 } 387 388 389 /*************************************************************************** 390 391 Returns: 392 the minimum value of the range 393 394 ***************************************************************************/ 395 396 public T min ( ) 397 { 398 return (&this).min_; 399 } 400 401 402 /*************************************************************************** 403 404 Returns: 405 the maximum value of the range 406 407 ***************************************************************************/ 408 409 public T max ( ) 410 { 411 return (&this).max_; 412 } 413 414 415 /*************************************************************************** 416 417 Sets the minimum value of the range. 418 419 Params: 420 min = new minimum value 421 422 Returns: 423 The newly set value which was given as parameter 424 425 ***************************************************************************/ 426 427 public T min ( T min ) 428 { 429 return (&this).min_ = min; 430 } 431 432 433 /*************************************************************************** 434 435 Sets the maximum value of the range. 436 437 Params: 438 max = new maximum value 439 440 Returns: 441 The newly set value which was given as parameter 442 443 ***************************************************************************/ 444 445 public T max ( T max ) 446 { 447 return (&this).max_ = max; 448 } 449 450 451 /*************************************************************************** 452 453 Returns: 454 true if the range is empty (null) 455 456 ***************************************************************************/ 457 458 public bool is_empty ( ) 459 { 460 return This.isEmpty((&this).min_, (&this).max_); 461 } 462 463 464 /*************************************************************************** 465 466 Returns: 467 true if this instance covers the full range of hash values 468 469 ***************************************************************************/ 470 471 public bool is_full_range ( ) 472 { 473 return This.isFullRange((&this).min_, (&this).max_); 474 } 475 476 477 /*************************************************************************** 478 479 Note that in non-release builds, the struct invariant ensures that 480 instances are always valid. This method can be called by user code to 481 explicitly check the validity of a range, for example when creating a 482 range from run-time data. 483 484 Returns: 485 true if the range is valid (min < max, or empty) 486 487 ***************************************************************************/ 488 489 public bool is_valid ( ) 490 { 491 return This.isValid((&this).min_, (&this).max_); 492 } 493 494 495 /*************************************************************************** 496 497 Returns: 498 the number of values in the range 499 500 Throws: 501 Exception if the full range is covered, i.e. `this.is_full_range` is 502 true. (This is to prevent an integer overflow.) 503 504 ***************************************************************************/ 505 506 public size_t length ( ) 507 { 508 enforce(!(&this).is_full_range, This.stringof ~ ".length(): full range"); 509 510 if ( (&this).is_empty ) return 0; 511 512 return ((&this).max_ - (&this).min_) + 1; 513 } 514 515 unittest 516 { 517 test!("==")(This.init.length, 0); 518 test!("==")(This(0, 0).length, 1); 519 test!("==")(This(5, 5).length, 1); 520 test!("==")(This(0, 1).length, 2); 521 test!("==")(This(5, 10).length, 6); 522 } 523 524 525 /*************************************************************************** 526 527 Predicate that checks whether the specified value is inside this range. 528 529 Params: 530 x = value to check 531 532 Returns: 533 true if this range includes x, false otherwise 534 535 ***************************************************************************/ 536 537 public bool contains ( T x ) 538 { 539 if ((&this).is_empty) 540 return false; 541 542 return (&this).min_ <= x && x <= (&this).max_; 543 } 544 545 unittest 546 { 547 // empty 548 test(!This.init.contains(0), "Empty range can't contain any value"); 549 test(!This.init.contains(17), "Empty range can't contain any value"); 550 test(!This.init.contains(T.max), "Empty range can't contain any value"); 551 552 // one point 553 test(This(0, 0).contains(0), "One point range should contain this point"); 554 test(This(17, 17).contains(17), "One point range should contain this point"); 555 test(This(T.max, T.max).contains(T.max), "One point range should contain this point"); 556 557 test(!This(0, 0).contains(1), "One point range can't contain other point"); 558 test(!This(17, 17).contains(16), "One point range can't contain other point"); 559 test(!This(T.max, T.max).contains(T.max - 1), "One point range can't contain other point"); 560 561 // more-point 562 test(!This(3, 24).contains(2), "This can't contain outside point"); 563 test(This(3, 24).contains(3), "This should contain boundary point"); 564 test(This(3, 24).contains(11), "This should contain inner point"); 565 test(This(3, 24).contains(24), "This should contain boundary point"); 566 test(!This(3, 24).contains(25), "This can't contain outside point"); 567 } 568 569 570 /*************************************************************************** 571 572 Checks whether the specified range is exactly identical to this range. 573 574 Params: 575 other = instance to compare this with 576 577 Returns: 578 true if both ranges are identical 579 580 ***************************************************************************/ 581 582 public equals_t opEquals ( This other ) 583 { 584 return (&this).min_ == other.min && (&this).max_ == other.max_; 585 } 586 587 unittest 588 { 589 // empty == empty 590 test!("==")(This.init, This.init); 591 592 // empty != a 593 test!("!=")(This.init, This(0, 1)); 594 595 // a != empty 596 test!("!=")(This(0, 1), This.init); 597 598 // a == b 599 test!("==")(This(0, 1), This(0, 1)); 600 601 // a != b 602 test!("!=")(This(0, 1), This(1, 2)); 603 } 604 605 /*************************************************************************** 606 607 Compares this instance with rhs. An empty range is considered to be < 608 all non-empty ranges. Otherwise, the comparison always considers the 609 range's minimum value before comparing the maximum value. 610 611 Params: 612 rhs = instance to compare with this 613 614 Returns: 615 a value less than 0 if this < rhs, 616 a value greater than 0 if this > rhs 617 or 0 if this == rhs. 618 619 ***************************************************************************/ 620 621 mixin (genOpCmp( 622 `{ 623 auto _this = cast(Unqual!(typeof(this))) this; 624 auto _rhs = cast(Unqual!(typeof(rhs))) rhs; 625 626 if ( _this.is_empty ) return _rhs.is_empty ? 0 : -1; 627 if ( _rhs.is_empty ) return 1; 628 629 if ( _this.min_ < _rhs.min_ ) return -1; 630 if ( _rhs.min_ < _this.min_ ) return 1; 631 assert(_this.min_ == _rhs.min_); 632 if ( _this.max_ < _rhs.max_ ) return -1; 633 if ( _rhs.max_ < _this.max_ ) return 1; 634 return 0; 635 }`)); 636 637 unittest 638 { 639 // empty < smallest range 640 test!("<")(This.init, This(0, 0)); 641 642 // smallest range, empty 643 test!(">")(This(0, 0), This.init); 644 645 // a, b 646 test!("<")(This(0, 1), This(2, 3)); 647 648 // a, b 649 test!(">")(This(2, 3), This(0, 1)); 650 651 // a, b (overlapping) 652 test!("<")(This(0, 1), This(1, 2)); 653 654 // a, b (overlapping) 655 test!(">")(This(1, 2), This(0, 1)); 656 657 // a, b and a.min == b.min 658 test!("<")(This(1, 3), This(1, 5)); 659 660 // a, b and a.min == b.min 661 test!(">")(This(1, 5), This(1, 3)); 662 } 663 664 665 /*************************************************************************** 666 667 Determines whether this instance is non-empty subset of the specified 668 range. All values in this range must be within the other range. 669 670 Note: For practical reasons, this isn't conforming strictly to 671 the mathematical definition, where an empty set is considered to be 672 a subset of any set. However, two equal ranges will be considered 673 to be subsets of one another. 674 675 Params: 676 other = instance to compare with this 677 678 Returns: 679 true if this range is a subset of the other range 680 681 ***************************************************************************/ 682 683 public bool isSubsetOf ( This other ) 684 { 685 if ( (&this).is_empty || other.is_empty ) 686 return false; 687 688 return (&this).min_ >= other.min_ && (&this).max_ <= other.max_; 689 } 690 691 unittest 692 { 693 // empty 694 test(!This.init.isSubsetOf(This(0, 10)), "Empty range doesn't count as subset"); 695 test(!This(0, 10).isSubsetOf(This.init), "Empty range can't be superset"); 696 697 // very proper subset 698 test(This(1, 9).isSubsetOf(This(0, 10))); 699 700 // equal 701 test(This(0, 10).isSubsetOf(This(0, 10)), "Equal range is a subset too"); 702 703 // ends touch, inside 704 test(This(0, 9).isSubsetOf(This(0, 10))); 705 test(This(1, 10).isSubsetOf(This(0, 10))); 706 707 // ends touch, outside 708 test(!This(0, 5).isSubsetOf(This(5, 10))); 709 test(!This(10, 15).isSubsetOf(This(5, 10))); 710 711 // very proper superset 712 test(!This(0, 10).isSubsetOf(This(1, 9)), "Proper superset can't be subset"); 713 714 // overlap 715 test(!This(0, 10).isSubsetOf(This(5, 15))); 716 717 // no overlap 718 test(!This(5, 10).isSubsetOf(This(15, 20))); 719 } 720 721 /*************************************************************************** 722 723 Determines whether this instance is a superset of the non-empty 724 specified range. All values in the other range must be within this range. 725 726 Note: For practical reasons, this isn't conforming strictly to 727 the mathematical definition, where an empty set is considered to be 728 a subset of any set. However, two equal ranges will be considered 729 to be supersets of one another. 730 731 Params: 732 other = instance to compare with this 733 734 Returns: 735 true if this range is a superset of the other range 736 737 ***************************************************************************/ 738 739 public bool isSupersetOf ( This other ) 740 { 741 return other.isSubsetOf(this); 742 } 743 744 unittest 745 { 746 // empty 747 test(!This.init.isSupersetOf(This(0, 10)), "Empty range can't be superset"); 748 test(!This(0, 10).isSupersetOf(This.init), "Empty range doesn't count as subset"); 749 750 // very proper superset 751 test(This(0, 10).isSupersetOf(This(1, 9))); 752 753 // equal 754 test(This(0, 10).isSupersetOf(This(0, 10)), "Equal range is a superset too"); 755 756 // ends touch, inside 757 test(This(0, 10).isSupersetOf(This(0, 9))); 758 test(This(0, 10).isSupersetOf(This(1, 10))); 759 760 // ends touch, outside 761 test(!This(5, 10).isSupersetOf(This(0, 5))); 762 test(!This(5, 10).isSupersetOf(This(10, 15))); 763 764 // very proper subset 765 test(!This(1, 9).isSupersetOf(This(0, 10)), "Proper subset can't be superset"); 766 767 // overlap 768 test(!This(0, 10).isSupersetOf(This(5, 15))); 769 770 // no overlap 771 test(!This(5, 10).isSupersetOf(This(15, 20))); 772 } 773 774 /*************************************************************************** 775 776 Predicate that checks whether the provided array of ranges exactly 777 tessellates this range. The term "tessellation" means that this 778 range is a union of the given ranges and that the given ranges form 779 a contiguous chain without gap or overlap. 780 781 It is assumed that the array is already sorted. 782 783 Params: 784 ranges = a sorted array of This!T 785 786 Returns: 787 true if this instance is tessellated by the given array 788 of ranges, false otherwise 789 790 ***************************************************************************/ 791 792 public bool isTessellatedBy ( This[] ranges ) 793 { 794 return (*(&this) == extent(ranges)) && isContiguous(ranges); 795 } 796 797 unittest 798 { 799 // minimal case: one range, test covers and not-covers 800 test(This(0, 0).isTessellatedBy([This(0, 0)])); 801 test(!This(0, 0).isTessellatedBy([This(1, 1)])); 802 803 // tessellation by itself 804 test(This(3, 12).isTessellatedBy([This(3, 12)]), "Any range should tessellate itself"); 805 806 // proper subset or proper superset can't be tessellation 807 test(!This(3, 12).isTessellatedBy([This(4, 11)]), "Proper superset can't be tessellation"); 808 test(!This(3, 12).isTessellatedBy([This(3, 11)]), "Proper superset can't be tessellation"); 809 test(!This(3, 12).isTessellatedBy([This(4, 12)]), "Proper superset can't be tessellation"); 810 test(!This(3, 12).isTessellatedBy([This(2, 13)]), "Proper subset can't be tessellation"); 811 test(!This(3, 12).isTessellatedBy([This(3, 13)]), "Proper subset can't be tessellation"); 812 test(!This(3, 12).isTessellatedBy([This(2, 12)]), "Proper subset can't be tessellation"); 813 814 // complete 815 test(This(0, 10).isTessellatedBy([This(0, 1), 816 This(2, 5), 817 This(6, 10)])); 818 819 // missing start 820 test(!This(0, 10).isTessellatedBy([This(1, 1), 821 This(2, 5), 822 This(6, 10)])); 823 824 // missing middle 825 test(!This(0, 10).isTessellatedBy([This(0, 1), 826 This(3, 5), 827 This(6, 10)])); 828 829 // missing end 830 test(!This(0, 10).isTessellatedBy([This(0, 1), 831 This(2, 5), 832 This(6, 9)])); 833 834 // overlapped ranges in list 835 test(!This(0, 10).isTessellatedBy([This(0, 2), 836 This(2, 5), 837 This(6, 10)])); 838 839 // empty ranges skipped 840 This empty; 841 test(This(0, 10).isTessellatedBy([empty, 842 empty, 843 This(0, 1), 844 This(2, 5), 845 This(6, 10)])); 846 847 // union of empty ranges and empty list 848 test(!This(0, 10).isTessellatedBy([empty, 849 empty, 850 empty])); 851 test(!This(0, 10).isTessellatedBy([empty])); 852 test(!This(0, 10).isTessellatedBy([])); 853 test(!This(0, 10).isTessellatedBy(null)); 854 } 855 856 857 /*************************************************************************** 858 859 Predicate that checks whether this range is covered by the given array 860 of ranges (i.e. whether it is a subset of the union of the array 861 of ranges). 862 863 It is assumed that the array is already sorted. 864 865 Params: 866 ranges = a sorted array of This!T to be checked 867 that covers this instance 868 869 Returns: 870 true if this range instance is covered by the given array of ranges, 871 false otherwise 872 873 ***************************************************************************/ 874 875 public bool isCoveredBy ( This[] ranges ) 876 { 877 return (&this).isSubsetOf(extent(ranges)) && !hasGap(ranges); 878 } 879 880 unittest 881 { 882 // minimal case: one hash range, test covers and not-covers 883 test(This(0, 0).isCoveredBy([This(0, 0)])); 884 test(!This(0, 0).isCoveredBy([This(1, 1)])); 885 886 // coverage by itself 887 test(This(3, 12).isCoveredBy([This(3, 12)]), "Any range should cover itself"); 888 889 // any superset can be coverage 890 test(This(3, 12).isCoveredBy([This(3, 13)]), "Proper superset should be coverage"); 891 test(This(3, 12).isCoveredBy([This(2, 12)]), "Proper superset should be coverage"); 892 test(This(3, 12).isCoveredBy([This(2, 13)]), "Proper superset should be coverage"); 893 894 // any subset can't be coverage 895 test(!This(3, 12).isCoveredBy([This(3, 11)]), "Proper subset can't be coverage"); 896 test(!This(3, 12).isCoveredBy([This(4, 12)]), "Proper subset can't be coverage"); 897 test(!This(3, 12).isCoveredBy([This(4, 11)]), "Proper subset can't be coverage"); 898 899 // a tessellation is a coverage 900 test(This(3, 12).isCoveredBy([This(3, 5), This(6, 12)])); 901 902 // overlap allowed 903 test(This(3, 12).isCoveredBy([This(3, 7), This(4, 12)])); 904 test(This(3, 12).isCoveredBy([This(1, 7), This(4, 15)])); 905 906 // gap not allowed 907 test(!This(3, 12).isCoveredBy([This(3, 5), This(7, 12)])); 908 test(!This(3, 12).isCoveredBy([This(1, 5), This(7, 15)])); 909 910 // empty ranges skipped 911 This empty; 912 test(This(0, 10).isCoveredBy([empty, 913 empty, 914 This(0, 3), 915 This(2, 5), 916 This(6, 11)])); 917 918 // union of empty ranges and empty list 919 test(!This(0, 10).isCoveredBy([empty, 920 empty, 921 empty])); 922 test(!This(0, 10).isCoveredBy([empty])); 923 test(!This(0, 10).isCoveredBy([])); 924 test(!This(0, 10).isCoveredBy(null)); 925 } 926 927 928 /*************************************************************************** 929 930 Special unittest which checks that isTessellatedBy implies isCoveredBy 931 (but isCoveredBy does not necessarily imply isTessellatedBy). 932 933 ***************************************************************************/ 934 935 unittest 936 { 937 // Note that given two logical conditions A and B, 938 // "A implies B" is equivalent to (A == true) <= (B == true) 939 940 auto target = This(12, 17); 941 This[] ranges; 942 943 // neither tessellated nor covered 944 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 945 946 ranges ~= [This(1, 5)]; 947 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 948 ranges.length = 0; 949 enableStomping(ranges); 950 951 ranges ~= [This(12, 15)]; 952 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 953 ranges.length = 0; 954 enableStomping(ranges); 955 956 ranges ~= [This(14, 17)]; 957 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 958 ranges.length = 0; 959 enableStomping(ranges); 960 961 ranges ~= [This(18, 25)]; 962 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 963 ranges.length = 0; 964 enableStomping(ranges); 965 966 ranges ~= [This(1, 5), This(19, 20)]; 967 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 968 ranges.length = 0; 969 enableStomping(ranges); 970 971 ranges ~= [This(1, 13), This(16, 20)]; 972 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 973 ranges.length = 0; 974 enableStomping(ranges); 975 976 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 977 978 // covered, but not tessellated 979 ranges ~= [This(11, 17)]; 980 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 981 ranges.length = 0; 982 enableStomping(ranges); 983 984 ranges ~= [This(12, 18)]; 985 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 986 ranges.length = 0; 987 enableStomping(ranges); 988 989 ranges ~= [This(11, 18)]; 990 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 991 ranges.length = 0; 992 enableStomping(ranges); 993 994 ranges ~= [This(1, 15), This(14, 20)]; 995 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 996 ranges.length = 0; 997 enableStomping(ranges); 998 999 ranges ~= [This(12, 15), This(15, 17)]; 1000 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 1001 ranges.length = 0; 1002 enableStomping(ranges); 1003 1004 ranges ~= [This(12, 16), This(14, 17)]; 1005 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 1006 ranges.length = 0; 1007 enableStomping(ranges); 1008 1009 // tessellated 1010 ranges ~= [This(12, 17)]; 1011 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 1012 ranges.length = 0; 1013 enableStomping(ranges); 1014 1015 ranges ~= [This(12, 14), This(15, 17)]; 1016 test!("<=")(target.isTessellatedBy(ranges), target.isCoveredBy(ranges)); 1017 ranges.length = 0; 1018 enableStomping(ranges); 1019 } 1020 1021 1022 /*************************************************************************** 1023 1024 Calculates the number of values shared by this range and the other range 1025 specified. 1026 1027 Params: 1028 other = instance to compare with this 1029 1030 Returns: 1031 the number of values shared by the two ranges 1032 1033 Throws: 1034 Exception if both this instance and other cover the full range, i.e. 1035 `this.is_full_range && other.full_range` is true. (This is to 1036 prevent an integer overflow.) 1037 1038 ***************************************************************************/ 1039 1040 public size_t overlapAmount ( Range other ) 1041 { 1042 enforce(!((&this).is_full_range && other.is_full_range), 1043 This.stringof ~ ".overlapAmount(): both ranges are full"); 1044 1045 if ( (&this).is_empty || other.is_empty ) return 0; 1046 1047 RangeEndpoint[4] a; 1048 This.sortEndpoints(this, other, a); 1049 1050 return a[0].owner_index != a[1].owner_index 1051 ? This(a[1].value, a[2].value).length : 0; 1052 } 1053 1054 unittest 1055 { 1056 // empty 1057 test!("==")(This.init.overlapAmount(This.init), 0); 1058 test!("==")(This.init.overlapAmount(This(0, 10)), 0); 1059 test!("==")(This(0, 10).overlapAmount(This.init), 0); 1060 1061 // empty vs. full 1062 test!("==")(This(T.min, T.max).overlapAmount(This.init), 0); 1063 test!("==")(This.init.overlapAmount(This(T.min, T.max)), 0); 1064 1065 // full 1066 testThrown!()(Range(T.min, T.max).overlapAmount(Range(T.min, T.max))); 1067 1068 // equal 1069 test!("==")(This(0, 10).overlapAmount(This(0, 10)), 11); 1070 1071 // proper subset 1072 test!("==")(This(0, 10).overlapAmount(This(1, 9)), 9); 1073 1074 // proper superset 1075 test!("==")(This(1, 9).overlapAmount(This(0, 10)), 9); 1076 1077 // proper superset of the full range 1078 test!("==")(This(1, 10).overlapAmount(This(T.min, T.max)), 10); 1079 test!("==")(This(T.min, T.max).overlapAmount(This(1, 10)), 10); 1080 1081 // ends touch 1082 test!("==")(This(0, 10).overlapAmount(This(10, 20)), 1); 1083 test!("==")(This(10, 20).overlapAmount(This(0, 10)), 1); 1084 1085 // subset + ends touch 1086 test!("==")(This(0, 10).overlapAmount(This(0, 9)), 10); 1087 test!("==")(This(0, 10).overlapAmount(This(1, 10)), 10); 1088 1089 // superset + ends touch 1090 test!("==")(This(0, 9).overlapAmount(This(0, 10)), 10); 1091 test!("==")(This(1, 10).overlapAmount(This(0, 10)), 10); 1092 1093 // overlaps 1094 test!("==")(This(0, 10).overlapAmount(This(9, 20)), 2); 1095 test!("==")(This(10, 20).overlapAmount(This(0, 11)), 2); 1096 1097 // no overlap 1098 test!("==")(This(0, 10).overlapAmount(This(11, 20)), 0); 1099 test!("==")(This(10, 20).overlapAmount(This(0, 9)), 0); 1100 } 1101 1102 1103 /*************************************************************************** 1104 1105 Checks whether this range shares any values with the other range 1106 specified. 1107 1108 Params: 1109 other = instance to compare with this 1110 1111 Returns: 1112 true if the two ranges share any values 1113 1114 ***************************************************************************/ 1115 1116 public bool overlaps ( This other ) 1117 { 1118 if ( (&this).is_empty || other.is_empty ) return false; 1119 1120 return !(other.max_ < (&this).min_ || other.min > (&this).max_); 1121 } 1122 1123 unittest 1124 { 1125 // empty 1126 test(!This.init.overlaps(This.init)); 1127 test(!This.init.overlaps(This(0, 10))); 1128 test(!This(0, 10).overlaps(This.init)); 1129 1130 // equal 1131 test(This(0, 10).overlaps(This(0, 10))); 1132 1133 // proper subset 1134 test(This(0, 10).overlaps(This(1, 9))); 1135 1136 // proper superset 1137 test(This(1, 9).overlaps(This(0, 10))); 1138 1139 // ends touch 1140 test(This(0, 10).overlaps(This(10, 20))); 1141 test(This(10, 20).overlaps(This(0, 10))); 1142 1143 // subset + ends touch 1144 test(This(0, 10).overlaps(This(0, 9))); 1145 test(This(0, 10).overlaps(This(1, 10))); 1146 1147 // superset + ends touch 1148 test(This(0, 9).overlaps(This(0, 10))); 1149 test(This(1, 10).overlaps(This(0, 10))); 1150 1151 // overlaps 1152 test(This(0, 10).overlaps(This(9, 20))); 1153 test(This(10, 20).overlaps(This(0, 11))); 1154 1155 // no overlap 1156 test(!This(0, 10).overlaps(This(11, 20))); 1157 test(!This(10, 20).overlaps(This(0, 9))); 1158 } 1159 1160 1161 /*************************************************************************** 1162 1163 Subtracts the specified range from this range, returning the remaining 1164 range(s) via the out parameters. Two separate ranges can result from a 1165 subtraction if the range being subtracted bisects the range being 1166 subtracted from, like: 1167 1168 subtract ------ 1169 from -------------- 1170 remainder ---- ---- 1171 1172 Params: 1173 other = range to subtract from this 1174 lower = lower output range. If only a single range results from the 1175 subtraction, it will be returned via this parameter 1176 upper = upper output range. Only set when the subtraction results in 1177 two ranges 1178 1179 ***************************************************************************/ 1180 1181 public void subtract ( This other, out This lower, out This upper ) 1182 { 1183 // this empty -- empty result 1184 if ( (&this).is_empty ) return; 1185 1186 // other empty -- no change 1187 if ( other.is_empty ) 1188 { 1189 lower = this; 1190 return; 1191 } 1192 1193 RangeEndpoint[4] a; 1194 This.sortEndpoints(this, other, a); 1195 1196 // no overlap 1197 if (a[0].owner_index == a[1].owner_index) 1198 { 1199 lower = this; 1200 return; 1201 } 1202 1203 auto first = a[0].owner_index < a[1].owner_index 1204 ? This.makeRange!("[)")(a[0].value, a[1].value) : This.init; 1205 auto second = a[2].owner_index > a[3].owner_index 1206 ? This.makeRange!("(]")(a[2].value, a[3].value) : This.init; 1207 1208 if (first.is_empty) 1209 { 1210 lower = second; 1211 } 1212 else 1213 { 1214 lower = first; 1215 upper = second; 1216 } 1217 } 1218 1219 unittest 1220 { 1221 static void testSubtract ( This r1, This r2, 1222 This l_expected, This u_expected = This.init, 1223 istring file = __FILE__, int line = __LINE__ ) 1224 { 1225 This l, u; 1226 r1.subtract(r2, l, u); 1227 test!("==")(l, l_expected, file, line); 1228 test!("==")(u, u_expected, file, line); 1229 } 1230 1231 // empty 1232 testSubtract(This.init, This.init, This.init); 1233 testSubtract(This.init, This(0, 0), This.init); 1234 testSubtract(This(0, 0), This.init, This(0, 0)); 1235 1236 // equal 1237 testSubtract(This(0, 0), This(0, 0), This.init); 1238 testSubtract(This(T.max, T.max), This(T.max, T.max), This.init); 1239 testSubtract(This(0, 10), This(0, 10), This.init); 1240 testSubtract(This(0, T.max), This(0, T.max), This.init); 1241 1242 // superset 1243 testSubtract(This(1, 9), This(0, 10), This.init); 1244 1245 // subset 1246 testSubtract(This(0, 10), This(1, 9), This(0, 0), This(10, 10)); 1247 testSubtract(This(0, 10), This(5, 5), This(0, 4), This(6, 10)); 1248 1249 // no overlap 1250 testSubtract(This(0, 10), This (11, 20), This(0, 10)); 1251 testSubtract(This(11, 20), This (0, 10), This(11, 20)); 1252 1253 // ends touch 1254 testSubtract(This(10, 20), This(0, 10), This(11, 20)); 1255 testSubtract(This(10, 20), This(20, 30), This(10, 19)); 1256 1257 // overlap 1258 testSubtract(This(5, 15), This(0, 10), This(11, 15)); 1259 testSubtract(This(5, 15), This(5, 10), This(11, 15)); 1260 testSubtract(This(5, 15), This(10, 20), This(5, 9)); 1261 testSubtract(This(5, 15), This(10, 15), This(5, 9)); 1262 } 1263 1264 1265 /*************************************************************************** 1266 1267 Helper function used by overlapAmount and subtract. Calculates a 1268 specially sorted static array of RangeEndpoint values corresponding 1269 to the endpoints of the two non-empty ranges 'first' and 'second' 1270 provided as input. The sorting is stable (i.e. initial order of 1271 equal values is preserved). 1272 1273 The owner_index values of the RangeEndpoints correspond to the first 1274 and second parameters, so e.g. if a given endpoint comes from the 1275 first range, its owner_index will be 0; if from the second, it will 1276 be 1. 1277 1278 Note: the sort will preserve the order {second.min, first.max} if 1279 their values are equal. 1280 1281 Note: In D2 it may be better to rewrite this function to: 1282 RangeEndpoint[4] sortEndpoints ( This first, This second ) 1283 1284 Params: 1285 first = the first of the two Ranges 1286 second = the second of the two Ranges 1287 array = (preferably static) array of 4 RangeEndpoints, 1288 which will be filled with the sorted endpoints 1289 of the first and second ranges 1290 1291 ***************************************************************************/ 1292 1293 private static void sortEndpoints ( This first, This second, 1294 RangeEndpoint[] array ) 1295 { 1296 verify(!first.is_empty); 1297 verify(!second.is_empty); 1298 verify(array.length == 4); 1299 1300 // N.B! the initial order is sufficient 1301 // being that stable sort preserve order of equal elements 1302 array[0] = RangeEndpoint(first.min_, 0); 1303 array[1] = RangeEndpoint(second.min_, 1); 1304 array[2] = RangeEndpoint(first.max_, 0); 1305 array[3] = RangeEndpoint(second.max_, 1); 1306 1307 // stable insert sort 1308 for (size_t i = 1; i < array.length; ++i) 1309 { 1310 auto pivot_index = i; 1311 auto pivot = array[pivot_index]; 1312 while (pivot_index > 0 && array[pivot_index - 1].value > pivot.value) 1313 { 1314 array[pivot_index] = array[pivot_index - 1]; 1315 --pivot_index; 1316 } 1317 array[pivot_index] = pivot; 1318 } 1319 } 1320 1321 unittest 1322 { 1323 RangeEndpoint[] a; 1324 a.length = 4; 1325 1326 // no overlap 1327 This.sortEndpoints(This(0, 10), This(15, 20), a); 1328 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(10, 0), 1329 RangeEndpoint(15, 1), RangeEndpoint(20, 1)][]); 1330 This.sortEndpoints(This(15, 20), This(0, 10), a); 1331 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(10, 1), 1332 RangeEndpoint(15, 0), RangeEndpoint(20, 0)][]); 1333 1334 // overlap 1335 This.sortEndpoints(This(0, 15), This(10, 20), a); 1336 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(10, 1), 1337 RangeEndpoint(15, 0), RangeEndpoint(20, 1)][]); 1338 This.sortEndpoints(This(10, 20), This(0, 15), a); 1339 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(10, 0), 1340 RangeEndpoint(15, 1), RangeEndpoint(20, 0)][]); 1341 1342 // outer touch 1343 This.sortEndpoints(This(0, 10), This(10, 20), a); 1344 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(10, 1), 1345 RangeEndpoint(10, 0), RangeEndpoint(20, 1)][]); 1346 This.sortEndpoints(This(10, 20), This(0, 10), a); 1347 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(10, 0), 1348 RangeEndpoint(10, 1), RangeEndpoint(20, 0)][]); 1349 1350 // inner touch 1351 This.sortEndpoints(This(0, 10), This(5, 10), a); 1352 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(5, 1), 1353 RangeEndpoint(10, 0), RangeEndpoint(10, 1)][]); 1354 This.sortEndpoints(This(5, 10), This(0, 10), a); 1355 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(5, 0), 1356 RangeEndpoint(10, 0), RangeEndpoint(10, 1)][]); 1357 This.sortEndpoints(This(0, 10), This(0, 5), a); 1358 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(0, 1), 1359 RangeEndpoint(5, 1), RangeEndpoint(10, 0)][]); 1360 This.sortEndpoints(This(0, 5), This(0, 10), a); 1361 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(0, 1), 1362 RangeEndpoint(5, 0), RangeEndpoint(10, 1)][]); 1363 1364 // ultra proper subrange 1365 This.sortEndpoints(This(0, 10), This(3, 7), a); 1366 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(3, 1), 1367 RangeEndpoint(7, 1), RangeEndpoint(10, 0)][]); 1368 This.sortEndpoints(This(3, 7), This(0, 10), a); 1369 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(3, 0), 1370 RangeEndpoint(7, 0), RangeEndpoint(10, 1)][]); 1371 1372 // equal 1373 This.sortEndpoints(This(0, 10), This(0, 10), a); 1374 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(0, 1), 1375 RangeEndpoint(10, 0), RangeEndpoint(10, 1)][]); 1376 This.sortEndpoints(This(5, 5), This(5, 5), a); 1377 test!("==")(a, [RangeEndpoint(5, 0), RangeEndpoint(5, 1), 1378 RangeEndpoint(5, 0), RangeEndpoint(5, 1)][]); 1379 1380 // one point range 1381 This.sortEndpoints(This(4, 4), This(5, 5), a); 1382 test!("==")(a, [RangeEndpoint(4, 0), RangeEndpoint(4, 0), 1383 RangeEndpoint(5, 1), RangeEndpoint(5, 1)][]); 1384 This.sortEndpoints(This(5, 5), This(4, 4), a); 1385 test!("==")(a, [RangeEndpoint(4, 1), RangeEndpoint(4, 1), 1386 RangeEndpoint(5, 0), RangeEndpoint(5, 0)][]); 1387 This.sortEndpoints(This(5, 5), This(0, 10), a); 1388 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(5, 0), 1389 RangeEndpoint(5, 0), RangeEndpoint(10, 1)][]); 1390 This.sortEndpoints(This(0, 10), This(5, 5), a); 1391 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(5, 1), 1392 RangeEndpoint(5, 1), RangeEndpoint(10, 0)][]); 1393 This.sortEndpoints(This(5, 5), This(5, 10), a); 1394 test!("==")(a, [RangeEndpoint(5, 0), RangeEndpoint(5, 1), 1395 RangeEndpoint(5, 0), RangeEndpoint(10, 1)][]); 1396 This.sortEndpoints(This(5, 10), This(5, 5), a); 1397 test!("==")(a, [RangeEndpoint(5, 0), RangeEndpoint(5, 1), 1398 RangeEndpoint(5, 1), RangeEndpoint(10, 0)][]); 1399 This.sortEndpoints(This(5, 5), This(0, 5), a); 1400 test!("==")(a, [RangeEndpoint(0, 1), RangeEndpoint(5, 0), 1401 RangeEndpoint(5, 0), RangeEndpoint(5, 1)][]); 1402 This.sortEndpoints(This(0, 5), This(5, 5), a); 1403 test!("==")(a, [RangeEndpoint(0, 0), RangeEndpoint(5, 1), 1404 RangeEndpoint(5, 0), RangeEndpoint(5, 1)][]); 1405 } 1406 } 1407 1408 1409 1410 /******************************************************************************* 1411 1412 Unittest to instantiate the Range template with all supported types, in turn 1413 running the unittests for each of them. 1414 1415 *******************************************************************************/ 1416 1417 unittest 1418 { 1419 Range!(ubyte) br; 1420 Range!(ushort) sr; 1421 Range!(ulong) lr; 1422 } 1423 1424 1425 /******************************************************************************* 1426 1427 Predicate that checks for the existence of one or more gaps 1428 in an array of Range!T. 1429 1430 It is assumed that the array is already sorted. All empty ranges are ignored. 1431 1432 Params: 1433 ranges = a sorted array of Range!T to be checked 1434 1435 Returns: 1436 true if at least one gap exists in the array 1437 1438 *******************************************************************************/ 1439 1440 public bool hasGap ( T ) ( Range!(T)[] ranges ) 1441 { 1442 trimEmptyRanges(ranges); 1443 1444 if (ranges.length > 0) 1445 { 1446 auto current_threshold = ranges[0].max_; 1447 1448 for (size_t i = 1; i < ranges.length; ++i) 1449 { 1450 if (ranges[i].min_ > current_threshold + 1) 1451 return true; 1452 1453 if (ranges[i].max_ > current_threshold) 1454 current_threshold = ranges[i].max_; 1455 } 1456 } 1457 1458 return false; 1459 } 1460 1461 unittest 1462 { 1463 // contiguous 1464 test(!hasGap([Range!(uint)(1, 5), 1465 Range!(uint)(6, 12), 1466 Range!(uint)(13, 15)]), "Contiguous ranges can't have gap"); 1467 1468 // overlap, but no gaps 1469 test(!hasGap([Range!(uint)(1, 5), 1470 Range!(uint)(3, 14), 1471 Range!(uint)(13, 15)])); 1472 test(!hasGap([Range!(uint)(1, 12), 1473 Range!(uint)(4, 7), 1474 Range!(uint)(13, 15)])); 1475 test(!hasGap([Range!(uint)(1, 13), 1476 Range!(uint)(4, 7), 1477 Range!(uint)(13, 15)])); 1478 test(!hasGap([Range!(uint)(1, 14), 1479 Range!(uint)(4, 7), 1480 Range!(uint)(13, 15)])); 1481 1482 // gap 1483 test(hasGap([Range!(uint)(1, 11), 1484 Range!(uint)(4, 7), 1485 Range!(uint)(13, 15)])); 1486 1487 // two equal range 1488 test(!hasGap([Range!(uint)(3, 17), 1489 Range!(uint)(3, 17)])); 1490 1491 // any count of empty ranges has no effect 1492 test(!hasGap([Range!(uint).init, 1493 Range!(uint)(1, 13), 1494 Range!(uint)(4, 7), 1495 Range!(uint)(13, 15)])); 1496 test(!hasGap([Range!(uint).init, 1497 Range!(uint)(1, 14), 1498 Range!(uint)(4, 7), 1499 Range!(uint)(13, 15)])); 1500 test(hasGap([Range!(uint).init, 1501 Range!(uint)(1, 11), 1502 Range!(uint)(4, 7), 1503 Range!(uint)(13, 15)])); 1504 test(!hasGap([Range!(uint).init, 1505 Range!(uint).init, 1506 Range!(uint)(1, 14), 1507 Range!(uint)(4, 7), 1508 Range!(uint)(13, 15)])); 1509 test(hasGap([Range!(uint).init, 1510 Range!(uint).init, 1511 Range!(uint)(1, 11), 1512 Range!(uint)(4, 7), 1513 Range!(uint)(13, 15)])); 1514 1515 // any combination of empty sets has no gaps 1516 test(!hasGap!(uint)(null)); 1517 test(!hasGap!(uint)([])); 1518 test(!hasGap([Range!(uint).init])); 1519 test(!hasGap([Range!(uint).init, 1520 Range!(uint).init])); 1521 test(!hasGap([Range!(uint).init, 1522 Range!(uint).init, 1523 Range!(uint).init])); 1524 } 1525 1526 1527 /******************************************************************************* 1528 1529 Predicate that checks for the existence of overlaps in array of Range!T. 1530 1531 It is assumed that the array is already sorted. All empty ranges are ignored. 1532 1533 Params: 1534 ranges = a sorted array of Range!T to be checked 1535 1536 Returns: 1537 true if at least one overlap exists in the array 1538 1539 *******************************************************************************/ 1540 1541 public bool hasOverlap ( T ) ( Range!(T)[] ranges ) 1542 { 1543 trimEmptyRanges(ranges); 1544 1545 if (ranges.length > 0) 1546 { 1547 auto current_threshold = ranges[0].max_; 1548 1549 for (size_t i = 1; i < ranges.length; ++i) 1550 { 1551 if (ranges[i].min_ <= current_threshold) 1552 return true; 1553 1554 if (ranges[i].max_ > current_threshold) 1555 current_threshold = ranges[i].max_; 1556 } 1557 } 1558 1559 return false; 1560 } 1561 1562 unittest 1563 { 1564 // contiguous 1565 test(!hasOverlap([Range!(uint)(1, 5), 1566 Range!(uint)(6, 12), 1567 Range!(uint)(13, 15)]), "Contiguous ranges can't overlap"); 1568 1569 // one common point 1570 test(hasOverlap([Range!(uint)(1, 5), 1571 Range!(uint)(5, 12), 1572 Range!(uint)(13, 15)])); 1573 test(hasOverlap([Range!(uint)(1, 5), 1574 Range!(uint)(6, 13), 1575 Range!(uint)(13, 15)])); 1576 1577 // overlap range 1578 test(hasOverlap([Range!(uint)(1, 5), 1579 Range!(uint)(3, 14), 1580 Range!(uint)(13, 15)])); 1581 1582 // has gap 1583 test(!hasOverlap([Range!(uint)(1, 4), 1584 Range!(uint)(6, 12), 1585 Range!(uint)(13, 15)])); 1586 test(hasOverlap([Range!(uint)(1, 4), 1587 Range!(uint)(6, 13), 1588 Range!(uint)(13, 15)])); 1589 test(hasOverlap([Range!(uint)(1, 4), 1590 Range!(uint)(6, 14), 1591 Range!(uint)(13, 15)])); 1592 1593 // the first range mask the second 1594 test(hasOverlap([Range!(uint)(1, 12), 1595 Range!(uint)(6, 8), 1596 Range!(uint)(13, 15)])); 1597 // the second range mask the first 1598 test(hasOverlap([Range!(uint)(3, 8), 1599 Range!(uint)(3, 12), 1600 Range!(uint)(13, 15)])); 1601 1602 // equal 1603 test(hasOverlap([Range!(uint)(3, 17), 1604 Range!(uint)(3, 17)])); 1605 1606 // any count of empty ranges has no effect 1607 test(!hasOverlap([Range!(uint).init, 1608 Range!(uint)(1, 5), 1609 Range!(uint)(6, 12), 1610 Range!(uint)(13, 15)])); 1611 test(hasOverlap([Range!(uint).init, 1612 Range!(uint)(1, 5), 1613 Range!(uint)(5, 12), 1614 Range!(uint)(13, 15)])); 1615 test(!hasOverlap([Range!(uint).init, 1616 Range!(uint).init, 1617 Range!(uint)(1, 5), 1618 Range!(uint)(6, 12), 1619 Range!(uint)(13, 15)])); 1620 test(hasOverlap([Range!(uint).init, 1621 Range!(uint).init, 1622 Range!(uint)(1, 5), 1623 Range!(uint)(5, 12), 1624 Range!(uint)(13, 15)])); 1625 1626 // any combination of empty sets has no overlaps 1627 test(!hasOverlap!(uint)(null)); 1628 test(!hasOverlap!(uint)([])); 1629 test(!hasOverlap([Range!(uint).init])); 1630 test(!hasOverlap([Range!(uint).init, 1631 Range!(uint).init])); 1632 test(!hasOverlap([Range!(uint).init, 1633 Range!(uint).init, 1634 Range!(uint).init])); 1635 } 1636 1637 /******************************************************************************* 1638 1639 Predicate that checks contiguity of the array of Range!T. 1640 1641 This function's result is equivalent to !hasGap && !hasOverlap. There is 1642 a special unittest which asserts this (see below). It has been implemented 1643 as a separate function because a more efficient implementation is possible. 1644 1645 It is assumed that the array is already sorted in lexicographical 1646 order: first check left boundaries of ranges if equal then right boundaries 1647 will be checked (that is current status quo of opCmp). All empty ranges 1648 are ignored. 1649 1650 Params: 1651 ranges = a sorted array of Range!T to be checked 1652 1653 Returns: 1654 true if collection is contiguous 1655 1656 *******************************************************************************/ 1657 1658 public bool isContiguous ( T ) ( Range!(T)[] ranges ) 1659 { 1660 trimEmptyRanges(ranges); 1661 1662 for (size_t i = 1; i < ranges.length; ++i) 1663 { 1664 if (ranges[i].min_ != ranges[i - 1].max_ + 1) 1665 return false; 1666 } 1667 1668 return true; 1669 } 1670 1671 unittest 1672 { 1673 // contiguous 1674 test(isContiguous([Range!(uint)(1, 5), 1675 Range!(uint)(6, 12), 1676 Range!(uint)(13, 15)])); 1677 1678 // one common point 1679 test(!isContiguous([Range!(uint)(1, 5), 1680 Range!(uint)(5, 12), 1681 Range!(uint)(13, 15)])); 1682 test(!isContiguous([Range!(uint)(1, 5), 1683 Range!(uint)(6, 13), 1684 Range!(uint)(13, 15)])); 1685 1686 // gap 1687 test(!isContiguous([Range!(uint)(1, 4), 1688 Range!(uint)(6, 12), 1689 Range!(uint)(13, 15)])); 1690 test(!isContiguous([Range!(uint)(1, 5), 1691 Range!(uint)(6, 11), 1692 Range!(uint)(13, 15)])); 1693 1694 // gap and common point 1695 test(!isContiguous([Range!(uint)(1, 4), 1696 Range!(uint)(6, 13), 1697 Range!(uint)(13, 15)])); 1698 1699 // two equal range 1700 test(!isContiguous([Range!(uint)(6, 13), 1701 Range!(uint)(6, 13)])); 1702 1703 // any count of empty ranges has no effect 1704 test(isContiguous([Range!(uint).init, 1705 Range!(uint)(1, 5), 1706 Range!(uint)(6, 12), 1707 Range!(uint)(13, 15)])); 1708 test(!isContiguous([Range!(uint).init, 1709 Range!(uint)(1, 5), 1710 Range!(uint)(6, 13), 1711 Range!(uint)(13, 15)])); 1712 test(!isContiguous([Range!(uint).init, 1713 Range!(uint)(1, 4), 1714 Range!(uint)(6, 12), 1715 Range!(uint)(13, 15)])); 1716 test(!isContiguous([Range!(uint).init, 1717 Range!(uint)(1, 4), 1718 Range!(uint)(6, 13), 1719 Range!(uint)(13, 15)])); 1720 test(isContiguous([Range!(uint).init, 1721 Range!(uint).init, 1722 Range!(uint)(1, 5), 1723 Range!(uint)(6, 12), 1724 Range!(uint)(13, 15)])); 1725 1726 // any combination of empty sets is contiguous 1727 test(isContiguous!(uint)(null)); 1728 test(isContiguous!(uint)([])); 1729 test(isContiguous([Range!(uint).init])); 1730 test(isContiguous([Range!(uint).init, 1731 Range!(uint).init])); 1732 test(isContiguous([Range!(uint).init, 1733 Range!(uint).init, 1734 Range!(uint).init])); 1735 } 1736 1737 1738 /******************************************************************************* 1739 1740 Special unittest which checks that: 1741 isContiguous <=> !hasGap && !hasOverlap 1742 1743 *******************************************************************************/ 1744 1745 unittest 1746 { 1747 Range!(uint)[] ranges; 1748 1749 // ranges is null 1750 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1751 1752 // contiguous ranges 1753 ranges ~= [Range!(uint)(1, 5), Range!(uint)(6, 12), Range!(uint)(13, 15)]; 1754 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1755 ranges.length = 0; 1756 enableStomping(ranges); 1757 1758 // overlap 1759 ranges ~= [Range!(uint)(1, 5), Range!(uint)(6, 13), Range!(uint)(13, 15)]; 1760 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1761 ranges.length = 0; 1762 enableStomping(ranges); 1763 1764 // gap 1765 ranges ~= [Range!(uint)(1, 4), Range!(uint)(6, 12), Range!(uint)(13, 15)]; 1766 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1767 ranges.length = 0; 1768 enableStomping(ranges); 1769 1770 // gap and overlap 1771 ranges ~= [Range!(uint)(1, 4), Range!(uint)(6, 13), Range!(uint)(13, 15)]; 1772 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1773 ranges.length = 0; 1774 enableStomping(ranges); 1775 1776 // range.length == 0 1777 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1778 1779 // only empty ranges 1780 ranges ~= Range!(uint).init; 1781 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1782 ranges ~= Range!(uint).init; 1783 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1784 ranges ~= Range!(uint).init; 1785 test!("==")(isContiguous(ranges), !hasGap(ranges) && !hasOverlap(ranges)); 1786 } 1787 1788 1789 /******************************************************************************* 1790 1791 Generate a single Range!T that covers the entire set of values found 1792 in an array of Range!T, i.e. whose min, max values reflect the smallest 1793 and largest min and max found in the array. 1794 1795 It is assumed that the array is sorted already in lexicographical order: 1796 first compare the left boundaries of the range, if they are equal then 1797 the right boundaries will be compared (that is current status quo of opCmp). 1798 All empty ranges are ignored. 1799 1800 Note: Although this method assumes sorted input, it would be possible 1801 to provide another implementation without this assumption. 1802 However, such an implementation would be more expensive, with 1803 an asymptotic complexity of O(n), whereas this version is O(1). 1804 1805 Params: 1806 ranges = a sorted array of Range!T 1807 1808 Returns: 1809 resulting minimal covering range, or an empty range 1810 if the input array is empty 1811 1812 *******************************************************************************/ 1813 1814 public Range!(T) extent (T) ( Range!(T)[] ranges ) 1815 { 1816 trimEmptyRanges(ranges); 1817 1818 return ranges.length == 0 ? Range!(T).init : Range!(T)(ranges[0].min_, ranges[$ - 1].max_); 1819 } 1820 1821 unittest 1822 { 1823 // one range 1824 test!("==")(extent([Range!(uint)(3, 5)]), Range!(uint)(3, 5)); 1825 1826 // two equal ranges 1827 test!("==")(extent([Range!(uint)(3, 5), 1828 Range!(uint)(3, 5)]), Range!(uint)(3, 5)); 1829 1830 // overlap 1831 test!("==")(extent([Range!(uint)(3, 5), 1832 Range!(uint)(4, 8)]), Range!(uint)(3, 8)); 1833 1834 // gap 1835 test!("==")(extent([Range!(uint)(3, 5), 1836 Range!(uint)(7, 9)]), Range!(uint)(3, 9)); 1837 1838 // gap and overlap 1839 test!("==")(extent([Range!(uint)(3, 5), 1840 Range!(uint)(7, 12), 1841 Range!(uint)(12, 15)]), Range!(uint)(3, 15)); 1842 1843 // the first has the same min as the second 1844 test!("==")(extent([Range!(uint)(3, 5), 1845 Range!(uint)(3, 7)]), Range!(uint)(3, 7)); 1846 1847 // any count of empty ranges has no effect 1848 test!("==")(extent([Range!(uint).init, 1849 Range!(uint)(3, 5)]), Range!(uint)(3, 5)); 1850 test!("==")(extent([Range!(uint).init, 1851 Range!(uint)(3, 5), 1852 Range!(uint)(7, 100)]), Range!(uint)(3, 100)); 1853 test!("==")(extent([Range!(uint).init, 1854 Range!(uint).init, 1855 Range!(uint)(3, 5), 1856 Range!(uint)(7, 100)]), Range!(uint)(3, 100)); 1857 1858 // any combination of empty sets has emty extent 1859 test!("==")(extent!(uint)(null), Range!(uint).init); 1860 test!("==")(extent!(uint)([]), Range!(uint).init); 1861 test!("==")(extent([Range!(uint).init]), Range!(uint).init); 1862 test!("==")(extent([Range!(uint).init, 1863 Range!(uint).init]), Range!(uint).init); 1864 } 1865 1866 1867 /******************************************************************************* 1868 1869 Trims any empty ranges from the start of a sorted array of Range!T. 1870 1871 It is assumed that the array is already sorted, which means all empty ranges 1872 will be at the beginning of the array. 1873 1874 Params: 1875 ranges = sorted array of Range!T from which empties drop out 1876 1877 *******************************************************************************/ 1878 1879 private void trimEmptyRanges ( T ) ( ref Range!(T)[] ranges ) 1880 { 1881 while (ranges.length > 0 && ranges[0].is_empty) 1882 { 1883 ranges = ranges[1 .. $]; 1884 } 1885 } 1886 1887 unittest 1888 { 1889 // empty and non-empty ranges 1890 { 1891 Range!(uint)[] a = [Range!(uint).init, Range!(uint).init, 1892 Range!(uint)(2, 9), Range!(uint)(12, 19)]; 1893 trimEmptyRanges(a); 1894 test!("==")(a, [Range!(uint)(2, 9), Range!(uint)(12, 19)][]); 1895 } 1896 1897 // only non-empty ranges 1898 { 1899 Range!(uint)[] a = [Range!(uint)(2, 9), Range!(uint)(12, 19)]; 1900 trimEmptyRanges(a); 1901 test!("==")(a, [Range!(uint)(2, 9), Range!(uint)(12, 19)][]); 1902 } 1903 1904 // array of empty ranges 1905 { 1906 Range!(uint)[] a = [Range!(uint).init, Range!(uint).init]; 1907 trimEmptyRanges(a); 1908 test!("==")(a.length, 0); 1909 } 1910 1911 // empty array 1912 { 1913 Range!(uint)[] a; 1914 trimEmptyRanges(a); 1915 test!("==")(a.length, 0); 1916 } 1917 }