`tools` — Core Infrastructure¶

Warning

Internal module — subject to change without notice. Do not import or subclass these objects in production code.

This module provides the core technical infrastructure for manipulating nested dictionaries. While hidden from the package’s public API, it serves as the foundation for all nested dictionary operations.

_StackedDict: Base class for nested dictionary structures
_HKey: Tree node representing hierarchical keys (private, optimized with tuples)
_Paths: View of all paths in a nested dictionary
_CPaths: Compact/factorized representation of paths in nested dictionaries

The module enables efficient navigation, querying, and factorization of deeply nested dictionary structures with support for various key types.

The _StackedDict class is the central engine of the ndict_tools package. It implements all the fundamental attributes, methods, and logic required to initialize, manage, and manipulate nested dictionaries. This class is designed to:

Orchestrate the basic building blocks of nested dictionary functionality
Provide the complete toolset for dictionary nesting, key management, and hierarchical data operations
Serve as a versatile base for current and future dictionary implementations

Module-level helpers¶

ndict_tools.tools.compare_dict(d1, d2) → bool¶

Recursively compare two potentially nested structures for equality.

Performs deep comparison of dictionaries, lists, tuples, sets, and scalar values. Two structures are considered equal if they have the same type and equal content at all nesting levels.

Parameters:

d1 (Any) – First structure to compare
d2 (Any) – Second structure to compare

Returns:

True if structures are identical in type and content

Return type:

bool

Examples

>>> compare_dict({'a': 1}, {'a': 1})
True
>>> compare_dict({'a': {'b': 1}}, {'a': {'b': 1}})
True
>>> compare_dict({'a': 1}, {'a': 2})
False
>>> compare_dict([1, 2], (1, 2))
False

Notes

Type checking is strict: [1, 2] != (1, 2) even with same values
Dictionary key sets must match exactly
Recursively handles nested structures of arbitrary depth

ndict_tools.tools.unpack_items(dictionary: dict[Any, Any]) → Generator[tuple[tuple[Any, ...], Any], None, None]¶

Recursively flatten a nested dictionary into (path, value) pairs.

Traverses a nested dictionary structure and yields each terminal value along with its hierarchical path represented as a tuple of keys. Empty dictionaries are preserved and yielded with their path.

Parameters:: dictionary (dict) – Dictionary to unpack (may be nested)
Yields:: tuple – (path_tuple, value) where path_tuple is a tuple of keys leading to value

Examples

>>> list(unpack_items({'a': 1, 'b': {'c': 2}}))
[(('a',), 1), (('b', 'c'), 2)]
>>> list(unpack_items({'a': {}}))
[(('a',), {})]
>>> list(unpack_items({'a': {'b': {'c': 1}}}))
[(('a', 'b', 'c'), 1)]

Notes

Uses depth-first traversal
Empty dictionaries are treated as terminal values
Paths are represented as immutable tuples for hashability

See also

_StackedDict.unpacked_items: Method wrapper for this function
_StackedDict.dfs: Depth-first traversal alternative

`_HKey` — Hierarchical key node¶

class ndict_tools.tools._HKey(key: Any, parent: _HKey | None = None, is_root: bool = False)¶

Bases: object

Private tree node representing a hierarchical key in a nested dictionary.

Each _HKey instance represents a single key in a nested dictionary structure, forming a tree where:

Each node holds a key value from the dictionary
Children nodes (stored as immutable tuples) represent keys in nested dictionaries
Parent’s references enable path reconstruction from any node

The use of immutable tuples for children optimizes memory usage and iteration performance for tree traversal algorithms (DFS, BFS).

Warning

This is a private class (underscore prefix) and should not be instantiated directly by external code. Access it through CompactPathsView or NestedDictionary.

Parameters:

key (Any) – The key value this node represents
parent (Optional[_HKey], optional) – Reference to parent node, None for root nodes
is_root (bool, optional) – Whether this node is a root node, by default False

key¶

The key value this node represents

Type:: Any

children¶

Immutable tuple of child nodes

Type:: tuple[_HKey, …]

parent¶

Reference to parent node (None for root)

Type:: Optional[_HKey]

is_root¶

True if this is a root node

Type:: bool

Examples

>>> root = _HKey('a')
>>> child_b = root.add_child('b')
>>> child_c = root.add_child('c')
>>> root.get_child_keys()
['b', 'c']
>>> child_b.get_path()
['a', 'b']

See also

_CPaths: Uses _HKey internally for tree representation

classmethod build_forest(stacked_dict: dict[Any, Any]) → _HKey¶

Build a forest of _HKey trees from a nested dictionary.

Creates a root node containing all top-level keys as children, recursively building the tree structure for nested dictionaries.

Parameters:: stacked_dict (dict) – A dictionary (or _StackedDict) to build the tree from
Returns:: Root node (with is_root=True, key=None) containing the forest
Return type:: _HKey

Examples

>>> data = {'a': 1, 'b': {'c': 2}}
>>> forest = _HKey.build_forest(data)
>>> forest.get_child_keys()
['a', 'b']
>>> forest.is_root
True

add_child(key: Any) → _HKey¶

Add a child node with the given key.

If a child with this key already exists, returns the existing child. Creates a new tuple with the additional child (O(n) operation).

Note

For adding multiple children, use add_children() for better performance.

Parameters:: key (Any) – Key for the new child node
Returns:: The child node (newly created or existing)
Return type:: _HKey

Examples

>>> node = _HKey('parent')
>>> child = node.add_child('child')
>>> child.key
'child'
>>> child.parent.key
'parent'

add_children(keys: list[Any]) → tuple[_HKey, ...]¶

Add multiple children at once (more efficient than repeated add_child).

Parameters:: keys (list[Any]) – list of keys to add as children
Returns:: tuple of newly created child nodes
Return type:: tuple[_HKey, …]

Examples

>>> node = _HKey('parent')
>>> children = node.add_children(['a', 'b', 'c'])
>>> len(node.children)
3

get_child(key: Any) → _HKey | None¶

Get a child node by key.

Parameters:: key (Any) – Key to look up
Returns:: Child node if found, None otherwise
Return type:: Optional[_HKey]

Examples

>>> node = _HKey('parent')
>>> node.add_child('child')
>>> child = node.get_child('child')
>>> child.key
'child'
>>> node.get_child('nonexistent') is None
True

get_child_keys() → list[Any]¶

Get list of all child keys.

Returns:: list of keys for all children
Return type:: list[Any]

Examples

>>> node = _HKey('parent')
>>> node.add_child('a')
>>> node.add_child('b')
>>> sorted(node.get_child_keys())
['a', 'b']

has_children() → bool¶

Check if this node has any children.

Returns:: True if node has at least one child
Return type:: bool

is_leaf() → bool¶

Check if this is a leaf node (no children).

Returns:: True if node has no children
Return type:: bool

get_path() → list[Any]¶

Get the path from root to this node.

Traverses parent references to reconstruct the full path.

Returns:: list of keys from root to this node
Return type:: list[Any]

Examples

>>> root = _HKey('a')
>>> child = root.add_child('b')
>>> grandchild = child.add_child('c')
>>> grandchild.get_path()
['a', 'b', 'c']

find_by_path(path: list[Any]) → _HKey | None¶

Find a node by following a path from this node.

Parameters:: path (list[Any]) – list of keys to follow
Returns:: Node at end of path, or None if path doesn’t exist
Return type:: Optional[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}})
>>> node = root.find_by_path(['a', 'b', 'c'])
>>> node.key
'c'
>>> root.find_by_path(['a', 'x']) is None
True

get_all_paths() → list[list[Any]]¶

Get all paths from this node to all descendants.

Recursively collects paths to every node in the subtree, including intermediate nodes and leaves.

Returns:: list of all paths in the subtree
Return type:: list[list[Any]]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> paths = root.get_all_paths()
>>> len(paths)
3
>>> sorted([tuple(p) for p in paths])
[('a',), ('a', 'b'), ('a', 'c')]

get_descendants() → list[_HKey]¶

Get all descendant nodes (children, grandchildren, etc.).

Returns:: list of all descendant nodes in DFS order
Return type:: list[_HKey]

get_depth() → int¶

Get the depth of this node (distance from root).

Returns:: Depth level (0 for direct children of root)
Return type:: int

get_max_depth() → int¶

Get the maximum depth of the subtree rooted at this node.

Returns:: Maximum depth (0 for leaf nodes)
Return type:: int

iter_children() → Iterator[_HKey]¶

Iterate over direct child nodes.

Yields:: _HKey – Each child node

iter_leaves() → Iterator[_HKey]¶

Iterate over all leaf nodes in the subtree.

Yields:: _HKey – Each leaf node (nodes with no children)

dfs_preorder(visit: Callable[[_HKey], None] | None = None) → Iterator[_HKey]¶

Depth-First Search traversal in pre-order (node, then children).

Pre-order: Visit current node before its children. Order: Root → Left subtree → Right subtree

This traversal is cycle-safe: if the underlying structure contains cycles (which should not happen in a valid tree), nodes that have already been seen will be skipped to prevent infinite loops.

Parameters:: visit (Optional[Callable[[_HKey], None]],) – Optional callback function called on each node
Yields:: _HKey – Each node in pre-order

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> keys = [node.key for node in root.dfs_preorder() if not node.is_root]
>>> keys
['a', 'b', 'c']

See also

dfs_postorder: Post-order DFS traversal
bfs: Breadth-first traversal

dfs_postorder(visit: Callable[[_HKey], None] | None = None) → Iterator[_HKey]¶

Depth-First Search traversal in post-order (children, then node).

Post-order: Visit children before current node. Order: Left subtree → Right subtree → Root Useful for deletion or bottom-up calculations.

This traversal is cycle-safe: previously visited nodes are skipped to prevent infinite recursion if a cycle is present.

Parameters:: visit (Optional[Callable[[_HKey], None]],) – Optional callback function called on each node
Yields:: _HKey – Each node in post-order

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> keys = [node.key for node in root.dfs_postorder() if not node.is_root]
>>> keys
['b', 'c', 'a']

See also

dfs_preorder: Pre-order DFS traversal

bfs(visit: Callable[[_HKey], None] | None = None) → Iterator[_HKey]¶

Breadth-First Search (level-order) traversal.

BFS explores all nodes at depth N before moving to depth N+1. Uses a queue (deque) for optimal O(1) operations.

This traversal is cycle-safe: nodes already seen are not enqueued again, preventing infinite loops in the presence of cycles.

Parameters:: visit (Optional[Callable[[_HKey], None]]) – Optional callback function called on each node
Yields:: _HKey – Each node in level-order

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}})
>>> keys = [node.key for node in root.bfs() if not node.is_root]
>>> keys
['a', 'b', 'c']

>>> # BFS with depth tracking
>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}, 'd': 3})
>>> for node in root.bfs():
...     if not node.is_root:
...         print(f"Depth {node.get_depth()}: {node.key}")
Depth 0: a
Depth 0: d
Depth 1: b
Depth 1: c

See also

dfs_preorder: Depth-first traversal
iter_by_level: Get nodes grouped by level

dfs_find(predicate: Callable[[_HKey], bool]) → _HKey | None¶

Find first node matching predicate using DFS.

Performs depth-first search and returns the first node for which the predicate returns True. Returns None if no match found. This method is cycle-safe as it leverages dfs_preorder which guards against revisiting nodes.

Parameters:: predicate (Callable[[_HKey], bool]) – Function that returns True for the target node
Returns:: First matching node, or None if not found
Return type:: Optional[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}, 'c': 2})
>>> node = root.dfs_find(lambda n: n.key == 'b')
>>> node.key
'b'
>>> root.dfs_find(lambda n: n.key == 'z') is None
True

See also

bfs_find: BFS-based search
find_all: Find all matching nodes

bfs_find(predicate: Callable[[_HKey], bool]) → _HKey | None¶

Find first node matching predicate using BFS.

Performs breadth-first search and returns the first node for which the predicate returns True. Finds nodes at shallower depths first.

Parameters:: predicate (Callable[[_HKey], bool]) – Function that returns True for the target node
Returns:: First matching node, or None if not found
Return type:: Optional[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}})
>>> # BFS finds 'b' before 'c' (closer to root)
>>> node = root.bfs_find(lambda n: n.key in ['b', 'c'])
>>> node.key
'b'

See also

dfs_find: DFS-based search

find_all(predicate: Callable[[_HKey], bool]) → list[_HKey]¶

Find all nodes matching predicate.

Parameters:: predicate (Callable[[_HKey], bool]) – Function that returns True for target nodes
Returns:: list of all matching nodes
Return type:: list[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}, 'c': {'b': 2}})
>>> nodes = root.find_all(lambda n: n.key == 'b')
>>> len(nodes)
2
>>> [n.get_path() for n in nodes]
[['a', 'b'], ['c', 'b']]

find_by_key(key: Any, find_all: bool = False) → _HKey | None | list[_HKey]¶

Find node(s) with specific key value.

Convenience method for finding nodes by their key value.

Parameters:

key (Any) – Key value to search for
find_all (bool, optional) – If True, return all matches; if False, return first match

Returns:

Single node if find_all=False, list of nodes if value find_all=True

Return type:

Optional[_HKey] or list[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}, 'c': {'b': 2}})
>>> node = root.find_by_key('b')
>>> node.get_path()
['a', 'b']
>>> nodes = root.find_by_key('b', find_all=True)
>>> len(nodes)
2

iter_by_level() → Iterator[tuple[int, list[_HKey]]]¶

Iterate over nodes grouped by depth level.

Yields tuples of (depth, nodes_at_depth) for each level of the tree.

Yields:: tuple[int, list[_HKey]] – (depth_level, list_of_nodes_at_that_level)

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> for depth, nodes in root.iter_by_level():
...     keys = [n.key for n in nodes if not n.is_root]
...     if keys:
...         print(f'Level {depth}: {keys}')
Level 0: ['a']
Level 1: ['b', 'c']

See also

bfs: Breadth-first traversal
get_nodes_at_depth: Get nodes at specific depth

get_nodes_at_depth(target_depth: int) → list[_HKey]¶

Get all nodes at a specific depth.

Parameters:: target_depth (int) – Depth level to query (0 = root’s children)
Returns:: All nodes at the specified depth
Return type:: list[_HKey]

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}})
>>> nodes = root.get_nodes_at_depth(1)
>>> [n.key for n in nodes]
['b']

See also

iter_by_level: Iterate all levels

filter_paths(predicate: Callable[[list[Any]], bool]) → list[list[Any]]¶

Filter paths based on a predicate function.

Parameters:: predicate (Callable[[list[Any]], bool]) – Function that takes a path and returns True to include it
Returns:: Filtered list of paths
Return type:: list[list[Any]]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}, 'd': 3})
>>> # Get paths longer than 1
>>> paths = root.filter_paths(lambda p: len(p) > 1)
>>> sorted([tuple(p) for p in paths])
[('a', 'b'), ('a', 'c')]

>>> # Get paths containing specific key
>>> paths = root.filter_paths(lambda p: 'b' in p)
>>> paths
[['a', 'b']]

map_nodes(func: Callable[[_HKey], Any]) → list[Any]¶

Apply a function to all nodes and collect results.

Parameters:: func (Callable[[_HKey], Any]) – Function to apply to each node
Returns:: list of results from applying func to each node
Return type:: list[Any]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}})
>>> # Get all keys with their depths
>>> results = root.map_nodes(lambda n: (n.key, n.get_depth()) if not n.is_root else None)
>>> [r for r in results if r is not None]
[('a', 0), ('b', 1)]

prune(predicate: Callable[[_HKey], bool]) → _HKey¶

Create a new tree containing only nodes matching the predicate and their ancestors.

This method implements “pruning with path preservation”, which filters the tree to keep only branches that lead to nodes satisfying the predicate. All ancestor nodes are automatically preserved to maintain tree connectivity and hierarchical structure.

The algorithm:

Identifies all nodes matching the predicate
Preserves all ancestors of matching nodes to maintain paths
Removes all other branches
Returns a new tree (original is unchanged)

Parameters:: predicate (Callable[[_HKey], bool]) – Function that takes an _HKey node and returns True if the node should be kept in the pruned tree. The function is called on each node during traversal.
Returns:: A new pruned tree (root node) containing only the filtered branches. The original tree remains unchanged. The returned tree preserves the same root properties (key, is_root flag).
Return type:: _HKey

Examples

>>> # Keep only nodes with key 'b' at depth 2
>>> root = _HKey.build_forest({'a': {'b': {'c': 1}, 'x': {'b': {'z': 1}}}})
>>> pruned = root.prune(lambda n: n.key == 'b' and n.get_depth() == 2)
>>> pruned.get_all_paths()
[['a'], ['a', 'b'], ['a', 'x'], ['a', 'x', 'b']]

>>> # Keep only leaf nodes
>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> pruned = root.prune(lambda n: n.is_leaf())
>>> pruned.get_all_paths()
[['a'], ['a', 'b'], ['a', 'c']]

>>> # Keep nodes with specific key value
>>> root = _HKey.build_forest({'a': {'target': 1, 'other': 2}, 'b': 3})
>>> pruned = root.prune(lambda n: n.key == 'target')
>>> pruned.get_all_paths()
[['a'], ['a', 'target']]

Notes

The pruned tree maintains hierarchical connectivity by preserving ancestor paths
This is a non-destructive operation; the original tree is not modified
If no nodes match the predicate, returns a tree with only the root node
The predicate is evaluated on every node in the tree (O(n) complexity)
All intermediate nodes required to reach matching nodes are preserved, even if they don’t match the predicate themselves

See also

filter_paths: Filter paths based on a predicate function
find_all: Find all nodes matching a predicate
dfs_find: Find first node matching a predicate using DFS
get_all_paths: Get all paths in the tree

get_statistics() → dict[str, Any]¶

Get comprehensive statistics about the tree.

Returns:: Dictionary containing various tree statistics
Return type:: dict[str, Any]

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}, 'd': 2})
>>> stats = root.get_statistics()
>>> stats['total_nodes']
4
>>> stats['max_depth']
2
>>> stats['leaf_count']
2

has_cycles() → tuple[bool, list[_HKey] | None]¶

Check if the tree contains cycles (should not in a proper tree).

Detects cycles by tracking visited nodes during DFS. A cycle exists if we encounter a node that’s already in the current path (back edge).

Returns:: (has_cycle, cycle_path) where cycle_path is the nodes forming the cycle
Return type:: tuple[bool, Optional[list[_HKey]]]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}})
>>> has_cycle, path = root.has_cycles()
>>> has_cycle
False

>>> # Manually create a cycle (should not happen normally)
>>> root = _HKey('a')
>>> child = root.add_child('b')
>>> # In a proper tree, this wouldn't happen

Notes

In a properly constructed _HKey tree, this should always return False. This method is useful for validation and debugging.

See also

is_valid_tree: Complete tree validation
is_dag: Check if structure is a Directed Acyclic Graph

is_dag() → bool¶

Check if the structure is a Directed Acyclic Graph (DAG).

A DAG is a directed graph with no cycles. All trees are DAGs, but not all DAGs are trees (DAGs can have multiple parents per node).

Returns:: True if structure is acyclic (is a DAG)
Return type:: bool

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> root.is_dag()
True

See also

has_cycles: Detect cycles with path information
is_valid_tree: Check if it’s a valid tree structure

is_valid_tree() → tuple[bool, list[str]]¶

Validate that this is a proper tree structure.

Checks multiple tree properties:

No cycles (acyclic)
Each non-root node has exactly one parent
Single root (or forest with explicit root marker)
All nodes reachable from root

Returns:: (is_valid, list_of_issues) where issues describes any problems found
Return type:: tuple[bool, list[str]]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}})
>>> is_valid, issues = root.is_valid_tree()
>>> is_valid
True
>>> issues
[]

See also

has_cycles: Check for cycles
check_parent_consistency: Verify parent references

check_parent_consistency() → list[str]¶

Check that parent-child relationships are consistent.

Verifies that:

Each child’s parent reference points to the correct parent
Each parent’s children list contains the child

Returns:: list of inconsistency messages (empty if consistent)
Return type:: list[str]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1}})
>>> issues = root.check_parent_consistency()
>>> len(issues)
0

is_complete_tree() → bool¶

Check if this is a complete tree.

A complete tree is a tree where all levels are fully filled except possibly the last level, which is filled from left to right.

Returns:: True if tree is complete
Return type:: bool

Examples

>>> # Complete tree: all levels filled
>>> root = _HKey('a')
>>> root.add_child('b')
>>> root.add_child('c')
>>> root.is_complete_tree()
True

>>> # Incomplete: last level not filled left-to-right
>>> root = _HKey('a')
>>> b = root.add_child('b')
>>> c = root.add_child('c')
>>> c.add_child('d')  # Only right child has children
>>> root.is_complete_tree()
False

Notes

This uses BFS to check level-by-level filling.

See also

is_perfect_tree: Check if perfectly balanced
is_balanced: Check if height-balanced

is_perfect_tree() → bool¶

Check if this is a perfect tree (all leaves at same depth, all internal nodes have 2 children).

A perfect tree is both complete and full:

All leaves are at the same depth
All internal nodes have exactly 2 children

Returns:: True if tree is perfect
Return type:: bool

Examples

>>> # Perfect tree with 2 children per node
>>> root = _HKey('a')
>>> b = root.add_child('b')
>>> c = root.add_child('c')
>>> b.add_child('d')
>>> b.add_child('e')
>>> c.add_child('f')
>>> c.add_child('g')
>>> root.is_perfect_tree()
True

Notes

This assumes binary tree structure. For n-ary trees, this checks if all internal nodes have the same number of children and all leaves are at the same depth.

See also

is_complete_tree: Less strict completeness check
is_balanced: Height-balanced check

is_balanced(threshold: int = 1) → bool¶

Check if the tree is height-balanced.

A balanced tree is one where the heights of the two subtrees of any node differ by at most the threshold value.

Parameters:: threshold (int, optional) – Maximum allowed height difference between subtrees, by default 1
Returns:: True if tree is balanced within the threshold
Return type:: bool

Examples

>>> root = _HKey.build_forest({'a': {'b': {'c': 1}}})
>>> root.is_balanced()
True

>>> # Unbalanced tree
>>> root = _HKey('a')
>>> b = root.add_child('b')
>>> b.add_child('c').add_child('d').add_child('e')
>>> root.add_child('f')
>>> root.is_balanced(threshold=1)
False

See also

get_balance_factor: Calculate balance factor for a node
is_perfect_tree: Check perfect balance

get_balance_factor() → int¶

Get the balance factor of this node.

Balance factor = max_child_height - min_child_height

Returns:: Balance factor (0 means perfectly balanced)
Return type:: int

Examples

>>> root = _HKey('a')
>>> b = root.add_child('b')
>>> c = root.add_child('c')
>>> b.add_child('d').add_child('e')  # Deep subtree
>>> root.get_balance_factor()
2

See also

is_balanced: Check if tree is balanced

count_nodes_by_degree() → dict[int, int]¶

Count nodes by their out-degree (number of children).

Returns:: Dictionary mapping degree to count of nodes with that degree
Return type:: dict[int, int]

Examples

>>> root = _HKey.build_forest({'a': {'b': 1, 'c': 2}})
>>> root.count_nodes_by_degree()
{2: 1, 0: 2}  # One node with 2 children, two nodes with 0 children

Notes

Degree 0 nodes are leaves. This is useful for analyzing tree branching structure.

See also

get_statistics: Comprehensive tree statistics

is_binary_tree() → bool¶

Check if this is a binary tree (all nodes have at most 2 children).

Returns:: True if all nodes have 0, 1, or 2 children
Return type:: bool

Examples

>>> root = _HKey('a')
>>> root.add_child('b')
>>> root.add_child('c')
>>> root.is_binary_tree()
True

>>> root.add_child('d')  # Now has 3 children
>>> root.is_binary_tree()
False

is_full_tree(n: int | None = None) → bool¶

Check if this is a full tree (all nodes have 0 or n children).

A full tree (also called proper or plane tree) has all internal nodes with the same number of children.

Parameters:: n (Optional[int], optional) – Expected number of children for internal nodes. If None, uses the number from the first internal node found.
Returns:: True if tree is full
Return type:: bool

Examples

>>> # Full binary tree (0 or 2 children)
>>> root = _HKey('a')
>>> b = root.add_child('b')
>>> c = root.add_child('c')
>>> b.add_child('d')
>>> b.add_child('e')
>>> root.is_full_tree(n=2)
True

See also

is_binary_tree: Check if binary
is_perfect_tree: Check if perfect

`_StackedDict` — Base engine¶

class ndict_tools.tools._StackedDict(*args, **kwargs)¶

Bases: defaultdict[Any, Any]

Internal base class for hierarchical nested dictionary structures.

_StackedDict is the central engine providing the foundation for all nested dictionary operations in the ndict_tools package. It extends Python’s defaultdict with hierarchical key support, path-based access, and specialized traversal methods.

Key features:

Hierarchical keys: Use lists as keys to access nested values: d[['a', 'b', 'c']]
Automatic nesting: Missing intermediate levels are created automatically
Path views: Access all paths via paths() and compact_paths()
Tree traversal: DFS and BFS algorithms for navigation
Deep operations: Specialized copy, equality, and conversion methods

Warning

This is a private class (underscore prefix) and should not be instantiated directly by external code. Access it through NestedDictionary or subclasses.

However, it can be used directly by developers for custom implementations as described in the usage documentation.

Parameters:

*args (iterable, optional) – Dictionaries or iterables to initialize from
**kwargs (dict, optional) – Either initialization data OR configuration via ‘default_setup’

indent¶

Indentation level for string representation (default: 2)

Type:: int

default_factory¶

Factory function for missing keys (inherited from defaultdict)

Type:: callable or None

_default_setup¶

Internal storage for configuration as set of (key, value) tuples

Type:: set

Examples

>>> setup = {'indent': 2, 'default_factory': None}
>>> sd = _StackedDict(default_setup=setup)
>>> sd['a']['b']['c'] = 1  # Automatic nesting
>>> sd[['a', 'b', 'c']]
1
>>> # Initialize with data
>>> sd = _StackedDict({'a': {'b': 1}}, default_setup=setup)
>>> list(sd.paths())
[['a'], ['a', 'b']]
>>> # Hierarchical key access
>>> sd[['a', 'b']] = 2
>>> sd['a']['b']
2

Notes

The class maintains two key invariants:

All nested dictionaries are _StackedDict instances (or subclass)
All instances share the same default_setup configuration

See also

_Paths: View object for accessing all paths
_CPaths: Compact representation of paths
_HKey: Internal tree structure for path operations

Initialize a new _StackedDict with configuration and optional data.

The constructor requires configuration via the ‘default_setup’ parameter, which must contain at least ‘indent’ and ‘default_factory’ keys. Additional initialization data can be provided through args or kwargs.

Parameters:

*args (iterable) – Dictionaries, _StackedDict instances, or iterables of (key, value) pairs
**kwargs (dict) – Either: - ‘default_setup’: dict with ‘indent’ and ‘default_factory’ keys - Direct key-value pairs to initialize (requires default_setup in kwargs)

Raises:

StackedKeyError – If ‘indent’ or ‘default_factory’ is missing from configuration
StackedAttributeError – If default_setup contains keys that aren’t valid attributes

Examples

>>> setup = {'indent': 2, 'default_factory': None}
>>> sd = _StackedDict(default_setup=setup)
>>> # Initialize with data
>>> sd = _StackedDict({'a': 1}, default_setup=setup)
>>> # Copy another _StackedDict
>>> sd2 = _StackedDict(sd, default_setup=setup)

Notes

Args are processed sequentially, later values override earlier ones
_StackedDict args are deep-copied
Regular dicts are converted to _StackedDict recursively
All configuration is propagated to nested instances

classmethod from_dict(dictionary: dict[Any, Any], **class_options) → _StackedDict¶

Recursively convert a standard dictionary to a _StackedDict or subclass.

Alternative constructor that transforms a regular nested dictionary into a _StackedDict-based structure. The target class is cls itself, eliminating the need to pass the class explicitly and preventing errors in recursive calls.

Parameters:

dictionary (dict) – The dictionary to transform (may be nested).
**class_options (dict) – Initialization options. Must contain default_setup key.

Returns:

New instance of cls containing the dictionary structure.

Return type:

_StackedDict

Raises:

StackedKeyError – If default_setup is missing from class_options.

Examples

>>> nd = NestedDictionary.from_dict(
...     {'a': {'b': 1}},
...     default_setup={'indent': 0, 'default_factory': None}
... )
>>> nd['a']['b']
1

Notes

Already-instantiated _StackedDict values are preserved as-is.
Regular dict values are recursively converted using cls.
Non-dict values are assigned directly.

See also

to_dict: Inverse operation.

to_json(path: str | Path, indent: int | None = None) → None¶

Serialize this dictionary to a JSON file.

Non-string keys are encoded as type-tagged strings of the form __type__:value (e.g., integer key 42 → "__int__:42", tuple key (1, 2) → "__tuple__:(1, 2)"). Round-trips are lossless for supported types: str, int, float, bool, flat tuple, flat frozenset. File I/O is delegated to json.dump.

Parameters:

path (str or Path) – Destination file path.
indent (int, optional) – JSON indentation level. Defaults to self.indent if not provided.

Examples

>>> nd = NestedDictionary({'a': {'b': 1}})
>>> nd.to_json('/tmp/nd.json')

See also

from_json: Reconstruct from a JSON file.

classmethod from_json(path: str | Path, **class_options) → _StackedDict¶

Reconstruct a _StackedDict (or subclass) from a JSON file.

Non-string keys stored as __type__:value tagged strings are decoded back to their original Python types. Round-trips are lossless for supported types: str, int, float, bool, flat tuple, flat frozenset.

Parameters:

path (str or Path) – Path to the JSON file.
**class_options (dict) – Passed to cls.from_dict; must include default_setup.

Returns:

Reconstructed instance of cls.

Return type:

_StackedDict

Examples

>>> nd = NestedDictionary.from_json(
...     '/tmp/nd.json',
...     default_setup={'indent': 0, 'default_factory': None}
... )

See also

to_json: Serialize to a JSON file.

to_pickle(path: str | Path, protocol: int | None = None) → None¶

Serialize this dictionary to a pickle file with SHA-256 verification.

Writes two files: <path> (pickle) and <path>.sha256 (hex digest).

Parameters:

path (str or Path) – Destination file path.
protocol (int, optional) – Pickle protocol. Defaults to pickle.DEFAULT_PROTOCOL.

Warns:

UserWarning – Pickle is unsafe with untrusted files.

See also

from_pickle: Reconstruct from a pickle file.

classmethod from_pickle(path: str | Path, verify: bool = True, **class_options) → _StackedDict¶

Reconstruct a _StackedDict (or subclass) from a pickle file.

Parameters:

path (str or Path) – Path to the pickle file.
verify (bool, optional) – If True (default), verify the SHA-256 sidecar before loading.
**class_options (dict) – Not used directly (the pickled object carries its own state), but accepted for API symmetry with from_json.

Returns:

Reconstructed instance.

Return type:

_StackedDict

Raises:

StackedValueError – If verify=True and the digest mismatches or sidecar is absent.

Warns:

UserWarning – Pickle is unsafe with untrusted files.

See also

to_pickle: Serialize to a pickle file.

property default_setup: list[tuple[str, Any]]¶

Get configuration as an ordered list of (key, value) tuples.

Returns a deterministic view of the internal configuration with priority ordering: ‘indent’, ‘default_factory’, then alphabetically.

Returns:: Configuration as [(key, value), …] in priority order
Return type:: list of tuple

Examples

>>> sd = _StackedDict(default_setup={'indent': 2, 'default_factory': None})
>>> sd.default_setup
[('indent', 2), ('default_factory', None)]

See also

default_setup.setter: set new configuration

equal(other)¶

Check equality: same class, configuration, and content.

Two _StackedDict instances are equal if they have: 1. Identical class type (exact match, not subclasses) 2. Identical default_setup configuration 3. Identical dictionary structure and values

Parameters:: other (Any) – Object to compare with
Returns:: True if all conditions met
Return type:: bool

Examples

>>> setup = {'indent': 2, 'default_factory': None}
>>> sd1 = _StackedDict({'a': 1}, default_setup=setup)
>>> sd2 = _StackedDict({'a': 1}, default_setup=setup)
>>> sd1 == sd2
True

>>> # Different setup
>>> sd3 = _StackedDict({'a': 1}, default_setup={'indent': 4, 'default_factory': None})
>>> sd1 == sd3
False

See also

__eq__: dictionaries equalities
__ne__: Inequality check
similar: Compare content only (ignore class/setup)
isomorph: Compare as plain dicts

similar(other)¶

Check if two structures share the same content (ignoring setup).

Two structures are similar if they: 1. Are both _StackedDict instances (any subclass) 2. Have identical dictionary content (keys and values)

Configuration differences are ignored.

Parameters:: other (Any) – Object to compare with
Returns:: True if both are _StackedDict with same content
Return type:: bool

Examples

>>> setup1 = {'indent': 2, 'default_factory': None}
>>> setup2 = {'indent': 4, 'default_factory': _StackedDict}
>>> sd1 = _StackedDict({'a': 1}, default_setup=setup1)
>>> sd2 = _StackedDict({'a': 1}, default_setup=setup2)
>>> sd1 == sd2
False
>>> sd1.similar(sd2)
True

See also

__eq__: dictionaries equalities
__ne__: Inequality check
equal: Strict equality (includes setup)
isomorph: Compare as plain dicts

isomorph(other)¶

Check if structures are isomorphic (same keys/values, any dict type).

Two structures are isomorphic if they represent the same nested dictionary structure, regardless of whether they’re _StackedDict, plain dict, or any other dict-like type.

Parameters:: other (dict or _StackedDict) – Dictionary to compare with
Returns:: True if structure-preserving mapping exists
Return type:: bool

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> regular_dict = {'a': {'b': 1}}
>>> sd.isomorph(regular_dict)
True

>>> sd.isomorph({'a': {'b': 2}})
False

Notes

Checks if sd[k1]…[kn] == other[k1]…[kn] for all paths. This is the most permissive comparison method.

See also

__eq__: dictionaries equalities
__ne__: Inequality check
equal: Strict equality
similar: Compare _StackedDict instances

unpacked_items() → Generator[tuple[tuple[Any, ...], Any], None, None]¶

Generate all (path, value) pairs from nested structure.

Yields terminal values along with their hierarchical paths as tuples. This provides a flattened view of the entire nested dictionary.

Yields:: tuple – (path_tuple, value) for each terminal value

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> list(sd.unpacked_items())
[(('a', 'b'), 1), (('c',), 2)]

>>> # Empty dict as value
>>> sd = _StackedDict({'a': {}}, default_setup={'indent': 2, 'default_factory': None})
>>> list(sd.unpacked_items())
[(('a',), {})]

Notes

Uses depth-first traversal
Empty dictionaries are treated as terminal values
Paths are immutable tuples for hashability

See also

unpacked_keys: Get only the paths
unpacked_values: Get only the values
dfs: Depth-first traversal alternative returning lists

unpacked_keys() → Generator[tuple[Any, ...], None, None]¶

Generate all hierarchical paths (keys) from nested structure.

Yields the path to each terminal value as a tuple of keys, providing access to all navigable paths in the dictionary.

Yields:: tuple – Path as tuple of keys

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> list(sd.unpacked_keys())
[('a', 'b')]

>>> sd = _StackedDict({'a': {'b': 1, 'c': 2}, 'd': 3}, default_setup={'indent': 2, 'default_factory': None})
>>> sorted(sd.unpacked_keys())
[('a', 'b'), ('a', 'c'), ('d',)]

See also

unpacked_items: Get (path, value) pairs
paths: Get paths as _Paths view object

unpacked_values() → Generator[Any, None, None]¶

Generate all terminal values from nested structure.

Yields only the leaf values, discarding path information. Useful for collecting all data values regardless of structure.

Yields:: Any – Each leaf value in the nested dictionary

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> list(sd.unpacked_values())
[1, 2]

>>> # Empty dict is a value
>>> sd = _StackedDict({'a': {}, 'b': 1}, default_setup={'indent': 2, 'default_factory': None})
>>> list(sd.unpacked_values())
[{}, 1]

See also

unpacked_items: Get (path, value) pairs
leaves: Alternative method returning list

to_dict() → dict[Any, Any]¶

Convert to a standard nested dictionary.

Recursively converts the _StackedDict and all nested _StackedDict instances to regular Python dictionaries, removing all special functionality but preserving the structure.

Returns:: Regular nested dictionary with same structure
Return type:: dict

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> regular = sd.to_dict()
>>> type(regular)
<class 'dict'>
>>> regular
{'a': {'b': 1}}

Notes

All _StackedDict instances are converted recursively
Other value types are preserved as-is
Inverse operation of from_dict()

See also

from_dict: Convert dict to _StackedDict
__deepcopy__: Create _StackedDict copy

copy() → _StackedDict¶

Create a shallow copy of the _StackedDict.

Returns:: Shallow copy with same configuration
Return type:: _StackedDict

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd2 = sd.copy()
>>> sd2['a'] is sd['a']
True

See also

__copy__: Internal implementation
deepcopy: Create independent copy

deepcopy() → _StackedDict¶

Create a deep copy of the _StackedDict.

Creates a completely independent copy where all nested structures are recursively duplicated.

Returns:: Complete independent copy
Return type:: _StackedDict

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd2 = sd.deepcopy()
>>> sd2['a']['b'] = 999
>>> sd['a']['b']
1

See also

__deepcopy__: Internal implementation
copy: Shallow copy alternative

pop(key: Any | list[Any], default=None) → Any¶

Remove and return value at key or hierarchical path.

Removes the specified key (flat or hierarchical) and returns its value. Automatically cleans up empty parent dictionaries after removal. If the key doesn’t exist, returns the default value or raises an error.

Parameters:

key (Any or list[Any]) – Single key or hierarchical path to remove
default (Any, optional) – Value to return if key doesn’t exist

Returns:

The value that was removed

Return type:

Any

Raises:

StackedKeyError – If key doesn’t exist and no default provided

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.pop('c')
2
>>> 'c' in sd
False

>>> # Hierarchical key
>>> sd.pop(['a', 'b'])
1
>>> 'a' in sd  # Empty 'a' was removed
False

>>> # With default
>>> sd.pop('nonexistent', 'default_value')
'default_value'

See also

popitem: Remove and return last item
__delitem__: Delete without returning value

popitem()¶

Remove and return the last item as (path, value) pair.

Removes the last item in the most deeply nested dictionary, returning its full hierarchical path and value. Uses depth-first traversal to locate the deepest rightmost item.

Returns:: (path_list, value) where path_list is the hierarchical path
Return type:: tuple
Raises:: StackedIndexError – If the dictionary is empty

Examples

>>> sd = _StackedDict({'a': {'b': 1, 'c': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> path, value = sd.popitem()
>>> path
['a', 'c']
>>> value
2

>>> # Empty dictionary
>>> sd = _StackedDict(default_setup={'indent': 2, 'default_factory': None})
>>> sd.popitem()  # Raises StackedIndexError

Notes

Follows DFS to find the last (rightmost, deepest) item
Cleans up empty parent dictionaries automatically
Path is returned as a list of keys

See also

pop: Remove item by key
unpacked_items: View all (path, value) pairs

update(_StackedDict__m: Mapping[Any, Any] | Iterable[tuple[Any, Any]] | None = None, **kwargs) → None¶

Update _StackedDict with key/value pairs from mapping, iterable, or kwargs.

Merges the provided mapping, iterable of key-value pairs, or keyword arguments into this _StackedDict, converting regular dicts to _StackedDict instances recursively while preserving existing _StackedDict values.

Parameters:

__m (Mapping[Any, Any] or Iterable[tuple[Any, Any]], optional) – Either a mapping (dict, _StackedDict) or an iterable of (key, value) tuples to merge. If None, only kwargs are used.
**kwargs (Any) – Additional key/value pairs to merge

Examples

>>> sd = _StackedDict({'a': 1}, default_setup={'indent': 2, 'default_factory': None})

>>> # From dict
>>> sd.update({'b': 2, 'c': {'d': 3}})
>>> sd['c']['d']
3

>>> # From iterable
>>> sd.update([('e', 4), ('f', {'g': 5})])
>>> sd['f']['g']
5

>>> # Using kwargs
>>> sd.update(h=6, i={'j': 7})
>>> sd['i']['j']
7

>>> # Combined
>>> sd.update({'k': 8}, l=9)
>>> sd['k'], sd['l']
(8, 9)

Notes

Accepts mappings (dict, _StackedDict, etc.)
Accepts iterables of (key, value) tuples
Accepts keyword arguments
Regular dicts are converted to _StackedDict recursively
_StackedDict values are accepted directly with synchronized config
Configuration is synchronized across all nested instances
Later values override earlier ones for duplicate keys

See also

__init__: Initialization with data
__setitem__: set individual items
from_dict: Convert dict to _StackedDict

is_key(key: Any) → bool¶

Check if an atomic key exists at any level in the hierarchy.

Searches through all hierarchical paths to determine if the given atomic key appears anywhere in the nested structure. Does not accept hierarchical paths (lists).

Parameters:: key (Any) – Atomic key to search for (not a list)
Returns:: True if key exists at any level
Return type:: bool
Raises:: StackedKeyError – If key is a list (hierarchical keys not allowed)

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.is_key('b')
True
>>> sd.is_key('c')
False

>>> # Lists not allowed
>>> sd.is_key(['a', 'b'])  # Raises StackedKeyError

Notes

Only searches for atomic keys
Checks all nesting levels
O(n) complexity where n is total number of keys

See also

occurrences: Count how many times key appears
key_list: Get all paths containing the key

occurrences(key: Any) → int¶

Count occurrences of an atomic key throughout the hierarchy.

Returns the total number of times a key appears in the nested structure, counting each occurrence in every hierarchical path.

Parameters:: key (Any) – Atomic key to count
Returns:: Number of occurrences (0 if key doesn’t exist)
Return type:: int

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': {'b': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.occurrences('b')
2
>>> sd.occurrences('a')
1
>>> sd.occurrences('z')
0

>>> # Key appearing multiple times in same path
>>> sd = _StackedDict({'a': {'a': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.occurrences('a')
2

See also

is_key: Check if key exists
key_list: Get all paths containing the key

key_list(key: Any) → list[list[Any]]¶

Get all hierarchical paths containing a specific key.

Returns a list of all complete paths (as tuples) that contain the specified atomic key at any position in the path.

Parameters:: key (Any) – Atomic key to search for
Returns:: list of paths (as tuples) containing the key
Return type:: list
Raises:: StackedKeyError – If key doesn’t exist in the dictionary

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': {'b': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.key_list('b')
[('a', 'b'), ('c', 'b')]

>>> sd.key_list('a')
[('a', 'b')]

>>> sd.key_list('nonexistent')  # Raises StackedKeyError

See also

is_key: Check if key exists
items_list: Get values at paths containing key
occurrences: Count occurrences

items_list(key: Any) → list[Any]¶

Get all values associated with paths containing a specific key.

Returns a list of all terminal values whose hierarchical paths contain the specified atomic key at any position.

Parameters:: key (Any) – Atomic key to search for
Returns:: list of values from paths containing the key
Return type:: list
Raises:: StackedKeyError – If key doesn’t exist in the dictionary

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': {'b': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.items_list('b')
[1, 2]

>>> sd.items_list('a')
[1]

>>> sd.items_list('nonexistent')  # Raises StackedKeyError

Notes

Returns values in the order they’re encountered during traversal
Multiple values returned if key appears in multiple paths
Only returns terminal (leaf) values

See also

key_list: Get paths containing the key
unpacked_items: Get all (path, value) pairs

paths() → _Paths¶

Get a view object for all hierarchical paths in the dictionary.

Returns a lazy view similar to dict.keys() that provides access to all hierarchical paths without materializing them in memory. The view supports iteration, length queries, and membership testing.

Returns:: Lazy view object for all hierarchical paths
Return type:: _Paths

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> paths = sd.paths()
>>> len(paths)
3
>>> ['a', 'b'] in paths
True
>>> list(paths)
[['a'], ['a', 'b'], ['c']]

Notes

Paths are generated lazily during iteration
Internal _HKey tree is built on first access
View updates automatically if dictionary changes
More efficient than unpacked_keys() for large structures

See also

compact_paths: Get factorized/compact representation
unpacked_keys: Generate paths as tuples
_Paths: View class documentation

compact_paths() → _CPaths¶

Get a compact/factorized representation of all paths.

Returns a view that represents the hierarchical structure in a factorized form where common prefixes are shared. This provides a more concise representation useful for visualization and analysis.

Returns:: Compact view with factorized path structure
Return type:: _CPaths

Examples

>>> sd = _StackedDict({'a': {'b': 1, 'c': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> c_paths = sd.compact_paths()
>>> c_paths.structure
[['a', 'b', 'c']]

>>> # Expand back to full paths
>>> c_paths.expand()
[['a'], ['a', 'b'], ['a', 'c']]

Notes

Provides bijective mapping between expanded and compact forms
Useful for path coverage analysis
More compact representation for deeply nested structures

See also

paths: Get full paths view
_CPaths: Compact view class documentation

dfs(node=None, path=None) → Generator[tuple[list[Any], Any], None, None]¶

Depth-First Search traversal of the nested dictionary.

Recursively traverses the dictionary in depth-first order, yielding each hierarchical path (as list) and its corresponding value. This includes both intermediate nodes and leaf values.

Parameters:

node (dict, optional) – Current node being traversed (defaults to root/self)
path (list, optional) – Current path being constructed (defaults to empty list)

Yields:

tuple – (path_list, value) for each node in DFS order

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> for path, value in sd.dfs():
...     print(f'{path} -> {value}')
['a'] -> <_StackedDict>
['a', 'b'] -> 1
['c'] -> 2

Notes

Visits nodes before their children (pre-order)
Returns paths as mutable lists (unlike unpacked_keys)
Includes intermediate dictionary nodes
Useful for tree-based operations

See also

bfs: Breadth-first traversal
unpacked_items: Similar but only terminal values

bfs() → Generator[tuple[tuple[Any, ...], Any], None, None]¶

Breadth-First Search traversal of the nested dictionary.

Iteratively traverses the dictionary level by level, visiting all nodes at depth N before moving to depth N+1. Uses a queue (deque) for efficient FIFO operations.

Yields:: tuple – (path_tuple, value) for each node in BFS order

Examples

>>> sd = _StackedDict({'a': {'b': {'c': 1}}}, default_setup={'indent': 2, 'default_factory': None})
>>> for path, value in sd.bfs():
...     print(f'{path} -> {value}')
('a',) -> <_StackedDict>
('a', 'b') -> <_StackedDict>
('a', 'b', 'c') -> 1

>>> # Only leaf values
>>> sd = _StackedDict({'a': {'b': 1, 'c': 2}, 'd': 3}, default_setup={'indent': 2, 'default_factory': None})
>>> leaves = [(p, v) for p, v in sd.bfs() if not isinstance(v, _StackedDict)]
>>> leaves
[(('a', 'b'), 1), ('a', 'c'), 2), (('d',), 3)]

Notes

Visits all nodes at same depth before going deeper
Returns paths as immutable tuples
Includes all nodes (intermediate and terminal)
More memory efficient than collecting all paths first

See also

dfs: Depth-first traversal
_HKey.bfs: Tree-based BFS traversal

height() → int¶

Compute the height (maximum depth) of the nested structure.

The height is defined as the length of the longest path from root to any leaf node. An empty dictionary has height 0.

Returns:: Maximum path length in the dictionary
Return type:: int

Examples

>>> sd = _StackedDict({'a': 1}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.height()
1

>>> sd = _StackedDict({'a': {'b': {'c': 1}}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.height()
3

>>> sd = _StackedDict(default_setup={'indent': 2, 'default_factory': None})
>>> sd.height()
0

Notes

Empty dictionary has height 0
Single-level dictionary has height 1
O(n) complexity where n is number of paths

See also

size: Count total number of keys
leaves: Get all leaf values

size() → int¶

Compute the total number of keys (nodes) in the structure.

Counts all keys at all nesting levels, including both intermediate dictionary keys and terminal value keys.

Returns:: Total number of keys across all levels
Return type:: int

Examples

>>> sd = _StackedDict({'a': {'b': 1}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.size()
2

>>> sd = _StackedDict({'a': {'b': 1, 'c': 2}, 'd': 3}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.size()
4

Notes

Counts all keys at all levels
Equivalent to number of nodes in tree representation
Different from len() which only counts top-level keys

See also

height: Get maximum depth
__len__: Get top-level key count

leaves() → list[Any]¶

Extract all leaf (terminal) values from the nested structure.

Returns a list of all values that are not themselves nested dictionaries, i.e., all terminal nodes in the tree structure.

Returns:: list of all leaf values
Return type:: list

Examples

>>> sd = _StackedDict({'a': {'b': 1}, 'c': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.leaves()
[1, 2]

>>> sd = _StackedDict({'a': {'b': {'c': 1}}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.leaves()
[1]

>>> # Empty dict as leaf value
>>> sd = _StackedDict({'a': {}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.leaves()
[{}]

Notes

Returns values in DFS order
Empty dictionaries are considered leaf values
Plain dicts (not _StackedDict) are also leaves

See also

unpacked_values: Generator alternative
dfs: Traversal including intermediate nodes

is_balanced() → bool¶

Check if the nested structure is height-balanced.

A balanced dictionary is one where the height difference between any two subtrees at the same level differs by at most 1. This indicates a relatively uniform distribution of nesting depth.

Returns:: True if structure is balanced, False otherwise
Return type:: bool

Examples

>>> # Balanced
>>> sd = _StackedDict({'a': {'b': 1}, 'c': {'d': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.is_balanced()
True

>>> # Unbalanced
>>> sd = _StackedDict({'a': {'b': {'c': 1}}, 'd': 2}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.is_balanced()
False

Notes

Uses recursive height calculation
Checks balance at every node
Empty dictionary is considered balanced
Useful for identifying skewed structures

See also

height: Get maximum depth
_HKey.is_balanced: Tree-based balance check

ancestors(value)¶

Find the hierarchical path (ancestors) leading to a specific value.

Searches the nested structure for the given value and returns the complete path of keys leading to it, excluding the final key. This returns the “ancestry” of the value in the tree.

Parameters:: value (Any) – Value to search for in the nested dictionary
Returns:: list of keys forming the path to the value (excluding final key)
Return type:: list
Raises:: StackedValueError – If value is not found in the dictionary

Examples

>>> sd = _StackedDict({'a': {'b': {'c': 1}}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.ancestors(1)
['a', 'b']

>>> sd = _StackedDict({'a': {'b': 1}, 'c': {'d': 2}}, default_setup={'indent': 2, 'default_factory': None})
>>> sd.ancestors(2)
['c']

>>> sd.ancestors(999)  # Raises StackedValueError

Notes

Returns path excluding the final key (direct parent of value)
Uses DFS to find the first occurrence
If value appears multiple times, returns first found path
Empty list returned for top-level values

See also

dfs: Depth-first traversal
unpacked_items: Get all (path, value) pairs

`_Paths` — Path view¶

class ndict_tools.tools._Paths(stacked_dict: _StackedDict | None = None)¶

Bases: object

A lazy view providing access to all hierarchical paths in a nested dictionary.

Similar to the standard dict_keys view, but designed specifically for hierarchical paths in nested dictionaries. Uses an internal _HKey tree for efficient path generation and querying.

The view provides lazy iteration over all paths without storing them in memory, and leverages the optimized tree structure of _HKey for fast operations.

Warning

This is a private class (underscore prefix) and should not be instantiated directly by external code. Access it through NestedDictionary

Parameters:: stacked_dict (_StackedDict) – The nested dictionary to create a view for

_stacked_dict¶

Reference to the source dictionary

Type:: _StackedDict

_hkey¶

Internal tree structure for efficient path operations (lazy-built)

Type:: _HKey

Examples

>>> data = _StackedDict({'a': {'b': 1}, 'c': 2})
>>> paths = _Paths(data)
>>> list(paths)
[['a'], ['a', 'b'], ['c']]
>>> ['a', 'b'] in paths
True
>>> len(paths)
3

See also

_CPaths: Factorized representation of paths
_StackedDict.paths: building paths for nested dictionaries.

get_children(path: list[Any]) → list[Any]¶

Get child keys at the next level after the given path.

Parameters:: path (list[Any]) – Path to query
Returns:: list of child keys, empty if path not found
Return type:: list[Any]

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': 1, 'c': 2}}))
>>> paths.get_children(['a'])
['b', 'c']
>>> paths.get_children(['a', 'b'])
[]

See also

has_children: Check if path has children

has_children(path: list[Any]) → bool¶

Check if a path has any children.

Parameters:: path (list[Any]) – Path to check
Returns:: True if path has children
Return type:: bool

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': 1}}))
>>> paths.has_children(['a'])
True
>>> paths.has_children(['a', 'b'])
False

get_subtree_paths(prefix: list[Any]) → list[list[Any]]¶

Get all paths that start with the given prefix.

Parameters:: prefix (list[Any]) – Prefix to filter by
Returns:: list of paths with this prefix
Return type:: list[list[Any]]

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': {'c': 1}, 'd': 2}}))
>>> paths.get_subtree_paths(['a'])
[['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'd']]

See also

filter_paths: Filter paths by predicate

filter_paths(predicate: Callable[[list[Any]], bool]) → list[list[Any]]¶

Filter paths based on a predicate function.

Parameters:: predicate (Callable[[list[Any]], bool]) – Function that returns True for paths to include
Returns:: Filtered list of paths
Return type:: list[list[Any]]

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': 1}, 'c': 2}))
>>> # Get paths longer than 1
>>> paths.filter_paths(lambda p: len(p) > 1)
[['a', 'b']]

See also

get_subtree_paths: Filter by prefix

get_depth() → int¶

Get the maximum depth of paths.

Returns:: Maximum path length
Return type:: int

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': {'c': 1}}}))
>>> paths.get_depth()
3

get_leaf_paths() → list[list[Any]]¶

Get all leaf paths (paths with no children).

Returns:: list of leaf paths
Return type:: list[list[Any]]

Examples

>>> paths = _Paths(_StackedDict({'a': {'b': 1}, 'c': 2}))
>>> paths.get_leaf_paths()
[['a', 'b'], ['c']]

to_compact() → _CPaths¶

Convert this _Paths to a _CPaths.

Returns:: Compact representation with the same paths
Return type:: _CPaths

`_CPaths` — Compact path view¶

class ndict_tools.tools._CPaths(stacked_dict: _StackedDict | None = None)¶

Bases: _Paths

A lazy view providing compact representation of hierarchical paths.

Extends _Paths to provide a factorized/compact representation where the hierarchical structure is represented as nested lists: - Leaf nodes: just the key - Internal nodes: [key, child1, child2, …]

The compact structure uses a bijective mapping: - Paths → Compact structure (factorization) - Compact structure → Paths (expansion)

Warning

This is a private class (underscore prefix) and should not be instantiated directly by external code.

Parameters:: stacked_dict (_StackedDict) – The nested dictionary to create a compact view for

_structure¶

Compact representation of paths (lazy-built)

Type:: Optional[list[Any]]

Examples

>>> data = _StackedDict({'a': 1, 'b': {'c': 2, 'd': 3}})
>>> c_paths = _CPaths(data)
>>> c_paths.structure
[['a'], ['b', 'c', 'd']]
>>> list(c_paths)  # Inherited from _Paths
[['a'], ['b'], ['b', 'c'], ['b', 'd']]

See also

_Paths: Base class for path views

property structure: list[Any]¶

Get the compact structure representation.

Returns:: Compact representation as nested lists
Return type:: list[Any]

Examples

>>> c_paths = _CPaths(_StackedDict({'a': {'b': 1, 'c': 2}}))
>>> c_paths.structure
[['a', 'b', 'c']]

static expand_structure(structure: list[Any]) → list[list[Any]]¶

Expand compact structure back to full paths.

This is the inverse operation of compactification, establishing the bijection between compact and expanded representations.

Parameters:: structure (list[Any]) – Compact structure to expand
Returns:: All expanded paths
Return type:: list[list[Any]]

Examples

>>> structure = [['a'], ['b', 'c', 'd']]
>>> _CPaths.expand_structure(structure)
[['a'], ['b'], ['b', 'c'], ['b', 'd']]

>>> structure = [['x', ['y', 'z1', 'z2'], 'a']]
>>> _CPaths.expand_structure(structure)
[['x'], ['x', 'y'], ['x', 'y', 'z1'], ['x', 'y', 'z2'], ['x', 'a']]

expand() → list[list[Any]]¶

Expand this instance’s compact structure to full paths.

Returns:: All expanded paths
Return type:: list[list[Any]]

Examples

>>> c_paths = _CPaths(_StackedDict({'a': {'b': 1}}))
>>> c_paths.expand()
[['a'], ['a', 'b']]

Notes

This is equivalent to calling expand_structure(self.structure), and should give the same result as list(self) from the parent class.

is_covering(stacked_dict) → bool¶

Check if this _CPaths covers all paths in the given _StackedDict.

A _CPaths is “covering” if its expanded paths exactly match all paths in the target _StackedDict.

Parameters:: stacked_dict (_StackedDict) – The _StackedDict to compare against
Returns:: True if all paths in stacked_dict are present in this _CPaths
Return type:: bool

Examples

>>> sdict = _StackedDict({'a': {'b': 1}, 'c': 2})
>>> c_paths = _CPaths(sdict)
>>> c_paths.is_covering(sdict)
True

>>> # Partial coverage
>>> c_paths.structure = [['a']]  # Only covers 'a', not 'a.b' or 'c'
>>> c_paths.is_covering(sdict)
False

Notes

For a _CPaths created directly from a _StackedDict: _CPaths(sdict).is_covering(sdict) will ALWAYS return True because the compact structure is built from all paths in sdict.

coverage(stacked_dict) → float¶

Calculate the coverage percentage of this _CPaths over a _StackedDict.

Coverage is defined as the ratio of paths in this _CPaths that exist in the target _StackedDict, divided by the total number of paths in the _StackedDict.

Parameters:: stacked_dict (_StackedDict) – The _StackedDict to compare against
Returns:: Coverage percentage between 0.0 and 1.0 (or > 1.0 if _CPaths contains paths not in stacked_dict)
Return type:: float

Examples

>>> sdict = _StackedDict({'a': {'b': 1, 'c': 2}, 'd': 3})
>>> c_paths = _CPaths(sdict)
>>> c_paths.coverage(sdict)
1.0

>>> # Partial coverage: only 'a' and 'a.b' out of 4 paths
>>> c_paths.structure = [['a', 'b']]
>>> c_paths.coverage(sdict)
0.5

>>> # Over-coverage: includes paths not in sdict
>>> c_paths.structure = [['a', 'b', 'c'], ['d'], ['e']]
>>> c_paths.coverage(sdict)
1.25

Notes

For a _CPaths created directly from a _StackedDict: _CPaths(sdict).coverage(sdict) will ALWAYS return 1.0 because all paths from sdict are included.

The coverage can be > 1.0 if the _CPaths contains more paths than the _StackedDict (e.g., manually set structure).

missing_paths(stacked_dict) → list[list[Any]]¶

Get paths from this _CPaths that are NOT in the _StackedDict.

Returns the list of paths that exist in this _CPaths’s expanded form but do not exist in the target _StackedDict. Useful for identifying extra or invalid paths.

Parameters:: stacked_dict (_StackedDict) – The _StackedDict to compare against
Returns:: list of paths in _CPaths but not in stacked_dict
Return type:: list[list[Any]]

Examples

>>> sdict = _StackedDict({'a': {'b': 1}})
>>> c_paths = _CPaths(sdict)
>>> c_paths.missing_paths(sdict)
[]

>>> # Add extra paths
>>> c_paths.structure = [['a', 'b', 'c'], ['d']]
>>> c_paths.missing_paths(sdict)
[['a', 'c'], ['d']]

Notes

For a _CPaths created directly from a _StackedDict: _CPaths(sdict).missing_paths(sdict) will ALWAYS return [] because all paths are derived from sdict.

See also

uncovered_paths: Get paths in _StackedDict not covered by _CPaths

uncovered_paths(stacked_dict) → list[list[Any]]¶

Get paths from _StackedDict that are NOT covered by this _CPaths.

Returns the list of paths that exist in the target _StackedDict but are not present in this _CPaths’s expanded form. Useful for identifying gaps in coverage.

Parameters:: stacked_dict (_StackedDict) – The _StackedDict to compare against
Returns:: list of paths in stacked_dict but not in _CPaths
Return type:: list[list[Any]]

Examples

>>> sdict = _StackedDict({'a': {'b': 1, 'c': 2}, 'd': 3})
>>> c_paths = _CPaths(sdict)
>>> c_paths.uncovered_paths(sdict)
[]

>>> # Partial structure
>>> c_paths.structure = [['a', 'b']]
>>> c_paths.uncovered_paths(sdict)
[['a', 'c'], ['d']]

Notes

For a _CPaths created directly from a _StackedDict: _CPaths(sdict).uncovered_paths(sdict) will ALWAYS return [] because all paths from sdict are included.

See also

missing_paths: Get paths in _CPaths not in _StackedDict
coverage: Get coverage ratio

tools — Core Infrastructure¶

Module-level helpers¶

_HKey — Hierarchical key node¶

_StackedDict — Base engine¶

_Paths — Path view¶

_CPaths — Compact path view¶

`tools` — Core Infrastructure¶

`_HKey` — Hierarchical key node¶

`_StackedDict` — Base engine¶

`_Paths` — Path view¶

`_CPaths` — Compact path view¶