AVLTree
view release on metacpan or search on metacpan
0.1.6 Sat 03 Mar 2018
* Support for tree traversal methods
0.0.6 Tue 02 Jan 2018
* Build with multi-threaded perl versions
0.0,4 Sun 24 Dec 2017
* Minor improvements in the documentation
0.0.3 Thu 21 Dec 2017
* Additional dependency necessary for CPAN testers
* Removed AVL::Tree import for benchmarking
0.01 Mon 18 Dec 2017
* First release to CPAN, partial port of jsw_avltree AVL tree C library, traversal methods not implemented.
The underlying C library is a reinterpretation of the C library originally
developed by Julienne Walker. This library has been adapted for dealing
directly with Perl (SV) variables.
INSTALLATION
To install this module, run the following commands:
perl Makefile.PL
make
make test
make install
SUPPORT AND DOCUMENTATION
After installing, you can find documentation for this module with the
perldoc command.
perldoc AVLTree
You can also look for information at:
requires 'Carp';
# for running benchmarks
recommends 'Benchmark';
recommends 'List::Util';
# test_requires 'Test::Warnings';
# test_requires 'Test::Differences';
# test_requires 'Test::Exception';
test_requires 'Test::More';
test_requires 'Test::LeakTrace';
test_requires 'Test::Deep';
# test_requires 'Devel::Peek';
# test_requires 'Devel::Cycle';
lib/AVLTree.pm view on Meta::CPAN
Description : Returns the previous element as specified by the order defined by the tree.
Returntype : The item, if found, as stored in the tree or undef
if the tree is empty.
Exceptions : None
Caller : General
Status : Unstable
=head1 DEPENDENCIES
AVLTree requires Carp and Test::More, Test::Deep and Test::LeakTrace to run the tests during installation.
If you want to run the benchmarks in the scripts directory, you need to install the Benchmark
and List::Util modules.
=head1 EXPORT
None
=head1 SEE ALSO
If you want to get a deeper insight into the module, you should of course take a look at the excellent AVL
--strip strip all script and doc functionality from
ppport.h
--list-provided list provided API
--list-unsupported list unsupported API
--api-info=name show Perl API portability information
=head1 COMPATIBILITY
This version of F<ppport.h> is designed to support operation with Perl
installations back to 5.003, and has been tested up to 5.11.5.
=head1 OPTIONS
=head2 --help
Display a brief usage summary.
=head2 --version
Display the version of F<ppport.h>.
The result will usually be a list of patches suggesting changes
that should at least be acceptable, if not necessarily the most
efficient solution, or a fix for all possible problems.
If you know that your XS module uses features only available in
newer Perl releases, if you're aware that it uses C++ comments,
and if you want all suggestions as a single patch file, you could
use something like this:
perl ppport.h --compat-version=5.6.0 --cplusplus --patch=test.diff
If you only want your code to be scanned without any suggestions
for changes, use:
perl ppport.h --nochanges
You can specify a different C<diff> program or options, using
the C<--diff> option:
perl ppport.h --diff='diff -C 10'
to display information for all known API elements.
=head1 BUGS
If this version of F<ppport.h> is causing failure during
the compilation of this module, please check if newer versions
of either this module or C<Devel::PPPort> are available on CPAN
before sending a bug report.
If F<ppport.h> was generated using the latest version of
C<Devel::PPPort> and is causing failure of this module, please
file a bug report using the CPAN Request Tracker at L<http://rt.cpan.org/>.
Please include the following information:
=over 4
=item 1.
The complete output from running "perl -V"
=item 4.
A full log of the build that failed.
=item 5.
Any other information that you think could be relevant.
=back
For the latest version of this code, please get the C<Devel::PPPort>
module from CPAN.
=head1 COPYRIGHT
Version 3.x, Copyright (c) 2004-2010, Marcus Holland-Moritz.
Version 2.x, Copyright (C) 2001, Paul Marquess.
Version 1.x, Copyright (C) 1999, Kenneth Albanowski.
if (s == send)
return 0;
/* next must be digit or the radix separator or beginning of infinity */
if (isDIGIT(*s)) {
/* UVs are at least 32 bits, so the first 9 decimal digits cannot
overflow. */
UV value = *s - '0';
/* This construction seems to be more optimiser friendly.
(without it gcc does the isDIGIT test and the *s - '0' separately)
With it gcc on arm is managing 6 instructions (6 cycles) per digit.
In theory the optimiser could deduce how far to unroll the loop
before checking for overflow. */
if (++s < send) {
int digit = *s - '0';
if (digit >= 0 && digit <= 9) {
value = value * 10 + digit;
if (++s < send) {
digit = *s - '0';
if (digit >= 0 && digit <= 9) {
t/00-load.t view on Meta::CPAN
#!perl -T
use 5.006;
use strict;
use warnings;
use Test::More;
plan tests => 1;
BEGIN {
use_ok( 'AVLTree' ) || print "Bail out!\n";
}
diag( "Testing AVLTree $AVLTree::VERSION, Perl $], $^X" );
t/01-numbers.t view on Meta::CPAN
#!perl -T
use 5.008;
use strict;
use warnings;
use Test::More;
plan tests => 28;
use AVLTree;
# test AVL tree with numbers
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");
t/01-numbers.t view on Meta::CPAN
ok($result, "Item found");
ok(!$tree->find(18), "Item not found");
ok(!$tree->remove(1), "Non existent item not removed");
is($tree->size(), 6, "Tree size preserved after unsuccessful removal");
ok($tree->remove(20), "Existing item removed");
ok(!$tree->find(20), "Item removed not found");
is($tree->size(), 5, "Tree size preserved after unsuccessful removal");
# test traversal
my $item = $tree->first;
is($item, 10, 'First item');
my @ids = qw/25 30 40 50/;
while ($item = $tree->next()) {
is($item, shift @ids, 'Next item');
}
$item = $tree->last;
is($item, 50, 'Last item');
@ids = qw/40 30 25 10/;
t/02-custom.t view on Meta::CPAN
#!perl -T
use 5.008;
use strict;
use warnings;
use Test::More;
use Test::Deep;
use Carp;
plan tests => 31;
use AVLTree;
# test AVL tree with custom data
# suppose data comes as a hash ref where the comparison is based on
# on the values associated to a given key, e.g. id
sub cmp_f {
my ($i1, $i2) = @_;
my ($id1, $id2) = ($i1->{id}, $i2->{id});
croak "Cannot compare items based on id"
unless defined $id1 and defined $id2;
return $id1<$id2?-1:($id1>$id2)?1:0;
t/02-custom.t view on Meta::CPAN
cmp_deeply($result, { id => 30, data => ['thirty'] }, "Item returned");
ok(!$tree->find({ id => 18 }), "Item not found");
ok(!$tree->remove({ id => 1 }), "Non existent item not removed");
is($tree->size(), 6, "Tree size preserved after unsuccessful removal");
ok($tree->remove({ id => 20 }), "Existing item removed");
ok(!$tree->find({ id => 20 }), "Item removed not found");
is($tree->size(), 5, "Tree size preserved after unsuccessful removal");
# test traversal
my $item = $tree->first;
ok($item->{id} == 10, 'First item');
my @ids = qw/25 30 40 50/;
while ($item = $tree->next()) {
ok($item->{id} == shift @ids, 'Next item');
}
$item = $tree->last;
ok($item->{id} == 50, 'Last item');
@ids = qw/40 30 25 10/;
t/03-leak.t view on Meta::CPAN
#!perl -T
use 5.008;
use strict;
use warnings FATAL => 'all';
use constant HAS_LEAKTRACE => eval{ require Test::LeakTrace };
use Test::More HAS_LEAKTRACE ? (tests => 10) : (skip_all => 'require Test::LeakTrace');
use Test::LeakTrace;
use Carp;
BEGIN { use_ok('AVLTree'); }
sub cmp_numbers {
my ($i1, $i2) = @_;
return $i1<$i2?-1:($i1>$i2)?1:0;
}
sub cmp_custom {
my ($i1, $i2) = @_;
my ($id1, $id2) = ($i1->{id}, $i2->{id});
croak "Cannot compare items based on id"
unless defined $id1 and defined $id2;
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 {
t/manifest.t view on Meta::CPAN
#!perl -T
use 5.006;
use strict;
use warnings;
use Test::More;
unless ( $ENV{RELEASE_TESTING} ) {
plan( skip_all => "Author tests not required for installation" );
}
my $min_tcm = 0.9;
eval "use Test::CheckManifest $min_tcm";
plan skip_all => "Test::CheckManifest $min_tcm required" if $@;
ok_manifest();
t/pod-coverage.t view on Meta::CPAN
#!perl -T
use 5.006;
use strict;
use warnings;
use Test::More;
unless ( $ENV{RELEASE_TESTING} ) {
plan( skip_all => "Author tests not required for installation" );
}
# Ensure a recent version of Test::Pod::Coverage
my $min_tpc = 1.08;
eval "use Test::Pod::Coverage $min_tpc";
plan skip_all => "Test::Pod::Coverage $min_tpc required for testing POD coverage"
if $@;
# Test::Pod::Coverage doesn't require a minimum Pod::Coverage version,
# but older versions don't recognize some common documentation styles
my $min_pc = 0.18;
eval "use Pod::Coverage $min_pc";
plan skip_all => "Pod::Coverage $min_pc required for testing POD coverage"
if $@;
all_pod_coverage_ok();
#!perl -T
use 5.006;
use strict;
use warnings;
use Test::More;
unless ( $ENV{RELEASE_TESTING} ) {
plan( skip_all => "Author tests not required for installation" );
}
# Ensure a recent version of Test::Pod
my $min_tp = 1.22;
eval "use Test::Pod $min_tp";
plan skip_all => "Test::Pod $min_tp required for testing POD" if $@;
all_pod_files_ok();
xt/boilerplate.t view on Meta::CPAN
#!perl -T
use 5.006;
use strict;
use warnings;
use Test::More;
plan tests => 3;
sub not_in_file_ok {
my ($filename, %regex) = @_;
open( my $fh, '<', $filename )
or die "couldn't open $filename for reading: $!";
my %violated;
while (my $line = <$fh>) {
while (my ($desc, $regex) = each %regex) {
( run in 2.146 seconds using v1.01-cache-2.11-cpan-3cd7ad12f66 )