"""
SparseArray data structure
"""

from __future__ import annotations

from collections import abc
import numbers
import operator
from typing import (
    TYPE_CHECKING,
    Any,
    Literal,
    Self,
    cast,
    overload,
)
import warnings

import numpy as np

from pandas._config.config import _global_config as config

from pandas._libs import (
    lib,
    missing as libmissing,
)
import pandas._libs.sparse as splib
from pandas._libs.sparse import (
    BlockIndex,
    IntIndex,
    SparseIndex,
)
from pandas._libs.tslibs import (
    NaT,
    Timedelta,
    Timestamp,
    is_supported_dtype,
)
from pandas.compat import PYPY
from pandas.compat.numpy import function as nv
from pandas.errors import (
    Pandas4Warning,
    PerformanceWarning,
)
from pandas.util._decorators import (
    set_module,
)
from pandas.util._exceptions import find_stack_level
from pandas.util._validators import (
    validate_bool_kwarg,
)

from pandas.core.dtypes.astype import astype_array
from pandas.core.dtypes.cast import (
    can_hold_element,
    construct_1d_object_array_from_listlike,
    find_common_type,
    maybe_box_datetimelike,
    maybe_promote,
)
from pandas.core.dtypes.common import (
    is_bool_dtype,
    is_integer,
    is_list_like,
    is_object_dtype,
    is_scalar,
    is_string_dtype,
    pandas_dtype,
)
from pandas.core.dtypes.dtypes import (
    BaseMaskedDtype,
    DatetimeTZDtype,
    SparseDtype,
)
from pandas.core.dtypes.generic import (
    ABCIndex,
    ABCSeries,
)
from pandas.core.dtypes.missing import (
    is_valid_na_for_dtype,
    isna,
    na_value_for_dtype,
    notna,
)

from pandas.core import (
    arraylike,
    nanops,
    ops,
)
import pandas.core.algorithms as algos
from pandas.core.arraylike import OpsMixin
from pandas.core.arrays import ExtensionArray
from pandas.core.base import PandasObject
import pandas.core.common as com
from pandas.core.construction import (
    ensure_wrapped_if_datetimelike,
    extract_array,
    sanitize_array,
)
from pandas.core.indexers import (
    check_array_indexer,
    unpack_tuple_and_ellipses,
)
from pandas.core.nanops import (
    check_below_min_count,
    dt64_any_all_msg,
    na_accum_func,
)
from pandas.core.ops.array_ops import (
    arithmetic_op,
    comparison_op,
    logical_op,
)

if TYPE_CHECKING:
    from collections.abc import (
        Callable,
        Sequence,
    )
    from typing import (
        Protocol,
        type_check_only,
    )

    from scipy.sparse import (
        csc_array,
        csc_matrix,
    )

    @type_check_only
    class _SparseMatrixLike(Protocol):
        @property
        def shape(self, /) -> tuple[int, int]: ...
        def tocsc(self, /) -> csc_array | csc_matrix: ...

    from pandas._typing import NumpySorter

    SparseIndexKind = Literal["integer", "block"]

    from pandas._typing import (
        ArrayLike,
        AstypeArg,
        Axis,
        AxisInt,
        Dtype,
        NpDtype,
        PositionalIndexer,
        Scalar,
        ScalarIndexer,
        SequenceIndexer,
        SortKind,
        npt,
    )

    from pandas import Series


# Reductions whose SparseArray method takes skipna and must be handed it directly.
_skipna_aware_reductions = frozenset(
    {
        "sum",
        "prod",
        "mean",
        "median",
        "var",
        "std",
        "sem",
        "skew",
        "kurt",
        "min",
        "max",
        "any",
        "all",
        "argmin",
        "argmax",
    }
)

# Reductions whose result is a position in the array, not one of its values.
_positional_reductions = frozenset({"argmin", "argmax"})

# Reductions of complex input that give a real result.
_complex_to_real_reductions = frozenset({"var", "std", "sem", "skew", "kurt"})

# Reductions that give a bool rather than a value of the array's own dtype.
_boolean_reductions = frozenset({"any", "all"})

# Op names, dunders stripped, whose result is bool rather than either operand's dtype.
_comparison_ops = frozenset({"eq", "ne", "lt", "gt", "le", "ge"})


# ----------------------------------------------------------------------------
# Array


def _get_fill(arr: SparseArray) -> np.ndarray:
    """
    Create a 0-dim ndarray containing the fill value

    Parameters
    ----------
    arr : SparseArray

    Returns
    -------
    fill_value : ndarray
        0-dim ndarray with just the fill value.

    Notes
    -----
    coerce fill_value to arr dtype if possible
    int64 SparseArray can have NaN as fill_value if there is no missing
    """
    try:
        return np.asarray(arr.fill_value, dtype=arr.dtype.subtype)
    except ValueError:
        return np.asarray(arr.fill_value)


def _has_dense_fill(arr: SparseArray) -> bool:
    """
    Whether _get_fill can express arr's fill value as an array at all.

    Its fallback catches only ValueError, so a pd.NA fill escapes as a TypeError;
    such an operand keeps the object-cast path, which carries the fill through.
    """
    try:
        with np.errstate(all="ignore"):
            _get_fill(arr)
    except TypeError:
        return False
    return True


def _sparse_array_op(
    left: SparseArray, right: SparseArray, op: Callable[..., Any], name: str
) -> SparseArray:
    """
    Perform a binary operation between two arrays.

    Parameters
    ----------
    left : Union[SparseArray, ndarray]
    right : Union[SparseArray, ndarray]
    op : Callable
        The binary operation to perform
    name str
        Name of the callable.

    Returns
    -------
    SparseArray
    """
    if name.startswith("__"):
        # For lookups in _libs.sparse we need non-dunder op name
        name = name[2:-2]

    # dtype used to find corresponding sparse method
    ltype = left.dtype.subtype
    rtype = right.dtype.subtype

    if ltype != rtype:
        subtype = find_common_type([ltype, rtype])
        if (
            is_object_dtype(subtype)
            and not (is_object_dtype(ltype) or is_object_dtype(rtype))
            and _has_dense_fill(left)
            and _has_dense_fill(right)
        ):
            # GH#68562 no common subtype, e.g. int64 and m8[us]: casting both
            #  to object would leave an object result where the dense op
            #  promotes to m8[us]
            return _dense_array_op(left, right, op, name)

        ltype = SparseDtype(subtype, left.fill_value)
        rtype = SparseDtype(subtype, right.fill_value)

        left = left.astype(ltype, copy=False)
        right = right.astype(rtype, copy=False)
        dtype = ltype.subtype
    else:
        dtype = ltype

    # dtype the result must have
    result_dtype = None

    if left.sp_index.ngaps == 0 or right.sp_index.ngaps == 0:
        with np.errstate(all="ignore"):
            result = op(left.to_dense(), right.to_dense())
            fill = op(_get_fill(left), _get_fill(right))

        if left.sp_index.ngaps == 0:
            index = left.sp_index
        else:
            index = right.sp_index
    elif left.sp_index.equals(right.sp_index):
        with np.errstate(all="ignore"):
            result = op(left.sp_values, right.sp_values)
            fill = op(_get_fill(left), _get_fill(right))
        index = left.sp_index
    else:
        if name[0] == "r":
            left, right = right, left
            name = name[1:]

        if name in ("and", "or", "xor") and dtype == "bool":
            opname = f"sparse_{name}_uint8"
            # to make template simple, cast here
            left_sp_values = left.sp_values.view(np.uint8)
            right_sp_values = right.sp_values.view(np.uint8)
            result_dtype = bool
        else:
            opname = f"sparse_{name}_{dtype}"
            left_sp_values = left.sp_values
            right_sp_values = right.sp_values

        if (
            name in ["floordiv", "mod"]
            and (right == 0).any()
            and left.dtype.kind in "iu"
        ):
            # Match the non-Sparse Series behavior
            opname = f"sparse_{name}_float64"
            left_sp_values = left_sp_values.astype("float64")
            right_sp_values = right_sp_values.astype("float64")

        sparse_op = getattr(splib, opname)

        with np.errstate(all="ignore"):
            result, index, fill = sparse_op(
                left_sp_values,
                left.sp_index,
                left.fill_value,
                right_sp_values,
                right.sp_index,
                right.fill_value,
            )

    if name == "divmod":
        # result is a 2-tuple
        # error: Incompatible return value type (got "Tuple[SparseArray,
        # SparseArray]", expected "SparseArray")
        return (  # type: ignore[return-value]
            _wrap_result(name, result[0], index, fill[0], dtype=result_dtype),
            _wrap_result(name, result[1], index, fill[1], dtype=result_dtype),
        )

    if result_dtype is None:
        result_dtype = result.dtype

    return _wrap_result(name, result, index, fill, dtype=result_dtype)


def _dense_array_op(
    left: SparseArray, right: SparseArray, op: Callable[..., Any], name: str
) -> SparseArray:
    """
    Densify both operands, run the non-sparse op, and re-sparsify on the fill value.

    For subtypes with no common type only the non-sparse op knows the result
    dtype, and only it applies pandas' rules for the pairs numpy would otherwise
    accept (e.g. int64 + M8[us]).
    """
    if name in {"and", "rand", "or", "ror", "xor", "rxor"}:
        dense_op = logical_op
    elif name in _comparison_ops:
        dense_op = comparison_op
    else:
        dense_op = arithmetic_op

    lvalues = ensure_wrapped_if_datetimelike(left.to_dense())
    rvalues = ensure_wrapped_if_datetimelike(right.to_dense())

    with np.errstate(all="ignore"):
        # length-1 arrays, not scalars, so the fill values promote the way the
        #  values did
        lfill = ensure_wrapped_if_datetimelike(_get_fill(left).reshape(1))
        rfill = ensure_wrapped_if_datetimelike(_get_fill(right).reshape(1))
        result = dense_op(lvalues, rvalues, op)
        fill = dense_op(lfill, rfill, op)

    if name in ("divmod", "rdivmod"):
        # error: Incompatible return value type (got "Tuple[SparseArray,
        # SparseArray]", expected "SparseArray")
        return (  # type: ignore[return-value]
            _wrap_dense_result(name, result[0], fill[0], left.kind),
            _wrap_dense_result(name, result[1], fill[1], left.kind),
        )
    return _wrap_dense_result(name, result, fill, left.kind)


def _wrap_dense_result(name: str, result, fill, kind: SparseIndexKind) -> SparseArray:
    """
    Sparsify one _dense_array_op result on the matching entry of its fill array.
    """
    values = np.asarray(result)
    # np.asarray so a datetimelike op's Timestamp/Timedelta fill is spelled the
    #  way every other _sparse_array_op path spells it
    fill_value = np.asarray(fill)[0]
    if values.dtype.kind in "mM" and isna(fill_value):
        # _get_fill gives up the subtype for a fill value it cannot hold -- the
        #  np.nan a float operand contributes -- so this can be the wrong NA
        fill_value = SparseDtype(values.dtype).fill_value
    return _wrap_result(name, values, None, fill_value, values.dtype, kind)


def _as_sparse_operand(
    values: np.ndarray, fill_value, dtype: Dtype | None = None
) -> SparseArray:
    """
    Wrap a non-sparse operand for _sparse_array_op, reusing the other operand's
    fill_value where that is a valid value for this operand's subtype.
    """
    # GH#68466 fill_value need not suit the operand's subtype; check it here
    #  rather than catch the construction, which can warn before it raises.
    try:
        SparseDtype(dtype if dtype is not None else values.dtype, fill_value)
    except (TypeError, ValueError):
        # leave any real incompatibility for op() to report
        return SparseArray(values, dtype=dtype)
    return SparseArray(values, fill_value=fill_value, dtype=dtype)


def _wrap_result(
    name: str,
    data,
    sparse_index,
    fill_value,
    dtype: Dtype | None = None,
    kind: SparseIndexKind = "integer",
) -> SparseArray:
    """
    wrap op result to have correct dtype
    """
    if name.startswith("__"):
        # e.g. __eq__ --> eq
        name = name[2:-2]

    if name in _comparison_ops:
        dtype = bool

    fill_value = lib.item_from_zerodim(fill_value)

    if is_bool_dtype(dtype):
        # fill_value may be np.bool_
        fill_value = bool(fill_value)
    if sparse_index is None:
        # a dense result, e.g. from _wrap_dense_result: sparsify it here
        return SparseArray(data, fill_value=fill_value, dtype=dtype, kind=kind)

    data, sparse_index = _prune_fill_value(data, sparse_index, fill_value)

    if dtype is not None:
        data = np.asarray(data, dtype=dtype)  # type: ignore[arg-type]
    else:
        data = np.asarray(data)
    sparse_dtype = SparseDtype(data.dtype, fill_value)
    return SparseArray._simple_new(data, sparse_index, sparse_dtype)


def _differs_from_fill(values: np.ndarray, fill_value) -> np.ndarray:
    """
    Which of ``values`` would not densify as ``fill_value``.
    """
    if isna(fill_value):
        return notna(values)
    mask = values != fill_value
    if values.dtype.kind == "f" and fill_value == 0:
        # -0.0 == 0.0 but the two densify differently, so a stored signed zero
        #  is a real point
        mask |= np.signbit(values) != np.signbit(fill_value)
    return mask


def _prune_fill_value(
    sp_values: np.ndarray, sparse_index: SparseIndex, fill_value
) -> tuple[np.ndarray, SparseIndex]:
    """
    Drop stored values that densify as fill_value, so sp_index holds only real points.

    GH#45126 the ops reuse an operand's sparse index or the union of both, either
    of which can cover a position the op turned into the fill value.
    """
    if sp_values.dtype.kind == "c":
        # isna() is True when either part is NaN, so it cannot decide a complex
        #  on its own
        mask = _differs_from_fill(sp_values.real, np.real(fill_value)) | (
            _differs_from_fill(sp_values.imag, np.imag(fill_value))
        )
    elif sp_values.dtype == object:
        if isna(fill_value):
            # object can hold several NAs at once, and only the fill's own spelling
            #  densifies back as the fill
            mask = np.array(
                [not libmissing.is_matching_na(x, fill_value) for x in sp_values],
                dtype=bool,
            )
        else:
            # 0, 0.0 and False compare equal, so use _make_sparse's type-aware check
            mask = splib.make_mask_object_ndarray(sp_values, fill_value)
    else:
        mask = _differs_from_fill(sp_values, fill_value)

    if mask.all():
        return sp_values, sparse_index

    kind: SparseIndexKind = "integer" if isinstance(sparse_index, IntIndex) else "block"
    indices = sparse_index.indices[mask]
    return sp_values[mask], make_sparse_index(sparse_index.length, indices, kind)


_BOOL_SPARSE_DTYPE_FALSE_FILL = SparseDtype(bool, False)
_BOOL_SPARSE_DTYPE_TRUE_FILL = SparseDtype(bool, True)


def _can_hold_for_fill(dtype: np.dtype, fill_value) -> bool:
    """
    Whether a dense ``dtype`` array can hold ``fill_value`` without promoting.
    """
    dummy = ensure_wrapped_if_datetimelike(np.empty(0, dtype=dtype))
    return can_hold_element(dummy, fill_value)


def _unbox_for_fill(dtype: np.dtype, fill_value):
    """
    ``fill_value`` unboxed — for a datetimelike ``dtype``, as a numpy scalar in
    that dtype's own unit. Only valid once ``_can_hold_for_fill`` has accepted it.
    """
    if dtype.kind not in "mM":
        # an object dtype holds these as-is; only a datetimelike array needs
        #  the numpy scalar, and only it rejects np.nan in place of NaT
        return fill_value
    if isna(fill_value):
        # a unitless NaT is deprecated as of numpy 2.5
        return dtype.type("NaT", np.datetime_data(dtype)[0])
    # numpy routes a boxed scalar through the stdlib datetime protocol and
    #  truncates; can_hold_element has already ruled out a lossy conversion
    box = Timestamp if dtype.kind == "M" else Timedelta
    return box(fill_value).asm8.astype(dtype)


def _promote_for_fill(dtype: np.dtype, fill_value) -> tuple[np.dtype, Any]:
    """
    Dense dtype wide enough to hold ``fill_value``, and ``fill_value`` unboxed —
    for a datetimelike ``dtype``, as a numpy scalar in that dtype's own unit.

    ``maybe_promote`` is no good on its own: its datetime64 arm widens to ``M8[ns]``
    whenever the fill value's unit differs, so a ``Timestamp`` would pull a
    ``Sparse[M8[s]]`` up to nanoseconds.
    """
    if _can_hold_for_fill(dtype, fill_value):
        return dtype, _unbox_for_fill(dtype, fill_value)
    return maybe_promote(dtype, fill_value)


@set_module("pandas.arrays")
class SparseArray(OpsMixin, PandasObject, ExtensionArray):
    """
    An ExtensionArray for storing sparse data.

    SparseArray efficiently stores data with a high frequency of a
    specific fill value (e.g., zeros), saving memory by only retaining
    non-fill elements and their indices. This class is particularly
    useful for large datasets where most values are redundant.

    Parameters
    ----------
    data : array-like or scalar
        A dense array of values to store in the SparseArray. This may contain
        `fill_value`.
    sparse_index : SparseIndex, optional
        Index indicating the locations of sparse elements.

        .. deprecated:: 3.1.0
            Use :meth:`SparseArray.from_indices` instead.
    fill_value : scalar, optional
        Elements in data that are ``fill_value`` are not stored in the
        SparseArray. For memory savings, this should be the most common value
        in `data`. By default, `fill_value` depends on the dtype of `data`:

        =========== ==========
        data.dtype  na_value
        =========== ==========
        float       ``np.nan``
        int         ``0``
        bool        False
        datetime64  ``np.datetime64("NaT")``
        timedelta64 ``np.timedelta64("NaT")``
        =========== ==========

        The fill value is potentially specified in three ways. In order of
        precedence, these are

        1. The `fill_value` argument
        2. ``dtype.fill_value`` if `fill_value` is None and `dtype` is
           a ``SparseDtype``
        3. ``data.dtype.fill_value`` if `fill_value` is None and `dtype`
           is not a ``SparseDtype`` and `data` is a ``SparseArray``.

    kind : str
        Can be 'integer' or 'block', default is 'integer'.
        The type of storage for sparse locations.

        * 'block': Stores a `block` and `block_length` for each
          contiguous *span* of sparse values. This is best when
          sparse data tends to be clumped together, with large
          regions of ``fill-value`` values between sparse values.
        * 'integer': uses an integer to store the location of
          each sparse value.

    dtype : np.dtype or SparseDtype, optional
        The dtype to use for the SparseArray. For numpy dtypes, this
        determines the dtype of ``self.sp_values``. For SparseDtype,
        this determines ``self.sp_values`` and ``self.fill_value``.
    copy : bool, default False
        Whether to explicitly copy the incoming `data` array.

    Attributes
    ----------
    None

    Methods
    -------
    None

    See Also
    --------
    SparseDtype : Dtype for sparse data.

    Examples
    --------
    >>> from pandas.arrays import SparseArray
    >>> arr = SparseArray([0, 0, 1, 2])
    >>> arr
    <SparseArray>
    [0, 0, 1, 2]
    Length: 4, dtype: Sparse[int64, 0]
    """

    _subtyp = "sparse_array"  # register ABCSparseArray
    _hidden_attrs = PandasObject._hidden_attrs | frozenset([])
    _sparse_index: SparseIndex
    _sparse_values: np.ndarray
    _dtype: SparseDtype

    def __init__(
        self,
        data,
        sparse_index=lib.no_default,
        fill_value=None,
        kind: SparseIndexKind = "integer",
        dtype: Dtype | None = None,
        copy: bool = False,
    ) -> None:
        if sparse_index is not lib.no_default:
            warnings.warn(
                "The 'sparse_index' parameter of SparseArray.__init__ is "
                "deprecated and will be removed in a future version. "
                "Use SparseArray.from_indices instead.",
                Pandas4Warning,
                stacklevel=find_stack_level(),
            )
        else:
            sparse_index = None

        if fill_value is None and isinstance(dtype, SparseDtype):
            fill_value = dtype.fill_value

        if isinstance(data, type(self)):
            # disable normal inference on dtype, sparse_index, & fill_value
            if sparse_index is None:
                sparse_index = data.sp_index
            if fill_value is None:
                fill_value = data.fill_value
            if dtype is None:
                dtype = data.dtype
            # TODO: make kind=None, and use data.kind?
            data = data.sp_values

        # Handle use-provided dtype
        if isinstance(dtype, str):
            # Two options: dtype='int', regular numpy dtype
            # or dtype='Sparse[int]', a sparse dtype
            try:
                dtype = SparseDtype.construct_from_string(dtype)
            except TypeError:
                dtype = pandas_dtype(dtype)

        if isinstance(dtype, SparseDtype):
            if fill_value is None:
                fill_value = dtype.fill_value
            dtype = dtype.subtype

        if is_scalar(data):
            raise TypeError(
                f"Cannot construct {type(self).__name__} from scalar data. "
                "Pass a sequence instead."
            )

        if dtype is not None:
            dtype = pandas_dtype(dtype)

        # TODO: disentangle the fill_value dtype inference from
        # dtype inference
        if data is None:
            # TODO: What should the empty dtype be? Object or float?

            # error: Argument "dtype" to "array" has incompatible type
            # "Union[ExtensionDtype, dtype[Any], None]"; expected "Union[dtype[Any],
            # None, type, _SupportsDType, str, Union[Tuple[Any, int], Tuple[Any,
            # Union[int, Sequence[int]]], List[Any], _DTypeDict, Tuple[Any, Any]]]"
            data = np.array([], dtype=dtype)  # type: ignore[arg-type]

        try:
            data = sanitize_array(data, index=None)
        except ValueError:
            # NumPy may raise a ValueError on data like [1, []]
            # we retry with object dtype here.
            if dtype is None:
                dtype = np.dtype(object)
                data = np.atleast_1d(np.asarray(data, dtype=dtype))
            else:
                raise

        if lib.is_np_dtype(data.dtype, "mM") and not is_supported_dtype(data.dtype):
            # GH#68522 cast to a resolution we can hold, and reject a multiplier
            #  unit, the way the dense constructors do
            data = np.asarray(ensure_wrapped_if_datetimelike(data))

        if copy:
            # TODO: avoid double copy when dtype forces cast.
            data = data.copy()

        if fill_value is None:
            fill_value_dtype = data.dtype if dtype is None else dtype
            if fill_value_dtype is None:
                fill_value = np.nan
            else:
                fill_value = na_value_for_dtype(fill_value_dtype)

        if isinstance(data, type(self)) and sparse_index is None:
            sparse_index = data._sparse_index
            # error: Argument "dtype" to "asarray" has incompatible type
            # "Union[ExtensionDtype, dtype[Any], None]"; expected "None"
            sparse_values = np.asarray(
                data.sp_values,
                dtype=dtype,  # type: ignore[arg-type]
            )
        elif sparse_index is None:
            data = extract_array(data, extract_numpy=True)
            if not isinstance(data, np.ndarray):
                # EA
                if isinstance(data.dtype, DatetimeTZDtype):
                    warnings.warn(
                        f"Creating SparseArray from {data.dtype} data "
                        "loses timezone information. Cast to object before "
                        "sparse to retain timezone information.",
                        UserWarning,
                        stacklevel=find_stack_level(),
                    )
                    data = np.asarray(data, dtype="datetime64[ns]")
                    if fill_value is NaT:
                        fill_value = np.datetime64("NaT", "ns")
                data = np.asarray(data)
            sparse_values, sparse_index, fill_value = _make_sparse(
                # error: Argument "dtype" to "_make_sparse" has incompatible type
                # "Union[ExtensionDtype, dtype[Any], None]"; expected
                # "Optional[dtype[Any]]"
                data,
                kind=kind,
                fill_value=fill_value,
                dtype=dtype,  # type: ignore[arg-type]
            )
        else:
            # error: Argument "dtype" to "asarray" has incompatible type
            # "Union[ExtensionDtype, dtype[Any], None]"; expected "None"
            sparse_values = np.asarray(data, dtype=dtype)  # type: ignore[arg-type]
            if len(sparse_values) != sparse_index.npoints:
                raise AssertionError(
                    f"Non array-like type {type(sparse_values)} must "
                    "have the same length as the index"
                )
        self._sparse_index = sparse_index
        self._sparse_values = sparse_values
        self._dtype = SparseDtype(sparse_values.dtype, fill_value)

    @classmethod
    def _simple_new(
        cls,
        sparse_array: np.ndarray,
        sparse_index: SparseIndex,
        dtype: SparseDtype,
    ) -> Self:
        new = object.__new__(cls)
        new._sparse_index = sparse_index
        new._sparse_values = sparse_array
        new._dtype = dtype
        return new

    @classmethod
    def from_spmatrix(cls, data: _SparseMatrixLike) -> Self:
        """
        Create a SparseArray from a scipy.sparse matrix.

        Parameters
        ----------
        data : scipy.sparse.sp_matrix
            This should be a SciPy sparse matrix where the size
            of the second dimension is 1. In other words, a
            sparse matrix with a single column.

        Returns
        -------
        SparseArray

        Examples
        --------
        >>> import scipy.sparse
        >>> mat = scipy.sparse.coo_matrix((4, 1))
        >>> pd.arrays.SparseArray.from_spmatrix(mat)
        <SparseArray>
        [0.0, 0.0, 0.0, 0.0]
        Length: 4, dtype: Sparse[float64, 0.0]
        """
        length, ncol = data.shape

        if ncol != 1:
            raise ValueError(f"'data' must have a single column, not '{ncol}'")

        # our sparse index classes require that the positions be strictly
        # increasing. So we need to sort loc, and arr accordingly.
        data_csc = data.tocsc()
        data_csc.sort_indices()
        arr = data_csc.data
        idx = data_csc.indices

        zero = np.array(0, dtype=arr.dtype).item()
        dtype = SparseDtype(arr.dtype, zero)
        index = IntIndex(length, idx)

        return cls._simple_new(arr, index, dtype)

    @classmethod
    def from_indices(
        cls,
        data,
        indices,
        length: int,
        fill_value=None,
        kind: SparseIndexKind = "integer",
        dtype: Dtype | None = None,
    ) -> Self:
        """
        Create a SparseArray from an array of sparse values and their indices.

        This allows constructing a SparseArray without materializing a dense
        array, which is useful for large arrays where most values are the
        fill value.

        Parameters
        ----------
        data : array-like
            The sparse (non-fill) values.
        indices : array-like of int
            The indices in the dense array where the sparse values are located.
            Must be strictly increasing and within ``[0, length)``.
        length : int
            The total length of the resulting SparseArray.
        fill_value : scalar, optional
            The fill value to use for positions not in ``indices``.
            By default, uses ``np.nan`` for float dtypes and the appropriate
            NA value for other dtypes.
        kind : {{'integer', 'block'}}, default 'integer'
            The type of sparse index to use.
        dtype : np.dtype or ExtensionDtype, optional
            The dtype for the sparse values.

        Returns
        -------
        SparseArray

        See Also
        --------
        SparseArray.from_spmatrix : Create a SparseArray from a scipy.sparse matrix.

        Examples
        --------
        >>> SparseArray.from_indices(
        ...     [1, 2, 3], indices=[1, 3, 5], length=7, fill_value=0
        ... )
        <SparseArray>
        [0, 1, 0, 2, 0, 3, 0]
        Length: 7, dtype: Sparse[int64, 0]

        This avoids materializing a dense array of length 7.
        """
        sparse_values = np.asarray(
            sanitize_array(data, index=None),  # type: ignore[arg-type]
            dtype=dtype,  # type: ignore[arg-type]
        )
        indices = np.asarray(indices, dtype=np.int32)

        if len(sparse_values) != len(indices):
            raise ValueError(
                f"Length of data ({len(sparse_values)}) must match "
                f"length of indices ({len(indices)})."
            )

        sparse_index = make_sparse_index(length, indices, kind)

        if fill_value is None:
            fill_value = na_value_for_dtype(sparse_values.dtype)

        sparse_dtype = SparseDtype(sparse_values.dtype, fill_value)
        return cls._simple_new(sparse_values, sparse_index, sparse_dtype)

    def __array__(
        self, dtype: NpDtype | None = None, copy: bool | None = None
    ) -> np.ndarray:
        if (
            dtype is not None
            and np.dtype(dtype) == object
            and self.sp_values.dtype.kind in "mM"
        ):
            # numpy renders datetime64/timedelta64 as ints when casting to
            # object; box them ourselves, see test_array_object_datetimelike
            if copy is False:
                raise ValueError(
                    "Unable to avoid copy while creating an array as requested."
                )
            dense = ensure_wrapped_if_datetimelike(np.asarray(self))
            return np.asarray(dense, dtype=object)

        if self.sp_index.ngaps == 0:
            # Compat for na dtype and int values.
            if copy is True:
                return np.array(self.sp_values)
            else:
                result = self.sp_values
                if self._readonly:
                    result = result.view()
                    result.flags.writeable = False
                return result

        if copy is False:
            raise ValueError(
                "Unable to avoid copy while creating an array as requested."
            )

        fill_value = self.fill_value

        if self.sp_values.dtype.kind in "mM":
            # np.result_type gives object for a Timestamp/Timedelta fill value
            #  and raises for np.nan; the helper also puts the fill in the
            #  subtype's unit, see test_to_dense_datetimelike_fill_other_unit
            inferred, fill_value = _promote_for_fill(self.sp_values.dtype, fill_value)
            if dtype is None:
                dtype = inferred
        elif dtype is None:
            # Can NumPy represent this type?
            # If not, `np.result_type` will raise. We catch that
            # and return object.
            try:
                dtype = np.result_type(self.sp_values.dtype, type(fill_value))
            except TypeError:
                dtype = object

        out = np.full(self.shape, fill_value, dtype=dtype)
        out[self.sp_index.indices] = self.sp_values
        return out

    def __setitem__(self, key, value) -> None:
        if self._readonly:
            raise ValueError("Cannot modify read-only array")
        # Only positions already held in sp_values could be written in place,
        #  and which those are depends on the value being set, so SparseDtype
        #  is _is_immutable, see GH#21818.
        msg = "SparseArray does not support item assignment via setitem"
        raise TypeError(msg)

    def sort(
        self,
        *,
        ascending: bool = True,
        kind: SortKind = "quicksort",
        na_position: str = "last",
    ) -> None:
        raise NotImplementedError("SparseArray does not support in-place sort")

    @classmethod
    def _from_sequence(
        cls, scalars, *, dtype: Dtype | None = None, copy: bool = False
    ) -> Self:
        return cls(scalars, dtype=dtype)

    @classmethod
    def _from_factorized(cls, values, original) -> Self:
        return cls(values, dtype=original.dtype)

    def _cast_pointwise_result(self, values):
        if not (isinstance(values, np.ndarray) and values.dtype == object):
            values = construct_1d_object_array_from_listlike(values)
        result = lib.maybe_convert_objects(values, convert_non_numeric=True)
        if result.dtype.kind == self.dtype.kind:
            try:
                # e.g. test_groupby_agg_extension
                res = type(self)._from_sequence(result, dtype=self.dtype)
                if ((res == result) | (isna(result) & res.isna())).all():
                    # This does not hold for e.g.
                    #  test_arith_frame_with_scalar[0-__truediv__]
                    return res
                return type(self)._from_sequence(result)
            except (ValueError, TypeError):
                return type(self)._from_sequence(result)
        else:
            # e.g. test_combine_le avoid casting bools to Sparse[float64, nan]
            return type(self)._from_sequence(result)

    # ------------------------------------------------------------------------
    # Data
    # ------------------------------------------------------------------------
    @property
    def sp_index(self) -> SparseIndex:
        """
        The SparseIndex containing the location of non- ``fill_value`` points.
        """
        return self._sparse_index

    @property
    def sp_values(self) -> np.ndarray:
        """
        An ndarray containing the non- ``fill_value`` values.

        This property returns the actual data values stored in the sparse
        representation, excluding the values that are equal to the ``fill_value``.
        The result is an ndarray of the underlying values, preserving the sparse
        structure by omitting the default ``fill_value`` entries.

        See Also
        --------
        Series.sparse.to_dense : Convert a Series from sparse values to dense.
        Series.sparse.fill_value : Elements in `data` that are `fill_value` are
            not stored.
        Series.sparse.density : The percent of non- ``fill_value`` points, as decimal.

        Examples
        --------
        >>> from pandas.arrays import SparseArray
        >>> s = SparseArray([0, 0, 1, 0, 2], fill_value=0)
        >>> s.sp_values
        array([1, 2])
        """
        return self._sparse_values

    @property
    def dtype(self) -> SparseDtype:
        return self._dtype

    @property
    def fill_value(self):
        """
        Elements in `data` that are `fill_value` are not stored.

        For memory savings, this should be the most common value in the array.

        See Also
        --------
        SparseDtype : Dtype for data stored in :class:`SparseArray`.
        Series.value_counts : Return a Series containing counts of unique values.
        Series.fillna : Fill NA/NaN in a Series with a specified value.

        Examples
        --------
        >>> ser = pd.Series([0, 0, 2, 2, 2], dtype="Sparse[int]")
        >>> ser.sparse.fill_value
        0
        >>> spa_dtype = pd.SparseDtype(dtype=np.int32, fill_value=2)
        >>> ser = pd.Series([0, 0, 2, 2, 2], dtype=spa_dtype)
        >>> ser.sparse.fill_value
        2
        """
        return self.dtype.fill_value

    @fill_value.setter
    def fill_value(self, value) -> None:
        self._dtype = SparseDtype(self.dtype.subtype, value)

    @property
    def kind(self) -> SparseIndexKind:
        """
        The kind of sparse index for this array. One of {'integer', 'block'}.
        """
        if isinstance(self.sp_index, IntIndex):
            return "integer"
        else:
            return "block"

    @property
    def _valid_sp_values(self) -> np.ndarray:
        sp_vals = self.sp_values
        mask = notna(sp_vals)
        return sp_vals[mask]

    def __len__(self) -> int:
        return self.sp_index.length

    @property
    def _null_fill_value(self) -> bool:
        return self._dtype._is_na_fill_value

    @property
    def nbytes(self) -> int:
        return self.sp_values.nbytes + self.sp_index.nbytes

    def memory_usage(self, deep: bool = False) -> int:
        """
        Memory usage of the stored values and the sparse index, in bytes.

        Positions holding ``fill_value`` are not stored.

        Parameters
        ----------
        deep : bool, default False
            Introspect the data deeply by interrogating an ``object`` subtype
            for system-level memory consumption. Has no effect on PyPy.

        Returns
        -------
        int
            Bytes consumed.

        See Also
        --------
        SparseArray.nbytes : Memory usage without deep introspection.
        Series.memory_usage : Memory usage of a Series.
        DataFrame.memory_usage : Memory usage of each column in a DataFrame.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray(["a", "a", "b"], fill_value="a")
        >>> arr.memory_usage()
        12
        >>> arr.memory_usage(deep=True) > arr.memory_usage()
        True
        """
        result = self.nbytes
        if deep and not PYPY and self.sp_values.dtype == object:
            # deep introspection relies on sys.getsizeof, which always
            # raises TypeError on PyPy (GH#46176)
            return result + lib.memory_usage_of_objects(self.sp_values)
        return result

    @property
    def density(self) -> float:
        """
        The percent of non- ``fill_value`` points, as decimal.

        This is calculated as the number of non-fill-value points divided by
        the total length of the array. A density of 1.0 means no values are
        the fill value, while 0.0 means all values are the fill value. An
        empty array has no density and returns ``nan``.

        See Also
        --------
        DataFrame.sparse.from_spmatrix : Create a new DataFrame from a
            scipy sparse matrix.

        Examples
        --------
        >>> from pandas.arrays import SparseArray
        >>> s = SparseArray([0, 0, 1, 1, 1], fill_value=0)
        >>> s.density
        0.6
        """
        if self.sp_index.length == 0:
            # 0 / 0 is undefined
            return np.nan
        return self.sp_index.npoints / self.sp_index.length

    @property
    def npoints(self) -> int:
        """
        The number of non- ``fill_value`` points.

        This property returns the number of elements in the sparse series that are
        not equal to the ``fill_value``. Sparse data structures store only the
        non-``fill_value`` elements, reducing memory usage when the majority of
        values are the same.

        See Also
        --------
        Series.sparse.to_dense : Convert a Series from sparse values to dense.
        Series.sparse.fill_value : Elements in ``data`` that are ``fill_value`` are
            not stored.
        Series.sparse.density : The percent of non- ``fill_value`` points, as decimal.

        Examples
        --------
        >>> from pandas.arrays import SparseArray
        >>> s = SparseArray([0, 0, 1, 1, 1], fill_value=0)
        >>> s.npoints
        3
        """
        return self.sp_index.npoints

    # error: Return type "SparseArray" of "isna" incompatible with return type
    # "ndarray[Any, Any] | ExtensionArrayNaResult" in supertype "ExtensionArray"
    def isna(self) -> Self:  # type: ignore[override]
        # If null fill value, we want SparseDtype[bool, true]
        # to preserve the same memory usage.
        if self._null_fill_value:
            return type(self)._simple_new(
                isna(self.sp_values),
                self.sp_index,
                _BOOL_SPARSE_DTYPE_TRUE_FILL,
            )
        # GH#41023 - avoid densify-then-resparsify round-trip.
        # The NA positions are exactly the subset of sp_index where sp_values
        # are NA; we can construct the sparse index directly.
        sp_mask = isna(self.sp_values)
        na_indices = self.sp_index.indices[sp_mask]
        new_sp_index = make_sparse_index(len(self), na_indices, self.kind)
        return type(self)._simple_new(
            np.ones(len(na_indices), dtype=bool),
            new_sp_index,
            _BOOL_SPARSE_DTYPE_FALSE_FILL,
        )

    def fillna(
        self,
        value,
        limit: int | None = None,
        copy: bool = True,
    ) -> Self:
        """
        Fill missing values with `value`.

        Parameters
        ----------
        value : scalar
        limit : int, optional
            Not supported for SparseArray, must be None.
        copy: bool, default True
            Ignored for SparseArray.

        Returns
        -------
        SparseArray

        Notes
        -----
        When `value` is specified, the result's ``fill_value`` depends on
        ``self.fill_value``. The goal is to maintain low-memory use.

        If ``self.fill_value`` is NA, the result dtype will be
        ``SparseDtype(self.dtype, fill_value=value)``. This will preserve
        amount of memory used before and after filling.

        When ``self.fill_value`` is not NA, the result dtype will be
        ``self.dtype``. Again, this preserves the amount of memory used.
        """
        if isinstance(value, dict):
            raise TypeError(
                "ExtensionArray.fillna does not support filling with a dict. "
                "Use Series.fillna instead."
            )
        if limit is not None:
            raise ValueError("limit must be None")

        subtype = self.sp_values.dtype
        if (
            subtype.kind in "mM"
            and is_scalar(value)
            and _can_hold_for_fill(subtype, value)
        ):
            # np.where resolves a scalar it cannot match against an M8/m8 array
            #  as object, or in the scalar's own unit, either way leaving
            #  sp_values disagreeing with the dtype
            value = _unbox_for_fill(subtype, value)

        new_values = np.where(isna(self.sp_values), value, self.sp_values)

        if self._null_fill_value:
            # This is essentially just updating the dtype.
            new_dtype = SparseDtype(self.dtype.subtype, fill_value=value)
        else:
            new_dtype = self.dtype

        return self._simple_new(new_values, self._sparse_index, new_dtype)

    def shift(self, periods: int = 1, fill_value=None) -> Self:
        if not len(self) or periods == 0:
            return self.copy()

        if isna(fill_value):
            fill_value = self.dtype.na_value

        subtype, fill_value = _promote_for_fill(self.dtype.subtype, fill_value)

        if subtype != self.dtype.subtype:
            # just coerce up front
            arr = self.astype(SparseDtype(subtype, self.fill_value))
        else:
            arr = self

        empty = self._from_sequence(
            [fill_value] * min(abs(periods), len(self)), dtype=arr.dtype
        )

        if periods > 0:
            a = empty
            b = arr[:-periods]
        else:
            a = arr[abs(periods) :]
            b = empty
        return arr._concat_same_type([a, b])

    def _first_fill_value_loc(self):
        """
        Get the location of the first fill value.

        Returns
        -------
        int
        """
        if len(self) == 0 or self.sp_index.npoints == len(self):
            return -1

        indices = self.sp_index.indices
        if not len(indices) or indices[0] > 0:
            return 0

        # a number larger than 1 should be appended to
        # the last in case of fill value only appears
        # in the tail of array
        diff = np.r_[np.diff(indices), 2]
        return indices[(diff > 1).argmax()] + 1

    def duplicated(
        self, keep: Literal["first", "last", False] = "first"
    ) -> npt.NDArray[np.bool_]:
        """
        Return boolean ndarray denoting duplicate values.

        Parameters
        ----------
        keep : {'first', 'last', False}, default 'first'
            - ``first`` : Mark duplicates as ``True`` except for the first occurrence.
            - ``last`` : Mark duplicates as ``True`` except for the last occurrence.
            - False : Mark all duplicates as ``True``.

        Returns
        -------
        ndarray[bool]
            With true in indices where elements are duplicated and false otherwise.

        See Also
        --------
        DataFrame.duplicated : Return boolean Series denoting
            duplicate rows.
        Series.duplicated : Indicate duplicate Series values.
        api.extensions.ExtensionArray.unique : Compute the ExtensionArray
            of unique values.

        Examples
        --------
        >>> pd.array([1, 1, 2, 3, 3], dtype=pd.SparseDtype(np.int64)).duplicated()
        array([False,  True, False, False,  True])
        """

        values = np.asarray(self)
        mask = np.asarray(self.isna())
        return algos.duplicated(values, keep=keep, mask=mask)

    def unique(self) -> Self:
        uniques = algos.unique(self.sp_values)
        if len(self.sp_values) != len(self):
            fill_loc = self._first_fill_value_loc()
            # Inorder to align the behavior of pd.unique or
            # pd.Series.unique, we should keep the original
            # order, here we use unique again to find the
            # insertion place. Since the length of sp_values
            # is not large, maybe minor performance hurt
            # is worthwhile to the correctness.
            insert_loc = len(algos.unique(self.sp_values[:fill_loc]))
            uniques = np.insert(uniques, insert_loc, self.fill_value)
        return type(self)._from_sequence(uniques, dtype=self.dtype)

    def _values_for_factorize(self):
        # Still override this for hash_pandas_object
        return np.asarray(self), self.fill_value

    def factorize(
        self,
        use_na_sentinel: bool = True,
    ) -> tuple[np.ndarray, SparseArray]:
        # Currently, ExtensionArray.factorize -> Tuple[ndarray, EA]
        # The sparsity on this is backwards from what Sparse would want. Want
        # ExtensionArray.factorize -> Tuple[EA, EA]
        # Given that we have to return a dense array of codes, why bother
        # implementing an efficient factorize?
        codes, uniques = algos.factorize(
            np.asarray(self), use_na_sentinel=use_na_sentinel
        )
        uniques_sp = SparseArray(uniques, dtype=self.dtype)
        return codes, uniques_sp

    def value_counts(self, dropna: bool = True) -> Series:
        """
        Returns a Series containing counts of unique values.

        Parameters
        ----------
        dropna : bool, default True
            Don't include counts of NaN, even if NaN is in sp_values.

        Returns
        -------
        counts : Series
        """
        from pandas import (
            Index,
            Series,
        )

        keys, counts, _ = algos.value_counts_arraylike(self.sp_values, dropna=dropna)
        fcounts = self.sp_index.ngaps
        if fcounts > 0 and (not self._null_fill_value or not dropna):
            if self._null_fill_value:
                mask = isna(keys)
            elif keys.dtype == object:
                # GH#68586 an object key such as pd.NA compares to a non-bool,
                #  which mask.any() cannot consume
                mask = ops.comp_method_OBJECT_ARRAY(operator.eq, keys, self.fill_value)
            else:
                mask = keys == self.fill_value
            if mask.any():
                counts[mask] += fcounts
            else:
                # error: Argument 1 to "insert" has incompatible type "Union[
                # ExtensionArray,ndarray[Any, Any]]"; expected "Union[
                # _SupportsArray[dtype[Any]], Sequence[_SupportsArray[dtype
                # [Any]]], Sequence[Sequence[_SupportsArray[dtype[Any]]]],
                # Sequence[Sequence[Sequence[_SupportsArray[dtype[Any]]]]], Sequence
                # [Sequence[Sequence[Sequence[_SupportsArray[dtype[Any]]]]]]]"
                keys = np.insert(keys, 0, self.fill_value)  # type: ignore[arg-type]
                counts = np.insert(counts, 0, fcounts)

        if not isinstance(keys, ABCIndex):
            index = Index(keys, copy=False)
        else:
            index = keys
        return Series(counts, index=index, copy=False)

    # --------
    # Indexing
    # --------
    @overload
    def __getitem__(self, key: ScalarIndexer) -> Any: ...

    @overload
    def __getitem__(self, key: SequenceIndexer) -> Self: ...

    def __getitem__(self, key: PositionalIndexer) -> Self | Any:
        if isinstance(key, tuple):
            key = unpack_tuple_and_ellipses(key)
            if key is ...:
                raise ValueError("Cannot slice with Ellipsis")

        if is_integer(key):
            return self._get_val_at(key)
        elif isinstance(key, tuple):
            data_slice = self.to_dense()[key]
        elif isinstance(key, slice):
            if key == slice(None):
                # to ensure arr[:] (used by view()) does not make a copy
                result = type(self)._simple_new(
                    self.sp_values, self.sp_index, self.dtype
                )
                result._readonly = self._readonly
                return result
            # Avoid densifying when handling contiguous slices
            if key.step is None or key.step == 1:
                start = 0 if key.start is None else key.start
                if start < 0:
                    start += len(self)

                end = len(self) if key.stop is None else key.stop
                if end < 0:
                    end += len(self)

                indices = self.sp_index.indices
                keep_inds = np.flatnonzero((indices >= start) & (indices < end))
                sp_vals = self.sp_values[keep_inds]

                sp_index = indices[keep_inds].copy()

                # If we've sliced to not include the start of the array, all our indices
                # should be shifted. NB: here we are careful to also not shift by a
                # negative value for a case like [0, 1][-100:] where the start index
                # should be treated like 0
                if start > 0:
                    sp_index -= start

                # Length of our result should match applying this slice to a range
                # of the length of our original array
                new_len = len(range(len(self))[key])
                new_sp_index = make_sparse_index(new_len, sp_index, self.kind)
                return type(self)._simple_new(sp_vals, new_sp_index, self.dtype)
            else:
                indices = np.arange(len(self), dtype=np.int32)[key]
                return self.take(indices)

        elif not is_list_like(key):
            # e.g. "foo" or 2.5
            # exception message copied from numpy
            raise IndexError(
                r"only integers, slices (`:`), ellipsis (`...`), numpy.newaxis "
                r"(`None`) and integer or boolean arrays are valid indices"
            )

        else:
            if isinstance(key, SparseArray):
                if is_bool_dtype(key):
                    if len(key) != len(self):
                        # the fast path below skips check_array_indexer, which
                        #  would raise here
                        raise IndexError(
                            f"Boolean index has wrong length: "
                            f"{len(key)} instead of {len(self)}"
                        )
                    # GH#45284 a stored value may equal the fill value, so select
                    #  on sp_values rather than on which positions are stored
                    if isna(key.fill_value) or not key.fill_value:
                        return self.take(key.sp_index.indices[key.sp_values])
                    mask = np.full(len(self), True, dtype=np.bool_)
                    mask[key.sp_index.indices] = key.sp_values
                    return self.take(np.flatnonzero(mask))
                else:
                    key = np.asarray(key)

            key = check_array_indexer(self, key)

            if com.is_bool_indexer(key):
                # mypy doesn't know we have an array here
                key = cast("np.ndarray", key)
                return self.take(np.arange(len(key), dtype=np.int32)[key])
            elif hasattr(key, "__len__"):
                return self.take(key)
            else:
                raise ValueError(f"Cannot slice with '{key}'")

        return type(self)(data_slice, kind=self.kind)

    def _get_val_at(self, loc):
        n = len(self)
        if loc < 0:
            loc += n

        if loc >= n or loc < 0:
            raise IndexError(
                f"index is out of bounds: must be an integer between -{n} and {n - 1}"
            )

        sp_loc = self.sp_index.lookup(loc)
        if sp_loc == -1:
            return self.fill_value
        else:
            val = self.sp_values[sp_loc]
            val = maybe_box_datetimelike(val, self.sp_values.dtype)
            return val

    def take(self, indices, *, allow_fill: bool = False, fill_value=None) -> Self:
        if is_scalar(indices):
            raise ValueError(f"'indices' must be an array, not a scalar '{indices}'.")
        indices = np.asarray(indices, dtype=np.int32)

        dtype = None
        if indices.size == 0:
            result = np.array([], dtype="object")
            dtype = self.dtype
        elif allow_fill:
            result = self._take_with_fill(indices, fill_value=fill_value)
        else:
            return self._take_without_fill(indices)

        return type(self)(
            result, fill_value=self.fill_value, kind=self.kind, dtype=dtype
        )

    def _take_with_fill(self, indices, fill_value=None) -> np.ndarray:
        if fill_value is None:
            fill_value = self.dtype.na_value

        if indices.min() < -1:
            raise ValueError(
                "Invalid value in 'indices'. Must be between -1 "
                "and the length of the array."
            )

        if indices.max() >= len(self):
            raise IndexError("out of bounds value in 'indices'.")

        if len(self) == 0:
            # Empty... Allow taking only if all empty
            if (indices == -1).all():
                dtype, new_fill = _promote_for_fill(self.sp_values.dtype, fill_value)
                taken = np.empty_like(indices, dtype=dtype)
                taken.fill(new_fill)
                return taken
            else:
                raise IndexError("cannot do a non-empty take from an empty axes.")

        # sp_indexer may be -1 for two reasons
        # 1.) we took for an index of -1 (new)
        # 2.) we took a value that was self.fill_value (old)
        sp_indexer = self.sp_index.lookup_array(indices)
        new_fill_indices = indices == -1
        old_fill_indices = (sp_indexer == -1) & ~new_fill_indices

        if self.sp_index.npoints == 0 and old_fill_indices.all():
            # We've looked up all valid points on an all-sparse array.
            _dtype, old_fill = _promote_for_fill(self.dtype.subtype, self.fill_value)
            taken = np.full(sp_indexer.shape, old_fill, dtype=_dtype)

        elif self.sp_index.npoints == 0:
            # Use the old fill_value unless we took for an index of -1
            _dtype, new_fill = _promote_for_fill(self.dtype.subtype, fill_value)
            _dtype, old_fill = _promote_for_fill(_dtype, self.fill_value)
            taken = np.full(sp_indexer.shape, new_fill, dtype=_dtype)
            taken[old_fill_indices] = old_fill
        else:
            taken = self.sp_values.take(sp_indexer)

            # Fill in two steps.
            # Old fill values
            # New fill values
            # potentially coercing to a new dtype at each stage.

            m0 = sp_indexer[old_fill_indices] < 0
            m1 = sp_indexer[new_fill_indices] < 0

            result_type = taken.dtype

            if m0.any():
                result_type, old_fill = _promote_for_fill(result_type, self.fill_value)
                taken = taken.astype(result_type, copy=False)
                taken[old_fill_indices] = old_fill

            if m1.any():
                result_type, new_fill = _promote_for_fill(result_type, fill_value)
                taken = taken.astype(result_type, copy=False)
                taken[new_fill_indices] = new_fill

        return taken

    def _take_without_fill(self, indices) -> Self:
        to_shift = indices < 0

        n = len(self)

        if (indices.max() >= n) or (indices.min() < -n):
            if n == 0:
                raise IndexError("cannot do a non-empty take from an empty axes.")
            raise IndexError("out of bounds value in 'indices'.")

        if to_shift.any():
            indices = indices.copy()
            indices[to_shift] += n

        sp_indexer = self.sp_index.lookup_array(indices)
        value_mask = sp_indexer != -1
        new_sp_values = self.sp_values[sp_indexer[value_mask]]

        value_indices = np.flatnonzero(value_mask).astype(np.int32, copy=False)

        new_sp_index = make_sparse_index(len(indices), value_indices, kind=self.kind)
        return type(self)._simple_new(new_sp_values, new_sp_index, dtype=self.dtype)

    def searchsorted(
        self,
        v: ArrayLike | object,
        side: Literal["left", "right"] = "left",
        sorter: NumpySorter | None = None,
    ) -> npt.NDArray[np.intp] | np.intp:
        if config["mode"]["performance_warnings"]:
            msg = "searchsorted requires high memory usage."
            warnings.warn(msg, PerformanceWarning, stacklevel=find_stack_level())
        v = np.asarray(v)
        return np.asarray(self, dtype=self.dtype.subtype).searchsorted(v, side, sorter)

    def copy(self) -> Self:
        values = self.sp_values.copy()
        return self._simple_new(values, self.sp_index, self.dtype)

    @classmethod
    def _concat_same_type(cls, to_concat: Sequence[Self]) -> Self:
        fill_value = to_concat[0].fill_value

        values = []
        length = 0

        if to_concat:
            sp_kind = to_concat[0].kind
        else:
            sp_kind = "integer"

        sp_index: SparseIndex
        if sp_kind == "integer":
            indices = []

            for arr in to_concat:
                int_idx = arr.sp_index.indices.copy()
                int_idx += length  # TODO: wraparound
                length += arr.sp_index.length

                values.append(arr.sp_values)
                indices.append(int_idx)

            data = np.concatenate(values)
            indices_arr = np.concatenate(indices)
            sp_index = IntIndex(length, indices_arr)

        else:
            # when concatenating block indices, we don't claim that you'll
            # get an identical index as concatenating the values and then
            # creating a new index. We don't want to spend the time trying
            # to merge blocks across arrays in `to_concat`, so the resulting
            # BlockIndex may have more blocks.
            blengths = []
            blocs = []

            for arr in to_concat:
                block_idx = arr.sp_index.to_block_index()

                values.append(arr.sp_values)
                blocs.append(block_idx.blocs.copy() + length)
                blengths.append(block_idx.blengths)
                length += arr.sp_index.length

            data = np.concatenate(values)
            blocs_arr = np.concatenate(blocs)
            blengths_arr = np.concatenate(blengths)

            sp_index = BlockIndex(length, blocs_arr, blengths_arr)

        sparse_dtype = SparseDtype(data.dtype, fill_value)
        return cls._simple_new(data, sp_index, sparse_dtype)

    def insert(self, loc: int, item) -> Self:
        if not is_valid_na_for_dtype(item, self.dtype):
            # GH#69028 our _from_sequence casts to the subtype instead of
            #  raising, so validate here; Index.insert widens on the raise
            if not _can_hold_for_fill(self.dtype.subtype, item):
                raise TypeError(f"Invalid value '{item!s}' for dtype '{self.dtype}'")
        return super().insert(loc, item)

    def astype(self, dtype: AstypeArg | None = None, copy: bool = True):
        """
        Change the dtype of a SparseArray.

        Parameters
        ----------
        dtype : np.dtype or ExtensionDtype
            For SparseDtype, this changes the subtype and the
            ``fill_value``, preserving the values.

            For any other dtype, the array is densified and cast to it.

        copy : bool, default True
            Whether to ensure a copy is made, even if not necessary.

        Returns
        -------
        np.ndarray or pandas.api.extensions.ExtensionArray
            A SparseArray for a SparseDtype, another ExtensionArray for any
            other ExtensionDtype, otherwise a dense ndarray of ``dtype``.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([0, 0, 1, 2])
        >>> arr
        <SparseArray>
        [0, 0, 1, 2]
        Length: 4, dtype: Sparse[int64, 0]

        >>> arr.astype(pd.SparseDtype(np.dtype("int32")))
        <SparseArray>
        [0, 0, 1, 2]
        Length: 4, dtype: Sparse[int32, 0]

        Changing the subtype can change the fill value too -- here ``0``
        becomes ``nan``, the default for ``float64``. The values are never
        changed to match a new fill value, so a fill value absent from the
        data leaves nothing to compress.

        >>> arr.astype(pd.SparseDtype(np.dtype("float64")))
        <SparseArray>
        [0.0, 0.0, 1.0, 2.0]
        Length: 4, dtype: Sparse[float64, nan]

        >>> arr.astype(pd.SparseDtype("float64", fill_value=0.0))
        <SparseArray>
        [0.0, 0.0, 1.0, 2.0]
        Length: 4, dtype: Sparse[float64, 0.0]
        """
        if dtype == self._dtype:
            if not copy:
                return self
            else:
                return self.copy()

        future_dtype = pandas_dtype(dtype)
        if not isinstance(future_dtype, SparseDtype):
            # GH#34457
            values = self._densify()
            values = ensure_wrapped_if_datetimelike(values)
            return astype_array(values, dtype=future_dtype, copy=False)

        dtype = self.dtype.update_dtype(dtype)

        # GH#49631: update_dtype resolves the target to the subtype's default
        # fill_value (e.g. 0 for int64) instead of converting the source
        # fill_value. Only fire when the target fill is the subtype default, so
        # an explicitly-requested non-default fill_value is respected.
        if (
            not dtype._is_na_fill_value
            and self.dtype.subtype.kind in "mM"
            and dtype.fill_value == na_value_for_dtype(dtype.subtype)
        ):
            # build from the source subtype so a boxed fill value converts too
            fv_arr = ensure_wrapped_if_datetimelike(np.zeros(1, self.dtype.subtype))
            fv_arr[0] = self.fill_value
            converted_fv = np.asarray(astype_array(fv_arr, dtype.subtype))
            dtype = SparseDtype(dtype.subtype, fill_value=converted_fv[0])
            # dtype.fill_value is now the converted self.fill_value, so the gaps
            # keep their value and the check below would only cost a densify
            converted_fill = True
        else:
            converted_fill = False

        subtype = pandas_dtype(dtype._subtype_with_str)
        subtype = cast("np.dtype", subtype)  # ensured by update_dtype

        if not converted_fill and not self._fill_value_matches(
            dtype.fill_value, subtype
        ):
            # GH#35795 the gaps hold self.fill_value, so keeping sp_index while
            # adopting a different fill_value would silently change those values
            values = ensure_wrapped_if_datetimelike(self._densify())
            values = np.asarray(astype_array(values, subtype, copy=False))
            return type(self)(values, kind=self.kind, dtype=dtype)

        values = ensure_wrapped_if_datetimelike(self.sp_values)
        sp_values = astype_array(values, subtype, copy=copy)
        sp_values = np.asarray(sp_values)

        return self._simple_new(sp_values, self.sp_index, dtype)

    def _fill_value_matches(self, fill_value, subtype) -> bool:
        """Whether fill_value is the value the gaps already hold under subtype."""
        if isna(self.fill_value) or isna(fill_value):
            return bool(isna(self.fill_value) and isna(fill_value))
        if is_object_dtype(self.dtype.subtype) or is_object_dtype(subtype):
            # _make_sparse tells 0, 0.0 and False apart for object data, so this
            # has to as well, see make_mask_object_ndarray
            return type(self.fill_value) is type(fill_value) and bool(
                self.fill_value == fill_value
            )
        return bool(self.fill_value == fill_value)

    def map(self, mapper, na_action: Literal["ignore"] | None = None) -> Self:
        """
        Map categories using an input mapping or function.

        Parameters
        ----------
        mapper : dict, Series, callable
            The correspondence from old values to new.
        na_action : {None, 'ignore'}, default None
            If 'ignore', propagate NA values, without passing them to the
            mapping correspondence.

        Returns
        -------
        SparseArray
            The output array will have the same density as the input.
            The output fill value will be the result of applying the
            mapping to ``self.fill_value``

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([0, 1, 2])
        >>> arr.map(lambda x: x + 10)
        <SparseArray>
        [10, 11, 12]
        Length: 3, dtype: Sparse[int64, 10]

        >>> arr.map({0: 10, 1: 11, 2: 12})
        <SparseArray>
        [10, 11, 12]
        Length: 3, dtype: Sparse[int64, 10]

        >>> arr.map(pd.Series([10, 11, 12], index=[0, 1, 2]))
        <SparseArray>
        [10, 11, 12]
        Length: 3, dtype: Sparse[int64, 10]
        """
        is_map = isinstance(mapper, (abc.Mapping, ABCSeries))

        fill_val = self.fill_value

        if na_action is None or notna(fill_val):
            fill_val = mapper.get(fill_val, fill_val) if is_map else mapper(fill_val)

        def func(sp_val):
            new_sp_val = mapper.get(sp_val, None) if is_map else mapper(sp_val)
            # check identity as well as equality because NA values are not equal to
            #  each other, and GH#68586 comparing a stored one gives a non-bool.
            #  is_scalar first: isna on a list-valued mapper result is not a bool
            if new_sp_val is fill_val or (
                not (is_scalar(new_sp_val) and isna(new_sp_val))
                and new_sp_val == fill_val
            ):
                msg = "fill value in the sparse values not supported"
                raise ValueError(msg)
            return new_sp_val

        sp_values = np.asarray(
            sanitize_array([func(x) for x in self.sp_values], index=None)
        )

        sparse_dtype = SparseDtype(sp_values.dtype, fill_val)
        return type(self)._simple_new(sp_values, self.sp_index, sparse_dtype)

    def _groupby_op(
        self,
        *,
        how: str,
        has_dropped_na: bool,
        min_count: int,
        ngroups: int,
        ids: npt.NDArray[np.intp],
        **kwargs,
    ):
        # first/last are handled by the base class to preserve EA type
        if how in ["first", "last"]:
            return self._groupby_first_last(
                how=how,
                min_count=min_count,
                ngroups=ngroups,
                ids=ids,
                skipna=kwargs.get("skipna", True),
            )

        npvalues = self._densify()

        if npvalues.dtype.kind in "mM":
            # Defer to DatetimeArray/TimedeltaArray, which reject the
            #  operations that are invalid for their dtype.
            return ensure_wrapped_if_datetimelike(npvalues)._groupby_op(
                how=how,
                has_dropped_na=has_dropped_na,
                min_count=min_count,
                ngroups=ngroups,
                ids=ids,
                **kwargs,
            )

        from pandas.core.groupby.ops import WrappedCythonOp

        op = WrappedCythonOp(how=how, has_dropped_na=has_dropped_na)

        res_values = op._cython_op_ndim_compat(
            npvalues,
            min_count=min_count,
            ngroups=ngroups,
            comp_ids=ids,
            mask=None,
            **kwargs,
        )

        return res_values

    def to_dense(self) -> np.ndarray:
        """
        Convert SparseArray to a NumPy array.

        Returns
        -------
        arr : NumPy array
        """
        return np.asarray(self, dtype=self.sp_values.dtype)

    def _densify(self) -> np.ndarray:
        """
        Dense values, keeping the dense dtype the subtype would have.

        ``to_dense`` is no good for this because it casts the fill_value to the
        subtype, turning the NAs of a ``Sparse[int64, nan]`` into 0s; ``np.asarray``
        is no good either because it promotes on ``type(fill_value)`` and so widens
        e.g. ``Sparse[uint64]`` to float64.

        With no gaps this is ``sp_values`` itself (or a read-only view of it), not
        a copy, so callers must not write to the result.
        """
        if self.sp_index.ngaps == 0:
            result = self.sp_values
            if self._readonly:
                result = result.view()
                result.flags.writeable = False
            return result

        npdtype = self.sp_values.dtype
        fill_value = self.fill_value
        if isna(fill_value):
            # SparseDtype._check_fill_value guarantees that a non-NA
            #  fill_value fits in the subtype, so only an NA needs promoting.
            npdtype, fill_value = maybe_promote(npdtype, fill_value)
        else:
            fill_value = _unbox_for_fill(npdtype, fill_value)
        npvalues = np.full(self.shape, fill_value, dtype=npdtype)
        npvalues[self.sp_index.indices] = self.sp_values
        return npvalues

    def _where(self, mask, value):
        # NB: may not preserve dtype, e.g. result may be Sparse[float64]
        #  while self is Sparse[int64]
        naive_implementation = np.where(mask, self, value)
        dtype = SparseDtype(naive_implementation.dtype, fill_value=self.fill_value)
        result = type(self)._from_sequence(naive_implementation, dtype=dtype)
        return result

    # ------------------------------------------------------------------------
    # IO
    # ------------------------------------------------------------------------
    def __setstate__(self, state) -> None:
        """Necessary for making this object picklable"""
        if isinstance(state, tuple):
            # Compat for pandas < 0.24.0
            nd_state, (fill_value, sp_index) = state
            sparse_values = np.array([])
            sparse_values.__setstate__(nd_state)

            self._sparse_values = sparse_values
            self._sparse_index = sp_index
            self._dtype = SparseDtype(sparse_values.dtype, fill_value)
        else:
            self.__dict__.update(state)

    def nonzero(self) -> tuple[npt.NDArray[np.int32]]:
        if self.fill_value == 0:
            return (self.sp_index.indices,)
        else:
            return (self.sp_index.indices[self.sp_values != 0],)

    # ------------------------------------------------------------------------
    # Reductions
    # ------------------------------------------------------------------------

    def _reduce(
        self, name: str, *, skipna: bool = True, keepdims: bool = False, **kwargs
    ):
        method = getattr(self, name, None)

        if method is None:
            raise TypeError(f"cannot perform {name} with type {self.dtype}")

        if name in _skipna_aware_reductions:
            # these methods handle skipna themselves; dropping NAs beforehand
            # would hide the NA from their skipna=False short-circuit
            result = method(skipna=skipna, **kwargs)
        else:
            if skipna:
                arr = self
            else:
                arr = self.dropna()
            result = getattr(arr, name)(**kwargs)

        if keepdims:
            dtype = self.dtype
            result_dtype = np.asarray(result).dtype
            if name in _positional_reductions:
                # intp over result_dtype, which varies with which branch of
                # _argmin_argmax answered.  See test_frame_idxmin_idxmax
                dtype = SparseDtype(np.intp)
            elif name in _boolean_reductions:
                # see test_any_all_keepdims_is_boolean
                dtype = SparseDtype(bool)
            elif name in _complex_to_real_reductions and dtype.subtype.kind == "c":
                # np.result_type below would widen the real result straight back to
                # complex, and a complex fill value has no real counterpart. Gated on
                # the reduction, not the result dtype; see
                # test_frame_complex_reduction_na_keeps_complex
                dtype = SparseDtype(result_dtype)
            elif dtype.subtype.kind in "biufc":
                # The reduction is not always closed over self.dtype, e.g. the
                # mean of an integer column, the sum of a narrow one, or the
                # NaN that min_count inserts; casting the result back to
                # self.dtype would silently truncate it.
                subtype = np.result_type(dtype.subtype, result)
                if subtype != dtype.subtype:
                    fill_value = self.fill_value
                    if notna(fill_value):
                        # keep the fill value so that reducing a frame of
                        # sparse columns does not mix fill values
                        fill_value = subtype.type(fill_value).item()
                    dtype = SparseDtype(subtype, fill_value)
            elif dtype.subtype.kind in "mM" and (
                result is NaT or isinstance(result, (Timestamp, Timedelta))
            ):
                # datetimelike reductions are closed over the subtype except std,
                # which turns a datetime64 column into a timedelta64 one. Go by
                # the reduction, not the result: a boxed result no longer says which.
                if dtype.subtype.kind == "M" and name in _complex_to_real_reductions:
                    unit = np.datetime_data(dtype.subtype)[0]
                    dtype = SparseDtype(np.dtype(f"m8[{unit}]"))
                if result is NaT:
                    # a boxed NaT is inferred as datetime64, so a timedelta64
                    # subtype needs the numpy NaT back
                    result = na_value_for_dtype(dtype.subtype, compat=False)
            return type(self)([result], dtype=dtype)
        else:
            return result

    @property
    def _na_scalar(self) -> Scalar:
        """
        The NA a reduction returns, boxed as NaT for a datetimelike subtype.
        """
        return maybe_box_datetimelike(
            na_value_for_dtype(self.dtype.subtype, compat=False), self.dtype.subtype
        )

    def _dense_reduce(self, name: str, *, skipna: bool, **kwargs):
        """
        Compute a reduction that has no sparse-aware kernel on the dense values.
        """
        result = getattr(nanops, f"nan{name}")(self._densify(), skipna=skipna, **kwargs)
        return maybe_box_datetimelike(result, self.dtype.subtype)

    def all(self, axis=None, *args, skipna: bool = True, **kwargs) -> bool:
        """
        Tests whether all elements evaluate True

        Parameters
        ----------
        axis : int, default None
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False, NA is evaluated for truthiness
            like any other value.
        *args, **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        all : bool

        See Also
        --------
        numpy.all
        """
        nv.validate_all(args, kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")

        if self.dtype.subtype.kind == "M":
            # GH#34479: match nanops.nanall on the dense values
            raise TypeError(dt64_any_all_msg("all"))

        values = self.sp_values
        fill_value = self.fill_value
        if skipna:
            # NaN and NaT are truthy, which is already what skipping them means for
            #  all() (see nanops.nanall); only a falsy object None needs the mask
            if values.dtype.kind == "O":
                values = self._valid_sp_values
            if isna(fill_value):
                fill_value = True
        elif isna(fill_value):
            # gaps count as what _densify puts there: the promoted NA. NaN and NaT
            #  are truthy; a pd.NA survives the promotion and raises like dense
            fill_value = maybe_promote(self.sp_values.dtype, fill_value)[1]

        # not np.all(): an object pd.NA fill then raises like dense; see
        #  test_any_all_na_fill_value
        if self.sp_index.ngaps > 0 and not fill_value:
            return False

        return values.all().item()

    def any(self, axis: AxisInt = 0, *args, skipna: bool = True, **kwargs) -> bool:
        """
        Tests whether at least one of elements evaluate True

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False, NA is evaluated for truthiness
            like any other value.
        *args, **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        any : bool

        See Also
        --------
        numpy.any
        """
        nv.validate_any(args, kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")

        if self.dtype.subtype.kind == "M":
            # GH#34479: match nanops.nanany on the dense values
            raise TypeError(dt64_any_all_msg("any"))

        values = self.sp_values
        fill_value = self.fill_value
        if skipna:
            # unlike all(), a truthy NaN does change the answer (see nanops.nanany),
            #  so every subtype that can hold NA needs the mask
            if values.dtype.kind not in "biu":
                values = self._valid_sp_values
            if isna(fill_value):
                fill_value = False
        elif isna(fill_value):
            # see the fill-value note in all()
            fill_value = maybe_promote(self.sp_values.dtype, fill_value)[1]

        # not np.any(); see the note in all()
        if self.sp_index.ngaps > 0 and fill_value:
            return True

        return values.any().item()

    def sum(
        self,
        axis: AxisInt = 0,
        min_count: int = 0,
        skipna: bool = True,
        *args,
        **kwargs,
    ) -> Scalar:
        """
        Sum of non-NA/null values

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        min_count : int, default 0
            The required number of valid values to perform the summation. If fewer
            than ``min_count`` valid values are present, the result will be the missing
            value indicator for subarray type.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        *args, **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar
        """
        nv.validate_sum(args, kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")

        if self.dtype.subtype.kind == "O" and not self._null_fill_value:
            # the fill_value * nsparse adjustment below assumes a commutative +,
            #  which str and bytes do not have; an NA fill is skipped, not added,
            #  so it needs none.  See test_sum_object_fill_value.
            return self._dense_reduce("sum", skipna=skipna, min_count=min_count)

        valid_vals = self._valid_sp_values
        sp_sum = valid_vals.sum()

        if not skipna and self._hasna:
            return self._na_scalar

        if self._null_fill_value:
            if check_below_min_count(valid_vals.shape, None, min_count):
                return self._na_scalar
            result = sp_sum
        else:
            nsparse = self.sp_index.ngaps
            if check_below_min_count(valid_vals.shape, None, min_count - nsparse):
                return self._na_scalar
            result = sp_sum + self.fill_value * nsparse
        return maybe_box_datetimelike(result, self.dtype.subtype)

    def _accumulate(self, name: str, *, skipna: bool = True, **kwargs) -> SparseArray:
        accum_func = {
            "cumsum": np.cumsum,
            "cumprod": np.cumprod,
            "cummin": np.minimum.accumulate,
            "cummax": np.maximum.accumulate,
        }.get(name)
        if accum_func is None:
            raise NotImplementedError(f"cannot perform {name} with type {self.dtype}")

        if name == "cumsum" and skipna and self.dtype.subtype.kind in "biufc":
            # numeric cumsum keeps the NA gaps as gaps instead of densifying;
            # other subtypes go dense to match its NA handling
            return self.cumsum(**kwargs)

        result: ExtensionArray | np.ndarray
        values = ensure_wrapped_if_datetimelike(self._densify())
        if isinstance(values, ExtensionArray):
            # datetimelike subtypes have their own accumulations
            result = values._accumulate(name, skipna=skipna, **kwargs)
        else:
            result = na_accum_func(values, accum_func, skipna=skipna)

        # like cumsum, the result's fill value is NA regardless of our own
        fill_value = na_value_for_dtype(result.dtype, compat=False)
        return type(self)(result, fill_value=fill_value)

    def prod(
        self,
        *,
        axis: AxisInt = 0,
        min_count: int = 0,
        skipna: bool = True,
        **kwargs,
    ) -> Scalar:
        """
        Product of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        min_count : int, default 0
            The required number of valid values to perform the multiplication. If
            fewer than ``min_count`` valid values are present, the result will be
            the missing value indicator for subarray type.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        SparseArray.sum : Sum of non-NA/null values.
        numpy.prod : Product of array elements over a given axis.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3])
        >>> arr.prod()
        np.int64(6)
        """
        nv.validate_prod((), kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("prod", skipna=skipna, min_count=min_count)

    def cumsum(self, axis: AxisInt = 0, *args, **kwargs) -> SparseArray:
        """
        Cumulative sum of non-NA/null values.

        When performing the cumulative summation, any non-NA/null values will
        be skipped. The resulting SparseArray will preserve the locations of
        NaN values, but the fill value will be `np.nan` regardless.

        Parameters
        ----------
        axis : int or None
            Axis over which to perform the cumulative summation. If None,
            perform cumulative summation over flattened array.

        Returns
        -------
        cumsum : SparseArray
        """
        nv.validate_cumsum(args, kwargs)

        if axis is not None and axis >= self.ndim:  # Mimic ndarray behaviour.
            raise ValueError(f"axis(={axis}) out of bounds")

        if not self._null_fill_value:
            return SparseArray(self.to_dense(), fill_value=np.nan).cumsum()

        sp_values = self.sp_values
        mask = isna(sp_values)
        if not mask.any():
            result = sp_values.cumsum()
        else:
            # a stored NA would otherwise propagate into every later entry,
            # see GH#68972
            filled = sp_values.copy()
            filled[mask] = 0
            result = filled.cumsum()
            # the dtype's own NA, not the stored object: nanops.na_accum_func
            # drops an imaginary-only NaN's real part too
            result[mask] = na_value_for_dtype(sp_values.dtype, compat=False)

        sparse_dtype = SparseDtype(result.dtype, self.fill_value)
        return type(self)._simple_new(result, self.sp_index, sparse_dtype)

    def mean(self, axis: Axis = 0, *args, skipna: bool = True, **kwargs):
        """
        Mean of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        *args, **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar
        """
        nv.validate_mean(args, kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")
        valid_vals = self._valid_sp_values
        sp_sum = valid_vals.sum()
        ct = len(valid_vals)

        nsparse = 0 if self._null_fill_value else self.sp_index.ngaps
        nobs = ct + nsparse

        if not nobs:
            # nobs == 0 is exactly "every entry is NA", empty arrays included; the
            # division and the fill_value adjustment both warn or raise there (GH#68484)
            return self._na_scalar

        # Compute the reduction before the skipna=False NA short-circuit so
        # unsupported dtypes still raise during the operation validation.
        if self._null_fill_value:
            mean = sp_sum / nobs
        else:
            mean = (sp_sum + self.fill_value * nsparse) / nobs

        if not skipna and self._hasna:
            return self._na_scalar

        return maybe_box_datetimelike(mean, self.dtype.subtype)

    def median(
        self,
        *,
        axis: AxisInt = 0,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Median of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.median : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.median()
        2.5
        """
        nv.validate_median((), kwargs)
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("median", skipna=skipna)

    def var(
        self,
        *,
        axis: AxisInt = 0,
        ddof: int = 1,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Unbiased variance of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        ddof : int, default 1
            Delta degrees of freedom. The divisor used in calculations is
            ``N - ddof``, where ``N`` is the number of non-NA/null values.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.var : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.var()
        1.6666666666666667
        """
        nv.validate_stat_ddof_func((), kwargs, fname="var")
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("var", skipna=skipna, ddof=ddof)

    def std(
        self,
        *,
        axis: AxisInt = 0,
        ddof: int = 1,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Sample standard deviation of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        ddof : int, default 1
            Delta degrees of freedom. The divisor used in calculations is
            ``N - ddof``, where ``N`` is the number of non-NA/null values.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.std : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.std()
        1.2909944487358056
        """
        nv.validate_stat_ddof_func((), kwargs, fname="std")
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("std", skipna=skipna, ddof=ddof)

    def sem(
        self,
        *,
        axis: AxisInt = 0,
        ddof: int = 1,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Standard error of the mean of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        ddof : int, default 1
            Delta degrees of freedom. The divisor used in calculations is
            ``N - ddof``, where ``N`` is the number of non-NA/null values.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.sem : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.sem()
        np.float64(0.6454972243679028)
        """
        nv.validate_stat_ddof_func((), kwargs, fname="sem")
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("sem", skipna=skipna, ddof=ddof)

    def skew(
        self,
        *,
        axis: AxisInt = 0,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Unbiased skew of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.skew : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.skew()
        np.float64(0.0)
        """
        nv.validate_stat_ddof_func((), kwargs, fname="skew")
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("skew", skipna=skipna)

    def kurt(
        self,
        *,
        axis: AxisInt = 0,
        skipna: bool = True,
        **kwargs,
    ):
        """
        Unbiased kurtosis of non-NA/null values.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Exclude NA/null values. If False and NA is present, return NA.
        **kwargs
            Not Used. NumPy compatibility.

        Returns
        -------
        scalar

        See Also
        --------
        Series.kurt : Equivalent method for Series.

        Examples
        --------
        >>> arr = pd.arrays.SparseArray([1, 2, 3, 4])
        >>> arr.kurt()
        np.float64(-1.200000000000001)
        """
        nv.validate_stat_ddof_func((), kwargs, fname="kurt")
        skipna = validate_bool_kwarg(skipna, "skipna")
        return self._dense_reduce("kurt", skipna=skipna)

    def max(self, *, axis: AxisInt | None = None, skipna: bool = True):
        """
        Max of array values, ignoring NA values if specified.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Whether to ignore NA values.

        Returns
        -------
        scalar
        """
        nv.validate_minmax_axis(axis, self.ndim)
        return self._min_max("max", skipna=skipna)

    def min(self, *, axis: AxisInt | None = None, skipna: bool = True):
        """
        Min of array values, ignoring NA values if specified.

        Parameters
        ----------
        axis : int, default 0
            Not Used. NumPy compatibility.
        skipna : bool, default True
            Whether to ignore NA values.

        Returns
        -------
        scalar
        """
        nv.validate_minmax_axis(axis, self.ndim)
        return self._min_max("min", skipna=skipna)

    def _min_max(self, kind: Literal["min", "max"], skipna: bool) -> Scalar:
        """
        Min/max of non-NA/null values

        Parameters
        ----------
        kind : {"min", "max"}
        skipna : bool

        Returns
        -------
        scalar
        """
        valid_vals = self._valid_sp_values
        has_nonnull_fill_vals = not self._null_fill_value and self.sp_index.ngaps > 0

        if len(valid_vals) > 0:
            sp_min_max = getattr(valid_vals, kind)()

            if not skipna and self._hasna:
                return self._na_scalar

            # If a non-null fill value is currently present, it might be the min/max
            if has_nonnull_fill_vals:
                func = max if kind == "max" else min
                result = func(sp_min_max, self.fill_value)
            else:
                # A present NA with skipna=False is handled above, so the min/max
                # of the valid sparse values is the result.
                result = sp_min_max
        elif not skipna and self._hasna:
            return self._na_scalar
        elif has_nonnull_fill_vals:
            result = self.fill_value
        else:
            return self._na_scalar
        return maybe_box_datetimelike(result, self.dtype.subtype)

    def _argmin_argmax(self, kind: Literal["argmin", "argmax"]) -> int:
        values = self._sparse_values
        index = self._sparse_index.indices
        mask = np.asarray(isna(values))
        func = np.argmax if kind == "argmax" else np.argmin

        idx = np.arange(values.shape[0])
        non_nans = values[~mask]
        non_nan_idx = idx[~mask]

        if len(non_nans) == 0 and not self._null_fill_value and self.sp_index.ngaps:
            # No stored value survives the mask, so the fill value is the only
            # candidate; if it is NA or holds no position, the all-NA check
            # below raises. GH#68462
            return self._first_fill_value_loc()

        if not len(non_nans) and len(self) and self.isna().all():
            # mask covers sp_values only, which is empty when every value is
            # an NA fill value, so the all-NA check has to look at the array
            raise ValueError("Encountered all NA values")

        _candidate = non_nan_idx[func(non_nans)]
        candidate = index[_candidate]

        if isna(self.fill_value):
            return candidate
        if kind == "argmin" and self[candidate] < self.fill_value:
            return candidate
        if kind == "argmax" and self[candidate] > self.fill_value:
            return candidate
        _loc = self._first_fill_value_loc()
        if _loc == -1:
            # fill_value doesn't exist
            return candidate
        else:
            return _loc

    def argmax(self, skipna: bool = True) -> int:
        validate_bool_kwarg(skipna, "skipna")
        if not skipna and self._hasna:
            raise ValueError("Encountered an NA value with skipna=False")
        return self._argmin_argmax("argmax")

    def argmin(self, skipna: bool = True) -> int:
        validate_bool_kwarg(skipna, "skipna")
        if not skipna and self._hasna:
            raise ValueError("Encountered an NA value with skipna=False")
        return self._argmin_argmax("argmin")

    # ------------------------------------------------------------------------
    # Ufuncs
    # ------------------------------------------------------------------------

    _HANDLED_TYPES = (np.ndarray, numbers.Number)

    def __array_ufunc__(self, ufunc: np.ufunc, method: str, *inputs, **kwargs):
        # this path never reaches ExtensionArray.__array_ufunc__, and a datetimelike
        #  scalar is not in _HANDLED_TYPES, so this has to precede that loop
        ops.disallow_datetimelike_logical_ufunc(ufunc, inputs)

        out = kwargs.get("out", ())

        for x in inputs + out:
            if not isinstance(x, (*self._HANDLED_TYPES, SparseArray)):
                return NotImplemented

        # for binary ops, use our custom dunder methods
        result = arraylike.maybe_dispatch_ufunc_to_dunder_op(
            self, ufunc, method, *inputs, **kwargs
        )
        if result is not NotImplemented:
            return result

        if "out" in kwargs:
            # e.g. tests.arrays.sparse.test_arithmetics.test_ndarray_inplace
            res = arraylike.dispatch_ufunc_with_out(
                self, ufunc, method, *inputs, **kwargs
            )
            return res

        if method == "reduce":
            result = arraylike.dispatch_reduction_ufunc(
                self, ufunc, method, *inputs, **kwargs
            )
            if result is not NotImplemented:
                # e.g. tests.series.test_ufunc.TestNumpyReductions
                return result

        if len(inputs) == 1:
            if method == "reduce":
                # GH#68453 reducing sp_values alone would drop the gaps
                return ufunc.reduce(self._densify(), **kwargs)

            if method == "accumulate":
                # GH#68566 numpy cannot accumulate the scalar fill_value; like
                #  _accumulate, the densified result's fill value is NA regardless
                result = ufunc.accumulate(self._densify(), **kwargs)
                fill_value = na_value_for_dtype(result.dtype, compat=False)
                return type(self)(result, fill_value=fill_value)

            # No alignment necessary.
            sp_values = getattr(ufunc, method)(self.sp_values, **kwargs)
            fill_value = getattr(ufunc, method)(self.fill_value, **kwargs)

            if ufunc.nout > 1:
                # multiple outputs. e.g. modf
                arrays = tuple(
                    self._simple_new(
                        sp_value, self.sp_index, SparseDtype(sp_value.dtype, fv)
                    )
                    for sp_value, fv in zip(sp_values, fill_value, strict=True)
                )
                return arrays

            return self._simple_new(
                sp_values, self.sp_index, SparseDtype(sp_values.dtype, fill_value)
            )

        new_inputs = tuple(np.asarray(x) for x in inputs)
        result = getattr(ufunc, method)(*new_inputs, **kwargs)
        if out:
            if len(out) == 1:
                out = out[0]
            return out

        if ufunc.nout > 1:
            return tuple(type(self)(x) for x in result)
        elif method == "at":
            # no return value
            return None
        else:
            return type(self)(result)

    # ------------------------------------------------------------------------
    # Ops
    # ------------------------------------------------------------------------

    def _arith_method(self, other, op):
        op_name = op.__name__

        if isinstance(other, SparseArray):
            return _sparse_array_op(self, other, op, op_name)

        elif is_scalar(other):
            with np.errstate(all="ignore"):
                fill = op(_get_fill(self), np.asarray(other))
                result = op(self.sp_values, other)

            if op_name == "divmod":
                left, right = result
                lfill, rfill = fill
                return (
                    _wrap_result(op_name, left, self.sp_index, lfill),
                    _wrap_result(op_name, right, self.sp_index, rfill),
                )

            return _wrap_result(op_name, result, self.sp_index, fill)

        else:
            if not isinstance(
                other, (list, np.ndarray, ExtensionArray)
            ) and not ops.has_castable_attr(other):
                warnings.warn(
                    f"Operation with {type(other).__name__} is deprecated. "
                    "In a future version these will be treated as scalar-like. "
                    "To retain the old behavior, explicitly wrap in a Series "
                    "instead.",
                    Pandas4Warning,
                    stacklevel=find_stack_level(),
                )

            other = np.asarray(other)
            with np.errstate(all="ignore"):
                if len(self) != len(other):
                    raise AssertionError(
                        f"length mismatch: {len(self)} vs. {len(other)}"
                    )
                if not isinstance(other, SparseArray):
                    dtype = getattr(other, "dtype", None)
                    other = _as_sparse_operand(other, self.fill_value, dtype=dtype)
                return _sparse_array_op(self, other, op, op_name)

    def _cmp_method(self, other, op) -> SparseArray:
        if isinstance(getattr(other, "dtype", None), BaseMaskedDtype):
            # GH#68579 defer to the masked operand's reflected comparison, which
            #  keeps its NA semantics; densifying here loses them.
            return NotImplemented

        return self._cmp_or_logical_op(other, op)

    def _cmp_or_logical_op(self, other, op) -> SparseArray:
        # Shared by _cmp_method and _logical_method's fast path.
        if (
            is_list_like(other)
            and not isinstance(other, (list, np.ndarray, ExtensionArray))
            and not ops.has_castable_attr(other)
        ):
            warnings.warn(
                f"Operation with {type(other).__name__} is deprecated. "
                "In a future version these will be treated as scalar-like. "
                "To retain the old behavior, explicitly wrap in a Series "
                "instead.",
                Pandas4Warning,
                stacklevel=find_stack_level(),
            )
        if not is_scalar(other) and not isinstance(other, type(self)):
            # convert list-like to ndarray
            other = np.asarray(other)

        if isinstance(other, np.ndarray):
            # TODO: make this more flexible than just ndarray...
            other = _as_sparse_operand(other, self.fill_value)

        op_name = op.__name__.strip("_")
        # _logical_method routes and/or/xor here for the sparse fast path, and the
        #  dense route below only knows the comparison operators
        is_cmp = op_name in ("eq", "ne", "lt", "gt", "le", "ge")

        if isinstance(other, SparseArray):
            if len(self) != len(other):
                raise ValueError(
                    f"operands have mismatched length {len(self)} and {len(other)}"
                )

            if is_cmp and object in (self.dtype.subtype, other.dtype.subtype):
                # GH#68586 _sparse_array_op casts both operands to their common
                #  subtype, so object on either side reaches a kernel splib lacks
                return self._cmp_method_dense(other.to_dense(), other.fill_value, op)

            return _sparse_array_op(self, other, op, op_name)
        elif other is libmissing.NA:
            # GH#68579 NA has no truth value, so the scalar arm below cannot
            #  build a boolean result; answer as the dense path does.
            fill_value = op is operator.ne
            if self.dtype.subtype.kind in "mM":
                result = ops.invalid_comparison(self, other, op)
            else:
                result = np.full(len(self), fill_value, dtype=np.bool_)
            return type(self)(result, fill_value=fill_value, dtype=np.bool_)
        elif is_cmp and self.dtype.subtype == object:
            # GH#68586 the np.bool_ buffer below cannot hold the result of comparing
            #  e.g. pd.NA, so use the kernel the dense path uses -- but only the
            #  stored values need it, so this stays O(nnz) rather than O(len)
            sp_values = ops.comparison_op(self.sp_values, other, op)
            fill_value = self._cmp_fill_value(other, op)
            return _wrap_result(op_name, sp_values, self.sp_index, fill_value)
        else:
            # scalar
            fill_value = op(self.fill_value, other)
            result = np.full(len(self), fill_value, dtype=np.bool_)
            result[self.sp_index.indices] = op(self.sp_values, other)

            return type(self)(
                result,
                fill_value=fill_value,
                dtype=np.bool_,
            )

    def _cmp_fill_value(self, other, op) -> bool:
        # GH#68586 through the object kernel so that an NA fill value compares
        #  False instead of making the bool() below raise
        return bool(
            ops.comparison_op(np.array([self.fill_value], dtype=object), other, op)[0]
        )

    def _cmp_method_dense(self, rvalues, rfill, op) -> SparseArray:
        # GH#68586 splib has no object comparison kernels, so an object subtype on
        #  either side is computed densely; unlike the scalar arm this cannot work
        #  off sp_values, because the two sparse indexes need not line up.
        result = ops.comparison_op(np.asarray(self), rvalues, op)
        return type(self)(
            result, fill_value=self._cmp_fill_value(rfill, op), dtype=np.bool_
        )

    def _logical_method(self, other, op):
        other_dtype = getattr(other, "dtype", None)
        if isinstance(other_dtype, BaseMaskedDtype) and other_dtype.kind == "b":
            # GH#68483 defer to the masked operand's reflected op, which keeps
            #  its Kleene NA semantics; densifying here loses them.
            #  Boolean only -- the other masked dtypes reach _arith_method,
            #  which cannot consume a SparseArray.
            return NotImplemented

        # GH#32119 the sparse fast path (see _sparse_array_op / splib) only
        #  implements and/or/xor for boolean and integer subtypes. When
        #  alignment upcasts an operand to object/float -- e.g. NA introduced
        #  by reindexing a boolean SparseArray to a longer index -- fall back
        #  to a dense computation so the result matches the non-sparse path.
        if not self._logical_needs_dense(other):
            return self._cmp_or_logical_op(other, op)

        lvalues = np.asarray(self)
        # GH#68569 keep an EA operand boxed so logical_op dispatches to it as the dense
        #  path does; densifying flattened e.g. a Categorical to object.
        rvalues = extract_array(other, extract_numpy=True)
        if isinstance(rvalues, SparseArray):
            # A sparse operand is the exception: dispatching would re-enter here with
            #  the two swapped, and logical_op treats its left and right differently
            #  -- see test_logical_op_both_sparse_matches_dense.
            rvalues = np.asarray(rvalues)
        result = logical_op(lvalues, rvalues, op)
        if not isinstance(result, np.ndarray):
            # GH#68569 the operand's own op answered in its dtype, as it does densely.
            #  Re-wrapping a nullable result as sparse would give it an NA fill value
            #  that later logical ops raise on.
            return result
        return type(self)(result)

    def _logical_needs_dense(self, other) -> bool:
        # The and/or/xor sparse kernels only support boolean/integer subtypes;
        #  everything else (object/float produced by NA upcasting) must be
        #  computed densely. Inspect dtypes without materializing so the fast
        #  path still receives the original operand (and its warnings).
        if self.dtype.subtype.kind not in "biu":
            return True
        other_dtype = getattr(other, "dtype", None)
        if other_dtype is None:
            # scalar or a dtype-less sequence (e.g. list); the fast path
            #  handles these, including raising on length mismatch
            return False
        if isinstance(other_dtype, SparseDtype):
            return other_dtype.subtype.kind not in "biu"
        return other_dtype.kind not in "biu"

    def _unary_method(self, op) -> SparseArray:
        fill_value = op(np.array(self.fill_value)).item()
        dtype = SparseDtype(self.dtype.subtype, fill_value)
        # NOTE: if fill_value doesn't change
        # we just have to apply op to sp_values
        if isna(self.fill_value) or fill_value == self.fill_value:
            values = op(self.sp_values)
            return type(self)._simple_new(values, self.sp_index, self.dtype)
        # In the other case we have to recalc indexes
        return type(self)(op(self.to_dense()), dtype=dtype)

    def __pos__(self) -> SparseArray:
        return self._unary_method(operator.pos)

    def __neg__(self) -> SparseArray:
        return self._unary_method(operator.neg)

    def __invert__(self) -> SparseArray:
        return self._unary_method(operator.invert)

    def __abs__(self) -> SparseArray:
        return self._unary_method(operator.abs)

    # ----------
    # Formatting
    # -----------
    # PandasObject (via OpsMixin) comes before ExtensionArray in the MRO,
    # and PandasObject.__repr__ falls back to object.__repr__. Explicitly
    # resolve to the ExtensionArray version.
    __repr__ = ExtensionArray.__repr__

    def _formatter(self, boxed: bool = False) -> Callable[[Any], str | None]:
        # Use str to avoid np.int64(...) wrapping in repr output.
        return str


def _make_sparse(
    arr: np.ndarray,
    kind: SparseIndexKind = "block",
    fill_value=None,
    dtype: np.dtype | None = None,
):
    """
    Convert ndarray to sparse format

    Parameters
    ----------
    arr : ndarray
    kind : {'block', 'integer'}
    fill_value : NaN or another value
    dtype : np.dtype, optional

    Returns
    -------
    (sparse_values, index, fill_value) : (ndarray, SparseIndex, Scalar)
    """
    assert isinstance(arr, np.ndarray)

    if arr.ndim > 1:
        raise TypeError("expected dimension <= 1 data")

    if fill_value is None:
        fill_value = na_value_for_dtype(arr.dtype)

    if isna(fill_value):
        mask = notna(arr)
    else:
        # cast to object comparison to be safe
        if is_string_dtype(arr.dtype):
            arr = arr.astype(object)

        if is_object_dtype(arr.dtype):
            # element-wise equality check method in numpy doesn't treat
            # each element type, eg. 0, 0.0, and False are treated as
            # same. So we have to check the both of its type and value.
            mask = splib.make_mask_object_ndarray(arr, fill_value)
        else:
            mask = arr != fill_value

    length = len(arr)
    if length != len(mask):
        # the arr is a SparseArray
        indices = mask.sp_index.indices
    else:
        indices = mask.nonzero()[0].astype(np.int32)

    index = make_sparse_index(length, indices, kind)
    sparsified_values = arr[mask]
    if dtype is not None:
        sparsified_values = ensure_wrapped_if_datetimelike(sparsified_values)
        sparsified_values = astype_array(sparsified_values, dtype=dtype)
        sparsified_values = np.asarray(sparsified_values)

    # TODO: copy
    return sparsified_values, index, fill_value


@overload
def make_sparse_index(length: int, indices, kind: Literal["block"]) -> BlockIndex: ...


@overload
def make_sparse_index(length: int, indices, kind: Literal["integer"]) -> IntIndex: ...


def make_sparse_index(length: int, indices, kind: SparseIndexKind) -> SparseIndex:
    index: SparseIndex
    if kind == "block":
        locs, lens = splib.get_blocks(indices)
        index = BlockIndex(length, locs, lens)
    elif kind == "integer":
        index = IntIndex(length, indices)
    else:  # pragma: no cover
        raise ValueError("must be block or integer type")
    return index