Implement a Queue ADT class that utilizes a circular buffer by completing the provided skeleton code in the file queue_sa.py. You will use the Static Array data structure from previous assignments as the underlying storage for your Queue ADT. YOU CANNOT USE ANY BUILT-IN PYTHON DATA STRUCTURES! This includes lists, dicts, etc.. only variables are permitted. The static array class file is all you need to mess with these "data structures"

You must solve this portion of the assignment by importing the StaticArray class provided in Assignment 1, and using class methods to write
your solution. You are also not allowed to directly access any variables of the StaticArray class (self._sa._size and self._sa._data). All work must be done by only using class
methods.

Help with enqueue and dequeue methods, for the queue class. they both rely on each other. I think I have the front method working correctly. I will provide below both the static array class, and the queue class, which relies on the static array class as an import. I've got it almost working, but both methods are still failing test cases. I'll post those failing test cases below.

TEST THAT IS FAILING:

 

Description : This is a test with random elements. It requires enqueue() and dequeue()
 

Input       : QUEUE: 4 element(s). [30000, 81300, -52000, -67777], enqueue(20000)

Expected    : QUEUE: 5 element(s). [30000, 81300, -52000, -67777, 20000]

Student     : QUEUE: 5 element(s). [-67777, 30000, 81300, -52000, 20000]

Queues are different.

 

HERE IS THE STATIC ARRAY CLASS CODE NEEDED, you do not need to do anything to this class:

 

class StaticArrayException(Exception):
    """
    Custom exception for Static Array class.
    Any changes to this class are forbidden.
    """
    pass


class StaticArray:
    """
    Implementation of Static Array Data Structure.
    Implemented methods: get(), set(), length()

    Any changes to this class are forbidden.

    Even if you make changes to your StaticArray file and upload to Gradescope
    along with your assignment, it will have no effect. Gradescope uses its
    own StaticArray file (a replica of this one) and any extra submission of
    a StaticArray file is ignored.
    """

    def __init__(self, size: int = 10) -> None:
        """
        Initialize all elements with values of None.
        If requested size is not a positive number,
        raise StaticArray Exception.
        """
        if size < 1:
            raise StaticArrayException('Array size must be a positive integer')

        # The underscore denotes this as a private variable and
        # private variables should not be accessed directly.
        # Use the length() method to get the size of a StaticArray.
        self._size = size

        # Remember, this is a built-in list and is used here
        # because Python doesn't have a fixed-size array type.
        # Don't initialize variables like this in your assignments!
        self._data = [None] * size

    def __iter__(self) -> None:
        """
        Disable iterator capability for StaticArray class.
        This means loops and aggregate functions like
        those shown below won't work:

        arr = StaticArray()
        for value in arr:     # will not work
        min(arr)              # will not work
        max(arr)              # will not work
        sort(arr)             # will not work
        """
        return None

    def __str__(self) -> str:
        """Override string method to provide more readable output."""
        return f"STAT_ARR Size: {self._size} {self._data}"

    def get(self, index: int):
        """
        Return value from given index position.
        Invalid index raises StaticArrayException.
        """
        if index < 0 or index >= self.length():
            raise StaticArrayException('Index out of bounds')
        return self._data[index]

    def set(self, index: int, value) -> None:
        """
        Store value at given index in the array.
        Invalid index raises StaticArrayException.
        """
        if index < 0 or index >= self.length():
            raise StaticArrayException('Index out of bounds')
        self._data[index] = value

    def __getitem__(self, index: int):
        """Enable bracketed indexing."""
        return self.get(index)

    def __setitem__(self, index: int, value: object) -> None:
        """Enable bracketed indexing."""
        self.set(index, value)

    def length(self) -> int:
        """Return length of the array (number of elements)."""
        return self._size


if __name__ == "__main__":

    # Using the Static Array #

    # Can use either the get/set methods or [] (bracketed indexing)         #
    # Both are public methods; using the [] calls the corresponding get/set #

    # new StaticArray object - is the default size
    arr = StaticArray()

    # These two statements are equivalent
    arr.set(0, 'hello')
    arr[0] = 'hello'

    # These two statements are equivalent
    print(arr.get(0))
    print(arr[0])

    # Print the number of elements stored in the array
    print(arr.length())

    # new StaticArray object to store 5 elements
    arr = StaticArray(5)

    # Set the value of each element equal to its index multiplied by 10
    for index in range(arr.length()):
        arr[index] = index * 10

    # Print the values of all elements in reverse order
    for index in range(arr.length() - 1, -1, -1):
        print(arr[index])

    # Special consideration below #

    # Don't ! This creates a built-in Python list and if you use
    # one you'll lose points.
    forbidden_list = [None] * 10

    print(type(arr))
    print(type(forbidden_list))

 

HERE IS THE CLASS I NEED HELP WITH, METHODS ENQUEUE AND DEQUEUE:
 

_double_queue is a helper method that can be edited.

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

from static_array import StaticArray


class QueueException(Exception):
    """Custom exception to be used by Queue class."""
    pass


class Queue:
    def __init__(self) -> None:
        """Initialize new queue based on Static Array."""
        self._sa = StaticArray(4)
        self._front = 0
        self._back = -1
        self._current_size = 0

    def __str__(self) -> str:
        """Override string method to provide more readable output."""

        size = self._current_size
        out = "QUEUE: " + str(size) + " element(s). ["

        front_index = self._front
        for _ in range(size - 1):
            out += str(self._sa[front_index]) + ', '
            front_index = self._increment(front_index)

        if size > 0:
            out += str(self._sa[front_index])

        return out + ']'

    def is_empty(self) -> bool:
        """Return True if the queue is empty, False otherwise."""
        return self._current_size == 0

    def size(self) -> int:
        """Return number of elements currently in the queue."""
        return self._current_size

    def print_underlying_sa(self) -> None:
        """Print underlying StaticArray. Used for testing purposes."""
        print(self._sa)

    def _increment(self, index: int) -> int:
        """Move index to next position."""

        # employ wraparound if needed
        index += 1
        if index == self._sa.length():
            index = 0

        return index

    # ---------------------------------------------------------------------- #

    def enqueue(self, value: object) -> None:
        """
        This method adds a new value to the end of the queue. It must be implemented with
        O(1) amortized runtime complexity.
        """
        if self._current_size == self._sa.length():
            self._double_queue()
        self._back = self._increment(self._back)
        self._sa.set(self._back, value)
        self._current_size += 1

    def dequeue(self) -> object:
        """
        This method removes and returns the value at the beginning of the queue. It must be
        implemented with O(1) runtime complexity. If the queue is empty, the method raises a
        custom "QueueException". Code for the exception is provided in the skeleton file.
        """
        if self.is_empty():
            raise QueueException
        item = self._sa.get(self._front)
        self._front = self._increment(self._front)
        self._current_size -= 1
        return item

    def front(self) -> object:
        """
        This method returns the value of the front element of the queue without removing it. It
        must be implemented with O(1) runtime complexity. If the queue is empty, the
        method raises a custom "QueueException". Code for the exception is provided in the
        skeleton file.
        """
        if self.is_empty():
            raise QueueException
        else:
            return self._sa.get(self._front)

    # The method below is optional, but recommended, to implement. #
    # You may alter it in any way you see fit.                     #

    def _double_queue(self) -> None:
        """
        TODO:  implementation
        """
        old_size = self._sa.length()
        new_size = old_size * 2
        newArr = StaticArray(new_size)

        for index in range(old_size):
            item = self._sa.get(index)
            newArr.set(index, item)

        self._sa = newArr
        self._front = 0
        self._back = old_size - 1

# ------------------- BASIC TESTING -----------------------------------------

if __name__ == "__main__":

    print("# Basic functionality tests #")
    print("# enqueue()")
    q = Queue()
    print(q)
    for value in [1, 2, 3, 4, 5]:
        q.enqueue(value)
    print(q)

    print("# dequeue()")
    q = Queue()
    for value in [1, 2, 3, 4, 5]:
        q.enqueue(value)
    print(q)
    for _ in range(q.size() + 1):
        try:
            print(q.dequeue())
        except Exception as e:
            print("No elements in queue", type(e))
    for value in [6, 7, 8, 111, 222, 3333, 4444]:
        q.enqueue(value)
    print(q)
    q.print_underlying_sa()

    print("# front()")
    q = Queue()
    print(q)
    for value in ['A', 'B', 'C', 'D']:
        try:
            print(q.front())
        except Exception as e:
            print("No elements in queue", type(e))
        q.enqueue(value)
    print(q)

    print("# Circular buffer tests: #")

    def action_and_print(
            header: str, action: callable, values: [], queue: Queue) -> None:
        """
        Print header, perform action,
        then print queue and its underlying storage.
        """
        print(header)
        if values:
            for value in values:
                action(value)
        else:
            action()
        print(queue)
        queue.print_underlying_sa()
        print()

    q = Queue()

    # action_and_print("# Enqueue: 2, 4, 6, 8", q.enqueue, [2, 4, 6, 8], q)

    # Calling the action_and_print() function declared two lines above,
    # would be equivalent to the following lines of code:
    print("# Enqueue: 2, 4, 6, 8")
    test_case = [2, 4, 6, 8]
    for value in test_case:
        q.enqueue(value)
    print(q)
    q.print_underlying_sa()
    print()

    action_and_print("# Dequeue a value", q.dequeue, [], q)
    action_and_print("# Enqueue: 10", q.enqueue, [10], q)
    action_and_print("# Enqueue: 12", q.enqueue, [12], q)

    print("# Dequeue until empty")
    while not q.is_empty():
        q.dequeue()
    print(q)
    q.print_underlying_sa()
    print()

    action_and_print("# Enqueue: 14, 16, 18", q.enqueue, [14, 16, 18], q)
    action_and_print("# Enqueue: 20", q.enqueue, [20], q)
    action_and_print("# Enqueue: 22, 24, 26, 28", q.enqueue,
                     [22, 24, 26, 28], q)
    action_and_print("# Enqueue: 30", q.enqueue, [30], q)