#! /usr/bin/env python
"""
mkinstance.py  -- make random instances for benchmarking bin packing algorithms
  * item sizes are generated with random.lognormvariate(1., var),
    where var is a parameter
  * each bin can be filled exactly; an optimal solution corresponds to the
    order of the items in the data
  * *** new on version 0.2 ***
    weights are made integer; bin capacity is set to 100000 by default
    (change parameter PRECISION if you wish to change this)
  

This program may be used as:

  python mkinstance.py dirname
            (for generating an instance set on 'dirname')

  pyhton mkinstance.py seed n_items n_bins variance
            (for generating a single instance on stdout)

Copyright Joao Pedro PEDROSO, FCUP/DCC, 02/2006
**********************************************************************
"""


from __future__ import division
import random
import math

#
# make a random instance
#
def mkexact(sigma, n_items, n_bins):
    """create an instance with an exact solution
       . n_bins  --> total (and optimal) number of bins
       . n_items  --> cardinality of each bin
       . sigma  --> 2nd. param of lognormvariate (variance for corresp. normal distrib.)
            sigma ~ 0.  --> all items with aprox same size
            sigma >> 1.  --> many small items, few big items
       """

    PRECISION = .00001
    DIGITS = int(-math.log10(PRECISION))
    EPS = PRECISION / 1000.	# max floating point error allowed
    
    data = []	# for collecting all the items
    for i in range(n_bins):

        # generate items for a new bin
        total = 0.
        j = 0
        bin = []
        while j < n_items:
            r = random.lognormvariate(1., sigma)	# unscaled size
            if r < n_items*10*PRECISION  or  r > 10.:	# discard too small or too large items
                continue
            total += r
            bin.append(r)
            j += 1

        # normalize sizes
        newtotal = 0.
        imax = 0
        vmax = 0.
        for i in range(n_items):
            value = round(bin[i]/total, DIGITS)
            bin[i] = value
            newtotal += value
            if value > vmax:
                vmax = bin[i]
                imax = i

        # correct largest item if sum != 1. (due to floating point rounding)
        diff = 1. - newtotal
        bin[imax] += diff	# update value of largest item, s.t. sum = 1
        bin[imax] = round(bin[imax], DIGITS)
        newtotal = 0

        # append items to the data
        for i in bin:
            assert i > 0.
            # newtotal += i	# use this for a floating point number
            # data.append(i)	# use this for a floating point number
            newtotal += int(round(i/PRECISION))
            data.append(int(round(i/PRECISION)))
        # print newtotal, newtotal - 1.
        # assert abs(newtotal-1.) < EPS	# use this for a floating point number
        assert abs(int(newtotal-1./PRECISION)) == 0	# use this for a floating point number
        

    return data




def mktestset(dirname):
    """ make a complete set of benchmark files
    """

    import gzip
    import os
    try:
        os.mkdir(dirname)
    except:
        print "error: directory", dirname, "exists or cannot be created"
        sys.exit(0)
    basename = "%s/cbp" % dirname
    for seed in range(1,6):
        random.seed(seed)
        for items in [4, 12, 36]:
            frac = 2.	# parameter for the distribution (variance)
            for bins in [100, 1000, 10000, 100000]:
                filename = "%s-%02d-%02d-%d.dat.gz" % (basename, seed, items, bins)
                print "creating instance", filename
                f = gzip.open(filename, "w",9)
                for b in range(bins):
                    data = mkexact(frac, items, 1)
                    for d in data:
                        # print >>f, "%.5f" % d, 	# use this for a floating point number
                        print >>f, "%6d" % d,                        
                    print >>f
                f.close()




if __name__ == "__main__":
    import sys

    if len(sys.argv) != 2 and len(sys.argv) != 5:
        print "usage:", sys.argv[0], "dirname"
        print "       (for generating an instance set on 'dirname')"
        print "   *** or: ***"
        print "usage:", sys.argv[0], "seed n_items n_bins variance"
        print "       (for generating a single instance on stdout)"
        sys.exit()

    if len(sys.argv) == 2:
        print "creating test set files on", sys.argv[1]
        mktestset(sys.argv[1])
    else:
        seed = int(sys.argv[1])
        n_items = int(sys.argv[2])
        n_bins = int(sys.argv[3])
        a = float(sys.argv[4])

        data = mkexact(a, n_items, n_bins)
        for i in range(len(data)):
            print "%6d" % data[i],
            if (i+1) % n_items == 0:
                print