Prioridad 2

#Daniel Bedialauneta
#EJERCICIO 2

class Cola_Prioridad:
    """Implementación estática circular, pertenencia marcada
    mediante una lista de posiciones excluidas, y las inserciones
    se realizan en el primer hueco disponible. Alternativa 1b"""

    def __init__(self,pri_f,MAX=8):
        self.elems=[None]*MAX
        self.fuera=set()    #Posiciones relativas de los huecos respecto de self.head
        self.priority=pri_f #pri_f(x) devuelve un entero, prioridad descendente
                            #es decir, la cabeza (head) tiene el valor más grande
        self.head=0
        self.q=-1
        self.nelems=0
        self.size=MAX
#Coste fijo el de __init__()


    def enqueue(self,x): #Coste fijo
        if self.isFull():
            return False
        elif len(self.fuera)==0:
            self.q=(self.q+1)%self.size
            self.elems[self.q]=x
            self.nelems+=1
        else:
            pos=min(self.fuera) #Porque supongp que self.q=0, porque en ningun momento lo modifico
            self.fuera.remove(pos)
            self.elems[(self.head+pos)%self.size]=x
            self.nelems+=1
#Coste fijo si no hay posiciones excluidas.
#Si las hay, el coste es O(k) donde k es la cantidad de posiciones exluidas que hay en self.fuera


    def dequeue(self):
        assert not self.isEmpty(), "Error en dequeue(): cola vacía"
        pri=None
        for i in range(self.size):
            if i in self.fuera:
                continue
            pri_parcial = self.priority(self.elems[i])
            if pri==None or pri_parcial > pri:
                pri = pri_parcial
                pos=i
        while (self.q-self.head)%self.size in self.fuera: #En caso de que el elemento extraido sea el que está en la cola
            self.q=(self.q-1)%self.size
        self.fuera.add((pos-self.head)%self.size)
        self.nelems-=1
        return self.elems[pos]
#Coste t(MAX)=MAX+2
#Si el elemento extraido está en la cola el coste es t(MAX)=MAX+2+k, donde k es la cantidad de huecos seguidos que hay justo por delante de la cola antes de ser extraida.

    def __len__(self):
        return self.nelems
#Coste fijo

    def isEmpty(self):
        return self.nelems==0
#Coste fijo

    def isFull(self):
        return self.nelems==self.size
#Coste fijo