class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)





#Linear Insertion
#Works from front to Back
class PriorityQueue1:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        for index in range(len(self.items)):
            comp = self.items[index]
            if comp>item:
                self.items.insert(index,item)
                return
            
        #If we haven't returned yet than all of the items
        #in the priority queue are smaller than this item
        #and it belongs at the end of the queue
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)    



#Logarithmic Insertion
class PriorityQueue2:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        if len(self.items)==0:  #If the queue is empty, it is simple
            self.items.append(item)
        elif self.items[-1]<=item: #If the new item is lower than anything in the queue
            self.items.append(item)
        elif self.items[0]>item: # if the new item has higher priority than anything in the queue
            self.items.insert(0,item)
        else: #If we get here the new item belongs somewhere inbetween other items in the queue
            after=0
            before=len(self.items)-1
            while after+1<before:
                index = (after+before)//2
                comp = self.items[index]
                if comp>item:
                    before=index
                else:
                    after=index
            self.items.insert(before,item)


    def dequeue(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items) 




def timeDemo(n):
    import time,random

    #Create dataset
    #Contains n items (assuming n is divisible by 4)
    #It contains 4 copies each of all numbers from 1 to n//4
    #We do this so there are some duplications in the priority ratings
    data = list(range(1,(n//4)+1))*4
    random.shuffle(data)
    

    print("Insert",len(data),"items using logarithmic insertion")
    q2 = PriorityQueue2()
    start = time.perf_counter()
    for item in data:
        q2.enqueue(item)
    end = time.perf_counter()
    print("Insertion time = ",(end-start))

    print()
    
    print("Insert",len(data),"items using linear insertion")
    q1 = PriorityQueue1()
    start = time.perf_counter()
    for item in data:
        q1.enqueue(item)
    end = time.perf_counter()
    print("Insertion time = ",(end-start))