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