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