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