from os import system
from random import random
from PriorityQueue import PriorityQueue

datafile = "AutoGeneratedGnuplotData.gpdata"
datafile2 = "AutoGeneratedGnuplotData2.gpdata"

# Algorithmic part

def Uniform():
    # attempt at producing uniformly distributed data over (0,1]
    p = random()
    if p == 0.0:
        p = 1.0
    return p

def MakeSequence(n):
    s = n * [None]
    i = 0
    while i < n:
        s[i] = Uniform()
        i += 1
    return s

def WorstFit(s):
    # keys are negated in the queue for use as max-queue
    q = PriorityQueue(100) # start size; the queue automatically extends
    q.insert(-(1-s[0]))
    i = 1
    while i < len(s):
        largestspace = -q.minimum()
        if s[i] <= largestspace:
            largestitem = -q.deletemin()
            q.insert(-(largestitem - s[i]))
        else:
            q.insert(-(1-s[i]))
        i += 1
    return q.size()

def NextFit(s):
    current = 1.0
    bins = 1
    i = 0
    while i < len(s):
        if s[i] <= current:
            current -= s[i]
        else:
            bins += 1
            current = 1.0 - s[i]
        i += 1
    return bins

# Averaging and Graphics part

def RatioOnOneSequence(n):
    s = MakeSequence(n)
    return 1.0 * NextFit(s) / WorstFit(s)

def AverageRatioOnMultipleSequences(n, samplesize):
    sum = 0.0
    i = 0
    while i < samplesize:
        sum += RatioOnOneSequence(n)
        i += 1
    return sum / samplesize

def RunAndShow(replacements):
    f = open("gnuplotFrame.gp", "r")
    gpFrame = f.read()
    f.close()
    for key in replacements.keys():
        gpFrame = gpFrame.replace(key, replacements[key])
    f = open("gnuplot.gp", "w")
    f.write(gpFrame)
    f.close()
    system("gnuplot gnuplot.gp")
#    system("gv results.ps")

def FixedSampleSizeGnuplotdata(n, samplesize):
    numberofpoints = 20
    f = open(datafile, "w")
    i = 1
    while i <= numberofpoints:
        SeqLength = i * n / numberofpoints
        avg = AverageRatioOnMultipleSequences(SeqLength, samplesize)
        f.write("%d\t%f\n" % (SeqLength, avg))
        i += 1
    f.close()
    RunAndShow({"XLABEL": "sequence length", \
                "SPECIFICTITLE": "comparing NextFit to WorstFit, sample size %d" % (samplesize)})
    system("ps2pdf results.ps %s" % ("ClassicSequence%dSample%d.pdf" % (n, samplesize)))

def FixedSequenceLengthGnuplotdata(n, samplesize):
    numberofpoints = 20
    f = open(datafile, "w")
    i = 1
    while i <= numberofpoints:
        ss = i * samplesize / numberofpoints
        avg = AverageRatioOnMultipleSequences(n, ss)
        f.write("%d\t%f\n" % (ss, avg))
        i += 1
    f.close()
    RunAndShow({"XLABEL": "number of samples", \
                "SPECIFICTITLE": "comparing NextFit to WorstFit, sequence length %d" % (n)})
    system("ps2pdf results.ps %s" % ("ClassicSequence%dSample%d.pdf" % (n, samplesize)))

def FuzzyAverageRatioOnMultipleSequences(f, n, samplesize):
    sum = 0.0
    i = 0
    while i < samplesize:
        ratio = RatioOnOneSequence(n)
        f.write("%d\t%f\n" % (n, ratio))
        sum += ratio
        i += 1
    return sum / samplesize

def FuzzyRunAndShow(replacements):
    f = open("gnuplotFrame2.gp", "r")
    gpFrame = f.read()
    f.close()
    for key in replacements.keys():
        gpFrame = gpFrame.replace(key, replacements[key])
    f = open("gnuplot.gp", "w")
    f.write(gpFrame)
    f.close()
    system("gnuplot gnuplot.gp")
#    system("gv results.ps")

def FuzzyFixedSampleSizeGnuplotdata(n, samplesize):
    numberofpoints = 20
    f = open(datafile, "w")
    f2 = open(datafile2, "w")
    i = 1
    while i <= numberofpoints:
        SeqLength = i * n / numberofpoints
        avg = FuzzyAverageRatioOnMultipleSequences(f2, SeqLength, samplesize)
        f.write("%d\t%f\n" % (SeqLength, avg))
        i += 1
    f.close()
    f2.close()
    FuzzyRunAndShow({"XLABEL": "sequence length", \
                     "SPECIFICTITLE": "comparing NextFit to WorstFit, sample size %d" % (samplesize)})
    system("ps2pdf results.ps %s" % ("ClassicSequence%dSample%d.pdf" % (n, samplesize)))


# Example main:

FuzzyFixedSampleSizeGnuplotdata(100, 10)
FuzzyFixedSampleSizeGnuplotdata(1000, 10)
FuzzyFixedSampleSizeGnuplotdata(10000, 10)
FuzzyFixedSampleSizeGnuplotdata(100000, 10)