import Queue as qu   # to get PriorityQueue
import time  # for testing use only
import sys  # for testing use only
import random  # for testing use only
import heapq  # for heap functions in HeapPQ class only

class RAC:
    """ Restricted Access Container.
    A container with an internal data storage that allows you to add items to that data store
    in an encapsulated manner.
    Retrieval of data items is not defined at this level.
    """
    def __init__(self):
        """ Constructor for the class.   Initializes the internal data store.
        """
        self._data = []

    def put(self, x):
        """ Add the given data item, x, to the internal data store.
        For convenience, returns the RAC itself.
        """
        self._data.append(x)
        return self
    
    def putList(self, aList):
        """ Convenience method to add a list if items to the internal data store.  
        Items are added in order starting from the front of the given list.
        For convenience, returns the RAC itself.
        """
        for x in aList:
            self.put(x)
        return self
    
    def isEmpty(self):
        """ REturns true if the internal data store is empty.  Returns false otherwise.
        """
        return 0 == len(self._data)
    
    def __str__(self):
        """ Returns the string representation of the internal data store, in order from oldest to the newest elements.
        """
        return str(self._data)
        
class Stack(RAC):
    """ Stack subclass of RAC where the data is retrieved in a 
    First In/Last Out (FILO) order.
    Inherits put(), putList(), isEmpty() and __str__() from RAC.
    """
   
    def __init__(self):
        """ Class constructor.  Simply calls the superclass constructor.
        """
        RAC.__init__(self)
        
    
    def get(self):
        """ Returns that latest element that was put into the Stack.
        Throws an exception if the Stack is empty.
        """
        return self._data.pop()
        

    
class Queue(RAC):
    """ Queue subclass of RAC where the data is retrieved in a 
    First In/First Out (FIFO) order.
    Inherits put(), putList(), isEmpty() and __str__() from RAC.
    """
   
    def __init__(self):
        """ Class constructor.  Simply calls the superclass constructor.
        """
        RAC.__init__(self)
        
    def get(self):
        """ Returns the oldest element currently in the Queue.
        Throws an exception if the Queue is empty.
        """
        return self._data.pop(0)


class OrderedPutPQ(RAC):
    """ A priority queue subclass of RAC where the put() method performs an ordered 
    insert into the internal data store.  get() is an O(1) retrieval from the end of the list.
    The queue is assumed to hold either priority values directly or tuples of the form (priority, value)
    """
    
    def __init__(self):
        """ Class constructor.  Simply calls the superclass constructor.
        """
        RAC.__init__(self)
        
    def put(self, x):
        """ Add the given data item, x, to the internal data store.
        x is a priority or a tuple of the form (priority, value)
        Overrides the put() inherited from RAC.
        For convenience, returns the RAC itself.
        """
        # self._data is assumed to be sorted such that the min priority is at the end of the list
        # thus enabling get() to be an O(1) operation that returns the min priority entry.
        for i in range(len(self._data)):
            if x > self._data[i]:  # comparing tuples only compares the first element
                self._data.insert(i, x)     
                return self
        self._data.append(x)
        return self
    
    def get(self):
        """ O(1) retrieval of smallest data element from end of internal data store.
        """
        return self._data.pop()
        
class OrderedGetPQ(RAC):
    """ A priority queue subclass of RAC where the get() method removes the minimum
    priority entry in the internal data store.  put() is the O(1) append onto the internal data store
    inherited from RAC.
    The queue is assumed to hold either priority values directly or tuples of the form (priority, value)
    """
    
    def __init__(self):
        """ Class constructor.  Simply calls the superclass constructor.
        """
        RAC.__init__(self)
        
    def get(self):
        """ Returns the minimum priority element in the queue.
        Throws an exception if the queue is empty.
        """
        # internal data store is assumed to be unsorted.  This enables put() 
        # to be an O(1) operation.
        min = self._data.pop()  # O(1) removal of a first guess min value
        for i in  range(len(self._data)):   # loop over all remaining values to find true min value
            x = self._data[i]  # save current value so you don't have to access it again.
            if x < min:   # comparing tuples only compares the first element
                self._data[i] = min  # put old guess back in data store
                min = x   # new guess value
        return min

class HeapPQ(RAC):
    """ A priority queue subclass of RAC where the internal data store is a heap.  
    put() and get() are heap insertion and removal operations.
    The queue is assumed to hold either priority values directly or tuples of the form (priority, value)
    """
    
    def __init__(self):
        """ Class constructor.  Simply calls the superclass constructor.
        """
        RAC.__init__(self)
        
    def put(self, x):
        """ Add the given data item, x, to the internal heap data store.
        x is a priority or a tuple of the form (priority, value)
        Overrides the put() inherited from RAC.
        For convenience, returns the RAC itself.
        """

        heapq.heappush(self._data, x)
        return self
    
    def get(self):
        """ Retrieval of smallest data element from internal heap data store.
        """
        return heapq.heappop(self._data)
        
# Test code:        
print
print "OrderedPutPQ tests:"
pq1 = OrderedPutPQ()
pq1.put((4, "a"))
pq1.put((42, "b")) 
pq1.put((2, "c"))       
print pq1.get()
print pq1.get()
print pq1.get()
print

print "OrderedGetPQ tests:"
pq2 = OrderedPutPQ()
pq2.put((40, "x"))
pq2.put((20, "y")) 
pq2.put((420, "z"))       
print pq2.get()
print pq2.get()
print pq2.get()
print
        
print "HeapPQ tests:"
hpq = HeapPQ()
hpq.put((200, "aa"))
hpq.put((-400, "bb")) 
hpq.put((42, "cc"))       
print hpq.get()
print hpq.get()
print hpq.get()
print

print "PriorityQueue tests:"
qpq = qu.PriorityQueue()
qpq.put((2000, "aa"))
qpq.put((4000, "bb")) 
qpq.put((-420, "cc"))       
print qpq.get()
print qpq.get()
print qpq.get()

print

def timeFn(fn, nTrials):
    """ Returns the elapsed time in seconds for running the no-parameter function, fn,
    nTrials times.
    """
    t1 = time.time()
    for i in range(nTrials):
        fn()
    return time.time()-t1
    
   
def timePQ(PQClass, preLoadData, testData):
    """ Prints the elapsed time for put() and get() operations 
    (averaged over 10000 trials) on an instance of the given class, PQClass 
    that has been loaded with n random integers.   PQClass is the class name of 
    the desired priority queue, without quotes or parentheses.
    """ 
    pq = PQClass()   # create an instance of the given class
    n = len(preLoadData)
    nTrials = len(testData)
    print "Pre-loading ", n,"elements into",PQClass.__name__,"queue..."
    for i in range(n):
        pq.put(preLoadData[i])
    print "Done loading queue."
    
    idx = [0]
    def testPut():
        """ Generates a random number and puts it into pq.
        """
        pq.put(testData[idx[0]])
        idx[0] += 1
   
    def testGet():
        """ Calls pq.get()
        """
        pq.get()    
    
    # Run put and get n times each and print the results:
    print PQClass.__name__+".put() @  n =", n," --> ", 1.0e6* timeFn(testPut, nTrials)/nTrials, "microsecs per operation"
    print PQClass.__name__+".get() @ n =", n," --> ", 1.0e6*timeFn(testGet, n)/nTrials, "microsecs per operation"
    print



def comparePQs(n):
    """ Time the put and get speeds for the different types of priority queues when the queue
    already holds n data elements.  Uses the same set of random data values for all tests.
    """
    max = sys.maxint
    min = -sys.maxint-1
    preData = [random.randint(min, max) for i in range(n)]

    nTrials = 10000
    putData = [random.randint(min, max) for i in range(nTrials)]

    
    timePQ(OrderedPutPQ, preData, putData)
    timePQ(OrderedGetPQ, preData, putData)
    timePQ(HeapPQ, preData, putData)
    timePQ(qu.PriorityQueue, preData, putData)    

    
nElements = 10000    
comparePQs(nElements)