view release on metacpan or  search on metacpan

lib/AI/Pathfinding/SMAstar/PriorityQueue.pm  view on Meta::CPAN

#
# PriorityQueue.pm
#

# Author:  matthias beebe
# Date :  June 2008
#
#
package AI::Pathfinding::SMAstar::PriorityQueue;


use Tree::AVL;
use AI::Pathfinding::SMAstar::Path;
use AI::Pathfinding::SMAstar::TreeOfQueues;
use Carp;
use strict;



##################################################
# PriorityQueue constructor 
##################################################
sub new {
    my $invocant = shift;
    my $class   = ref($invocant) || $invocant;
    my $self = { 
        _hash_of_trees_ref    => {},
	
	_cost_min_max_tree   => Tree::AVL->new( fcompare => \&fp_compare,  # floating-point compare
						fget_key => sub { $_[0] },
						fget_data => sub { $_[0] },),

	f_depth        => \&AI::Pathfinding::SMAstar::Path::depth,
	f_fcost        => \&AI::Pathfinding::SMAstar::Path::fcost,
	f_avl_compare  => \&AI::Pathfinding::SMAstar::Path::compare_by_depth,
	f_avl_get_key  => \&AI::Pathfinding::SMAstar::Path::depth,
	f_avl_get_data => \&AI::Pathfinding::SMAstar::Path::get_data,

	_size                 => 0,

	@_,    # attribute override
    };
    return bless $self, $class;
}

################################################
# accessors
################################################

sub hash_of_trees {
    my $self = shift;
    if (@_) { $self->{_hash_of_trees_ref} = shift }
    return $self->{_hash_of_trees_ref};
}

sub size {
    my $self = shift;
    if (@_) { $self->{_size} = shift }
    return $self->{_size};    
}



################################################
##
## other methods       
##
################################################

sub insert {
    my ($self, $pobj) = @_;

    my $cost_hash_ref = $self->{_hash_of_trees_ref};
    my $cost_hash_key_func = $self->{f_fcost};

    my $cost_min_max_tree = $self->{_cost_min_max_tree};

    my $depth_func = $self->{f_depth};
    
    my $avl_compare_func = $self->{f_avl_compare};
    my $avl_get_key_func = $self->{f_avl_get_key};
    my $avl_get_data_func = $self->{f_avl_get_data};

    my $cost_key = $pobj->$cost_hash_key_func();
    my $data = $pobj->$avl_get_data_func();

    
    # inserting pobj with key: $cost_key, data: $data    
    if(!$cost_hash_ref->{$cost_key}){
	# no tree for this depth yet, so create one.
	my $avltree = AI::Pathfinding::SMAstar::TreeOfQueues->new(
	    f_avl_compare => $avl_compare_func,
	    f_obj_get_key => $avl_get_key_func,
	    f_obj_get_data => $avl_get_data_func,
	    );
       
	$avltree->insert($pobj);	
	$cost_hash_ref->{$cost_key} = \$avltree;
	# insert the cost_key in the cost tree
	$cost_min_max_tree->insert($cost_key);
    }
    else{
    # there is already a tree at $cost_key, so inserting there