TreeEditor.hpp

#pragma once
 
#include "MorphologicalTree.hpp"
 
#include <cstdint>
#include <memory>
#include <optional>
#include <stdexcept>
#include <vector>
 
namespace mmcfilters {
 
template <AltitudeValue T> class ValuedMorphologicalTreeEditor;
 
class TreeEditor {
    friend class MorphologicalTree;
    template <AltitudeValue T> friend class ValuedMorphologicalTreeEditor;
 
  public:
    class IncrementalProof {
        friend class TreeEditor;
 
        const TreeEditor* editor_ = nullptr;
        const MorphologicalTree* tree_ = nullptr;
        std::size_t mutationVersion_ = 0;
        TreeEditValidationMode validationMode_ = TreeEditValidationMode::Complete;
 
        IncrementalProof(const TreeEditor& editor, TreeEditValidationMode validationMode) noexcept
            : editor_(&editor), tree_(editor.tree_), mutationVersion_(editor.tree_ != nullptr ? editor.tree_->getMutationVersion() : 0),
              validationMode_(validationMode) {}
 
      public:
        IncrementalProof(const IncrementalProof&) = delete;
        IncrementalProof& operator=(const IncrementalProof&) = delete;
 
        IncrementalProof(IncrementalProof&& other) noexcept
            : editor_(other.editor_), tree_(other.tree_), mutationVersion_(other.mutationVersion_), validationMode_(other.validationMode_) {
            other.editor_ = nullptr;
            other.tree_ = nullptr;
        }
 
        IncrementalProof& operator=(IncrementalProof&&) = delete;
 
        [[nodiscard]] bool usedCompleteValidation() const noexcept { return validationMode_ == TreeEditValidationMode::Complete; }
    };
 
  private:
    template <class Id, Id InvalidId> class DeltaIdSet {
        std::vector<Id> ids_;
        std::vector<Id> table_;
 
        [[nodiscard]] static std::size_t hash(Id id) noexcept {
            return static_cast<std::size_t>(static_cast<std::uint32_t>(id) * std::uint32_t{2654435761u});
        }
 
        void rebuild(std::size_t capacity) {
            std::vector<Id> newTable(capacity, InvalidId);
            const std::size_t mask = capacity - 1;
            for (Id id : ids_) {
                std::size_t slot = hash(id) & mask;
                while (newTable[slot] != InvalidId) {
                    slot = (slot + 1) & mask;
                }
                newTable[slot] = id;
            }
            table_ = std::move(newTable);
        }
 
      public:
        [[nodiscard]] bool contains(Id id) const noexcept {
            if (id == InvalidId || table_.empty()) {
                return false;
            }
            const std::size_t mask = table_.size() - 1;
            std::size_t slot = hash(id) & mask;
            while (table_[slot] != InvalidId) {
                if (table_[slot] == id) {
                    return true;
                }
                slot = (slot + 1) & mask;
            }
            return false;
        }
 
        [[nodiscard]] bool insert(Id id) {
            if (id == InvalidId) {
                return false;
            }
            if (table_.empty()) {
                ids_.reserve(16);
                rebuild(32);
            } else if ((ids_.size() + 1) * 10 > table_.size() * 7) {
                rebuild(table_.size() * 2);
            }
 
            const std::size_t mask = table_.size() - 1;
            std::size_t slot = hash(id) & mask;
            while (table_[slot] != InvalidId) {
                if (table_[slot] == id) {
                    return false;
                }
                slot = (slot + 1) & mask;
            }
            ids_.push_back(id);
            table_[slot] = id;
            return true;
        }
 
        [[nodiscard]] const std::vector<Id>&
        entries() const noexcept {
            return ids_;
        }
    };
 
    using DeltaNodeSet = DeltaIdSet<NodeId, InvalidNode>;
 
    using DeltaPixelSet = DeltaIdSet<PixelId, InvalidPixel>;
 
    struct NodeRollbackState {
        NodeId node = InvalidNode;
        NodeId parent = InvalidNode;
        NodeId firstChild = InvalidNode;
        NodeId nextSibling = InvalidNode;
        NodeId prevSibling = InvalidNode;
        NodeId lastChild = InvalidNode;
        int numChildren = 0;
        std::uint8_t alive = 0;
        PixelId properHead = InvalidPixel;
        PixelId properTail = InvalidPixel;
        int properPartCardinality = 0;
    };
 
    struct PixelRollbackState {
        PixelId pixel = InvalidPixel;
        NodeId smallestNodeId = InvalidNode;
        PixelId next = InvalidPixel;
        PixelId previous = InvalidPixel;
    };
 
    enum class FreeListMutation { Popped, Pushed };
 
    struct FreeListRollbackState {
        FreeListMutation mutation = FreeListMutation::Popped;
        NodeId node = InvalidNode;
    };
 
    struct RollbackJournal {
        std::size_t originalNodeSlots = 0;
        NodeId root = InvalidNode;
        int numNodes = 0;
        std::optional<NodeId> preservedExternalNodeIdOffset;
        std::size_t nodeStructureVersion = 0;
        std::size_t topologyVersion = 0;
        std::size_t properPartVersion = 0;
        std::size_t mutationVersion = 0;
        DeltaNodeSet capturedNodes;
        DeltaPixelSet capturedPixels;
        std::vector<NodeRollbackState> nodes;
        std::vector<PixelRollbackState> pixels;
        std::vector<FreeListRollbackState> freeListMutations;
    };
 
    MorphologicalTree* tree_ = nullptr;
    bool active_ = false;
    bool recoverable_ = false;
    std::unique_ptr<RollbackJournal> rollbackJournal_;
    DeltaNodeSet touchedNodes_;
    int detachedNodeBalance_ = 0;
    int unsupportedLeafBalance_ = 0;
    bool incrementalValidationSupported_ = true;
    bool invariantsEstablishedByConstruction_ = false;
 
    class EditSessionPause {
      private:
        MorphologicalTree& tree_;
        bool wasEditing_ = false;
 
      public:
        explicit EditSessionPause(MorphologicalTree& tree) noexcept : tree_(tree), wasEditing_(tree.editSessionOpen_) { tree_.editSessionOpen_ = false; }
 
        ~EditSessionPause() noexcept { tree_.editSessionOpen_ = wasEditing_; }
    };
 
    explicit TreeEditor(MorphologicalTree& tree, bool invariantsEstablishedByConstruction = false)
        : tree_(&tree), active_(true), recoverable_(!invariantsEstablishedByConstruction),
          invariantsEstablishedByConstruction_(invariantsEstablishedByConstruction) {
        tree_->beginEditSession();
    }
 
    void ensureRollbackJournal() {
        if (!recoverable_ || rollbackJournal_) {
            return;
        }
        auto journal = std::make_unique<RollbackJournal>();
        journal->originalNodeSlots = tree_->nodeParent_.size();
        journal->root = tree_->rootNodeId_;
        journal->numNodes = tree_->numNodes_;
        journal->preservedExternalNodeIdOffset = tree_->preservedExternalNodeIdOffset_;
        journal->nodeStructureVersion = tree_->nodeStructureVersion_;
        journal->topologyVersion = tree_->topologyVersion_;
        journal->properPartVersion = tree_->properPartVersion_;
        journal->mutationVersion = tree_->mutationVersion_;
        rollbackJournal_ = std::move(journal);
    }
 
    MorphologicalTree& tree() const {
        if (!active_ || tree_ == nullptr) {
            throw std::logic_error("TreeEditor operation requires an active edit session.");
        }
        return *tree_;
    }
 
    void finishCommit(TreeEditValidationMode validationMode) noexcept {
        if (active_ && tree_ != nullptr) {
            tree_->recordEditCommit(validationMode);
            tree_->endEditSession();
            active_ = false;
            recoverable_ = false;
            rollbackJournal_.reset();
        }
    }
 
    void captureNodeForRollback(NodeId node) {
        if (!recoverable_ || node < 0 || static_cast<std::size_t>(node) >= tree_->nodeParent_.size()) {
            return;
        }
        ensureRollbackJournal();
        if (static_cast<std::size_t>(node) >= rollbackJournal_->originalNodeSlots || rollbackJournal_->capturedNodes.contains(node)) {
            return;
        }
        rollbackJournal_->nodes.reserve(rollbackJournal_->nodes.size() + 1);
        if (!rollbackJournal_->capturedNodes.insert(node)) {
            return;
        }
        const std::size_t slot = static_cast<std::size_t>(node);
        rollbackJournal_->nodes.push_back({node, tree_->nodeParent_[slot], tree_->firstChild_[slot], tree_->nextSibling_[slot], tree_->prevSibling_[slot],
                                           tree_->lastChild_[slot], tree_->numChildrenByNode_[slot], tree_->alive_[slot], tree_->properHead_[slot],
                                           tree_->properTail_[slot], tree_->properPartCardinalityByNode_[slot]});
    }
 
    void capturePixelForRollback(PixelId pixel) {
        if (!recoverable_ || !tree_->isPixel(pixel)) {
            return;
        }
        ensureRollbackJournal();
        if (rollbackJournal_->capturedPixels.contains(pixel)) {
            return;
        }
        rollbackJournal_->pixels.reserve(rollbackJournal_->pixels.size() + 1);
        if (!rollbackJournal_->capturedPixels.insert(pixel)) {
            return;
        }
        const std::size_t slot = static_cast<std::size_t>(pixel);
        rollbackJournal_->pixels.push_back({pixel, tree_->smallestNodeMap_[slot], tree_->nextProperPart_[slot], tree_->prevProperPart_[slot]});
    }
 
    void captureNodeLinkNeighborhood(NodeId node) {
        if (node < 0 || static_cast<std::size_t>(node) >= tree_->nodeParent_.size()) {
            return;
        }
        captureNodeForRollback(node);
        captureNodeForRollback(tree_->nodeParent_[static_cast<std::size_t>(node)]);
        captureNodeForRollback(tree_->prevSibling_[static_cast<std::size_t>(node)]);
        captureNodeForRollback(tree_->nextSibling_[static_cast<std::size_t>(node)]);
    }
 
    void capturePixelLinkNeighborhood(PixelId pixel) {
        if (!tree_->isPixel(pixel)) {
            return;
        }
        capturePixelForRollback(pixel);
        capturePixelForRollback(tree_->prevProperPart_[static_cast<std::size_t>(pixel)]);
        capturePixelForRollback(tree_->nextProperPart_[static_cast<std::size_t>(pixel)]);
    }
 
    void prepareFreeListGrowth(std::size_t count) {
        if (!recoverable_ || count == 0) {
            return;
        }
        ensureRollbackJournal();
        rollbackJournal_->freeListMutations.reserve(rollbackJournal_->freeListMutations.size() + count);
        tree_->freeNodeIds_.reserve(tree_->freeNodeIds_.size() + count);
    }
 
    void recordFreeListGrowth(std::size_t previousSize) noexcept {
        if (!rollbackJournal_) {
            return;
        }
        for (std::size_t i = previousSize; i < tree_->freeNodeIds_.size(); ++i) {
            rollbackJournal_->freeListMutations.push_back({FreeListMutation::Pushed, tree_->freeNodeIds_[i]});
        }
    }
 
    void restoreRollbackJournal() noexcept {
        if (!active_ || tree_ == nullptr || !recoverable_) {
            return;
        }
        if (!rollbackJournal_) {
            tree_->endEditSession();
            recoverable_ = false;
            active_ = false;
            return;
        }
 
        for (auto it = rollbackJournal_->freeListMutations.rbegin(); it != rollbackJournal_->freeListMutations.rend(); ++it) {
            if (it->mutation == FreeListMutation::Pushed) {
                assert(!tree_->freeNodeIds_.empty());
                assert(tree_->freeNodeIds_.back() == it->node);
                tree_->freeNodeIds_.pop_back();
            } else {
                tree_->freeNodeIds_.push_back(it->node);
            }
        }
 
        const std::size_t originalSlots = rollbackJournal_->originalNodeSlots;
        tree_->nodeParent_.resize(originalSlots);
        tree_->firstChild_.resize(originalSlots);
        tree_->nextSibling_.resize(originalSlots);
        tree_->prevSibling_.resize(originalSlots);
        tree_->lastChild_.resize(originalSlots);
        tree_->numChildrenByNode_.resize(originalSlots);
        tree_->alive_.resize(originalSlots);
        tree_->properHead_.resize(originalSlots);
        tree_->properTail_.resize(originalSlots);
        tree_->properPartCardinalityByNode_.resize(originalSlots);
 
        for (const NodeRollbackState& state : rollbackJournal_->nodes) {
            const std::size_t slot = static_cast<std::size_t>(state.node);
            tree_->nodeParent_[slot] = state.parent;
            tree_->firstChild_[slot] = state.firstChild;
            tree_->nextSibling_[slot] = state.nextSibling;
            tree_->prevSibling_[slot] = state.prevSibling;
            tree_->lastChild_[slot] = state.lastChild;
            tree_->numChildrenByNode_[slot] = state.numChildren;
            tree_->alive_[slot] = state.alive;
            tree_->properHead_[slot] = state.properHead;
            tree_->properTail_[slot] = state.properTail;
            tree_->properPartCardinalityByNode_[slot] = state.properPartCardinality;
        }
 
        for (const PixelRollbackState& state : rollbackJournal_->pixels) {
            const std::size_t slot = static_cast<std::size_t>(state.pixel);
            tree_->smallestNodeMap_[slot] = state.smallestNodeId;
            tree_->nextProperPart_[slot] = state.next;
            tree_->prevProperPart_[slot] = state.previous;
        }
 
        tree_->rootNodeId_ = rollbackJournal_->root;
        tree_->numNodes_ = rollbackJournal_->numNodes;
        tree_->preservedExternalNodeIdOffset_ = rollbackJournal_->preservedExternalNodeIdOffset;
        tree_->nodeStructureVersion_ = rollbackJournal_->nodeStructureVersion;
        tree_->topologyVersion_ = rollbackJournal_->topologyVersion;
        tree_->properPartVersion_ = rollbackJournal_->properPartVersion;
        tree_->mutationVersion_ = rollbackJournal_->mutationVersion;
        tree_->invalidateDfsIntervalCache();
        tree_->invalidateLcaCache();
        tree_->endEditSession();
        rollbackJournal_.reset();
        recoverable_ = false;
        active_ = false;
    }
 
    [[nodiscard]] static bool isDetached(const MorphologicalTree& tree, NodeId node) noexcept {
        return tree.isAlive(node) && node != tree.rootNodeId_ && tree.nodeParent_[static_cast<std::size_t>(node)] == node;
    }
 
    void recordDetachedTransition(bool wasDetached, bool isNowDetached) noexcept {
        if (invariantsEstablishedByConstruction_) {
            return;
        }
        detachedNodeBalance_ += static_cast<int>(isNowDetached) - static_cast<int>(wasDetached);
    }
 
    [[nodiscard]] static bool isUnsupportedLeaf(const MorphologicalTree& tree, NodeId node) noexcept {
        return tree.isAlive(node) && tree.numChildrenByNode_[static_cast<std::size_t>(node)] == 0 &&
               tree.properPartCardinalityByNode_[static_cast<std::size_t>(node)] == 0;
    }
 
    void recordUnsupportedLeafTransition(bool wasUnsupported, bool isNowUnsupported) noexcept {
        if (invariantsEstablishedByConstruction_) {
            return;
        }
        unsupportedLeafBalance_ += static_cast<int>(isNowUnsupported) - static_cast<int>(wasUnsupported);
    }
 
    void touch(NodeId node) {
        if (invariantsEstablishedByConstruction_) {
            return;
        }
        try {
            static_cast<void>(touchedNodes_.insert(node));
        } catch (...) {
            incrementalValidationSupported_ = false;
            throw;
        }
    }
 
  public:
    TreeEditor(const TreeEditor&) = delete;
    TreeEditor& operator=(const TreeEditor&) = delete;
 
    TreeEditor(TreeEditor&& other) noexcept
        : tree_(other.tree_), active_(other.active_), recoverable_(other.recoverable_), rollbackJournal_(std::move(other.rollbackJournal_)),
          touchedNodes_(std::move(other.touchedNodes_)), detachedNodeBalance_(other.detachedNodeBalance_),
          unsupportedLeafBalance_(other.unsupportedLeafBalance_), incrementalValidationSupported_(other.incrementalValidationSupported_),
          invariantsEstablishedByConstruction_(other.invariantsEstablishedByConstruction_) {
        other.tree_ = nullptr;
        other.active_ = false;
        other.recoverable_ = false;
        other.rollbackJournal_.reset();
        other.detachedNodeBalance_ = 0;
        other.unsupportedLeafBalance_ = 0;
        other.incrementalValidationSupported_ = false;
        other.invariantsEstablishedByConstruction_ = false;
    }
 
    TreeEditor& operator=(TreeEditor&&) = delete;
 
    ~TreeEditor() { restoreRollbackJournal(); }
 
    [[nodiscard]] bool canRollback() const noexcept { return active_ && recoverable_; }
 
    void rollback() {
        if (!active_ || tree_ == nullptr) {
            throw std::logic_error("TreeEditor::rollback requires an active edit session.");
        }
        if (!recoverable_) {
            throw std::logic_error("TreeEditor::rollback is unavailable for the internal journal-free editor.");
        }
        restoreRollbackJournal();
    }
 
    [[nodiscard("Discarding a detached node id makes the staged edit impossible to complete safely")]] NodeId createDetachedNode() {
        MorphologicalTree& t = tree();
        if (invariantsEstablishedByConstruction_) {
            return t.createDetachedNode();
        }
 
        ensureRollbackJournal();
        const bool reusesFreeSlot = !t.freeNodeIds_.empty();
        const NodeId candidate = reusesFreeSlot ? t.freeNodeIds_.back() : static_cast<NodeId>(t.nodeParent_.size());
        captureNodeForRollback(candidate);
        if (reusesFreeSlot) {
            rollbackJournal_->freeListMutations.reserve(rollbackJournal_->freeListMutations.size() + 1);
            rollbackJournal_->freeListMutations.push_back({FreeListMutation::Popped, candidate});
        }
        const NodeId nodeId = t.createDetachedNode();
        recordDetachedTransition(false, isDetached(t, nodeId));
        recordUnsupportedLeafTransition(false, isUnsupportedLeaf(t, nodeId));
        touch(nodeId);
        return nodeId;
    }
 
    void detach(NodeId nodeId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(nodeId)) {
            throw std::invalid_argument("TreeEditor::detach requires a live node.");
        }
        if (t.isRoot(nodeId)) {
            throw std::invalid_argument("TreeEditor::detach cannot detach the connected root.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.detachNode(nodeId);
            return;
        }
        const NodeId oldParent = t.parent(nodeId);
        captureNodeLinkNeighborhood(nodeId);
        touch(nodeId);
        const bool wasDetached = isDetached(t, nodeId);
        const bool oldParentWasUnsupported = isUnsupportedLeaf(t, oldParent);
        t.detachNode(nodeId);
        recordDetachedTransition(wasDetached, isDetached(t, nodeId));
        recordUnsupportedLeafTransition(oldParentWasUnsupported, isUnsupportedLeaf(t, oldParent));
    }
 
    void reparent(NodeId nodeId, NodeId newParentId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(nodeId) || !t.isAlive(newParentId)) {
            throw std::invalid_argument("TreeEditor::reparent requires live node ids.");
        }
        if (t.isRoot(nodeId)) {
            throw std::invalid_argument("TreeEditor::reparent cannot move the connected root.");
        }
        if (nodeId == newParentId) {
            throw std::invalid_argument("TreeEditor::reparent requires distinct node ids.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.moveNode(nodeId, newParentId);
            return;
        }
        const NodeId oldParent = t.parent(nodeId);
        captureNodeLinkNeighborhood(nodeId);
        captureNodeForRollback(newParentId);
        captureNodeForRollback(t.lastChild_[static_cast<std::size_t>(newParentId)]);
        touch(nodeId);
        const bool wasDetached = isDetached(t, nodeId);
        const bool oldParentWasUnsupported = isUnsupportedLeaf(t, oldParent);
        const bool newParentWasUnsupported = isUnsupportedLeaf(t, newParentId);
        t.moveNode(nodeId, newParentId);
        recordDetachedTransition(wasDetached, isDetached(t, nodeId));
        recordUnsupportedLeafTransition(oldParentWasUnsupported, isUnsupportedLeaf(t, oldParent));
        if (oldParent != newParentId) {
            recordUnsupportedLeafTransition(newParentWasUnsupported, isUnsupportedLeaf(t, newParentId));
        }
    }
 
    void attach(NodeId parentId, NodeId detachedNodeId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(parentId) || !t.isAlive(detachedNodeId)) {
            throw std::invalid_argument("TreeEditor::attach requires live node ids.");
        }
        if (parentId == detachedNodeId) {
            throw std::invalid_argument("TreeEditor::attach requires distinct node ids.");
        }
        if (t.parent(detachedNodeId) != detachedNodeId) {
            throw std::invalid_argument("TreeEditor::attach expects a detached self-parented node.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.attachNode(parentId, detachedNodeId);
            return;
        }
        captureNodeLinkNeighborhood(detachedNodeId);
        captureNodeForRollback(parentId);
        captureNodeForRollback(t.lastChild_[static_cast<std::size_t>(parentId)]);
        touch(detachedNodeId);
        const bool wasDetached = isDetached(t, detachedNodeId);
        const bool parentWasUnsupported = isUnsupportedLeaf(t, parentId);
        t.attachNode(parentId, detachedNodeId);
        recordDetachedTransition(wasDetached, isDetached(t, detachedNodeId));
        recordUnsupportedLeafTransition(parentWasUnsupported, isUnsupportedLeaf(t, parentId));
    }
 
    void moveChildren(NodeId parentId, NodeId sourceId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(parentId) || !t.isAlive(sourceId)) {
            throw std::invalid_argument("TreeEditor::moveChildren requires live node ids.");
        }
        if (parentId == sourceId) {
            throw std::invalid_argument("TreeEditor::moveChildren requires distinct node ids.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.moveChildren(parentId, sourceId);
            return;
        }
        captureNodeForRollback(parentId);
        captureNodeForRollback(sourceId);
        captureNodeForRollback(t.lastChild_[static_cast<std::size_t>(parentId)]);
        for (NodeId child = t.firstChild_[static_cast<std::size_t>(sourceId)]; child != InvalidNode; child = t.nextSibling_[static_cast<std::size_t>(child)]) {
            captureNodeForRollback(child);
        }
        touch(parentId);
        const bool parentWasUnsupported = isUnsupportedLeaf(t, parentId);
        const bool sourceWasUnsupported = isUnsupportedLeaf(t, sourceId);
        t.moveChildren(parentId, sourceId);
        recordUnsupportedLeafTransition(parentWasUnsupported, isUnsupportedLeaf(t, parentId));
        recordUnsupportedLeafTransition(sourceWasUnsupported, isUnsupportedLeaf(t, sourceId));
    }
 
    void movePixelToProperPart(NodeId targetNodeId, NodeId sourceNodeId, PixelId pixel) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(targetNodeId) || !t.isAlive(sourceNodeId)) {
            throw std::invalid_argument("TreeEditor::movePixelToProperPart requires live node ids.");
        }
        if (targetNodeId == sourceNodeId) {
            throw std::invalid_argument("TreeEditor::movePixelToProperPart requires distinct source and target nodes.");
        }
        if (!t.isPixel(pixel)) {
            throw std::invalid_argument("TreeEditor::movePixelToProperPart requires a valid proper-part id.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.movePixelToProperPart(targetNodeId, sourceNodeId, pixel);
            return;
        }
        captureNodeForRollback(targetNodeId);
        captureNodeForRollback(sourceNodeId);
        capturePixelLinkNeighborhood(pixel);
        capturePixelForRollback(t.properTail_[static_cast<std::size_t>(targetNodeId)]);
        const bool targetWasUnsupported = isUnsupportedLeaf(t, targetNodeId);
        const bool sourceWasUnsupported = isUnsupportedLeaf(t, sourceNodeId);
        t.movePixelToProperPart(targetNodeId, sourceNodeId, pixel);
        recordUnsupportedLeafTransition(targetWasUnsupported, isUnsupportedLeaf(t, targetNodeId));
        recordUnsupportedLeafTransition(sourceWasUnsupported, isUnsupportedLeaf(t, sourceNodeId));
    }
 
    void mergeProperParts(NodeId targetNodeId, NodeId sourceNodeId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(targetNodeId) || !t.isAlive(sourceNodeId)) {
            throw std::invalid_argument("TreeEditor::mergeProperParts requires live node ids.");
        }
        if (targetNodeId == sourceNodeId) {
            throw std::invalid_argument("TreeEditor::mergeProperParts requires distinct source and target nodes.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.mergeProperParts(targetNodeId, sourceNodeId);
            return;
        }
        captureNodeForRollback(targetNodeId);
        captureNodeForRollback(sourceNodeId);
        capturePixelForRollback(t.properTail_[static_cast<std::size_t>(targetNodeId)]);
        for (PixelId pixel = t.properHead_[static_cast<std::size_t>(sourceNodeId)]; pixel != InvalidPixel;
             pixel = t.nextProperPart_[static_cast<std::size_t>(pixel)]) {
            capturePixelForRollback(pixel);
        }
        const bool targetWasUnsupported = isUnsupportedLeaf(t, targetNodeId);
        const bool sourceWasUnsupported = isUnsupportedLeaf(t, sourceNodeId);
        t.mergeProperParts(targetNodeId, sourceNodeId);
        recordUnsupportedLeafTransition(targetWasUnsupported, isUnsupportedLeaf(t, targetNodeId));
        recordUnsupportedLeafTransition(sourceWasUnsupported, isUnsupportedLeaf(t, sourceNodeId));
    }
 
    void removeChild(NodeId parentNodeId, NodeId childId, bool releaseNodeFlag) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(parentNodeId) || !t.isAlive(childId)) {
            throw std::invalid_argument("TreeEditor::removeChild requires live node ids.");
        }
        if (!t.hasChild(parentNodeId, childId)) {
            throw std::invalid_argument("TreeEditor::removeChild requires a direct parent-child relation.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.removeChild(parentNodeId, childId, releaseNodeFlag);
            return;
        }
        captureNodeLinkNeighborhood(childId);
        captureNodeForRollback(parentNodeId);
        const bool willRelease =
            releaseNodeFlag && t.numChildrenByNode_[static_cast<std::size_t>(childId)] == 0 && t.properPartCardinalityByNode_[static_cast<std::size_t>(childId)] == 0;
        if (willRelease) {
            prepareFreeListGrowth(1);
        }
        touch(childId);
        const bool wasDetached = isDetached(t, childId);
        const bool parentWasUnsupported = isUnsupportedLeaf(t, parentNodeId);
        const bool childWasUnsupported = isUnsupportedLeaf(t, childId);
        const std::size_t freeListSize = t.freeNodeIds_.size();
        t.removeChild(parentNodeId, childId, releaseNodeFlag);
        recordFreeListGrowth(freeListSize);
        recordDetachedTransition(wasDetached, isDetached(t, childId));
        recordUnsupportedLeafTransition(parentWasUnsupported, isUnsupportedLeaf(t, parentNodeId));
        recordUnsupportedLeafTransition(childWasUnsupported, isUnsupportedLeaf(t, childId));
    }
 
    void releaseNode(NodeId nodeId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(nodeId)) {
            throw std::invalid_argument("TreeEditor::releaseNode requires a live node.");
        }
        if (t.isRoot(nodeId)) {
            throw std::invalid_argument("TreeEditor::releaseNode cannot release the connected root.");
        }
        if (t.parent(nodeId) != nodeId) {
            throw std::invalid_argument("TreeEditor::releaseNode expects a detached self-parented node.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.releaseNode(nodeId);
            return;
        }
        captureNodeForRollback(nodeId);
        const bool willRelease = t.numChildrenByNode_[static_cast<std::size_t>(nodeId)] == 0 && t.properPartCardinalityByNode_[static_cast<std::size_t>(nodeId)] == 0;
        if (willRelease) {
            prepareFreeListGrowth(1);
        }
        const bool wasDetached = isDetached(t, nodeId);
        const bool wasUnsupported = isUnsupportedLeaf(t, nodeId);
        const std::size_t freeListSize = t.freeNodeIds_.size();
        t.releaseNode(nodeId);
        recordFreeListGrowth(freeListSize);
        recordDetachedTransition(wasDetached, isDetached(t, nodeId));
        recordUnsupportedLeafTransition(wasUnsupported, isUnsupportedLeaf(t, nodeId));
    }
 
    void setRoot(NodeId nodeId) {
        MorphologicalTree& t = tree();
        if (!t.isAlive(nodeId)) {
            throw std::invalid_argument("TreeEditor::setRoot requires a live node.");
        }
        if (invariantsEstablishedByConstruction_) {
            t.setRoot(nodeId);
            return;
        }
        const NodeId oldRoot = t.root();
        const NodeId oldParent = t.parent(nodeId);
        captureNodeForRollback(oldRoot);
        captureNodeLinkNeighborhood(nodeId);
        captureNodeForRollback(oldParent);
        touch(oldRoot);
        touch(oldParent);
        touch(nodeId);
        const bool oldRootWasDetached = isDetached(t, oldRoot);
        const bool nodeWasDetached = isDetached(t, nodeId);
        t.setRoot(nodeId);
        recordDetachedTransition(oldRootWasDetached, isDetached(t, oldRoot));
        if (nodeId != oldRoot) {
            recordDetachedTransition(nodeWasDetached, isDetached(t, nodeId));
        }
    }
 
    void pruneNode(NodeId nodeId) {
        MorphologicalTree& t = tree();
        if (invariantsEstablishedByConstruction_) {
            EditSessionPause pause(t);
            t.pruneNode(nodeId);
            return;
        }
        incrementalValidationSupported_ = false;
 
        if (t.isAlive(nodeId) && !t.isRoot(nodeId)) {
            const NodeId parent = t.nodeParent_[static_cast<std::size_t>(nodeId)];
            if (parent != InvalidNode && parent != nodeId) {
                std::vector<NodeId> subtree;
                subtree.push_back(nodeId);
                for (std::size_t i = 0; i < subtree.size(); ++i) {
                    const NodeId current = subtree[i];
                    for (NodeId child = t.firstChild_[static_cast<std::size_t>(current)]; child != InvalidNode;
                         child = t.nextSibling_[static_cast<std::size_t>(child)]) {
                        subtree.push_back(child);
                    }
                }
 
                captureNodeForRollback(parent);
                captureNodeLinkNeighborhood(nodeId);
                capturePixelForRollback(t.properTail_[static_cast<std::size_t>(parent)]);
                for (NodeId current : subtree) {
                    captureNodeForRollback(current);
                    for (PixelId pixel = t.properHead_[static_cast<std::size_t>(current)]; pixel != InvalidPixel;
                         pixel = t.nextProperPart_[static_cast<std::size_t>(pixel)]) {
                        capturePixelForRollback(pixel);
                    }
                }
                prepareFreeListGrowth(subtree.size());
            }
        }
 
        const std::size_t freeListSize = t.freeNodeIds_.size();
        EditSessionPause pause(t);
        t.pruneNode(nodeId);
        recordFreeListGrowth(freeListSize);
    }
 
    void mergeNodeIntoParent(NodeId nodeId) {
        MorphologicalTree& t = tree();
        if (invariantsEstablishedByConstruction_) {
            EditSessionPause pause(t);
            t.mergeNodeIntoParent(nodeId);
            return;
        }
        incrementalValidationSupported_ = false;
 
        if (t.isAlive(nodeId) && !t.isRoot(nodeId)) {
            const NodeId parent = t.nodeParent_[static_cast<std::size_t>(nodeId)];
            if (parent != InvalidNode && parent != nodeId) {
                captureNodeForRollback(parent);
                captureNodeLinkNeighborhood(nodeId);
                capturePixelForRollback(t.properTail_[static_cast<std::size_t>(parent)]);
                for (PixelId pixel = t.properHead_[static_cast<std::size_t>(nodeId)]; pixel != InvalidPixel;
                     pixel = t.nextProperPart_[static_cast<std::size_t>(pixel)]) {
                    capturePixelForRollback(pixel);
                }
                for (NodeId child = t.firstChild_[static_cast<std::size_t>(nodeId)]; child != InvalidNode;
                     child = t.nextSibling_[static_cast<std::size_t>(child)]) {
                    captureNodeForRollback(child);
                }
                prepareFreeListGrowth(1);
            }
        }
 
        const std::size_t freeListSize = t.freeNodeIds_.size();
        EditSessionPause pause(t);
        t.mergeNodeIntoParent(nodeId);
        recordFreeListGrowth(freeListSize);
    }
 
    [[nodiscard]] bool hasDetachedAliveNodes() const noexcept { return active_ && tree_ != nullptr && tree_->hasDetachedAliveNodes(); }
 
  private:
    [[nodiscard]] TreeValidationResult validateIncrementalTopology(bool changedParentCyclesExcluded) const noexcept {
        try {
            if (!active_ || tree_ == nullptr) {
                return {false, "Incremental topology validation requires an active edit session."};
            }
            if (detachedNodeBalance_ != 0) {
                return {false, "Incremental topology validation found detached alive nodes."};
            }
            if (unsupportedLeafBalance_ != 0) {
                return {false, "Incremental topology validation found a live node whose subtree support is empty."};
            }
 
            const NodeId root = tree_->root();
            if (!tree_->isAlive(root) || tree_->parent(root) != root) {
                return {false, "Incremental topology validation requires a live self-parented root."};
            }
 
            const int numNodes = tree_->numNodes();
            for (NodeId node : touchedNodes_.entries()) {
                if (!tree_->isAlive(node)) {
                    continue;
                }
 
                if (!changedParentCyclesExcluded) {
                    NodeId cursor = node;
                    int pathLength = 0;
                    while (cursor != root) {
                        if (!tree_->isAlive(cursor)) {
                            return {false, "Incremental topology validation found a parent path outside the alive node domain."};
                        }
                        const NodeId parent = tree_->parent(cursor);
                        if (parent == InvalidNode || parent == cursor || !tree_->isAlive(parent)) {
                            return {false, "Incremental topology validation found a detached or invalid parent path."};
                        }
                        cursor = parent;
                        if (++pathLength > numNodes) {
                            return {false, "Incremental topology validation found a parent cycle."};
                        }
                    }
                }
            }
            return {true, ""};
        } catch (const std::exception& ex) {
            return {false, ex.what()};
        } catch (...) {
            return {false, "Incremental topology validation failed with an unknown error."};
        }
    }
 
    [[nodiscard]] IncrementalProof proveIncrementalImpl(bool changedParentCyclesExcluded) {
        TreeValidationResult result;
        TreeEditValidationMode validationMode = TreeEditValidationMode::Incremental;
        if (invariantsEstablishedByConstruction_ && incrementalValidationSupported_) {
            result = {true, ""};
        } else if (incrementalValidationSupported_) {
            result = validateIncrementalTopology(changedParentCyclesExcluded);
        } else {
            result = validate();
            validationMode = TreeEditValidationMode::Complete;
        }
        if (!result.ok) {
            throw std::runtime_error(result.message);
        }
#ifndef NDEBUG
        if (validationMode == TreeEditValidationMode::Incremental) {
            const TreeValidationResult oracle = validate();
            if (!oracle.ok) {
                throw std::runtime_error(std::string("Incremental topology proof disagrees with the complete validation oracle: ") + oracle.message);
            }
        }
#endif
        return IncrementalProof(*this, validationMode);
    }
 
    [[nodiscard]] IncrementalProof proveIncrementalWithStrictAltitudeAcyclicity() { return proveIncrementalImpl(true); }
 
  public:
    [[nodiscard]] IncrementalProof proveIncremental() { return proveIncrementalImpl(false); }
 
    void commit(IncrementalProof&& proof) {
        if (!active_ || tree_ == nullptr || proof.editor_ != this || proof.tree_ != tree_ || proof.mutationVersion_ != tree_->getMutationVersion()) {
            throw std::logic_error("Incremental topology proof is stale or belongs to another edit session.");
        }
 
        const TreeEditValidationMode validationMode = proof.validationMode_;
        proof.editor_ = nullptr;
        proof.tree_ = nullptr;
        finishCommit(validationMode);
    }
 
    [[nodiscard]] TreeValidationResult validate() const noexcept {
        if (!active_ || tree_ == nullptr) {
            return {false, "TreeEditor validation requires an active edit session."};
        }
        return tree_->validateConnectedRootedTreeResult();
    }
 
    [[nodiscard("Inspect the validation result or use commit() for exception-based failure handling")]] TreeValidationResult validateAndCommit() noexcept {
        TreeValidationResult result = validate();
        if (!result.ok) {
            return result;
        }
        finishCommit(TreeEditValidationMode::Complete);
        return result;
    }
 
    void commit() {
        TreeValidationResult result = validateAndCommit();
        if (!result.ok) {
            throw std::runtime_error(result.message);
        }
    }
};
 
inline TreeEditor MorphologicalTree::edit() { return TreeEditor(*this); }
 
} // namespace mmcfilters