#!/usr/bin/perl -w

package Algorithm::Numerical::WeightedShuffle;

######################
#
# Algorithm::Numerical::WeightedShuffle;
# v0.01
# Michael K. Neylon
# mneylon-pm@masemware.com
# May 27, 2001
#
# Shuffles a list based on weights, as to have items with 
# heavier weights to have a better chance of being located 
# earlier in the shuffled list
#
# Loosely based and borrowed from Abigail's 
# Algorithm::Numerical::Shuffle
#
# Suggestions/Comments/Ideas are highly desired and can be 
# sent to the eamil address above.
#
# Change History:
#
# v0.01 - May 27, 2001
# - Initial Release
#
######################

use strict;
use Exporter;

use vars qw /$VERSION @ISA @EXPORT @EXPORT_OK/;

@ISA       = qw /Exporter/;
@EXPORT    = qw //;
@EXPORT_OK = qw /weightedshuffle weightedshuffleindex/;

$VERSION   = 0.01;

sub weightedshuffle {
    die "Need two equal length arrays for WeightedShuffle"
        if !@_ || ref $_[0] ne 'ARRAY' || ref $_[1] ne 'ARRAY'
            || @{$_[0]} != @{$_[1]};
    
    my ( $list, $weights ) = @_;
    my @array = map { $list->[ $_ ] } 
                weightedshuffleindex( $weights );
    wantarray ? @array : \@array;
}

sub weightedshuffleindex {
    return @_ if !@_ || ref $_ [0] eq 'ARRAY' && !@{$_ [0]};
    # We need a copy here, since we destroy it
    my @weights = @_ == 1 && ref $_ [0] eq 'ARRAY' ? @{shift()} : @_;

    my @indices = ( 0..@weights - 1);
    my @array = ();

    my $sum = 0;
    foreach ( @weights ) { $sum += ( $_ > 0 ? $_ : 0 )  };
    while ( $sum > 0 ) {
        my $r = rand $sum ;
        my $total = 0;
        my $i = -1;
        while ( $total < $r ) { 
            $total += ( $weights[ $i+1 ] > 0 ? $weights[ $i+1 ] : 0 );
            $i++;
        }
        push @array, splice( @indices, $i, 1 );
        splice( @weights, $i, 1 );
        $sum = 0; foreach ( @weights ) { $sum += ( $_ > 0 ? $_ : 0 )  
+};
    }
    # anything left over, push to the end
    push @array, @indices;
    wantarray ? @array : \@array;
}

__END__

=head1 NAME

Algorithm::Numerical::WeightedShuffle - Shuffle a list using weights.

=head1 SYNOPSIS

    use Algorithm::Numerical::WeightedShuffle 
        qw( weightedshuffle weightedshuffleindex );

    @array = ( 1..10 );
    @weights = map { $_*$_ } @array;
    @shuffled = weightedshuffle( \@array, \@weights );

    %hash = ( one=>1, two=>2, three=>3, four=>4, five=>5 );
    my @keys = keys %hash;
     @shuffled_keys = map { $keys[$_] } 
                 weightedshuffleindex( map { $hash{ $_ } } @keys );

=head1 DESCRIPTION

C<weightedshuffle> takes two array references; the first is the list
to be shuffled, while the second are the weights for the items in this
list.  The list is then shuffled such that items with higher weights w
+ill
have a better chance of appearing earlier in the returned list.  
Weights should be non-zero positive numbers, but need not sum to 1; 
negative or zero weights will be ignored and items associated with 
these will simply be appended to the end of the list.

The subroutine returns the list in list context, and a reference to
the list in scalar context.

C<weightedshuffleindex> takes a single array or array reference, being
the list of weights.  It then returns an array of indices based on 
this list, such that indices of larger weights will have a better
chance of being earlier in the list.  The same requirements for the
weights from C<weightedshuffle> apply here as well.  The indices array
returned by this function can be used further by a map statement, to 
shuffle the keys of a hash, for example.

The subroutine returns the list in list context, and a reference to
the list in scalar context.

=head1 HISTORY

    Revision 0.01  2001/05/27   Michael K. Neylon
    Initial revision

=head1 AUTHOR

This package was written by Michael K. Neylon

=head1 COPYRIGHT

Copyright 2001 by Michael K. Neylon

=head1 LICENSE

Permission is hereby granted, free of charge, to any person obtaining 
+a
copy of this software and associated documentation files (the "Softwar
+e"),
to deal in the Software without restriction, including without limitat
+ion
the rights to use, copy, modify, merge, publish, distribute, sublicens
+e,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be include
+d
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRES
+S OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILIT
+Y,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHAL
+L
THE AUTHOR BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

=cut

1;