From cb9e08f328892eaf46825d7426216995ca673a67 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Thu, 16 Dec 2010 01:18:29 +0000
Subject: [PATCH] Add IntervalMapOverlaps - An iterator for overlapping
 intervals in two IntervalMaps.

The IntervalMaps can have different template parameters, but the KeyT and Traits
types must be the same.

Tests are forthcoming.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121935 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/IntervalMap.h | 91 ++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)

diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index a44ee6bee5a..ae79e845088 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -940,6 +940,7 @@ class IntervalMap {
 
 public:
   typedef typename Sizer::Allocator Allocator;
+  typedef Traits KeyTraits;
 
 private:
   // The root data is either a RootLeaf or a RootBranchData instance.
@@ -2006,6 +2007,96 @@ iterator::overflow(unsigned Level) {
   return SplitRoot;
 }
 
+//===----------------------------------------------------------------------===//
+//---                       IntervalMapOverlaps                           ----//
+//===----------------------------------------------------------------------===//
+
+/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two
+/// IntervalMaps. The maps may be different, but the KeyT and Traits types
+/// should be the same.
+///
+/// Typical uses:
+///
+/// 1. Test for overlap:
+///    bool overlap = IntervalMapOverlaps(a, b).valid();
+///
+/// 2. Enumerate overlaps:
+///    for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... }
+///
+template <typename MapA, typename MapB>
+class IntervalMapOverlaps {
+  typedef typename MapA::KeyTraits Traits;
+  typename MapA::const_iterator posA;
+  typename MapB::const_iterator posB;
+
+  /// advance - Move posA and posB forward until reaching an overlap, or until
+  /// either meets end.
+  /// Don't move the iterators if they are already overlapping.
+  void advance() {
+    for (;;) {
+      // Make a.end > b.start.
+      posA.advanceTo(posB.start());
+      if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start()))
+        return;
+      // Make b.end > a.start.
+      posB.advanceTo(posA.start());
+      if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
+        return;
+    }
+  }
+
+public:
+  /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
+  IntervalMapOverlaps(const MapA &a, const MapB &b)
+    : posA(b.empty() ? a.end() : a.find(b.start())),
+      posB(posA.valid() ? b.find(posA.start()) : b.end()) {
+    if (valid())
+      advance();
+  }
+
+  /// valid - Return true if iterator is at an overlap.
+  bool valid() const {
+    return posA.valid() && posB.valid();
+  }
+
+  /// a - access the left hand side in the overlap.
+  const typename MapA::const_iterator &a() const { return posA; }
+
+  /// b - access the right hand side in the overlap.
+  const typename MapB::const_iterator &b() const { return posB; }
+
+  /// skipA - Move to the next overlap that doesn't involve a().
+  void skipA() {
+    ++posA;
+    if (!posA.valid() || !Traits::stopLess(posB.end(), posA.start()))
+      return;
+    // Second half-loop of advance().
+    posB.advanceTo(posA.start());
+    if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
+      return ;
+    advance();
+  }
+
+  /// skipB - Move to the next overlap that doesn't involve b().
+  void skipB() {
+    ++posB;
+    if (!posB.valid() || !Traits::stopLess(posA.end(), posB.start()))
+        return;
+    advance();
+  }
+
+  /// Preincrement - Move to the next overlap.
+  IntervalMapOverlaps &operator++() {
+    // Bump the iterator that ends first. The other one may have more overlaps.
+    if (Traits::startLess(posB.end(), posA.end()))
+      skipB();
+    else
+      skipA();
+    return *this;
+  }
+};
+
+
 } // namespace llvm
 
 #endif
-- 
2.34.1