# Queue.py
# CS42 HW8, problem 2
# Author:
# Implements several versions of the Queue ADT and then compares their speed

import collections
import time

# We provide the deque implementation.   You will write ListQ and RawQ.
class DequeQ(object):
    ''' A queue implementation based on python's built-in queue'''
    def __init__(self):
        ''' Initialize a new queue.'''
        self.deque = collections.deque()

    def __repr__(self):
        ''' Return a string representation of the queue.'''
        ret = "<FRONT> "
        for i in self.deque:
            ret += str(i) + " "
        ret += "<BACK>"
        return ret

    def getType(self):
        ''' Return the type of queue we've implemented.'''
        return "DequeQ"

    def enqueue(self, item):
        ''' Add an item to the queue.'''
        self.deque.append(item)

    def dequeue(self):
        ''' Remove an item from the queue.'''
        if not self.empty():
            return self.deque.popleft()

    def empty(self):
        ''' Return whether or not the queue is empty.'''
        return len(self.deque) == 0

    def peek(self):
        ''' Look at the first item in the queue, but don't remove it.'''
        if not self.empty():
            return self.deque[0]

# Tester code for the queues.
# Make sure these tests pass before profiling
# Also note that these tests do not test the repr method.  You should
# make sure you test that method too.
def qTester(qToTest):
    ''' A tester for a given queue.  The queue should be passed in empty '''
    print
    print "Testing", qToTest.getType()

    # Test 1 empty
    testIt(qToTest.empty(), True, 1)
    for i in range(10):
        qToTest.enqueue(i)
    # Test 2, dequeue
    item = qToTest.dequeue()
    testIt(item, 0, 2)
    # Test 3, peek
    item = qToTest.peek()
    testIt(item, 1, 3)
    # Test 4, peek+dequeue
    item = qToTest.dequeue()
    testIt(item, 1, 4)
    # Test 5, more enqueue and dequeue
    qToTest.enqueue(42)
    qToTest.enqueue(65)
    item = qToTest.dequeue()
    testIt(item, 2, 5)
    for i in range(7):
        qToTest.dequeue()
    item = qToTest.dequeue()
    # Test 6: empty again
    testIt(qToTest.empty(), False, 6)
    item = qToTest.dequeue()
    
    # Test 7: last item
    testIt(item, 65, 7)

    # Test 8: empty
    testIt(qToTest.empty(), True, 8)
    # Test 9: dequeue from empty queue
    item = qToTest.dequeue()
    testIt(item, None, 9)

def testIt(value, expected, num):
    ''' Check a value against an expected value.'''
    if value == expected:
        print "Test", num, "passed."
    else:
        print "Test", num, "FAILED.  Expected", expected, "given", value

        
# Profiling code adapted from
# http://code.activestate.com/recipes/577355-python-27-linked-list-vs-list/
class Stopwatch(object):
    def __init__(self):
        self.__start = 0.0
        self.__stop = 0.0
        self.__duration = 0.0
    
    def start(self):
        self.__start = time.time()
        return self
    
    def stop(self):
        self.__stop = time.time()
        self.__duration = self.__stop - self.__start
        return self.__duration
    
    def duration(self):
        return self.__duration   

class Profiler(object):
    def __init__(self, size, queues):
        ''' Initialize the profiler given a size and a list of different queue
             implementations.'''
        self.size = size
        self.queues = queues
        # Create a list of stopwatches, one for each type of queue
        # for both creating the queues and removing from them
        self.create_sws = []
        for i in range(len(queues)):
            self.create_sws.append(Stopwatch())
        self.remove_sws = []
        for i in range(len(queues)):
            self.remove_sws.append(Stopwatch())
            
    def create_test(self):
        ''' Run the tests of adding all the elements to each queue.'''
        for sw_index in range(len(self.create_sws)):
            sw = self.create_sws[sw_index]
            q = self.queues[sw_index]
            sw.start()
            for value in range(self.size):
                q.enqueue(value)
            sw.stop()
    
    def delete_test(self):
        ''' Run the tests of deleting all the elements from each queue.'''
        for sw_index in range(len(self.remove_sws)):
            sw = self.remove_sws[sw_index]
            q = self.queues[sw_index]
            sw.start()
            for value in range(self.size):
                q.dequeue()
            sw.stop()
            
    def report(self):
        ''' Report the results of the tests.'''
        print("%6s %10d" % ("Size", self.size))
        print("%6s %10s %10s %10s" % ("Type", "Create", "Pop", "Total"))
        for qind in range(len(self.queues)):
            print("%6s" % (self.queues[qind].getType())),
            print("%10.2f %10.2f %10.2f" % (self.create_sws[qind].duration(), \
                                            self.remove_sws[qind].duration(), \
                                            self.create_sws[qind].duration() + \
                                            self.remove_sws[qind].duration()))
        print
        
    def run(self):
        ''' Run the tests.'''
        self.create_test()
        self.delete_test()
        self.report()
   
if __name__ == '__main__':
    qTester(DequeQ())
    # uncomment the next two lines once you've implemented these classes
    #qTester(ListQ())
    #qTester(RawQ())
    qs = []
    qs.append(DequeQ())
    # uncomment the next two lines once you've implemented these classes
    #qs.append(ListQ())
    #qs.append(RawQ())
    Profiler(1000, qs).run()
    Profiler(2000, qs).run()
    Profiler(5000, qs).run()
    Profiler(10000, qs).run()
    Profiler(20000, qs).run()
    Profiler(50000, qs).run()
    Profiler(100000, qs).run()
    print "Complete."