Page MenuHomePhabricator

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

Authored by labath on Dec 17 2018, 4:26 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

labath created this revision.Dec 17 2018, 4:26 AM

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 added inline comments.Dec 17 2018, 9:08 AM
include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

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

1145 ↗(On Diff #178442)

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

labath marked an inline comment as done.Dec 17 2018, 9:32 AM
labath added inline comments.
include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

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 added a comment.Dec 17 2018, 9:36 AM

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

include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

'overlaps' sgtm.

dblaikie added inline comments.Dec 17 2018, 10:58 AM
include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

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

labath updated this revision to Diff 178613.Dec 18 2018, 12:43 AM
labath marked 4 inline comments as done.
  • rename the function to "overlaps"
  • fix up comments
labath added inline comments.Dec 18 2018, 12:44 AM
include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

"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 added inline comments.Dec 18 2018, 7:05 AM
unittests/ADT/IntervalMapTest.cpp
622 ↗(On Diff #178613)

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 marked an inline comment as done.Dec 18 2018, 7:09 AM
labath added inline comments.
unittests/ADT/IntervalMapTest.cpp
622 ↗(On Diff #178613)

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 added inline comments.Dec 18 2018, 7:44 AM
include/llvm/ADT/IntervalMap.h
1140 ↗(On Diff #178442)

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

dexonsmith added inline comments.Dec 18 2018, 1:41 PM
unittests/ADT/IntervalMapTest.cpp
622 ↗(On Diff #178613)

Got it; thanks for explaining!

This revision was not accepted when it landed; it landed in state Needs Review.Dec 21 2018, 5:08 AM
Closed by commit rL349898: [ADT] IntervalMap: add overlaps(a, b) method (authored by labath, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.