ENH: Intervalindex
State: closed

closes #7640 
closes #8625


reprise of #8707 
- redid the construction impl a bit, now uses the proper Index calling conventions (as well as other sub-classing conventions).
- more testing, including all generic index tests (but still prob need some more)
- add ._mask to track internal nans (its lazily computed), IOW you can have null entries in the index.
- using tempita, so have intervalindex.pxi.in
- the extension is housed in _interval now, rather than a part of lib
- IntervalDtype is full fledged

```
In [11]: df = DataFrame({'A': range(10)})
    ...: s = pd.cut(df.A, 5)
    ...: df['B'] = s
    ...: df['C'] = np.array(s)
    ...: df2 = df.set_index('B')
    ...: df3 = df.set_index('C')
    ...: 
    ...: 

In [12]: df
Out[12]: 
   A              B              C
0  0  (-0.009, 1.8]  (-0.009, 1.8]
1  1  (-0.009, 1.8]  (-0.009, 1.8]
2  2     (1.8, 3.6]     (1.8, 3.6]
3  3     (1.8, 3.6]     (1.8, 3.6]
4  4     (3.6, 5.4]     (3.6, 5.4]
5  5     (3.6, 5.4]     (3.6, 5.4]
6  6     (5.4, 7.2]     (5.4, 7.2]
7  7     (5.4, 7.2]     (5.4, 7.2]
8  8     (7.2, 9.0]     (7.2, 9.0]
9  9     (7.2, 9.0]     (7.2, 9.0]

In [13]: df.dtypes
Out[13]: 
A       int64
B    category
C      object
dtype: object

In [14]: df.C.values
Out[14]: 
array([Interval(-0.0089999999999999993, 1.8, closed='right'),
       Interval(-0.0089999999999999993, 1.8, closed='right'),
       Interval(1.8, 3.6000000000000001, closed='right'),
       Interval(1.8, 3.6000000000000001, closed='right'),
       Interval(3.6000000000000001, 5.4000000000000004, closed='right'),
       Interval(3.6000000000000001, 5.4000000000000004, closed='right'),
       Interval(5.4000000000000004, 7.2000000000000002, closed='right'),
       Interval(5.4000000000000004, 7.2000000000000002, closed='right'),
       Interval(7.2000000000000002, 9.0, closed='right'),
       Interval(7.2000000000000002, 9.0, closed='right')], dtype=object)
```

Similar indicies
```
In [6]: df3.index
Out[6]: 
IntervalIndex(left=[-0.009, -0.009, 1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2],
              right=[1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2, 9.0, 9.0],
              closed='right',
              name='C',
              dtype='interval[float64]')

In [7]: df2.index
Out[7]: CategoricalIndex([(-0.009, 1.8], (-0.009, 1.8], (1.8, 3.6], (1.8, 3.6], (3.6, 5.4], (3.6, 5.4], (5.4, 7.2], (5.4, 7.2], (7.2, 9.0], (7.2, 9.0]], categories=[(-0.009, 1.8], (1.8, 3.6], (3.6, 5.4], (5.4, 7.2], (7.2, 9.0]], ordered=True, name='B', dtype='category')
```

indexing
```
In [2]: df2
Out[2]: 
               A              C
B                              
(-0.009, 1.8]  0  (-0.009, 1.8]
(-0.009, 1.8]  1  (-0.009, 1.8]
(1.8, 3.6]     2     (1.8, 3.6]
(1.8, 3.6]     3     (1.8, 3.6]
(3.6, 5.4]     4     (3.6, 5.4]
(3.6, 5.4]     5     (3.6, 5.4]
(5.4, 7.2]     6     (5.4, 7.2]
(5.4, 7.2]     7     (5.4, 7.2]
(7.2, 9.0]     8     (7.2, 9.0]
(7.2, 9.0]     9     (7.2, 9.0]

In [3]: df2.loc[[2, 5]]
Out[3]: 
            A           C
B                        
(1.8, 3.6]  2  (1.8, 3.6]
(1.8, 3.6]  3  (1.8, 3.6]
(3.6, 5.4]  4  (3.6, 5.4]
(3.6, 5.4]  5  (3.6, 5.4]

# work similarly
In [5]: df3.loc[[2, 5]]
Out[5]: 
            A           B
C                        
(1.8, 3.6]  2  (1.8, 3.6]
(1.8, 3.6]  3  (1.8, 3.6]
(3.6, 5.4]  4  (3.6, 5.4]
(3.6, 5.4]  5  (3.6, 5.4]
```

Labels:
name: Enhancement
name: Interval
description: Interval data type

Comments:
@shoyer so ``interval_range`` is sort of trivial for the basic case, but I think you want something like

```
pd.interval_range(start, stop, step=1)

In [1]: pd.IntervalIndex.from_breaks(np.arange(0, 10, 2))
Out[1]: 
IntervalIndex(left=[0, 2, 4, 6],
              right=[2, 4, 6, 8],
              closed='right',
              dtype='interval[int64]')
```

what other signature is useful here?
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=h1) Report
> :exclamation: No coverage uploaded for pull request base (`master@7ee73ff`). [Click here to learn what that means](https://docs.codecov.io/docs/error-reference#section-missing-base-commit).
> The diff coverage is `91.47%`.

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

```diff
@@            Coverage Diff            @@
##             master   #15309   +/-   ##
=========================================
  Coverage          ?      91%           
=========================================
  Files             ?      145           
  Lines             ?    50236           
  Branches          ?        0           
=========================================
  Hits              ?    45718           
  Misses            ?     4518           
  Partials          ?        0
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.8% <91.47%> (?)` | |
| #single | `40.38% <25.71%> (?)` | |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/types/api.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2FwaS5weQ==) | `100% <ø> (ø)` | |
| [pandas/tseries/period.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL3RzZXJpZXMvcGVyaW9kLnB5) | `92.74% <100%> (ø)` | |
| [pandas/types/inference.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2luZmVyZW5jZS5weQ==) | `98.33% <100%> (ø)` | |
| [pandas/types/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2dlbmVyaWMucHk=) | `100% <100%> (ø)` | |
| [pandas/indexes/api.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvYXBpLnB5) | `98.68% <100%> (ø)` | |
| [pandas/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvbXVsdGkucHk=) | `96.7% <100%> (ø)` | |
| [pandas/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvY2F0ZWdvcnkucHk=) | `98.43% <100%> (ø)` | |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.57% <100%> (ø)` | |
| [pandas/core/api.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXBpLnB5) | `100% <100%> (ø)` | |
| [pandas/core/indexing.py](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhpbmcucHk=) | `94.01% <100%> (ø)` | |
| ... and [10 more](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15309?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/15309?src=pr&el=footer). Last update [7ee73ff...11ab1e1](https://codecov.io/gh/pandas-dev/pandas/pull/15309?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
> so interval_range is sort of trivial for the basic case, but I think you want something like

Yes, that's one use case, though it's not necessarily worth doing it that's all it does.

I was thinking of `interval_range` also for datetimes (with `start`/`periods` arguments), as part of envisioning Interval as a eventual replacement for Period. But that is a long way off (if ever) and I don't think it will be terribly useful in the meanwhile, unless we get Interval working for resample operations.
@shoyer 

```
In [1]: df = DataFrame({'A': range(10)})
   ...: s = pd.cut(df.A, 5)
   ...: df['B'] = s
   ...: df = df.set_index('B')
   ...: 

In [2]: df
Out[2]: 
               A
B               
(-0.009, 1.8]  0
(-0.009, 1.8]  1
(1.8, 3.6]     2
(1.8, 3.6]     3
(3.6, 5.4]     4
(3.6, 5.4]     5
(5.4, 7.2]     6
(5.4, 7.2]     7
(7.2, 9.0]     8
(7.2, 9.0]     9

In [3]: df.index
Out[3]: 
IntervalIndex(left=[-0.009, -0.009, 1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2],
              right=[1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2, 9.0, 9.0],
              closed='right',
              name='B',
              dtype='interval[float64]')
```

```
In [4]: df.loc[4]
Out[4]: 
            A
B            
(3.6, 5.4]  4
(3.6, 5.4]  5

In [5]: df.index.get_loc(4)
Out[5]: array([4, 5])
```

```
In [6]: df.index.get_indexer([4])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-6-f6dde575d826> in <module>()
----> 1 df.index.get_indexer([4])
In [6]: df.index.get_indexer([4])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-6-f6dde575d826> in <module>()
----> 1 df.index.get_indexer([4])

/Users/jreback/pandas/pandas/indexes/interval.py in get_indexer(self, target, method, limit, tolerance)
    521                     'for IntervalIndex indexers')
    522             else:
--> 523                 return self._engine.get_indexer(target.values)
    524 
    525     def sort_values(self, return_indexer=False, ascending=True):

/Users/jreback/pandas/pandas/src/intervaltree.pxi in pandas._interval.IntervalTree.get_indexer (pandas/src/interval.c:11925)()
    141                 result.append(-1)
    142             elif result.data.n > old_len + 1:
--> 143                 raise KeyError(
    144                     'indexer does not intersect a unique set of intervals')
    145             old_len = result.data.n

KeyError: 'indexer does not intersect a unique set of intervals'

In [7]: df.index.is_unique
Out[7]: False
```
Is [6] just not well-represented in the intervaltrees?

I actually think this is a pretty common case. 
> In [3]: df.index
Out[3]: 
IntervalIndex(left=[-0.009, -0.009, 1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2],
              right=[1.8, 1.8, 3.6, 3.6, 5.4, 5.4, 7.2, 7.2, 9.0, 9.0],
              closed='right',
              name='B',
              dtype='interval[float64]')

Shouldn't this be a CategoricalIndex with IntervalIndex categories?

> Is [6] just not well-represented in the intervaltrees?

I think it's just as well represented for interval trees as it is for hash tables. But my understanding is that `get_indexer` is always supposed to return an array of the same length as the requested labels, so it doesn't work if you don't have unique values. I think this is the analogous case for `Int64Index`:
```
>>> idx = pd.Index([1, 2, 2, 2, 3])
>>> idx.get_indexer([1])  # note that I'm not even indexing the duplicated value (2)
InvalidIndexError: Reindexing only valid with uniquely valued Index objects
```

So actually, for consistency we should probably raise in `get_indexer` whenever the index has non-unique or even overlapping values.

For this sort of behavior, I think you want `get_indexer_non_unique` -- and I actually wrote an IntervalTree method for that, though it may not be hooked up into IntervalIndex.
> Shouldn't this be a CategoricalIndex with IntervalIndex categories?

interesting you should say that, I fiddled with this a bit

```
In [1]: df = DataFrame({'A': range(10)})
   ...: s = pd.cut(df.A, 5)
   ...: 

In [2]: s
Out[2]: 
0    (-0.009, 1.8]
1    (-0.009, 1.8]
2       (1.8, 3.6]
3       (1.8, 3.6]
4       (3.6, 5.4]
5       (3.6, 5.4]
6       (5.4, 7.2]
7       (5.4, 7.2]
8       (7.2, 9.0]
9       (7.2, 9.0]
Name: A, dtype: category
Categories (5, interval[float64]): [(-0.009, 1.8] < (1.8, 3.6] < (3.6, 5.4] < (5.4, 7.2] < (7.2, 9.0]]

In [4]: s.cat.categories
Out[4]: 
IntervalIndex(left=[-0.009, 1.8, 3.6, 5.4, 7.2],
              right=[1.8, 3.6, 5.4, 7.2, 9.0],
              closed='right',
              dtype='interval[float64]')
```

so ``.cut`` return a ``Categorical`` (Series/Index depending on what's passed in). This is the *same* as we do now, but the Index is made up of the Interval-like strings.

So this actually makes a lot of sense. BUT, if you assign it to a DataFrame what should this do. I *can* leave it as a categorical, but then you get weird inconsistences, see here: https://github.com/pandas-dev/pandas/pull/15309/commits/bfd99d399a3f4d1fc25e731d3341687b17de91e9, so instead I coerce this to a ndarray of intervals. Thus the index because an ``IntervalIndex`` automatically. Which is way more useful that a ``Categorical of IntervalIndex``. I think this is ok.
> So this actually makes a lot of sense. BUT, if you assign it to a DataFrame what should this do. I can leave it as a categorical, but then you get weird inconsistences, see here: bfd99d3, so instead I coerce this to a ndarray of intervals. Thus the index because an IntervalIndex automatically. Which is way more useful that a Categorical of IntervalIndex. I think this is ok.

ahh, yes I can easily try different paths for unique and non-unique, ok.

Do you have an implementation for non-unique? (e.g. given indexers return the included intervals for that indexer). 
@shoyer ahh I see you DO have a ``get_indexer_non_unique``, ahh let me try that.
```
In [1]:         df = DataFrame({'A': range(10)})
   ...:         s = pd.cut(df.A, 5)
   ...:         df['B'] = s
   ...:         df = df.set_index('B')
   ...: 

In [2]: df
Out[2]: 
               A
B               
(-0.009, 1.8]  0
(-0.009, 1.8]  1
(1.8, 3.6]     2
(1.8, 3.6]     3
(3.6, 5.4]     4
(3.6, 5.4]     5
(5.4, 7.2]     6
(5.4, 7.2]     7
(7.2, 9.0]     8
(7.2, 9.0]     9
```

this all looks ok
```
In [3]: df.loc[[4]]
Out[3]: 
            A
B            
(3.6, 5.4]  4
(3.6, 5.4]  5

In [4]: df.loc[[4, 5]]
Out[4]: 
            A
B            
(3.6, 5.4]  4
(3.6, 5.4]  5
(3.6, 5.4]  4
(3.6, 5.4]  5

In [5]: df.loc[[10]]
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-5-315006c1f115> in <module>()
----> 1 df.loc[[10]]

/Users/jreback/pandas/pandas/core/indexing.py in __getitem__(self, key)
   1338         else:
   1339             key = com._apply_if_callable(key, self.obj)
-> 1340             return self._getitem_axis(key, axis=0)
   1341 
   1342     def _is_scalar_access(self, key):

/Users/jreback/pandas/pandas/core/indexing.py in _getitem_axis(self, key, axis)
   1538                     raise ValueError('Cannot index with multidimensional key')
   1539 
-> 1540                 return self._getitem_iterable(key, axis=axis)
   1541 
   1542             # nested tuple slicing

dev/pandas/pull/15309/commits/464cff2d04be86753ce72cd0f3d96eb2fad7c227

   1541 
   1542             # nested tuple slicing

/Users/jreback/pandas/pandas/core/indexing.py in _getitem_iterable(self, key, axis)
   1048     def _getitem_iterable(self, key, axis=0):
   1049         if self._should_validate_iterable(axis):
-> 1050             self._has_valid_type(key, axis)
   1051 
   1052         labels = self.obj._get_axis(axis)

/Users/jreback/pandas/pandas/core/indexing.py in _has_valid_type(self, key, axis)
   1428 
   1429                 raise KeyError("None of [%s] are in the [%s]" %
-> 1430                                (key, self.obj._get_axis_name(axis)))
   1431 
   1432             return True

KeyError: 'None of [[10]] are in the [index]'
```

This is suspect, this should be returning -1 for the indexers (rather than raising). So going to fix.
```
In [6]: df.loc[[10, 4]]
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-6-50e470a1fe86> in <module>()
----> 1 df.loc[[10, 4]]

/Users/jreback/pandas/pandas/core/indexing.py in __getitem__(self, key)
   1338         else:
   1339             key = com._apply_if_callable(key, self.obj)
-> 1340             return self._getitem_axis(key, axis=0)
   1341 
   1342     def _is_scalar_access(self, key):

/Users/jreback/pandas/pandas/core/indexing.py in _getitem_axis(self, key, axis)
   1538                     raise ValueError('Cannot index with multidimensional key')
   1539 
-> 1540                 return self._getitem_iterable(key, axis=axis)
   1541 
   1542             # nested tuple slicing

/Users/jreback/pandas/pandas/core/indexing.py in _getitem_iterable(self, key, axis)
   1068             # have the index handle the indexer and possibly return
   1069             # an indexer or raising
-> 1070             indexer = labels._convert_list_indexer(keyarr, kind=self.name)
   1071             if indexer is not None:
   1072                 return self.obj.take(indexer, axis=axis)

/Users/jreback/pandas/pandas/indexes/interval.py in _convert_list_indexer(self, keyarr, kind)
    415         # TODO: handle keyarr if it includes intervals
    416         if (locs == -1).any():
--> 417             raise KeyError("a list-indexer must only include "
    418                            "existing intervals")
    419 

KeyError: 'a list-indexer must only include existing intervals'
```

@shoyer 

this is from the original issue

> IntervalIndex should play nicely when used as the levels for Categorical variable (#7217), but it is not the same as a CategoricalIndex (#7629). For example, a IntervalIndex should not allow for redundant values. To represent redundant or non-continuous intervals, you would need to make in a Categorical or CategoricalIndex which uses a IntervalIndex for the levels. Calling df.reset_index() on an DataFrame with an IntervalIndex would create a new Categorical column.

why should an ``IntervalIndex`` NOT allow redundant values? (and instead be a ``CategoricalIndex`` with level of an ``IntervalIndex``). Is there a reason for this constraint? (just want to understand your rationale here).

> why should an IntervalIndex NOT allow redundant values? (and instead be a CategoricalIndex with level of an IntervalIndex). Is there a reason for this constraint? (just want to understand your rationale here).

Yeah, I don't remember why now but this does seem strange.

The only reason why this makes any sense to me is that there are optimizations one can do for look-ups if the IntervalIndex consists of non-overlapping, continuous intervals (you can use binary search instead of the interval tree).
If you don't me asking... if I wanted to use the new `pd.cut` in this PR right now, what would I need to do?  I have:
```
git remote add jreback https://github.com/jreback/pandas.git
git fetch jreback
git checkout remotes/jreback/intervalindex
git checkout -b intervalindex
```
The code now has the changes made in this PR,  but `import pandas` raises an Error except for if I switched back to the `master` branch.  Do I need to somehow reinstall pandas off the `intervalindex` branch?  
@qAp This PR has changes in the c code, so you need to rebuild pandas. So after the commands you used above to checkout the correct branch, you need to do `python setup.py build_ext -i`. 
See the contributing docs for more information: http://pandas.pydata.org/pandas-docs/stable/contributing.html
@qAp happy to have you test this out.....pls report any issues here.
@jreback Any news on this? 
@zfrenchee I have to make a few more internal changes to make some things consistent.

can I ask your usecases? / examples (e.g. so can have additional tests mainly.....)
@jreback We have two sets of genomic regions e.g. `regions 1: (base 10-15, base 22-26, etc...)` and `regions 2: (base 17-19, base 25-31)` and we'll want to report back any overlaps between the two regions. e.g. `overlaps: [(22-26, 25-31), (...),...]`. Each set of regions might be ~10k-100k large and we want to get this list of overlaps as speedily as possible. Right now I'm using https://github.com/chaimleib/intervaltree which was extremely convenient but doesn't optimize for speed. 
@zfrenchee cursory look at that seems to be a compat API (though we might have some missing things, and indexing is using standard pandas idioms). Can you show a sample of what you are doing (in a dataframe itself would be ideal).

cc @shoyer ?

@jreback I'm not sure I understand. I think the issue is that I don't know what a compat API is. 

I have two dataframes, each with "starts" and "ends" columns. I want to compute an overlap between these two dataframes which represent sets of intervals. In my case, each dataframe never overlaps itself, but we expect a fair bit of overlap between them.  
@zfrenchee what I mean is show a small sample for each frame and the operation you wish to do (and the results). It can be some pseudo code (or actual code if you have). I want to see the kind of operations. Ideally you can show a small (copy-pastable example), and certainly make up number / fields as appropriate.
@jreback sure

```
A = pd.DataFrame([(1, 3), (5, 7)], columns=["start","stop"])
B = pd.DataFrame([(2, 4), (6, 8)], columns=["start","stop"])
C = A.intersect(B)
C 
# => pd.dataframe([(1, 3, 2, 4), (5, 7, 6, 8)], columns=["A_start","A_stop","B_start","B_stop"])
```

Or something thereabouts. 
@zfrenchee ok, going to start back with this tomorrow, so will have a look

how big is each frame that you are looking at?
About 10k-100k rows, in the average case I think. 
ok so here's a way of doing what I *think* you want.

creating a frame, we have the evens and odds which are both intervals. setting the index to evens
```
In [16]: df = pd.DataFrame({'evens': pd.IntervalIndex.from_breaks(np.arange(0, N, 2)), 'odds': pd.IntervalIndex.from_breaks(np.arange(1, N+1, 2)), 'n':np.arange(N//2-1)}).set_index('evens')

In [17]: df
Out[17]: 
                    n            odds
evens                                
(0, 2]              0          (1, 3]
(2, 4]              1          (3, 5]
(4, 6]              2          (5, 7]
(6, 8]              3          (7, 9]
(8, 10]             4         (9, 11]
...               ...             ...
(99988, 99990]  49994  (99989, 99991]
(99990, 99992]  49995  (99991, 99993]
(99992, 99994]  49996  (99993, 99995]
(99994, 99996]  49997  (99995, 99997]
(99996, 99998]  49998  (99997, 99999]

[49999 rows x 2 columns]
```

We have an intervalindex
```
In [18]: df.index
Out[18]: 
IntervalIndex(left=[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 196, 198, ...],
              right=[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 196, 198, 200, ...],
              closed='right',
              name='evens',
              dtype='interval[int64]')
```

Here we are using a super-hacked up version of ``.get_indexer`` that handles this overlap case. Its quite inefficient ATM (because I am doing some internal python looping for a part), though the lookups are using the intervalclass cython that @shoyer wrote, but easy to fix.

The idea here is we are finding the overlaps. (the dupes are wrong, as my lookups are weird here).
```
In [21]: df.loc[df.index.find_intersections(pd.IntervalIndex(df['odds']))]
Out[21]: 
                    n            odds
evens                                
(0, 2]              0          (1, 3]
(0, 2]              0          (1, 3]
(2, 4]              1          (3, 5]
(2, 4]              1          (3, 5]
(4, 6]              2          (5, 7]
...               ...             ...
(49992, 49994]  24996  (49993, 49995]
(49994, 49996]  24997  (49995, 49997]
(49994, 49996]  24997  (49995, 49997]
(49996, 49998]  24998  (49997, 49999]
(49996, 49998]  24998  (49997, 49999]

[49998 rows x 2 columns]
```

```
In [22]: %timeit df.loc[df.index.find_intersections(pd.IntervalIndex(df['odds']))]
1 loop, best of 3: 648 ms per loop
```
@shoyer 

```
    def find_intersections(self, other):
        """
        super-hacky intersection

        other: IntervalIndex
        """
        tuples = list(zip(self._engine.get_indexer(other.left.values),
                          self._engine.get_indexer(other.right.values)))

        # to filter the missing ones
        tuples = [ tup for tup in tuples if tup[0] != -1 and tup[1] != -1]
        return type(self).from_tuples(tuples, closed=self.closed,
                                      name=self.name)

```
@jreback one note is that in my case, I want to allow many-to-many overlaps, so if intervals `a_1` and `a_2` from `A` both overlap with `b_1` and `b_2` from `B`, then as an output I'd like
```
a_1 b_1
a_1 b_2
a_2 b_1
a_2 b_2
```

I've been assuming we need to merge this PR in order to have access to `IntervalIndex`. Is that assumption valid? 
if anyone who is interested would have a look!

I revised this to remove the API change that I had before. now ``pd.cut``, still returns a ``CategoricalIndex`` (as it does in master). The difference is that the categories are now an ``IntervalIndex`` rather than an ``Index`` (of string intervals). The before was that I was actually returning an ``IntervalIndex``.

I also updated the top section.

The reasons for this change are that the conversion between an array of ``Intervals`` and the ``IntervalIndex`` itself is not super cheap (as we don't actually have an ``IntervalBlock`` type).

Indexing is quite logical as you can directly index just as you would with any other type. The semantics here are that a ``Categorical`` index can now defer to its categories to index (which actually is generally useful).

IOW it makes sense to be able to index via ``.loc`` w/o actually having to specify something *in* the categories directly, rather the lookup is defered to the index.

This allows one to select things via an integer/float where it is *included* in the an interval itself, rather than having to a-priori specify the intervals (which you can do as well).

So ``CategoricalIndex`` is really just an efficient holder of the ``Interval`` objects.

From a user point of view these interactions are pretty seemless and you won't really directly have an ``IntervalIndex`` unless you are actually setting it directly from an Interval column. This is almost identical to how we work with a *regular* index today, so I don't see any issues with this.
https://github.com/pandas-dev/pandas/pull/15309/commits/40198b971747c19a5cdd86908f0b37150602b629

```
In [2]: i = pd.IntervalIndex([0, 1], [1, 2])

In [3]: i
Out[3]: 
IntervalIndex(left=[0, 1],
              right=[1, 2],
              closed='right',
              dtype='interval[int64]')

In [4]: 0 in i
Out[4]: False

In [5]: 3 in i
Out[5]: False

In [6]: pd.Interval(0, 1) in i
Out[6]: True

In [7]: pd.Interval(0, 4) in i
Out[7]: True

In [8]: pd.Interval(0, .5) in i
Out[8]: True

In [9]: pd.Interval(-1, .5) in i
Out[9]: True

In [10]: pd.Interval(-5, -2) in i
Out[10]: False

In [11]: i._is_contained_in(4)
Out[11]: False

In [12]: i._is_contained_in(0.5)
Out[12]: True

In [14]: i._is_contained_in(0)
Out[14]: False

In [15]: i._is_contained_in(0.1)
Out[15]: True

In [16]: i._is_contained_in(1)
Out[16]: True

```

I am not completely happy with this as we have the problem of what does an interval that only partially overlaps return?

It 'works' well enough now though (e.g. indexing is now internally using ``_is_contained_in``) which is what you need for key validation.
@cpcloud if you can give this a once-over and show some usecases would be great.
@jreback May largely be out of scope for this PR, but playing around this as an unveven `Period` alternative.  Setup

```
left = pd.DataFrame({'start': pd.to_datetime(['2014-01-01', '2014-01-04']), 
                     'end': pd.to_datetime(['2014-01-04', '2014-01-09']), 
                     'key': [1, 2]})

left.index = pd.IntervalIndex(left['start'], left['end'], closed='left')

right = pd.DataFrame({'date': pd.date_range('2014-01-01', periods=6), 
                      'value': range(6)}).set_index('date')

left
Out[29]: 
                                                  end  key      start
[2014-01-01 00:00:00, 2014-01-04 00:00:00) 2014-01-04    1 2014-01-01
[2014-01-04 00:00:00, 2014-01-09 00:00:00) 2014-01-09    2 2014-01-04

right
Out[30]: 
            value
date             
2014-01-01      0
2014-01-02      1
2014-01-03      2
2014-01-04      3
2014-01-05      4
2014-01-06      5
```

I didn't expect this to work, but also maybe should raise than return this?
```
In [31]: left.join(right)
Out[31]: 
                                                  end  key      start  value
[2014-01-01 00:00:00, 2014-01-04 00:00:00) 2014-01-04    1 2014-01-01    NaN
[2014-01-04 00:00:00, 2014-01-09 00:00:00) 2014-01-09    2 2014-01-04    NaN
```

If I did want to join, is something like this as good as I can do?
```
In [41]: pd.concat([left.loc[right.index, :].reset_index(), right.reset_index()], axis=1)
Out[41]: 
                                        index        end  key      start  \
0  [2014-01-01 00:00:00, 2014-01-04 00:00:00) 2014-01-04    1 2014-01-01   
1  [2014-01-01 00:00:00, 2014-01-04 00:00:00) 2014-01-04    1 2014-01-01   
2  [2014-01-01 00:00:00, 2014-01-04 00:00:00) 2014-01-04    1 2014-01-01   
3  [2014-01-04 00:00:00, 2014-01-09 00:00:00) 2014-01-09    2 2014-01-04   
4  [2014-01-04 00:00:00, 2014-01-09 00:00:00) 2014-01-09    2 2014-01-04   
5  [2014-01-04 00:00:00, 2014-01-09 00:00:00) 2014-01-09    2 2014-01-04   

        date  value  
0 2014-01-01      0  
1 2014-01-02      1  
2 2014-01-03      2  
3 2014-01-04      3  
4 2014-01-05      4  
5 2014-01-06      5  
```