# INCOMPLETE IMPLEMENTATION OF CLASS BAG TO BE USED

# An implementation of ADT Bag that uses Python's dict type as the # underlying data structure.

import random

class Bag:

def __init__(self): """Initialize an empty bag.

>>> bag = Bag() >>> bag {} """ raise NotImplementedError("__init__ hasn't been implemented.")

def __str__(self) -> str: """Return a string representation of this bag.

>>> bag = Bag() >>> for x in ['a', 'b', 'c', 'd', 'c', 'b', 'a']: ... bag.add(x) ... >>> str(bag) "{'a': 2, 'b': 2, 'c': 2, 'd': 1}"

# Note: the order in which the items are listed may be different # from what is shown in this example. """ return str(self._items)

def __repr__(self) -> str: """Return a string representation of this bag. This string is identical to the one returned by __str__.

>>> bag = Bag() >>> for x in ['a', 'b', 'c', 'd', 'c', 'b', 'a']: ... bag.add(x) .... >>> repr(bag) "{'a': 2, 'b': 2, 'c': 2, 'd': 1}" >>> bag {'a': 2, 'b': 2, 'c': 2, 'd': 1}

# Note: the order in which the items are listed may be different # from what is shown in these examples. """ raise NotImplementedError("__repr__ hasn't been implemented.")

def __iter__(self): """Return an iterator for this bag.

>>> bag = Bag() >>> for x in ['a', 'b', 'c', 'd', 'c', 'b', 'a']: ... bag.add(x) ... >>> for x in bag: ... print(x) ... ('a', 2) # bag has two a's ('b', 2) # bag has two b's ('c', 2) # bag has two c's ('d', 1) # bag has one d """ # The iterator returned by this method produces a sequence of 2-tuples. # The first element in each tuple is an item in the bag, and the second # element is the number of occurrences of that item. return iter(self._items.items())

def add(self, item: str) -> None: """Add item to this bag.

>>> bag = Bag() >>> for x in ['c', 'a', 'b', 'c', 'd']: ... bag.add(x) ... >>> bag {'c': 2, 'a': 1, 'b': 1, 'd': 1}

# Note: the order in which the items are listed may be different # from what is shown in this example. """ raise NotImplementedError("add hasn't been implemented.")

def __len__(self) -> int: """Return the number of items in this bag.

>>> bag = Bag() >>> len(bag) 0 >>> for x in ['a', 'b', 'c', 'd', 'c', 'b', 'a']: ... bag.add(x) ... >>> len(bag) 7 """ raise NotImplementedError("__len__ hasn't been implemented.")

def __contains__(self, item: str) -> bool: """Return True if item is in the bag.

>>> bag = Bag() >>> for x in ['a', 'b', 'c', 'd']: ... bag.add(x) ... >>> 'b' in bag True >>> 'k' in bag False """ raise NotImplementedError("__contains__ hasn't been implemented.")

def count(self, item: str) -> int: """Return the total number of occurrences of item in this bag.

>>> bag = Bag() >>> for x in ['c', 'a', 'b', 'c', 'd']: ... bag.add(x) ... >>> bag {'c': 2, 'a': 1, 'b': 1, 'd': 1}

>>> bag.count('c') 2 >>> bag.count('k') 0 """ raise NotImplementedError("count hasn't been implemented.")

def remove(self, item: str) -> str: """Remove and return one instance of item from this bag.

Raises KeyError if the bag is empty. Raises ValueError if item is not in the bag.

>>> bag = Bag() >>> for x in ['c', 'a', 'b', 'c', 'd']: ... bag.add(x) ... >>> bag {'c': 2, 'a': 1, 'b': 1, 'd': 1}

>>> bag.remove('c') 'c' >>> bag {'c': 1, 'a': 1, 'b': 1, 'd': 1}

>>> bag.remove('c') 'c' >>> bag {'a': 1, 'b': 1, 'd': 1}

# Note: the order in which the items are listed may be different # from what is shown in these examples. """ raise NotImplementedError("remove hasn't been implemented.")

page. Open this file in Wing 101. It contains an incomplete implementation of class Bag. Two methods have been completed for you: - str returns a string representation of the bag. This method is simple: return str(self._items) Instance variable _items refers to the dict that stores the bag's contents. The method simply returns the string returned by the underlying dictionary's _str_ method. Liter__ returns an object that can be used to iterate over the bag. In other words, if shopping_bag refers to an instance of Bag, you can write: for item in shopping_bag: # Print the bag's contents one-by-one. print(item) A bag's iterator returns a sequence of the key/value pairs in the bag's dictionary. Each key/value pair is returned in a tuple. See the method's docstring for an example. "Stub" implementations have been provided for the other methods. If you call any of these methods on a Bag object, Python will throw a NotImplementedError exception. When implementing the methods, take advantage of the operations provided by type dict. All the methods, except remove, can be implemented with a single statement (but it's ok to have more than one statement in your function bodies). Hint: none of the methods require for loops or while loops. Exercise 1: Read the docstring for __init__. A Bag object should have one instance variable, names_items, which is initialized to an empty instance of Python's dict type. Replace the raise statement with a correct implementation of the method. Use this test to check if your method is correct: >>> bag = Bag() >>> bag._items {} # Shows that _items refers to an empty dict. Exercise 2: Read the docstring for repr_. Replace the raise statement with a correct implementation of the method. Use the shell to test _repr__. (You'll only be able to test if _repr__ works with an empty bag, because we don't yet have a way to put items in a bag.) Exercise 3: Read the docstring for add. Replace the raise statement with a correct implementation of the method. Use the shell to test add. Now that you can put items in a bag, you can also verify that __repr_works with a bag that contains one or more items. You should also run the example in the docstring for Liter__, to convince yourself that we can iterate over the items in a bag. Exercise 4: Try this experiment: >>> bag = Bag() >>> len(bag) In order for Python's built-in len function to work with Bag objects, we need to define a _len_ method in the class. Read the docstring for len__. Replace the raise statement with a correct implementation of the method. Use the shell to test_len__. Exercise 5: Try this experiment: = >>> bag Bag() >>> 'k' in bag In order for Python's in operator to work with Bag objects, we need to define a _contains method in the class. Read the docstring for _contains __. Replace the raise statement with a correct implementation of the method. Use the shell to test _contains_. Exercise 6: Read the docstring for count. Replace the raise statement with a correct implementation of the method. Use the shell to test count. Exercise 7: Read the docstring for remove. Replace the raise statement with a correct implementation of the method. When the bag is empty, the method should raise a KeyError exception that displays the message, "bag.remove(x): remove from empty bag". 3 page. Open this file in Wing 101. It contains an incomplete implementation of class Bag. Two methods have been completed for you: - str returns a string representation of the bag. This method is simple: return str(self._items) Instance variable _items refers to the dict that stores the bag's contents. The method simply returns the string returned by the underlying dictionary's _str_ method. Liter__ returns an object that can be used to iterate over the bag. In other words, if shopping_bag refers to an instance of Bag, you can write: for item in shopping_bag: # Print the bag's contents one-by-one. print(item) A bag's iterator returns a sequence of the key/value pairs in the bag's dictionary. Each key/value pair is returned in a tuple. See the method's docstring for an example. "Stub" implementations have been provided for the other methods. If you call any of these methods on a Bag object, Python will throw a NotImplementedError exception. When implementing the methods, take advantage of the operations provided by type dict. All the methods, except remove, can be implemented with a single statement (but it's ok to have more than one statement in your function bodies). Hint: none of the methods require for loops or while loops. Exercise 1: Read the docstring for __init__. A Bag object should have one instance variable, names_items, which is initialized to an empty instance of Python's dict type. Replace the raise statement with a correct implementation of the method. Use this test to check if your method is correct: >>> bag = Bag() >>> bag._items {} # Shows that _items refers to an empty dict. Exercise 2: Read the docstring for repr_. Replace the raise statement with a correct implementation of the method. Use the shell to test _repr__. (You'll only be able to test if _repr__ works with an empty bag, because we don't yet have a way to put items in a bag.) Exercise 3: Read the docstring for add. Replace the raise statement with a correct implementation of the method. Use the shell to test add. Now that you can put items in a bag, you can also verify that __repr_works with a bag that contains one or more items. You should also run the example in the docstring for Liter__, to convince yourself that we can iterate over the items in a bag. Exercise 4: Try this experiment: >>> bag = Bag() >>> len(bag) In order for Python's built-in len function to work with Bag objects, we need to define a _len_ method in the class. Read the docstring for len__. Replace the raise statement with a correct implementation of the method. Use the shell to test_len__. Exercise 5: Try this experiment: = >>> bag Bag() >>> 'k' in bag In order for Python's in operator to work with Bag objects, we need to define a _contains method in the class. Read the docstring for _contains __. Replace the raise statement with a correct implementation of the method. Use the shell to test _contains_. Exercise 6: Read the docstring for count. Replace the raise statement with a correct implementation of the method. Use the shell to test count. Exercise 7: Read the docstring for remove. Replace the raise statement with a correct implementation of the method. When the bag is empty, the method should raise a KeyError exception that displays the message, "bag.remove(x): remove from empty bag". 3