AVLTree
view release on metacpan or search on metacpan
README
scripts/benchmarks.pl
t/00-load.t
t/01-numbers.t
t/02-custom.t
t/03-leak.t
t/manifest.t
t/pod-coverage.t
t/pod.t
TODO
typemap
xt/boilerplate.t
META.yml Module YAML meta-data (added by MakeMaker)
META.json Module JSON meta-data (added by MakeMaker)
lib/AVLTree.pm view on Meta::CPAN
sub cmp_f = sub {
my ($i1, $i2) = @_;
return $i1<$i2?-1:($i1>$i2)?1:0;
}
# Instantiate a tree which holds numbers
my $tree = AVLTree->new(\&cmp_f);
# Add some numbers to the tree
map { $tree->insert($_) } qw/10 20 30 40 50 25/;
# Now invoke some useful methods
# Size of the tree
printf "Size of the tree: %d\n", $tree->size();
# Query the tree
my $query = 30;
print "Query: %d, Found: %d\n", $query, $tree->find($query)?1:0;
# Remove an item
die "Invalid version number format: '$opt{'compat-version'}'\n";
}
die "Only Perl 5 is supported\n" if $r != 5;
die "Invalid version number: $opt{'compat-version'}\n" if $v >= 1000 || $s >= 1000;
$opt{'compat-version'} = sprintf "%d.%03d%03d", $r, $v, $s;
}
else {
$opt{'compat-version'} = 5;
}
my %API = map { /^(\w+)\|([^|]*)\|([^|]*)\|(\w*)$/
? ( $1 => {
($2 ? ( base => $2 ) : ()),
($3 ? ( todo => $3 ) : ()),
(index($4, 'v') >= 0 ? ( varargs => 1 ) : ()),
(index($4, 'p') >= 0 ? ( provided => 1 ) : ()),
(index($4, 'n') >= 0 ? ( nothxarg => 1 ) : ()),
} )
: die "invalid spec: $_" } qw(
AvFILLp|5.004050||p
AvFILL|||
}
$function = [$1, ''] if m{^DPPP_\(my_(\w+)\)};
$replace = $1 if m{^\s*$rccs\s+Replace:\s+(\d+)\s+$rcce\s*$};
$replace{$2} = $1 if $replace and m{^\s*#\s*define\s+(\w+)(?:\([^)]*\))?\s+(\w+)};
$replace{$2} = $1 if m{^\s*#\s*define\s+(\w+)(?:\([^)]*\))?\s+(\w+).*$rccs\s+Replace\s+$rcce};
$replace{$1} = $2 if m{^\s*$rccs\s+Replace (\w+) with (\w+)\s+$rcce\s*$};
if (m{^\s*$rccs\s+(\w+(\s*,\s*\w+)*)\s+depends\s+on\s+(\w+(\s*,\s*\w+)*)\s+$rcce\s*$}) {
my @deps = map { s/\s+//g; $_ } split /,/, $3;
my $d;
for $d (map { s/\s+//g; $_ } split /,/, $1) {
push @{$depends{$d}}, @deps;
}
}
$need{$1} = 1 if m{^#if\s+defined\(NEED_(\w+)(?:_GLOBAL)?\)};
}
for (values %depends) {
my %s;
$_ = [sort grep !$s{$_}++, @$_];
push @flags, 'hint' if exists $hints{$f};
push @flags, 'warning' if exists $warnings{$f};
my $flags = @flags ? ' ['.join(', ', @flags).']' : '';
print "$f$flags\n";
}
exit 0;
}
my @files;
my @srcext = qw( .xs .c .h .cc .cpp -c.inc -xs.inc );
my $srcext = join '|', map { quotemeta $_ } @srcext;
if (@ARGV) {
my %seen;
for (@ARGV) {
if (-e) {
if (-f) {
push @files, $_ unless $seen{$_}++;
}
else { warn "'$_' is not a file.\n" }
}
}
else {
eval {
require File::Find;
File::Find::find(sub {
$File::Find::name =~ /($srcext)$/i
and push @files, $File::Find::name;
}, '.');
};
if ($@) {
@files = map { glob "*$_" } @srcext;
}
}
if (!@ARGV || $opt{filter}) {
my(@in, @out);
my %xsc = map { /(.*)\.xs$/ ? ("$1.c" => 1, "$1.cc" => 1) : () } @files;
for (@files) {
my $out = exists $xsc{$_} || /\b\Q$ppport\E$/i || !/($srcext)$/i;
push @{ $out ? \@out : \@in }, $_;
}
if (@ARGV && @out) {
warning("Skipping the following files (use --nofilter to avoid this):\n| ", join "\n| ", @out);
}
@files = @in;
}
return undef;
}
sub rec_depend
{
my($func, $seen) = @_;
return () unless exists $depends{$func};
$seen = {%{$seen||{}}};
return () if $seen->{$func}++;
my %s;
grep !$s{$_}++, map { ($_, rec_depend($_, $seen)) } @{$depends{$func}};
}
sub parse_version
{
my $ver = shift;
if ($ver =~ /^(\d+)\.(\d+)\.(\d+)$/) {
return ($1, $2, $3);
}
elsif ($ver !~ /^\d+\.[\d_]+$/) {
scripts/benchmarks.pl view on Meta::CPAN
use Benchmark;
$| = 1;
print '-' x 21, "\n 100K random inserts\n", '-' x 21, "\n\n";
my @items = shuffle 1 .. 100000;
# my $start = new Benchmark;
# print "[Tree::AVL]\t\t";
# my $treeavl = Tree::AVL->new();
# map { $treeavl->insert($_) } @items;
# my $end = new Benchmark;
# my $diff = timediff($end, $start);
# printf "time taken was %s seconds\n", timestr($diff, 'all');
my $start = new Benchmark;
print "[AVLTree]\t\t";
my $avltree = AVLTree->new(\&cmp_f);
map { $avltree->insert($_) } @items;
my $end = new Benchmark;
my $diff = timediff($end, $start);
printf "time taken was %s seconds\n\n\n", timestr($diff, 'all');
print '-' x 23, "\n 10K random deletions\n", '-' x 23, "\n\n";
@items = shuffle 1 .. 10000;
# $start = new Benchmark;
# print "[Tree::AVL]\t\t";
# map { $treeavl->remove($_) } @items;
# $end = new Benchmark;
# $diff = timediff($end, $start);
# printf "time taken was %s seconds\n", timestr($diff, 'all');
$start = new Benchmark;
print "[AVLTree]\t\t";
map { $avltree->remove($_) } @items;
$end = new Benchmark;
$diff = timediff($end, $start);
printf "time taken was %s seconds\n", timestr($diff, 'all');
sub cmp_f {
my ($i1, $i2) = @_;
return $i1<$i2?-1:($i1>$i2)?1:0;
}
t/01-numbers.t view on Meta::CPAN
sub cmp_f {
my ($i1, $i2) = @_;
return $i1<$i2?-1:($i1>$i2)?1:0;
}
my $tree = AVLTree->new(\&cmp_f);
isa_ok($tree, "AVLTree");
is($tree->size(), 0, "Empty tree upon construction");
map { ok($tree->insert($_), "Insert item") } qw/10 20 30 40 50 25/;
is($tree->size(), 6, "Tree size after insertion");
ok(!$tree->find(), "No query");
ok(!$tree->find(undef), "Undefined query");
my $query = 30;
my $result = $tree->find($query);
ok($result, "Item found");
ok(!$tree->find(18), "Item not found");
t/02-custom.t view on Meta::CPAN
my $items =
[
{ id => 10, data => ['ten'] },
{ id => 20, data => ['twenty'] },
{ id => 30, data => ['thirty'] },
{ id => 40, data => ['forty'] },
{ id => 50, data => ['fifty'] },
{ id => 25, data => ['twentyfive'] },
];
map { ok($tree->insert($_), "Insert item") } @{$items};
is($tree->size(), 6, "Tree size after insertion");
ok(!$tree->find(), "No query");
ok(!$tree->find(undef), "Undefined query");
my $query = { id => 30, data => 'something' };
my $result = $tree->find($query);
ok($result, "Item found");
cmp_deeply($result, { id => 30, data => ['thirty'] }, "Item returned");
t/03-leak.t view on Meta::CPAN
return $id1<$id2?-1:($id1>$id2)?1:0;
}
# tests with numbers
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_numbers);
} 'Empty tree';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_numbers);
map { $tree->insert($_) } qw/10 20 30 40 50 25/;
} 'Non-empty tree';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_numbers);
map { $tree->insert($_) } qw/10 20 30 40 50 25/;
my $query = 30;
my $result = $tree->find($query);
} 'After inserting&querying';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_numbers);
map { $tree->insert($_) } qw/10 20 30 40 50 25/;
$tree->remove(1); # unsuccessful removal
$tree->remove(10); # successful removal
} 'After inserting&removing';
# repeat with custom data
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_custom);
} 'Empty tree';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_custom);
map { $tree->insert($_) }
({ id => 10, data => 'ten' },
{ id => 20, data => 'twenty' },
{ id => 30, data => 'thirty' },
{ id => 40, data => 'forty' },
{ id => 50, data => 'fifty' },
{ id => 25, data => 'twneryfive' });
} 'Non-empty tree';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_custom);
map { $tree->insert($_) }
({ id => 10, data => 'ten' },
{ id => 20, data => 'twenty' },
{ id => 30, data => 'thirty' },
{ id => 40, data => 'forty' },
{ id => 50, data => 'fifty' },
{ id => 25, data => 'twneryfive' });
my $query = { id => 30 };
my $result = $tree->find($query);
} 'After inserting&querying';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_custom);
map { $tree->insert($_) }
({ id => 10, data => 'ten' },
{ id => 20, data => 'twenty' },
{ id => 30, data => 'thirty' },
{ id => 40, data => 'forty' },
{ id => 50, data => 'fifty' },
{ id => 25, data => 'twneryfive' });
$tree->remove({ id => 1 }); # unsuccessful removal
$tree->remove({ id => 10 }); # successful removal
} 'After inserting&removing';
no_leaks_ok {
my $tree = AVLTree->new(\&cmp_custom);
map { $tree->insert($_) }
({ id => 10, data => 'ten' },
{ id => 20, data => 'twenty' },
{ id => 30, data => 'thirty' },
{ id => 40, data => 'forty' },
{ id => 50, data => 'fifty' },
{ id => 25, data => 'twneryfive' });
my $item = $tree->first;
while ($item = $tree->next) {}
} 'Tree traversal';
( run in 3.694 seconds using v1.01-cache-2.11-cpan-140bd7fdf52 )