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