ENH/API: ExtensionArray.factorize
Adds factorize to the interface for ExtensionArray, with a default
implementation.

This is a stepping stone to groupby.

Categorical already has a custom implementation.

Decimal reuses the default.

JSON can't use the default since an array of dictionaries isn't hashable, so we use a custom implementation.
Marking this as a WIP for now. For JSONArray, the `value_counts` test is failing. I'd like to see if we can reuse `factorize` in `value_counts`. In principal, a counting the labels and doing a `uniques.take` on the index of the counts should work. The failures are caused by a "bug" in `is_extension_array_dtype`. https://github.com/pandas-dev/pandas/pull/20363 This should pass now. # [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20361?src=pr&el=h1) Report
> Merging [#20361](https://codecov.io/gh/pandas-dev/pandas/pull/20361?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/1b1b99b3ffa1080dc86f9074ce0e78e0fc92dd38?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `96.55%`.

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

```diff
@@            Coverage Diff             @@
##           master   #20361      +/-   ##
==========================================
- Coverage   91.82%   91.82%   -0.01%     
==========================================
  Files         152      152              
  Lines       49232    49249      +17     
==========================================
+ Hits        45209    45223      +14     
- Misses       4023     4026       +3
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.21% <96.55%> (-0.01%)` | :arrow_down: |
| #single | `41.89% <62.06%> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/20361?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `96.19% <100%> (-0.01%)` | :arrow_down: |
| [pandas/core/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYmFzZS5weQ==) | `96.8% <100%> (+0.01%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.36% <100%> (+0.04%)` | :arrow_up: |
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `84.14% <90%> (+0.81%)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `84.52% <0%> (-0.21%)` | :arrow_down: |
| [pandas/core/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/20361/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ2VuZXJpYy5weQ==) | `95.85% <0%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/20361?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/20361?src=pr&el=footer). Last update [1b1b99b...c06da3a](https://codecov.io/gh/pandas-dev/pandas/pull/20361?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
 Sorry about the tangentially related changes refactoring the docstring. I can revert if needed, but I don't think it complicates review too much since the only non-doc change to `algos.py` is replacing an `is_categorical` with an `is_extension_array_dtype`.

Tracking down a py-2 failure now. Here's the new docstring for pandas.factorize

![fireshot capture 005 - pandas factorize pandas 0 23 0 dev0_ - file____users_taugspurger_sandbox_](https://user-images.githubusercontent.com/1312546/37541452-ad85b388-2928-11e8-8b71-e300ff9544af.png)
 hmm, ``order`` is still there I thought we removed that? (or maybe we just deprecated it, can you add back as a deprecated parm)?

also, as a public interface, may not really need ``size_hint`` (as now have ``_factorize_array`` which can be an internal interface, but this is small potatoes). maybe link to ``pd.unique`` as well > can you add back as a deprecated parm

yeah, lost that in the shuffle.

> also, as a public interface, may not really need size_hint

Agreed.

> maybe link to pd.unique as well

👍  needs a rebase Do we want to have `ExtensionArray.factorize` use the shared docstring as well? There's an import order issue, I've tried to keep `arrays/base.py` from importing much from pandas (just `AbstractMethodError` so far. If we do a shared doc I would have to move the docstring to a file on it's own, and then import it from `algorithms.py`, `arrays/base.py`, `core/base.py` and `categorical.py`.

I also haven't really thought through if that would break anything for EA implementers.  Ugh I mixed up my branches and merged https://github.com/pandas-dev/pandas/pull/19957 into here... Fixing now.

OK hopefully fixed. this looks fine. I am still concerned about the API expansion for implementors here, IOW you have both ``_values_for_factorize`` and now ``_from_factorize``. > I dislike how this opens up the internals of pandas' factorization algorithms to the public more. Is it publicly documented anywhere that iNaT is the minimum integer? How would an EA author know to do something like what we do for Categorical (and PeriodArray when we get there)?

But is it needed that the extension author specifies this value? 
Because what are the options? If the array has integer-like dtype, it is iNaT, otherwise it is np.nan ? 
(if that is the case, I think we could deduce that?)


In general, I am wondering if we couldn't make this simpler. If we could somehow extend `factorize` to specify a mask or a na_value, then the `factorize` method on EA could be something like:

```
def factorize(self, na_sentinel=-1):
    mask = self.isna()
    values = ... # this is the part to fill in by the extension array author (equivalent _values_for_factorize)
    labels, uniques = pd.factorize(values, na_sentinel=na_sentinel, mask=mask)
    uniques = ... # coerce back to extension array (_from_factorized)
    return labels, uniques
```

This is of course *very* similar to the current `factorize` implementation, but with the difference that it does not use internal APIs. And actually, overriding this does not take more lines of code than overriding both `_values_for_factorize` and `_from_factorized`. So I am not fully sure of the advantage of providing both ways to do it.
 > So I am not fully sure of the advantage of providing both ways to do it.

"both" being

1. `EA.factorize`
2. `EA._values_for_factorize`, and `EA._from_factorized`

correct?

Let me see if I can make `mask` as an argument to `factorize` work. That would indeed be cleaner. > "both" being
>
>   EA.factorize
>   EA._values_for_factorize, and EA._from_factorized

Yes. Looking at the diff now, it seems to me that overwriting `EA._values_for_factorize` and `EA._from_factorized` will actually need as much as custom code as just overwriting `EA.factorize`. So then the argument of providing `_values_for_factorize` to reduce duplication of the actual `factorize` implementation (like we had for `argsort`) does not fully hold in this case (assuming that we can use the public `pd.factorize` instead of `_factorize_arrays`).

> Let me see if I can make mask as an argument to factorize work. That would indeed be cleaner.

Then of course we need to be OK with exposing this in the public `factorize` API. But from an extension author point of view this seems rather clean. 
An alternative would be to specify a `na_value` and then calculate the mask, but I am not sure if that has any advantage over a mask.

@jreback what are your thoughts on such a `mask` keyword for `pd.factorize` I'm having some trouble making the `mask` approach work. It seems like pandas' factorization methods do the right thing for some missing values, like `Decimal(NaN)`.


```python
In [2]: from decimal import Decimal

In [3]: pd.factorize([Decimal('0.0'), Decimal('NaN'), Decimal('0.0')])
Out[3]: (array([ 0, -1,  0]), array([Decimal('0.0')], dtype=object))
```

So in that situation we would have to choose to ignore the mask argument (side-note, `pd.isna` does not consider `Decimal('NaN')` to be NA, so detecting this seems fragile). But for those object arrays, we can always use `np.nan` or `None` I think if a mask is specified? That will always work, regardless of whether the actual NA value is recognized by `factorize` ? > But for those object arrays, we can always use np.nan or None I think if a mask is specified? 

So you think modify `values[mask] = np.nan`? I think we assumed different meanings for `mask`. I was thinking of it as "factorize anything, and fixup the missing values later." Your were thinking of it as "fixup missing values before factorization"?

But with my way of interpreting `mask` there could be a conflict between what `pd.factorize` considers missing, and what `mask` says is missing.

FTR, here's my change.

```python
def _refactorize(values, labels, uniques, na_sentinel, mask=None):
    """Fixup missing value handling according to a mask.

    This modifies labels and uniques inplace.

    Parameters
    ----------
    values : ndarray
    labels : ndarray
        Integer labels. Missing values may be improperly coded as
        values and not `na_sentinel` going in.
    uniques : ndarray
        Unique set of `values`. Missing values may be improperly
        included in `uniques`, and will be removed.
    na_sentinel : int
        The value to use for marking missing values in `labels`.
    mask : ndarray, optional
        Boolean mask. If specified, this will be used to find the missing
        value sentinel from `values`.
    """
    from pandas import isna

    if mask is not None and mask.any():
        # fixup
        idx = mask.argmax()
        na_code = labels[idx]
        # fixup labels
        labels[labels == na_code] = na_sentinel
        labels[labels > na_code] -= 1

        # fixup uniques
        na_value = values[idx]
        uniques_mask = np.ones_like(uniques, dtype='bool')
        uniques_mask[uniques == na_value] = False
        uniques = uniques[uniques_mask]

    return labels, uniques
``` Ah, yes, I was thinking of the "change `values` before passing to `factorize`". 
The problem with that is of course that we then should take a copy of `values`, which might be an unnecessary copy in case the `values` were constructed specifically for `factorize` Here are the cases I see. I put quotes around the ExtensionArray's definition of missing, which may differ from pandas'.

1. float/object values with "NA" values as NA (Decimal)
2. float/object values with "NA" values as something else (IPArray)
3. integer values with "NA" values as iNaT (DatetimeTZ)
4. integer values with "NA" values as something else (Categorical)

You could add a 5/6 for our uint64 hashtable. I don't think that changes anything.

So for cases where the NA values align (1, 3), things will just work, no `mask` required.

For cases where they don't align (2, 4), we'll need to either modify the values going into the hashtable, so that `values[mask] = pandas_na_for_hashtable`, or modify that labels / uniques coming out.

Detecting which case where in should be possible. Will try that now... Though it occurs to me that a mask with NA values goes against https://github.com/pandas-dev/pandas/issues/20328 a bit... Implementing https://github.com/pandas-dev/pandas/issues/20328 would also make this cleaner, as the EX author need only pass through an `na_value`, and everything should be OK. I'll see if doing that is simple. @TomAugspurger Alternative is to just document that if you have float/object data, we expect np.nan, if you have integer data, we expect iNaT as missing value. And that extension authors then apply the mask themselves. 
That brings us back to the original implementation of the PR I think ..  #20328 doesn't look trivial, so I've abandoned it for now.

> Alternative is to just document that if you have float/object data, we expect np.nan, if you have integer data, we expect iNaT as missing value.

Yes, we'll need to do this regardless, as extension-array authors may have to take precautions if they use iNaT (int min) as a valid value. But I think we'll have to make it clear that this is an implementation detail at the moment.

>  That brings us back to the original implementation of the PR I think ..

Close. The main difference is that in c288d67, we mask the values going *into* the hashtable.

If this approach looks OK, I will add sufficiently scary warnings that the default implementation is using features private to pandas (`_factorize_array`, the missing value markers for each type of hashtable, etc.).

Tangent, I noticed that the UInt64Hashtable doesn't have a missing value marker. Was that intentional (ping @gfyoung I think).

```python
In [9]: from pandas.core.algorithms import _factorize_array

In [10]: _factorize_array(arr, check_nulls=True)
Out[10]:
(array([0, 0, 1, 2]),
 array([                   0,                    1, 18446744073709551615],
       dtype=uint64))
```

In hashtable_helper, the null condition seems to be the string `'False'`.

```
# name, dtype, null_condition, float_group
dtypes = [('Float64', 'float64', 'val != val', True),
          ('UInt64', 'uint64', 'False', False),
          ('Int64', 'int64', 'val == iNaT', False)]
```

Anyway, changing this probably isn't desired, but thought I'd mention it. > Tangent, I noticed that the UInt64Hashtable doesn't have a missing value marker.

@TomAugspurger : Unfortunately, there is no well-defined missing value marker for `uint` AFAIK. @jreback you can ignore all the back and forth between Joris and I yesterday about `mask`. I think https://github.com/pandas-dev/pandas/pull/20473 will make things nice for EA authors. They'll just need to specify

- The array to be used for factorization
- The scalar in their array to be considered NA.

Some examples:

- defualt: `self.astype(object), np.nan`
- Categorical: `self.codes.astype(int64), -1`
- MACArray: `self.data, 0` (this is in cyberpandas. A uint64 array, where 0 is NA) ok let's work on #20473 first then, that is exactly the kind of things would like to see. e.g. moving around pandas internals to make more friendly by essentially pushing things down rather than doing them solely in the EA. Updated on top of the parametrized NA value. Things look relatively clean now I think (most of the diff is due to moving docstrings to a shared spot). In terms of API:

```python
def _values_for_argsort(): -> Tuple[ndarray, Any]
    # array to factorize and na_value

@classmethod
@abstractmethod
def _from_factorized(cls, values, original): -> ExtensionArray
    # Reconstruct uniques from values & original
```

This is adequate for all our examples in pandas, including `JSONArray` which isn't otherwise factorizable (non-hashable). It also works well for IPArray and MACArray (Uint64 with 0 as the NA value).

@jorisvandenbossche do you think this will work well for geopandas? Can you have missing geometries?

The categorical tests are an example of using `original` in `_from_factorized`, as we copy over the unobserved categories to the `uniques` dtype. > @jorisvandenbossche do you think this will work well for geopandas? Can you have missing geometries?

Yes, that should be fine. I am not fully sure yet, but I think I will use a binary blob for each geometry ("well known binary" format), which will give an object array of bytes, and with eg None as missing value. So this should work (that should already work with `pd.factorize` itself without the new infrastructure I think). 
I will also need the `original` to add back metadata about the coordinate reference system.

 From Python your array of pointers look like Int64s, right? Could those be factorized? I *think* it should work, though I haven't thought it through fully.