1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
"""Celko's "Nested Sets" Tree Structure.
https://www.intelligententerprise.com/001020/celko.jhtml
"""
from sqlalchemy import case
from sqlalchemy import Column
from sqlalchemy import create_engine
from sqlalchemy import event
from sqlalchemy import func
from sqlalchemy import Integer
from sqlalchemy import select
from sqlalchemy import String
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import aliased
from sqlalchemy.orm import Session
Base = declarative_base()
class Employee(Base):
__tablename__ = "personnel"
__mapper_args__ = {
"batch": False # allows extension to fire for each
# instance before going to the next.
}
parent = None
emp = Column(String, primary_key=True)
left = Column("lft", Integer, nullable=False)
right = Column("rgt", Integer, nullable=False)
def __repr__(self):
return "Employee(%s, %d, %d)" % (self.emp, self.left, self.right)
@event.listens_for(Employee, "before_insert")
def before_insert(mapper, connection, instance):
if not instance.parent:
instance.left = 1
instance.right = 2
else:
personnel = mapper.mapped_table
right_most_sibling = connection.scalar(
select(personnel.c.rgt).where(
personnel.c.emp == instance.parent.emp
)
)
connection.execute(
personnel.update()
.where(personnel.c.rgt >= right_most_sibling)
.values(
lft=case(
(
personnel.c.lft > right_most_sibling,
personnel.c.lft + 2,
),
else_=personnel.c.lft,
),
rgt=case(
(
personnel.c.rgt >= right_most_sibling,
personnel.c.rgt + 2,
),
else_=personnel.c.rgt,
),
)
)
instance.left = right_most_sibling
instance.right = right_most_sibling + 1
# before_update() would be needed to support moving of nodes
# after_delete() would be needed to support removal of nodes.
engine = create_engine("sqlite://", echo=True)
Base.metadata.create_all(engine)
session = Session(bind=engine)
albert = Employee(emp="Albert")
bert = Employee(emp="Bert")
chuck = Employee(emp="Chuck")
donna = Employee(emp="Donna")
eddie = Employee(emp="Eddie")
fred = Employee(emp="Fred")
bert.parent = albert
chuck.parent = albert
donna.parent = chuck
eddie.parent = chuck
fred.parent = chuck
# the order of "add" is important here. elements must be added in
# the order in which they should be INSERTed.
session.add_all([albert, bert, chuck, donna, eddie, fred])
session.commit()
print(session.query(Employee).all())
# 1. Find an employee and all their supervisors, no matter how deep the tree.
ealias = aliased(Employee)
print(
session.query(Employee)
.filter(ealias.left.between(Employee.left, Employee.right))
.filter(ealias.emp == "Eddie")
.all()
)
# 2. Find the employee and all their subordinates.
# (This query has a nice symmetry with the first query.)
print(
session.query(Employee)
.filter(Employee.left.between(ealias.left, ealias.right))
.filter(ealias.emp == "Chuck")
.all()
)
# 3. Find the level of each node, so you can print the tree
# as an indented listing.
for indentation, employee in (
session.query(func.count(Employee.emp).label("indentation") - 1, ealias)
.filter(ealias.left.between(Employee.left, Employee.right))
.group_by(ealias.emp)
.order_by(ealias.left)
):
print(" " * indentation + str(employee))
|
