package Rand::Dist::Weighted;

# Copyright (C) 2004  Nick Urbanik <nicku(at)vtc.edu.hk>

# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

use warnings;
use strict;
use vars qw( $VERSION );
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT_OK = qw( &rand_dist_weighted );
$VERSION = 0.01;

# See page 584 of Algorthms With Perl:
sub rand_dist_weighted {
    my ( $dist, $key_order, $total_weight ) = @_;
    $key_order = [ sort { $dist->{$a} <=> $dist->{$b} } keys %$dist ]
        unless $key_order;
    unless ( $total_weight ) {
        foreach ( @$key_order ) { $total_weight += $dist->{$_} }
    }
    my $rand = rand $total_weight;
    my $running_weight;
    foreach my $key ( @$key_order ) {
        $running_weight += $dist->{$key};
        return $key if $running_weight >= $rand;
        #return $key if $running_weight += $dist->{$key} >= $rand;
    }
    die "Oh dear, no result for %$dist!: ";
    # Wrong.  Oh dear, poor proof reading of the book.
    #while ( my ( $key, $weight ) = each %$dist ) {
    #    return $key if $running_weight += $weight >= $rand;
    #}
}

1;