Add spec for new Interval / IntervalIndex methods: .overlaps(), .covers()
State: closed

- [x] part 2/2 for #16316
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`

Working on parameterizing the tests. Will ping when ready for review. 

Labels:
name: Testing
description: pandas testing functions or related to the test suite
name: Interval
description: Interval data type

Comments:
Hello @zfrenchee! Thanks for updating the PR.



 - In the file [`pandas/tests/indexes/interval/test_interval_overlaps_covers.py`](https://github.com/pandas-dev/pandas/blob/d28f9326de26882a9b4dc0bee9dec5c598747190/pandas/tests/indexes/interval/test_interval_overlaps_covers.py), following are the PEP8 issues :

> [Line 32:41](https://github.com/pandas-dev/pandas/blob/d28f9326de26882a9b4dc0bee9dec5c598747190/pandas/tests/indexes/interval/test_interval_overlaps_covers.py#L32): [E128](https://duckduckgo.com/?q=pep8%20E128) continuation line under-indented for visual indent
> [Line 53:41](https://github.com/pandas-dev/pandas/blob/d28f9326de26882a9b4dc0bee9dec5c598747190/pandas/tests/indexes/interval/test_interval_overlaps_covers.py#L53): [E128](https://duckduckgo.com/?q=pep8%20E128) continuation line under-indented for visual indent





##### Comment last updated on April 02, 2018 at 20:45 Hours UTC
Ready for a look-over on structure @jreback @jschendel. Are the tests in the right place / well structured? Are there missing tests / cases?
what is the reason for *both* covers and overlaps? 
@jreback (from @shoyer):

> An interval covers another interval if all points in the second interval are found in the first interval.
>
> An interval overlaps another interval if there exist any points found in both intervals.

-- (https://github.com/pandas-dev/pandas/issues/16316#issuecomment-301352130)

I personally am interested in overlaps, but I can imagine people might want to ask what intervals are covered by their IntervalIndex or vice-versa. Does that answer the question? 
> what is the reason for both covers and overlaps?

FWIW other implementations of `Interval` have both methods, e.g. the `intervaltree` package on pypi, and `range` types in postgres, albeit with a slightly different naming convention for `covers`.  The `intervaltree` package uses a `contains_interval` method for `covers`.  In postgres it's just an operator, `@>`,  which is described in the docs as "contains range".  I suppose we could maybe rename `covers` to be more in line with these, but I don't really have a strong opinion either way.

Is there any utility in adding a `strict` kwarg to `covers`?  By that I basically mean `strict=False` is existing behavior (default), `strict=True` is existing behavior and no shared endpoints:
```python
In [1]: iv = Interval(0, 1)

In [2]: iv.covers(iv, strict=False)
Out[2]: True

In [3]: iv.covers(iv, strict=True)
Out[3]: False
```
Could probably wait to see if there's demand for `strict` prior to implementing, unless there's a reason anyone wants it immediately implemented.

rebase and push again, fixed some hanging by Travis CI
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=h1) Report
> Merging [#18975](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/cdfce2b0ad99f7faad57cc5247cf33aab5725bed?src=pr&el=desc) will **decrease** coverage by `0.31%`.
> The diff coverage is `n/a`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/18975/graphs/tree.svg?height=150&width=650&token=eZ4WkYLtcO&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #18975      +/-   ##
==========================================
- Coverage   91.82%    91.5%   -0.32%     
==========================================
  Files         152      150       -2     
  Lines       49248    48739     -509     
==========================================
- Hits        45222    44600     -622     
- Misses       4026     4139     +113
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `89.87% <ø> (-0.34%)` | :arrow_down: |
| #single | `41.73% <ø> (-0.17%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/tseries/plotting.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL3RzZXJpZXMvcGxvdHRpbmcucHk=) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/plotting/\_compat.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL19jb21wYXQucHk=) | `62% <0%> (-28.91%)` | :arrow_down: |
| [pandas/io/parquet.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL3BhcnF1ZXQucHk=) | `52.29% <0%> (-19.51%)` | :arrow_down: |
| [pandas/core/missing.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvbWlzc2luZy5weQ==) | `84.3% <0%> (-7.35%)` | :arrow_down: |
| [pandas/plotting/\_timeseries.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL190aW1lc2VyaWVzLnB5) | `60.82% <0%> (-4.49%)` | :arrow_down: |
| [pandas/core/ops.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvb3BzLnB5) | `93.11% <0%> (-3.25%)` | :arrow_down: |
| [pandas/core/reshape/tile.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS90aWxlLnB5) | `90.25% <0%> (-3.12%)` | :arrow_down: |
| [pandas/io/html.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2h0bWwucHk=) | `85.98% <0%> (-2.81%)` | :arrow_down: |
| [pandas/io/formats/format.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvZm9ybWF0LnB5) | `96.24% <0%> (-2.01%)` | :arrow_down: |
| [pandas/core/internals.py](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW50ZXJuYWxzLnB5) | `94.53% <0%> (-1.01%)` | :arrow_down: |
| ... and [74 more](https://codecov.io/gh/pandas-dev/pandas/pull/18975/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=footer). Last update [cdfce2b...d28f932](https://codecov.io/gh/pandas-dev/pandas/pull/18975?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

@zfrenchee : Looks like you have some lint errors.  Otherwise, Travis looks happy to me.
I'd like to revisit the interface we agreed upon (initially from @shoyer) which this PR introduces tests for. The interface was

```
class Interval:
    def covers(self, other: Interval) -> bool
    def covers(self, other: IntervalIndex) -> IntegerArray1D
    def overlaps(self, other: Interval) -> bool
    def overlaps(self, other: IntervalIndex) -> IntegerArray1D

class IntervalIndex:
    def covers(self, other: Interval) -> IntegerArray1D
    def covers(self, other: IntervalIndex) -> Tuple[IntegerArray1D, IntegerArray1D]
    def overlaps(self, other: Interval) -> IntegerArray1D
    def overlaps(self, other: IntervalIndex) -> Tuple[IntegerArray1D, IntegerArray1D]
```

This is the last call for modifications to that interface in this PR. @jreback @jorisvandenbossche @gfyoung . What do you think? 


Thinking about this again: there's some ambiguity about whether coverage for `IntervalIndex.covers(IntervalIndex)`  is:
- elementwise: does each interval in the first index cover each corresponding interval?
- all: does each interval in the first index cover *all* of the second intervals?
- any: does each interval in the first index cover *any* of the second intervals?

Most pandas operations work elementwise, so arguably that's clearest. That would suggest we should only return booleans/boolean-arrays, i.e.,
```
class Interval:
    def covers(self, other: Interval) -> bool
    def covers(self, other: IntervalIndex) -> BoolArray1D
    def overlaps(self, other: Interval) -> bool
    def overlaps(self, other: IntervalIndex) -> BoolArray1D

class IntervalIndex:
    def covers(self, other: Interval) -> BoolArray1D
    def covers(self, other: IntervalIndex) -> BoolArray1D
    def overlaps(self, other: Interval) -> BoolArray1D
    def overlaps(self, other: IntervalIndex) -> BoolArray1D
```

If we adopted this choice, we would save "covers all", "covers any", "overlaps all" and "overlaps any" for another method, which might be implemented in the future (if necessary).
Thanks for those comments @shoyer. 

I'm personally rather attached to your original suggestion, because I think all these other methods can be expressed with short recipes derived from the methods in their current form in the spec. I'm not sure anyone will really be asking the question "which intervals in IntervalIndex A cover _every_ interval in IntervalIndex B?" and even if they did want to ask that, using the current spec they could get indices back and then check if that index set is complete (2 lines instead of 1). The reverse doesn't work -- If we provide these methods, we can't ask the more basic question "which intervals from A cover which intervals from B?" 

Are you thinking of a particular other method in the current pandas API to base your suggestion from? If so we have to weigh consistency as a factor. Let me know what you think. 
@pep8speaks 
@jreback @gfyoung I believe this is ready for merge. 
@jreback done. feel free to have another look. 
@jreback 

```
~/Documents/pandas(master) » git remote add upstream https://github.com/pandas-dev/pandas.git
------------------------------------------------------------
~/Documents/pandas(master) » git diff upstream/master -u -- "*.py" | flake8 --diff                                                     alex@alexs-mbp
fatal: bad revision 'upstream/master'
```
@zfrenchee your upstream may be called something else, use ``git remote -v`` to see (our docs say to call it this, which is why we put this here)
@jreback how do I configure autopep so it conforms to pandas style? When I invoke it now, it makes >79 char lines.
I think you have to tell autopep to fix the lines, its not automatic:

``autopep8 --max-line-length``

note that we generally *don't* like to use autopep for line breaking. we do this manually (because autopep8  produces weird output).

Its not that much code you can easily fix it manually.
@jreback green. 
Before we merge this, can someone else weigh in on the API options here? See https://github.com/pandas-dev/pandas/pull/18975#issuecomment-354787556 and the comment below
> Most pandas operations work elementwise, so arguably that's clearest. That would suggest we should only return booleans/boolean-arrays, i.e.,

I agree with this. For me it looks very strange that a Index operation returns a tuple.

But I find it very hard to think about this without code. @zfrenchee could you write up a few hypothetical example of how you would use it? To have a bit more the idea how it would look like.

As I asked for in the other PR as well, I think it would also be helpful to clear out the design to actually write out the reference docs (the docstrings of those methods). We can eg add them now as a multi-line comment at the top of the test files. BTW, I think it would also be rather easy to actually implement the methods (a basic, possibly non-performant implementation). That might make it easier to experiment with. 
> can someone else weigh in on the API options here

I agree with @shoyer that returning booleans/boolean-arrays makes more sense for `overlaps` and `covers`.  I plan to implement an interval accessor (#16401) in the near future now that the new accessor interface PR has been merged.  I haven't looked too closely at the implementation, but I _think_ returning booleans would enable indexing syntax along the lines of `df[df.interval_col.iv.overlaps(other)]`.  At the very least it seems like it would make this behavior consistent with the accessor.

That being said, I'm not opposed to adding the functionality suggested by @zfrenchee, but it might be better served with a different name.  Perhaps with a prefix along the lines of `get_*`, e.g. `IntervalIndex.get_overlaps(other)`, or maybe even a more generic method with a `how` parameter, e.g. `IntervalIndex.something_generic(other, how='overlaps|covers|...')`.

Unrelated, but one thing that stands out to me is `Interval.overlaps(IntervalIndex)` (likewise `covers`).  Looks like this is identical to `IntervalIndex.overlaps(Interval)`, so having both seems a little redundant.  Syntactically `Interval.overlaps(IntervalIndex)` feels a little strange to me, since you have a method on a scalar taking a non-scalar argument.  I'd be fine removing `Interval.overlaps(IntervalIndex)` and just implementing `IntervalIndex.overlaps(Interval)` (likewise `covers`), but I don't have particularly strong feelings either way.
> But I find it very hard to think about this without code. @zfrenchee could you write up a few hypothetical example of how you would use it? To have a bit more the idea how it would look like.

I'm hoping to do genome arithmetic, like [BEDtools](http://bedtools.readthedocs.io/en/latest/). Check out the [BEDtools tools](http://bedtools.readthedocs.io/en/latest/content/bedtools-suite.html), e.g. [intersect](http://bedtools.readthedocs.io/en/latest/content/tools/intersect.html), [merge](http://bedtools.readthedocs.io/en/latest/content/tools/merge.html), and [closest](http://bedtools.readthedocs.io/en/latest/content/tools/closest.html). With the current implementation of overlaps (in order to do something like bedtools intersect) I would do
```
one, two = idx1.overlaps(idx2)
return pd.concat((idx1[one], idx2[two]), axis=1)
```

I think that the issue with the boolean overlaps function is that it's hard to trace what overlaps what. E.g. consider: 
```
idx1 = IntervalIndex.from_tuples([(1, 5), (2, 6)])
idx2 = IntervalIndex.from_tuples([(0, 4), (3, 7)])
```
then if `idx1.overlaps(idx2)` returns a boolean mask on `idx1`....
```
pd.concat((idx1[idx1.overlaps(idx2)], idx2[idx2.overlaps(idx2)]))
```
misses half of the overlaps. Do you see what I mean? Let me know if that needs to be clearer. Basically, if it were booleans, you wouldn't necessarily get all pairs of overlaps out from the overlaps function. I think `.overlaps()` should be able to tell you what all the overlaps are. 

---

> I agree with this. For me it looks very strange that a Index operation returns a tuple.

I can't deny it looks off. However, for this index, for this operation, it might be the only thing that makes sense? Very open to alternatives that can find all the overlaps...

---

> Unrelated, but one thing that stands out to me is Interval.overlaps(IntervalIndex) (likewise covers). Looks like this is identical to IntervalIndex.overlaps(Interval), so having both seems a little redundant. Syntactically Interval.overlaps(IntervalIndex) feels a little strange to me, since you have a method on a scalar taking a non-scalar argument.

This is a good point. [We discussed this a little.](https://github.com/pandas-dev/pandas/issues/16316#issuecomment-354573878) I also don't have strong feelings, and agree that if we were to remove one of them, `Interval.overlaps(IntervalIndex)` would be the one. I'd love to find some other useful functionality for that function signature, but I wasn't able to come up with one. I feel very weakly that if the choices are keep it or remove it, I would keep it for now. 

@shoyer @jreback @jschendel @jorisvandenbossche  

bump @jreback @shoyer @jschendel @jorisvandenbossche 
@zfrenchee I am still trying to understand the logic behind `one, two = idx1.overlaps(idx2)` (I mean what it does exactly). Can you show what the output would be for the example `idx1` and `idx2` ?
(sidenote: if we decide something like this it too complicated or inconsistent for as a method, we should make sure it is not too hard to write a function that does that)
@jorisvandenbossche: @shoyer 's original API plan, which I add tests for in this PR:

```
>>> idx1 = IntervalIndex.from_tuples([(1, 5), (2, 6)])
>>> idx2 = IntervalIndex.from_tuples([(0, 4), (3, 7)])
>>> idx1.overlaps(idx2)
([0, 0, 1, 1], [0, 1, 0, 1])
```
as opposed to 
```
>>> idx1 = IntervalIndex.from_tuples([(1, 5), (2, 6)])
>>> idx2 = IntervalIndex.from_tuples([(0, 4), (3, 7)])
>>> idx1.overlaps(idx2)
[true, true]
```


I'm alright renaming the method `.find_overlaps` if that reduces the confusion for not returning boolean masks, or even (maybe) setting this as a method on dataframes with IntervalIndex indexes, rather than on the indexes themselves... I just really want this functionality!
> I am still trying to understand the logic behind `one, two = idx1.overlaps(idx2)` (I mean what it does exactly)

@jorisvandenbossche : IIUC the "plain english" interpretation is, looking at the two lists pairwise, specifically which interval in `idx1` overlaps which interval in `idx2`.  For example, in the output that @zfrenchee just posted:
```python
>>> idx1 = IntervalIndex.from_tuples([(1, 5), (2, 6)])
>>> idx2 = IntervalIndex.from_tuples([(0, 4), (3, 7)])
>>> idx1.overlaps(idx2)
([0, 0, 1, 1], [0, 1, 0, 1])
```
The first pairwise element, `(0, 0)`, says that `idx1[0]` overlaps `idx2[0]`.  And likewise for the other pairs, `(0, 1)`, `(1, 0)`, and `(1, 1)`.
Thanks @jschendel. Sorry if I wasn't clear, @jorisvandenbossche.