Commit | Line | Data |
87427fdb |
1 | package DBIx::Class::Tree::AdjacencyList; |
bb17efa0 |
2 | # vim: ts=8:sw=4:sts=4:et |
3 | |
87427fdb |
4 | use strict; |
5 | use warnings; |
bb17efa0 |
6 | |
87427fdb |
7 | use base qw( DBIx::Class ); |
8 | use Carp qw( croak ); |
9 | |
10 | =head1 NAME |
11 | |
af9120b0 |
12 | DBIx::Class::Tree::AdjacencyList - Manage a tree of data using the common adjacency list model. |
87427fdb |
13 | |
14 | =head1 SYNOPSIS |
15 | |
16 | Create a table for your tree data. |
17 | |
18 | CREATE TABLE employees ( |
19 | employee_id INTEGER PRIMARY KEY AUTOINCREMENT, |
82958127 |
20 | parent_id INTEGER NOT NULL DEFAULT 0, |
87427fdb |
21 | name TEXT NOT NULL |
22 | ); |
23 | |
3c94ae56 |
24 | In your Schema or DB class add Tree::AdjacencyList to the top |
87427fdb |
25 | of the component list. |
26 | |
27 | __PACKAGE__->load_components(qw( Tree::AdjacencyList ... )); |
87427fdb |
28 | |
57f04bd5 |
29 | Specify the column that contains the parent ID of each row. |
87427fdb |
30 | |
31 | package My::Employee; |
32 | __PACKAGE__->parent_column('parent_id'); |
33 | |
98277fa5 |
34 | Optionally, automatically maintane a consistent tree structure. |
35 | |
36 | __PACKAGE__->repair_tree( 1 ); |
37 | |
87427fdb |
38 | Thats it, now you can modify and analyze the tree. |
39 | |
82958127 |
40 | #!/usr/bin/perl |
87427fdb |
41 | use My::Employee; |
3c94ae56 |
42 | |
87427fdb |
43 | my $employee = My::Employee->create({ name=>'Matt S. Trout' }); |
3c94ae56 |
44 | |
87427fdb |
45 | my $rs = $employee->children(); |
46 | my @siblings = $employee->children(); |
3c94ae56 |
47 | |
87427fdb |
48 | my $parent = $employee->parent(); |
49 | $employee->parent( 7 ); |
50 | |
51 | =head1 DESCRIPTION |
52 | |
3c94ae56 |
53 | This module provides methods for working with adjacency lists. The |
54 | adjacency list model is a very common way of representing a tree structure. |
55 | In this model each row in a table has a prent ID column that references the |
56 | primary key of another row in the same table. Because of this the primary |
57 | key must only be one column and is usually some sort of integer. The row |
58 | with a parent ID of 0 is the root node and is usually the parent of all |
59 | other rows. Although, there is no limitation in this module that would |
9717d3ca |
60 | stop you from having multiple root nodes. |
87427fdb |
61 | |
62 | =head1 METHODS |
63 | |
64 | =head2 parent_column |
65 | |
66 | __PACKAGE__->parent_column('parent_id'); |
67 | |
3c94ae56 |
68 | Declares the name of the column that contains the self-referential |
e7353352 |
69 | ID which defines the parent row. This will create a has_many (children) |
bfeda3d7 |
70 | and belongs_to (parent) relationship. |
87427fdb |
71 | |
bfeda3d7 |
72 | This method also sets up an additional has_many relationship called |
3c94ae56 |
73 | parents which is useful when you want to treat an adjacency list |
bb17efa0 |
74 | as a DAG. |
75 | |
87427fdb |
76 | =cut |
77 | |
82958127 |
78 | __PACKAGE__->mk_classdata( '_parent_column' => 'parent_id' ); |
79 | |
80 | sub parent_column { |
81 | my $class = shift; |
82 | if (@_) { |
83 | my $parent_col = shift; |
84 | my $primary_col = ($class->primary_columns())[0]; |
85 | $class->belongs_to( '_parent' => $class => { "foreign.$primary_col" => "self.$parent_col" } ); |
86 | $class->has_many( 'children' => $class => { "foreign.$parent_col" => "self.$primary_col" } ); |
1dfd20a4 |
87 | $class->has_many( 'parents' => $class => { "foreign.$primary_col" => "self.$parent_col" }, { cascade_delete => 0, cascade_copy => 0 } ); |
82958127 |
88 | $class->_parent_column( $parent_col ); |
89 | return 1; |
90 | } |
91 | return $class->_parent_column(); |
92 | } |
87427fdb |
93 | |
98277fa5 |
94 | =head2 repair_tree |
95 | |
96 | __PACKAGE__->repair_tree( 1 ); |
97 | |
98 | When set a true value this flag causes all changes to a node's parent to |
99 | trigger an integrity check on the tree. If, when changing a node's parent |
100 | to one of it's descendents then all its children will first be moved to have |
101 | the same current parent, and then the node's parent is changed. |
102 | |
103 | So, for example, if the tree is like this: |
104 | |
105 | A |
106 | B |
107 | C |
108 | D |
109 | E |
110 | F |
111 | |
112 | And you execute: |
113 | |
114 | $b->parent( $d ); |
115 | |
bfeda3d7 |
116 | Since D is a descendant of B then all of D's siblings get their parent |
98277fa5 |
117 | changed to A. Then B's parent is set to D. |
c0d76c37 |
118 | |
98277fa5 |
119 | A |
120 | C |
121 | D |
122 | B |
123 | E |
124 | F |
125 | |
126 | =cut |
127 | |
128 | __PACKAGE__->mk_classdata( 'repair_tree' => 0 ); |
c0d76c37 |
129 | |
87427fdb |
130 | =head2 parent |
131 | |
132 | my $parent = $employee->parent(); |
133 | $employee->parent( $parent_obj ); |
134 | $employee->parent( $parent_id ); |
135 | |
3c94ae56 |
136 | Retrieves the object's parent object, or changes the object's |
137 | parent to the specified parent or parent ID. If you would like |
9717d3ca |
138 | to make the object the root node, just set the parent to 0. |
139 | |
3c94ae56 |
140 | If you are setting the parent then 0 will be returned if the |
141 | specified parent is already the object's parent and 1 on |
9717d3ca |
142 | success. |
87427fdb |
143 | |
87427fdb |
144 | =cut |
145 | |
146 | sub parent { |
82958127 |
147 | my $self = shift; |
148 | if (@_) { |
149 | my $new_parent = shift; |
150 | my $parent_col = $self->_parent_column(); |
87427fdb |
151 | if (ref($new_parent)) { |
82958127 |
152 | $new_parent = $new_parent->id() || croak('Parent object does not have an ID');; |
87427fdb |
153 | } |
82958127 |
154 | return 0 if ($new_parent == ($self->get_column($parent_col)||0)); |
98277fa5 |
155 | |
156 | if ($self->repair_tree()) { |
157 | my $found = $self->has_descendant( $new_parent ); |
158 | if ($found) { |
159 | my $children = $self->children(); |
160 | |
161 | while (my $child = $children->next()) { |
162 | $child->parent( $self->$parent_col() ); |
163 | } |
164 | } |
165 | } |
166 | |
82958127 |
167 | $self->set_column( $parent_col => $new_parent ); |
87427fdb |
168 | $self->update(); |
169 | return 1; |
170 | } |
82958127 |
171 | return $self->_parent(); |
87427fdb |
172 | } |
3c94ae56 |
173 | =head2 ancestors |
174 | |
175 | @list = $employee->ancestors(); |
176 | |
177 | Returns a list of ancestors starting with a record's |
178 | parent and moving toward the tree root. |
179 | |
180 | =cut |
181 | |
182 | sub ancestors { |
183 | my $self = shift; |
184 | my @ancestors = (); |
185 | my $rec = $self; |
186 | while ($rec = $rec->parent) { |
187 | push(@ancestors, $rec); |
188 | } |
189 | return @ancestors; |
190 | } |
191 | |
87427fdb |
192 | |
98277fa5 |
193 | =head2 has_descendant |
c0d76c37 |
194 | |
98277fa5 |
195 | if ($employee->has_descendant( $id )) { ... } |
c0d76c37 |
196 | |
98277fa5 |
197 | Returns true if the object has a descendant with the |
198 | specified ID. |
c0d76c37 |
199 | |
200 | =cut |
201 | |
98277fa5 |
202 | sub has_descendant { |
203 | my ($self, $find_id) = @_; |
204 | |
205 | my $children = $self->children(); |
206 | while (my $child = $children->next()) { |
207 | if ($child->id() eq $find_id) { |
208 | return 1; |
c0d76c37 |
209 | } |
98277fa5 |
210 | return 1 if ($child->has_descendant( $find_id )); |
c0d76c37 |
211 | } |
c0d76c37 |
212 | |
98277fa5 |
213 | return 0; |
214 | } |
c0d76c37 |
215 | |
bb17efa0 |
216 | =head2 parents |
217 | |
218 | my $parents = $node->parents(); |
219 | my @parents = $node->parents(); |
220 | |
3c94ae56 |
221 | This has_many relationship is not that useful as it will |
222 | never return more than one parent due to the one-to-many |
223 | structure of adjacency lists. The reason this relationship |
224 | is defined is so that this tree type may be treated as if |
bb17efa0 |
225 | it was a DAG. |
226 | |
87427fdb |
227 | =head2 children |
228 | |
229 | my $children_rs = $employee->children(); |
230 | my @children = $employee->children(); |
231 | |
3c94ae56 |
232 | Returns a list or record set, depending on context, of all |
233 | the objects one level below the current one. This method |
234 | is created when parent_column() is called, which sets up a |
82958127 |
235 | has_many relationship called children. |
87427fdb |
236 | |
98277fa5 |
237 | =head2 attach_child |
87427fdb |
238 | |
98277fa5 |
239 | $parent->attach_child( $child ); |
240 | $parent->attach_child( $child, $child, ... ); |
87427fdb |
241 | |
3c94ae56 |
242 | Sets the child, or children, to the new parent. Returns 1 |
243 | on success and returns 0 if the parent object already has |
9717d3ca |
244 | the child. |
87427fdb |
245 | |
246 | =cut |
247 | |
98277fa5 |
248 | sub attach_child { |
9717d3ca |
249 | my $self = shift; |
250 | my $return = 1; |
251 | foreach my $child (@_) { |
252 | $child->parent( $self ); |
253 | } |
254 | return $return; |
87427fdb |
255 | } |
256 | |
82958127 |
257 | =head2 siblings |
258 | |
259 | my $rs = $node->siblings(); |
260 | my @siblings = $node->siblings(); |
261 | |
3c94ae56 |
262 | Returns either a result set or an array of all other objects |
82958127 |
263 | with the same parent as the calling object. |
264 | |
265 | =cut |
266 | |
267 | sub siblings { |
268 | my( $self ) = @_; |
269 | my $parent_col = $self->_parent_column; |
270 | my $primary_col = ($self->primary_columns())[0]; |
271 | my $rs = $self->result_source->resultset->search( |
272 | { |
273 | $parent_col => $self->get_column($parent_col), |
274 | $primary_col => { '!=' => $self->get_column($primary_col) }, |
275 | }, |
276 | ); |
277 | return $rs->all() if (wantarray()); |
278 | return $rs; |
279 | } |
280 | |
98277fa5 |
281 | =head2 attach_sibling |
87427fdb |
282 | |
98277fa5 |
283 | $obj->attach_sibling( $sibling ); |
284 | $obj->attach_sibling( $sibling, $sibling, ... ); |
87427fdb |
285 | |
3c94ae56 |
286 | Sets the passed in object(s) to have the same parent |
287 | as the calling object. Returns 1 on success and |
9717d3ca |
288 | 0 if the sibling already has the same parent. |
87427fdb |
289 | |
290 | =cut |
291 | |
98277fa5 |
292 | sub attach_sibling { |
9717d3ca |
293 | my $self = shift; |
294 | my $return = 1; |
295 | foreach my $node (@_) { |
296 | $return = 0 if (!$node->parent( $self->parent() )); |
297 | } |
298 | return $return; |
87427fdb |
299 | } |
300 | |
74d97bdc |
301 | =head2 is_leaf |
302 | |
303 | if ($obj->is_leaf()) { ... } |
304 | |
305 | Returns 1 if the object has no children, and 0 otherwise. |
306 | |
307 | =cut |
308 | |
309 | sub is_leaf { |
310 | my( $self ) = @_; |
98277fa5 |
311 | |
ab184e4a |
312 | my $has_child = $self->children_rs->count(); |
c0d76c37 |
313 | |
98277fa5 |
314 | return $has_child ? 0 : 1; |
315 | } |
c0d76c37 |
316 | |
74d97bdc |
317 | =head2 is_root |
318 | |
319 | if ($obj->is_root()) { ... } |
320 | |
321 | Returns 1 if the object has no parent, and 0 otherwise. |
322 | |
323 | =cut |
324 | |
325 | sub is_root { |
326 | my( $self ) = @_; |
98277fa5 |
327 | return ( $self->get_column( $self->_parent_column ) ? 0 : 1 ); |
74d97bdc |
328 | } |
329 | |
330 | =head2 is_branch |
331 | |
332 | if ($obj->is_branch()) { ... } |
333 | |
3c94ae56 |
334 | Returns 1 if the object has a parent and has children. |
74d97bdc |
335 | Returns 0 otherwise. |
336 | |
337 | =cut |
338 | |
339 | sub is_branch { |
340 | my( $self ) = @_; |
98277fa5 |
341 | return ( ($self->is_leaf() or $self->is_root()) ? 0 : 1 ); |
c0d76c37 |
342 | } |
343 | |
74d97bdc |
344 | =head2 set_primary_key |
345 | |
3c94ae56 |
346 | This method is an override of DBIx::Class' method for setting the |
347 | class' primary key column(s). This method passes control right on |
348 | to the normal method after first validating that only one column is |
349 | being selected as a primary key. If more than one column is then |
74d97bdc |
350 | an error will be thrown. |
351 | |
352 | =cut |
353 | |
c0d76c37 |
354 | sub set_primary_key { |
74d97bdc |
355 | my $self = shift; |
356 | if (@_>1) { |
357 | croak('You may only specify a single column as the primary key for adjacency tree classes'); |
358 | } |
359 | return $self->next::method( @_ ); |
360 | } |
361 | |
87427fdb |
362 | 1; |
363 | __END__ |
364 | |
e7353352 |
365 | =head1 CAVEATS |
366 | |
367 | =head2 Generated schemas |
368 | |
369 | If you are using L<DBIx::Class::Schema/deploy> methods either directly |
370 | or via L<DBIx::Class::DeploymentHandler> or L<DBIx::Migration>, you |
f77790db |
371 | will need the following L<SQL::Translator> hook to remove the constraint |
372 | from C<parent_column>, otherwise you will not be able to user 0 (zero) as |
373 | a value. |
e7353352 |
374 | |
375 | sub sqlt_deploy_hook { |
376 | my ($self, $sqlt_table) = @_; |
377 | |
f77790db |
378 | foreach my $constraint ($sqlt_table->get_constraints) { |
379 | if ($constraint->field_names->[0] eq $self->parent_column) { |
380 | $sqlt_table->drop_constraint($constraint->name); |
e7353352 |
381 | last; |
382 | } |
383 | } |
384 | } |
385 | |
386 | ALso see L<DBIx::Class::Manual::Cookbook/Adding Indexes And Functions To |
387 | Your SQL> for other examples. |
388 | |
4b44af23 |
389 | =head1 INHERITED METHODS |
390 | |
391 | =head2 DBIx::Class |
392 | |
393 | =over 4 |
394 | |
395 | =item * |
396 | |
397 | L<mk_classdata|DBIx::Class/mk_classdata> |
398 | |
399 | =item * |
400 | |
401 | L<component_base_class|DBIx::Class/component_base_class> |
402 | |
403 | =back |
404 | |
405 | =head2 DBIx::Class::Componentised |
406 | |
407 | =over 4 |
408 | |
409 | =item * |
410 | |
411 | L<inject_base|DBIx::Class::Componentised/inject_base> |
412 | |
413 | =item * |
414 | |
415 | L<load_components|DBIx::Class::Componentised/load_components> |
416 | |
417 | =item * |
418 | |
419 | L<load_own_components|DBIx::Class::Componentised/load_own_components> |
420 | |
421 | =back |
422 | |
423 | =head2 Class::Data::Accessor |
424 | |
425 | =over 4 |
426 | |
427 | =item * |
428 | |
429 | L<mk_classaccessor|Class::Data::Accessor/mk_classaccessor> |
430 | |
431 | =back |
432 | |
87427fdb |
433 | =head1 AUTHOR |
434 | |
435 | Aran Clary Deltac <bluefeet@cpan.org> |
436 | |
437 | =head1 LICENSE |
438 | |
439 | You may distribute this code under the same terms as Perl itself. |
440 | |