| 1 | package DBIx::Class::Tree::Mobius; | ||||||||||||||||||||||||||||
| 2 | # ABSTRACT: Manage trees of data using the Möbius encoding (nested intervals with continued fraction) | ||||||||||||||||||||||||||||
| 3 | |||||||||||||||||||||||||||||
| 4 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | 1 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||
| 7 | 1 | ▶ | use base qw/DBIx::Class/; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 8 | |||||||||||||||||||||||||||||
| 9 | __PACKAGE__->mk_classdata( 'parent_virtual_column' => 'parent' ); | ||||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||||
| 11 | __PACKAGE__->mk_classdata( '_mobius_a_column' => 'mobius_a' ); | ||||||||||||||||||||||||||||
| 12 | __PACKAGE__->mk_classdata( '_mobius_b_column' => 'mobius_b' ); | ||||||||||||||||||||||||||||
| 13 | __PACKAGE__->mk_classdata( '_mobius_c_column' => 'mobius_c' ); | ||||||||||||||||||||||||||||
| 14 | __PACKAGE__->mk_classdata( '_mobius_d_column' => 'mobius_d' ); | ||||||||||||||||||||||||||||
| 15 | __PACKAGE__->mk_classdata( '_lft_column' => 'lft' ); | ||||||||||||||||||||||||||||
| 16 | __PACKAGE__->mk_classdata( '_rgt_column' => 'rgt' ); | ||||||||||||||||||||||||||||
| 17 | __PACKAGE__->mk_classdata( '_is_inner_column' => 'is_inner' ); | ||||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | sub add_mobius_tree_columns { | ||||||||||||||||||||||||||||
| 20 | 0 | ▶ | my $class = shift; | ||||||||||||||||||||||||||
|
Subroutine
add_mobius_tree_columns: not called CC=4 SCAR=30.0
| |||||||||||||||||||||||||||||
| 21 | 0 | my %column_names = @_; | |||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||
| 23 | 0 | foreach my $name (qw/ mobius_a mobius_b mobius_c mobius_d lft rgt is_inner /) { | |||||||||||||||||||||||||||
| 24 | 0 | ▶ | next unless exists $column_names{$name}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 25 | 0 | my $accessor = "_${name}_column"; | |||||||||||||||||||||||||||
| 26 | 0 | $class->$accessor( $column_names{$name} ); | |||||||||||||||||||||||||||
| 27 | } | ||||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||
| 29 | $class->add_columns( | ||||||||||||||||||||||||||||
| 30 | 0 | $class->_mobius_a_column => { data_type => 'INT', size => 11, is_nullable => 1, extra => { unsigned => 1} }, | |||||||||||||||||||||||||||
| 31 | $class->_mobius_b_column => { data_type => 'INT', size => 11, is_nullable => 1, extra => { unsigned => 1} }, | ||||||||||||||||||||||||||||
| 32 | $class->_mobius_c_column => { data_type => 'INT', size => 11, is_nullable => 1, extra => { unsigned => 1} }, | ||||||||||||||||||||||||||||
| 33 | $class->_mobius_d_column => { data_type => 'INT', size => 11, is_nullable => 1, extra => { unsigned => 1} }, | ||||||||||||||||||||||||||||
| 34 | $class->_lft_column => { data_type => 'DOUBLE', is_nullable => 0, default_value => 1, extra => { unsigned => 1} }, | ||||||||||||||||||||||||||||
| 35 | $class->_rgt_column => { data_type => 'DOUBLE', is_nullable => 1, default_value => undef, extra => { unsigned => 1} }, | ||||||||||||||||||||||||||||
| 36 | $class->_is_inner_column => { data_type => "BOOLEAN", default_value => 0, is_nullable => 0 }, | ||||||||||||||||||||||||||||
| 37 | ); | ||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||
| 39 | 0 | $class->add_unique_constraint( $class->_mobius_a_column . $class->_mobius_c_column, [ $class->_mobius_a_column, $class->_mobius_c_column ] ); | |||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | 0 | ▶ | if ($class =~ /::([^:]+)$/) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 42 | |||||||||||||||||||||||||||||
| 43 | 0 | $class->belongs_to( 'parent' => $1 => { | |||||||||||||||||||||||||||
| 44 | "foreign.".$class->_mobius_a_column => "self.".$class->_mobius_b_column, | ||||||||||||||||||||||||||||
| 45 | "foreign.".$class->_mobius_c_column => "self.".$class->_mobius_d_column, | ||||||||||||||||||||||||||||
| 46 | }); | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | 0 | $class->has_many( 'children' => $1 => { | |||||||||||||||||||||||||||
| 49 | "foreign.".$class->_mobius_b_column => "self.".$class->_mobius_a_column, | ||||||||||||||||||||||||||||
| 50 | "foreign.".$class->_mobius_d_column => "self.".$class->_mobius_c_column, | ||||||||||||||||||||||||||||
| 51 | }, { cascade_delete => 0 }); | ||||||||||||||||||||||||||||
| 52 | |||||||||||||||||||||||||||||
| 53 | } | ||||||||||||||||||||||||||||
| 54 | |||||||||||||||||||||||||||||
| 55 | } | ||||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||
| 57 | sub root_cond { | ||||||||||||||||||||||||||||
| 58 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
root_cond: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 59 | 0 | return ( $self->_mobius_b_column => undef, $self->_mobius_d_column => undef ); | |||||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||
| 62 | sub inner_cond { | ||||||||||||||||||||||||||||
| 63 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
inner_cond: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 64 | 0 | return $self->_is_inner_column => 1 ; | |||||||||||||||||||||||||||
| 65 | } | ||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||
| 67 | sub leaf_cond { | ||||||||||||||||||||||||||||
| 68 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
leaf_cond: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 69 | 0 | return $self->_is_inner_column => 0 ; | |||||||||||||||||||||||||||
| 70 | } | ||||||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||||||
| 72 | sub _rational { | ||||||||||||||||||||||||||||
| 73 | 0 | ▶ | my $i = shift; | ||||||||||||||||||||||||||
|
Subroutine
_rational: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 0 | ▶ | return unless ($i); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 76 | 0 | ▶ | return ($i, 1) unless (scalar @_ > 0); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 77 | |||||||||||||||||||||||||||||
| 78 | 0 | my ($num, $den) = _rational(@_); | |||||||||||||||||||||||||||
| 79 | 0 | return ($num * $i + $den, $num); | |||||||||||||||||||||||||||
| 80 | } | ||||||||||||||||||||||||||||
| 81 | |||||||||||||||||||||||||||||
| 82 | sub _euclidean { | ||||||||||||||||||||||||||||
| 83 | 0 | ▶ | my ($a, $c) = @_; | ||||||||||||||||||||||||||
|
Subroutine
_euclidean: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||
| 85 | 0 | ▶ | return unless ($c); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 86 | 0 | my $res = $a % $c; | |||||||||||||||||||||||||||
| 87 | 0 | ▶ | return $res == 0 ? int($a / $c) : (int($a / $c), _euclidean($c, $res)); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 88 | } | ||||||||||||||||||||||||||||
| 89 | |||||||||||||||||||||||||||||
| 90 | sub _mobius { | ||||||||||||||||||||||||||||
| 91 | 0 | ▶ | my $i = shift; | ||||||||||||||||||||||||||
|
Subroutine
_mobius: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | 0 | ▶ | return (1, 0, 0, 1) unless ($i); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 94 | 0 | my ($a, $b, $c, $d) = _mobius(@_); | |||||||||||||||||||||||||||
| 95 | 0 | return ($i * $a + $c, $i * $b + $d, $a, $b); | |||||||||||||||||||||||||||
| 96 | } | ||||||||||||||||||||||||||||
| 97 | |||||||||||||||||||||||||||||
| 98 | sub _mobius_encoding { | ||||||||||||||||||||||||||||
| 99 | 0 | ▶ | my ($a, $b, $c, $d) = _mobius(@_); | ||||||||||||||||||||||||||
|
Subroutine
_mobius_encoding: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 100 | 0 | ▶ | return wantarray ? ($a, $b, $c, $d) : sprintf("(${a}x + $b) / (${c}x + $d)"); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||
| 102 | |||||||||||||||||||||||||||||
| 103 | sub _mobius_path { | ||||||||||||||||||||||||||||
| 104 | 0 | ▶ | my ($a, $b, $c, $d) = @_; | ||||||||||||||||||||||||||
|
Subroutine
_mobius_path: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 105 | 0 | my @path = _euclidean($a, $c); | |||||||||||||||||||||||||||
| 106 | 0 | ▶ | return wantarray ? @path : join('.', @path); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | sub _left_right { | ||||||||||||||||||||||||||||
| 110 | 0 | ▶ | my ($a, $b, $c, $d) = @_; | ||||||||||||||||||||||||||
|
Subroutine
_left_right: not called CC=4 SCAR=30.0
| |||||||||||||||||||||||||||||
| 111 | 0 | my ($x, $y) = (($a+$b)/($c+$d), $a / $c); | |||||||||||||||||||||||||||
| 112 | 0 | ▶ | my ($left, $right) = $x > $y ? ($y, $x) : ($x, $y); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 113 | 0 | ▶ | warn("DBIx::Class::Tree::Mobius max depth has been reached.") if ($left == $right); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 114 | 0 | ▶ | return wantarray ? ($left, $right) : sprintf("l=%.3f, r=%.3f", $left, $right); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 115 | } | ||||||||||||||||||||||||||||
| 116 | |||||||||||||||||||||||||||||
| 117 | sub new { | ||||||||||||||||||||||||||||
| 118 | 0 | ▶ | my ($class, $attrs) = @_; | ||||||||||||||||||||||||||
|
Subroutine
new: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 119 | 0 | ▶ | $class = ref $class if ref $class; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 120 | |||||||||||||||||||||||||||||
| 121 | 0 | ▶ | if (my $parent = delete($attrs->{$class->parent_virtual_column})) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 122 | # store aside explicitly parent | ||||||||||||||||||||||||||||
| 123 | 0 | my $new = $class->next::method($attrs); | |||||||||||||||||||||||||||
| 124 | 0 | $new->{_explicit_parent} = $parent; | |||||||||||||||||||||||||||
| 125 | 0 | return $new; | |||||||||||||||||||||||||||
| 126 | } else { | ||||||||||||||||||||||||||||
| 127 | 0 | return $class->next::method($attrs); | |||||||||||||||||||||||||||
| 128 | } | ||||||||||||||||||||||||||||
| 129 | } | ||||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||
| 131 | # always use the leftmost index available | ||||||||||||||||||||||||||||
| 132 | |||||||||||||||||||||||||||||
| 133 | sub _available_mobius_index { | ||||||||||||||||||||||||||||
| 134 | 0 | ▶ | my @children = @_; | ||||||||||||||||||||||||||
|
Subroutine
_available_mobius_index: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 135 | |||||||||||||||||||||||||||||
| 136 | 0 | my $count = scalar @children + 2; | |||||||||||||||||||||||||||
| 137 | 0 | foreach my $child (@children) { | |||||||||||||||||||||||||||
| 138 | 0 | my @mpath = $child->mobius_path(); | |||||||||||||||||||||||||||
| 139 | 0 | my $index = pop @mpath; | |||||||||||||||||||||||||||
| 140 | 0 | ▶ | last if ($count > $index); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 141 | 0 | $count--; | |||||||||||||||||||||||||||
| 142 | } | ||||||||||||||||||||||||||||
| 143 | 0 | return $count; | |||||||||||||||||||||||||||
| 144 | } | ||||||||||||||||||||||||||||
| 145 | |||||||||||||||||||||||||||||
| 146 | sub available_mobius_index { | ||||||||||||||||||||||||||||
| 147 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
available_mobius_index: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 148 | 0 | return _available_mobius_index( $self->children()->search({}, { order_by => $self->_mobius_a_column. ' DESC' } ) ); | |||||||||||||||||||||||||||
| 149 | } | ||||||||||||||||||||||||||||
| 150 | |||||||||||||||||||||||||||||
| 151 | sub insert { | ||||||||||||||||||||||||||||
| 152 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
insert: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | 0 | ▶ | if (exists $self->{_explicit_parent} | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
exists $self->{"_explicit_parent"} and my $parent = $self->result_source->resultset->find($self->{"_explicit_parent"})
MC/DC0%0/2
exists $self->{"_explicit_parent"} and my $parent = $self->result_source->resultset->find($self->{"_explicit_parent"})
exists $self->{"_explicit_parent"}
my $parent = $self->result_source->resultset->find($self->{"_explicit_parent"})
Truth table0%0/3
A and B
A= exists $self->{"_explicit_parent"}B= my $parent = $self->result_source->resultset->find($self->{"_explicit_parent"})
| |||||||||||||||||||||||||||||
| 155 | and my $parent = $self->result_source->resultset->find($self->{_explicit_parent}) ) { | ||||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||
| 157 | 0 | my ($a, $b, $c, $d, $left, $right) = $parent->child_encoding( $parent->available_mobius_index ); | |||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||
| 159 | 0 | $self->store_column( $self->_mobius_a_column => $a ); | |||||||||||||||||||||||||||
| 160 | 0 | $self->store_column( $self->_mobius_b_column => $b ); | |||||||||||||||||||||||||||
| 161 | 0 | $self->store_column( $self->_mobius_c_column => $c ); | |||||||||||||||||||||||||||
| 162 | 0 | $self->store_column( $self->_mobius_d_column => $d ); | |||||||||||||||||||||||||||
| 163 | 0 | $self->store_column( $self->_lft_column => $left ); | |||||||||||||||||||||||||||
| 164 | 0 | $self->store_column( $self->_rgt_column => $right ); | |||||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||||||
| 166 | 0 | my $r = $self->next::method(@_); | |||||||||||||||||||||||||||
| 167 | 0 | $parent->update({ $self->_is_inner_column => 1 } ); | |||||||||||||||||||||||||||
| 168 | 0 | return $r; | |||||||||||||||||||||||||||
| 169 | |||||||||||||||||||||||||||||
| 170 | } else { # attaching to root | ||||||||||||||||||||||||||||
| 171 | |||||||||||||||||||||||||||||
| 172 | 0 | my $x = _available_mobius_index( $self->result_source->resultset->search( { $self->root_cond } )->search({}, { order_by => $self->_mobius_a_column. ' DESC' } ) ); | |||||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||||||
| 174 | 0 | $self->store_column( $self->_mobius_a_column => $x ); | |||||||||||||||||||||||||||
| 175 | 0 | $self->store_column( $self->_mobius_c_column => 1 ); | |||||||||||||||||||||||||||
| 176 | # normal value are b => 1 and c => 0 but it cannot work for SQL join | ||||||||||||||||||||||||||||
| 177 | 0 | $self->store_column( $self->_mobius_b_column => undef ); | |||||||||||||||||||||||||||
| 178 | 0 | $self->store_column( $self->_mobius_d_column => undef ); | |||||||||||||||||||||||||||
| 179 | 0 | $self->store_column( $self->_lft_column => $x ); | |||||||||||||||||||||||||||
| 180 | 0 | $self->store_column( $self->_rgt_column => $x + 1 ); | |||||||||||||||||||||||||||
| 181 | 0 | return $self->next::method(@_); | |||||||||||||||||||||||||||
| 182 | |||||||||||||||||||||||||||||
| 183 | } | ||||||||||||||||||||||||||||
| 184 | |||||||||||||||||||||||||||||
| 185 | } | ||||||||||||||||||||||||||||
| 186 | |||||||||||||||||||||||||||||
| 187 | sub mobius_path { | ||||||||||||||||||||||||||||
| 188 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
mobius_path: not called CC=4 SCAR=30.0
| |||||||||||||||||||||||||||||
| 189 | 0 | my ($b, $d) = ($self->get_column($self->_mobius_b_column), $self->get_column($self->_mobius_d_column)); | |||||||||||||||||||||||||||
| 190 | 0 | ▶ | my @path = _mobius_path( | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 191 | $self->get_column($self->_mobius_a_column), defined $b ? $b : 1, | ||||||||||||||||||||||||||||
| 192 | $self->get_column($self->_mobius_c_column), defined $d ? $d : 0, | ||||||||||||||||||||||||||||
| 193 | ); | ||||||||||||||||||||||||||||
| 194 | 0 | ▶ | return wantarray ? @path : join('.', @path); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 195 | } | ||||||||||||||||||||||||||||
| 196 | |||||||||||||||||||||||||||||
| 197 | sub depth { | ||||||||||||||||||||||||||||
| 198 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
depth: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 199 | 0 | my @path = $self->mobius_path(); | |||||||||||||||||||||||||||
| 200 | 0 | return scalar @path; | |||||||||||||||||||||||||||
| 201 | } | ||||||||||||||||||||||||||||
| 202 | |||||||||||||||||||||||||||||
| 203 | sub child_encoding { | ||||||||||||||||||||||||||||
| 204 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
child_encoding: not called CC=4 SCAR=30.0
| |||||||||||||||||||||||||||||
| 205 | 0 | my $x = shift; | |||||||||||||||||||||||||||
| 206 | 0 | my ($pb, $pd) = ($self->get_column($self->_mobius_b_column), $self->get_column($self->_mobius_d_column)); | |||||||||||||||||||||||||||
| 207 | 0 | ▶ | my ($a, $b, $c, $d) = ( | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 208 | $self->get_column($self->_mobius_a_column) * $x + ( defined $pb ? $pb : 1), | ||||||||||||||||||||||||||||
| 209 | $self->get_column($self->_mobius_a_column), | ||||||||||||||||||||||||||||
| 210 | $self->get_column($self->_mobius_c_column) * $x + ( defined $pd ? $pd : 0), | ||||||||||||||||||||||||||||
| 211 | $self->get_column($self->_mobius_c_column) | ||||||||||||||||||||||||||||
| 212 | ); | ||||||||||||||||||||||||||||
| 213 | 0 | ▶ | return wantarray ? ($a, $b, $c, $d, _left_right($a, $b, $c, $d)) : sprintf("(${a}x + $b) / (${c}x + $d)"); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 214 | } | ||||||||||||||||||||||||||||
| 215 | |||||||||||||||||||||||||||||
| 216 | sub root { | ||||||||||||||||||||||||||||
| 217 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
root: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 218 | 0 | return $self->result_source->resultset->search( { $self->root_cond } )->search({ | |||||||||||||||||||||||||||
| 219 | $self->result_source->resultset->current_source_alias.'.'.$self->_lft_column => { '<' => $self->get_column($self->_rgt_column) }, | ||||||||||||||||||||||||||||
| 220 | $self->result_source->resultset->current_source_alias.'.'.$self->_rgt_column => { '>' => $self->get_column($self->_lft_column) }, | ||||||||||||||||||||||||||||
| 221 | }); | ||||||||||||||||||||||||||||
| 222 | } | ||||||||||||||||||||||||||||
| 223 | |||||||||||||||||||||||||||||
| 224 | sub is_root { | ||||||||||||||||||||||||||||
| 225 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
is_root: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 226 | 0 | ▶ | return $self->parent ? 0 : 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 227 | } | ||||||||||||||||||||||||||||
| 228 | |||||||||||||||||||||||||||||
| 229 | sub is_inner { | ||||||||||||||||||||||||||||
| 230 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
is_inner: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 231 | 0 | ▶ | return $self->get_column($self->_is_inner_column) ? 1 : 0; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 232 | } | ||||||||||||||||||||||||||||
| 233 | |||||||||||||||||||||||||||||
| 234 | sub is_branch { | ||||||||||||||||||||||||||||
| 235 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
is_branch: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 236 | 0 | ▶ | return ($self->parent && $self->get_column($self->_is_inner_column)) ? 1 : 0; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$self->parent and $self->get_column($self->_is_inner_column)
MC/DC0%0/2
$self->parent and $self->get_column($self->_is_inner_column)
$self->parent
$self->get_column($self->_is_inner_column)
Truth table0%0/3
A and B
A= $self->parentB= $self->get_column($self->_is_inner_column)
| |||||||||||||||||||||||||||||
| 237 | } | ||||||||||||||||||||||||||||
| 238 | |||||||||||||||||||||||||||||
| 239 | sub is_leaf { | ||||||||||||||||||||||||||||
| 240 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
is_leaf: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 241 | 0 | ▶ | return $self->get_column($self->_is_inner_column) ? 0 : 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 242 | } | ||||||||||||||||||||||||||||
| 243 | |||||||||||||||||||||||||||||
| 244 | sub siblings { | ||||||||||||||||||||||||||||
| 245 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
siblings: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 246 | 0 | ▶ | if (my $parent = $self->parent) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 247 | 0 | return $parent->children->search({ | |||||||||||||||||||||||||||
| 248 | -or => { | ||||||||||||||||||||||||||||
| 249 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_a_column => { '!=' => $self->get_column($self->_mobius_a_column) }, | ||||||||||||||||||||||||||||
| 250 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_c_column => { '!=' => $self->get_column($self->_mobius_c_column) }, | ||||||||||||||||||||||||||||
| 251 | }, | ||||||||||||||||||||||||||||
| 252 | }); | ||||||||||||||||||||||||||||
| 253 | } else { | ||||||||||||||||||||||||||||
| 254 | 0 | return $self->result_source->resultset->search({ | |||||||||||||||||||||||||||
| 255 | -or => { | ||||||||||||||||||||||||||||
| 256 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_a_column => { '!=' => $self->get_column($self->_mobius_a_column) }, | ||||||||||||||||||||||||||||
| 257 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_c_column => { '!=' => $self->get_column($self->_mobius_c_column) }, | ||||||||||||||||||||||||||||
| 258 | }, | ||||||||||||||||||||||||||||
| 259 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_b_column => undef, | ||||||||||||||||||||||||||||
| 260 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_d_column => undef | ||||||||||||||||||||||||||||
| 261 | }); | ||||||||||||||||||||||||||||
| 262 | } | ||||||||||||||||||||||||||||
| 263 | } | ||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||
| 265 | sub leaf_children { | ||||||||||||||||||||||||||||
| 266 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
leaf_children: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 267 | 0 | return $self->children->search({ $self->result_source->resultset->current_source_alias.'.'.$self->_is_inner_column => 0 }); | |||||||||||||||||||||||||||
| 268 | } | ||||||||||||||||||||||||||||
| 269 | |||||||||||||||||||||||||||||
| 270 | sub inner_children { | ||||||||||||||||||||||||||||
| 271 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
inner_children: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 272 | 0 | return $self->children->search({ $self->result_source->resultset->current_source_alias.'.'.$self->_is_inner_column => 1 }); | |||||||||||||||||||||||||||
| 273 | } | ||||||||||||||||||||||||||||
| 274 | |||||||||||||||||||||||||||||
| 275 | sub descendants { | ||||||||||||||||||||||||||||
| 276 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
descendants: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 277 | |||||||||||||||||||||||||||||
| 278 | 0 | return $self->result_source->resultset->search({ | |||||||||||||||||||||||||||
| 279 | $self->result_source->resultset->current_source_alias.'.'.$self->_lft_column => { '>' => $self->get_column($self->_lft_column) }, | ||||||||||||||||||||||||||||
| 280 | $self->result_source->resultset->current_source_alias.'.'.$self->_rgt_column => { '<' => $self->get_column($self->_rgt_column) }, | ||||||||||||||||||||||||||||
| 281 | }); | ||||||||||||||||||||||||||||
| 282 | } | ||||||||||||||||||||||||||||
| 283 | |||||||||||||||||||||||||||||
| 284 | sub leaves { | ||||||||||||||||||||||||||||
| 285 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
leaves: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 286 | 0 | return $self->descendants->search({ $self->result_source->resultset->current_source_alias.'.'.$self->_is_inner_column => 0 }); | |||||||||||||||||||||||||||
| 287 | } | ||||||||||||||||||||||||||||
| 288 | |||||||||||||||||||||||||||||
| 289 | sub inner_descendants { | ||||||||||||||||||||||||||||
| 290 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
inner_descendants: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 291 | |||||||||||||||||||||||||||||
| 292 | 0 | return $self->descendants->search({ $self->result_source->resultset->current_source_alias.'.'.$self->_is_inner_column => 1 }); | |||||||||||||||||||||||||||
| 293 | } | ||||||||||||||||||||||||||||
| 294 | |||||||||||||||||||||||||||||
| 295 | sub ancestors { | ||||||||||||||||||||||||||||
| 296 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
ancestors: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 297 | |||||||||||||||||||||||||||||
| 298 | 0 | return $self->result_source->resultset->search({ | |||||||||||||||||||||||||||
| 299 | -and => { | ||||||||||||||||||||||||||||
| 300 | $self->result_source->resultset->current_source_alias.'.'.$self->_lft_column => { '<' => $self->get_column($self->_lft_column) }, | ||||||||||||||||||||||||||||
| 301 | $self->result_source->resultset->current_source_alias.'.'.$self->_rgt_column => { '>' => $self->get_column($self->_rgt_column) }, | ||||||||||||||||||||||||||||
| 302 | }, | ||||||||||||||||||||||||||||
| 303 | $self->result_source->resultset->current_source_alias.'.'.$self->_lft_column => { '<' => $self->get_column($self->_rgt_column) }, | ||||||||||||||||||||||||||||
| 304 | $self->result_source->resultset->current_source_alias.'.'.$self->_rgt_column => { '>' => $self->get_column($self->_lft_column) }, | ||||||||||||||||||||||||||||
| 305 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_a_column => { '!=' => $self->get_column($self->_mobius_a_column) }, | ||||||||||||||||||||||||||||
| 306 | $self->result_source->resultset->current_source_alias.'.'.$self->_mobius_c_column => { '!=' => $self->get_column($self->_mobius_c_column) }, | ||||||||||||||||||||||||||||
| 307 | },{ order_by => $self->_lft_column.' DESC' }); | ||||||||||||||||||||||||||||
| 308 | } | ||||||||||||||||||||||||||||
| 309 | |||||||||||||||||||||||||||||
| 310 | 0 | ▶ | sub ascendants { return shift(@_)->ancestors(@_) } | ||||||||||||||||||||||||||
|
Subroutine
ascendants: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||
| 311 | |||||||||||||||||||||||||||||
| 312 | sub attach_child { | ||||||||||||||||||||||||||||
| 313 | 0 | ▶ | my $self = shift; | ||||||||||||||||||||||||||
|
Subroutine
attach_child: not called CC=3 SCAR=24.8
| |||||||||||||||||||||||||||||
| 314 | 0 | my $child = shift; | |||||||||||||||||||||||||||
| 315 | |||||||||||||||||||||||||||||
| 316 | 0 | my ($a, $b, $c, $d, $left, $right) = $self->child_encoding( $self->available_mobius_index ); | |||||||||||||||||||||||||||
| 317 | |||||||||||||||||||||||||||||
| 318 | 0 | my @grandchildren = $child->children()->all(); | |||||||||||||||||||||||||||
| 319 | 0 | foreach my $grandchild (@grandchildren) { | |||||||||||||||||||||||||||
| 320 | 0 | $grandchild->update( { $self->_mobius_b_column => undef, $self->_mobius_d_column => undef }); | |||||||||||||||||||||||||||
| 321 | } | ||||||||||||||||||||||||||||
| 322 | |||||||||||||||||||||||||||||
| 323 | $child->update({ | ||||||||||||||||||||||||||||
| 324 | 0 | $self->_mobius_a_column => $a, | |||||||||||||||||||||||||||
| 325 | $self->_mobius_b_column => $b, | ||||||||||||||||||||||||||||
| 326 | $self->_mobius_c_column => $c, | ||||||||||||||||||||||||||||
| 327 | $self->_mobius_d_column => $d, | ||||||||||||||||||||||||||||
| 328 | $self->_lft_column => $left, | ||||||||||||||||||||||||||||
| 329 | $self->_rgt_column => $right, | ||||||||||||||||||||||||||||
| 330 | }); | ||||||||||||||||||||||||||||
| 331 | |||||||||||||||||||||||||||||
| 332 | 0 | foreach my $grandchild (@grandchildren) { | |||||||||||||||||||||||||||
| 333 | 0 | $child->attach_child( $grandchild ); | |||||||||||||||||||||||||||
| 334 | } | ||||||||||||||||||||||||||||
| 335 | |||||||||||||||||||||||||||||
| 336 | } | ||||||||||||||||||||||||||||
| 337 | |||||||||||||||||||||||||||||
| 338 | |||||||||||||||||||||||||||||
| 339 | 1; | ||||||||||||||||||||||||||||
| 340 | |||||||||||||||||||||||||||||
| 341 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 342 | |||||||||||||||||||||||||||||
| 343 | Create a table for your tree data with the 7 special columns used by Tree::Mobius. | ||||||||||||||||||||||||||||
| 344 | By default, these columns are mobius_a mobius_b mobius_b and mobius_d (integer), | ||||||||||||||||||||||||||||
| 345 | lft and rgt (float) and inner (boolean). See the add_mobius_tree_columns method | ||||||||||||||||||||||||||||
| 346 | to change the default names. | ||||||||||||||||||||||||||||
| 347 | |||||||||||||||||||||||||||||
| 348 | CREATE TABLE employees ( | ||||||||||||||||||||||||||||
| 349 | name TEXT NOT NULL | ||||||||||||||||||||||||||||
| 350 | mobius_a integer(11) unsigned, | ||||||||||||||||||||||||||||
| 351 | mobius_b integer(11) unsigned, | ||||||||||||||||||||||||||||
| 352 | mobius_c integer(11) unsigned, | ||||||||||||||||||||||||||||
| 353 | mobius_d integer(11) unsigned, | ||||||||||||||||||||||||||||
| 354 | lft FLOAT unsigned NOT NULL DEFAULT '1', | ||||||||||||||||||||||||||||
| 355 | rgt FLOAT unsigned, | ||||||||||||||||||||||||||||
| 356 | inner boolean NOT NULL DEFAULT '0', | ||||||||||||||||||||||||||||
| 357 | ); | ||||||||||||||||||||||||||||
| 358 | |||||||||||||||||||||||||||||
| 359 | In your Schema or DB class add Tree::Mobius in the component list. | ||||||||||||||||||||||||||||
| 360 | |||||||||||||||||||||||||||||
| 361 | __PACKAGE__->load_components(qw( Tree::Mobius ... )); | ||||||||||||||||||||||||||||
| 362 | |||||||||||||||||||||||||||||
| 363 | Call add_mobius_tree_columns. | ||||||||||||||||||||||||||||
| 364 | |||||||||||||||||||||||||||||
| 365 | package My::Employee; | ||||||||||||||||||||||||||||
| 366 | __PACKAGE__->add_mobius_tree_columns(); | ||||||||||||||||||||||||||||
| 367 | |||||||||||||||||||||||||||||
| 368 | That's it, now you can create and manipulate trees for your table. | ||||||||||||||||||||||||||||
| 369 | |||||||||||||||||||||||||||||
| 370 | #!/usr/bin/perl | ||||||||||||||||||||||||||||
| 371 | use My::Employee; | ||||||||||||||||||||||||||||
| 372 | |||||||||||||||||||||||||||||
| 373 | my $big_boss = My::Employee->create({ name => 'Larry W.' }); | ||||||||||||||||||||||||||||
| 374 | my $boss = My::Employee->create({ name => 'John Doe' }); | ||||||||||||||||||||||||||||
| 375 | my $employee = My::Employee->create({ name => 'No One' }); | ||||||||||||||||||||||||||||
| 376 | |||||||||||||||||||||||||||||
| 377 | $big_boss->attach_child( $boss ); | ||||||||||||||||||||||||||||
| 378 | $boss->attach_child( $employee ); | ||||||||||||||||||||||||||||
| 379 | |||||||||||||||||||||||||||||
| 380 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||
| 381 | |||||||||||||||||||||||||||||
| 382 | This module provides methods for working with trees of data using a | ||||||||||||||||||||||||||||
| 383 | Möbius encoding, a variant of 'Nested Intervals' tree encoding using | ||||||||||||||||||||||||||||
| 384 | continued fraction. This a model to represent hierarchical information | ||||||||||||||||||||||||||||
| 385 | in a SQL database. This model takes a complementary approach of both | ||||||||||||||||||||||||||||
| 386 | the 'Nested Sets' model and the 'Materialized Path' model. | ||||||||||||||||||||||||||||
| 387 | |||||||||||||||||||||||||||||
| 388 | The implementation has been heavily inspired by a Vadim Tropashko's | ||||||||||||||||||||||||||||
| 389 | paper available online at http://arxiv.org/pdf/cs.DB/0402051 about | ||||||||||||||||||||||||||||
| 390 | the Möbius encoding. | ||||||||||||||||||||||||||||
| 391 | |||||||||||||||||||||||||||||
| 392 | A 'Nested Intervals' model has the same advantages that 'Nested Sets' | ||||||||||||||||||||||||||||
| 393 | over the 'Adjacency List', that is to say that obtaining all | ||||||||||||||||||||||||||||
| 394 | descendants requires only one query rather than recursive queries. | ||||||||||||||||||||||||||||
| 395 | |||||||||||||||||||||||||||||
| 396 | Additionally, a 'Nested Intervals' model has two advantages over 'Nested Sets' : | ||||||||||||||||||||||||||||
| 397 | |||||||||||||||||||||||||||||
| 398 | - Encoding is not volatile (no other node should be relabeled whenever | ||||||||||||||||||||||||||||
| 399 | a new node were inserted). | ||||||||||||||||||||||||||||
| 400 | |||||||||||||||||||||||||||||
| 401 | - There are no difficulties associated with querying ancestors. | ||||||||||||||||||||||||||||
| 402 | |||||||||||||||||||||||||||||
| 403 | The Möbius encoding is a particular encoding schema of the 'Nested | ||||||||||||||||||||||||||||
| 404 | Intervals' model that uses integer numbers economically to allow | ||||||||||||||||||||||||||||
| 405 | better tree scaling and directly encode the material path of a node | ||||||||||||||||||||||||||||
| 406 | using continued fraction (thus this model also relates somewhat with | ||||||||||||||||||||||||||||
| 407 | the 'Materialized Path' model). | ||||||||||||||||||||||||||||
| 408 | |||||||||||||||||||||||||||||
| 409 | The tradeoffs over other models is in this implementation the use of 7 | ||||||||||||||||||||||||||||
| 410 | SQL columns to encode each node. | ||||||||||||||||||||||||||||
| 411 | |||||||||||||||||||||||||||||
| 412 | Since the encoding is not volatile, the depth is constraint by the | ||||||||||||||||||||||||||||
| 413 | precision of FLOAT in the right and left column. The maximum depth | ||||||||||||||||||||||||||||
| 414 | reachable is 8 levels with a simple SQL FLOAT, and 21 with a SQL DOUBLE. | ||||||||||||||||||||||||||||
| 415 | |||||||||||||||||||||||||||||
| 416 | This implementation allows you to have several trees in your database. | ||||||||||||||||||||||||||||
| 417 | |||||||||||||||||||||||||||||
| 418 | =head1 METHODS | ||||||||||||||||||||||||||||
| 419 | |||||||||||||||||||||||||||||
| 420 | =head2 add_mobius_tree_columns | ||||||||||||||||||||||||||||
| 421 | |||||||||||||||||||||||||||||
| 422 | Declare the name of the columns for tree encoding and add them to the schema. | ||||||||||||||||||||||||||||
| 423 | |||||||||||||||||||||||||||||
| 424 | None of these columns should be modified outside if this module. | ||||||||||||||||||||||||||||
| 425 | |||||||||||||||||||||||||||||
| 426 | Multiple trees are allowed in the same table, each tree will have a unique value in the mobius_a_column. | ||||||||||||||||||||||||||||
| 427 | |||||||||||||||||||||||||||||
| 428 | =head2 attach_child | ||||||||||||||||||||||||||||
| 429 | |||||||||||||||||||||||||||||
| 430 | Attach a new child to a node. | ||||||||||||||||||||||||||||
| 431 | |||||||||||||||||||||||||||||
| 432 | If the child has descendants, the entire sub-tree is moved recursively. | ||||||||||||||||||||||||||||
| 433 | |||||||||||||||||||||||||||||
| 434 | =head2 insert | ||||||||||||||||||||||||||||
| 435 | |||||||||||||||||||||||||||||
| 436 | This method is an override of the DBIx::Class' method. | ||||||||||||||||||||||||||||
| 437 | |||||||||||||||||||||||||||||
| 438 | The method is not meant to not be used directly but it allows one to | ||||||||||||||||||||||||||||
| 439 | add a parent virtual column when calling the DBIx::Class method create. | ||||||||||||||||||||||||||||
| 440 | |||||||||||||||||||||||||||||
| 441 | This virtual column should be set with the primary key value of the parent. | ||||||||||||||||||||||||||||
| 442 | |||||||||||||||||||||||||||||
| 443 | My::Employee->create({ name => 'Another Intern', parent => $boss->id }); | ||||||||||||||||||||||||||||
| 444 | |||||||||||||||||||||||||||||
| 445 | =head2 parent | ||||||||||||||||||||||||||||
| 446 | |||||||||||||||||||||||||||||
| 447 | Returns a DBIx::Class Row of the parent of a node. | ||||||||||||||||||||||||||||
| 448 | |||||||||||||||||||||||||||||
| 449 | =head2 children | ||||||||||||||||||||||||||||
| 450 | |||||||||||||||||||||||||||||
| 451 | Returns a DBIx::Class resultset of all children (direct descendants) of a node. | ||||||||||||||||||||||||||||
| 452 | |||||||||||||||||||||||||||||
| 453 | =head2 leaf_children | ||||||||||||||||||||||||||||
| 454 | |||||||||||||||||||||||||||||
| 455 | Returns a DBIx::Class resultset of all children (direct descendants) of a node that do not possess any child themselves. | ||||||||||||||||||||||||||||
| 456 | |||||||||||||||||||||||||||||
| 457 | =head2 inner_children | ||||||||||||||||||||||||||||
| 458 | |||||||||||||||||||||||||||||
| 459 | Returns a DBIx::Class resultset of all children (direct descendants) of a node that possess one or more child. | ||||||||||||||||||||||||||||
| 460 | |||||||||||||||||||||||||||||
| 461 | =head2 descendants | ||||||||||||||||||||||||||||
| 462 | |||||||||||||||||||||||||||||
| 463 | Returns a DBIx::Class resultset of all descendants of a node (direct or not). | ||||||||||||||||||||||||||||
| 464 | |||||||||||||||||||||||||||||
| 465 | =head2 leaves | ||||||||||||||||||||||||||||
| 466 | |||||||||||||||||||||||||||||
| 467 | Returns a DBIx::Class resultset of all descendants of a node that do not possess any child themselves. | ||||||||||||||||||||||||||||
| 468 | |||||||||||||||||||||||||||||
| 469 | =head2 inner_descendants | ||||||||||||||||||||||||||||
| 470 | |||||||||||||||||||||||||||||
| 471 | Returns a DBIx::Class resultset of all descendants of a node that possess one or more child. | ||||||||||||||||||||||||||||
| 472 | |||||||||||||||||||||||||||||
| 473 | =head2 ancestors | ||||||||||||||||||||||||||||
| 474 | |||||||||||||||||||||||||||||
| 475 | Returns a DBIx::Class resultset of all ancestors of a node. | ||||||||||||||||||||||||||||
| 476 | |||||||||||||||||||||||||||||
| 477 | =head2 ascendants | ||||||||||||||||||||||||||||
| 478 | |||||||||||||||||||||||||||||
| 479 | An alias method for ancestors. | ||||||||||||||||||||||||||||
| 480 | |||||||||||||||||||||||||||||
| 481 | =head2 root | ||||||||||||||||||||||||||||
| 482 | |||||||||||||||||||||||||||||
| 483 | Returns a DBIx::Class resultset containing the root ancestor of a given node. | ||||||||||||||||||||||||||||
| 484 | |||||||||||||||||||||||||||||
| 485 | =head2 siblings | ||||||||||||||||||||||||||||
| 486 | |||||||||||||||||||||||||||||
| 487 | Returns a DBIx::Class resultset containing all the nodes with the same parent of a given node. | ||||||||||||||||||||||||||||
| 488 | |||||||||||||||||||||||||||||
| 489 | =head2 is_root | ||||||||||||||||||||||||||||
| 490 | |||||||||||||||||||||||||||||
| 491 | Returns 1 if the node has no parent, and 0 otherwise. | ||||||||||||||||||||||||||||
| 492 | |||||||||||||||||||||||||||||
| 493 | =head2 is_inner | ||||||||||||||||||||||||||||
| 494 | |||||||||||||||||||||||||||||
| 495 | Returns 1 if the node has at least one child, and 0 otherwise. | ||||||||||||||||||||||||||||
| 496 | |||||||||||||||||||||||||||||
| 497 | =head2 is_branch | ||||||||||||||||||||||||||||
| 498 | |||||||||||||||||||||||||||||
| 499 | Returns 1 if the node has at least one child and is not a root node, 0 otherwise. | ||||||||||||||||||||||||||||
| 500 | |||||||||||||||||||||||||||||
| 501 | =head2 is_leaf | ||||||||||||||||||||||||||||
| 502 | |||||||||||||||||||||||||||||
| 503 | Returns 1 if the node has no child, and 0 otherwise. | ||||||||||||||||||||||||||||
| 504 | |||||||||||||||||||||||||||||
| 505 | =head2 available_mobius_index | ||||||||||||||||||||||||||||
| 506 | |||||||||||||||||||||||||||||
| 507 | Returns the smallest mobius index available in the subtree of a given node. | ||||||||||||||||||||||||||||
| 508 | |||||||||||||||||||||||||||||
| 509 | =head2 child_encoding | ||||||||||||||||||||||||||||
| 510 | |||||||||||||||||||||||||||||
| 511 | Given a mobius index, return the mobius a,b,c,d column values. | ||||||||||||||||||||||||||||
| 512 | |||||||||||||||||||||||||||||
| 513 | =head2 depth | ||||||||||||||||||||||||||||
| 514 | |||||||||||||||||||||||||||||
| 515 | Return the depth of a node in a tree (depth of a root node is 1). | ||||||||||||||||||||||||||||
| 516 | |||||||||||||||||||||||||||||
| 517 | =for Pod::Coverage new mobius_path root_cond inner_cond leaf_cond | ||||||||||||||||||||||||||||
| 518 | |||||||||||||||||||||||||||||