tessl/pypi-django-treebeard

Efficient tree implementations for Django models providing three different tree algorithms with unified API

—

Pending

Overview

Eval results

Files

Tree Navigation

Name: tessl/pypi-django-treebeard
Author: tessl

Methods for traversing tree structures, getting related nodes, and querying tree relationships. These navigation methods work consistently across all tree implementations and are optimized for each algorithm's strengths.

Capabilities

Parent and Root Access

Methods for accessing parent nodes and tree roots.

def get_parent(self, update=False):
    """
    Get the parent node of this node.
    
    Parameters:
        update (bool): Whether to refresh from database
        
    Returns:
        Node or None: Parent node, or None if this is a root node
    """

def get_root(self):
    """
    Get the root node of this tree.
    
    Returns:
        Node: The root node of the tree containing this node
    """

Usage examples:

# Get parent
parent = child_node.get_parent()
if parent:
    print(f"Parent: {parent.name}")
else:
    print("This is a root node")

# Get root of current tree
root = any_node.get_root()
print(f"Tree root: {root.name}")

Children Access

Methods for accessing direct child nodes.

def get_children(self):
    """
    Get queryset of direct child nodes.
    
    Returns:
        QuerySet: Direct children of this node, ordered appropriately
    """

def get_children_count(self):
    """
    Get count of direct child nodes.
    
    Returns:
        int: Number of direct children
    """

def get_first_child(self):
    """
    Get the first (leftmost) child node.
    
    Returns:
        Node or None: First child node, or None if no children
    """

def get_last_child(self):
    """
    Get the last (rightmost) child node.
    
    Returns:
        Node or None: Last child node, or None if no children
    """

Usage examples:

# Get all children
children = parent.get_children()
for child in children:
    print(f"Child: {child.name}")

# Check if node has children
if parent.get_children_count() > 0:
    print("Node has children")

# Get specific child positions
first = parent.get_first_child()
last = parent.get_last_child()

Sibling Access

Methods for accessing sibling nodes at the same tree level.

def get_siblings(self):
    """
    Get queryset of all sibling nodes, including this node.
    
    Returns:
        QuerySet: All nodes at same level, including self
    """

def get_first_sibling(self):
    """
    Get the first (leftmost) sibling node.
    
    Returns:
        Node: First sibling (may be self if this is first)
    """

def get_last_sibling(self):
    """
    Get the last (rightmost) sibling node.
    
    Returns:
        Node: Last sibling (may be self if this is last)
    """

def get_prev_sibling(self):
    """
    Get the previous (left) sibling node.
    
    Returns:
        Node or None: Previous sibling, or None if this is first
    """

def get_next_sibling(self):
    """
    Get the next (right) sibling node.
    
    Returns:
        Node or None: Next sibling, or None if this is last
    """

Usage examples:

# Get all siblings (including self)
siblings = node.get_siblings()
print(f"Total siblings: {siblings.count()}")

# Navigate between siblings
prev_node = node.get_prev_sibling()
next_node = node.get_next_sibling()

# Get sibling boundaries
first_sibling = node.get_first_sibling()
last_sibling = node.get_last_sibling()

Ancestor Access

Methods for accessing ancestor nodes up the tree hierarchy.

def get_ancestors(self):
    """
    Get queryset of all ancestor nodes.
    
    Returns nodes from root down to immediate parent.
    
    Returns:
        QuerySet: All ancestor nodes, ordered from root to parent
    """

Usage examples:

# Get all ancestors
ancestors = node.get_ancestors()
for ancestor in ancestors:
    print(f"Ancestor: {ancestor.name}")

# Build breadcrumb navigation
breadcrumbs = []
for ancestor in node.get_ancestors():
    breadcrumbs.append(ancestor.name)
breadcrumbs.append(node.name)
print(" > ".join(breadcrumbs))

# Check if node has ancestors
if node.get_ancestors().exists():
    print("Node is not a root")

Descendant Access

Methods for accessing descendant nodes down the tree hierarchy.

def get_descendants(self):
    """
    Get queryset of all descendant nodes.
    
    Returns all nodes in the subtree rooted at this node,
    excluding this node itself.
    
    Returns:
        QuerySet: All descendant nodes in depth-first order
    """

def get_descendant_count(self):
    """
    Get count of all descendant nodes.
    
    Returns:
        int: Total number of descendants
    """

Usage examples:

# Get all descendants
descendants = node.get_descendants()
print(f"Total descendants: {descendants.count()}")

# Process entire subtree
for descendant in descendants:
    print(f"Descendant: {descendant.name} (depth: {descendant.get_depth()})")

# Quick count check
if node.get_descendant_count() > 100:
    print("Large subtree - consider pagination")

Depth and Level Information

Methods for determining node position in tree hierarchy.

def get_depth(self):
    """
    Get the depth/level of this node in the tree.
    
    Root nodes have depth 0, their children have depth 1, etc.
    
    Returns:
        int: Depth level (0 for root nodes)
    """

Usage examples:

# Get node depth
depth = node.get_depth()
print(f"Node depth: {depth}")

# Create indented display
indent = "  " * node.get_depth()
print(f"{indent}{node.name}")

# Filter by depth level
shallow_nodes = Category.objects.filter(depth__lte=2)

Node Relationship Tests

Methods for testing relationships between nodes.

def is_root(self):
    """
    Check if this node is a root node.
    
    Returns:
        bool: True if node has no parent
    """

def is_leaf(self):
    """
    Check if this node is a leaf node (has no children).
    
    Returns:
        bool: True if node has no children
    """

def is_sibling_of(self, node):
    """
    Check if this node is a sibling of another node.
    
    Parameters:
        node (Node): Node to test relationship with
        
    Returns:
        bool: True if nodes are siblings (same parent)
    """

def is_child_of(self, node):
    """
    Check if this node is a child of another node.
    
    Parameters:
        node (Node): Potential parent node
        
    Returns:
        bool: True if this node is direct child of given node
    """

def is_descendant_of(self, node):
    """
    Check if this node is a descendant of another node.
    
    Parameters:
        node (Node): Potential ancestor node
        
    Returns:
        bool: True if this node is descendant of given node
    """

Usage examples:

# Test node types
if node.is_root():
    print("This is a root node")

if node.is_leaf():
    print("This is a leaf node")

# Test relationships
if child.is_child_of(parent):
    print("Direct parent-child relationship")

if grandchild.is_descendant_of(grandparent):
    print("Descendant relationship exists")

if node1.is_sibling_of(node2):
    print("Nodes are siblings")

Advanced Navigation

Tree Traversal Patterns

Get complete tree structures with annotation and formatting.

@classmethod
def get_tree(cls, parent=None):
    """
    Get tree as depth-first ordered list of nodes.
    
    Parameters:
        parent (Node, optional): Root node to start from
        
    Returns:
        list: List of nodes in depth-first traversal order
    """

@classmethod
def get_annotated_list(cls, parent=None, max_depth=None):
    """
    Get annotated tree list with depth and formatting info.
    
    Parameters:
        parent (Node, optional): Root node to start from  
        max_depth (int, optional): Maximum depth to include
        
    Returns:
        list: List of dicts with node and annotation data
    """

@classmethod
def get_annotated_list_qs(cls, qs):
    """
    Get annotated list from existing queryset.
    
    Parameters:
        qs (QuerySet): Pre-filtered queryset of nodes
        
    Returns:
        list: Annotated list with depth and formatting info
    """

Usage examples:

# Get complete tree structure
tree_nodes = Category.get_tree()
for node in tree_nodes:
    indent = "  " * node.get_depth()
    print(f"{indent}{node.name}")

# Get annotated tree with metadata
annotated = Category.get_annotated_list(max_depth=3)
for item in annotated:
    node = item['node']
    print(f"{'  ' * item['level']}{node.name} ({item['open']}/{item['close']})")

# Work with filtered queryset
active_categories = Category.objects.filter(active=True)
annotated_active = Category.get_annotated_list_qs(active_categories)

Descendant Group Counting

Get sibling nodes with descendant count information.

@classmethod  
def get_descendants_group_count(cls, parent=None):
    """
    Get siblings with descendant count information.
    
    Parameters:
        parent (Node, optional): Parent node (None for roots)
        
    Returns:
        QuerySet: Sibling nodes annotated with descendant counts
    """

Usage example:

# Get root nodes with descendant counts
roots_with_counts = Category.get_descendants_group_count()
for root in roots_with_counts:
    print(f"{root.name}: {root.descendants_count} total items")

# Get children of specific node with counts
children_with_counts = Category.get_descendants_group_count(parent=electronics)
for child in children_with_counts:
    print(f"{child.name}: {child.descendants_count} subitems")

Performance Considerations

Implementation Differences

AL_Node (Adjacency List):

get_ancestors(): Requires recursive queries (O(depth))
get_descendants(): Requires recursive queries (O(subtree_size))
get_children(): Very efficient (O(1) query)
get_parent(): Very efficient (cached or O(1))

MP_Node (Materialized Path):

get_ancestors(): Efficient path prefix query (O(1))
get_descendants(): Efficient path prefix query (O(1))
get_children(): Efficient path-based query (O(1))
get_parent(): Efficient path manipulation (O(1))

NS_Node (Nested Sets):

get_ancestors(): Very efficient range query (O(1))
get_descendants(): Very efficient range query (O(1))
get_children(): Efficient with proper indexing (O(1))
get_parent(): Efficient range query (O(1))

Optimization Tips

# Use select_related for parent access
nodes = Category.objects.select_related('parent')
for node in nodes:
    parent = node.get_parent()  # No additional query

# Use prefetch_related for children
parents = Category.objects.prefetch_related('children')
for parent in parents:
    children = parent.get_children()  # Uses prefetched data

# Cache depth calculations for display
nodes_with_depth = Category.objects.extra(select={'cached_depth': 'depth'})

# Limit descendant queries for large trees
shallow_descendants = node.get_descendants().filter(depth__lte=node.get_depth() + 2)

Memory Usage

For large trees, consider pagination or limiting depth:

# Paginate large descendant sets
from django.core.paginator import Paginator

descendants = node.get_descendants()
paginator = Paginator(descendants, 50)
page = paginator.get_page(1)

# Limit depth for navigation
max_nav_depth = 3
nav_nodes = Category.objects.filter(depth__lte=max_nav_depth)

Install with Tessl CLI