WIP/API/ENH: IntervalIndex
closes #7640 
closes #8625

This is a work in progress, but it's far enough along that I'd love to get
some feedback.

TODOs (more called out in the code):
- [ ] documentation
- [x] docstrings
- [x] implement an IntervalTree under the hood to handle index methods
- [x] index methods handle point queries properly:
  - [x] `get_loc`
  - [x] `get_indexer`
  - [x] `slice_locs`
- [x] index methods handle interval queries properly
  - [x] `get_loc`
  - [x] `get_indexer` (for non-overlapping monotonic indexes)
- [x] comparison operations (should be lexicographic)
- [x] ensure `is_monotonic` always works (also lexicographic)
- [x] ensure `order` works
- [x] cast arrays of intervals when input to `pd.Index`
- [x] cythonize the bottlenecks:
  - [x] `values`
  - [x] `from_intervals`?
  - [x] `Interval`?
  - [ ] `from_tuples`?
- [ ] `Categorical`/`cut`
- [ ] nice to haves (not essential for MVP)
  - [ ] `get_indexer` in full generality (for randomly ordered indexes)
  - [ ] support for arithmetic operations
  - [ ] `MultiIndex` -- should at least give a sane error messages
  - [ ] serialization (HDF5) -- should at least raise `NotImplementedError`
  - [ ] consider creating `interval_range` -- like `period_range`
  - [ ] add `to_interval` for casting strings (e.g., `to_interval('(0, 1]')`)
  - [ ] release the GIL in IntervalTree queries
- [ ] loads more tests:
  - [x] `Series.loc.__getitem__`
  - [ ] `Series.loc.__setitem__`
  - [ ] indexing a dataframe
  - [ ] groupby
  - [x] reset_index
  - [x] add tests in test_index for the subcommon API

CC @jreback @cpcloud @immerrr

so one of the big use cases here is as the index in a series coming out of cut/qcut
eg it returns an IntervalIndex
 so the whole notion of boxing - eg having an underlying impl then getting s boxed scalar type out is inherent in what u r doing

you get this for free - see here 
https://github.com/pydata/pandas/blob/master/pandas/tseries/base.py

though prob need to strip out the box/iter stuff (and maybe some other stuff - contains)

can put in another mixin that u can use (it could live in index.py maybe BoxMixIn)
and as long as update tseries/base.py should be good to go
 @shoyer 

looks really good!

Instead of cythonizing `Interval`, you can prob get away with just creating a fastpath constructor lke this: https://github.com/pydata/pandas/blob/master/pandas/tseries/period.py#L68

You are using an `_engine` of `ObjectEngine` (the default) in `IntervalIndex`. You might need to create a `IntervalIndexEngine` to handle the indexing (but not necessary for first version).
 @shoyer sort of confused why `_data` materialis Intervals at ALL.

you don't need it for indexing (e.g you have left/right for that purpose).

ONLY on boxing do you need to do this (e.g. you need to implement the `format` methods I think).
e.g. so displaying a frame with this as an index would materialze only a small subset of the values

Think of this like `DatetimeIndex`. You have an underlying imple (e.g. an array of i8). Where you do virtually all computations. ONLY when asked (e.g. could be a selection or iteration), do you actually materialize the values. (which can be expensive I agree).
 @jreback Yes, not including _data at all and skipping all the standard index machinery was my original idea.

But, there are actually a few advantages to keeping that representation around (the object index):
1. It gives us default implementations for miscellaneous index methods like is_unique (not entirely sure this is worth the trouble, though).
2. It gives us the possibility of doing fast O(1) lookups for `Interval` objects in the index. This could make a significant difference for operations like reindexing/`get_indexer` (although, again, `np.searchsorted` is already quite fast).
 I disagree entirely. The whole point is that you don't need the object representation. You already have the impl in `_left/_right` which is very fast to lookup. 

```
In [18]: def f1():
   ....:     i = pd.IntervalIndex.from_breaks(np.arange(1000))
   ....:     iv = pd.Interval(50,51)
   ....:     return i.get_loc(iv)
   ....: 

In [19]: %timeit f1()
100 loops, best of 3: 6.19 ms per loop

In [20]: def f2():
   ....:     i = pd.IntervalIndex.from_breaks(np.arange(1000))
   ....:     iv = pd.Interval(50,51)
   ....:     return i._left.get_loc(iv.left), i._right.get_loc(iv.right)
   ....: 

In [21]: f2()
Out[21]: (50, 50)

In [22]: f1()    
Out[22]: 50

In [23]: %timeit f2()
10000 loops, best of 3: 72.3 us per loop
```

caveat:

what I did is naive. And not sure of the exact lookup semantics for IN an interval, but easy enough to maybe keep a 'freq' for left/right, (or can just do right-left), e.g. to find the 'natural' interval of the Index. Then you can take a number and find the left and right of it (WITHOUT using searchsorted, but indexing which is O(1)) then do a simple comparison.

you ONLY need to use search sorted I think if their is no freq. E.g. you have a bunch of non-regular intervals (but since you have left and right you can prob do a pretty good job, e.g. if you find where it is on the lft, then you know about where it is on the right). You may need a custom searchsorted type of this 'irregular' intervals.
 `unique` is easy too, something like

(this is w/o boxing)

```
In [26]: %timeit Index(zip(i._left,i._right)).unique()
1000 loops, best of 3: 1.27 ms per loop
```

With Boxing

```
In [32]: %timeit [ pd.Interval(*x) for x in Index(zip(i._left,i._right)).unique() ]
100 loops, best of 3: 2.18 ms per loop
```

remember these still bee the original construction + ._data 

and keeping it around has memory overhead (much more than 2x the original)
 @jreback OK, I will give this a try without using `_data` at all. Using a natural interval "frequency" is indeed an appealing idea for facilitating O(1) lookups (this is similar to the "grid index" I discussed in the original proposal).
 haha, ok.

so the freq I am talking about is between 2 Intervals and not the distance in a single interval (which is a value like the left/right). Hmm do they have to be the same? I guess for a regular interval series they do.

```
In [40]: x = pd.IntervalIndex.from_breaks(pd.timedelta_range('1s',periods=1000,freq='s'))

In [41]: pd.Interval(pd.Timedelta('1s'),pd.Timedelta('3s'))
Out[41]: Interval(Timedelta('0 days 00:00:01'), Timedelta('0 days 00:00:03'), closed='right')
```

have a look at tseries.frequency.FrequencyInferer, though it this case its almost trivial

e.g. `(i._right-i.left).unique()` if you have 1 value only then that s the freq

```
In [44]: (x._right-x._left).unique()[0]
Out[44]: Timedelta('0 days 00:00:01')
```

BTW, my point of this example is to have tests for the possible types of interval operands:

integer, float, Timedeltas come to mind, though I suppose Timestamps/Periods make sense too.

hmm, then their is:

`Interval('a','b')`

Which i suppose 'works', but not sure how searching this would work. Maybe only allow certain types (and the left/right of an Interval should be the same).

I think CategoricalIndex is the way to the above.
 I think you do need both the space between intervals and the distance for single intervals to be at a constant frequency in order to be able to do fast lookups. Everything needs to be able to map to a `Int64Index` under the hood (not unlike `PeriodIndex`).

I may try to get things working first for the general case and then add the optimized `freq` later, though I agree that this is a important as intervals with a constant frequency are extremely common.

Also agreed that we need tests for many types. Strings can't have a well-defined frequency, but I don't much harm in allowing their use.
 yup

though you don't need it to map to `Int64Index` per-se, more like you need to have the Index support certain operations, e.g. `get_loc` and subtraction (which all of the indexes do).

This Index is just a dispatcher really to the combination of the underlying indexes. Much like MultiIndex is a collection of Index objects (that is well-ordered).
 Just do this to subtract the 2 dti's (and not so set difference). bti I would for now not allow tz's in any passed in left/right (may work though)

```
In [8]: rng = date_range('20130101',periods=5)

In [9]: rng2 = rng+pd.to_timedelta(np.arange(5),unit='s')

In [10]: rng
Out[10]: 
<class 'pandas.tseries.index.DatetimeIndex'>
[2013-01-01, ..., 2013-01-05]
Length: 5, Freq: D, Timezone: None

In [11]: rng2
Out[11]: 
<class 'pandas.tseries.index.DatetimeIndex'>
[2013-01-01 00:00:00, ..., 2013-01-05 00:00:04]
Length: 5, Freq: 86401S, Timezone: None

In [12]: pd.TimedeltaIndex(rng2.values-rng.values)
Out[12]: 
<class 'pandas.tseries.tdi.TimedeltaIndex'>
['00:00:00', ..., '00:00:04']
Length: 5, Freq: None
```
 @jreback you're not worried about NaT screwing things up? I suppose we might as well insist that left and right cannot have missing values, anyways.
 Actually, turns out subtracting  `NaT` is _not_ entirely broken in numpy:

```
# wtf
In [9]: pd.to_datetime(['NaT']).values - pd.to_datetime(['2000-01-01']).values
Out[9]: array([-9223372036854775808], dtype='timedelta64[ns]')

# but put it in an index, and it's still NaT!
In [10]: pd.Index(pd.to_datetime(['NaT']).values - pd.to_datetime(['2000-01-01']).values)
Out[10]:
<class 'pandas.tseries.tdi.TimedeltaIndex'>
[NaT]
Length: 1, Freq: None
```

I am shocked!
 hahha

their is a simple routine to do this
maybe I need a `dti.sub(dti2)`

though let me see about making this not do set difference and do subtraction on - it does make more sense

maybe

`dti - dti2.values` works now 
 OK, tests finally pass (with a few commented out) but there is still plenty more work to do. The basic indexing functionality works, at least in a series object.

The fact that array indexing with `.loc` does reindexing makes things a little awkward with `IntervalIndex` -- it means that doing array indexing will give you back a result with a different type of index:

```
In [10]: s = pd.Series(range(4), pd.IntervalIndex.from_breaks(range(5)))

In [11]: s
Out[11]:
(0, 1]    0
(1, 2]    1
(2, 3]    2
(3, 4]    3
dtype: int64

In [12]: s.loc[[0.5, 1.5, 2.5, 3.5]]
Out[12]:
0.5    0
1.5    1
2.5    2
3.5    3
dtype: int64
```

I expect users will find this surprising, but I don't see any easy way around it short of making `.loc` no longer do reindexing (which I wouldn't be opposed to in theory, but for which the ship has long sailed).
 https://github.com/shoyer/pandas/commit/e881cb55f2348b0faeab86c5ce71512ec6f15202

You just need to override the methods (and implement in IntervalIndex), e.g. the `_convert_*` ones

These are dispatched by `core/indexing` 

You basically do whatever you want based on the key type (e.g. scalar, list, mixed list, etc.) and then if you return not-None it will do a `.take` on what you have returned. So it unambiguous and dependent on the index type. (e.g this is how `Float64Index` and `Int64Index` can interpret floats differently (well `Int64Index`` can warn on them)
 @jreback Thanks for the example and PR to my fork! But wow, `_convert_list_indexer_for_mixed` is quite a kludge. I see that you introduced it for a bug fix (#6548; reminds me that I need to test `__setitem__`). I could certainly (ab)use that method, but is that really a good idea? IMO the existing behavior is more consistent with the reindexing nature of `.loc`.
 @shoyer Prob better to simply define `IntervalIndex.reindex` where you can directly deal with the passed values. You never want to actually return a different type of index when you are doing an indexing operation (at least I can't think of any off hand).

When you do `s.loc[[0.5,1.5]]` (on a Series with an IntervalIndex) what are you trying to get? e.g. what is natural/logical here?
 @jreback Generally I do agree. But I think it is even worse for the type of the index returned from `.loc` to depend on whether a requested value is found.

To continue my example, consider also what should happen with `s.loc[[0.5, 4.5]]`. 4.5 is not found in the index, so we will need to insert a new value. This leaves us with a few options:
1. always return a series with a `Float64Index`
2. always return a series with an `IntervalIndex` -- raise an exception instead of doing reindexing.
3. return a series with an object index with mixed intervals / floats, depending on whether values are found
4. return an `IntervalIndex`, or, if that is not possible, fall back to returning a float index.

Starting from scratch, 2 would be my preferred option, but it's quite inconsistent with current (re)indexing behavior. 3 is terrible from a usability perspective, so we can reject it. I think you are suggesting 4, but that is also pretty bad, because it means user code needs a check for the type of the returned object (users won't bother until necessary, so they'll end up with bugs). This leaves option 1.
 Maybe a use-case example would help. By the way `MultiIndex` DOES currently raise when you ask for a value that doesn't exist. So I wouldn't think its a problem to raise a `KeyError`. Or you could have a concept of a 'point' Interval (that is that value), but not sure if that makes sense. 

(this is from 0.15.0 whatsnew, breaking changes section).

```
In [89]: s = Series(np.arange(3,dtype='int64'),
   ....:            index=MultiIndex.from_product([['A'],['foo','bar','baz']],
   ....:                                          names=['one','two'])
   ....:           ).sortlevel()
   ....: 

In [90]: s
Out[90]: 
one  two
A    bar    1
     baz    2
     foo    0
dtype: int64

In [91]: try:
   ....:    s.loc[['D']]
   ....: except KeyError as e:
   ....:    print("KeyError: " + str(e))
   ....: 
KeyError: 'cannot index a multi-index axis with these keys'
```

IMHO the point of different index types is to have DIFFERENT behavior for certain use-cases (which make senses). E.g. Datetimetindex can do string lookup at partial frequencies for example. Or FloatIndex always doing slice like lookups. It makes sense. We want perfect consistency but not gonna happen :)

So I would err on the side of what makes sense (2) is just fine. The users have to be able to handle a `KeyError` when looking up in your index if the index type doesn't support it. Anything else is just too kludgy.
 @jreback Interesting that MultiIndex does not support looking up missing values with `.loc`. I think I can get behind this for IntervalIndex, too.

It would be nice to figure out how to do that in a way that does not add more special cases to `pandas.core.indexing`, though. Ideally, adding a new index type to pandas _should not_ require any indexing fixes (but obviously some scenarios are hard to anticipate).

Maybe a new method like `reindex_safe` that only succeeds if the type of the index can be preserved? I suppose index types are not so important with `Index`/`Int64Index`/`Float64Index` since they have basically the same API but `IntervalIndex` is pretty different.

Point intervals do make sense, but only if `closed='both'`.
 yep, their is some _special case_ support already in the indexing code (mostly I have tried to move it out the actual index classes, but some does remain esp for `MultiIndex`). So its not the `reindex` operation that 'fails' here, but before, e.g. really `get_loc` raises (or returns -1) ,then THAT signals an error.

Worth having a `Point()` sub-class of `Interval`? 
 > Worth having a Point() sub-class of Interval?

I don't think so? Interval and IntervalIndex already need to support duck typed "points" aka scalar values. I don't think adding explicit points would simplify anything.
 Spent some time today playing around with Cython extension types. The syntax is really not bad and these things are very fast! Initialization and comparison operations for my Cython `Interval` are roughly 5-10x faster than the Python version, so I think the trouble will be worth it.
 @shoyer need to have a number of test cases for sorting/ordering, as its a primary usecase (like Categoricals are), see some of the linked issues.

thxs.
 Yep, totally agreed. This has been on my back burner recently but I'll get back to it soon.

On Fri, Nov 21, 2014 at 6:45 AM, jreback notifications@github.com wrote:

> @shoyer need to have a number of test cases for sorting/ordering, as its a primary usecase (like Categoricals are), see some of the linked issues.
> 
> ## thxs.
> 
> Reply to this email directly or view it on GitHub:
> https://github.com/pydata/pandas/pull/8707#issuecomment-63978901
 @shoyer gr8!

fyi, will get a cameo at my on on sunday at PyDataNYC:http://nbviewer.ipython.org/github/jreback/pydata2014-pandas/blob/master/notebooks/Intervals.ipynb
 I guess I'm committed then! :)

On Fri, Nov 21, 2014 at 9:07 AM, jreback notifications@github.com wrote:

> @shoyer gr8!
> 
> ## fyi, will get a cameo at my on on sunday at PyDataNYC:http://nbviewer.ipython.org/github/jreback/pydata2014-pandas/blob/master/notebooks/Intervals.ipynb
> 
> Reply to this email directly or view it on GitHub:
> https://github.com/pydata/pandas/pull/8707#issuecomment-64003327
 Hi @shoyer! I built something similar to this earlier this year, and I heard about your IntervalIndex implementation from @jreback's PyData talk. I reviewed your code and played around with it for a bit and I think it's very promising! My implementation is limited to datetime intervals (tz-naive and tz-aware), but it has well-tested outer join, intersection, and union operations between IntervalIndex objects containing overlapping Intervals. In the coming weeks I'd like to contribute the features and tests I already have and ultimately adopt your implementation once it's merged. Would it be okay for me to submit PRs to your fork as I work through this?

Best,
Sean
