view release on metacpan or  search on metacpan

lib/AVLTree.pm  view on Meta::CPAN

  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;
  }

  # Now can do the same as with numbers
  my $tree = AVLTree->new(\&compare);

  my $insert_ok = $tree->insert({ id => 10, data => 'ten' });
  croak "Could not insert item" unless $insert_ok;

  $insert_ok = $tree->insert({ id => 20, data => 'twenty' });
  
  ...

  my $id = 10;
  my $result = $tree->find({ id => $id });
  if($result) {
    printf "Item with id %d found\nData: %s\n", $id, $result->{data};
  } else {
    print "Item with id $id not found\n";
  }

  # forward tree traversal
  my $item = $tree->first();
  print "First item: ", $item, "\n";

  while($item = $tree->next()) {
    print $item, "\n";
  }

  # and similarly for reverse iteratio, using last/prev methods

  ...

=head1 METHODS

=head2 C<new>

  Arg [1]     : (required) A reference to a subroutine
  
  Example     : my $tree->new(\&compare);
                carp "Unable to instantiate tree" unless defined $tree;

  Description : Creates a new AVL tree object.
                The objects hold by the tree are implicitly defined
                by the provided callback.

  Returntype  : AVLTreePtr or undef if unable to instantiate
  Exceptions  : None
  Caller      : General
  Status      : Unstable, interface might change to accomodate suitable defaults, 
                e.g. numbers

=head2 C<find>

  Arg [1]     : Item to search, can be defined just in terms of the attribute
                with which the items in the tree are compared. 
  
  Example     : $tree->find({ id => 10 }); # objects in the tree can hold data as well
                if($result) {
                  printf "Item with id %d found\nData: %s\n", $id, $result->{data};
                } else { print "Item with id $id not found\n"; }

  Description : Query if an item exists in the tree.

  Returntype  : The item, if found, as stored in the tree or undef
                if the item was not found or the query was not provided
                or it was undefined.
  Exceptions  : None
  Caller      : General
  Status      : Unstable

=head2 C<insert>

  Arg [1]     : An item to insert in the tree.
  
  Example     : my $ok = $tree->insert({ id => 10, data => 'ten' });
                croak "Unable to insert 10" unless $ok;

  Description : Insert an item in the tree, use the provided, upon tree construction,
                comparison function to determine the position of the item in the tree

  Returntype  : Bool, true if the item was successfully installed, false otherwise 
  Exceptions  : None
  Caller      : General
  Status      : Unstable

=head2 C<remove>

  Arg[1]      : An item to remove from the tree
  
  Example     : my $ok = $tree->remove({ id => 10 });
                croak "Unable to remove 10" unless $ok;

  Description : Remove an item from the tree.

  Returntype  : Bool, true if the item was successfully installed, false otherwise 
  Exceptions  : None
  Caller      : General