Mutable connected-subset tree on a finite pixel domain. More...

#include <MorphologicalTree.hpp>

Classes
class	AliveNodeIterator
	Iterator over live node ids in the dense internal-node domain. More...

class	AliveNodeRange
	Range wrapper for iterating over live node ids. More...

class	AncestorNodeIterator
	Iterator that walks from a node towards the root. More...

class	AncestorNodeRange
	Range wrapper for rootward path traversal. More...

class	BreadthFirstNodeIterator
	Breadth-first iterator over one subtree. More...

class	BreadthFirstNodeRange
	Range wrapper for breadth-first subtree traversal. More...

class	ChildrenIterator
	Iterator over the direct children of one node. More...

class	ChildrenRange
	Range wrapper for direct-child iteration. More...

class	DescendantNodeRange
	Range wrapper over the proper descendants of one node. More...

class	NodeSupportIterator
	Iterator over all pixels in one node support. More...

class	NodeSupportRange
	Range wrapper for node-support pixel iteration. More...

class	PathBetweenNodesIterator
	Iterator over a materialised path between two nodes. More...

class	PathBetweenNodesRange
	Range wrapper for the path connecting two nodes in the same component. More...

class	PostOrderNodeIterator
	Post-order iterator over one subtree. More...

class	PostOrderNodeRange
	Range wrapper for post-order subtree traversal. More...

class	ProperPartIterator
	Iterator over the pixels in one node's proper part. More...

class	ProperPartRange
	Range wrapper for direct proper-part iteration. More...

class	SubtreeNodeIterator
	Depth-first iterator over a subtree in pre-order. More...

class	SubtreeNodeRange
	Range wrapper for pre-order subtree traversal. More...

Public Member Functions
	MorphologicalTree (const MorphologicalTree &)=delete
	Copying is disabled to keep topology storage explicit.

MorphologicalTree &	operator= (const MorphologicalTree &)=delete
	Copy assignment is disabled to keep topology storage explicit.

	MorphologicalTree (MorphologicalTree &&other)
	Moves a complete committed topology.

MorphologicalTree &	operator= (MorphologicalTree &&other)
	Move-assigns a complete committed topology.

virtual	~MorphologicalTree ()=default
	Destroys the topology storage and cached traversal state.

	MorphologicalTree (detail::MorphologicalTreeConstructionTag, std::span< const NodeId > nodeParent, std::span< const NodeId > smallestNodeMap, NodeId root, int rows, int columns, MorphologicalTreeSemantics semantics)
	Tag-protected import from native mmcfilters topology buffers.

	MorphologicalTree (detail::MorphologicalTreeConstructionTag, std::span< const NodeId > nodeParent, std::span< const NodeId > smallestNodeMap, NodeId root, MorphologicalTreeSemantics semantics)
	Imports a native hierarchy over an abstract finite pixel set.

MorphologicalTree	clone () const
	Creates an independent copy of the structural tree state.

std::size_t	getMutationVersion () const noexcept
	Returns the monotonic mutation counter used by read-only views.

void	requireMutationVersion (std::size_t expectedVersion, const char *context) const
	Rejects stale read-only views that captured an older mutation version.

int	numInternalNodeSlots () const
	Returns the size of the dense internal-node id domain.

int	numPixels () const
	Returns the cardinality of the pixel domain.

int	getNumHigraNodes () const
	Returns the size of the preserved imported Higra node-id domain.

int	getNodeIdSpaceSize (NodeIdSpace outputSpace) const
	Returns the size of the requested node-id domain.

NodeId	getHigraNodeId (NodeId nodeId) const noexcept
	Returns the preserved imported Higra node id for one live tree node.

NodeId	root () const
	Returns the current hierarchy root.

bool	isNode (NodeId nodeId) const noexcept
	Tests whether `nodeId` belongs to the internal-node id domain.

bool	isPixel (PixelId pixel) const noexcept
	Tests whether `pixel` belongs to the pixel domain.

bool	isAlive (NodeId nodeId) const
	Tests whether a node slot currently represents a live node.

bool	isRoot (NodeId nodeId) const
	Tests whether `nodeId` is the current root.

int	getNumFreeNodeSlots () const
	Returns the number of currently reusable node slots.

int	numLeafNodes () const
	Counts the live nodes that currently have no children.

int	numChildren (NodeId nodeId) const
	Returns the number of direct children of `nodeId`.

int	numDescendants (NodeId nodeId) const
	Returns the number of internal descendants of `nodeId`.

int	numSiblings (NodeId nodeId) const
	Returns the number of siblings of `nodeId`.

int	dfsEntryIndex (NodeId nodeId) const
	Returns the zero-based DFS entry-event index of `nodeId`.

int	dfsExitIndex (NodeId nodeId) const
	Returns the zero-based DFS exit-event index of `nodeId`.

NodeId	getFirstChild (NodeId nodeId) const
	Returns the first direct child of `nodeId`, or `InvalidNode`.

NodeId	getNextSibling (NodeId nodeId) const
	Returns the next sibling of `nodeId`, or `InvalidNode`.

bool	isLeaf (NodeId nodeId) const
	Tests whether `nodeId` has no direct children.

int	properPartCardinality (NodeId nodeId) const
	Returns the cardinality of the proper part of `nodeId`.

bool	hasEmptyProperPart (NodeId nodeId) const
	Tests whether `nodeId` has an empty proper part.

bool	hasChild (NodeId parentNodeId, NodeId childId) const
	Tests whether `childId` is a direct child of `parentNodeId`.

NodeId	parent (NodeId nodeId) const
	Returns the direct parent of `nodeId`.

NodeId	smallestNode (PixelId pixel) const
	Returns the smallest node containing `pixel`.

std::span< const NodeId >	smallestNodeMap () const noexcept
	Returns the pixel-indexed smallest-node map.

std::vector< NodeId >	leaves () const
	Returns all live leaf nodes in the current hierarchy.

MorphologicalTreeKind	kind () const noexcept
	Returns the optional descriptive hierarchy-family label.

const MorphologicalTreeSemantics &	semantics () const noexcept
	Returns all generic semantic capabilities of this hierarchy.

NodeAltitudeOrder	nodeAltitudeOrder () const noexcept
	Returns the global parent-to-child altitude ordering constraint.

const MorphologicalTreeConstructionContext &	constructionContext () const noexcept
	Returns the typed construction context retained by this tree.

const SharedAdjacencyContext *	sharedAdjacencyContext () const noexcept
	Returns the shared-adjacency context, or `nullptr`.

const RegularGridAdjacency2D *	constructionAdjacency () const noexcept
	Returns the adjacency retained by a shared construction context.

const TopographicConvention *	topographicConvention () const noexcept
	Returns the topographic convention, or `nullptr`.

const ComplementaryAdjacencies *	complementaryAdjacencies () const noexcept
	Returns the complementary adjacencies explicitly retained by a topographic immersion.

int	numNodes () const noexcept
	Returns the number of currently live nodes.

bool	isEditing () const noexcept
	Tests whether a staged edit session is currently open.

const TreeEditValidationStatistics &	getEditValidationStatistics () const noexcept
	Returns validation-path counters for committed edit sessions.

void	requireNotEditing (const char *context) const
	Rejects operations that require a committed connected topology.

bool	hasDetachedAliveNodes () const noexcept
	Returns whether the tree currently contains alive detached nodes.

bool	hasGridDomain2D () const noexcept
	Tests whether pixel ids have an attached row/column layout.

const std::optional< GridDomain2D > &	gridDomain2D () const noexcept
	Returns the optional regular 2D pixel domain.

const GridDomain2D &	requireGridDomain2D (const char *context) const
	Returns the regular 2D domain or rejects a geometry-dependent call.

int	numRows () const
	Returns the number of rows in the regular 2D pixel domain.

int	numColumns () const
	Returns the number of columns in the regular 2D pixel domain.

void	validateConnectedRootedTree () const
	Validates one rooted tree with a complete smallest-node map and non-empty supports.

TreeValidationResult	validateConnectedRootedTreeResult () const noexcept
	Runs strong validation and returns the result instead of throwing.

bool	isTreeOfPartialPartitions () const
	Tests whether every live node has a non-empty proper part.

void	validateTreeOfPartialPartitions () const
	Validates the connected-subset invariants and the non-empty proper-part specialization.

bool	isAncestor (NodeId u, NodeId v) const
	Tests whether `u` is an ancestor of `v`.

bool	isDescendant (NodeId u, NodeId v) const
	Tests whether `u` is a descendant of `v`.

bool	isComparable (NodeId u, NodeId v) const
	Tests whether `u` and `v` are comparable in the ancestry order.

bool	isStrictAncestor (NodeId u, NodeId v) const
	Tests whether `u` is a strict ancestor of `v`.

bool	isStrictDescendant (NodeId u, NodeId v) const
	Tests whether `u` is a strict descendant of `v`.

bool	isStrictComparable (NodeId u, NodeId v) const
	Tests whether `u` and `v` are strictly comparable in the ancestry order.

NodeId	lowestCommonAncestor (NodeId u, NodeId v) const
	Returns the lowest common ancestor of `u` and `v`.

std::vector< NodeId >	lowestCommonAncestors (std::span< const std::pair< NodeId, NodeId > > queries) const
	Returns lowest common ancestors for a batch of node pairs.

AliveNodeRange	aliveNodeIds () const
	Returns a fail-fast range over all live node ids.

ChildrenRange	children (NodeId nodeId) const
	Returns a fail-fast range over the direct children of `nodeId`.

ProperPartRange	properPart (NodeId nodeId) const
	Returns a fail-fast range over the pixels in the proper part of `nodeId`.

NodeSupportRange	nodeSupport (NodeId nodeId) const
	Returns a fail-fast range over the pixels in the support of `nodeId`.

PostOrderNodeRange	postOrder () const
	Returns a post-order traversal range rooted at the connected root.

PostOrderNodeRange	postOrder (NodeId rootNodeId) const
	Returns a post-order traversal range rooted at `rootNodeId`.

BreadthFirstNodeRange	breadthFirstTraversal () const
	Returns a breadth-first traversal range rooted at the connected root.

BreadthFirstNodeRange	breadthFirstTraversal (NodeId rootNodeId) const
	Returns a breadth-first traversal range rooted at `rootNodeId`.

AncestorNodeRange	ancestors (NodeId nodeId) const
	Returns `nodeId` and its proper ancestors through the connected root.

PathBetweenNodesRange	getPathBetweenNodes (NodeId sourceNodeId, NodeId targetNodeId) const
	Returns the path that connects `sourceNodeId` and `targetNodeId`.

SubtreeNodeRange	subtreeNodes (NodeId nodeId) const
	Returns a pre-order traversal range over the subtree of `nodeId`.

DescendantNodeRange	descendants (NodeId nodeId) const
	Returns a range over all proper descendants of `nodeId`.

TreeEditor	edit ()
	Opens the only public entrypoint for staged structural mutations.

void	pruneNode (NodeId nodeId)
	Prunes the subtree of `nodeId`, moving all its support to the parent.

void	mergeNodeIntoParent (NodeId nodeId)
	Merges `nodeId` into its parent and releases the emptied slot.

Friends
class	TreeEditor

class	MorphologicalTreeFactory

class	detail::TreeKernelAccess

template<AltitudeValue T>
ValuedMorphologicalTree< T >	detail::materializeNativeHierarchy (NativeHierarchyOwned< T > &&hierarchy, std::optional< NodeId > preservedExternalNodeIdOffset, detail::MaterializedVersionPolicy versionPolicy)
	Allows the native hierarchy materializer to initialize owned topology buffers and construction metadata.

Detailed Description

Mutable connected-subset tree on a finite pixel domain.

MorphologicalTree is the central mutable hierarchy of this project. It can represent any rooted connected-subset tree model supported by the project. A morphological tree of partial partitions is the stricter case in which every node has a non-empty proper part. The class exposes a dense NodeId domain together with the smallest-node map, explicit parent/child links, linked pixel lists for the nodes' proper parts, optional regular 2D pixel metadata, and a small set of structural caches used by the public traversal and ancestry queries.

Data model:

pixels are indexed in the range [0, numPixels());
internal nodes are indexed by NodeId in the range [0, numInternalNodeSlots());
properPart(node) contains the pixels whose smallest node is node and may be empty;
nodeSupport(node) is the union of the proper parts in the node's subtree;
every node in a checked committed hierarchy has non-empty node support;
the root and detached nodes point to themselves as parent.

Main responsibilities:

expose mutable topology operations used by filters and adjusters;
provide structural traversals over live nodes, children, proper parts, node supports, and subtrees;
serve as the topology/smallest-node core used by valued wrappers such as ValuedMorphologicalTree<std::uint8_t>.

The class intentionally keeps only the canonical structural state and a small number of derived caches. Higher-level attribute computation is delegated to the incremental attribute computers in mmcfilters/attributes.

Definition at line 117 of file MorphologicalTree.hpp.

Constructor & Destructor Documentation

◆ MorphologicalTree() [1/3]

mmcfilters::MorphologicalTree::MorphologicalTree ( MorphologicalTree && other )

inline

Moves a complete committed topology.

Moving an owner with an active editor would leave that editor pointing at the moved-from object, so active edit sessions are rejected.

Parameters

other Object to compare with or transfer from.

Definition at line 1646 of file MorphologicalTree.hpp.

◆ MorphologicalTree() [2/3]

mmcfilters::MorphologicalTree::MorphologicalTree	(	detail::MorphologicalTreeConstructionTag	,
		std::span< const NodeId >	nodeParent,
		std::span< const NodeId >	smallestNodeMap,
		NodeId	root,
		int	rows,
		int	columns,
		MorphologicalTreeSemantics	semantics
	)

inline

Tag-protected import from native mmcfilters topology buffers.

This path is used by builders that already materialize internal-node parent links and a row-major smallest-node map. Nodes are not required to have a non-empty proper part, so the representation supports the general connected-subset tree model. The buffers are copied into canonical tree storage and validated as one connected rooted hierarchy in which every node has non-empty subtree support.

Parameters

nodeParent	Parent-node value.
smallestNodeMap	Pixel-indexed smallest node map.
root	Root node of the traversal.
rows	Number of rows in the domain.
columns	Number of columns in the domain.
semantics	Hierarchy semantics validated by the operation.

Definition at line 1700 of file MorphologicalTree.hpp.

◆ MorphologicalTree() [3/3]

mmcfilters::MorphologicalTree::MorphologicalTree	(	detail::MorphologicalTreeConstructionTag	,
		std::span< const NodeId >	nodeParent,
		std::span< const NodeId >	smallestNodeMap,
		NodeId	root,
		MorphologicalTreeSemantics	semantics
	)

inline

Imports a native hierarchy over an abstract finite pixel set.

No row/column interpretation is attached. Regular-grid reconstruction and geometry-dependent algorithms consequently reject this tree explicitly, while purely topological and support-based algorithms remain available.

Parameters

nodeParent	Parent-node value.
smallestNodeMap	Pixel-indexed smallest node map.
root	Root node of the traversal.
semantics	Hierarchy semantics validated by the operation.

Definition at line 1718 of file MorphologicalTree.hpp.

Member Function Documentation

◆ aliveNodeIds()

AliveNodeRange mmcfilters::MorphologicalTree::aliveNodeIds ( ) const

inline

Returns a fail-fast range over all live node ids.

Returns: A fail-fast range over all live node ids.

Definition at line 2683 of file MorphologicalTree.hpp.

◆ ancestors()

AncestorNodeRange mmcfilters::MorphologicalTree::ancestors ( NodeId nodeId ) const

inline

Returns nodeId and its proper ancestors through the connected root.

The queried node is the first element, so this range is inclusive of self. The connected root is the last element.

Parameters

nodeId Dense internal node identifier.

Returns: The inclusive ancestor chain from nodeId to the connected root.

Definition at line 2766 of file MorphologicalTree.hpp.

◆ breadthFirstTraversal() [1/2]

BreadthFirstNodeRange mmcfilters::MorphologicalTree::breadthFirstTraversal ( ) const

inline

Returns a breadth-first traversal range rooted at the connected root.

Returns: A breadth-first traversal range rooted at the connected root.

Definition at line 2744 of file MorphologicalTree.hpp.

◆ breadthFirstTraversal() [2/2]

BreadthFirstNodeRange mmcfilters::MorphologicalTree::breadthFirstTraversal ( NodeId rootNodeId ) const

inline

Returns a breadth-first traversal range rooted at rootNodeId.

Parameters

rootNodeId Identifier of the traversal root.

Returns: A breadth-first traversal range rooted at rootNodeId.

Definition at line 2752 of file MorphologicalTree.hpp.

◆ children()

ChildrenRange mmcfilters::MorphologicalTree::children ( NodeId nodeId ) const

inline

Returns a fail-fast range over the direct children of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: A fail-fast range over the direct children of nodeId.

Definition at line 2691 of file MorphologicalTree.hpp.

◆ clone()

MorphologicalTree mmcfilters::MorphologicalTree::clone ( ) const

inline

Creates an independent copy of the structural tree state.

The public copy constructor stays deleted so ownership remains explicit at API boundaries. This method is used by wrappers that need to preserve a caller-owned topology while creating a new tree-backed object. A staged edit cannot be cloned because its topology may be a temporary forest and has not crossed the commit validation boundary.

Returns: The created independent copy of the structural tree state.

Definition at line 1734 of file MorphologicalTree.hpp.

◆ complementaryAdjacencies()

const ComplementaryAdjacencies * mmcfilters::MorphologicalTree::complementaryAdjacencies ( ) const

inlinenoexcept

Returns the complementary adjacencies explicitly retained by a topographic immersion.

Returns: Borrowed adjacencies, or nullptr when no complementary grid immersion is stored.

Definition at line 2194 of file MorphologicalTree.hpp.

◆ constructionAdjacency()

const RegularGridAdjacency2D * mmcfilters::MorphologicalTree::constructionAdjacency ( ) const

inlinenoexcept

Returns the adjacency retained by a shared construction context.

Returns: Borrowed adjacency, or nullptr when no shared-adjacency context is stored.

Definition at line 2178 of file MorphologicalTree.hpp.

◆ constructionContext()

const MorphologicalTreeConstructionContext & mmcfilters::MorphologicalTree::constructionContext ( ) const

inlinenoexcept

Returns the typed construction context retained by this tree.

Returns: The typed construction context retained by this tree.

Definition at line 2167 of file MorphologicalTree.hpp.

◆ descendants()

DescendantNodeRange mmcfilters::MorphologicalTree::descendants ( NodeId nodeId ) const

inline

Returns a range over all proper descendants of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: A range over all proper descendants of nodeId.

Definition at line 2801 of file MorphologicalTree.hpp.

◆ dfsEntryIndex()

int mmcfilters::MorphologicalTree::dfsEntryIndex ( NodeId nodeId ) const

inline

Returns the zero-based DFS entry-event index of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The index at which DFS enters nodeId in the interleaved event sequence.

Definition at line 1989 of file MorphologicalTree.hpp.

◆ dfsExitIndex()

int mmcfilters::MorphologicalTree::dfsExitIndex ( NodeId nodeId ) const

inline

Returns the zero-based DFS exit-event index of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The index at which DFS exits nodeId in the interleaved event sequence.

Definition at line 2001 of file MorphologicalTree.hpp.

◆ edit()

TreeEditor mmcfilters::MorphologicalTree::edit ( )

inline

Opens the only public entrypoint for staged structural mutations.

Use this for multi-step topology rewiring that may temporarily detach nodes, move children/proper parts, or create intermediate nodes. TreeEditor::commit() runs the strong connected-rooted-tree validation.

Defined in TreeEditor.hpp after TreeEditor is complete; at this point only the forward declaration is available.

Returns: The opened only public entrypoint for staged structural mutations.

Definition at line 1306 of file TreeEditor.hpp.

◆ getEditValidationStatistics()

const TreeEditValidationStatistics & mmcfilters::MorphologicalTree::getEditValidationStatistics ( ) const

inlinenoexcept

Returns validation-path counters for committed edit sessions.

Returns: Validation-path counters for committed edit sessions.

Definition at line 2222 of file MorphologicalTree.hpp.

◆ getFirstChild()

NodeId mmcfilters::MorphologicalTree::getFirstChild ( NodeId nodeId ) const

inline

Returns the first direct child of nodeId, or InvalidNode.

Parameters

nodeId Dense internal node identifier.

Returns: The first direct child of nodeId, or InvalidNode.

Definition at line 2013 of file MorphologicalTree.hpp.

◆ getHigraNodeId()

NodeId mmcfilters::MorphologicalTree::getHigraNodeId ( NodeId nodeId ) const

inlinenoexcept

Returns the preserved imported Higra node id for one live tree node.

Returns InvalidNode when the original Higra node-id space is not preserved.

Parameters

nodeId Dense internal node identifier.

Returns: The preserved imported Higra node id for one live tree node.

Definition at line 1870 of file MorphologicalTree.hpp.

◆ getMutationVersion()

std::size_t mmcfilters::MorphologicalTree::getMutationVersion ( ) const

inlinenoexcept

Returns the monotonic mutation counter used by read-only views.

Returns: The monotonic mutation counter used by read-only views.

Definition at line 1797 of file MorphologicalTree.hpp.

◆ getNextSibling()

NodeId mmcfilters::MorphologicalTree::getNextSibling ( NodeId nodeId ) const

inline

Returns the next sibling of nodeId, or InvalidNode.

Parameters

nodeId Dense internal node identifier.

Returns: The next sibling of nodeId, or InvalidNode.

Definition at line 2024 of file MorphologicalTree.hpp.

◆ getNodeIdSpaceSize()

int mmcfilters::MorphologicalTree::getNodeIdSpaceSize ( NodeIdSpace outputSpace ) const

inline

Returns the size of the requested node-id domain.

NodeIdSpace::Higra means the preserved imported Higra domain, not the compact domain that would be generated by exporting the current tree.

Parameters

outputSpace Node-id domain used to index the output.

Returns: The size of the requested node-id domain.

Definition at line 1851 of file MorphologicalTree.hpp.

◆ getNumFreeNodeSlots()

int mmcfilters::MorphologicalTree::getNumFreeNodeSlots ( ) const

inline

Returns the number of currently reusable node slots.

Returns: The number of currently reusable node slots.

Definition at line 1928 of file MorphologicalTree.hpp.

◆ getNumHigraNodes()

int mmcfilters::MorphologicalTree::getNumHigraNodes ( ) const

inline

Returns the size of the preserved imported Higra node-id domain.

Returns: The size of the preserved imported Higra node-id domain.

Exceptions

std::runtime_error if the tree was not imported from Higra or if the preserved Higra node-id space was invalidated by an edit.

Definition at line 1835 of file MorphologicalTree.hpp.

◆ getPathBetweenNodes()

PathBetweenNodesRange mmcfilters::MorphologicalTree::getPathBetweenNodes	(	NodeId	sourceNodeId,
		NodeId	targetNodeId
	)		const

inline

Returns the path that connects sourceNodeId and targetNodeId.

Parameters

sourceNodeId	Node identifier.
targetNodeId	Node identifier.

Returns: The path that connects sourceNodeId and targetNodeId.

Definition at line 2778 of file MorphologicalTree.hpp.

◆ gridDomain2D()

const std::optional< GridDomain2D > & mmcfilters::MorphologicalTree::gridDomain2D ( ) const

inlinenoexcept

Returns the optional regular 2D pixel domain.

Returns: The optional regular 2D pixel domain.

Definition at line 2274 of file MorphologicalTree.hpp.

◆ hasChild()

bool mmcfilters::MorphologicalTree::hasChild	(	NodeId	parentNodeId,
		NodeId	childId
	)		const

inline

Tests whether childId is a direct child of parentNodeId.

Parameters

parentNodeId	Identifier of the parent node.
childId	Identifier of the child node.

Returns: True if childId is a direct child of parentNodeId; otherwise false.

Definition at line 2063 of file MorphologicalTree.hpp.

◆ hasDetachedAliveNodes()

bool mmcfilters::MorphologicalTree::hasDetachedAliveNodes ( ) const

inlinenoexcept

Returns whether the tree currently contains alive detached nodes.

Detached alive nodes are self-parented nodes other than the connected root. They are allowed during explicit edit sessions but make the hierarchy a forest rather than a single rooted tree.

Returns: Whether the tree currently contains alive detached nodes.

Definition at line 2243 of file MorphologicalTree.hpp.

◆ hasEmptyProperPart()

bool mmcfilters::MorphologicalTree::hasEmptyProperPart ( NodeId nodeId ) const

inline

Tests whether nodeId has an empty proper part.

Parameters

nodeId Dense internal node identifier.

Returns: True if the proper part of nodeId is empty; otherwise false.

Definition at line 2054 of file MorphologicalTree.hpp.

◆ hasGridDomain2D()

bool mmcfilters::MorphologicalTree::hasGridDomain2D ( ) const

inlinenoexcept

Tests whether pixel ids have an attached row/column layout.

Returns: True if pixel ids have an attached row/column layout; otherwise false.

Definition at line 2267 of file MorphologicalTree.hpp.

◆ isAlive()

bool mmcfilters::MorphologicalTree::isAlive ( NodeId nodeId ) const

inline

Tests whether a node slot currently represents a live node.

Parameters

nodeId Dense internal node identifier.

Returns: True if a node slot currently represents a live node; otherwise false.

Definition at line 1906 of file MorphologicalTree.hpp.

◆ isAncestor()

bool mmcfilters::MorphologicalTree::isAncestor	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u is an ancestor of v.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u is an ancestor of v; otherwise false.

Definition at line 2561 of file MorphologicalTree.hpp.

◆ isComparable()

bool mmcfilters::MorphologicalTree::isComparable	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u and v are comparable in the ancestry order.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u and v are comparable in the ancestry order; otherwise false.

Definition at line 2594 of file MorphologicalTree.hpp.

◆ isDescendant()

bool mmcfilters::MorphologicalTree::isDescendant	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u is a descendant of v.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u is a descendant of v; otherwise false.

Definition at line 2578 of file MorphologicalTree.hpp.

◆ isEditing()

bool mmcfilters::MorphologicalTree::isEditing ( ) const

inlinenoexcept

Tests whether a staged edit session is currently open.

Returns: True if a staged edit session is currently open; otherwise false.

Definition at line 2215 of file MorphologicalTree.hpp.

◆ isLeaf()

bool mmcfilters::MorphologicalTree::isLeaf ( NodeId nodeId ) const

inline

Tests whether nodeId has no direct children.

Parameters

nodeId Dense internal node identifier.

Returns: True if nodeId has no direct children; otherwise false.

Definition at line 2035 of file MorphologicalTree.hpp.

◆ isNode()

bool mmcfilters::MorphologicalTree::isNode ( NodeId nodeId ) const

inlinenoexcept

Tests whether nodeId belongs to the internal-node id domain.

Parameters

nodeId Dense internal node identifier.

Returns: True if nodeId belongs to the internal-node id domain; otherwise false.

Definition at line 1890 of file MorphologicalTree.hpp.

◆ isPixel()

bool mmcfilters::MorphologicalTree::isPixel ( PixelId pixel ) const

inlinenoexcept

Tests whether pixel belongs to the pixel domain.

Parameters

pixel Pixel identifier.

Returns: True if pixel belongs to the pixel domain; otherwise false.

Definition at line 1898 of file MorphologicalTree.hpp.

◆ isRoot()

bool mmcfilters::MorphologicalTree::isRoot ( NodeId nodeId ) const

inline

Tests whether nodeId is the current root.

Parameters

nodeId Dense internal node identifier.

Returns: True if nodeId is the current root; otherwise false.

Definition at line 1921 of file MorphologicalTree.hpp.

◆ isStrictAncestor()

bool mmcfilters::MorphologicalTree::isStrictAncestor	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u is a strict ancestor of v.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u is a strict ancestor of v; otherwise false.

Definition at line 2603 of file MorphologicalTree.hpp.

◆ isStrictComparable()

bool mmcfilters::MorphologicalTree::isStrictComparable	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u and v are strictly comparable in the ancestry order.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u and v are strictly comparable in the ancestry order; otherwise false.

Definition at line 2621 of file MorphologicalTree.hpp.

◆ isStrictDescendant()

bool mmcfilters::MorphologicalTree::isStrictDescendant	(	NodeId	u,
		NodeId	v
	)		const

inline

Tests whether u is a strict descendant of v.

Parameters

u	First endpoint or element.
v	Second endpoint or element.

Returns: True if u is a strict descendant of v; otherwise false.

Definition at line 2612 of file MorphologicalTree.hpp.

◆ isTreeOfPartialPartitions()

bool mmcfilters::MorphologicalTree::isTreeOfPartialPartitions ( ) const

inline

Tests whether every live node has a non-empty proper part.

Returns: True exactly when the connected-subset tree is a morphological tree of partial partitions.

Definition at line 2528 of file MorphologicalTree.hpp.

◆ kind()

MorphologicalTreeKind mmcfilters::MorphologicalTree::kind ( ) const

inlinenoexcept

Returns the optional descriptive hierarchy-family label.

Algorithms must use explicit capabilities such as nodeAltitudeOrder() and the typed construction context instead of dispatching on this label.

Returns: The optional descriptive hierarchy-family label.

Definition at line 2146 of file MorphologicalTree.hpp.

◆ leaves()

std::vector< NodeId > mmcfilters::MorphologicalTree::leaves ( ) const

inline

Returns all live leaf nodes in the current hierarchy.

Returns: All live leaf nodes in the current hierarchy.

Definition at line 2117 of file MorphologicalTree.hpp.

◆ lowestCommonAncestor()

NodeId mmcfilters::MorphologicalTree::lowestCommonAncestor	(	NodeId	u,
		NodeId	v
	)		const

inline

Returns the lowest common ancestor of u and v.

Queries take O(1) time once the required caches exist. For N internal node slots, DFS intervals require O(N) time and storage and resolve comparable pairs. The first incomparable pair may additionally build an Euler/RMQ cache in O(N log(N + 1)) time and storage. The tree retains these caches until the corresponding topology state is invalidated.

Parameters

u	First internal node identifier.
v	Second internal node identifier.

Returns: Lowest common ancestor, or InvalidNode for invalid or dead endpoints or when no common ancestor can be resolved.

Definition at line 2637 of file MorphologicalTree.hpp.

◆ lowestCommonAncestors()

std::vector< NodeId > mmcfilters::MorphologicalTree::lowestCommonAncestors ( std::span< const std::pair< NodeId, NodeId > > queries ) const

inline

Returns lowest common ancestors for a batch of node pairs.

Invalid or dead endpoints produce InvalidNode. An existing persistent Euler/RMQ cache is reused. When that cache has not been built, DFS intervals first resolve equality, ancestry, and disconnection. The remaining incomparable pairs use streamed RMQ or iterative offline Tarjan, selected from their estimated storage.

Parameters

queries Pairwise node queries.

Returns: LCA results in the same order as queries.

Definition at line 2656 of file MorphologicalTree.hpp.

◆ mergeNodeIntoParent()

void mmcfilters::MorphologicalTree::mergeNodeIntoParent ( NodeId nodeId )

inline

Merges nodeId into its parent and releases the emptied slot.

This is a safe committed edit: children and direct proper parts are transferred to the parent before the node slot is released. The operation advances the tree mutation version and invalidates derived state.

Parameters

nodeId Dense internal node identifier.

Definition at line 2877 of file MorphologicalTree.hpp.

◆ nodeAltitudeOrder()

NodeAltitudeOrder mmcfilters::MorphologicalTree::nodeAltitudeOrder ( ) const

inlinenoexcept

Returns the global parent-to-child altitude ordering constraint.

Returns: The global parent-to-child altitude ordering constraint.

Definition at line 2160 of file MorphologicalTree.hpp.

◆ nodeSupport()

NodeSupportRange mmcfilters::MorphologicalTree::nodeSupport ( NodeId nodeId ) const

inline

Returns a fail-fast range over the pixels in the support of nodeId.

The range walks the subtree rooted at nodeId and yields every pixel in the proper parts of those nodes, without materialising a vector.

Parameters

nodeId Dense internal node identifier.

Returns: A fail-fast range over the pixels in the support represented by nodeId.

Definition at line 2716 of file MorphologicalTree.hpp.

◆ numChildren()

int mmcfilters::MorphologicalTree::numChildren ( NodeId nodeId ) const

inline

Returns the number of direct children of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The number of direct children of nodeId.

Definition at line 1951 of file MorphologicalTree.hpp.

◆ numColumns()

int mmcfilters::MorphologicalTree::numColumns ( ) const

inline

Returns the number of columns in the regular 2D pixel domain.

Returns: The number of columns in the regular 2D pixel domain.

Definition at line 2301 of file MorphologicalTree.hpp.

◆ numDescendants()

int mmcfilters::MorphologicalTree::numDescendants ( NodeId nodeId ) const

inline

Returns the number of internal descendants of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The number of internal descendants of nodeId.

Definition at line 1962 of file MorphologicalTree.hpp.

◆ numInternalNodeSlots()

int mmcfilters::MorphologicalTree::numInternalNodeSlots ( ) const

inline

Returns the size of the dense internal-node id domain.

Some slots may currently be free and therefore not correspond to live nodes.

Returns: The size of the dense internal-node id domain.

Definition at line 1817 of file MorphologicalTree.hpp.

◆ numLeafNodes()

int mmcfilters::MorphologicalTree::numLeafNodes ( ) const

inline

Counts the live nodes that currently have no children.

Returns: Counts the live nodes that currently have no children.

Definition at line 1935 of file MorphologicalTree.hpp.

◆ numNodes()

int mmcfilters::MorphologicalTree::numNodes ( ) const

inlinenoexcept

Returns the number of currently live nodes.

Returns: The number of currently live nodes.

Definition at line 2208 of file MorphologicalTree.hpp.

◆ numPixels()

int mmcfilters::MorphologicalTree::numPixels ( ) const

inline

Returns the cardinality of the pixel domain.

Returns: The number of pixels in the tree domain.

Definition at line 1824 of file MorphologicalTree.hpp.

◆ numRows()

int mmcfilters::MorphologicalTree::numRows ( ) const

inline

Returns the number of rows in the regular 2D pixel domain.

Returns: The number of rows in the regular 2D pixel domain.

Definition at line 2294 of file MorphologicalTree.hpp.

◆ numSiblings()

int mmcfilters::MorphologicalTree::numSiblings ( NodeId nodeId ) const

inline

Returns the number of siblings of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The number of siblings of nodeId.

Definition at line 1974 of file MorphologicalTree.hpp.

◆ operator=() [1/2]

MorphologicalTree & mmcfilters::MorphologicalTree::operator= ( const MorphologicalTree & )

delete

Copy assignment is disabled to keep topology storage explicit.

Returns: Mutable reference to the updated object.

◆ operator=() [2/2]

MorphologicalTree & mmcfilters::MorphologicalTree::operator= ( MorphologicalTree && other )

inline

Move-assigns a complete committed topology.

Both owners must be outside edit sessions so no editor can retain a pointer to storage that changes owner.

Parameters

other Object to compare with or transfer from.

Returns: Mutable reference to the updated object.

Definition at line 1660 of file MorphologicalTree.hpp.

◆ parent()

NodeId mmcfilters::MorphologicalTree::parent ( NodeId nodeId ) const

inline

Returns the direct parent of nodeId.

The root and detached nodes report themselves as parent.

Parameters

nodeId Dense internal node identifier.

Returns: The direct parent of nodeId.

Definition at line 2077 of file MorphologicalTree.hpp.

◆ postOrder() [1/2]

PostOrderNodeRange mmcfilters::MorphologicalTree::postOrder ( ) const

inline

Returns a post-order traversal range rooted at the connected root.

Returns: A post-order traversal range rooted at the connected root.

Definition at line 2726 of file MorphologicalTree.hpp.

◆ postOrder() [2/2]

PostOrderNodeRange mmcfilters::MorphologicalTree::postOrder ( NodeId rootNodeId ) const

inline

Returns a post-order traversal range rooted at rootNodeId.

Parameters

rootNodeId Identifier of the traversal root.

Returns: A post-order traversal range rooted at rootNodeId.

Definition at line 2734 of file MorphologicalTree.hpp.

◆ properPart()

ProperPartRange mmcfilters::MorphologicalTree::properPart ( NodeId nodeId ) const

inline

Returns a fail-fast range over the pixels in the proper part of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: A fail-fast range over the pixels in the proper part of nodeId.

Definition at line 2702 of file MorphologicalTree.hpp.

◆ properPartCardinality()

int mmcfilters::MorphologicalTree::properPartCardinality ( NodeId nodeId ) const

inline

Returns the cardinality of the proper part of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: The number of pixels in the proper part of nodeId.

Definition at line 2043 of file MorphologicalTree.hpp.

◆ pruneNode()

void mmcfilters::MorphologicalTree::pruneNode ( NodeId nodeId )

inline

Prunes the subtree of nodeId, moving all its support to the parent.

This is a safe committed edit: it is a complete local operation and does not intentionally leave the tree in a staged disconnected state, but it still advances the tree mutation version and invalidates derived state.

Parameters

nodeId Dense internal node identifier.

Definition at line 2829 of file MorphologicalTree.hpp.

◆ requireGridDomain2D()

const GridDomain2D & mmcfilters::MorphologicalTree::requireGridDomain2D ( const char * context ) const

inline

Returns the regular 2D domain or rejects a geometry-dependent call.

Parameters

context Operation context or diagnostic label.

Returns: The regular 2D domain or rejects a geometry-dependent call.

Definition at line 2282 of file MorphologicalTree.hpp.

◆ requireMutationVersion()

void mmcfilters::MorphologicalTree::requireMutationVersion	(	std::size_t	expectedVersion,
		const char *	context
	)		const

inline

Rejects stale read-only views that captured an older mutation version.

Parameters

expectedVersion	Mutation version required by the operation.
context	Operation context or diagnostic label.

Definition at line 1805 of file MorphologicalTree.hpp.

◆ requireNotEditing()

void mmcfilters::MorphologicalTree::requireNotEditing ( const char * context ) const

inline

Rejects operations that require a committed connected topology.

Parameters

context Operation context or diagnostic label.

Definition at line 2229 of file MorphologicalTree.hpp.

◆ root()

NodeId mmcfilters::MorphologicalTree::root ( ) const

inline

Returns the current hierarchy root.

Returns: The current hierarchy root.

Definition at line 1882 of file MorphologicalTree.hpp.

◆ semantics()

const MorphologicalTreeSemantics & mmcfilters::MorphologicalTree::semantics ( ) const

inlinenoexcept

Returns all generic semantic capabilities of this hierarchy.

Returns: All generic semantic capabilities of this hierarchy.

Definition at line 2153 of file MorphologicalTree.hpp.

◆ sharedAdjacencyContext()

const SharedAdjacencyContext * mmcfilters::MorphologicalTree::sharedAdjacencyContext ( ) const

inlinenoexcept

Returns the shared-adjacency context, or nullptr.

Returns: Stored context when its variant is active.

Definition at line 2170 of file MorphologicalTree.hpp.

◆ smallestNode()

NodeId mmcfilters::MorphologicalTree::smallestNode ( PixelId pixel ) const

inline

Returns the smallest node containing pixel.

Parameters

pixel Pixel in the finite tree domain.

Returns: The smallest node whose support contains pixel, or InvalidNode for an invalid pixel in checked builds.

Definition at line 2098 of file MorphologicalTree.hpp.

◆ smallestNodeMap()

std::span< const NodeId > mmcfilters::MorphologicalTree::smallestNodeMap ( ) const

inlinenoexcept

Returns the pixel-indexed smallest-node map.

Returns: A read-only view P satisfying pixel in properPart(P[pixel]).

Definition at line 2110 of file MorphologicalTree.hpp.

◆ subtreeNodes()

SubtreeNodeRange mmcfilters::MorphologicalTree::subtreeNodes ( NodeId nodeId ) const

inline

Returns a pre-order traversal range over the subtree of nodeId.

Parameters

nodeId Dense internal node identifier.

Returns: A pre-order traversal range over the subtree of nodeId.

Definition at line 2790 of file MorphologicalTree.hpp.

◆ topographicConvention()

const TopographicConvention * mmcfilters::MorphologicalTree::topographicConvention ( ) const

inlinenoexcept

Returns the topographic convention, or nullptr.

Returns: Stored convention when its variant is active.

Definition at line 2186 of file MorphologicalTree.hpp.

◆ validateConnectedRootedTree()

void mmcfilters::MorphologicalTree::validateConnectedRootedTree ( ) const

inline

Validates one rooted tree with a complete smallest-node map and non-empty supports.

This validation is intended for edit-session commits and debug/invariant checks. It is intentionally stronger than the local runtime guards used by low-level mutators.

Definition at line 2310 of file MorphologicalTree.hpp.

◆ validateConnectedRootedTreeResult()

TreeValidationResult mmcfilters::MorphologicalTree::validateConnectedRootedTreeResult ( ) const

inlinenoexcept

Runs strong validation and returns the result instead of throwing.

Returns: Result produced by running strong validation and returns the result instead of throwing.

Definition at line 2511 of file MorphologicalTree.hpp.

◆ validateTreeOfPartialPartitions()

void mmcfilters::MorphologicalTree::validateTreeOfPartialPartitions ( ) const

inline

Validates the connected-subset invariants and the non-empty proper-part specialization.

Exceptions

std::runtime_error if the tree is invalid or any live node has an empty proper part.

Definition at line 2545 of file MorphologicalTree.hpp.

Friends And Related Symbol Documentation

◆ detail::materializeNativeHierarchy

template<AltitudeValue T>

ValuedMorphologicalTree< T > detail::materializeNativeHierarchy	(	NativeHierarchyOwned< T > &&	hierarchy,
		std::optional< NodeId >	preservedExternalNodeIdOffset,
		detail::MaterializedVersionPolicy	versionPolicy
	)

friend

Allows the native hierarchy materializer to initialize owned topology buffers and construction metadata.

Template Parameters

T	Node-altitude type.

Parameters

hierarchy	Owned hierarchy transferred into the valued tree.
preservedExternalNodeIdOffset	Original Higra node-id offset, when present.
versionPolicy	Initial mutation-version policy.

Returns: Valued tree owning the transferred hierarchy.

◆ detail::TreeKernelAccess

friend class detail::TreeKernelAccess

friend

Definition at line 121 of file MorphologicalTree.hpp.

◆ MorphologicalTreeFactory

friend class MorphologicalTreeFactory

friend

Definition at line 120 of file MorphologicalTree.hpp.

◆ TreeEditor

friend class TreeEditor

friend

Definition at line 119 of file MorphologicalTree.hpp.

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

mmcfilters/trees/MorphologicalTree.hpp
mmcfilters/trees/TreeEditor.hpp

Classes

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ MorphologicalTree() [1/3]

◆ MorphologicalTree() [2/3]

◆ MorphologicalTree() [3/3]

Member Function Documentation

◆ aliveNodeIds()

◆ ancestors()

◆ breadthFirstTraversal() [1/2]

◆ breadthFirstTraversal() [2/2]

◆ children()

◆ clone()

◆ complementaryAdjacencies()

◆ constructionAdjacency()

◆ constructionContext()

◆ descendants()

◆ dfsEntryIndex()

◆ dfsExitIndex()

◆ edit()

◆ getEditValidationStatistics()

◆ getFirstChild()

◆ getHigraNodeId()

◆ getMutationVersion()

◆ getNextSibling()

◆ getNodeIdSpaceSize()

◆ getNumFreeNodeSlots()

◆ getNumHigraNodes()

◆ getPathBetweenNodes()

◆ gridDomain2D()

◆ hasChild()

◆ hasDetachedAliveNodes()

◆ hasEmptyProperPart()

◆ hasGridDomain2D()

◆ isAlive()

◆ isAncestor()

◆ isComparable()

◆ isDescendant()

◆ isEditing()

◆ isLeaf()

◆ isNode()

◆ isPixel()

◆ isRoot()

◆ isStrictAncestor()

◆ isStrictComparable()

◆ isStrictDescendant()

◆ isTreeOfPartialPartitions()

◆ kind()

◆ leaves()

◆ lowestCommonAncestor()

◆ lowestCommonAncestors()

◆ mergeNodeIntoParent()

◆ nodeAltitudeOrder()

◆ nodeSupport()

◆ numChildren()

◆ numColumns()

◆ numDescendants()

◆ numInternalNodeSlots()

◆ numLeafNodes()

◆ numNodes()

◆ numPixels()

◆ numRows()

◆ numSiblings()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ postOrder() [1/2]

◆ postOrder() [2/2]

◆ properPart()

◆ properPartCardinality()

◆ pruneNode()

◆ requireGridDomain2D()

◆ requireMutationVersion()

◆ requireNotEditing()

◆ root()

◆ semantics()

◆ sharedAdjacencyContext()

◆ smallestNode()