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 SaturatedResidualContext *	saturatedResidualContext () const noexcept
	Returns the saturated-residual context, or `nullptr`.

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

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::CommittedTreeAccess

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 114 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 1640 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 1694 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 1712 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 2658 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 2741 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 2719 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 2727 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 2666 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 1728 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 2161 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 2776 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 1983 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 1995 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 1303 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 2197 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 2007 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 1864 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 1791 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 2018 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 1845 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 1922 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 1829 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 2753 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 2249 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 2057 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 2218 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 2048 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 2242 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 1900 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 2536 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 2569 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 2553 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 2190 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 2029 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 1884 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 1892 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 1915 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 2578 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 2596 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 2587 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 2503 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 2140 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 2111 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 2612 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 2631 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 2852 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 2154 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 2691 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 1945 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 2276 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 1956 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 1811 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 1929 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 2183 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 1818 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 2269 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 1968 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 1654 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 2071 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 2701 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 2709 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 2677 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 2037 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 2804 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 2257 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 1799 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 2204 of file MorphologicalTree.hpp.

◆ root()

NodeId mmcfilters::MorphologicalTree::root ( ) const

inline

Returns the current hierarchy root.

Returns: The current hierarchy root.

Definition at line 1876 of file MorphologicalTree.hpp.

◆ saturatedResidualContext()

const SaturatedResidualContext * mmcfilters::MorphologicalTree::saturatedResidualContext ( ) const

inlinenoexcept

Returns the saturated-residual context, or nullptr.

Returns: Stored context when its variant is active.

Definition at line 2169 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 2147 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 2164 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 2092 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 2104 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 2765 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 2174 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 2285 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 2486 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 2520 of file MorphologicalTree.hpp.

Friends And Related Symbol Documentation

◆ detail::CommittedTreeAccess

friend class detail::CommittedTreeAccess

friend

Definition at line 118 of file MorphologicalTree.hpp.

◆ MorphologicalTreeFactory

friend class MorphologicalTreeFactory

friend

Definition at line 117 of file MorphologicalTree.hpp.

◆ TreeEditor

friend class TreeEditor

friend

Definition at line 116 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()

◆ 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()

◆ saturatedResidualContext()

◆ semantics()

◆ sharedAdjacencyContext()

◆ smallestNode()

◆ smallestNodeMap()