#!/usr/common/usg/languages/perl/5.16.0/bin/perl -w
#
# prefixBalancer.pl by Jarrod Chapman <jchapman@lbl.gov> Fri Mar 16 23:15:48 PDT 2012
# Copyright 2012 Jarrod Chapman. All rights reserved.
#

use Getopt::Std;
my %opts = ();
my $validLine = getopts('p:M:', \%opts);
my @required = ("p",);
my $nRequired = 0;
map {$nRequired += exists($opts{$_})} @required;
$validLine &= ($nRequired == @required);
if ($validLine != 1) {
    print "Usage: ./prefixBalancer.pl <-p prefixFile> <<-M maxFraction>>\n";
    exit;
}

my $prefixFile = $opts{"p"};
open (P, $prefixFile) || die "Couldn't open $prefixFile\n";

my %prefixFraction = ();
my @prefixes = ();

while (my $line = <P>) {
    chomp $line;
    my ($p,$f) = $line =~ /^(\S+)\s+(\S+)$/;

    $prefixFraction{$p} = $f;
    push (@prefixes,$p);
}
close P;

my @sortedPrefixes = sort {$prefixFraction{$b} <=> $prefixFraction{$a}} @prefixes;

#foreach my $p (@sortedPrefixes) {
#    print "$p\t$prefixFraction{$p}\n";
#}

my $maxPrefix = $sortedPrefixes[0];
my $maxFraction = $prefixFraction{$maxPrefix};
if (exists($opts{"M"})) {
    my $maxFrac = $opts{"M"};
    $maxFraction = ($maxFrac > $maxFraction) ? $maxFrac : $maxFraction;
}

my $nPrefixes = scalar(@prefixes);

my %binned = ();
my %binTotal = ();
my %binPrefixes = ();
my $maxBin = 0;
    
foreach my $p (@sortedPrefixes) {
    if (exists($binned{$p})) {
	next;
    }
    my $f = $prefixFraction{$p};
    my $unbinned = 1;
    my $binID=0;
    while ($unbinned) {
	if (exists($binTotal{$binID})) {
	    my $binTotal = $binTotal{$binID};
	    if ($binTotal + $f <= $maxFraction) {
		$binned{$p} = $binID;
		$binTotal{$binID} += $f;
		$binPrefixes{$binID} .= "+$p";
		$unbinned = 0;
	    } else {
		$binID++;
		$maxBin = ($binID > $maxBin) ? $binID : $maxBin;
	    }
	} else {
	    $binned{$p} = $binID;
	    $binTotal{$binID} = $f;
	    $binPrefixes{$binID} = "$p";
	    $unbinned = 0;
	}
    }
}

for (my $b = 0; $b <= $maxBin; $b++) {
    print "$b\t$binPrefixes{$b}\t$binTotal{$b}\n";
}

