view release on metacpan or  search on metacpan

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

#
# TreeOfQueues.pm
#
# An implementation of a binary tree of queues.
# This is a way to solve the problem of duplicate elements within
# a tree.  We want to remove elements from the tree in time oldest-first
# order.   In order to do this, a queue is located at each node in 
# the tree.   The queue contains objects with duplicate
# tree-keys.
#
# Author:  matthias beebe
# Date :  June 2008
#
#
package AI::Pathfinding::SMAstar::TreeOfQueues;
use strict;
use Tree::AVL;
use AI::Pathfinding::SMAstar::AVLQueue;


##################################################
# TreeOfQueues constructor 
##################################################
sub new {
    my $invocant = shift;
    my $class   = ref($invocant) || $invocant;
    my $self = {
	f_avl_compare => undef,
	f_obj_get_key  => undef,
	f_obj_get_data => undef,
	_avl_tree   => Tree::AVL->new(fcompare => \&AI::Pathfinding::SMAstar::AVLQueue::compare,
				      fget_key => \&AI::Pathfinding::SMAstar::AVLQueue::key,
				      fget_data => \&AI::Pathfinding::SMAstar::AVLQueue::key),
        @_, # attribute override
    };

    return bless $self, $class;
}


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

    # check to see if there is a Queue in the tree with the key of obj.
    # if not, create one and insert
    my $fget_key = $self->{f_obj_get_key};
    my $avl_compare = $self->{f_avl_compare};
    my $key = $obj->$fget_key();
    my $queue = AI::Pathfinding::SMAstar::AVLQueue->new(_key => $key);

    my $found_queue = $self->{_avl_tree}->lookup_obj($queue);

    if(!$found_queue){
	$self->{_avl_tree}->insert($queue); # insert queue, with no duplicates	
	$queue->insert($obj); # insert object onto new queue
    }
    else { # found a queue here.  insert obj
	$found_queue->insert($obj);
    }
}


sub remove{
    my ($self, $obj, $cmp_func) = @_;

    # check to see if there is a Queue in the tree with the key of obj.
    # if not, create one and insert
    my $fget_key = $self->{f_obj_get_key};
    my $avl_compare = $self->{f_avl_compare};
    my $key = $obj->$fget_key();
    my $queue = AI::Pathfinding::SMAstar::AVLQueue->new(_key => $key);
    my $avltree = \$self->{_avl_tree};
    my $found_queue = $self->{_avl_tree}->lookup_obj($queue);



    if(!$found_queue){
#	print "TreeOfQueues::remove: did not find queue with key $key\n";
#	$self->{_avl_tree}->print();
    }
    else { # found a queue here.  remove obj
	#print "TreeOfQueues::remove: found queue, removing obj using $cmp_func\n";
	$found_queue->remove($obj, $cmp_func);
	if($found_queue->is_empty()){
	    #print "TreeOfQueues::remove: found queue is now empty, removing queue from tree\n";
	    $$avltree->remove($found_queue);	    
	}	
    }    
}

sub largest_oldest{
    my ($self) = @_;    
    my $avltree = \$self->{_avl_tree};

#    $$avltree->print("-");

    # get the avl tree with the largest key