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

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] = 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)