1use strict; 2use warnings; 3 4use Tree::Binary::Search; 5use Tree::Binary::VisitorFactory; 6 7use Test::More tests => 140; 8 9## ---------------------------------------------------------------------------- 10## Theorem Proving and Unit tests 11## ---------------------------------------------------------------------------- 12# This test is an attempt at trying to use Theorems to build useful unit tests 13# with. 14# 15# For more on this topic, see the following Perl Monks node: 16# http://www.perlmonks.org/index.pl?node_id=385774 17# 18# BTW, these theorems are not mine, but instead they come from the book: 19# 'ML for the Working Programmer by L. C. Paulson' 20# specifically chapter 6 and the subsection the section 6.5 entitled 21# 'Structural induction on trees'. 22## ---------------------------------------------------------------------------- 23 24# NOTE: 25# it makes sense to do this more than once, 26# so we loop a couple of times to test. I got 27# this idea from reading about the QuickCheck 28# testing tool for Haskell. 29# http://www.cs.chalmers.se/~rjmh/QuickCheck/ 30 31foreach (1 .. 20) { 32 # create a random binary tree 33 my $num_nodes = int rand() * 100; 34 $num_nodes++ if $num_nodes == 0; 35 my $tree = rand_tree($num_nodes); 36 37 ## ---------------------------------------------- 38 ## preorder(mirror(mirror(t))) = preorder(t) 39 ## ---------------------------------------------- 40 # The mirror of a mirror of a tree is equal to 41 # the original tree. 42 ## ---------------------------------------------- 43 44 is_deeply( 45 [ preorder(mirror(mirror($tree))) ], 46 [ preorder($tree) ] 47 , '... mirror(mirror(t)) = t'); 48 49 ## ---------------------------------------------- 50 ## size(mirror(t)) = size(t) 51 ## ---------------------------------------------- 52 # The size of a mirror of a tree is equal to the 53 # size of the original tree. 54 ## ---------------------------------------------- 55 56 cmp_ok(size(mirror($tree)), '==', size($tree), '... size(mirror(t)) = size(t)'); 57 58 ## ---------------------------------------------- 59 ## postorder(mirror(t)) = reverse(preorder(t)) 60 ## ---------------------------------------------- 61 # The portorder of a mirror of a tree is equal to 62 # the reverse of the preorder of the tree. 63 ## ---------------------------------------------- 64 65 is_deeply( 66 [ postorder(mirror($tree)) ], 67 [ reverse(preorder($tree)) ] 68 , '... postorder(mirror(t)) = reverse(preorder(t))'); 69 70 ## ---------------------------------------------- 71 ## inorder(mirror(t)) = reverse(inorder(t)) 72 ## ---------------------------------------------- 73 # The inorder of a mirror-ed tree is equal to the 74 # reverse of the inorder of the tree. 75 ## ---------------------------------------------- 76 77 is_deeply( 78 [ inorder(mirror($tree)) ], 79 [ reverse(inorder($tree)) ] 80 , '... inorder(mirror(t)) = reverse(inorder(t))'); 81 82 ## ---------------------------------------------- 83 ## reverse(inorder(mirror(t))) = inorder(t) 84 ## ---------------------------------------------- 85 # The reverse of the inorder of the mirror of the 86 # tree is equal to the inorder of the tree. 87 ## ---------------------------------------------- 88 89 is_deeply( 90 [ reverse(inorder(mirror($tree))) ], 91 [ inorder($tree) ] 92 , '... reverse(inorder(mirror(t))) = inorder(t)'); 93 94 ## ---------------------------------------------- 95 ## size(t) <= 2 ** height(t) - 1 96 ## ---------------------------------------------- 97 # The size of a tree is less than or equal to 98 # 2 to the power of the the height of the tree 99 # minus 1. 100 ## ---------------------------------------------- 101 102 cmp_ok(size($tree), '<=', ((2 ** height($tree)) - 1), '... size(t) <= 2 ** height(t) - 1'); 103 104 ## ---------------------------------------------- 105 ## length(preorder(t)) = size(t) 106 ## ---------------------------------------------- 107 # The length of the preorder is the same as the 108 # size of the tree 109 ## ---------------------------------------------- 110 111 cmp_ok(scalar(preorder($tree)), '==', size($tree), '... length(preorder(t)) = size(t)'); 112 113} 114 115## ---------------------------------------------------------------------------- 116## convience functions for proofs 117## ---------------------------------------------------------------------------- 118 119sub rand_tree { 120 my ($num_nodes) = @_; 121 my $rand_ceil = $num_nodes * 2; 122 123 my $btree = Tree::Binary::Search->new(); 124 $btree->useNumericComparison(); 125 126 for (0 .. $num_nodes) { 127 my $num = ((rand() * $rand_ceil) % $rand_ceil); 128 while ($btree->exists($num)) { 129 $num = ((rand() * $rand_ceil) % $rand_ceil); 130 } 131 $btree->insert($num => $num); 132 } 133 134 return $btree->getTree(); 135} 136 137sub mirror { 138 my ($tree) = @_; 139 return $tree->clone()->mirror(); 140} 141 142sub size { 143 my ($tree) = @_; 144 return $tree->size(); 145} 146 147sub height { 148 my ($tree) = @_; 149 return $tree->height(); 150} 151 152sub postorder { 153 my ($tree) = @_; 154 my $visitor = Tree::Binary::VisitorFactory->get('PostOrderTraversal'); 155 $tree->accept($visitor); 156 my @results = $visitor->getResults(); 157 return @results; 158} 159 160sub inorder { 161 my ($tree) = @_; 162 my $visitor = Tree::Binary::VisitorFactory->get('InOrderTraversal'); 163 $tree->accept($visitor); 164 my @results = $visitor->getResults(); 165 return @results; 166} 167 168sub preorder { 169 my ($tree) = @_; 170 my $visitor = Tree::Binary::VisitorFactory->get('PreOrderTraversal'); 171 $tree->accept($visitor); 172 my @results = $visitor->getResults(); 173 return @results; 174} 175 176## ----------------------------------------------------------------------------