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