MorphologicalTreeFactory.hpp

#pragma once
 
#include "MorphologicalTree.hpp"
#include "NativeHierarchy.hpp"
#include "TreeOfShapesProducer.hpp"
#include "TreeAltitudeAlgorithms.hpp"
#include "ValuedMorphologicalTree.hpp"
#include "detail/ComponentTreeProducerDetail.hpp"
#include "detail/HigraHierarchyAdapterDetail.hpp"
#include "detail/MorphologicalTreeConstructionTag.hpp"
#include "detail/NativeHierarchyValidationDetail.hpp"
#include "sdrt/SaturatedResidualTreeBuilder.hpp"
#include "sdrt/ResidualEvolution.hpp"
#include "sdrt/UnrestrictedResidualTreeBuilder.hpp"
#include "../utils/Image.hpp"
#include "../utils/Contract.hpp"
 
#include <cstddef>
#include <cstdint>
#include <optional>
#include <span>
#include <utility>
#include <vector>
 
namespace mmcfilters {
 
class MorphologicalTreeFactory {
  private:
    template <AltitudeValue T> static void validateComponentTreeImage(const ImagePtr<T>& img, const char* context) {
        MMCFILTERS_CONTRACT_REQUIRE(img != nullptr, throw std::invalid_argument(std::string(context) + " requires a non-null image."));
        MMCFILTERS_CONTRACT_REQUIRE(img->getNumRows() > 0 && img->getNumColumns() > 0 && img->getSize() > 0,
                                    throw std::invalid_argument(std::string(context) + " requires a non-empty 2D image."));
        MMCFILTERS_CONTRACT_CHECKED_ONLY(TreeAltitudeAlgorithms::validateFiniteImageAltitudes(img, context));
    }
 
    static void validateConnectedComponentTreeAdjacency(const RegularGridAdjacency2D& adjacency) {
        const int numPixels = adjacency.getNumRows() * adjacency.getNumColumns();
        std::vector<std::uint8_t> visited(static_cast<std::size_t>(numPixels), 0);
        std::vector<PixelId> pending;
        pending.reserve(static_cast<std::size_t>(numPixels));
        pending.push_back(0);
        visited[0] = 1;
        int reached = 0;
        while (!pending.empty()) {
            const PixelId pixel = pending.back();
            pending.pop_back();
            ++reached;
            for (PixelId neighbor : adjacency.getNeighborIndices(pixel)) {
                if (visited[static_cast<std::size_t>(neighbor)] == 0) {
                    visited[static_cast<std::size_t>(neighbor)] = 1;
                    pending.push_back(neighbor);
                }
            }
        }
        if (reached != numPixels) {
            throw std::invalid_argument("Component-tree adjacency must induce one connected image-domain graph.");
        }
    }
 
    enum class MaterializedVersionPolicy { CanonicalNative, PreserveLinkedConstruction };
 
    static constexpr detail::MorphologicalTreeConstructionTag tag() noexcept { return detail::MorphologicalTreeConstructionTag{}; }
 
    static void validateTreeOfShapesImage(const ImageUInt8Ptr& img) {
        if (!img) {
            throw std::invalid_argument("MorphologicalTreeFactory::createTreeOfShapes requires a non-null image.");
        }
        if (img->getNumRows() <= 0 || img->getNumColumns() <= 0 || img->getSize() <= 0) {
            throw std::invalid_argument("MorphologicalTreeFactory::createTreeOfShapes requires a non-empty 2D image.");
        }
    }
 
    static void resolveTopographicImmersion(TopographicConvention& convention, int numRows, int numColumns) {
        const auto* canonical = std::get_if<CanonicalComplementaryGridImmersion>(&convention.immersion);
        if (canonical == nullptr) {
            return;
        }
        constexpr double connectivity4Radius = 1.0;
        constexpr double connectivity8Radius = 1.5;
        const bool min4Max8 = canonical->pairing == ComplementaryPairing::Min4Max8;
        convention.immersion = ComplementaryGridImmersion{ComplementaryAdjacencies{
            RegularGridAdjacency2D(numRows, numColumns, min4Max8 ? connectivity4Radius : connectivity8Radius),
            RegularGridAdjacency2D(numRows, numColumns, min4Max8 ? connectivity8Radius : connectivity4Radius)}};
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T>
    materializeNativeHierarchy(detail::ValidatedNativeHierarchy<T>&& hierarchy, std::optional<NodeId> preservedExternalNodeIdOffset = std::nullopt,
                               MaterializedVersionPolicy versionPolicy = MaterializedVersionPolicy::CanonicalNative) {
        auto storage = std::move(hierarchy).release();
        const std::size_t numNodes = storage.parent.size();
        MorphologicalTree topology(tag(), std::move(storage.parent), std::move(storage.smallestNodeMap), storage.root, storage.gridDomain2D,
                                   std::move(storage.semantics), std::move(storage.topologyProof));
        if (versionPolicy == MaterializedVersionPolicy::PreserveLinkedConstruction) {
            // Account for initialization, non-root links, and finalization.
            topology.mutationVersion_ = numNodes + 1;
        }
        if (preservedExternalNodeIdOffset) {
            topology.preserveExternalNodeIdOffset(*preservedExternalNodeIdOffset);
        }
        return ValuedMorphologicalTree<T>(tag(), std::move(topology), std::move(storage.nodeAltitudes));
    }
 
  public:
    template <AltitudeValue T> [[nodiscard]] static ValuedMorphologicalTree<T> createMaxTree(ImagePtr<T> img, double radius = 1.5) {
        validateComponentTreeImage(img, "MorphologicalTreeFactory::createMaxTree");
        RegularGridAdjacency2D adjacency(img->getNumRows(), img->getNumColumns(), radius);
        MMCFILTERS_CONTRACT_REQUIRE(img->getSize() == 1 || radius >= 1.0,
                                    throw std::invalid_argument("Component-tree adjacency must induce one connected image-domain graph."));
        return materializeNativeHierarchy<T>(
            detail::kernel::ComponentTreeProducer<T>(detail::kernel::ComponentTreePolarity::MaxTree, std::move(adjacency)).build(img), std::nullopt,
            MaterializedVersionPolicy::PreserveLinkedConstruction);
    }
 
    template <AltitudeValue T> [[nodiscard]] static ValuedMorphologicalTree<T> createMaxTree(ImagePtr<T> img, RegularGridAdjacency2D adjacency) {
        validateComponentTreeImage(img, "MorphologicalTreeFactory::createMaxTree");
        MMCFILTERS_CONTRACT_REQUIRE(adjacency.getNumRows() == img->getNumRows() && adjacency.getNumColumns() == img->getNumColumns(),
                                    throw std::invalid_argument("Component-tree adjacency domain must match the input image domain."));
        MMCFILTERS_CONTRACT_CHECKED_ONLY(validateConnectedComponentTreeAdjacency(adjacency));
        return materializeNativeHierarchy<T>(
            detail::kernel::ComponentTreeProducer<T>(detail::kernel::ComponentTreePolarity::MaxTree, std::move(adjacency)).build(img), std::nullopt,
            MaterializedVersionPolicy::PreserveLinkedConstruction);
    }
 
    template <AltitudeValue T> [[nodiscard]] static ValuedMorphologicalTree<T> createMinTree(ImagePtr<T> img, double radius = 1.5) {
        validateComponentTreeImage(img, "MorphologicalTreeFactory::createMinTree");
        RegularGridAdjacency2D adjacency(img->getNumRows(), img->getNumColumns(), radius);
        MMCFILTERS_CONTRACT_REQUIRE(img->getSize() == 1 || radius >= 1.0,
                                    throw std::invalid_argument("Component-tree adjacency must induce one connected image-domain graph."));
        return materializeNativeHierarchy<T>(
            detail::kernel::ComponentTreeProducer<T>(detail::kernel::ComponentTreePolarity::MinTree, std::move(adjacency)).build(img), std::nullopt,
            MaterializedVersionPolicy::PreserveLinkedConstruction);
    }
 
    template <AltitudeValue T> [[nodiscard]] static ValuedMorphologicalTree<T> createMinTree(ImagePtr<T> img, RegularGridAdjacency2D adjacency) {
        validateComponentTreeImage(img, "MorphologicalTreeFactory::createMinTree");
        MMCFILTERS_CONTRACT_REQUIRE(adjacency.getNumRows() == img->getNumRows() && adjacency.getNumColumns() == img->getNumColumns(),
                                    throw std::invalid_argument("Component-tree adjacency domain must match the input image domain."));
        MMCFILTERS_CONTRACT_CHECKED_ONLY(validateConnectedComponentTreeAdjacency(adjacency));
        return materializeNativeHierarchy<T>(
            detail::kernel::ComponentTreeProducer<T>(detail::kernel::ComponentTreePolarity::MinTree, std::move(adjacency)).build(img), std::nullopt,
            MaterializedVersionPolicy::PreserveLinkedConstruction);
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T>
    createUnrestrictedResidualTree(ImagePtr<T> img, RegularGridAdjacency2D adjacency,
                                   sdrt::UnrestrictedResidualTreeOptions options = {}) {
        auto minTree = createMinTree(img, adjacency);
        auto maxTree = createMaxTree(img, adjacency);
        sdrt::UnrestrictedResidualTreeBuilder<T> builder(adjacency, options);
        builder.build(img, std::move(minTree), std::move(maxTree));
        return materializeNativeHierarchy<T>(
            std::move(builder).takeValidatedHierarchy(makeMorphologicalTreeSemantics(
                MorphologicalTreeKind::UnrestrictedResidualTree, SharedAdjacencyContext{std::move(adjacency)})));
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T>
    createUnrestrictedResidualTree(ImagePtr<T> img, double radius = 1.5, sdrt::UnrestrictedResidualTreeOptions options = {}) {
        TreeAltitudeAlgorithms::validateFiniteImageAltitudes(img, "MorphologicalTreeFactory::createUnrestrictedResidualTree image");
        RegularGridAdjacency2D adjacency(img->getNumRows(), img->getNumColumns(), radius);
        return createUnrestrictedResidualTree(std::move(img), std::move(adjacency), options);
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T>
    createSaturatedResidualTree(ImagePtr<T> img, RegularGridAdjacency2D adjacency, PixelId infinityPixel,
                                sdrt::SaturatedResidualTreeOptions options = {}) {
        auto minTree = createMinTree(img, adjacency);
        auto maxTree = createMaxTree(img, adjacency);
        sdrt::SaturatedResidualTreeBuilder<T> builder(adjacency, infinityPixel, options);
        builder.build(img, std::move(minTree), std::move(maxTree));
        return materializeNativeHierarchy<T>(
            std::move(builder).takeValidatedHierarchy(makeMorphologicalTreeSemantics(
                MorphologicalTreeKind::SaturatedResidualTree, SaturatedResidualContext{std::move(adjacency), infinityPixel})));
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T>
    createSaturatedResidualTree(ImagePtr<T> img, PixelId infinityPixel, double radius = 1.5,
                                sdrt::SaturatedResidualTreeOptions options = {}) {
        TreeAltitudeAlgorithms::validateFiniteImageAltitudes(img, "MorphologicalTreeFactory::createSaturatedResidualTree image");
        RegularGridAdjacency2D adjacency(img->getNumRows(), img->getNumColumns(), radius);
        return createSaturatedResidualTree(std::move(img), std::move(adjacency), infinityPixel, options);
    }
 
    template <class Altitude = std::uint8_t>
    [[nodiscard]] static ValuedMorphologicalTree<Altitude> createTreeOfShapes(ImageUInt8Ptr img, TopographicConvention convention = {}) {
        validateTreeOfShapesImage(img);
        resolveTopographicImmersion(convention, img->getNumRows(), img->getNumColumns());
 
        TreeOfShapesProducer producer(convention);
        TreeOfShapesBuildResult<Altitude> result = producer.build<Altitude>(img);
        MorphologicalTreeSemantics semantics = makeMorphologicalTreeSemantics(MorphologicalTreeKind::TreeOfShapes, std::move(convention));
        return materializeNativeHierarchy<Altitude>(std::move(result).takeValidatedHierarchy(std::move(semantics)));
    }
 
    template <AltitudeValue T> [[nodiscard]] static ValuedMorphologicalTree<T> createFromNativeHierarchy(NativeHierarchyView<T> hierarchy) {
        return materializeNativeHierarchy<T>(detail::validateAndCopyNativeHierarchy<T>(std::move(hierarchy)));
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T> createFromNativeTopology(std::span<const NodeId> parent, std::span<const NodeId> smallestNodeMap,
                                                                               std::span<const T> nodeAltitudes, NodeId root, MorphologicalTreeSemantics semantics) {
        return createFromNativeHierarchy<T>(NativeHierarchyView<T>{parent, smallestNodeMap, nodeAltitudes, root, std::nullopt, std::move(semantics)});
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T> createFromNativeTopology(std::span<const NodeId> parent, std::span<const NodeId> smallestNodeMap,
                                                                               std::span<const T> nodeAltitudes, NodeId root, int rows, int columns,
                                                                               MorphologicalTreeSemantics semantics) {
        return createFromNativeHierarchy<T>(
            NativeHierarchyView<T>{parent, smallestNodeMap, nodeAltitudes, root, GridDomain2D{rows, columns}, std::move(semantics)});
    }
 
    template <AltitudeValue T>
    [[nodiscard]] static ValuedMorphologicalTree<T> createFromHigraParent(std::span<const NodeId> parent, std::span<const T> nodeAltitudes, int rows,
                                                                            int columns, MorphologicalTreeKind kind,
                                                                            std::optional<RegularGridAdjacency2D> adjacency = std::nullopt) {
        auto imported = detail::adaptHigraHierarchy<T>(parent, nodeAltitudes, rows, columns, kind, std::move(adjacency));
        return materializeNativeHierarchy<T>(std::move(imported.hierarchy), imported.internalNodeOffset, MaterializedVersionPolicy::PreserveLinkedConstruction);
    }
};
 
} // namespace mmcfilters