1 /* 2 * Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. 3 * Use of this file is governed by the BSD 3-clause license that 4 * can be found in the LICENSE.txt file in the project root. 5 */ 6 7 module antlr.v4.runtime.misc.IntervalSet; 8 9 import antlr.v4.runtime.TokenConstantDefinition; 10 import antlr.v4.runtime.Vocabulary; 11 import antlr.v4.runtime.misc; 12 import std.algorithm; 13 import std.array; 14 import std.container.rbtree; 15 import std.conv; 16 import std.stdio; 17 18 // Class IntervalSet 19 /** 20 * This class implements the {@link IntSet} backed by a sorted array of 21 * non-overlapping intervals. It is particularly efficient for representing 22 * large collections of numbers, where the majority of elements appear as part 23 * of a sequential range of numbers that are all part of the set. For example, 24 * the set { 1, 2, 3, 4, 7, 8 } may be represented as { [1, 4], [7, 8] }. 25 * 26 * <p> 27 * This class is able to represent sets containing any combination of values in 28 * the range {@link Integer#MIN_VALUE} to {@link Integer#MAX_VALUE} 29 * (inclusive).</p> 30 */ 31 class IntervalSet : IntSet 32 { 33 34 public static IntervalSet COMPLETE_CHAR_SET; 35 36 public static IntervalSet EMPTY_SET; 37 38 private bool readonly; 39 40 /** 41 * The list of sorted, disjoint intervals. 42 */ 43 private Interval[] intervals_; 44 45 public this() 46 { 47 COMPLETE_CHAR_SET = IntervalSet.of(char.min, char.min); 48 COMPLETE_CHAR_SET.setReadonly(true); 49 EMPTY_SET = new IntervalSet(1); 50 EMPTY_SET.clear; 51 EMPTY_SET.setReadonly(true); 52 } 53 54 public this(Interval[] intervals) 55 { 56 this.intervals_ = intervals; 57 } 58 59 public this(IntervalSet set) 60 { 61 this(); 62 addAll(set); 63 } 64 65 public this(int[] els ...) 66 { 67 foreach (int e; els) 68 add(e); 69 } 70 71 /** 72 * Create a set with a single element, el. 73 */ 74 public static IntervalSet of(int a) 75 { 76 IntervalSet s = new IntervalSet(); 77 s.add(a); 78 return s; 79 } 80 81 /** 82 * Create a set with all ints within range [a..b] (inclusive) 83 */ 84 public static IntervalSet of(int a, int b) 85 { 86 IntervalSet s = new IntervalSet(1); 87 s.clear; 88 s.add(a, b); 89 return s; 90 } 91 92 public void clear() 93 { 94 assert(!readonly, "can't alter readonly IntervalSet"); 95 intervals_.length = 0; 96 } 97 98 /** 99 * Add a single element to the set. An isolated element is stored 100 * as a range el..el. 101 * @uml 102 * @override 103 */ 104 public override void add(int el) 105 { 106 assert(!readonly, "can't alter readonly IntervalSet"); 107 add(el, el); 108 } 109 110 /** 111 * Add interval; i.e., add all integers from a to b to set. 112 * If b<a, do nothing. 113 * Keep list in sorted order (by left range value). 114 * If overlap, combine ranges. For example, 115 * If this is {1..5, 10..20}, adding 6..7 yields 116 * {1..5, 6..7, 10..20}. Adding 4..8 yields {1..8, 10..20}. 117 */ 118 public void add(int a, int b) 119 { 120 assert(!readonly, "can't alter readonly IntervalSet"); 121 add(Interval.of(a ,b)); 122 } 123 124 /** 125 * copy on write so we can cache a..a intervals and sets of that 126 */ 127 protected void add(Interval addition) 128 { 129 assert(!readonly, "can't alter readonly IntervalSet"); 130 debug (IntervalSet) 131 writefln("add %1$s to %2$s", addition, intervals_); 132 if (addition.b < addition.a) { 133 return; 134 } 135 // find position in list 136 // Use iterators as we modify list in place 137 foreach (int index, ref el; intervals_) { 138 Interval r = el; 139 if (addition.equals(r)) { 140 return; 141 } 142 if (addition.adjacent(r) || !addition.disjoint(r)) { 143 // next to each other, make a single larger interval 144 Interval bigger = addition.unionInterval(r); 145 el = bigger; 146 // make sure we didn't just create an interval that 147 // should be merged with next interval in list 148 while (++index < intervals_.length) { 149 Interval next = intervals_[index]; 150 if (!bigger.adjacent(next) && bigger.disjoint(next)) { 151 continue; 152 } 153 // if we bump up against or overlap next, merge 154 intervals_ = intervals_.remove(index); 155 // move backwards to what we just set 156 intervals_[--index] = bigger.unionInterval(next); // set to 3 merged ones 157 } 158 return; 159 } 160 161 if (addition.startsBeforeDisjoint(r)) { 162 // insert before r 163 intervals_ = intervals_[0..index] ~ addition ~ 164 intervals_[index..$]; 165 return; 166 } 167 // if disjoint and after r, a future iteration will handle it 168 } 169 // ok, must be after last interval (and disjoint from last interval) 170 // just add it 171 intervals_ ~= addition; 172 } 173 174 public IntervalSet addAll(IntSet set) 175 { 176 if (set is null) { 177 return this; 178 } 179 if (typeid(typeof(set)) == typeid(IntervalSet*)) { 180 IntervalSet other = cast(IntervalSet)set; 181 // walk set and add each interval 182 auto n = other.intervals_.length; 183 for (auto i = 0; i < n; i++) { 184 Interval I = other.intervals_[i]; 185 this.add(I.a,I.b); 186 } 187 } 188 else { 189 foreach (int value; set.toList) { 190 add(value); 191 } 192 } 193 return this; 194 } 195 196 public IntervalSet complement(int minElement, int maxElement) 197 { 198 return this.complement(IntervalSet.of(minElement, maxElement)); 199 } 200 201 /** 202 * {@inheritDoc} 203 */ 204 public IntervalSet complement(IntSet vocabulary) 205 { 206 if (vocabulary is null || vocabulary.isNil) { 207 return null; // nothing in common with null set 208 } 209 IntervalSet vocabularyIS = new IntervalSet(); 210 vocabularyIS.addAll(vocabulary); 211 return vocabularyIS.subtract(this); 212 } 213 214 public IntervalSet complement(IntervalSet vocabulary) 215 { 216 if (vocabulary is null || vocabulary.isNil) { 217 return null; // nothing in common with null set 218 } 219 IntervalSet vocabularyIS = vocabulary; 220 return vocabularyIS.subtract(this); 221 } 222 223 public IntervalSet subtract(IntSet a) 224 { 225 if (!a) { 226 return new IntervalSet(this); 227 } 228 if (cast(IntervalSet)a) { 229 return subtract(this, cast(IntervalSet)a); 230 } 231 232 IntervalSet other = new IntervalSet; 233 other.addAll(a); 234 return subtract(this, other); 235 } 236 237 public IntervalSet or(IntSet a) 238 { 239 IntervalSet o = new IntervalSet(); 240 o.addAll(this); 241 o.addAll(a); 242 return o; 243 } 244 245 public IntervalSet and(IntSet other) 246 { 247 if (other is null ) { //|| !(other instanceof IntervalSet) ) { 248 return null; // nothing in common with null set 249 } 250 251 auto myIntervals = this.intervals_; 252 auto theirIntervals = (cast(IntervalSet)other).intervals_; 253 IntervalSet intersection; 254 auto mySize = myIntervals.length; 255 auto theirSize = theirIntervals.length; 256 int i = 0; 257 int j = 0; 258 // iterate down both interval lists looking for nondisjoint intervals 259 while (i < mySize && j < theirSize) { 260 Interval mine = myIntervals[i]; 261 Interval theirs = theirIntervals[j]; 262 //System.out.println("mine="+mine+" and theirs="+theirs); 263 if (mine.startsBeforeDisjoint(theirs) ) { 264 // move this iterator looking for interval that might overlap 265 i++; 266 } 267 else if ( theirs.startsBeforeDisjoint(mine) ) { 268 // move other iterator looking for interval that might overlap 269 j++; 270 } 271 else if ( mine.properlyContains(theirs) ) { 272 // overlap, add intersection, get next theirs 273 if (intersection is null) { 274 intersection = new IntervalSet(); 275 } 276 intersection.add(mine.intersection(theirs)); 277 j++; 278 } 279 else if (theirs.properlyContains(mine)) { 280 // overlap, add intersection, get next mine 281 if (intersection is null) { 282 intersection = new IntervalSet(); 283 } 284 intersection.add(mine.intersection(theirs)); 285 i++; 286 } 287 else if ( !mine.disjoint(theirs) ) { 288 // overlap, add intersection 289 if (intersection is null) { 290 intersection = new IntervalSet(); 291 } 292 intersection.add(mine.intersection(theirs)); 293 // Move the iterator of lower range [a..b], but not 294 // the upper range as it may contain elements that will collide 295 // with the next iterator. So, if mine=[0..115] and 296 // theirs=[115..200], then intersection is 115 and move mine 297 // but not theirs as theirs may collide with the next range 298 // in thisIter. 299 // move both iterators to next ranges 300 if ( mine.startsAfterNonDisjoint(theirs) ) { 301 j++; 302 } 303 else if ( theirs.startsAfterNonDisjoint(mine) ) { 304 i++; 305 } 306 } 307 } 308 if (intersection is null) { 309 return new IntervalSet(); 310 } 311 return intersection; 312 } 313 314 public bool contains(int el) 315 { 316 foreach (I; intervals_) { 317 int a = I.a; 318 int b = I.b; 319 if (el < a) { 320 break; // list is sorted and el is before this interval; not here 321 } 322 if (el >= a && el <= b) { 323 return true; // found in this interval 324 } 325 } 326 return false; 327 } 328 329 public bool isNil() 330 { 331 return intervals_ is null || intervals_.length == 0; 332 } 333 334 public int getSingleElement() 335 { 336 if (intervals_ !is null && intervals_.length == 1 ) { 337 Interval I = intervals_[0]; 338 if (I.a == I.b) { 339 return I.a; 340 } 341 } 342 return TokenConstantDefinition.INVALID_TYPE; 343 } 344 345 /** 346 * Returns the maximum value contained in the set. 347 * 348 * @return the maximum value contained in the set. If the set is empty, this 349 * method returns {@link Token#INVALID_TYPE}. 350 */ 351 public int getMaxElement() 352 { 353 if (isNil) { 354 return TokenConstantDefinition.INVALID_TYPE; 355 } 356 Interval last = intervals_[$-1]; 357 return last.b; 358 } 359 360 /** 361 * Returns the minimum value contained in the set. 362 * 363 * @return the minimum value contained in the set. If the set is empty, this 364 * method returns {@link Token#INVALID_TYPE}. 365 */ 366 public int getMinElement() 367 { 368 if (isNil) { 369 return TokenConstantDefinition.INVALID_TYPE; 370 } 371 return intervals_[0].a; 372 } 373 374 /** 375 * combine all sets in the array returned the or'd value 376 */ 377 public static IntervalSet or(IntervalSet[] sets) 378 { 379 IntervalSet r = new IntervalSet(1); 380 r.clear; 381 foreach (IntervalSet s; sets) { 382 r.addAll(s); 383 } 384 return r; 385 } 386 387 /** 388 * Compute the set difference between two interval sets. The specific 389 * operation is {@code left - right}. If either of the input sets is 390 * {@code null}, it is treated as though it was an empty set. 391 */ 392 public IntervalSet subtract(IntervalSet left, IntervalSet right) 393 { 394 if (left is null || left.size == 0) { 395 return new IntervalSet(); 396 } 397 IntervalSet result = new IntervalSet(left); 398 if (right is null || right.isNil) { 399 // right set has no elements; just return the copy of the current set 400 return result; 401 } 402 403 int resultI = 0; 404 int rightI = 0; 405 while (resultI < result.intervals_.length && rightI < right.intervals_.length) { 406 Interval resultInterval = result.intervals_[resultI]; 407 Interval rightInterval = right.intervals_[rightI]; 408 409 // operation: (resultInterval - rightInterval) and update indexes 410 411 if (rightInterval.b < resultInterval.a) { 412 rightI++; 413 continue; 414 } 415 416 if (rightInterval.a > resultInterval.b) { 417 resultI++; 418 continue; 419 } 420 421 Interval beforeCurrent = null; 422 Interval afterCurrent = null; 423 if (rightInterval.a > resultInterval.a) { 424 beforeCurrent = new Interval(resultInterval.a, rightInterval.a - 1); 425 } 426 427 if (rightInterval.b < resultInterval.b) { 428 afterCurrent = new Interval(rightInterval.b + 1, resultInterval.b); 429 } 430 431 if (beforeCurrent !is null) { 432 if (afterCurrent !is null) { 433 // split the current interval into two 434 result.intervals_[resultI] = beforeCurrent; 435 result.intervals_ ~= afterCurrent; 436 resultI++; 437 rightI++; 438 continue; 439 } 440 else { 441 // replace the current interval 442 result.intervals_[resultI] = beforeCurrent; 443 resultI++; 444 continue; 445 } 446 } 447 else { 448 if (afterCurrent !is null) { 449 // replace the current interval 450 result.intervals_[resultI] = afterCurrent; 451 rightI++; 452 continue; 453 } 454 else { 455 // remove the current interval (thus no need to increment resultI) 456 //result.intervals.remove(resultI); 457 result.intervals_ = result.intervals_[0..resultI].dup ~ 458 result.intervals_[resultI+1..$].dup; 459 continue; 460 } 461 } 462 } 463 // If rightI reached right.intervals.size(), no more intervals to subtract from result. 464 // If resultI reached result.intervals.size(), we would be subtracting from an empty set. 465 // Either way, we are done. 466 return result; 467 } 468 469 public string elementName(Vocabulary vocabulary, int a) 470 { 471 if (a == TokenConstantDefinition.EOF) { 472 return "<EOF>"; 473 } 474 else if (a == TokenConstantDefinition.EPSILON) { 475 return "<EPSILON>"; 476 } 477 else { 478 return vocabulary.getDisplayName(a); 479 } 480 } 481 482 public int size() 483 { 484 int n = 0; 485 auto numIntervals = intervals_.length; 486 if (numIntervals == 1) { 487 Interval firstInterval = intervals_[0]; 488 return firstInterval.b - firstInterval.a + 1; 489 } 490 for (auto i = 0; i < numIntervals; i++) { 491 Interval I = intervals_[i]; 492 n += (I.b - I.a + 1); 493 } 494 return n; 495 } 496 497 public IntegerList toIntegerList() 498 { 499 IntegerList values = new IntegerList(); 500 auto n = intervals_.length; 501 for (auto i = 0; i < n; i++) { 502 Interval I = intervals_[i]; 503 int a = I.a; 504 int b = I.b; 505 for (int v = a; v <= b; v++) { 506 values.add(v); 507 } 508 } 509 return values; 510 } 511 512 public int[] toList() 513 { 514 int[] values; 515 auto n = intervals_.length; 516 for (auto i = 0; i < n; i++) { 517 Interval I = intervals_[i]; 518 int a = I.a; 519 int b = I.b; 520 for (int v = a ; v <= b; v++) { 521 values ~= v; 522 } 523 } 524 return values; 525 } 526 527 public RedBlackTree!int toSet() 528 { 529 auto s = new RedBlackTree!int(); 530 foreach (Interval I; intervals_) { 531 int a = I.a; 532 int b = I.b; 533 for (int v=a; v<=b; v++) { 534 s.insert(v); 535 } 536 } 537 return s; 538 } 539 540 /** 541 * Get the ith element of ordered set. Used only by RandomPhrase so 542 * don't bother to implement if you're not doing that for a new 543 * ANTLR code gen target. 544 * @uml 545 * @safe 546 * @pure 547 */ 548 public int get(int i) @safe pure 549 { 550 auto n = intervals_.length; 551 ulong index = 0; 552 for (auto j = 0; j < n; j++) { 553 Interval I = intervals_[j]; 554 int a = I.a; 555 int b = I.b; 556 for (int v = a; v <= b; v++) { 557 if (to!int(index) == i ) { 558 return v; 559 } 560 index++; 561 } 562 } 563 return -1; 564 } 565 566 public int[] toArray() 567 { 568 return toIntegerList().toArray; 569 } 570 571 public void remove(int el) 572 { 573 assert(!readonly, "can't alter readonly IntervalSet"); 574 auto n = intervals_.length; 575 for (auto i = 0; i < n; i++) { 576 Interval I = intervals_[i]; 577 int a = I.a; 578 int b = I.b; 579 if (el < a) { 580 break; // list is sorted and el is before this interval; not here 581 } 582 // if whole interval x..x, remove i 583 if (el == a && el == b ) { 584 intervals_ = intervals_[0..i] ~ intervals_[i+1..$]; 585 break; 586 } 587 // if on left edge x..b, adjust left 588 if (el == a) { 589 I.a++; 590 break; 591 } 592 // if on right edge a..x, adjust right 593 if (el == b) { 594 I.b--; 595 break; 596 } 597 // if in middle a..x..b, split interval 598 if (el >a && el < b) { // found in this interval 599 int oldb = I.b; 600 I.b = el-1; // [a..x-1] 601 add(el+1, oldb); // add [x+1..b] 602 } 603 } 604 } 605 606 /** 607 * @uml 608 * @safe 609 * @pure 610 */ 611 public bool isReadonly() @safe pure 612 { 613 return readonly; 614 } 615 616 /** 617 * @uml 618 * @safe 619 * @pure 620 */ 621 public void setReadonly(bool readonly) @safe pure 622 { 623 assert(!this.readonly, "can't alter readonly IntervalSet"); 624 this.readonly = readonly; 625 } 626 627 /** 628 * @uml 629 * @override 630 */ 631 public override bool opEquals(Object obj) 632 { 633 IntervalSet other = cast(IntervalSet)obj; 634 return intervals_ == other.intervals_; 635 } 636 637 /** 638 * @uml 639 * @override 640 */ 641 public override string toString() 642 { 643 return toString(false); 644 } 645 646 public string toString(bool elemAreChar) 647 { 648 auto buf = appender!string; 649 if (intervals_ is null || intervals_.length == 0) { 650 return "{}"; 651 } 652 if (this.size() > 1) { 653 buf.put("{"); 654 } 655 foreach (int index, I; this.intervals_) { 656 int a = I.a; 657 int b = I.b; 658 if (a == b) { 659 if (a == TokenConstantDefinition.EOF) buf.put("<EOF>"); 660 else if (elemAreChar) buf.put("'" ~ to!string(a) ~ "'"); 661 else buf.put(to!string(a)); 662 } 663 else { 664 if (elemAreChar) buf.put("'" ~ to!string(a) ~ "'..'" ~ to!string(b) ~ "'"); 665 else buf.put(to!string(a) ~ ".." ~ to!string(b)); 666 } 667 if (index + 1 < intervals_.length) { 668 buf.put(", "); // not last element 669 } 670 } 671 if (this.size() > 1) { 672 buf.put("}"); 673 } 674 return buf.data; 675 676 } 677 678 public string toString(Vocabulary vocabulary) 679 { 680 auto buf = appender!string; 681 if (intervals_ is null || intervals_.length == 0) { 682 return "{}"; 683 } 684 if (size() > 1) { 685 buf.put("{"); 686 } 687 foreach (int index, I; this.intervals_) { 688 int a = I.a; 689 int b = I.b; 690 if ( a==b ) { 691 buf.put(elementName(vocabulary, a)); 692 } 693 else { 694 for (int i=a; i<=b; i++) { 695 if ( i>a ) buf.put(", "); 696 buf.put(elementName(vocabulary, i)); 697 } 698 } 699 if (index + 1 < intervals_.length) { 700 buf.put(", "); 701 } 702 } 703 if (size() > 1) { 704 buf.put("}"); 705 } 706 return buf.data; 707 708 } 709 710 /** 711 * @uml 712 * @final 713 */ 714 public final Interval[] intervals() 715 { 716 return this.intervals_; 717 } 718 719 } 720 721 version(unittest) { 722 import dshould : be, equal, not, should; 723 import unit_threaded; 724 725 class Test { 726 727 @Tags("IntervalSet") 728 @("Empty") 729 unittest { 730 IntervalSet s = new IntervalSet; 731 s.should.not.be(null); 732 s.intervals.length.should.equal(0); 733 s.isNil.should.equal(true); 734 } 735 736 @Tags("IntervalSet") 737 @("One") 738 unittest { 739 IntervalSet s = new IntervalSet; 740 s.add(30); 741 s.intervals.length.should.equal(1); 742 s.isNil.should.equal(false); 743 s.contains(30).should.equal(true); 744 s.contains(29).should.equal(false); 745 s.contains(31).should.equal(false); 746 } 747 748 @Tags("IntervalSet") 749 @("Two") 750 unittest { 751 IntervalSet s = new IntervalSet; 752 s.add(30); 753 s.add(40); 754 s.intervals.length.should.equal(2); 755 s.isNil.should.equal(false); 756 s.contains(30).should.equal(true); 757 s.contains(40).should.equal(true); 758 s.contains(35).should.equal(false); 759 } 760 761 @Tags("IntervalSet") 762 @("Range") 763 unittest { 764 IntervalSet s = new IntervalSet; 765 s.add(30, 41); 766 s.intervals.length.should.equal(1); 767 s.isNil.should.equal(false); 768 s.contains(30).should.equal(true); 769 s.contains(40).should.equal(true); 770 s.contains(35).should.equal(true); 771 } 772 773 @Tags("IntervalSet") 774 @("Distinct1") 775 unittest { 776 IntervalSet s = new IntervalSet; 777 s.add(30, 32); 778 s.add(40, 42); 779 s.intervals.length.should.equal(2); 780 s.isNil.should.equal(false); 781 s.contains(30).should.equal(true); 782 s.contains(40).should.equal(true); 783 s.contains(35).should.equal(false); 784 } 785 786 @Tags("IntervalSet") 787 @("Distinct2") 788 unittest { 789 IntervalSet s = new IntervalSet; 790 s.add(40, 42); 791 s.add(30, 32); 792 s.intervals.length.should.equal(2); 793 s.isNil.should.equal(false); 794 s.contains(30).should.equal(true); 795 s.contains(40).should.equal(true); 796 s.contains(35).should.equal(false); 797 } 798 799 @Tags("IntervalSet") 800 @("Contiguous1") 801 unittest { 802 IntervalSet s = new IntervalSet; 803 s.add(30, 36); 804 s.add(36, 41); 805 s.add(41, 44); 806 s.intervals.length.should.equal(1); 807 s.isNil.should.equal(false); 808 s.contains(30).should.equal(true); 809 s.contains(40).should.equal(true); 810 s.contains(43).should.equal(true); 811 s.contains(44).should.equal(true); 812 s.contains(45).should.equal(false); 813 } 814 815 @Tags("IntervalSet") 816 @("Contiguous2") 817 unittest { 818 IntervalSet s = new IntervalSet; 819 s.add(41, 44); 820 s.add(36, 41); 821 s.add(30, 36); 822 s.intervals.length.should.equal(1); 823 s.isNil.should.equal(false); 824 s.contains(30).should.equal(true); 825 s.contains(40).should.equal(true); 826 s.contains(43).should.equal(true); 827 s.contains(44).should.equal(true); 828 s.contains(45).should.equal(false); 829 } 830 831 @Tags("IntervalSet") 832 @("Overlapping1") 833 unittest { 834 IntervalSet s = new IntervalSet; 835 s.add(30, 40); 836 s.add(35, 44); 837 s.add(31, 36); 838 s.intervals.length.should.equal(1); 839 s.isNil.should.equal(false); 840 s.contains(30).should.equal(true); 841 s.contains(40).should.equal(true); 842 s.contains(43).should.equal(true); 843 s.contains(44).should.equal(true); 844 s.contains(45).should.equal(false); 845 } 846 847 @Tags("IntervalSet") 848 @("Overlapping2") 849 unittest { 850 IntervalSet s = new IntervalSet; 851 s.add(35, 44); 852 s.add(31, 36); 853 s.add(30, 40); 854 s.intervals.length.should.equal(1); 855 s.isNil.should.equal(false); 856 s.contains(30).should.equal(true); 857 s.contains(40).should.equal(true); 858 s.contains(43).should.equal(true); 859 s.contains(44).should.equal(true); 860 s.contains(45).should.equal(false); 861 } 862 863 @Tags("IntervalSet") 864 @("Overlapping3") 865 unittest { 866 IntervalSet s = new IntervalSet; 867 s.add(30, 32); 868 s.add(40, 42); 869 s.add(140, 144); 870 s.add(50, 52); 871 s.add(20, 61); 872 s.add(50, 52); 873 s.intervals.length.should.equal(2); 874 s.isNil.should.equal(false); 875 s.contains(20).should.equal(true); 876 s.contains(40).should.equal(true); 877 s.contains(43).should.equal(true); 878 s.contains(61).should.equal(true); 879 s.contains(4).should.equal(false); 880 s.contains(62).should.equal(false); 881 s.contains(139).should.equal(false); 882 s.contains(140).should.equal(true); 883 s.contains(144).should.equal(true); 884 s.contains(145).should.equal(false); 885 s.toString.should.equal("{20..61, 140..144}"); 886 } 887 888 @Tags("IntervalSet") 889 @("Complement") 890 unittest { 891 IntervalSet s = new IntervalSet; 892 s.add(10, 21); 893 auto c = s.complement(1, 100); 894 c.intervals.length.should.equal(2); 895 c.toString.should.equal("{1..9, 22..100}"); 896 c.contains(1).should.equal(true); 897 c.contains(40).should.equal(true); 898 c.contains(22).should.equal(true); 899 c.contains(10).should.equal(false); 900 c.contains(20).should.equal(false); 901 } 902 } 903 }