Commit | Line | Data |
c50c603e |
1 | |
2 | package BinaryTree; |
3 | |
4 | use strict; |
5 | use warnings; |
6 | |
1a7ebbb3 |
7 | use Class::MOP 'meta'; |
8 | |
c50c603e |
9 | our $VERSION = '0.01'; |
10 | |
c50c603e |
11 | __PACKAGE__->meta->add_attribute( |
727919c5 |
12 | Class::MOP::Attribute->new('$:uid' => ( |
68deeb05 |
13 | reader => 'getUID', |
14 | writer => 'setUID', |
c50c603e |
15 | default => sub { |
16 | my $instance = shift; |
17 | ("$instance" =~ /\((.*?)\)$/); |
18 | } |
19 | )) |
20 | ); |
21 | |
22 | __PACKAGE__->meta->add_attribute( |
727919c5 |
23 | Class::MOP::Attribute->new('$:node' => ( |
c50c603e |
24 | reader => 'getNodeValue', |
25 | writer => 'setNodeValue', |
26 | init_arg => ':node' |
27 | )) |
28 | ); |
29 | |
30 | __PACKAGE__->meta->add_attribute( |
727919c5 |
31 | Class::MOP::Attribute->new('$:parent' => ( |
68deeb05 |
32 | predicate => 'hasParent', |
c50c603e |
33 | reader => 'getParent', |
68deeb05 |
34 | writer => 'setParent' |
c50c603e |
35 | )) |
36 | ); |
37 | |
38 | __PACKAGE__->meta->add_attribute( |
727919c5 |
39 | Class::MOP::Attribute->new('$:left' => ( |
c50c603e |
40 | predicate => 'hasLeft', |
41 | reader => 'getLeft', |
42 | writer => { |
43 | 'setLeft' => sub { |
44 | my ($self, $tree) = @_; |
68deeb05 |
45 | $tree->setParent($self) if defined $tree; |
727919c5 |
46 | $self->{'$:left'} = $tree; |
c50c603e |
47 | $self; |
48 | } |
49 | }, |
50 | )) |
51 | ); |
52 | |
53 | __PACKAGE__->meta->add_attribute( |
727919c5 |
54 | Class::MOP::Attribute->new('$:right' => ( |
c50c603e |
55 | predicate => 'hasRight', |
56 | reader => 'getRight', |
57 | writer => { |
58 | 'setRight' => sub { |
59 | my ($self, $tree) = @_; |
68deeb05 |
60 | $tree->setParent($self) if defined $tree; |
727919c5 |
61 | $self->{'$:right'} = $tree; |
c50c603e |
62 | $self; |
63 | } |
64 | } |
65 | )) |
66 | ); |
67 | |
c50c603e |
68 | sub new { |
69 | my $class = shift; |
70 | bless $class->meta->construct_instance(':node' => shift) => $class; |
71 | } |
72 | |
73 | sub removeLeft { |
74 | my ($self) = @_; |
68deeb05 |
75 | my $left = $self->getLeft(); |
c50c603e |
76 | $left->setParent(undef); |
68deeb05 |
77 | $self->setLeft(undef); |
c50c603e |
78 | return $left; |
79 | } |
80 | |
81 | sub removeRight { |
82 | my ($self) = @_; |
68deeb05 |
83 | my $right = $self->getRight; |
c50c603e |
84 | $right->setParent(undef); |
68deeb05 |
85 | $self->setRight(undef); |
c50c603e |
86 | return $right; |
87 | } |
88 | |
89 | sub isLeaf { |
90 | my ($self) = @_; |
91 | return (!$self->hasLeft && !$self->hasRight); |
92 | } |
93 | |
68deeb05 |
94 | sub isRoot { |
c50c603e |
95 | my ($self) = @_; |
68deeb05 |
96 | return !$self->hasParent; |
c50c603e |
97 | } |
98 | |
99 | sub traverse { |
100 | my ($self, $func) = @_; |
101 | $func->($self); |
68deeb05 |
102 | $self->getLeft->traverse($func) if $self->hasLeft; |
103 | $self->getRight->traverse($func) if $self->hasRight; |
c50c603e |
104 | } |
105 | |
106 | sub mirror { |
107 | my ($self) = @_; |
108 | # swap left for right |
68deeb05 |
109 | my $left = $self->getLeft; |
110 | $self->setLeft($self->getRight()); |
111 | $self->setRight($left); |
c50c603e |
112 | # and recurse |
68deeb05 |
113 | $self->getLeft->mirror() if $self->hasLeft(); |
114 | $self->getRight->mirror() if $self->hasRight(); |
c50c603e |
115 | $self; |
116 | } |
117 | |
118 | sub size { |
119 | my ($self) = @_; |
120 | my $size = 1; |
68deeb05 |
121 | $size += $self->getLeft->size() if $self->hasLeft(); |
122 | $size += $self->getRight->size() if $self->hasRight(); |
c50c603e |
123 | return $size; |
124 | } |
125 | |
126 | sub height { |
127 | my ($self) = @_; |
128 | my ($left_height, $right_height) = (0, 0); |
68deeb05 |
129 | $left_height = $self->getLeft->height() if $self->hasLeft(); |
130 | $right_height = $self->getRight->height() if $self->hasRight(); |
c50c603e |
131 | return 1 + (($left_height > $right_height) ? $left_height : $right_height); |
132 | } |
133 | |