6 use Test::More tests => 68;
10 use_ok('t::lib::BinaryTree');
13 ## ----------------------------------------------------------------------------
14 ## These are all tests which are derived from the Tree::Binary test suite
15 ## ----------------------------------------------------------------------------
17 ## ----------------------------------------------------------------------------
18 ## t/10_Tree_Binary_test.t
20 can_ok("BinaryTree", 'new');
21 can_ok("BinaryTree", 'setLeft');
22 can_ok("BinaryTree", 'setRight');
24 my $btree = BinaryTree->new("/")
43 isa_ok($btree, 'BinaryTree');
45 ## informational methods
47 can_ok($btree, 'isRoot');
48 ok($btree->isRoot(), '... this is the root');
50 can_ok($btree, 'isLeaf');
51 ok(!$btree->isLeaf(), '... this is not a leaf node');
52 ok($btree->getLeft()->getLeft()->isLeaf(), '... this is a leaf node');
54 can_ok($btree, 'hasLeft');
55 ok($btree->hasLeft(), '... this has a left node');
57 can_ok($btree, 'hasRight');
58 ok($btree->hasRight(), '... this has a right node');
62 can_ok($btree, 'getUID');
65 my $UID = $btree->getUID();
66 is(("$btree" =~ /\((.*?)\)$/), $UID, '... our UID is derived from the stringified object');
69 can_ok($btree, 'getNodeValue');
70 is($btree->getNodeValue(), '/', '... got what we expected');
73 can_ok($btree, 'getLeft');
74 my $left = $btree->getLeft();
76 isa_ok($left, 'BinaryTree');
78 is($left->getNodeValue(), '+', '... got what we expected');
80 can_ok($left, 'getParent');
82 my $parent = $left->getParent();
83 isa_ok($parent, 'BinaryTree');
85 is($parent, $btree, '.. got what we expected');
89 can_ok($btree, 'getRight');
90 my $right = $btree->getRight();
92 isa_ok($right, 'BinaryTree');
94 is($right->getNodeValue(), '*', '... got what we expected');
96 can_ok($right, 'getParent');
98 my $parent = $right->getParent();
99 isa_ok($parent, 'BinaryTree');
101 is($parent, $btree, '.. got what we expected');
106 can_ok($btree, 'setUID');
107 $btree->setUID("Our UID for this tree");
109 is($btree->getUID(), 'Our UID for this tree', '... our UID is not what we expected');
111 can_ok($btree, 'setNodeValue');
112 $btree->setNodeValue('*');
114 is($btree->getNodeValue(), '*', '... got what we expected');
118 can_ok($btree, 'removeLeft');
119 my $left = $btree->removeLeft();
120 isa_ok($left, 'BinaryTree');
122 ok(!$btree->hasLeft(), '... we dont have a left node anymore');
123 ok(!$btree->isLeaf(), '... and we are not a leaf node');
125 $btree->setLeft($left);
127 ok($btree->hasLeft(), '... we have our left node again');
128 is($btree->getLeft(), $left, '... and it is what we told it to be');
133 my $left_leaf = $btree->getLeft()->removeLeft();
134 isa_ok($left_leaf, 'BinaryTree');
136 ok($left_leaf->isLeaf(), '... our left leaf is a leaf');
138 ok(!$btree->getLeft()->hasLeft(), '... we dont have a left leaf node anymore');
140 $btree->getLeft()->setLeft($left_leaf);
142 ok($btree->getLeft()->hasLeft(), '... we have our left leaf node again');
143 is($btree->getLeft()->getLeft(), $left_leaf, '... and it is what we told it to be');
147 can_ok($btree, 'removeRight');
148 my $right = $btree->removeRight();
149 isa_ok($right, 'BinaryTree');
151 ok(!$btree->hasRight(), '... we dont have a right node anymore');
152 ok(!$btree->isLeaf(), '... and we are not a leaf node');
154 $btree->setRight($right);
156 ok($btree->hasRight(), '... we have our right node again');
157 is($btree->getRight(), $right, '... and it is what we told it to be')
162 my $right_leaf = $btree->getRight()->removeRight();
163 isa_ok($right_leaf, 'BinaryTree');
165 ok($right_leaf->isLeaf(), '... our right leaf is a leaf');
167 ok(!$btree->getRight()->hasRight(), '... we dont have a right leaf node anymore');
169 $btree->getRight()->setRight($right_leaf);
171 ok($btree->getRight()->hasRight(), '... we have our right leaf node again');
172 is($btree->getRight()->getRight(), $right_leaf, '... and it is what we told it to be');
175 # some of the recursive informational methods
179 my $btree = BinaryTree->new("o")
191 ->setRight(BinaryTree->new("o"))
212 ->setRight(BinaryTree->new("o"))
215 isa_ok($btree, 'BinaryTree');
217 can_ok($btree, 'size');
218 cmp_ok($btree->size(), '==', 14, '... we have 14 nodes in the tree');
220 can_ok($btree, 'height');
221 cmp_ok($btree->height(), '==', 6, '... the tree is 6 nodes tall');
225 ## ----------------------------------------------------------------------------
226 ## t/13_Tree_Binary_mirror_test.t
228 sub inOrderTraverse {
231 my $_inOrderTraverse = sub {
232 my ($tree, $traversal_function) = @_;
233 $traversal_function->($tree->getLeft(), $traversal_function) if $tree->hasLeft();
234 push @results => $tree->getNodeValue();
235 $traversal_function->($tree->getRight(), $traversal_function) if $tree->hasRight();
237 $_inOrderTraverse->($tree, $_inOrderTraverse);
241 # test it on a simple well balanaced tree
243 my $btree = BinaryTree->new(4)
262 isa_ok($btree, 'BinaryTree');
265 [ inOrderTraverse($btree) ],
267 '... check that our tree starts out correctly');
269 can_ok($btree, 'mirror');
273 [ inOrderTraverse($btree) ],
275 '... check that our tree ends up correctly');
278 # test is on a more chaotic tree
280 my $btree = BinaryTree->new(4)
311 isa_ok($btree, 'BinaryTree');
313 my @results = inOrderTraverse($btree);
318 [ inOrderTraverse($btree) ],
319 [ reverse(@results) ],
320 '... this should be the reverse of the original');