[ADT] IntervalMap: add contains(a, b) method

[labath]

Summary

This function checks whether the interval map contains any mapping in
the range [a;b]. The motivation is to enable checking for overlap before
inserting a new interval into the map.

[labath]

See D55761 for an example of usage. The reason I am sinking this functionality here is because I am about to add a second piece of code with similar logic (and it also seems like a logical extension of the current API).

[vsk]

include/llvm/ADT/IntervalMap.h

1140

When I read ‘contains’, I tend to assume ‘contains entire subset/subrange’. Would ‘containsSubrangeOf’ or some variant help readability?

1145

It might help future readers out to explain that at this point, y = find(a).

[labath]

include/llvm/ADT/IntervalMap.h

1140

Good question. I chose contains because this is similar in functionality to std::map::contains, but it is true that this whole class is not very STL-like, so maybe it's not good to try to appear like it is.

If we're going to go with a custom name, then maybe overlaps could do the trick (there is a IntervalMapOverlaps class at the bottom of this file, which is doing something similar, but for two maps)?

[vsk]

I think it'll be really useful to have this helper around. Thanks, lgtm with the name change!

include/llvm/ADT/IntervalMap.h

1140

'overlaps' sgtm.

[dblaikie]

include/llvm/ADT/IntervalMap.h

1140

'intersects'? (the word is in the comment below, which seems telling)

[labath]

• rename the function to "overlaps"
• fix up comments

[labath]

include/llvm/ADT/IntervalMap.h

1140

"overlap" seems to be more consistent with other usages in this file (e.g. "(...) stopLess(a, b) can be used to determine if two
intervals overlap."). So, I propose to stick with overlaps, and change the comment to use this word also, if that's ok with you.

[dexonsmith]

unittests/ADT/IntervalMapTest.cpp

622

I’m surprised this one returns true. Are these half-open intervals? If so I think you shouldn’t get overlap until you stop at 11.

[labath]

unittests/ADT/IntervalMapTest.cpp

622

These are closed on both sides. Half-open intervals are tested below (where this indeed returns false). The half-openedness of an IntervalMap is controlled via template arguments (see line 17 and 18 in this file).

[dblaikie]

include/llvm/ADT/IntervalMap.h

1140

Fair enough - I don't feel too strongly (:

[dexonsmith]

unittests/ADT/IntervalMapTest.cpp

622

Got it; thanks for explaining!

include/llvm/ADT/IntervalMap.h

const_iterator find(KeyT x) const {
     return I;
   }
 
   iterator find(KeyT x) {
     iterator I(*this);
     I.find(x);
     return I;
   }
+
+  /// overlaps(a, b) - Return true if the intervals in this map overlap with the
+  /// interval [a;b].
+  bool overlaps(KeyT a, KeyT b) {
+    assert(Traits::nonEmpty(a, b));
+    const_iterator I = find(a);
+    if (!I.valid())
+      return false;
+    // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the
+    // second part (y = find(a).stop()), so it is sufficient to check the first
+    // one.
+    return !Traits::stopLess(b, I.start());
+  }
 };
 
 /// treeSafeLookup - Return the mapped value at x or NotFound, assuming a
 /// branched root.
 template <typename KeyT, typename ValT, unsigned N, typename Traits>
 ValT IntervalMap<KeyT, ValT, N, Traits>::
 treeSafeLookup(KeyT x, ValT NotFound) const {
   assert(branched() && "treeLookup assumes a branched root");

unittests/ADT/IntervalMapTest.cpp

TEST(IntervalMapTest, RandomCoalescing) {
   // Map should be fully coalesced after that exercise.
   EXPECT_FALSE(map.empty());
   EXPECT_EQ(0u, map.start());
   EXPECT_EQ(40959u, map.stop());
   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 
 }
 
+TEST(IntervalMapTest, Overlaps) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+  map.insert(10, 20, 0);
+  map.insert(30, 40, 0);
+  map.insert(50, 60, 0);
+
+  EXPECT_FALSE(map.overlaps(0, 9));
+  EXPECT_TRUE(map.overlaps(0, 10));
+  EXPECT_TRUE(map.overlaps(0, 15));
+  EXPECT_TRUE(map.overlaps(0, 25));
+  EXPECT_TRUE(map.overlaps(0, 45));
+  EXPECT_TRUE(map.overlaps(10, 45));
+  EXPECT_TRUE(map.overlaps(30, 45));
+  EXPECT_TRUE(map.overlaps(35, 36));
+  EXPECT_TRUE(map.overlaps(40, 45));
+  EXPECT_FALSE(map.overlaps(45, 45));
+  EXPECT_TRUE(map.overlaps(60, 60));
+  EXPECT_TRUE(map.overlaps(60, 66));
+  EXPECT_FALSE(map.overlaps(66, 66));
+}
+
+TEST(IntervalMapTest, OverlapsHalfOpen) {
+  UUHalfOpenMap::Allocator allocator;
+  UUHalfOpenMap map(allocator);
+  map.insert(10, 20, 0);
+  map.insert(30, 40, 0);
+  map.insert(50, 60, 0);
+
+  EXPECT_FALSE(map.overlaps(0, 9));
+  EXPECT_FALSE(map.overlaps(0, 10));
+  EXPECT_TRUE(map.overlaps(0, 15));
+  EXPECT_TRUE(map.overlaps(0, 25));
+  EXPECT_TRUE(map.overlaps(0, 45));
+  EXPECT_TRUE(map.overlaps(10, 45));
+  EXPECT_TRUE(map.overlaps(30, 45));
+  EXPECT_TRUE(map.overlaps(35, 36));
+  EXPECT_FALSE(map.overlaps(40, 45));
+  EXPECT_FALSE(map.overlaps(45, 46));
+  EXPECT_FALSE(map.overlaps(60, 61));
+  EXPECT_FALSE(map.overlaps(60, 66));
+  EXPECT_FALSE(map.overlaps(66, 67));
+}
+
 TEST(IntervalMapOverlapsTest, SmallMaps) {
   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
   UUMap::Allocator allocator;
   UUMap mapA(allocator);
   UUMap mapB(allocator);
 
   // empty, empty.
   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());