interval.cc 24.4 KB
Newer Older
1
2
3
4
5
6
7
8
/*
 * File:   interval.ccc
 * Author: Jordan P. Lefebvre, lefebvre.jordan@gmail.com
 *
 * Created on August 16, 2012, 7:28 PM
 */

#include "radixgeometry/interval.hh"
9
10
#include <algorithm>
#include <cstring>
11
12
13
#include <iomanip>
#include <iostream>
#include <sstream>
14
15
#include "radixbug/bug.hh"
namespace radix {
16

17
18
19
20
Interval::Interval()
    : a(minReal)
    , b(maxReal)
    , id(0) {}
21

22
23
24
25
Interval::Interval(const Interval &orig)
    : a(orig.a)
    , b(orig.b)
    , id(orig.id) {}
26

27
Interval::Interval(Real start, Real finish, Identifier id)
28
29
30
    : a(start)
    , b(finish)
    , id(id) {}
31

32
33
34
35
36
37
Interval::~Interval() {}
std::string Interval::toString() const {
  std::stringstream result;
  result << std::fixed << std::setprecision(15);
  result << "a=" << a << " b=" << b << " id=" << id;
  return result.str();
38
}
39
40
41
42
43
44
45
int Interval::diff(const Interval &rhs, Interval &a, Interval &b) const {
  radix_require(this->a <= this->b);
  radix_require(rhs.a <= rhs.b);

  Interval::List result;
  int resultCount = 0;
  switch (compare(rhs)) {
46
47
48
49
    case IC_BEFORE:
    case IC_SHARED_LEFT:
    case IC_SHARED_RIGHT:
    case IC_AFTER:
50
51
52
53
      if (this->a != this->b) {
        a           = *this;
        resultCount = 1;
      }
54

55
      break;
56
57
    case IC_OVERLAP_LEFT:
    case IC_SUPERSET_RIGHT:
58
59
60
61
      if (this->a != rhs.a) {
        a           = Interval(this->a, rhs.a, this->id);
        resultCount = 1;
      }
62

63
      break;
64
65
    case IC_SUPERSET_LEFT:
    case IC_OVERLAP_RIGHT:
66
67
68
69
      if (rhs.b != this->b) {
        a           = Interval(rhs.b, this->b, this->id);
        resultCount = 1;
      }
70

71
      break;
72
    case IC_SUPERSET_MIDDLE:
73
74
75
76
      if (this->a != rhs.a) {
        a           = Interval(this->a, rhs.a, this->id);
        resultCount = 1;
      }
77

78
79
80
81
      if (rhs.b != this->b) {
        b = Interval(rhs.b, this->b, this->id);
        resultCount++;
      }
82

83
      break;
84
    default:
85
86
      break;
  }
87

88
  return resultCount;
89
}
90
91
92
Interval::List Interval::operator^(const Interval &rhs) const {
  radix_require(this->a <= this->b);
  radix_require(rhs.a <= rhs.b);
93

94
  Interval::List result;
95

96
  switch (compare(rhs)) {
97
98
99
100
    case IC_BEFORE:
    case IC_SHARED_LEFT:
    case IC_SHARED_RIGHT:
    case IC_AFTER:
101
102
103
      if (this->a != this->b) {
        result.push_back(*this);
      }
104

105
      break;
106
107
    case IC_OVERLAP_LEFT:
    case IC_SUPERSET_RIGHT:
108
109
110
      if (this->a != rhs.a) {
        result.push_back(Interval(this->a, rhs.a, this->id));
      }
111

112
      break;
113
114
    case IC_SUPERSET_LEFT:
    case IC_OVERLAP_RIGHT:
115
116
117
      if (rhs.b != this->b) {
        result.push_back(Interval(rhs.b, this->b, this->id));
      }
118

119
      break;
120
    case IC_SUPERSET_MIDDLE:
121
122
123
      if (this->a != rhs.a) {
        result.push_back(Interval(this->a, rhs.a, this->id));
      }
124

125
126
127
      if (rhs.b != this->b) {
        result.push_back(Interval(rhs.b, this->b, this->id));
      }
128

129
      break;
130
    default:
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
      break;
  }

  return result;
  //        // there are 6 scenarios
  //        // 1) this is a subset of rhs, resulting in an empty set
  //        // 2) rhs misses to the left, resulting in this
  //        // 3) rhs misses to the right, resulting in this
  //        // 4) rhs truncates this on the left, resulting in [rhs.b,this.b]
  //        // 5) rhs truncats this on the right, resulting in [this.a,rhs.a]
  //        // 6) rhs resides in the middle of this, resulting in [this.a,rhs.a]
  //        and [rhs.b,this.b]
  //
  //        // 1) this is a subset of rhs
  //        if( this->a >= rhs.a && this->b <= rhs.b ){
  //            // return empty set
  //            return Interval::List();
  //        }
  //        // 2) rhs misses to the left
  //        else if( rhs.b <= this->a ){
  //            Interval::List intervals;
  //            intervals.push_back(*this);
  //            return intervals;
  //        }
  //        // 3) rhs misses to the right
  //        else if( rhs.a >= this->b ){
  //            Interval::List intervals;
  //            intervals.push_back(*this);
  //            return intervals;
  //        }
  //        // 4) rhs truncates this on the left, resulting in [rhs.b,this.b]
  //        else if( rhs.a <= this->a && rhs.b > this->a){
  //            Interval::List intervals;
  //            radix_ensure(rhs.b <= this->b);
  //            intervals.push_back(Interval(rhs.b,this->b,this->id));
  //            return intervals;
  //        }
  //
  //        // 5) rhs truncates this on the right, resulting in [this.a,rhs.a]
  //        else if( rhs.a < this->b && rhs.b >= this->b ){
  //            Interval::List intervals;
  //            radix_ensure(this->a <= rhs.a);
  //            intervals.push_back(Interval(this->a,rhs.a,this->id));
  //            return intervals;
  //        }
  //
  //        // 6) rhs resides in the middle of this, resulting in [this.a,rhs.a]
  //        and [rhs.b,this.b] else if( this->a < rhs.a && rhs.b < this->b){
  //            Interval::List intervals;
  //            radix_ensure(this->a <= rhs.a);
  //            intervals.push_back(Interval(this->a,rhs.a,this->id));
  //            radix_ensure(rhs.b <= this->b);
  //            intervals.push_back(Interval(rhs.b,this->b,this->id));
  //            return intervals;
  //        }
  //        radix_tagged_line("un-accounted for scenario where taking
  //        IA("<<this->toString()<<")^IB("<<rhs.toString()<<") "); throw
  //        "Scenario not implemented yet!";
189
}
190
191
192
193
194
195
bool Interval::intersect(const Interval &rhs, Interval &result) const {
  radix_insist(this->a <= this->b, "Interval invalid - " + this->toString());
  radix_require(rhs.a <= rhs.b);

  bool intersected = false;
  switch (compare(rhs)) {
196
    case IC_OVERLAP_LEFT:
197
198
199
200
      if (rhs.a != this->b) {
        result      = Interval(rhs.a, this->b, this->id);
        intersected = true;
      }
201

202
      break;
203
204
205
    case IC_SUPERSET_LEFT:
    case IC_SUPERSET_MIDDLE:
    case IC_SUPERSET_RIGHT:
206
207
208
209
      if (rhs.a != rhs.b) {
        result      = Interval(rhs.a, rhs.b, this->id);
        intersected = true;
      }
210

211
      break;
212
213
214
215
    case IC_EQUAL:
    case IC_SUBSET_LEFT:
    case IC_SUBSET_MIDDLE:
    case IC_SUBSET_RIGHT:
216
217
218
219
      if (this->a != this->b) {
        result      = *this;
        intersected = true;
      }
220

221
      break;
222
    case IC_OVERLAP_RIGHT:
223
224
225
226
      if (this->a != rhs.b) {
        result      = Interval(this->a, rhs.b, this->id);
        intersected = true;
      }
227

228
      break;
229
    default:
230
231
232
      break;
  }
  return intersected;
233
234
235
}

/**
236
237
238
239
240
241
242
243
 * @brief the union operator (|)
 * a|b reads 'in a or in b'
 * @param rhs
 * @return IntervalList
 */
Interval::List Interval::operator|(const Interval &rhs) const {
  radix_require(this->a <= this->b);
  radix_require(rhs.a <= rhs.b);
244

245
  Interval::List result;
246

247
  switch (compare(rhs)) {
248
    case IC_BEFORE:
249
250
251
      if (this->a != this->b) {
        result.push_back(*this);
      }
252

253
254
255
      if (rhs.a != rhs.b) {
        result.push_back(rhs);
      }
256

257
      break;
258
259
    case IC_SHARED_LEFT:
    case IC_OVERLAP_LEFT:
260
261
262
      if (this->a != rhs.b) {
        result.push_back(Interval(this->a, rhs.b, this->id));
      }
263

264
      break;
265
266
267
268
    case IC_EQUAL:
    case IC_SUPERSET_LEFT:
    case IC_SUPERSET_MIDDLE:
    case IC_SUPERSET_RIGHT:
269
270
271
      if (this->a != this->b) {
        result.push_back(*this);
      }
272

273
      break;
274
275
276
    case IC_SUBSET_LEFT:
    case IC_SUBSET_MIDDLE:
    case IC_SUBSET_RIGHT:
277
278
279
      if (rhs.a != rhs.b) {
        result.push_back(rhs);
      }
280

281
      break;
282
283
    case IC_OVERLAP_RIGHT:
    case IC_SHARED_RIGHT:
284
285
286
      if (rhs.a != this->b) {
        result.push_back(Interval(rhs.a, this->b, this->id));
      }
287

288
      break;
289
    case IC_AFTER:
290
291
292
      if (rhs.a != rhs.b) {
        result.push_back(rhs);
      }
293

294
295
296
      if (this->a != this->b) {
        result.push_back(*this);
      }
297

298
299
      break;
  }
300

301
302
  radix_ensure(!result.empty());
  return result;
303
}
304
305
306
307
308
309
310
311
312
313
314
315
bool Interval::contiguous(const Interval::List &intervals,
                          Interval::PairList &pairs) {
  radix_require(isSorted(intervals));
  auto n              = intervals.begin();
  size_t previousSize = pairs.size();
  for (auto i = intervals.begin(), end = intervals.end(); i != end; i++) {
    n++;
    if (n == intervals.end()) break;
    const Interval &a = *i;
    const Interval &b = *n;
    if (a.b < b.a && !isWithinKEpsilon(a.b, b.a)) {
      pairs.push_back(Pair(a, b));
316
    }
317
318
  }
  return pairs.size() == previousSize;
319
320
}

321
322
323
324
bool Interval::overlap(const Interval::List &intervals) {
  if (intervals.empty()) {
    return false;
  }
325

326
  radix_require(isSorted(intervals));
327

328
329
330
  Interval::List::const_iterator end;
  Interval::List::const_iterator i;
  Interval::List::const_iterator j;
331

332
333
  for (i = intervals.begin(), end = intervals.end(); i != end; i++) {
    const Interval &a(*i);
334

335
336
337
338
    for (j = i + 1; j != end; j++) {
      const Interval &b(*j);
      Interval result;
      bool intersected = a.intersect(b, result);
339

340
341
342
343
344
      if (intersected) {
        if ((result.a - result.b) >= kEpsilon) {
          return true;
        }
      }
345
    }
346
  }
347

348
349
  return false;
}
350

351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
void Interval::intersect(const Interval::List &left,
                         const Interval::List &right,
                         Interval::List &intervals) {
  // don't waste time if either list is empty
  if (left.empty() || right.empty()) {
    return;
  }

  // we assume the incoming interval lists are sorted
  radix_require(isSorted(left));
  radix_require(isSorted(right));

  // don't waste time if none of the items can intersect
  if (left.back().b < right.front().a || left.front().a > right.back().b) {
    return;
  }

  Interval::List::const_iterator i;
  Interval::List::const_iterator iEnd;
  Interval::List::const_iterator j;
  Interval::List::const_iterator jEnd;

  i    = left.begin();
  iEnd = left.end();
  j    = right.begin();
  jEnd = right.end();
  // at worst, the left
  intervals.reserve(std::min(left.size(), right.size()));
  while (i != iEnd && j != jEnd) {
    const Interval &a(*i);
    const Interval &b(*j);

    IntervalCompare comp;

    comp = a.compare(b);

    switch (comp) {
      case IC_BEFORE:
        i++;
        break;
      case IC_AFTER:
        j++;
        break;
      default:
        Interval r;
        if (a.intersect(b, r)) {
          intervals.push_back(r);
        }
399

400
401
402
403
404
        switch (comp) {
          case IC_SHARED_LEFT:
            i++;
            break;
          case IC_OVERLAP_LEFT:
405
406
            i++;
            break;
407
          case IC_SUPERSET_LEFT:
408
409
            j++;
            break;
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
          case IC_SUBSET_LEFT:
            i++;
            break;
          case IC_EQUAL:
            i++;
            j++;
            break;
          case IC_SUPERSET_MIDDLE:
            j++;
            break;
          case IC_SUBSET_MIDDLE:
            i++;
            break;
          case IC_SUPERSET_RIGHT:
            i++;
            j++;
            break;
          case IC_SUBSET_RIGHT:
            i++;
            j++;
            break;
          case IC_OVERLAP_RIGHT:
            j++;
            break;
          case IC_SHARED_RIGHT:
            j++;
            break;
          default:
            radix_check(0);
439
440
        }
    }
441
  }
442

443
  radix_ensure(!overlap(intervals));
444
445
}

446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
void Interval::unite(const Interval::List &left, const Interval::List &right,
                     Interval::List &intervals) {
  // we assume the incoming interval lists are sorted
  radix_require(isSorted(left));
  radix_require(isSorted(right));

  intervals.insert(intervals.end(), left.begin(), left.end());
  intervals.insert(intervals.end(), right.begin(), right.end());

  // don't waste time if either list is empty
  if (left.empty()) return;
  if (right.empty()) return;

  std::sort(intervals.begin(), intervals.end());

  // the following algorithm assumes no interval from
  // the left or right lists overlap with another
  // interval from their respective interval lists
  for (size_t i = 0; i < intervals.size(); i++) {
    Interval &a = intervals[i];

    for (size_t j = i + 1; j < intervals.size(); j++) {
      const Interval &b = intervals[j];

      // union will produce
      // an list of size 1 or 2
      const Interval::List &united = a | b;

      //                radix_tagged_line( "Intervals created from " <<
      //                a.toString() << " unioned with " << b.toString() << "
      //                are " << united.size() );
      radix_check(united.size() > 0);

      // we have two scenarios
      // 1) the intervals merged to form one contiguous interval or
      //    in this case we need to remove the interval a and b and replace
      //    with the new merged interval, decrementing j because b was erased
      // 2) the intervals didn't merge resulting in no change
      //    in this case we need to break out of the loop
      //    given that we know interval a will not be merged with anything
      //    passed interval b.

      // case 1, merged intervals
      if (united.size() == 1) {
        //                    radix_tagged_line( "Replacing " << a.toString() <<
        //                    " with " << united.front().toString() );

        a = united.front();  // overwrite a
        intervals.erase(intervals.begin() + j);
        j--;
        continue;
      }
      // case 2, nothing changed
      else if (united.size() == 2) {
        break;
      }

      //                radix_tagged_line( "Un-accounted for interval scenario
      //                for " + a.toString() + " and " + b.toString() );
      std::stringstream ss;
      ss << "Un-accounted for interval scenario for " << a.toString() << " and "
         << b.toString();
      throw std::logic_error(ss.str());
    }  // end of look ahead loop
  }    // end of interval evaluation loop
511
512
}

513
514
bool Interval::isSorted(const Interval::List &intervals) {
  if (!intervals.empty()) {
515
516
    Interval::List::const_iterator end;
    Interval::List::const_iterator i;
517
    Interval::List::const_iterator j;
518
519
520

    end = intervals.end();
    i   = intervals.begin();
521
    j   = i + 1;
522

523
524
525
526
527
528
    for (; j != end; i++, j++) {
      if (i->a > j->a) {
        //                    radix_tagged_line( "Intervals are not sorted!" );
        print(intervals, std::cout);
        return false;
      }
529
    }
530
  }
531

532
533
534
535
536
537
538
539
540
  return true;
}
void Interval::print(const Interval::PairList &pairs, std::ostream &stream) {
  auto end = pairs.end();
  auto i   = pairs.begin();
  for (int count = 1; i != end; count++, i++) {
    stream << count << " ) " << i->first.toString() << " -- "
           << i->second.toString() << std::endl;
  }
541
542
}

543
544
545
void Interval::print(const Interval::List &intervals, std::ostream &stream) {
  Interval::List::const_iterator end;
  Interval::List::const_iterator i;
546

547
548
  end = intervals.end();
  i   = intervals.begin();
549

550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
  for (int count = 1; i != end; count++, i++) {
    stream << count << ") " << i->toString() << std::endl;
  }
  //        for( size_t i = 0; i < intervals.size(); i++){
  //            stream<<i+1<<") "<<intervals[i].toString()<<std::endl;
  //        }
}
void Interval::printPretty(const Interval::List &intervals,
                           std::ostream &stream) {
  Interval::List::const_iterator end;
  Interval::List::const_iterator i;

  end = intervals.end();
  i   = intervals.begin();
  stream << std::setprecision(12);
  for (int count = 1; i != end; count++, i++) {
    if (count != 1) stream << ",";
    stream << "{" << i->a << "," << i->b << "," << i->id << "}" << std::endl;
  }
}
void Interval::difference(Interval::List &keep, const Interval::List &remove) {
  // we assume the incoming interval lists are sorted
  radix_require(isSorted(keep));
  radix_require(isSorted(remove));

  // dont waste out time
  if (remove.empty()) return;
  if (keep.empty()) return;
  // radix_check if all intervals from keep miss removal intervals
  if (keep.back().b <= remove.front().a) return;
  if (keep.front().a >= remove.back().b) return;

  // intervals for difference operations
  Interval l, r;

  // loop over keepers, comparing against
  for (size_t i = 0; i < keep.size(); i++) {
    for (size_t j = 0; j < remove.size(); j++) {
      const Interval &a = keep[i];
      const Interval &b = remove[j];
      // if interval a is prior to interval b
      // and since removal list is assumed to be sorted
      // than we know a will never intersect an interval in b
      // so we can leave a, and move on
      if (a.b < b.a) {
        //                    radix_tagged_line("Interval "<<a.toString()<<" is
        //                    completely prior to interval "<<b.toString()<<"
        //                    indicating no future intersections possible");
        break;  // quit comparing interval a against removal intervals
      }
      if (a.a > b.b) {
        //                    radix_tagged_line("Interval "<<a.toString()<<" is
        //                    completely after interval "<<b.toString()<<"
        //                    indicating potential future intersections are
        //                    possible");
        continue;
      }
      //                const Interval::List intervals = a ^ b;

      int resultCount = a.diff(b, l, r);
      radix_check(resultCount >= 0 && resultCount <= 2);
      // four scenarios
      // 1) intervals is empty (b completely intersected a)
      // 2) intervals contains 2 (b is a subset of a)
      // 3) intervals contains exactly interval a (no intersection occurred)
      // 4) intervals contains a subset of interval a ( b truncated a )

      // 1) intervals is empty (b completely intersected a)
      // we need to remove interval a and break out of the loop
      if (resultCount == 0) {
        //                    radix_tagged_line("Removing "<<a.toString());
        keep.erase(keep.begin() + i);
        i--;
        break;
      }
      // 2) intervals contains 2 (b is a subset of a)
      // here we replace the old interval a with a1 and a2
      // given that the removal list is sorted we know interval a1
      // will not intersect any future intervals so we can break from our
      // comparison loop and compare interval a2
      else if (resultCount == 2) {
        //                    radix_tagged_line("Replacing "<<a.toString());
        //                    radix_tagged_line("   with
        //                    "<<intervals.front().toString());
        //                    radix_tagged_line("   and
        //                    "<<intervals.back().toString());
        keep[i] = l;  // replace interval a with interval a1
        keep.insert(keep.begin() + i + 1, r);
        break;  // stop comparing interval a
      }
      // 3) intervals contains exactly interval a (no intersection occurred)
      // technically this should have been caught in our
      // previous radix_check before getting into our if-else scenarios
      // but if we do manage to get here we want to do nothing,
      // just move ahead in our comparison of interval a with intervals
      // from our removal list
      else if (l == a) {
        continue;  // look to the next interval
      }
      // 4) intervals contains a subset of interval a ( b truncated a )
      else if (resultCount == 1) {
        //                    radix_tagged_line("Replacing "<<a.toString());
        //                    radix_tagged_line("   with
        //                    "<<intervals.front().toString());
        keep[i] = l;
      }
    }  // end of loop over removals
  }    // end of loop over keepers
}  // end of difference method
659

660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
/**
 * @brief invert the given list of intervals
 * Inverts the list of intervals, appending the results to the results list.
 * The inverse will start from 0
 * @param list2Invert - the list to invert - cannot be empty
 * @param results - the list to which the results will be appended
 */
void Interval::invert(const Interval::List &list2Invert,
                      Interval::List &results) {
  radix_require(!list2Invert.empty());

  Interval::List::const_iterator end;
  Interval::List::const_iterator i;
  Interval::List::const_iterator j;

  end = list2Invert.end();
  i   = list2Invert.begin();
  j   = i + 1;

  // first, see if the intervals start after zero
  // we will need to insert an interval
  if (i->a > kEpsilon) {
    results.push_back(Interval(0, i->a - halfKEpsilon, 0));
    //            radix_tagged_line( "Creating inverse interval " <<
    //            results.back().toString() );
  }

  for (; j != end; i++, j++) {
    // if there is any space between the current interval
    // and the previous interval, we need to create this
    const Interval &previous(*i);
    const Interval &current(*j);

    if (previous.b < current.a) {
      //                radix_tagged_line( "Creating inverse interval " <<
      //                results.back().toString() );
      results.push_back(
          Interval(previous.b + halfKEpsilon, current.a - halfKEpsilon, 0));
698
    }
699
700
701
702
703
704
705
706
707
  }

  // lastly we need to determine if there is space from the last interval to
  // infinity that is to be included
  if (i->b < maxReal) {
    results.push_back(Interval(i->b + halfKEpsilon, maxReal, 0));
    //            radix_tagged_line( "Creating inverse interval " <<
    //            results.back().toString() );
  }
708
709
}

710
711
712
void Interval::mapIds(Interval::List &intervals, Identifier id) {
  Interval::List::iterator end;
  Interval::List::iterator i;
713

714
715
  end = intervals.end();
  i   = intervals.begin();
716

717
718
719
720
721
722
723
  for (; i != end; i++) {
    i->id = id;
  }
  //        for( size_t i = 0; i < intervals.size(); i++ )
  //        {
  //            intervals[i].id = id;
  //        }
724
}
725
726
727
728
729
730
731
732
void Interval::append(Interval::List &intervals,
                      const Interval::List &additional) {
  size_t asize = additional.size();
  if (asize == 0) return;
  size_t psize = intervals.size();
  intervals.resize(psize + asize);
  std::memcpy((char *)&(intervals[psize]), (char *)&(additional[0]),
              sizeof(Interval) * asize);
733
}
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
void Interval::moveAll(Interval::List &intervals, Real offset) {
  Interval::List::iterator end;
  Interval::List::iterator i;

  end = intervals.end();
  i   = intervals.begin();

  for (; i != end; i++) {
    i->a += offset;
    i->b += offset;
  }
  //        for( size_t i = 0; i < intervals.size(); i++ )
  //        {
  //            Interval& interval( intervals[i] );
  //
  //            interval.a += offset;
  //            interval.b += offset;
  //        }
752
753
}

754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
IntervalCompare Interval::compare(const Interval &rhs) const {
  // special case to handle an infinite endpoint
  if (a == rhs.a && b == rhs.b) {
    return IC_EQUAL;
  }

  const Real aa        = a - rhs.a;
  const Real ab        = a - rhs.b;
  const Real ba        = b - rhs.a;
  const Real bb        = b - rhs.b;
  const Real tolerance = halfKEpsilon;

  /*
   * Before rhs
   * this: -----
   * rhs:        -----
   */
  if (ba < -tolerance) {
    return IC_BEFORE;
  }
  /*
   * Shares rhs's left end point
   * this: -----
   * rhs:       -----
   */
  else if (ba <= tolerance) {
    return IC_SHARED_LEFT;
  } else if (aa < -tolerance) {
782
    /*
783
784
785
786
787
788
     * Overlaps rhs on the left
     * this: -----
     * rhs:    -----
     */
    if (bb < -tolerance) {
      return IC_OVERLAP_LEFT;
789
790
    }
    /*
791
792
793
794
795
796
     * Superset of rhs (rhs internal subset of this)
     * this: -----
     * rhs:   ---
     */
    else if (bb > tolerance) {
      return IC_SUPERSET_MIDDLE;
797
798
    }
    /*
799
800
801
802
803
804
     * Superset of rhs (rhs subset on right side of this)
     * this: -----
     * rhs:    ---
     */
    else if (bb >= -tolerance && bb <= tolerance) {
      return IC_SUPERSET_RIGHT;
805
    }
806
  } else if (aa <= tolerance) {
807
    /*
808
809
810
811
812
813
     * Superset of rhs (rhs subset on left side of this)
     * this: -----
     * rhs:  ---
     */
    if (bb > tolerance) {
      return IC_SUPERSET_LEFT;
814
815
    }
    /*
816
817
818
819
820
821
     * Subset on left side of rhs
     * this: ---
     * rhs:  -----
     */
    else if (bb < -tolerance) {
      return IC_SUBSET_LEFT;
822
823
    }
    /*
824
825
826
827
828
829
     * Equal to rhs
     * this: -----
     * rhs:  -----
     */
    else if (bb >= -tolerance && bb <= tolerance) {
      return IC_EQUAL;
830
    }
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
  }
  /*
   * Subset internally to rhs
   * this:  ---
   * rhs:  -----
   */
  else if (bb < -tolerance) {
    return IC_SUBSET_MIDDLE;
  }
  /*
   * Subset on right side of rhs
   * this:   ---
   * rhs:  -----
   */
  else if (bb <= tolerance) {
    return IC_SUBSET_RIGHT;
  }
  /*
   * Overlaps rhs on the right
   * this:   -----
   * rhs:  -----
   */
  else if (ab < -tolerance) {
    return IC_OVERLAP_RIGHT;
  }
  /*
   * Shares rhs's right end point
   * this:      -----
   * rhs:  -----
   */
  else if (ab >= -tolerance && ab <= tolerance) {
    return IC_SHARED_RIGHT;
  }
  /*
   * After rhs
   * this:       -----
   * rhs:  -----
   */
  else if (ab > tolerance) {
    return IC_AFTER;
  }

  std::cout << "Interval::compare: unknown scenario --- this: " << toString()
            << "; rhs: " << rhs.toString() << std::endl;
  throw "Interval::compare: unknown scenario!";
876
}
877
}  // namespace radix