IntervalIndex get_indexer may return -1 for values that are in the index

[nateyoder]

Code Sample, a copy-pastable example if possible

idx = pd.IntervalIndex.from_breaks(pd.np.arange(10))
target = pd.Interval(0, 1, closed='right')
# Indexer works in this case if index was sorted
a = idx.get_indexer([target])
assert a[0] == 0

idx = pd.Index(pd.np.roll(idx.values, 1))
a = idx.get_indexer([target])
assert tmp == idx[1]
# Even though the second value in the index is equal to the target `get_indexer` returns -1
a[0]
>>> -1

Problem description

I expected get_indexer on IntervalIndex is expected to return the index of matching values. However it does not always seem to do so.

Expected Output

In the above example I expected an output of a = np.array([1])

Output of pd.show_versions()

INSTALLED VERSIONS

commit: 4111382
python: 3.5.2.final.0
python-bits: 64
OS: Darwin
OS-release: 16.5.0
machine: x86_64
processor: i386
byteorder: little
LC_ALL: None
LANG: en_US.UTF-8
LOCALE: en_US.UTF-8

pandas: 0.21.0.dev+67.g4111382
pytest: 3.0.7
pip: 8.1.2
setuptools: 35.0.2
Cython: 0.25.2
numpy: 1.12.1
scipy: 0.19.0
xarray: None
IPython: 5.1.0
sphinx: 1.4.8
patsy: None
dateutil: 2.6.0
pytz: 2017.2
blosc: None
bottleneck: 1.2.0
tables: 3.3.0
numexpr: 2.6.2
feather: None
matplotlib: 2.0.0
openpyxl: None
xlrd: None
xlwt: None
xlsxwriter: None
lxml: None
bs4: None
html5lib: None
sqlalchemy: 1.1.2
pymysql: 0.7.9.None
psycopg2: None
jinja2: 2.8
s3fs: None
pandas_gbq: None
pandas_datareader: None

[jreback]

this should raise. We cannot efficiently handle non-monotonic indexes, though I think we actually try to do this.

@shoyer @buyology

[jreback]

@nateyoder welcome to have you take a look.

[nateyoder]

@jreback sounds like your desired behavior for now is raising? If that is the case I can try to take a look.

[shoyer]

Agreed, get_indexer should always do an exact lookup here.

[jreback]

actually .get_indexer() doesn't raise, so this is correct (meaning it was not found).

so this is correct (though certainly may not be handled correctly elsewhere), where are you seeing this (aside from the top-example)?

In [1]: Index([1, 2, 3]).get_indexer([10])
Out[1]: array([-1])

[nateyoder]

The issue with this get_indexer call for IntervalIndex is that it returns -1 even though the interval IS in the index (as shown with the second assert in my example). If non-monotonic IntervalIndex objects are not handled in the code it seems to me like creating one should raise?

[jreback]

@nateyoder sorry, you are right. this should return the right value, but get_indexer() never raises by definition. (the -1 indicate missing values)

[shoyer]

Sometimes we raise a different error (e.g., pandas.errors.UnsortedIndexError) but in general we do try to avoid this.

…

On Mon, May 22, 2017 at 10:02 AM Jeff Reback ***@***.***> wrote: @nateyoder <https://github.com/nateyoder> sorry, you are right. this should return the right value, but get_indexer() never raises by definition. (the -1 indicate missing values) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#16410 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABKS1pBOqn-w0YSwIGIHRqRjHgxgmAZHks5r8b-egaJpZM4Nhwpx> .

[makbigc]

The bug is still here for non-monotonic index.

In [1]: import pandas as pd                                                     

In [2]: idx1 = pd.IntervalIndex.from_tuples([(2,3), (4,5), (0,1)])              

In [3]: idx2 = pd.IntervalIndex.from_tuples([(0,1), (2,3), (6,7), (8,9)])       

In [4]: idx1.get_indexer(idx2)                                                  
Out[4]: array([-1, -1, -1, -1])
# The expected output is array([2, 0, -1, -1])

In [5]: idx1[1:]                                                                
Out[5]: 
IntervalIndex([(4, 5], (0, 1]],
              closed='right',
              dtype='interval[int64]')

In [6]: idx1.get_indexer(idx1[1:])                                              
Out[6]: array([ 0,  1, -1])
# The expected output is array([1, 2])

I guess this bug is due to that IntervalTree.get_indexer only returns the correct values for its right.
In my first example,

pandas/pandas/core/indexes/interval.py

Lines 850 to 851 in a1fee91

	lindexer = self._engine.get_indexer(left.values)
	rindexer = self._engine.get_indexer(right.values)

rindexer gets array([2, 0, -1, -1]), but lindexer gets array([-1, -1, -1, -1]).

Digging deeper into the IntervalTree.

pandas/pandas/_libs/intervaltree.pxi.in

Line 358 in a1fee91

if self.left[i] {{cmp_left}} point {{cmp_right}} self.right[i]:

Becuase IntervalIndex is right closed by default, {{cmp_left}} is <. left.values, which is point in the above code, is just excluded by the < operator. While right.values is included by <= operator.

[mroeschke]

The original issue isn't fully copy pasteable, but @makbigc's examples look to work on master. Could use a test.

In [30]: In [2]: idx1 = pd.IntervalIndex.from_tuples([(2,3), (4,5), (0,1)])
    ...:
    ...: In [3]: idx2 = pd.IntervalIndex.from_tuples([(0,1), (2,3), (6,7), (8,9)])
    ...:
    ...: In [4]: idx1.get_indexer(idx2)
Out[30]: array([ 2,  0, -1, -1])

In [31]: In [6]: idx1.get_indexer(idx1[1:])
Out[31]: array([1, 2])

In [32]: pd.__version__
Out[32]: '0.26.0.dev0+627.gef77b5700'