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