[C++] Implement min_max kernel for array[string]

[asfimport]

As noted in pandas-dev/pandas#42597, pyarrow.compute.min_max on a string dtype array currently raises. Here's an example from Python

{{
In [1]: import pyarrow, pyarrow.compute

In [2]: a = pyarrow.array(['c', 'a', 'b'])

In [4]: pyarrow.compute.min_max(a)

ArrowNotImplementedError Traceback (most recent call last)
in
----> 1 pyarrow.compute.min_max(a)

~/miniconda3/envs/pandas=1.3.0/lib/python3.9/site-packages/pyarrow/compute.py in min_max(array, options, memory_pool, **kwargs)

~/miniconda3/envs/pandas=1.3.0/lib/python3.9/site-packages/pyarrow/_compute.pyx in pyarrow._compute.Function.call()

~/miniconda3/envs/pandas=1.3.0/lib/python3.9/site-packages/pyarrow/error.pxi in pyarrow.lib.pyarrow_internal_check_status()

~/miniconda3/envs/pandas=1.3.0/lib/python3.9/site-packages/pyarrow/error.pxi in pyarrow.lib.check_status()

ArrowNotImplementedError: Function min_max has no kernel matching input types (array[string])
}}

Reporter: Tom Augspurger / @TomAugspurger

Related issues:

• [C++] Add compute function min_max support for more types (is a child of)
• [C++] String algorithm library for StringArray/BinaryArray (is a child of)
• [C++] Add compute function min_max support for more types (is superceded by)

_{Note: This issue was originally created as ARROW-13410. Please see the migration documentation for further details.}

[asfimport]

Eduardo Ponce / @edponce:
A simple algorithm for finding the min/max string between a pair of strings:

for (int i = 0; i < std::min(s1.size(), s2.size()); ++i) {
        // They are different, one is greater than the other
        if (s1[i] > s2[i]) return s1;  // for min return s2
        if (s1[i] < s2[i]) return s2;  // for min return s1
    }
    // At least one is empty string, longest string is max
    return (s1.size() > s2.size()) ? s1 : s2;  // swap s1/s2 for min

Then use this function for a running min/max to get the result.
For UTF8 inputs, codepoints are decoded and compared instead.

[asfimport]

Eduardo Ponce / @edponce:
Actually the std::string library supports comparing strings in the same manner.
And there is a std::minmax function as well.

[asfimport]

Antoine Pitrou / @pitrou:
@edponce Are you still willing to work on this? Otherwise, can you please unassign?

[asfimport]

Eduardo Ponce / @edponce:
Not working on this at the moment.

[asfimport]

Antoine Pitrou / @pitrou:
This was actually fixed in ARROW-13882 and released in 6.0.0.