t/100_BinaryTree_test.t

   1 #!/usr/bin/perl
   2
   3 use strict;
   4 use warnings;
   5
   6 use Test::More tests => 67;
   7
   8 BEGIN {
   9     use_ok('t::lib::BinaryTree');
  10 }
  11
  12 ## ----------------------------------------------------------------------------
  13 ## These are all tests which are derived from the Tree::Binary test suite
  14 ## ----------------------------------------------------------------------------
  15
  16 ## ----------------------------------------------------------------------------
  17 ## t/10_Tree_Binary_test.t
  18
  19 can_ok("BinaryTree", 'new');
  20 can_ok("BinaryTree", 'setLeft');
  21 can_ok("BinaryTree", 'setRight');
  22
  23 my $btree = BinaryTree->new("/")
  24                         ->setLeft(
  25                             BinaryTree->new("+")
  26                                         ->setLeft(
  27                                             BinaryTree->new("2")
  28                                         )
  29                                         ->setRight(
  30                                             BinaryTree->new("2")
  31                                         )
  32                         )
  33                         ->setRight(
  34                             BinaryTree->new("*")
  35                                         ->setLeft(
  36                                             BinaryTree->new("4")
  37                                         )
  38                                         ->setRight(
  39                                             BinaryTree->new("5")
  40                                         )
  41                         );
  42 isa_ok($btree, 'BinaryTree');
  43
  44 ## informational methods
  45
  46 can_ok($btree, 'isRoot');
  47 ok($btree->isRoot(), '... this is the root');
  48
  49 can_ok($btree, 'isLeaf');
  50 ok(!$btree->isLeaf(), '... this is not a leaf node');
  51 ok($btree->getLeft()->getLeft()->isLeaf(), '... this is a leaf node');
  52
  53 can_ok($btree, 'hasLeft');
  54 ok($btree->hasLeft(), '... this has a left node');
  55
  56 can_ok($btree, 'hasRight');
  57 ok($btree->hasRight(), '... this has a right node');
  58
  59 ## accessors
  60
  61 can_ok($btree, 'getUID');
  62
  63 {
  64     my $UID = $btree->getUID();
  65     is(("$btree" =~ /\((.*?)\)$/), $UID, '... our UID is derived from the stringified object');
  66 }
  67
  68 can_ok($btree, 'getNodeValue');
  69 is($btree->getNodeValue(), '/', '... got what we expected');
  70
  71 {
  72     can_ok($btree, 'getLeft');
  73     my $left = $btree->getLeft();
  74
  75     isa_ok($left, 'BinaryTree');
  76
  77     is($left->getNodeValue(), '+', '... got what we expected');
  78
  79     can_ok($left, 'getParent');
  80
  81     my $parent = $left->getParent();
  82     isa_ok($parent, 'BinaryTree');
  83
  84     is($parent, $btree, '.. got what we expected');
  85 }
  86
  87 {
  88     can_ok($btree, 'getRight');
  89     my $right = $btree->getRight();
  90
  91     isa_ok($right, 'BinaryTree');
  92
  93     is($right->getNodeValue(), '*', '... got what we expected');
  94
  95     can_ok($right, 'getParent');
  96
  97     my $parent = $right->getParent();
  98     isa_ok($parent, 'BinaryTree');
  99
 100     is($parent, $btree, '.. got what we expected');
 101 }
 102
 103 ## mutators
 104
 105 can_ok($btree, 'setUID');
 106 $btree->setUID("Our UID for this tree");
 107
 108 is($btree->getUID(), 'Our UID for this tree', '... our UID is not what we expected');
 109
 110 can_ok($btree, 'setNodeValue');
 111 $btree->setNodeValue('*');
 112
 113 is($btree->getNodeValue(), '*', '... got what we expected');
 114
 115
 116 {
 117     can_ok($btree, 'removeLeft');
 118     my $left = $btree->removeLeft();
 119     isa_ok($left, 'BinaryTree');
 120
 121     ok(!$btree->hasLeft(), '... we dont have a left node anymore');
 122     ok(!$btree->isLeaf(), '... and we are not a leaf node');
 123
 124     $btree->setLeft($left);
 125
 126     ok($btree->hasLeft(), '... we have our left node again');
 127     is($btree->getLeft(), $left, '... and it is what we told it to be');
 128 }
 129
 130 {
 131     # remove left leaf
 132     my $left_leaf = $btree->getLeft()->removeLeft();
 133     isa_ok($left_leaf, 'BinaryTree');
 134
 135     ok($left_leaf->isLeaf(), '... our left leaf is a leaf');
 136
 137     ok(!$btree->getLeft()->hasLeft(), '... we dont have a left leaf node anymore');
 138
 139     $btree->getLeft()->setLeft($left_leaf);
 140
 141     ok($btree->getLeft()->hasLeft(), '... we have our left leaf node again');
 142     is($btree->getLeft()->getLeft(), $left_leaf, '... and it is what we told it to be');
 143 }
 144
 145 {
 146     can_ok($btree, 'removeRight');
 147     my $right = $btree->removeRight();
 148     isa_ok($right, 'BinaryTree');
 149
 150     ok(!$btree->hasRight(), '... we dont have a right node anymore');
 151     ok(!$btree->isLeaf(), '... and we are not a leaf node');
 152
 153     $btree->setRight($right);
 154
 155     ok($btree->hasRight(), '... we have our right node again');
 156     is($btree->getRight(), $right, '... and it is what we told it to be')
 157 }
 158
 159 {
 160     # remove right leaf
 161     my $right_leaf = $btree->getRight()->removeRight();
 162     isa_ok($right_leaf, 'BinaryTree');
 163
 164     ok($right_leaf->isLeaf(), '... our right leaf is a leaf');
 165
 166     ok(!$btree->getRight()->hasRight(), '... we dont have a right leaf node anymore');
 167
 168     $btree->getRight()->setRight($right_leaf);
 169
 170     ok($btree->getRight()->hasRight(), '... we have our right leaf node again');
 171     is($btree->getRight()->getRight(), $right_leaf, '... and it is what we told it to be');
 172 }
 173
 174 # some of the recursive informational methods
 175
 176 {
 177
 178     my $btree = BinaryTree->new("o")
 179                             ->setLeft(
 180                                 BinaryTree->new("o")
 181                                     ->setLeft(
 182                                         BinaryTree->new("o")
 183                                     )
 184                                     ->setRight(
 185                                         BinaryTree->new("o")
 186                                             ->setLeft(
 187                                                 BinaryTree->new("o")
 188                                                     ->setLeft(
 189                                                         BinaryTree->new("o")
 190                                                             ->setRight(BinaryTree->new("o"))
 191                                                     )
 192                                             )
 193                                     )
 194                             )
 195                             ->setRight(
 196                                 BinaryTree->new("o")
 197                                             ->setLeft(
 198                                                 BinaryTree->new("o")
 199                                                     ->setRight(
 200                                                         BinaryTree->new("o")
 201                                                             ->setLeft(
 202                                                                 BinaryTree->new("o")
 203                                                             )
 204                                                             ->setRight(
 205                                                                 BinaryTree->new("o")
 206                                                             )
 207                                                     )
 208                                             )
 209                                             ->setRight(
 210                                                 BinaryTree->new("o")
 211                                                     ->setRight(BinaryTree->new("o"))
 212                                             )
 213                             );
 214     isa_ok($btree, 'BinaryTree');
 215
 216     can_ok($btree, 'size');
 217     cmp_ok($btree->size(), '==', 14, '... we have 14 nodes in the tree');
 218
 219     can_ok($btree, 'height');
 220     cmp_ok($btree->height(), '==', 6, '... the tree is 6 nodes tall');
 221
 222 }
 223
 224 ## ----------------------------------------------------------------------------
 225 ## t/13_Tree_Binary_mirror_test.t
 226
 227 sub inOrderTraverse {
 228     my $tree = shift;
 229     my @results;
 230     my $_inOrderTraverse = sub {
 231         my ($tree, $traversal_function) = @_;
 232         $traversal_function->($tree->getLeft(), $traversal_function) if $tree->hasLeft();
 233         push @results => $tree->getNodeValue();
 234         $traversal_function->($tree->getRight(), $traversal_function) if $tree->hasRight();
 235     };
 236     $_inOrderTraverse->($tree, $_inOrderTraverse);
 237     @results;
 238 }
 239
 240 # test it on a simple well balanaced tree
 241 {
 242     my $btree = BinaryTree->new(4)
 243                     ->setLeft(
 244                         BinaryTree->new(2)
 245                             ->setLeft(
 246                                 BinaryTree->new(1)
 247                                 )
 248                             ->setRight(
 249                                 BinaryTree->new(3)
 250                                 )
 251                         )
 252                     ->setRight(
 253                         BinaryTree->new(6)
 254                             ->setLeft(
 255                                 BinaryTree->new(5)
 256                                 )
 257                             ->setRight(
 258                                 BinaryTree->new(7)
 259                                 )
 260                         );
 261     isa_ok($btree, 'BinaryTree');
 262
 263     is_deeply(
 264         [ inOrderTraverse($btree) ],
 265         [ 1 .. 7 ],
 266         '... check that our tree starts out correctly');
 267
 268     can_ok($btree, 'mirror');
 269     $btree->mirror();
 270
 271     is_deeply(
 272         [ inOrderTraverse($btree) ],
 273         [ reverse(1 .. 7) ],
 274         '... check that our tree ends up correctly');
 275 }
 276
 277 # test is on a more chaotic tree
 278 {
 279     my $btree = BinaryTree->new(4)
 280                     ->setLeft(
 281                         BinaryTree->new(20)
 282                             ->setLeft(
 283                                 BinaryTree->new(1)
 284                                         ->setRight(
 285                                             BinaryTree->new(10)
 286                                                 ->setLeft(
 287                                                     BinaryTree->new(5)
 288                                                 )
 289                                         )
 290                                 )
 291                             ->setRight(
 292                                 BinaryTree->new(3)
 293                                 )
 294                         )
 295                     ->setRight(
 296                         BinaryTree->new(6)
 297                             ->setLeft(
 298                                 BinaryTree->new(5)
 299                                     ->setRight(
 300                                         BinaryTree->new(7)
 301                                             ->setLeft(
 302                                                 BinaryTree->new(90)
 303                                             )
 304                                             ->setRight(
 305                                                 BinaryTree->new(91)
 306                                             )
 307                                         )
 308                                 )
 309                         );
 310     isa_ok($btree, 'BinaryTree');
 311
 312     my @results = inOrderTraverse($btree);
 313
 314     $btree->mirror();
 315
 316     is_deeply(
 317         [ inOrderTraverse($btree) ],
 318         [ reverse(@results) ],
 319         '... this should be the reverse of the original');
 320 }
 321