BUG: Add uint64 support to IntervalTree
State: closed

- [X] xref https://github.com/pandas-dev/pandas/issues/20636#issuecomment-380276144
- [X] tests added / passed
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [X] whatsnew entry

Note that this doesn't fully close the linked issue; this just resolves the `uint64` case, which was relatively straightforward.  The datetimelike case still needs to be resolved, but seems distinct enough for a different PR.

Labels:
name: Bug
name: Dtype Conversions
description: Unexpected or buggy dtype conversions
name: Interval
description: Interval data type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20651?src=pr&el=h1) Report
> Merging [#20651](https://codecov.io/gh/pandas-dev/pandas/pull/20651?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/4e6aa1c012d91d663edcfd13658a35f88a49da30?src=pr&el=desc) will **decrease** coverage by `0.02%`.
> The diff coverage is `n/a`.

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

```diff
@@            Coverage Diff             @@
##           master   #20651      +/-   ##
==========================================
- Coverage   91.83%   91.81%   -0.03%     
==========================================
  Files         153      153              
  Lines       49269    49270       +1     
==========================================
- Hits        45247    45238       -9     
- Misses       4022     4032      +10
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.2% <ø> (-0.03%)` | :arrow_down: |
| #single | `41.9% <ø> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/20651?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/plotting/\_converter.py](https://codecov.io/gh/pandas-dev/pandas/pull/20651/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL19jb252ZXJ0ZXIucHk=) | `65.07% <0%> (-1.74%)` | :arrow_down: |
| [pandas/core/indexes/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/20651/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZXMucHk=) | `95.73% <0%> (ø)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/20651/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `84.59% <0%> (+0.2%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20651?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/20651?src=pr&el=footer). Last update [4e6aa1c...4e0ec35](https://codecov.io/gh/pandas-dev/pandas/pull/20651?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

thanks @jschendel 
side issue: do we have tests constructing (and raising) non-supported dtypes, e.g. ``int16``. They raise on directly constructing an ``IntervalTree``, so should add some tests for this (I believe have tests directly constructing an II)
this is generating lots of build warnings

```
building 'pandas._libs.interval' extension
gcc -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/Users/jreback/miniconda3/envs/pandas/include -arch x86_64 -I/Users/jreback/miniconda3/envs/pandas/include -arch x86_64 -Ipandas/_libs/src/klib -Ipandas/_libs/src -I/Users/jreback/miniconda3/envs/pandas/lib/python3.6/site-packages/numpy/core/include -I/Users/jreback/miniconda3/envs/pandas/include/python3.6m -c pandas/_libs/interval.c -o build/temp.macosx-10.7-x86_64-3.6/pandas/_libs/interval.o -Wno-unused-function
In file included from pandas/_libs/interval.c:525:
In file included from /Users/jreback/miniconda3/envs/pandas/lib/python3.6/site-packages/numpy/core/include/numpy/arrayobject.h:4:
In file included from /Users/jreback/miniconda3/envs/pandas/lib/python3.6/site-packages/numpy/core/include/numpy/ndarrayobject.h:18:
In file included from /Users/jreback/miniconda3/envs/pandas/lib/python3.6/site-packages/numpy/core/include/numpy/ndarraytypes.h:1816:
/Users/jreback/miniconda3/envs/pandas/lib/python3.6/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: "Using deprecated NumPy API, disable it by "          "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-W#warnings]
#warning "Using deprecated NumPy API, disable it by " \
 ^
pandas/_libs/interval.c:13323:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:13580:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:13837:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:14094:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:14351:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:15478:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:15734:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:15990:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:16246:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:16502:33: warning: comparison of integers of different signs: 'Py_ssize_t' (aka 'long') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
  for (__pyx_t_3 = 0; __pyx_t_3 < __pyx_t_2; __pyx_t_3+=1) {
                      ~~~~~~~~~ ^ ~~~~~~~~~
pandas/_libs/interval.c:67694:139: warning: comparison of integers of different signs: '__pyx_t_5numpy_int32_t' (aka 'int') and '__pyx_t_5numpy_uint64_t' (aka 'unsigned long') [-Wsign-compare]
      __pyx_t_8 = ((*((__pyx_t_5numpy_int32_t *) ( /* dim=0 */ (__pyx_v_self->left.data + __pyx_t_11 * __pyx_v_self->left.strides[0]) ))) <= __pyx_v_point);
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ^  ~~~~~~~~~~~~~
pandas/_libs/interval.c:67697:36: warning: comparison of integers of different signs: '__pyx_t_5numpy_uint64_t' (aka 'unsigned long') and '__pyx_t_5numpy_int32_t' (aka 'int') [-Wsign-compare]
        __pyx_t_8 = (__pyx_v_point < (*((__pyx_t_5numpy_int32_t *) ( /* dim=0 */ (__pyx_v_self->right.data + __pyx_t_12 * __pyx_v_self->right.strides[0]) ))));
                     ~~~~~~~~~~~~~ ^  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pandas/_libs/interval.c:67740:34: warning: comparison of integers of different signs: '__pyx_t_5numpy_uint64_t' (aka 'unsigned long') and '__pyx_t_5numpy_int32_t' (aka 'int') [-Wsign-compare]
    __pyx_t_13 = ((__pyx_v_point < __pyx_v_self->pivot) != 0);
                   ~~~~~~~~~~~~~ ^ ~~~~~~~~~~~~~~~~~~~
pandas/_libs/interval.c:67788:138: warning: comparison of integers of different signs: '__pyx_t_5numpy_int32_t' (aka 'int') and '__pyx_t_5numpy_uint64_t' (aka 'unsigned long') [-Wsign-compare]
        __pyx_t_13 = ((!(((*((__pyx_t_5numpy_int32_t *) ( /* dim=0 */ (__pyx_v_values.data + __pyx_t_17 * __pyx_v_values.strides[0]) ))) <= __pyx_v_point) != 0)) != 0);
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  ^  ~~~~~~~~~~~~~
```
Looking into the warnings. The warnings I get are similar but slightly different,; guessing it's a compiler thing.  I have a fix that addresses the warnings, but it causes an `OverflowError` instead of a `KeyError` when querying negative values on a `uint64` dtype `IntervalTree`.  Trying to find a way to gracefully handle it.

> do we have tests constructing (and raising) non-supported dtypes, e.g. int16. They raise on directly constructing an IntervalTree, so should add some tests for this

Also added a test for this on my warnings fix branch, and made some minor changes to yield a more informative error.