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## ----------------------------------------------------------------------------