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

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

false, true = 0, 1

# Algorithmic part

class FirstFitTree:
    # using heap layout for tree
    # for n bins, index 1..(n-1) are internal, and index n..(2n-1) bins/leaves
    # the list (array) has size 2n and index 0 is unused
    # the leaves are the bins
    # internal nodes contain maximum available space of any bin in subtree
    # internal nodes always have two children

    def __init__(self, n):
        self.tree = (2 * n) * [1.0]
        self.lastindex = 2 * n - 1

    def insert(self, x):
        if x <= self.tree[1]:
            # it fits
            p = 1
            found = false
            while not found:
                left, right = 2*p, 2*p+1
                if left > self.lastindex:
                    # p is a leaf
                    found = true
                else:
                    # p is an internal node
                    if x <= self.tree[left]:
                        p = left
                    else: # x <= self.tree[right]
                        p = right
            # adjust
            self.tree[p] -= x
            p = p / 2
            while p != 0:
                self.tree[p] = max(self.tree[2*p], self.tree[2*p+1])
                p = p / 2
            return true
        else:
            # it does not fit
            return false

    def printtree(self):
        self.recprinttree(1, 0)
        print "===================="

    def recprinttree(self, p, adj):
        left, right = 2*p, 2*p+1
        if left > self.lastindex:
            # p is a leaf
            print adj * " ", self.tree[p]
        else:
            self.recprinttree(2*p+1, adj + 5)
            print adj * " ", self.tree[p]
            self.recprinttree(2*p, adj + 5)
        
def Uniform():
    # attempt at producing uniformly distributed data over (0,1]
    p = random()
    if p == 0.0:
        p = 1.0
    return p

# choosing uniformly from [0,1) until it sums up to at least n
def MakeSequence(n):
    s = []
    sum = 0
    while sum < n:
        item = Uniform()
        s.append(item)
        sum += item
    return s

def WorstFit(s, bins):
    # keys are negated in the queue for use as max-queue
    q = PriorityQueue(bins)
    i = 0
    while i < bins:
        q.insert(-1.0)
        i += 1
    accepted = 0
    i = 0
    while i < len(s):
        largestspace = -q.minimum()
        if s[i] <= largestspace:
            largestitem = -q.deletemin()
            q.insert(-(largestitem - s[i]))
            accepted += 1
        i += 1
    return accepted

def FirstFit(s, bins):
    t = FirstFitTree(bins)
    accepted = 0
    i = 0
    while i < len(s):
        if t.insert(s[i]):
            accepted += 1
        i += 1
    return accepted

# Averaging and Graphics part

def RatioOnOneSequence(bins):
    s = MakeSequence(bins)
    return 1.0 * FirstFit(s, bins) / WorstFit(s, bins)

def AverageRatioOnMultipleSequences(samplesize, bins):
    sum = 0.0
    i = 0
    while i < samplesize:
        sum += RatioOnOneSequence(bins)
        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(samplesize, bins):
    numberofpoints = 20
    f = open(datafile, "w")
    i = 1
    while i <= numberofpoints:
        adjbins = i * bins / numberofpoints
        avg = AverageRatioOnMultipleSequences(samplesize, adjbins)
        f.write("%d\t%f\n" % (adjbins, avg))
        i += 1
    f.close()
    RunAndShow({"XLABEL": "sequence volume", \
                "SPECIFICTITLE": "comparing FirstFit to WorstFit, sample size %d" % (samplesize)})
    system("ps2pdf results.ps %s" % ("DualSequence%dSample%d.pdf" % (bins, samplesize)))


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


def FuzzyAverageRatioOnMultipleSequences(f, samplesize, bins):
    sum = 0.0
    i = 0
    while i < samplesize:
        ratio = RatioOnOneSequence(bins)
        f.write("%d\t%f\n" % (bins, 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(samplesize, bins):
    numberofpoints = 20
    f = open(datafile, "w")
    f2 = open(datafile2, "w")
    i = 1
    while i <= numberofpoints:
        adjbins = i * bins / numberofpoints
        avg = FuzzyAverageRatioOnMultipleSequences(f2, samplesize, adjbins)
        f.write("%d\t%f\n" % (adjbins, avg))
        i += 1
    f.close()
    f2.close()
    FuzzyRunAndShow({"XLABEL": "sequence volume", \
                     "SPECIFICTITLE": "comparing FirstFit to WorstFit, sample size %d" % (samplesize)})
    system("ps2pdf results.ps %s" % ("DualSequence%dSample%d.pdf" % (bins, samplesize)))

# Example main:

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