Question
I only need part 2! Please write test cases that may fail the unknown buggy code using the hint. from __future__ import annotations from typing
I only need part 2! Please write test cases that may fail the unknown buggy code using the hint.
from __future__ import annotations from typing import Any, Optional
class _Node: """A node in a linked list.
Note that this is considered a "private class", one which is only meant to be used in this module by the LinkedList class, but not by client code.
=== Attributes === item: The data stored in this node. next: The next node in the list, or None if there are no more nodes. """ item: Any next: Optional[_Node]
def __init__(self, item: Any) -> None: """Initialize a new node storing
class LinkedList: """A linked list implementation of the List ADT. """ # === Private Attributes === # _first: # The first node in the linked list, or None if the list is empty. # curr : cursor pointing to nodes during the run
_first: Optional[_Node]
def __init__(self) -> None: """Initialize an empty linked list. """ self._first = None
def print_items(self) -> None: """Print out each item in this linked list.""" curr = self._first while curr is not None: print(curr.item) curr = curr.next
########################################################################## # Part 1 # # For each of the following linked list methods, read its docstring # and the complete its implementation. # You should use the provided *linked list traversal* code template # as your starting point, but of course you should modify it as necessary! # # NOTE: the first two methods are new special methods (you can tell by the # double underscores), and enable some special Python behaviour that we've # illustrated in the doctests. # # At the bottom of this file, we've included some helpers # to create some basic linked lists for our doctests. ##########################################################################
def __len__(self) -> int: """Return the number of elements in this list.
>>> lst = LinkedList() >>> len(lst) # Equivalent to lst.__len__() 0 >>> lst = three_items(1, 2, 3) >>> len(lst) 3 """ curr = self._first 1 = 0 while curr is not None: 1 += 1 curr = curr.next return count
def __contains__(self, item: Any) -> bool: """Return whether
Use == to compare items.
>>> lst = three_items(1, 2, 3) >>> 2 in lst # Equivalent to lst.__contains__(2) True >>> 4 in lst False """ curr = self._first while curr is not None: if curr.item == item: return True curr = curr.next return False
# HINTS: for this one, you'll be adding a new item to a linked list. # 1. Create a new _Node object first. # 2. Consider the cases where the list is empty and non-empty separately. # 3. For the non-empty case, you'll first need to iterate to the # *last node* in the linked list. (Review this prep's Quercus quiz!) def append(self, item: Any) -> None: """Append
>>> lst = LinkedList() >>> lst.append(1) >>> lst._first.item 1 >>> lst.append(2) >>> lst._first.next.item 2 """ n = Node(item)
curr = self._first
if curr is None:
self._first = n
else:
while curr.next is not None:
curr = curr.next
curr.next = n # ------------------------------------------------------------------------ # Helpers for creating linked lists (testing purposes only) # You may use these to help you construct a LinkedList # Do NOT change these helper functions. # ------------------------------------------------------------------------ def one_item(x: Any) -> LinkedList: """Return a linked list containing the given item.""" lst = LinkedList() node = _Node(x) lst._first = node return lst
def three_items(x1: Any, x2: Any, x3: Any) -> LinkedList: """Return a linked list containing the given three items.""" lst = LinkedList() node1 = _Node(x1) node2 = _Node(x2) node3 = _Node(x3) node1.next = node2 node2.next = node3 lst._first = node1 return lst
# Part 2 # In this part of the prep, you are to write test cases for the __contains__ # method. # # We will run your tests on a correct version of prep5.py, as well as a version # with an undisclosed bug in the __contains__ method. We will not give you # hints as to what the bug is, so test thoroughly! # # When you are done, run the automated self-test on MarkUs. If you pass the # test case named 'test_contains_test_cases': congratulations! You've found # the bug, and you're done with this part. # # You may write as many test cases as you want. However, your test cases must # fulfill the following requirements: # - All of your tests must pass on our correct version of prep5.py # - At least one of your tests must fail on the version with a bug. # # Make sure your tests all have different names that start with test_! # # You may assume __len__ and append work properly in both versions of prep5.py # that we run your test cases on. # # Hint: Try to think about the different LinkedLists you could have: # - Consider both the length of the LinkedList, and its content. # - Consider the item being searched for: its position, and whether # it's in the LinkedList at all. # There are many different combinations for you to try. ################################################################################
# Below are provided sample test cases for your use. You are encouraged # to add additional test cases. # WARNING: THIS IS AN EXTREMELY INCOMPLETE SET OF TESTS! # Add your own to practice writing tests and to be confident your code is # correct. def test_len_empty() -> None: """Test LinkedList.__len__ for an empty linked list.""" lst = LinkedList() assert len(lst) == 0
def test_len_three() -> None: """Test LinkedList.__len__ on a linked list of length 3.""" lst = LinkedList() node1 = _Node(10) node2 = _Node(20) node3 = _Node(30) node1.next = node2 node2.next = node3 lst._first = node1
assert len(lst) == 3
def test_contains_doctest() -> None: """Test LinkedList.__contains__ on the given doctest.""" lst = LinkedList() node1 = _Node(1) node2 = _Node(2) node3 = _Node(3) node1.next = node2 node2.next = node3 lst._first = node1
assert (2 in lst) is True assert (4 in lst) is False
def test_append_empty() -> None: """Test LinkedList.append on an empty list.""" lst = LinkedList() lst.append(1) assert lst._first.item == 1
def test_append_one() -> None: """Test LinkedList.append on a list of length 1.""" lst = LinkedList() lst._first = _Node(1) lst.append(2) assert lst._first.next.item == 2
if __name__ == '__main__': import pytest pytest.main(['prep5_starter_tests.py'])
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started