source: utilitiespy/tudelft/utilities/tools/queue.py

from typing import TypeVar, Collection, Any, Generic, List
from tudelft.utilities.tools.comparator import Comparator, DefaultComparator

E=TypeVar("E") 

class PriorityQueue(Generic[E]):
    '''
    An unbounded priority {@linkplain Queue queue} based on a priority heap.
    The elements of the priority queue are ordered according to their
    {@linkplain Comparable natural ordering}, or by a {@link Comparator}
    provided at queue construction time, depending on which constructor is
    used.  A priority queue does not permit {@code null} elements.
    A priority queue relying on natural ordering also does not permit
    insertion of non-comparable objects (doing so may result in
    {@code ClassCastException}).
    
    <p>The <em>head</em> of this queue is the <em>least</em> element
    with respect to the specified ordering.  If multiple elements are
    tied for least value, the head is one of those elements -- ties are
    broken arbitrarily.  The queue retrieval operations {@code poll},
    {@code remove}, {@code peek}, and {@code element} access the
    element at the head of the queue.
    
    <p>A priority queue is unbounded, but has an internal
    <i>capacity</i> governing the size of an array used to store the
    elements on the queue.  It is always at least as large as the queue
    size.  As elements are added to a priority queue, its capacity
    grows automatically.  The details of the growth policy are not
    specified.
    
    <p>This class and its iterator implement all of the
    <em>optional</em> methods of the {@link Collection} and {@link
    Iterator} interfaces.  The Iterator provided in method {@link
    #iterator()} and the Spliterator provided in method {@link #spliterator()}
    are <em>not</em> guaranteed to traverse the elements of
    the priority queue in any particular order. If you need ordered
    traversal, consider using {@code Arrays.sort(pq.toArray())}.
    
    <p><strong>Note that this implementation is not synchronized.</strong>
    Multiple threads should not access a {@code PriorityQueue}
    instance concurrently if any of the threads modifies the queue.
    Instead, use the thread-safe {@link
    java.util.concurrent.PriorityBlockingQueue} class.
    
    <p>Implementation note: this implementation provides
    O(log(n)) time for the enqueuing and dequeuing methods
    ({@code offer}, {@code poll}, {@code remove()} and {@code add});
    linear time for the {@code remove(Object)} and {@code contains(Object)}
    methods; and constant time for the retrieval methods
    ({@code peek}, {@code element}, and {@code size}).
    
    <p>This class is a member of the
    <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
    Java Collections Framework</a>.
    @param data a set of data of type E
    @param  comparator the comparator that will be used to order this
             priority queue.  If {@code null}, the {@linkplain Comparable
            natural ordering} of the elements will be used.
    @param <E> the type of elements held in this queue
    '''
    
    def __init__(self, data:List[E]=[], comparator:Comparator[E]=DefaultComparator()):
        self.__comparator:Comparator[E] = comparator
        self.__data:List[E]=[]
        self.extend(data)
        
    def append(self, e:E)->bool:
        '''
        Inserts the specified element into this priority queue.
        
        @return {@code true} 

        '''
        if e==None:
            raise ValueError("e is None")
        
        
        # python 3.8 bisect seems unable to handke key 
        # insert is linear anyway.
        for i in range(len(self.__data)):
            if self.__comparator.compare(e, self.__data[i]) <0:
                self.__data.insert(i, e)
                return True
        self.__data.append(e) # at last pos
        return True
    
    def extend(self,c:Collection[E]):
        for e in c:
            self.append(e)
            
    def __add__(self, c:Collection[E]):
        self.extend(c)
            
    def index(self, item):
        return self.__data.index(item)

    def __len__(self):
        return len(self.__data)

    def __contains__(self, o:Any):
        return o in self.__data
    
    def __getitem__(self, i:int)->E:
        return self.__data[i]
    
    def __repr__(self):
        return repr(self.__data)
    
    '''
    Remove the item at the given position in the list, and return it. If
    It raises an IndexError if the list is empty or the index is outside the list range.
    '''
    def pop(self, n:int) -> E: 
        return self.__data.pop(n)