# NOTE: This example isn't meant to be run as-is.
#
# You can get the Heap::Elem module from http://www.perl.com/CPAN/modules/by-module/Heap.

package map_route;

use Heap::Elem;

@ISA = qw(Heap::Elem);

# new - create a new map route object to try to create a
#     route from a starting node to a target node.
#
# $route = map_route->new( $start_town, $finish_town );
sub new {
    my $class = shift;
    $class    = ref($class) || $class;
    my $start = shift;
    my $end   = shift;

    return $class->SUPER::new(
        cur          => $start,
        end          => $end,
        cost_so_far  => 0,
        route_so_far => [$start],
    );
}

# cmp - compare two map routes.
#
# $cmp = $node1->cmp($node2);
sub cmp {
    my $self  = shift;
    my $other = shift;

    return $self->{cost_so_far} <=> $other->{cost_so_far};
}

# is_answer - does this route end at the destination (yet)
#
# $boolean = $route->is_answer;
sub is_answer {
    my $self = shift;
    return $self->{cur} eq $self->{end};
}

# prepare_moves - get ready to look at all valid roads.
#
# $route->prepare_moves;
sub prepare_moves {
    my $self = shift;
    $self->{edge} = -1;
}

# next_move - find next usable road.
#
# $move = $route->next_move;
sub next_move {
    my $self = shift;
    return $self->{cur}->edge( ++$self->{edge} );
}

# make_move - create a new route object that extends the
#     current route to travel the specified road.
#
# $route_new = $route->make_move( $move );
sub make_move {
    my $self = shift;
    my $edge = shift;
    my $next = $edge->dest;
    my $cost = $self->{cost_so_far} + $edge->cost;

    return $self->SUPER::new(
        cur          => $next,
        end          => $self->{end},
        cost_so_far  => $cost,
        route_so_far => [ @{$self->{route_so_far}}, $edge, $next ],
    );
}