#!/usr/bin/env python
"""
Tests the PQueue implementation a little bit.
"""
import pqueue
import pq3
from time import clock
import whrandom

benchdefault = 100000

def generatetestset(num=benchdefault):
    print "Generating", num, "random (priority, data) pairs....",
    start = clock()
    testset = []
    for x in xrange(num):
        testset.append((whrandom.randint(0,num),x,))
    stop = clock()
    print "done --", stop-start, "seconds."
    return testset

def testinsert(pq, testset):
    print "Inserting into the priority queue....",
    insert = 0
    for priority,data in testset:
        start = clock()
        pq.insert(priority, data)
        stop = clock()
        insert = insert + stop-start
    print "done --", insert, "seconds."
    return

def testextract(pq, testset, reduceset=None):
    if reduceset:
        print "Reducing/extracting from the queue....",
    else:
        print "Extracting from the priority queue....",
    extract = 0
    reduce = 0
    reducecount = 0
    copyt = testset[:]
    out = []
    maxtest = len(testset)-1
    for x in testset:
        start = clock()
        try:
            out.append(pq.pop())
        except IndexError: break
        stop = clock()
        extract = extract + stop-start
        if reduceset:
            index = whrandom.randint(0,maxtest)
            data = copyt[index][1]
            try:
                newpriority = pq[data] / 2
            except KeyError: continue
            reducecount = reducecount + 1
            copyt[index] = (newpriority,data)
            start = clock()
            pq[data] = newpriority
            stop = clock()
            reduce = reduce + stop-start

    if reduceset:
        print "done *", reducecount, "--", reduce, "/", extract, "seconds."
    else:
        print "done --", extract, "seconds."

    print "Checking the results....",
    copyt.sort()

    if reduceset:
        out.sort()
        if copyt == out:
            print "hrm... data probably ok."
        else:
            print "doh... it looks screwed."
    else:
        f = lambda x:x[0]
        if map(f,copyt) == map(f,out):
            print "oooh... looking good...",
            if copyt == out:
                print "and stable!"
            else:
                print "unstable...",
                out.sort()
                if copyt == out:
                    print "but data ok."
                else:
                    print "and data buggered."
        else:
            print "doh... they look screwed:"

def testpq(pq,nums,reduce=None):
    testinsert(pq,nums)
    testextract(pq,nums)
    if reduce:
        testinsert(pq,nums)
        testextract(pq,nums,reduce)

def main(argv):
    benchsize = benchdefault
    if len(argv) > 1:
        import string
        try:
            benchsize = string.atoi(argv[1])
        except ValueError:
            benchsize = benchdefault
    p = pqueue.PQueue()
    testset = generatetestset(benchsize)
    print "-"*20
    print "Testing pqueue.PQueue:"
    testpq(p,testset,1)
    
    p = pq3.PQ0()
    # Kludge the PQ0 class to use the same method names
    p.insert = p.addelt
    p.pop = p.popsmallest
    print "-"*20
    print "Testing pq3.PQ0:"
    testpq(p,testset)

    p = pq3.PQueue()
    # Kludge the PQ0 class to use the same method names
    p.insert = p.addelt
    p.pop = p.popsmallest
    print "-"*20
    print "Testing pq3.PQueue:"
    testpq(p,testset)

    p = pq3.PQEquivBig()
    # Kludge the PQ0 class to use the same method names
    p.insert = p.addelt
    p.pop = p.popsmallest
    print "-"*20
    print "Testing pq3.PQEquivBig:"
    testpq(p,testset)

if __name__ == "__main__":
    import sys
    main(sys.argv)

# End.