view release on metacpan or  search on metacpan

lib/AVLTree.pm  view on Meta::CPAN

package AVLTree;

use 5.008;
use strict;
use warnings;

our $VERSION = '0.1.7';
our $ENABLE_DEBUG = 0;

require XSLoader;
XSLoader::load('AVLTree', $VERSION);

1; # End of AVLTree
__END__

=head1 NAME

AVLTree - Perl extension for efficient creation and manipulation of AVL balanced binary trees.

=head1 VERSION

Version 0.1.7

=head1 DESCRIPTION

This module provides a simple and fast implementation of B<AVL balanced binary trees>.
It uses the Perl XS extension mechanism by providing a tiny wrapper around 
an efficient C library which does the core of the work. Preliminary benchmarking 
shows this module one order of magnitude faster than a pure perl implementation.

The nodes of an AVL tree object can hold any kind of item, as long as each 
one of these can be used or has an element that can be use to define a partial order 
on the set of possible items. This is specified by providing, upon tree construction,
a reference to a function for comparing any two of the possible items.

The underlying C library is a reinterpretation of the C library originally 
developed by Julienne Walker L<http://www.eternallyconfuzzled.com/jsw_home.aspx>. 
This library has been adapted for dealing directly with Perl (SV) variables.

The module at the moment is in beta stage but it is usable. It provides methods 
for creating and querying an AVL tree, get its size and insert and remove elements 
from it. Additionaly, it is possible to traverse the tree in forward/reverse order.

=head1 SYNOPSIS

  use AVLTree;

  # Define a function to compare two numbers i1 and i2,
  # return -1 if i1 < i2, 1 if i2 > i1 and 0 otherwise 

  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
  my $item = 1
  if($tree->remove($item)) {
    print "Item $item has been removed\n";
  } else {
    print "Item $item was not in the tree so it's not been removed\n";
  }
  
  printf "Size of tree is now: %d\n", $tree->size();

  ...

  # Suppose you want the tree to hold generic data items, e.g. hashrefs
  # which hold some data. We can deal with these by definying a custom
  # comparison function based on one of the attributes of these data items, 
  # e.g. 'id':
 
  sub compare {
    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;
  }