Implement a Queue ADT class that utilizes a circular buffer by completing the provided skeleton code in
Question:
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)
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill