Circular Queue ADT Class

"""
-------------------------------------------------------
[program description]
-------------------------------------------------------
Author:  Ryan Chisholm
__updated__ = "2023-02-10"
-------------------------------------------------------
"""
from copy import deepcopy


class Queue:
    """
    -------------------------------------------------------
    Constants
    -------------------------------------------------------
    """
    # a default maximum size when one is not provided
    DEFAULT_CAPACITY = 10

    def __init__(self, capacity=DEFAULT_CAPACITY):
        """
        -------------------------------------------------------
        Initializes an empty queue. Data is stored in a fixed-size list.
        Use: target = Queue(capacity)
        Use: target = Queue()  # uses default capacity
        -------------------------------------------------------
        Parameters:
            capacity - maximum size of the queue (int > 0)
        Returns:
            a new Queue object (Queue)
        -------------------------------------------------------
        """
        assert capacity > 0, "Queue size must be > 0"

        self._capacity = capacity
        self._values = [None] * self._capacity
        self._front = None   # queue has no data
        self._rear = 0       # first available index for insertion
        self._count = 0      # number of data items
        

    def is_empty(self):
        """
        -------------------------------------------------------
        Determines if the queue is empty.
        Use: empty = source.is_empty()
        -------------------------------------------------------
        Returns:
            True if the queue is empty, False otherwise.
        -------------------------------------------------------
        """             
        return self._count == 0
    
    

    def is_full(self):
        """
        -------------------------------------------------------
        Determines if the queue is full.
        Use: full = source.is_full()
        -------------------------------------------------------
        Returns:
            True if the queue is full, False otherwise.
        -------------------------------------------------------
        """
        return self._count == self._capacity 
    
    

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

    def __eq__(self, target):
        """
        ----------------
        Determines whether two Queues are equal.
        Values in self and target are compared and if all values are equal
        and in the same order, returns True, otherwise returns False.
        Use: equals = source == target
        ---------------
        Parameters:
            target - a queue (Queue)
        Returns:
            equals - True if source contains the same values
                as target in the same order, otherwise False. (boolean)
        ---------------
        """
        _values = self._values
        equals = False
        i = deepcopy(self._front)
        j = 0
        t = [] #temp list for easier comparison
                
        for values in target: #add values in target to list
            t.append(values)
        
        if t[j] in _values and self._count == len(t): #make sure they have same number of values, can't be equal if values are missing
            while t[j] != _values[i]:
                j += 1 #find value where both are equal, start comparison from there
            
            while t[j] == _values[i] and i < (self._count - 1): #run until they are not equal, or reach the end of local queue
                j += 1
                i += 1
                
                if j >= len(t) and i < self._count: #circular queue, avoid going out of range
                    j = j - len(t)
                    
            if i == (self._count - 1): #ending i value is equal to end of queue, meaning the loop went all the way through without finding any unequal values
                equals = True
                        
        return equals
    
    

    def insert(self, value):
        """
        -------------------------------------------------------
        Adds a copy of value to the rear of the queue.
        Use: source.insert( value )
        -------------------------------------------------------
        Parameters:
            value - a data element (?)
        Returns:
            None
        -------------------------------------------------------
        """
        assert self._rear is not None, "Cannot add to a full queue"
        _values = self._values
        _rear = self._rear
        i = 0
        
        if _rear >= len(_values) and self._count != self._capacity: #checks if value is out of range of queue, assumes it is linear, not circular
            index = _rear - len(_values)
            _values[index] = deepcopy(value)

        else:
            _values[_rear] = deepcopy(value) #add copy of value at rear of queue
        
        self._rear += 1 #rear index increases        
        self._count += 1 #each time insert is called, count is increased
        
        if self._count == 1: #if there is onlt one value in queue
            while _values[i] is None and i < len(_values): #find front
                i += 1
            
            self._front = i
                        
        return
        

    def remove(self):
        """
        -------------------------------------------------------
        Removes and returns value from the queue.
        Use: v = source.remove()
        -------------------------------------------------------
        Returns:
            value - the value at the front of the queue - the value is
                removed from the queue (?)
        -------------------------------------------------------
        """
        assert self._front is not None, "Cannot remove from an empty queue"
        _values = self._values
        _front = self._front
        
        value = _values[_front] #value to be removed, assigned to value, so it can be returned
        
        _values[_front] = None #removal
        
        self._front += 1 #move front to next value
        
        self._count -= 1 #decrease count
        
        return value
    
    

    def peek(self):
        """
        -------------------------------------------------------
        Peeks at the front of queue.
        Use: v = source.peek()
        -------------------------------------------------------
        Returns:
            value - a copy of the value at the front of the queue -
                the value is not removed from the queue (?)
        -------------------------------------------------------
        """
        assert self._count > 0, "Cannot peek at an empty queue"
        
        _values = self._values
        _front = self._front
        
        value = deepcopy(_values[_front])
        
        return value
    


    def __iter__(self):
        """
        USE FOR TESTING ONLY
        -------------------------------------------------------
        Generates a Python iterator. Iterates through the queue
        from front to rear.
        Use: for v in cq:
        -------------------------------------------------------
        Returns:
            value - the next value in the queue (?)
        -------------------------------------------------------
        """
        if self._front is not None:
            # queue is not empty
            j = self._front
            i = 0

            while i < self._count:
                yield self._values[j]
                i += 1
                j = (j + 1) % self._capacity