use constant Size            => 10;
use Test::More tests         => ( ( ( Size + 1 ) * 5 ) );
use Algorithm::Treap IntKey =>
    #DEBUG=>1,
    key_lt  => '$1 < $2',
    key_gt  => '$1 > $2',
    heap_lt => '$1 < $2',
    ;
use List::Util 'shuffle';
use strict;
use warnings;
#use Data::BFDump;#
use Data::Dumper;#
{
    my $treap=Treap::IntKey->Tied_Hash();
    $treap->{1}=10;
    $treap->{2}=5;
    $treap->{10}=5;
    diag join(", ",keys %$treap),"\n";
}

srand 501;

my @list = map { $_ => int rand 100 } shuffle 1 .. Size;

my $obj = Treap::IntKey->new(@list);
isa_ok( $obj, 'Treap::IntKey', 'Treap::IntKey' );

diag $obj->dump_tree;
diag scalar $obj->breadth_first;

my $size = Size;
is( $obj->count, $size, "count $size" );
my @delete = ( -1, shuffle( 1 .. $size / 2 ), (0) x ( $size / 2 ) );

while (@delete) {
    my $x = shift @delete;
    if ( $x > -1 ) {
		if ($x) {
			eval { $obj->Delete($x); };
			ok( !$@, $@ || "Delete $x" );
		} else {
			eval { $obj->extract_top; };
			ok( !$@, $@ || "extract_top" );
		}
		is( $obj->count, --$size, "count $size" );
    } else {
		diag "After new()";
    }
    eval {
		my $last;
		foreach my $item ( $obj->in_order ) {
			die "Not in in_order after delete $x" if $last && $last->key > $item->key;
			$last = $item;
		}
    };
    ok( !$@, $@ || "in_order after delete $x" );
    eval {
		my $last;
		foreach my $item ( $obj->rev_order ) {
			die "Not in rev_order after delete $x" if $last && $last->key < $item->key;
			$last = $item;
		}
    };
    ok( !$@, $@ || "rev_order after delete $x" );
    eval {
		my $last;
		foreach my $item ( $obj->heap_order ) {
			die "Not in heap_order after delete $x" if $last && $last->weight > $item->weight;
			$last = $item;
		}
    };
    ok( !$@, $@ || "heap_order after delete $x" );
}

my $t=Random::Treap->Tied_Hash();
$t->{$_}=$_ for ('A'..'Z');
tied(%$t)->print_order('heap_order');
tied(%$t)->print_order('in_order');
print Dumper($t);
my $itor=tied(%$t)->left;
print($itor->key),$itor=$itor->succ while $itor;



my $test=Treap->new();
my %Test=(A => 121, B => 674, C => 970, D => 82, E => 658, F => 957);
print "(".join(", ",map { "$_ => $Test{$_}" } sort keys %Test),")\n";

foreach my $key (shuffle keys %Test) {
	$test->Store($key,$Test{$key});

}
$test->Store('D',600);
$test->Store('A',500);

$test->print_order('in_order');
$test->print_order('rev_order');
$test->print_order('heap_order');
print $test->dump_tree;
print "-----\n";
@list=qw(A 11 B 11 C 3 D 2 E 1);
while (@list) {
	$test->Store(shift @list,shift @list);
}
$test->print_order('in_order');
$test->print_order('rev_order');
$test->print_order('heap_order');
print $test->dump_tree;

print "Delete\n";
$test->Delete('D');
print $test->dump_tree;
#print Data::BFDump::Dumper(\%INC);