41     T end;  member
43     Interval() : begin(-1), end(-1) {}  in Interval()
45     Interval(T b, T e) : begin(b), end(e) {}  in Interval()
48       return begin < i.begin || (begin == i.begin && end > i.end);
52       return begin == i.begin && end == i.end;
56       return begin != i.begin || end != i.end;
64       end = n;  in Read()
71       n = end;  in Write()
100          it != intervals->end(); ++it)  in Union()
108         lower_bound(intervals_.begin(), intervals_.end(), interval);  in Member()
111     return (--lb)->end > value;  in Member()
126         intervals_[0].begin + 1 == intervals_[0].end;  in Singleton()
175   sort(intervals_.begin(), intervals_.end());  in Normalize()
181     if (inti.begin == inti.end)  in Normalize()
185       if (intj.begin > inti.end)  in Normalize()
187       if (intj.end > inti.end)  in Normalize()
188         inti.end = intj.end;  in Normalize()
191     count_ += inti.end - inti.begin;  in Normalize()
210   while (it1 != intervals_.end() && it2 != iintervals->end()) {  in Intersect()
211     if (it1->end <= it2->begin) {  in Intersect()
213     } else if (it2->end <= it1->begin) {  in Intersect()
218       interval.end = min(it1->end, it2->end);  in Intersect()
220       oset->count_ += interval.end - interval.begin;  in Intersect()
221       if (it1->end < it2->end)  in Intersect()
240        it != intervals_.end();  in Complement()
242     interval.end = min(it->begin, maxval);  in Complement()
243     if (interval.begin < interval.end) {  in Complement()
245       oset->count_ += interval.end - interval.begin;  in Complement()
247     interval.begin = it->end;  in Complement()
249   interval.end = maxval;  in Complement()
250   if (interval.begin < interval.end) {  in Complement()
252     oset->count_ += interval.end - interval.begin;  in Complement()
266     iset.Complement(intervals_.back().end, &cset);  in Difference()
279   while (it1 != intervals_.end() && it2 != intervals->end()) {  in Overlaps()
280     if (it1->end <= it2->begin) {  in Overlaps()
282     } else if (it2->end <= it1->begin) {  in Overlaps()
302   while (it1 != intervals_.end() && it2 != intervals->end()) {  in StrictlyOverlaps()
303     if (it1->end <= it2->begin) {  // no overlap - it1 first  in StrictlyOverlaps()
306     } else if (it2->end <= it1->begin) {  // no overlap - it2 first  in StrictlyOverlaps()
309     } else if (it2->begin == it1->begin && it2->end == it1->end) {  // equals  in StrictlyOverlaps()
313     } else if (it2->begin <= it1->begin && it2->end >= it1->end) {  // 1 c 2  in StrictlyOverlaps()
317     } else if (it1->begin <= it2->begin && it1->end >= it2->end) {  // 2 c 1  in StrictlyOverlaps()
329   if (it1 != intervals_.end())  in StrictlyOverlaps()
331   if (it2 != intervals->end())  in StrictlyOverlaps()
348   while (it1 != intervals_.end() && it2 != intervals->end()) {  in Contains()
349     if (it1->end <= it2->begin) {  // no overlap - it1 first  in Contains()
351     } else if (it2->begin < it1->begin || it2->end > it1->end) {  // no C  in Contains()
353     } else if (it2->end == it1->end) {  in Contains()
360   return it2 == intervals->end();  in Contains()
369        it != intervals->end();
373     strm << "[" << it->begin << "," << it->end << ")";