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 | |
12 | DBIx::Class::Tree::AdjacencyList - Manage a tree of data using the common adjacency list model. (EXPERIMENTAL) |
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 | |
24 | In your Schema or DB class add Tree::AdjacencyList to the top |
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 | |
34 | Thats it, now you can modify and analyze the tree. |
35 | |
82958127 |
36 | #!/usr/bin/perl |
87427fdb |
37 | use My::Employee; |
38 | |
39 | my $employee = My::Employee->create({ name=>'Matt S. Trout' }); |
40 | |
41 | my $rs = $employee->children(); |
42 | my @siblings = $employee->children(); |
43 | |
44 | my $parent = $employee->parent(); |
45 | $employee->parent( 7 ); |
46 | |
47 | =head1 DESCRIPTION |
48 | |
49 | This module provides methods for working with adjacency lists. The |
50 | adjacency list model is a very common way of representing a tree structure. |
51 | In this model each row in a table has a prent ID column that references the |
52 | primary key of another row in the same table. Because of this the primary |
53 | key must only be one column and is usually some sort of integer. The row |
9717d3ca |
54 | with a parent ID of 0 is the root node and is usually the parent of all |
55 | other rows. Although, there is no limitation in this module that would |
56 | stop you from having multiple root nodes. |
87427fdb |
57 | |
c0d76c37 |
58 | |
59 | |
87427fdb |
60 | =head1 METHODS |
61 | |
c0d76c37 |
62 | |
63 | |
87427fdb |
64 | =head2 parent_column |
65 | |
66 | __PACKAGE__->parent_column('parent_id'); |
67 | |
68 | Declares the name of the column that contains the self-referential |
82958127 |
69 | ID which defines the parent row. Defaults to "parent_id". This |
70 | will create a has_many (children) and belongs_to (parent) |
71 | relationship. |
87427fdb |
72 | |
bb17efa0 |
73 | This method also setups an additional has_many relationship called |
74 | parents which is useful when you want to treat an adjacency list |
75 | as a DAG. |
76 | |
87427fdb |
77 | =cut |
78 | |
82958127 |
79 | __PACKAGE__->mk_classdata( '_parent_column' => 'parent_id' ); |
80 | |
81 | sub parent_column { |
82 | my $class = shift; |
83 | if (@_) { |
84 | my $parent_col = shift; |
85 | my $primary_col = ($class->primary_columns())[0]; |
86 | $class->belongs_to( '_parent' => $class => { "foreign.$primary_col" => "self.$parent_col" } ); |
87 | $class->has_many( 'children' => $class => { "foreign.$parent_col" => "self.$primary_col" } ); |
c0d76c37 |
88 | $class->has_many( 'parents' => $class => { "foreign.$primary_col" => "self.$parent_col" }, {cascade_delete=>0} ); |
82958127 |
89 | $class->_parent_column( $parent_col ); |
90 | return 1; |
91 | } |
92 | return $class->_parent_column(); |
93 | } |
87427fdb |
94 | |
c0d76c37 |
95 | |
96 | |
87427fdb |
97 | =head2 parent |
98 | |
99 | my $parent = $employee->parent(); |
100 | $employee->parent( $parent_obj ); |
101 | $employee->parent( $parent_id ); |
102 | |
82958127 |
103 | Retrieves the object's parent object, or changes the object's |
9717d3ca |
104 | parent to the specified parent or parent ID. If you would like |
105 | to make the object the root node, just set the parent to 0. |
106 | |
107 | If you are setting the parent then 0 will be returned if the |
108 | specified parent is already the object's parent and 1 on |
109 | success. |
87427fdb |
110 | |
87427fdb |
111 | =cut |
112 | |
113 | sub parent { |
82958127 |
114 | my $self = shift; |
115 | if (@_) { |
116 | my $new_parent = shift; |
117 | my $parent_col = $self->_parent_column(); |
87427fdb |
118 | if (ref($new_parent)) { |
82958127 |
119 | $new_parent = $new_parent->id() || croak('Parent object does not have an ID');; |
87427fdb |
120 | } |
82958127 |
121 | return 0 if ($new_parent == ($self->get_column($parent_col)||0)); |
122 | $self->set_column( $parent_col => $new_parent ); |
87427fdb |
123 | $self->update(); |
124 | return 1; |
125 | } |
82958127 |
126 | return $self->_parent(); |
87427fdb |
127 | } |
128 | |
c0d76c37 |
129 | |
130 | |
131 | =head2 set_parent |
132 | |
133 | $employee->set_parent($boss_obj); |
134 | $employee->set_parent($boss_id); |
135 | |
136 | A syntactic alternative to ->parent() for setting only. |
137 | |
138 | =cut |
139 | |
140 | sub set_parent { |
141 | my $self = shift; |
142 | if (@_) { |
143 | my $new_parent = shift; |
144 | my $parent_col = $self->_parent_column(); |
145 | if (ref($new_parent)) { |
146 | $new_parent = $new_parent->id() || croak('Parent object does not have an ID');; |
147 | } |
148 | return 0 if ($new_parent == ($self->get_column($parent_col)||0)); |
149 | $self->set_column( $parent_col => $new_parent ); |
150 | $self->update(); |
151 | return 1; |
152 | } |
153 | } |
154 | |
155 | |
156 | |
bb17efa0 |
157 | =head2 parents |
158 | |
159 | my $parents = $node->parents(); |
160 | my @parents = $node->parents(); |
161 | |
162 | This has_many relationship is not that useful as it will |
163 | never return more than one parent due to the one-to-many |
164 | structure of adjacency lists. The reason this relationship |
165 | is defined is so that this tree type may be treated as if |
166 | it was a DAG. |
167 | |
87427fdb |
168 | =head2 children |
169 | |
170 | my $children_rs = $employee->children(); |
171 | my @children = $employee->children(); |
172 | |
173 | Returns a list or record set, depending on context, of all |
82958127 |
174 | the objects one level below the current one. This method |
175 | is created when parent_column() is called, which sets up a |
176 | has_many relationship called children. |
87427fdb |
177 | |
c0d76c37 |
178 | =head2 add_child |
87427fdb |
179 | |
c0d76c37 |
180 | $parent->add_child( $child ); |
181 | $parent->add_child( $child, $child, ... ); |
87427fdb |
182 | |
9717d3ca |
183 | Sets the child, or children, to the new parent. Returns 1 |
184 | on success and returns 0 if the parent object already has |
185 | the child. |
87427fdb |
186 | |
187 | =cut |
188 | |
c0d76c37 |
189 | sub add_child { |
9717d3ca |
190 | my $self = shift; |
191 | my $return = 1; |
192 | foreach my $child (@_) { |
193 | $child->parent( $self ); |
194 | } |
195 | return $return; |
87427fdb |
196 | } |
197 | |
c0d76c37 |
198 | |
199 | |
200 | =head2 add_children |
201 | |
202 | An alias for add_child. |
203 | |
204 | =cut |
205 | |
206 | sub add_children { |
207 | my $self = shift; |
208 | return $self->add_child(@_); |
209 | } |
210 | |
211 | |
212 | |
82958127 |
213 | =head2 siblings |
214 | |
215 | my $rs = $node->siblings(); |
216 | my @siblings = $node->siblings(); |
217 | |
218 | Returns either a result set or an array of all other objects |
219 | with the same parent as the calling object. |
220 | |
221 | =cut |
222 | |
223 | sub siblings { |
224 | my( $self ) = @_; |
225 | my $parent_col = $self->_parent_column; |
226 | my $primary_col = ($self->primary_columns())[0]; |
227 | my $rs = $self->result_source->resultset->search( |
228 | { |
229 | $parent_col => $self->get_column($parent_col), |
230 | $primary_col => { '!=' => $self->get_column($primary_col) }, |
231 | }, |
232 | ); |
233 | return $rs->all() if (wantarray()); |
234 | return $rs; |
235 | } |
236 | |
82958127 |
237 | |
87427fdb |
238 | |
c0d76c37 |
239 | =head2 add_sibling |
240 | |
241 | $obj->add_sibling( $sibling ); |
242 | $obj->add_sibling( $sibling, $sibling, ... ); |
87427fdb |
243 | |
9717d3ca |
244 | Sets the passed in object(s) to have the same parent |
245 | as the calling object. Returns 1 on success and |
246 | 0 if the sibling already has the same parent. |
87427fdb |
247 | |
248 | =cut |
249 | |
c0d76c37 |
250 | sub add_sibling { |
9717d3ca |
251 | my $self = shift; |
252 | my $return = 1; |
253 | foreach my $node (@_) { |
254 | $return = 0 if (!$node->parent( $self->parent() )); |
255 | } |
256 | return $return; |
87427fdb |
257 | } |
258 | |
c0d76c37 |
259 | |
260 | |
74d97bdc |
261 | =head2 is_leaf |
262 | |
263 | if ($obj->is_leaf()) { ... } |
264 | |
265 | Returns 1 if the object has no children, and 0 otherwise. |
266 | |
267 | =cut |
268 | |
269 | sub is_leaf { |
270 | my( $self ) = @_; |
271 | return $self->result_source->resultset->search( |
272 | { $self->_parent_column => $self->id() }, |
273 | { limit => 1 } |
274 | )->count(); |
275 | } |
276 | |
c0d76c37 |
277 | |
278 | |
74d97bdc |
279 | =head2 is_root |
280 | |
281 | if ($obj->is_root()) { ... } |
282 | |
283 | Returns 1 if the object has no parent, and 0 otherwise. |
284 | |
285 | =cut |
286 | |
287 | sub is_root { |
288 | my( $self ) = @_; |
289 | return ( $self->get_column( $self->_parent_column ) ? 1 : 0 ); |
290 | } |
291 | |
c0d76c37 |
292 | |
293 | |
74d97bdc |
294 | =head2 is_branch |
295 | |
296 | if ($obj->is_branch()) { ... } |
297 | |
298 | Returns 1 if the object has a parent and has children. |
299 | Returns 0 otherwise. |
300 | |
301 | =cut |
302 | |
303 | sub is_branch { |
304 | my( $self ) = @_; |
c0d76c37 |
305 | return !($self->is_leaf() or $self->is_root()); |
306 | } |
307 | |
308 | |
309 | |
310 | =head2 descendents |
311 | |
312 | Returns a flat list of *all* the node's descendents. |
313 | Dangerously recursive. Use with extreme caution. May contain |
314 | nuts. |
315 | |
316 | =cut |
317 | |
318 | sub descendents { |
319 | my $self = shift; |
320 | my @descendents; |
321 | for my $child ($self->children) { |
322 | push @descendents, $child, $child->descendents; |
323 | } |
324 | return @descendents; |
325 | } |
326 | |
327 | |
328 | |
329 | =head2 pharaoh_delete |
330 | |
331 | Deletes a node and all it's children (even if cascade_delete is off) |
332 | |
333 | =cut |
334 | |
335 | sub pharaoh_delete { |
336 | my $self = shift; |
337 | for my $child ($self->children) { |
338 | $child->pharaoh_delete; |
339 | } |
340 | $self->delete; |
74d97bdc |
341 | } |
342 | |
c0d76c37 |
343 | |
344 | |
345 | =head2 grandmother_delete |
346 | |
347 | Deletes a node and sends all its children to live with their grandmother |
348 | |
349 | =cut |
350 | |
351 | sub grandmother_delete { |
352 | my $self = shift; |
353 | $self->parent->add_children($self->children); |
354 | $self->delete; |
355 | } |
356 | |
357 | |
358 | |
359 | =head2 promote_eldest_child_delete |
360 | |
361 | Deletes a node and promotes the first of it children to take its place. |
362 | If that node already had children, they will now be siblings of the new |
363 | parent node's former siblings (which are now its children). |
364 | |
365 | =cut |
366 | |
367 | sub promote_eldest_child_delete { |
368 | my $self = shift; |
369 | my @children = $self->children; |
370 | my $eldest = shift @children; |
371 | $eldest->set_parent($self->parent); |
372 | $eldest->add_children(@children); |
373 | $self->delete; |
374 | } |
375 | |
376 | |
377 | |
378 | =head2 |
379 | |
380 | Replaces the current node with the given replacement, and then deletes the |
381 | current node. The replacement node with have the old node's parent, and its |
382 | children will be the union of its original children and the old node's |
383 | children. |
384 | |
385 | =cut |
386 | |
387 | sub replace_with_and_delete { |
388 | my ($self, $replacement) = @_; |
389 | $replacement->add_children($self->children); |
390 | $replacement->set_parent($self->parent); |
391 | $self->delete; |
392 | } |
393 | |
394 | |
395 | |
74d97bdc |
396 | =head2 set_primary_key |
397 | |
398 | This method is an override of DBIx::Class' method for setting the |
399 | class' primary key column(s). This method passes control right on |
400 | to the normal method after first validating that only one column is |
401 | being selected as a primary key. If more than one column is then |
402 | an error will be thrown. |
403 | |
404 | =cut |
405 | |
c0d76c37 |
406 | sub set_primary_key { |
74d97bdc |
407 | my $self = shift; |
408 | if (@_>1) { |
409 | croak('You may only specify a single column as the primary key for adjacency tree classes'); |
410 | } |
411 | return $self->next::method( @_ ); |
412 | } |
413 | |
87427fdb |
414 | 1; |
415 | __END__ |
416 | |
4b44af23 |
417 | =head1 INHERITED METHODS |
418 | |
419 | =head2 DBIx::Class |
420 | |
421 | =over 4 |
422 | |
423 | =item * |
424 | |
425 | L<mk_classdata|DBIx::Class/mk_classdata> |
426 | |
427 | =item * |
428 | |
429 | L<component_base_class|DBIx::Class/component_base_class> |
430 | |
431 | =back |
432 | |
433 | =head2 DBIx::Class::Componentised |
434 | |
435 | =over 4 |
436 | |
437 | =item * |
438 | |
439 | L<inject_base|DBIx::Class::Componentised/inject_base> |
440 | |
441 | =item * |
442 | |
443 | L<load_components|DBIx::Class::Componentised/load_components> |
444 | |
445 | =item * |
446 | |
447 | L<load_own_components|DBIx::Class::Componentised/load_own_components> |
448 | |
449 | =back |
450 | |
451 | =head2 Class::Data::Accessor |
452 | |
453 | =over 4 |
454 | |
455 | =item * |
456 | |
457 | L<mk_classaccessor|Class::Data::Accessor/mk_classaccessor> |
458 | |
459 | =back |
460 | |
87427fdb |
461 | =head1 AUTHOR |
462 | |
463 | Aran Clary Deltac <bluefeet@cpan.org> |
464 | |
465 | =head1 LICENSE |
466 | |
467 | You may distribute this code under the same terms as Perl itself. |
468 | |