Prioridad, 1

#Daniel Bedialauneta
#EJERCICIO 1 DE COLAS DE PRIORIDAD
class Cola_Prioridad:
    """Implementación estática circular, pertenencia marcada
    mediante una lista de posiciones excluidas, y las inserciones
    se realizan en cola. Alternativa 1a"""

    def __init__(self,pri_f,MAX=100):
        self.elems=[None]*MAX
        self.fuera=set() #Conjunto que contiene las posiciones de los elementos que no estan en la self.elems
                      #es decir, contienes las posiciones que se pueden sustituir por otro valor.
        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 compactacion(self): #Voy a crear una nueva lista
        nueva_lista=[]
        for i in range(len(self.elems)): #Añado a una nueva lista solo los elementos que no estén en self.fuera
            if i not in self.fuera:
                nueva_lista.append(self.elems[i])
        self.head=0
        self.q=len(nueva_lista)-1
        for i in range(len(self.fuera)): #La lista tiene que ser de tamaño MAX, hay elementos que estaban en self.fuera que no hemos añadido,
                                         #añado ahora None para tener longitud MAX
            nueva_lista.append(None)
        self.fuera.clear()
        self.elems=nueva_lista

#Coste t(MAX) = 1+MAX+1+k+1 = MAX+k+3, donde MAX es la longitud de self.elems, y k es la longitud de self.fuera (la cantidad de posiciones excluidas)

    def enqueue(self,x): #Coste fijo
        if self.isFull():
            return False

        if not self.isEmpty() and (self.q+1)%self.size==self.head: #Hay que recurrir a la compactación
            self.compactacion()
        self.q=(self.q+1)%self.size
        self.elems[self.q]=x
        self.nelems+=1
        return True
#Coste fijo a menos que (self.q+1)%self.size==self.head, en cuyo caso tendría prácticamente el coste de compactacion()

    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
        self.fuera.add(pos)
        while self.q in self.fuera: #Por si acaso el elemento que se ha extraido era el de la cola
            self.q=(self.q-1)%self.size

        self.nelems-=1
        return self.elems[pos]
#Coste t(MAX)=MAX+2, por lo general
#Ahora bien, en caso de que el elemento de mayor prioridad que se extrae fuese la cola, se disminuye la cola cuanto sea necesario hasta indicar una posición fuera de los huecos
#En este caso el coste sería t(MAX)=MAX+2+k, donde k es la cantidad de huecos seguidos que están justo delante de la cola

    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