mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t > Class Template Reference

Incremental updater for a paired min-tree / max-tree state. More...

#include <DualMinMaxTreeIncrementalFilter.hpp>

Public Member Functions
	DualMinMaxTreeIncrementalFilter (tree_t *mintree, tree_t *maxtree, const RegularGridAdjacency2D &graph)
	Creates an adjuster for externally owned min/max-tree states.
void	setAttributeComputer (const attribute_computer_t &computerMin, const attribute_computer_t &computerMax, std::vector< double > &bufferMin, std::vector< double > &bufferMax)
	Registers incremental attribute computers and their external buffers.
void	setAttributeComputer (const attribute_computer_t &computer, std::vector< double > &bufferMin, std::vector< double > &bufferMax)
	Registers one shared incremental attribute computer for both trees.
void	pruneMaxTreeAndUpdateMinTree (const std::vector< NodeId > &nodesToPrune)
	Prunes max-tree subtrees and updates the min-tree before each prune.
void	pruneMinTreeAndUpdateMaxTree (const std::vector< NodeId > &nodesToPrune)
	Prunes min-tree subtrees and updates the max-tree before each prune.

Static Public Member Functions
static constexpr bool	usesDenseLevelBackend ()
	Reports whether this altitude type uses dense per-level buckets.
static constexpr int	denseLevelBackendMaxBits ()
	Returns the bit-width threshold for dense bucket selection.

Detailed Description

template<AltitudeValue altitude_t>
class mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >

Incremental updater for a paired min-tree / max-tree state.

This class ports the Higra dual component-tree adjustment algorithm to this repository's ValuedMorphologicalTree<T> representation. It implements the update-rather-than-rebuild strategy used for efficient connected alternating sequential filters: when a rooted subtree is removed from one component tree, the dual tree is updated in place so both trees remain consistent with the same filtered image.

The algorithmic structure is intentionally kept the same:

• a rooted subtree is selected for pruning in the primal tree;
• its full support defines the proper-part set C;
• valid graph-adjacent components around C are collected in the dual tree;
• each relevant ancestor chain is climbed once;
• collected nodes are bucketed by altitude and swept in tree order;
• local unions, frontier reattachments, and empty-node contractions update the dual tree without rebuilding it globally.

Public usage model:

• construct the helper from an externally owned min-tree / max-tree pair and their shared adjacency relation;
• optionally register incremental attribute computers and attribute buffers to refresh after local edits;
• call either pruneMaxTreeAndUpdateMinTree(...) or pruneMinTreeAndUpdateMaxTree(...).

State managed by this class:

• two mutable valuedTree component trees (mintree_, maxtree_);
• one adjacency relation shared by both trees;
• optional incremental attribute computers and two external attribute buffers;
• transient merge buckets, frontier roots, proper-part sets, and mark sets reused across update steps.

Ownership and lifetime:

• this class does not own the trees, adjacency relation, attribute computers, or attribute buffers;
• callers must keep these objects alive for the whole lifetime of the filter;
• external buffers must be indexed on this project's internal node-id space.

Representation notes:

• node ids are this project's dense internal node ids, not Higra global ids;
• altitudes are read from ValuedMorphologicalTree<T>::nodeAltitude;
• this is a mutable valued-tree boundary, not a ValuedMorphologicalTreeView boundary: topology, smallest-node mapping, owned altitude, and optional dynamic attributes are updated in lockstep;
• the altitude_t template parameter is the owned tree altitude type and also controls merge-bucket keys/backends;
• low-level edits go through ValuedMorphologicalTreeEditor<T> and publish with the generic move-only proof protocol; the update establishes its invariants during the existing algorithmic passes, while assertion-enabled builds retain the complete validation oracle;
• optional attribute buffers are kept in sync through DynamicTreeAttributeComputer<std::uint8_t>.

Internal notation follows the original adjustment routine:

• nodeCa: implementation-side representative of the extremal node in the dual tree that contains the set C at level a;
• b: altitude of the parent of the subtree removed in the primal tree;
• frontierNodesAboveB: roots that leave the merge interval and are reattached when the sweep reaches the boundary level;
• properPartSetC_: pixels directly removed or relocated in the dual tree.

Backend selection for mergeNodesByLevel:

• dense array-based buckets for small integral altitude domains, up to MMCFILTERS_COMPONENT_TREE_ADJUSTMENT_DENSE_MAX_BITS bits;
• sparse ordered-map buckets for larger integral domains and floating-point altitudes.

The expected cost remains local to the affected region. The dominant terms are the same as in the Higra implementation: collecting C, visiting adjacent seeds, climbing relevant ancestor chains once, sweeping the active altitude buckets, and contracting the nodes actually emptied by the step. The class never rebuilds the dual tree globally as part of an adjustment.

Definition at line 107 of file DualMinMaxTreeIncrementalFilter.hpp.

Constructor & Destructor Documentation

DualMinMaxTreeIncrementalFilter()

template<AltitudeValue altitude_t>

mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::DualMinMaxTreeIncrementalFilter ( tree_t *  mintree, tree_t *  maxtree, const RegularGridAdjacency2D &  graph  )

inline

Creates an adjuster for externally owned min/max-tree states.

Parameters

mintree	Mutable min-tree state.
maxtree	Mutable max-tree state.
graph	Shared image-domain adjacency relation.

The constructor sizes all generation-stamped mark sets from the current node/proper-part spaces of the two trees. The tree topology is expected to keep these slot spaces stable under local releases performed by the adjuster.

Definition at line 1270 of file DualMinMaxTreeIncrementalFilter.hpp.

Member Function Documentation

denseLevelBackendMaxBits()

template<AltitudeValue altitude_t>

static constexpr int mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::denseLevelBackendMaxBits ( )

inlinestaticconstexpr

Returns the bit-width threshold for dense bucket selection.

Returns

The bit-width threshold for dense bucket selection.

Definition at line 1257 of file DualMinMaxTreeIncrementalFilter.hpp.

pruneMaxTreeAndUpdateMinTree()

template<AltitudeValue altitude_t>

void mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::pruneMaxTreeAndUpdateMinTree ( const std::vector< NodeId > &  nodesToPrune )

inline

Prunes max-tree subtrees and updates the min-tree before each prune.

Invalid, dead, and root nodes are ignored. For each valid max-tree root, the min-tree is updated first against the subtree that is about to be removed; then the max-tree subtree is pruned.

Parameters

nodesToPrune

Node identifiers selected for pruning.

Definition at line 1325 of file DualMinMaxTreeIncrementalFilter.hpp.

pruneMinTreeAndUpdateMaxTree()

template<AltitudeValue altitude_t>

void mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::pruneMinTreeAndUpdateMaxTree ( const std::vector< NodeId > &  nodesToPrune )

inline

Prunes min-tree subtrees and updates the max-tree before each prune.

Invalid, dead, and root nodes are ignored. For each valid min-tree root, the max-tree is updated first against the subtree that is about to be removed; then the min-tree subtree is pruned.

Parameters

nodesToPrune

Node identifiers selected for pruning.

Definition at line 1347 of file DualMinMaxTreeIncrementalFilter.hpp.

setAttributeComputer() [1/2]

template<AltitudeValue altitude_t>

void mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::setAttributeComputer ( const attribute_computer_t &  computer, std::vector< double > &  bufferMin, std::vector< double > &  bufferMax  )

inline

Registers one shared incremental attribute computer for both trees.

Parameters

computer	Flag controlling computer.
bufferMin	Min-tree attribute buffer.
bufferMax	Max-tree attribute buffer.

Definition at line 1312 of file DualMinMaxTreeIncrementalFilter.hpp.

setAttributeComputer() [2/2]

template<AltitudeValue altitude_t>

void mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::setAttributeComputer ( const attribute_computer_t &  computerMin, const attribute_computer_t &  computerMax, std::vector< double > &  bufferMin, std::vector< double > &  bufferMax  )

inline

Registers incremental attribute computers and their external buffers.

The buffers are not owned by the adjuster. They must remain alive and indexed by internal NodeId while pruning/update calls are executed.

Parameters

computerMin	Flag controlling computer min.
computerMax	Flag controlling computer max.
bufferMin	Min-tree attribute buffer.
bufferMax	Max-tree attribute buffer.

Definition at line 1297 of file DualMinMaxTreeIncrementalFilter.hpp.

usesDenseLevelBackend()

template<AltitudeValue altitude_t>

static constexpr bool mmcfilters::adjust::DualMinMaxTreeIncrementalFilter< altitude_t >::usesDenseLevelBackend ( )

inlinestaticconstexpr

Reports whether this altitude type uses dense per-level buckets.

Returns

True if this altitude type uses dense per-level buckets; otherwise false.

Definition at line 1250 of file DualMinMaxTreeIncrementalFilter.hpp.

---

The documentation for this class was generated from the following file:

• mmcfilters/trees/adjust/DualMinMaxTreeIncrementalFilter.hpp