1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
# Before `make install' is performed this script should be runnable with
# `make test'. After `make install' it should work as `perl test.pl'
my $fibi;
my $biny;
my $binl;
my $b1;
BEGIN {
chdir 't' if -d 't';
use lib '../lib';
$| = 1;
my $arg = $ENV{HEAPTESTARG};
my $types;
$b1 = 50;
# env var $HEAPTESTARG can change the test set
# It can contain chars i y l to select fibonaccI binarY or binomiaL.
# It can contain a number to control the (number of items heaped)/4
# default is iyl50 (test all three, 200 numbers on heap).
# All comments below use the 50/200 default, other sizes are
# for debug purposes.
if( defined $arg ) {
$fibi = $biny = $binl = 0;
++$fibi if $arg =~ /i/;
++$biny if $arg =~ /y/;
++$binl if $arg =~ /l/;
$b1 = $1 if $arg =~ /([\d]+)/;
} else {
$fibi = 1;
$biny = 1;
$binl = 1;
}
print "1..", ($b1*2*8+4)*($fibi+$biny+$binl)+1, "\n";
}
END {print "not ok 1\n" unless $loaded;}
use Heap;
$loaded = 1;
print "ok 1\n";
my $b2 = $b1*2;
my $b3 = $b1*3;
my $b4 = $b1*4;
my $b0p1 = 1;
my $b1p1 = $b1+1;
my $b2p1 = $b2+1;
my $b3p1 = $b3+1;
use Heap::Fibonacci;
use Heap::Binomial;
use Heap::Binary;
use Heap::Elem::Num( NumElem );
my $count = 1;
sub testaheap {
my $heap = shift;
my @elems = map { NumElem($_) } 1..($b4);
unshift @elems, undef; # index them 1..200, not 0..199
# add block4, block3, block2, block1 to mix the order a bit
foreach( ($b3p1)..($b4),
($b2p1)..($b3),
($b1p1)..($b2),
($b0p1)..($b1) ) {
$heap->add( $elems[$_] );
}
sub testit {
print( ($_[0] ? "ok " : "not ok "), $_[1], "\n" );
}
# test 2..801
# We should find 1..100 in order on the heap, each element
# should have its heap value defined while it is still in
# the heap, and then undef after it is removed.
# Meanwhile, after removing element i (in 1..100) we then
# remove element i+100 out of order using delete, to test
# that the heap doesn't get corrupted.
# (i.e. 1, 101, 2, 102, ..., 100, 200)
foreach my $index ( 1..$b2 ) {
my $el;
$el = $heap->top;
testit( $index == $el->val, ++$count );
testit( defined($el->heap), ++$count );
$el = $heap->extract_top;
testit( $index == $el->val, ++$count );
testit( ! defined($el->heap), ++$count );
$el = $elems[$index+$b2];
testit( $index+$b2 == $el->val, ++$count );
testit( defined($el->heap), ++$count );
$heap->delete( $el );
testit( $index+$b2 == $el->val, ++$count );
testit( ! defined($el->heap), ++$count );
}
# test 802..805 - heap should be empty, and return undef
testit( ! defined($heap->top), ++$count );
testit( ! defined($heap->extract_top), ++$count );
testit( ! defined($heap->top), ++$count );
testit( ! defined($heap->extract_top), ++$count );
}
$fibi && testaheap( Heap::Fibonacci->new );
$binl && testaheap( Heap::Binomial->new );
$biny && testaheap( Heap::Binary->new );
|
