0
# Utility Functions
1
2
Helper functions for number base conversion, tree validation, database operations, and other utility functions that support tree operations. These utilities are used internally by the tree implementations but are also available for advanced use cases.
3
4
## Capabilities
5
6
### Number Base Conversion
7
8
Utility functions and classes for converting between different number bases, primarily used by MP_Node for path encoding.
9
10
#### NumConv Class
11
12
```python { .api }
13
class NumConv:
14
"""
15
Number conversion utility for different bases.
16
17
Converts integers to string representations using custom alphabets
18
and radixes, used for encoding tree paths in MP_Node.
19
"""
20
21
def __init__(self, radix=10, alphabet=BASE85):
22
"""
23
Initialize number converter.
24
25
Parameters:
26
radix (int): Base for number conversion (default: 10)
27
alphabet (str): Character set for encoding (default: BASE85)
28
"""
29
self.radix = radix
30
self.alphabet = alphabet
31
32
def int2str(self, num):
33
"""
34
Convert integer to string representation.
35
36
Parameters:
37
num (int): Integer to convert
38
39
Returns:
40
str: String representation in configured base
41
"""
42
43
def str2int(self, num):
44
"""
45
Convert string representation back to integer.
46
47
Parameters:
48
num (str): String representation to convert
49
50
Returns:
51
int: Integer value
52
"""
53
```
54
55
#### Module-Level Functions
56
57
```python { .api }
58
def int2str(num, radix=10, alphabet=BASE85):
59
"""
60
Convert integer to string representation.
61
62
Quick conversion function without creating NumConv instance.
63
64
Parameters:
65
num (int): Integer to convert
66
radix (int): Base for conversion (default: 10)
67
alphabet (str): Character set for encoding (default: BASE85)
68
69
Returns:
70
str: String representation in specified base
71
"""
72
73
def str2int(num, radix=10, alphabet=BASE85):
74
"""
75
Convert string representation back to integer.
76
77
Quick conversion function without creating NumConv instance.
78
79
Parameters:
80
num (str): String representation to convert
81
radix (int): Base for conversion (default: 10)
82
alphabet (str): Character set for encoding (default: BASE85)
83
84
Returns:
85
int: Integer value
86
"""
87
```
88
89
#### Alphabet Constants
90
91
```python { .api }
92
# Base16 alphabet (hexadecimal)
93
BASE16 = '0123456789ABCDEF'
94
95
# RFC4648 Base32 alphabet
96
BASE32 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'
97
98
# Base32 hex alphabet
99
BASE32HEX = '0123456789ABCDEFGHIJKLMNOPQRSTUV'
100
101
# Base62 alphabet (alphanumeric)
102
BASE62 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
103
104
# RFC4648 Base64 alphabet
105
BASE64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
106
107
# URL-safe Base64 alphabet
108
BASE64URL = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_'
109
110
# Base85 alphabet (default for MP_Node paths)
111
BASE85 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~'
112
```
113
114
### Tree Validation
115
116
Functions for checking and repairing tree structure integrity.
117
118
```python { .api }
119
@classmethod
120
def find_problems(cls):
121
"""
122
Check tree structure for problems and inconsistencies.
123
124
Identifies various types of tree corruption including:
125
- Orphaned nodes
126
- Invalid parent references
127
- Incorrect depth calculations
128
- Path inconsistencies (MP_Node)
129
- Boundary violations (NS_Node)
130
131
Returns:
132
list: List of problem descriptions found in tree
133
"""
134
135
@classmethod
136
def fix_tree(cls, destructive=False):
137
"""
138
Fix tree structure inconsistencies.
139
140
Attempts to repair common tree problems by recalculating
141
tree structure fields and removing invalid nodes.
142
143
Parameters:
144
destructive (bool): Whether to remove unfixable nodes
145
146
Returns:
147
dict: Summary of fixes applied
148
149
Warning:
150
destructive=True may result in data loss
151
"""
152
```
153
154
### Database Utilities
155
156
Database-specific utility functions for SQL generation and database operations.
157
158
#### Database Vendor Detection
159
160
```python { .api }
161
@classmethod
162
def get_database_vendor(cls, action='read'):
163
"""
164
Get database vendor for SQL generation.
165
166
Determines database backend for generating appropriate SQL.
167
168
Parameters:
169
action (str): Type of operation ('read', 'write', 'delete')
170
171
Returns:
172
str: Database vendor ('postgresql', 'mysql', 'sqlite', 'mssql')
173
"""
174
```
175
176
#### SQL Generation Functions (MP_Node)
177
178
```python { .api }
179
def sql_concat(*args, **kwargs):
180
"""
181
Generate database-specific SQL for string concatenation.
182
183
Parameters:
184
*args: String expressions to concatenate
185
**kwargs: Additional options (vendor, etc.)
186
187
Returns:
188
str: Database-specific concatenation SQL
189
"""
190
191
def sql_length(field, vendor=None):
192
"""
193
Generate database-specific SQL for string length.
194
195
Parameters:
196
field (str): Field name or expression
197
vendor (str, optional): Database vendor override
198
199
Returns:
200
str: Database-specific length function SQL
201
"""
202
203
def sql_substr(field, pos, length=None, **kwargs):
204
"""
205
Generate database-specific SQL for substring extraction.
206
207
Parameters:
208
field (str): Field name or expression
209
pos (int): Starting position (1-based)
210
length (int, optional): Length of substring
211
**kwargs: Additional options (vendor, etc.)
212
213
Returns:
214
str: Database-specific substring SQL
215
"""
216
```
217
218
#### Result Class Utilities
219
220
```python { .api }
221
def get_result_class(cls):
222
"""
223
Determine appropriate result class for tree operations.
224
225
Handles inheritance scenarios where operations may return
226
different model classes than the initiating class.
227
228
Parameters:
229
cls (type): Tree model class
230
231
Returns:
232
type: Appropriate result class for operations
233
"""
234
```
235
236
### NS_Node Utilities
237
238
Specialized utilities for Nested Sets tree operations.
239
240
```python { .api }
241
def merge_deleted_counters(c1, c2):
242
"""
243
Merge delete operation counters for nested sets.
244
245
Combines statistics from multiple delete operations
246
for batch processing and reporting.
247
248
Parameters:
249
c1 (dict): First counter dictionary
250
c2 (dict): Second counter dictionary
251
252
Returns:
253
dict: Merged counter statistics
254
"""
255
```
256
257
## Usage Examples
258
259
### Number Base Conversion
260
261
```python
262
from treebeard.numconv import NumConv, int2str, str2int, BASE62
263
264
# Quick conversions
265
hex_value = int2str(255, radix=16, alphabet='0123456789ABCDEF')
266
print(hex_value) # 'FF'
267
268
decimal_value = str2int('FF', radix=16, alphabet='0123456789ABCDEF')
269
print(decimal_value) # 255
270
271
# Using NumConv class for repeated conversions
272
converter = NumConv(radix=62, alphabet=BASE62)
273
274
# Convert sequence of numbers
275
numbers = [1, 100, 1000, 10000]
276
encoded = [converter.int2str(n) for n in numbers]
277
print(encoded) # ['1', '1C', 'G8', '2bI']
278
279
# Convert back
280
decoded = [converter.str2int(s) for s in encoded]
281
print(decoded) # [1, 100, 1000, 10000]
282
283
# Custom alphabet for specific encoding needs
284
custom_alphabet = '0123456789ABCDEFGHIJ' # Base 20
285
converter = NumConv(radix=20, alphabet=custom_alphabet)
286
result = converter.int2str(399) # 19 * 20 + 19 = 399
287
print(result) # 'JJ'
288
```
289
290
### Tree Validation and Repair
291
292
```python
293
from myapp.models import Category
294
295
# Check for tree problems
296
problems = Category.find_problems()
297
if problems:
298
print("Tree problems found:")
299
for problem in problems:
300
print(f" - {problem}")
301
else:
302
print("Tree structure is valid")
303
304
# Fix tree problems
305
print("Attempting to fix tree...")
306
fixes = Category.fix_tree(destructive=False)
307
print(f"Applied {len(fixes)} fixes")
308
309
# For serious corruption, use destructive repair
310
if problems:
311
print("Applying destructive fixes...")
312
fixes = Category.fix_tree(destructive=True)
313
print("Tree repaired, but some data may have been lost")
314
315
# Verify fix was successful
316
remaining_problems = Category.find_problems()
317
if not remaining_problems:
318
print("Tree structure successfully repaired")
319
```
320
321
### Custom MP_Node Path Configuration
322
323
```python
324
from treebeard.numconv import BASE62
325
from treebeard.mp_tree import MP_Node
326
327
class CompactCategory(MP_Node):
328
"""Category with compact path encoding."""
329
name = models.CharField(max_length=100)
330
331
# Use Base62 for more compact paths
332
alphabet = BASE62
333
steplen = 3 # Shorter steps for more levels
334
335
# Custom path configuration
336
@classmethod
337
def get_path_info(cls, path=None):
338
"""Get path information for debugging."""
339
if not path:
340
return None
341
342
steps = []
343
for i in range(0, len(path), cls.steplen):
344
step = path[i:i + cls.steplen]
345
value = cls.str2int(step, radix=len(cls.alphabet), alphabet=cls.alphabet)
346
steps.append({'step': step, 'value': value})
347
348
return {
349
'path': path,
350
'depth': len(steps),
351
'steps': steps
352
}
353
354
# Usage
355
root = CompactCategory.add_root(name='Root')
356
child = root.add_child(name='Child')
357
358
print("Path info:", CompactCategory.get_path_info(child.path))
359
# Output: {'path': '001002', 'depth': 2, 'steps': [{'step': '001', 'value': 1}, {'step': '002', 'value': 2}]}
360
```
361
362
### Database-Specific Operations
363
364
```python
365
# Check database vendor
366
vendor = Category.get_database_vendor()
367
print(f"Using database: {vendor}")
368
369
# Generate database-specific SQL (for advanced use cases)
370
if vendor == 'postgresql':
371
# PostgreSQL-specific optimizations
372
sql = "SELECT * FROM category WHERE path ~ '^001'"
373
elif vendor == 'mysql':
374
# MySQL-specific optimizations
375
sql = "SELECT * FROM category WHERE path LIKE '001%'"
376
else:
377
# Generic SQL
378
sql = "SELECT * FROM category WHERE path LIKE '001%'"
379
380
# Use in raw queries
381
from django.db import connection
382
383
with connection.cursor() as cursor:
384
cursor.execute(sql)
385
results = cursor.fetchall()
386
```
387
388
### Custom Tree Analysis
389
390
```python
391
def analyze_tree_structure(model_class):
392
"""Analyze tree structure and provide statistics."""
393
stats = {
394
'total_nodes': model_class.objects.count(),
395
'root_nodes': model_class.get_root_nodes().count(),
396
'max_depth': 0,
397
'avg_children': 0,
398
'leaf_nodes': 0
399
}
400
401
# Calculate depth statistics
402
depths = model_class.objects.values_list('depth', flat=True)
403
if depths:
404
stats['max_depth'] = max(depths)
405
stats['depth_distribution'] = {}
406
for depth in depths:
407
stats['depth_distribution'][depth] = stats['depth_distribution'].get(depth, 0) + 1
408
409
# Calculate children statistics
410
children_counts = []
411
leaf_count = 0
412
413
for node in model_class.objects.all():
414
child_count = node.get_children_count()
415
children_counts.append(child_count)
416
if child_count == 0:
417
leaf_count += 1
418
419
if children_counts:
420
stats['avg_children'] = sum(children_counts) / len(children_counts)
421
stats['max_children'] = max(children_counts)
422
423
stats['leaf_nodes'] = leaf_count
424
stats['internal_nodes'] = stats['total_nodes'] - leaf_count
425
426
return stats
427
428
# Usage
429
stats = analyze_tree_structure(Category)
430
print("Tree Analysis:")
431
print(f" Total nodes: {stats['total_nodes']}")
432
print(f" Root nodes: {stats['root_nodes']}")
433
print(f" Max depth: {stats['max_depth']}")
434
print(f" Leaf nodes: {stats['leaf_nodes']}")
435
print(f" Average children per node: {stats['avg_children']:.2f}")
436
```
437
438
### Performance Monitoring
439
440
```python
441
import time
442
from django.db import connection
443
444
def benchmark_tree_operations(model_class, num_operations=100):
445
"""Benchmark common tree operations."""
446
447
# Reset query count
448
initial_queries = len(connection.queries)
449
start_time = time.time()
450
451
# Create test tree
452
root = model_class.add_root(name='Benchmark Root')
453
454
# Benchmark child creation
455
child_start = time.time()
456
for i in range(num_operations):
457
root.add_child(name=f'Child {i}')
458
child_time = time.time() - child_start
459
460
# Benchmark tree traversal
461
traverse_start = time.time()
462
descendants = root.get_descendants()
463
list(descendants) # Force evaluation
464
traverse_time = time.time() - traverse_start
465
466
# Benchmark move operations
467
children = list(root.get_children()[:10]) # Get first 10 children
468
move_start = time.time()
469
for i, child in enumerate(children[1:], 1):
470
child.move(children[0], 'right')
471
move_time = time.time() - move_start
472
473
total_time = time.time() - start_time
474
total_queries = len(connection.queries) - initial_queries
475
476
# Cleanup
477
root.delete()
478
479
return {
480
'total_time': total_time,
481
'child_creation_time': child_time,
482
'traversal_time': traverse_time,
483
'move_time': move_time,
484
'total_queries': total_queries,
485
'avg_time_per_operation': total_time / num_operations,
486
'queries_per_operation': total_queries / num_operations
487
}
488
489
# Compare implementations
490
al_stats = benchmark_tree_operations(ALCategory, 100)
491
mp_stats = benchmark_tree_operations(MPCategory, 100)
492
ns_stats = benchmark_tree_operations(NSCategory, 100)
493
494
print("Performance Comparison:")
495
print(f"AL_Node: {al_stats['total_time']:.3f}s, {al_stats['total_queries']} queries")
496
print(f"MP_Node: {mp_stats['total_time']:.3f}s, {mp_stats['total_queries']} queries")
497
print(f"NS_Node: {ns_stats['total_time']:.3f}s, {ns_stats['total_queries']} queries")
498
```
499
500
## Advanced Utility Patterns
501
502
### Custom Validation Rules
503
504
```python
505
def validate_tree_business_rules(model_class):
506
"""Validate business-specific tree rules."""
507
errors = []
508
509
# Rule: No more than 5 levels deep
510
deep_nodes = model_class.objects.filter(depth__gt=4)
511
if deep_nodes.exists():
512
errors.append(f"Found {deep_nodes.count()} nodes deeper than 5 levels")
513
514
# Rule: Root nodes must have specific naming pattern
515
invalid_roots = model_class.get_root_nodes().exclude(name__regex=r'^[A-Z]')
516
if invalid_roots.exists():
517
errors.append("Root nodes must start with capital letter")
518
519
# Rule: No orphaned nodes (for AL_Node)
520
if hasattr(model_class, 'parent'):
521
orphaned = model_class.objects.filter(
522
parent__isnull=False,
523
parent__in=model_class.objects.none()
524
)
525
if orphaned.exists():
526
errors.append(f"Found {orphaned.count()} orphaned nodes")
527
528
return errors
529
530
# Usage in management command
531
class Command(BaseCommand):
532
def handle(self, *args, **options):
533
errors = validate_tree_business_rules(Category)
534
if errors:
535
for error in errors:
536
self.stdout.write(self.style.ERROR(error))
537
else:
538
self.stdout.write(self.style.SUCCESS("All business rules validated"))
539
```
540
541
### Tree Import/Export Utilities
542
543
```python
544
import json
545
from django.core.serializers.json import DjangoJSONEncoder
546
547
def export_tree_to_json(model_class, root_node=None, include_fields=None):
548
"""Export tree structure to JSON format."""
549
550
def serialize_node(node):
551
data = {'id': node.pk}
552
553
# Include specified fields
554
if include_fields:
555
for field in include_fields:
556
data[field] = getattr(node, field)
557
else:
558
# Include all non-tree fields
559
for field in node._meta.fields:
560
if field.name not in ['id', 'path', 'depth', 'numchild', 'lft', 'rgt', 'tree_id']:
561
data[field.name] = field.value_from_object(node)
562
563
# Add children recursively
564
children = node.get_children()
565
if children:
566
data['children'] = [serialize_node(child) for child in children]
567
568
return data
569
570
if root_node:
571
return serialize_node(root_node)
572
else:
573
roots = model_class.get_root_nodes()
574
return [serialize_node(root) for root in roots]
575
576
def import_tree_from_json(model_class, json_data, parent=None):
577
"""Import tree structure from JSON format."""
578
created_nodes = []
579
580
if isinstance(json_data, str):
581
json_data = json.loads(json_data)
582
583
if not isinstance(json_data, list):
584
json_data = [json_data]
585
586
for node_data in json_data:
587
children_data = node_data.pop('children', [])
588
node_data.pop('id', None) # Remove original ID
589
590
# Create node
591
if parent:
592
node = parent.add_child(**node_data)
593
else:
594
node = model_class.add_root(**node_data)
595
596
created_nodes.append(node)
597
598
# Create children recursively
599
if children_data:
600
child_nodes = import_tree_from_json(model_class, children_data, parent=node)
601
created_nodes.extend(child_nodes)
602
603
return created_nodes
604
605
# Usage
606
tree_data = export_tree_to_json(Category, include_fields=['name', 'description', 'active'])
607
with open('tree_backup.json', 'w') as f:
608
json.dump(tree_data, f, cls=DjangoJSONEncoder, indent=2)
609
610
# Later, restore from backup
611
with open('tree_backup.json', 'r') as f:
612
backup_data = json.load(f)
613
614
restored_nodes = import_tree_from_json(Category, backup_data)
615
print(f"Restored {len(restored_nodes)} nodes")
616
```
617
618
These utilities provide the foundation for advanced tree operations, custom validation, performance monitoring, and data migration scenarios.