ValuedMorphologicalTree.hpp

#pragma once
 
#include "MorphologicalTree.hpp"
#include "TreeAltitudeAlgorithms.hpp"
#include "TreeEditor.hpp"
#include "ValuedMorphologicalTreeView.hpp"
#include "NativeHierarchyOwned.hpp"
#include "../utils/Contract.hpp"
#include "../utils/Image.hpp"
 
#include <memory>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <optional>
#include <utility>
#include <vector>
 
namespace mmcfilters {
 
template <AltitudeValue T> class ValuedMorphologicalTreeEditor;
 
template <AltitudeValue T> class ValuedMorphologicalTree;
 
namespace detail {
 
template <AltitudeValue T> [[nodiscard]] ValuedMorphologicalTreeEditor<T> beginEstablishedValuedEdit(ValuedMorphologicalTree<T>& tree);
 
} // namespace detail
 
template <AltitudeValue T> class ValuedMorphologicalTree {
    friend class ValuedMorphologicalTreeEditor<T>;
 
  public:
    using AltitudeType = T;
 
    using NodeAltitudeBuffer = mmcfilters::NodeAltitudeBuffer<T>;
 
  private:
    MorphologicalTree tree_;
    NodeAltitudeBuffer nodeAltitudes_;
 
    static bool skipsMonotoneValidation(const MorphologicalTree& tree) noexcept { return tree.nodeAltitudeOrder() == NodeAltitudeOrder::Unconstrained; }
 
    [[nodiscard]] bool validateLocalMonotoneNodeAltitudeUpdate(NodeId nodeId, T value) const {
        if (skipsMonotoneValidation(tree_)) {
            return false;
        }
 
        const bool increasingFromRoot = tree_.nodeAltitudeOrder() == NodeAltitudeOrder::Increasing;
        if (!tree_.isRoot(nodeId)) {
            const NodeId parentNodeId = tree_.parent(nodeId);
            if (parentNodeId == InvalidNode || !tree_.isAlive(parentNodeId)) {
                throw std::runtime_error("Monotone altitude update requires an alive non-root node to have an alive parent.");
            }
            const T parentAltitude = nodeAltitudes_[static_cast<size_t>(parentNodeId)];
            if (increasingFromRoot && parentAltitude >= value) {
                throw std::runtime_error("Hierarchy altitude update must remain strictly increasing from parent to child.");
            }
            if (!increasingFromRoot && parentAltitude <= value) {
                throw std::runtime_error("Hierarchy altitude update must remain strictly decreasing from parent to child.");
            }
        }
 
        for (NodeId childId : tree_.children(nodeId)) {
            const T childAltitude = nodeAltitudes_[static_cast<size_t>(childId)];
            if (increasingFromRoot && value >= childAltitude) {
                throw std::runtime_error("Hierarchy altitude update must remain strictly increasing from parent to child.");
            }
            if (!increasingFromRoot && value <= childAltitude) {
                throw std::runtime_error("Hierarchy altitude update must remain strictly decreasing from parent to child.");
            }
        }
        return true;
    }
 
  private:
    ValuedMorphologicalTree() = delete;
 
  public:
    ValuedMorphologicalTree(const ValuedMorphologicalTree&) = delete;
    ValuedMorphologicalTree& operator=(const ValuedMorphologicalTree&) = delete;
 
    ValuedMorphologicalTree(ValuedMorphologicalTree&& other) : tree_(std::move(other.tree_)), nodeAltitudes_(std::move(other.nodeAltitudes_)) {}
 
    ValuedMorphologicalTree& operator=(ValuedMorphologicalTree&& other) {
        if (this != &other) {
            tree_ = std::move(other.tree_);
            nodeAltitudes_ = std::move(other.nodeAltitudes_);
        } else {
            tree_.requireNotEditing("ValuedMorphologicalTree self move assignment");
        }
        return *this;
    }
 
    ValuedMorphologicalTree(detail::MorphologicalTreeConstructionTag, MorphologicalTree&& topology, NodeAltitudeBuffer&& altitude)
        : tree_(std::move(topology)), nodeAltitudes_(std::move(altitude)) {}
 
    void validateNodeAltitudeBufferShape() const { TreeAltitudeAlgorithms::validateNodeAltitudeBufferShape(tree_, nodeAltitudeSpan()); }
 
    [[nodiscard]] const MorphologicalTree& topology() const noexcept { return tree_; }
 
    [[nodiscard]] const NodeAltitudeBuffer& nodeAltitudes() const noexcept { return nodeAltitudes_; }
 
    [[nodiscard]] NodeAltitudeSpan<T> nodeAltitudeSpan() const noexcept { return std::span<const T>(nodeAltitudes_); }
 
    [[nodiscard]] ValuedMorphologicalTreeView<T> asView() const { return ValuedMorphologicalTreeView<T>(*this); }
 
    void setNodeAltitudes(NodeAltitudeBuffer altitudeBuffer) {
        tree_.requireNotEditing("ValuedMorphologicalTree::setNodeAltitudes");
        if (altitudeBuffer.size() != static_cast<size_t>(tree_.numInternalNodeSlots())) {
            throw std::runtime_error("Altitude buffer size must match the dense internal-node domain.");
        }
        TreeAltitudeAlgorithms::validateFiniteAltitudeValues(std::span<const T>(altitudeBuffer), "ValuedMorphologicalTree::setNodeAltitudes");
        TreeAltitudeAlgorithms::validateMonotoneNodeAltitudes(tree_, std::span<const T>(altitudeBuffer));
        nodeAltitudes_ = std::move(altitudeBuffer);
    }
 
    void validateMonotoneNodeAltitudes() const { TreeAltitudeAlgorithms::validateMonotoneNodeAltitudes(tree_, nodeAltitudeSpan()); }
 
    [[nodiscard]] T nodeAltitude(NodeId nodeId) const {
        MMCFILTERS_CONTRACT_REQUIRE(tree_.isAlive(nodeId) && static_cast<size_t>(nodeId) < nodeAltitudes_.size(),
                                    throw std::invalid_argument("ValuedMorphologicalTree::nodeAltitude requires a live internal NodeId."));
        return nodeAltitudes_[static_cast<size_t>(nodeId)];
    }
 
    void setNodeAltitude(NodeId nodeId, T value) {
        tree_.requireNotEditing("ValuedMorphologicalTree::setNodeAltitude");
        if (!tree_.isAlive(nodeId) || static_cast<size_t>(nodeId) >= nodeAltitudes_.size()) {
            throw std::invalid_argument("ValuedMorphologicalTree::setNodeAltitude requires a live internal NodeId.");
        }
        TreeAltitudeAlgorithms::validateFiniteAltitudeValue(value, static_cast<std::size_t>(nodeId), "ValuedMorphologicalTree::setNodeAltitude");
        static_cast<void>(validateLocalMonotoneNodeAltitudeUpdate(nodeId, value));
        nodeAltitudes_[static_cast<size_t>(nodeId)] = value;
    }
 
    void pruneNode(NodeId nodeId) {
        tree_.requireNotEditing("ValuedMorphologicalTree::pruneNode");
        tree_.pruneNode(nodeId);
    }
 
    void mergeNodeIntoParent(NodeId nodeId) {
        tree_.requireNotEditing("ValuedMorphologicalTree::mergeNodeIntoParent");
        tree_.mergeNodeIntoParent(nodeId);
    }
 
    [[nodiscard]] AltitudeDifference<T> nodeResidue(NodeId nodeId) const { return TreeAltitudeAlgorithms::nodeResidue(tree_, nodeAltitudeSpan(), nodeId); }
 
    [[nodiscard]] ImagePtr<T> reconstructFromNodeAltitudes() const {
        return TreeAltitudeAlgorithms::reconstructFromNodeAltitudes(tree_, nodeAltitudeSpan(), "ValuedMorphologicalTree::reconstructFromNodeAltitudes");
    }
 
    template <class Contribution>
        requires(std::is_arithmetic_v<Contribution> && !std::is_same_v<std::remove_cv_t<Contribution>, bool>)
    [[nodiscard]] ImagePtr<Contribution> reconstructFromNodeContributions(std::span<const Contribution> nodeContributions) const {
        return TreeAltitudeAlgorithms::reconstructFromNodeContributions(tree_, nodeContributions,
                                                                         "ValuedMorphologicalTree::reconstructFromNodeContributions");
    }
 
    [[nodiscard]] std::pair<std::vector<NodeId>, std::vector<T>> exportHigraHierarchy() const {
        return TreeAltitudeAlgorithms::exportHigraHierarchy(tree_, nodeAltitudeSpan());
    }
 
    [[nodiscard]] ValuedMorphologicalTreeEditor<T> edit() { return ValuedMorphologicalTreeEditor<T>(*this); }
};
 
template <AltitudeValue T> class ValuedMorphologicalTreeEditor {
    friend class ValuedMorphologicalTree<T>;
    friend ValuedMorphologicalTreeEditor<T> detail::beginEstablishedValuedEdit<T>(ValuedMorphologicalTree<T>& tree);
 
  private:
    struct AltitudeRollbackJournal {
        std::size_t originalSize = 0;
        TreeEditor::DeltaNodeSet captured;
        std::vector<std::pair<NodeId, T>> values;
    };
 
    ValuedMorphologicalTree<T>& valuedTree_;
    TreeEditor editor_;
    std::size_t originalAltitudeSize_ = 0;
    std::unique_ptr<AltitudeRollbackJournal> altitudeRollbackJournal_;
    std::size_t editRevision_ = 0;
    std::optional<std::size_t> provenRevision_;
 
    explicit ValuedMorphologicalTreeEditor(ValuedMorphologicalTree<T>& valuedTree, [[maybe_unused]] bool transactional = false,
                                bool invariantsEstablishedByConstruction = false)
        : valuedTree_(valuedTree), editor_(valuedTree.tree_, invariantsEstablishedByConstruction), originalAltitudeSize_(valuedTree.nodeAltitudes_.size()) {}
 
    void ensureAltitudeRollbackJournal() {
        if (!editor_.canRollback()) {
            return;
        }
        editor_.ensureRollbackJournal();
        if (!altitudeRollbackJournal_) {
            altitudeRollbackJournal_ = std::make_unique<AltitudeRollbackJournal>();
            altitudeRollbackJournal_->originalSize = originalAltitudeSize_;
        }
    }
 
    void captureAltitudeForRollback(NodeId nodeId) {
        ensureAltitudeRollbackJournal();
        if (!altitudeRollbackJournal_) {
            return;
        }
        if (nodeId < 0 || static_cast<std::size_t>(nodeId) >= originalAltitudeSize_) {
            return;
        }
        if (altitudeRollbackJournal_->captured.contains(nodeId)) {
            return;
        }
        altitudeRollbackJournal_->values.reserve(altitudeRollbackJournal_->values.size() + 1);
        if (!altitudeRollbackJournal_->captured.insert(nodeId)) {
            return;
        }
        altitudeRollbackJournal_->values.emplace_back(nodeId, valuedTree_.nodeAltitudes_[static_cast<std::size_t>(nodeId)]);
    }
 
    void restoreAltitudeJournal() noexcept {
        if (!altitudeRollbackJournal_ || !editor_.canRollback()) {
            return;
        }
        valuedTree_.nodeAltitudes_.resize(altitudeRollbackJournal_->originalSize);
        for (const auto& [nodeId, altitude] : altitudeRollbackJournal_->values) {
            valuedTree_.nodeAltitudes_[static_cast<std::size_t>(nodeId)] = altitude;
        }
    }
 
    void recordMutation() noexcept {
        if (editor_.invariantsEstablishedByConstruction_) {
            return;
        }
        ++editRevision_;
        provenRevision_.reset();
    }
 
  public:
    ValuedMorphologicalTreeEditor(const ValuedMorphologicalTreeEditor&) = delete;
    ValuedMorphologicalTreeEditor& operator=(const ValuedMorphologicalTreeEditor&) = delete;
 
    ValuedMorphologicalTreeEditor(ValuedMorphologicalTreeEditor&& other) noexcept
        : valuedTree_(other.valuedTree_), editor_(std::move(other.editor_)), originalAltitudeSize_(other.originalAltitudeSize_),
          altitudeRollbackJournal_(std::move(other.altitudeRollbackJournal_)), editRevision_(other.editRevision_), provenRevision_(other.provenRevision_) {
        other.altitudeRollbackJournal_.reset();
        other.provenRevision_.reset();
    }
 
    ValuedMorphologicalTreeEditor& operator=(ValuedMorphologicalTreeEditor&&) = delete;
 
    ~ValuedMorphologicalTreeEditor() { restoreAltitudeJournal(); }
 
    [[nodiscard]] bool canRollback() const noexcept { return editor_.canRollback(); }
 
    void rollback() {
        if (!canRollback()) {
            throw std::logic_error("ValuedMorphologicalTreeEditor::rollback is unavailable for the internal journal-free editor.");
        }
        restoreAltitudeJournal();
        editor_.rollback();
    }
 
    [[nodiscard("Discarding a detached node id makes the staged edit impossible to complete safely")]] NodeId createDetachedNode(T altitude = T{}) {
        TreeAltitudeAlgorithms::validateFiniteAltitudeValue(altitude, 0, "ValuedMorphologicalTreeEditor::createDetachedNode");
        const std::size_t requiredAltitudeSize =
            static_cast<std::size_t>(valuedTree_.tree_.numInternalNodeSlots()) + (valuedTree_.tree_.getNumFreeNodeSlots() == 0 ? 1u : 0u);
        valuedTree_.nodeAltitudes_.reserve(requiredAltitudeSize);
        ensureAltitudeRollbackJournal();
        const NodeId nodeId = editor_.createDetachedNode();
        valuedTree_.nodeAltitudes_.resize(static_cast<size_t>(valuedTree_.tree_.numInternalNodeSlots()), T{});
        captureAltitudeForRollback(nodeId);
        valuedTree_.nodeAltitudes_[static_cast<size_t>(nodeId)] = altitude;
        recordMutation();
        return nodeId;
    }
 
    void setNodeAltitude(NodeId nodeId, T altitude) {
        if (!valuedTree_.tree_.isAlive(nodeId)) {
            throw std::invalid_argument("ValuedMorphologicalTreeEditor::setNodeAltitude requires a live node.");
        }
        TreeAltitudeAlgorithms::validateFiniteAltitudeValue(altitude, static_cast<std::size_t>(nodeId), "ValuedMorphologicalTreeEditor::setNodeAltitude");
        captureAltitudeForRollback(nodeId);
        valuedTree_.nodeAltitudes_[static_cast<size_t>(nodeId)] = altitude;
        editor_.touch(nodeId);
        recordMutation();
    }
 
    void detach(NodeId nodeId) {
        editor_.detach(nodeId);
        recordMutation();
    }
 
    void reparent(NodeId nodeId, NodeId newParentId) {
        editor_.reparent(nodeId, newParentId);
        recordMutation();
    }
 
    void attach(NodeId parentId, NodeId detachedNodeId) {
        editor_.attach(parentId, detachedNodeId);
        recordMutation();
    }
 
    void moveChildren(NodeId parentId, NodeId sourceId) {
        editor_.moveChildren(parentId, sourceId);
        recordMutation();
    }
 
    void movePixelToProperPart(NodeId targetNodeId, NodeId sourceNodeId, PixelId pixel) {
        editor_.movePixelToProperPart(targetNodeId, sourceNodeId, pixel);
        recordMutation();
    }
 
    void mergeProperParts(NodeId targetNodeId, NodeId sourceNodeId) {
        editor_.mergeProperParts(targetNodeId, sourceNodeId);
        recordMutation();
    }
 
    void removeChild(NodeId parentNodeId, NodeId childId, bool releaseNodeFlag) {
        editor_.removeChild(parentNodeId, childId, releaseNodeFlag);
        recordMutation();
    }
 
    void releaseNode(NodeId nodeId) {
        editor_.releaseNode(nodeId);
        recordMutation();
    }
 
    void setRoot(NodeId nodeId) {
        editor_.setRoot(nodeId);
        recordMutation();
    }
 
    void pruneNode(NodeId nodeId) {
        editor_.pruneNode(nodeId);
        recordMutation();
    }
 
    void mergeNodeIntoParent(NodeId nodeId) {
        editor_.mergeNodeIntoParent(nodeId);
        recordMutation();
    }
 
    [[nodiscard]] bool hasDetachedAliveNodes() const noexcept { return editor_.hasDetachedAliveNodes(); }
 
    [[nodiscard]] TreeEditor::IncrementalProof proveIncremental() {
        bool strictAltitudeExcludesCycles = !ValuedMorphologicalTree<T>::skipsMonotoneValidation(valuedTree_.tree_);
        if (!editor_.invariantsEstablishedByConstruction_) {
            for (NodeId node : editor_.touchedNodes_.entries()) {
                if (!valuedTree_.tree_.isAlive(node)) {
                    continue;
                }
                strictAltitudeExcludesCycles =
                    valuedTree_.validateLocalMonotoneNodeAltitudeUpdate(node, valuedTree_.nodeAltitudes_[static_cast<std::size_t>(node)]) && strictAltitudeExcludesCycles;
            }
        }
 
        auto proof = strictAltitudeExcludesCycles ? editor_.proveIncrementalWithStrictAltitudeAcyclicity() : editor_.proveIncremental();
#ifndef NDEBUG
        // The assertion-enabled oracle runs exactly once, including when the
        // topology proof already fell back to complete validation.
        valuedTree_.validateMonotoneNodeAltitudes();
#else
        if (proof.usedCompleteValidation()) {
            valuedTree_.validateMonotoneNodeAltitudes();
        }
#endif
        provenRevision_ = editRevision_;
        return proof;
    }
 
    void commit(TreeEditor::IncrementalProof&& proof) {
        if (!provenRevision_ || *provenRevision_ != editRevision_) {
            throw std::logic_error("Incremental valued-tree proof is stale or belongs to another edit revision.");
        }
        editor_.commit(std::move(proof));
        provenRevision_.reset();
        altitudeRollbackJournal_.reset();
    }
 
    [[nodiscard]] TreeValidationResult validate() const noexcept { return editor_.validate(); }
 
    [[nodiscard("Inspect the validation result or use commit() for exception-based failure handling")]] TreeValidationResult validateAndCommit() noexcept {
        TreeValidationResult result = editor_.validate();
        if (!result.ok) {
            return result;
        }
        try {
            valuedTree_.validateMonotoneNodeAltitudes();
        } catch (const std::exception& ex) {
            return {false, ex.what()};
        } catch (...) {
            return {false, "ValuedMorphologicalTreeEditor monotone-altitude validation failed with an unknown error."};
        }
        editor_.finishCommit(TreeEditValidationMode::Complete);
        altitudeRollbackJournal_.reset();
        provenRevision_.reset();
        return result;
    }
 
    void commit() {
        TreeValidationResult result = validateAndCommit();
        if (!result.ok) {
            throw std::runtime_error(result.message);
        }
    }
};
 
namespace detail {
 
template <AltitudeValue T>
[[nodiscard]] ValuedMorphologicalTree<T> materializeNativeHierarchy(NativeHierarchyOwned<T>&& hierarchy,
                                                                  std::optional<NodeId> preservedExternalNodeIdOffset,
                                                                  MaterializedVersionPolicy versionPolicy) {
    const MorphologicalTreeConstructionTag tag{};
    const std::size_t numNodes = hierarchy.parent.size();
    MorphologicalTree topology(tag, std::move(hierarchy.parent), std::move(hierarchy.smallestNodeMap), hierarchy.root, hierarchy.gridDomain2D,
                               std::move(hierarchy.semantics));
    if (versionPolicy == MaterializedVersionPolicy::PreserveLinkedConstruction) {
        topology.mutationVersion_ = numNodes + 1;
    }
    if (preservedExternalNodeIdOffset) {
        topology.preserveExternalNodeIdOffset(*preservedExternalNodeIdOffset);
    }
    return ValuedMorphologicalTree<T>(tag, std::move(topology), std::move(hierarchy.nodeAltitudes));
}
 
template <AltitudeValue T> [[nodiscard]] ValuedMorphologicalTreeEditor<T> beginEstablishedValuedEdit(ValuedMorphologicalTree<T>& tree) {
    return ValuedMorphologicalTreeEditor<T>(tree, false, true);
}
 
} // namespace detail
 
} // namespace mmcfilters