# LICENSE HEADER MANAGED BY add-license-header
#
# Copyright 2018 Kornia Team
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#

import torch
import torch.nn.functional as F


def connected_components(image: torch.Tensor, num_iterations: int = 100) -> torch.Tensor:
    r"""Label 8-connected foreground components by a fixed number of max-pooling steps.

    ``labels = connected_components(image, num_iterations)`` takes a ``(*, 1, H, W)`` mask whose pixels equal to 1 are
    foreground and returns ``int64`` labels of the same shape, 0 on the background. A component comes out whole only
    when every pixel is within ``num_iterations`` 8-connected steps, inside the component, of its last pixel in raster
    order; otherwise it is split. For the exact partition at any size, use :func:`connected_components_union_find`.

    .. image:: https://github.com/kornia/data/raw/main/cells_segmented.png

    The implementation adapts https://gist.github.com/efirdc/5d8bd66859e574c683a504a4690ae8bc.

    .. warning::
        This is an experimental API subject to changes and optimization improvements.

    .. note::
       See a working example `here <https://www.kornia.org/tutorials/nbs/connected_components.html>`__.

    Convention:
        - Components are 8-connected: pixels that touch at a corner are connected. :ref:`labeling-method` maps this
          onto SciPy, OpenCV and scikit-image.
        - Foreground is a value exactly equal to 1: 0.5 and 2 are background. Other values and dtypes are accepted.
        - The label of a component is 1 plus the largest raster index of its pixels in the batch flattened to
          ``(N, H, W)``; background is 0. Labels are therefore not contiguous, and an image gets other labels at
          another batch position or transposed.
        - The default 100 already splits a 1 x 102 line, and a filled 120 x 150 rectangle comes out with 1000 labels.
        - The labels carry no gradient. The function has no host synchronization and compiles with
          ``torch.compile(fullgraph=True)``.

    Args:
        image: the binary input image with shape ``(*, 1, H, W)``.
        num_iterations: the number of max-pooling steps, at least 1.

    Return:
        int64 labels with the shape of the input.

    Raises:
        TypeError: if ``image`` is not a tensor or ``num_iterations`` is not a positive integer.
        ValueError: if ``image`` is not ``(*, 1, H, W)``, or, on MPS, has more than :math:`2^{24}` pixels per image.

    See Also:
        - :func:`connected_components_union_find`: the exact partition with no iteration budget, at the cost of host
          synchronizations and other label values.

    Example:
        >>> img = torch.rand(2, 1, 4, 5)
        >>> img_labels = connected_components(img, num_iterations=100)

    """
    if not isinstance(image, torch.Tensor):
        raise TypeError(f"Input imagetype is not a torch.Tensor. Got: {type(image)}")

    if not isinstance(num_iterations, int) or num_iterations < 1:
        raise TypeError("Input num_iterations must be a positive integer.")

    if len(image.shape) < 3 or image.shape[-3] != 1:
        raise ValueError(f"Input image shape must be (*,1,H,W). Got: {image.shape}")

    H, W = image.shape[-2:]
    # Before the reshape: reshape(-1, 1, 0, W) cannot infer -1 from zero elements.
    if image.numel() == 0:
        return torch.zeros(image.shape, dtype=torch.int64, device=image.device)
    image_view = image.reshape(-1, 1, H, W)
    B = image_view.shape[0]
    num_ids = H * W
    # Pooling never mixes batch planes, so every plane is labelled with its own ids 1..H*W and the plane offset is added
    # in int64 afterwards. Labels are pooled as floats (max_pool2d has no integer kernel): float32 holds every integer
    # up to 2**24 exactly; larger planes need float64, which MPS does not have.
    id_dtype = torch.float32
    if num_ids > 2**24:
        if image.device.type == "mps":
            raise ValueError(
                f"connected_components labels {num_ids} pixels in one image; on MPS (no float64) the limit is 2**24 "
                "pixels per image. Run it on the CPU instead."
            )
        id_dtype = torch.float64

    # precompute a mask with the valid values
    mask = image_view == 1
    out = torch.arange(1, num_ids + 1, device=image.device, dtype=id_dtype).view(1, 1, H, W).expand(B, 1, H, W)
    out = out * mask

    for _ in range(num_iterations):
        out = F.max_pool2d(out, kernel_size=3, stride=1, padding=1)
        out = torch.mul(out, mask)  # mask using element-wise multiplication

    labels = out.to(torch.int64)
    offset = torch.arange(B, device=image.device, dtype=torch.int64).view(-1, 1, 1, 1) * num_ids
    # Shift the foreground labels by the plane offset in place; the mask zeroes the background again.
    return labels.add_(offset).mul_(mask).view(image.shape)


def connected_components_union_find(image: torch.Tensor) -> torch.Tensor:
    r"""Label 8-connected foreground components exactly, by block union-find.

    ``labels = connected_components_union_find(image)`` takes a ``(*, 1, H, W)`` mask whose pixels equal to 1 are
    foreground and returns ``int64`` labels of the same shape and device, 0 on the background. It iterates until the
    partition converges, so components of any size and shape come out whole.

    The pure PyTorch implementation contracts each 2x2 block, following Allegretti, Bolelli and Grana, *Optimized
    Block-Based Algorithms to Label Connected Components on GPUs*, TPDS 2020,
    https://doi.org/10.1109/TPDS.2019.2934683. Root hooking with ``scatter_reduce_`` and pointer jumping replace the
    paper's custom CUDA union kernels.

    Convention:
        :ref:`labeling-method` maps its 8-connectivity onto SciPy, OpenCV and scikit-image, and compares it with
        :func:`connected_components`.

    Args:
        image: Binary image of shape ``(*, 1, H, W)``. Boolean, integer and
            floating-point tensors are accepted. Only values equal to 1 are
            foreground, as in :func:`connected_components`.

    Returns:
        Foreground labels are the minimum 1-based block
        index in each component, in raster order over flattened batches and
        the :math:`\lceil H/2\rceil \times \lceil W/2\rceil` block grid.
        Labels are deterministic and distinct across images, but not contiguous
        and not equal to the labels of the pooling implementation.

    Note:
        This discrete operation is not differentiable. Working memory is linear
        in the number of pixels. Convergence checks synchronize the device with
        the host; CUDA graph capture and ``torch.compile(fullgraph=True)`` are
        not supported. All mask, edge and label computation stays on the input
        device.

    Raises:
        TypeError: if ``image`` is not a tensor.
        ValueError: if ``image`` is not ``(*, 1, H, W)``.

    See Also:
        - :func:`connected_components`: a fixed number of pooling steps, which compiles with ``fullgraph=True`` and
          splits components longer than its budget.

    Example:
        >>> mask = torch.tensor([[[1, 0, 0], [0, 0, 1]]], dtype=torch.bool)
        >>> connected_components_union_find(mask)
        tensor([[[1, 0, 0],
                 [0, 0, 2]]])

    """
    if not isinstance(image, torch.Tensor):
        raise TypeError(f"Input image is not a torch.Tensor. Got: {type(image)}")
    if image.ndim < 3 or image.shape[-3] != 1:
        raise ValueError(f"Input image shape must be (*,1,H,W). Got: {image.shape}")
    if image.numel() == 0:
        return torch.zeros_like(image, dtype=torch.int64)

    height, width = image.shape[-2:]
    mask = (image == 1).reshape(-1, height, width)
    # MPSGraph's boolean padding can abort the process; allocate the border explicitly.
    padded = mask.new_zeros((mask.shape[0], height + height % 2, width + width % 2))
    padded[:, :height, :width] = mask
    top_left, top_right = padded[:, ::2, ::2], padded[:, ::2, 1::2]
    bottom_left, bottom_right = padded[:, 1::2, ::2], padded[:, 1::2, 1::2]
    # Every pair of foreground pixels inside a 2x2 block is 8-connected.
    # A block may connect to four already-visited neighbors, but only if an
    # actual pair of foreground pixels touches across the shared boundary.
    blocks = torch.arange(top_left.numel(), device=image.device).reshape(top_left.shape)
    left = (top_left[:, :, 1:] | bottom_left[:, :, 1:]) & (top_right[:, :, :-1] | bottom_right[:, :, :-1])
    above = (top_left[:, 1:, :] | top_right[:, 1:, :]) & (bottom_left[:, :-1, :] | bottom_right[:, :-1, :])
    above_left = top_left[:, 1:, 1:] & bottom_right[:, :-1, :-1]
    above_right = top_right[:, 1:, :-1] & bottom_left[:, :-1, 1:]

    sources = torch.cat(
        [
            blocks[:, :, 1:].flatten(),
            blocks[:, 1:, :].flatten(),
            blocks[:, 1:, 1:].flatten(),
            blocks[:, 1:, :-1].flatten(),
        ]
    )
    # Absent edges become self-loops. Fixed-size arrays avoid nonzero/boolean
    # indexing, which would add device synchronizations during edge creation.
    targets = torch.cat(
        [
            torch.where(left, blocks[:, :, :-1], blocks[:, :, 1:]).flatten(),
            torch.where(above, blocks[:, :-1, :], blocks[:, 1:, :]).flatten(),
            torch.where(above_left, blocks[:, :-1, :-1], blocks[:, 1:, 1:]).flatten(),
            torch.where(above_right, blocks[:, :-1, 1:], blocks[:, 1:, :-1]).flatten(),
        ]
    )
    parents = blocks.flatten()
    # Some MPS devices cannot compile int64 atomic min. Keep the forest in
    # int32 when every zero-based block index fits, without narrowing edge indices.
    if image.device.type == "mps" and parents.numel() <= torch.iinfo(torch.int32).max + 1:
        parents = parents.to(torch.int32)
    while True:
        source_roots, target_roots = parents[sources], parents[targets]
        merged = parents.clone()
        merged.scatter_reduce_(
            0,
            torch.maximum(source_roots, target_roots).long(),
            torch.minimum(source_roots, target_roots),
            reduce="amin",
        )
        # Only roots are hooked and every parent decreases, so cycles cannot
        # form. Fully compress before hooking again: hooking non-roots could
        # detach an already-merged subtree.
        while True:
            compressed = merged[merged.long()]
            if torch.equal(compressed, merged):
                break
            merged = compressed
        if torch.equal(merged, parents):
            break
        parents = merged

    # Widen before reserving zero for background, including the largest int32 root.
    labels = (parents.long().reshape(blocks.shape) + 1).repeat_interleave(2, -2).repeat_interleave(2, -1)
    return (labels[:, :height, :width] * mask).reshape(image.shape)
