Priority Queue ADT Class

"""
-------------------------------------------------------
Priority Queue Class
-------------------------------------------------------
Author:  Ryan Chisholm
__updated__ = "2023-02-01"
-------------------------------------------------------
"""
from copy import deepcopy


class Priority_Queue:

    def __init__(self):
        """
        -------------------------------------------------------
        Initializes an empty priority queue.
        Use: pq = Priority_Queue()
        -------------------------------------------------------
        Returns:
            a new Priority_Queue object (Priority_Queue)
        -------------------------------------------------------
        """
        self._values = []
        self._first = None
        

    def is_empty(self):
        """
        -------------------------------------------------------
        Determines if the priority queue is empty.
        Use: b = pq.is_empty()
        -------------------------------------------------------
        Returns:
            True if priority queue is empty, False otherwise.
        -------------------------------------------------------
        """
        return len(self._values) == 0
    
    

    def __len__(self):
        """
        -------------------------------------------------------
        Returns the length of the priority queue.
        Use: n = len(pq)
        -------------------------------------------------------
        Returns:
            the number of values in the priority queue.
        -------------------------------------------------------
        """
        return len(self._values)
    
    

    def insert(self, value):
        """
        -------------------------------------------------------
        A copy of value is appended to the end of the the priority queue
        Python list, and _first is updated as appropriate to the index of
        value with the highest priority.
        Use: pq.insert(value)
        -------------------------------------------------------
        Parameters:
            value - a data element (?)
        Returns:
            None
        -------------------------------------------------------
        """
        self._values.append(deepcopy(value))
        _values = self._values
        
        if len(_values) == 1: #if there is only one item in queue, it is highest priority
            self._first = 0 #highest priority index is the first index
            
        if _values[-1] < _values[self._first]: #check if newest item added is higher priority
            self._first = _values.index(value)        
                
        return
    

    def peek(self):
        """
        -------------------------------------------------------
        Peeks at the highest priority value of the priority queue.
        Use: v = pq.peek()
        -------------------------------------------------------
        Returns:
            value - a copy of the highest priority value in the priority queue -
                the value is not removed from the priority queue. (?)
        -------------------------------------------------------
        """
        assert len(self._values) > 0, "Cannot peek at an empty priority queue"   
        _values = self._values
        self._set_first() #call method to determine highest priority value
        
        value = deepcopy(self._first)
        value = _values[value] #find value at index of highest priority
            
        return value
    

    def remove(self):
        """
        -------------------------------------------------------
        Removes and returns the highest priority value from the priority queue.
        Use: value = pq.remove()
        -------------------------------------------------------
        Returns:
            value - the highest priority value in the priority queue -
                the value is removed from the priority queue. (?)
        -------------------------------------------------------
        """
        assert len(self._values) > 0, "Cannot remove from an empty priority queue"
        _values = self._values
        self._set_first() #call method to determine highest priority in queue        
                 
        value = _values.pop(self._first) #remove value at index of highest priority
        
        self._set_first() #call again to redefine the highest priority value after it was previously removed
                
        return value
    

    def _set_first(self):
        """
        -------------------------------------------------------
        Private helper function to set the value of _first.
        _first is the index of the value with the highest
        priority in the priority queue. None if queue is empty.
        Use: self._set_first()
        -------------------------------------------------------
        Returns:
            None
        -------------------------------------------------------
        """
        _values = self._values
              
        if len(_values) != 0:     
            self._first = 0 #set default priority to be first index
            
            for i in range(len(_values)):
                if _values[i] < _values[self._first]: #compare to find highest priority
                    self._first = i
                    
        else:
            self._first = None
            
            
            
    def split_key(self, key):
        """
        -------------------------------------------------------
        Splits a priority queue into two depending on an external
        priority key. The source priority queue is empty when the method
        ends. The order of the values from source is preserved.
        Use: target1, target2 = source.split_key(key)
        -------------------------------------------------------
        Parameters:
            key - a data object (?)
        Returns:
            target1 - a priority queue that contains all values
                with priority higher than key (Priority_Queue)
            target2 - priority queue that contains all values with
                priority lower than or equal to key (Priority_Queue)
        -------------------------------------------------------
        """
        _values = self._values
        
        target1 = Priority_Queue()
        target2 = Priority_Queue()
        
        while len(_values) != 0: #until local pq is empty
            value = _values.pop()
            
            if value < key: #if removed value is higher priority than key
                target1.insert(value)
                
            else: #if removed value is equal or lesser priority than key
                target2.insert(value)
                
        return target1, target2
                
            
        
        
        
    def __iter__(self):
        """
        FOR TESTING ONLY
        -------------------------------------------------------
        Generates a Python iterator. Iterates through the priority queue
        from front to rear. Not in priority order.
        Use: for value in pq:
        -------------------------------------------------------
        Returns:
            value - the next value in the priority queue (?)
        -------------------------------------------------------
        """
        for value in self._values:
            yield value