1 module intervaltree; 2 3 /// Interval with zero-based, half-open coordinates 4 /// Any other Interval struct (or class?) OK 5 /// as long as it contains "start" and "end" 6 struct BasicInterval 7 { 8 int start; /// zero-based half-open 9 int end; /// zero-based half-open 10 11 /// override the <, <=, >, >= operators; we'll use compiler generated default opEqual 12 @safe 13 @nogc nothrow 14 int opCmp(const ref BasicInterval other) const 15 { 16 if (this.start < other.start) return -1; 17 else if(this.start > other.start) return 1; 18 else if(this.start == other.start && this.end < other.end) return -1; // comes third as should be less common 19 else if(this.start == other.start && this.end > other.end) return 1; 20 else return 0; // would be reached in case of equality 21 } 22 /// override <, <=, >, >= to compare directly to int: compare only the start coordinate 23 @nogc nothrow 24 int opCmp(const int other) const 25 { 26 return this.start - other; 27 } 28 29 string toString() const 30 { 31 import std.format : format; 32 return format("[%d, %d)", this.start, this.end); 33 } 34 35 invariant 36 { 37 assert(this.start <= this.end); 38 } 39 } 40 41 /** Detect overlap between this interval and other given interval 42 in a half-open coordinate system [start, end) 43 44 Top-level function template for reuse by many types of Interval objects 45 Template type parameter Interval Type must have {start, end} 46 Still usable with member-function style due to UFCS: interval.overlaps(other) 47 48 return true in any of the following four situations: 49 int1 ===== ======= 50 int2 ======= ======= 51 52 int1 ======= ======= 53 int2 === ======= 54 55 return false in any other scenario: 56 int1 ===== | ===== 57 int2 ===== | ===== 58 59 NOTE that in half-open coordinates [start, end) 60 i1.end == i2.start => Adjacent, but NO overlap 61 */ 62 @nogc pure @safe nothrow 63 bool overlaps(IntervalType1, IntervalType2)(IntervalType1 int1, IntervalType2 int2) 64 if (__traits(hasMember, IntervalType1, "start") && 65 __traits(hasMember, IntervalType1, "end") && 66 __traits(hasMember, IntervalType2, "start") && 67 __traits(hasMember, IntervalType2, "end")) 68 { 69 // DMD cannot inline this 70 version(LDC) pragma(inline, true); 71 version(GNU) pragma(inline, true); 72 if (int2.start < int1.end && int1.start < int2.end) return true; 73 else return false; 74 }