from copy import deepcopy """ The PyDev module 'test_Set.py' contains a few sample tests for some of the Set methods. The method 'print_set' is a testing method that shows you the complete contents of a Set object in human-readable form and can also be used for testing. """ class Set: """ ------------------------------------------------------- Data structure that contains a set of unique values, i.e. no values are repeated in a Set. Values stored in fixed-length Python list like in the Circular Queue. Do not use Python list methods that change the length of the list: append, insert, remove, pop, extend, delete Empty slots contain None. ------------------------------------------------------- Examples of Set attributes: _values = [None, None, None, None], _max_size = 4, _count = 0, _slot = 0 _values = [1, None, 9, None], _max_size = 4, _count = 2, _slot = 1 _values = [1, None, 9, 3], _max_size = 4, _count = 3, _slot = 1 _values = [1, 4, None, 3], _max_size = 4, _count = 3, _slot = 2 _values = [1, 4, 9, 3], _max_size = 4, _count = 4, _slot = None ------------------------------------------------------- """ # Default maximum size when max_size parameter is not provided DEFAULT_SIZE = 10 def __init__(self, max_size=DEFAULT_SIZE): """ ------------------------------------------------------- Efficiency: ------------------------------------------------------- Initializes an empty Set. Use: target = Set(max_size) Use: target = Set() # uses DEFAULT_SIZE ------------------------------------------------------- Parameters: max_size - maximum size of the set (int > 0) Returns: a new Set object (Set) ------------------------------------------------------- """ # Maximum size of Python list to store data. self._max_size = max_size # Python list that stores data - initialized to list of None. self._values = [None] * self._max_size # First available index for adding values -set to None if Set is full. self._slot = 0 # Number of unique values in Set. Cannot exceed _max_size. self._count = 0 def is_empty(self): """ ------------------------------------------------------- Efficiency:O(1) ------------------------------------------------------- Determines if the set is empty. In an empty set, all slots in _values contain None. Use: empty = source.is_empty() ------------------------------------------------------- Returns: True if the set is empty, False otherwise. ------------------------------------------------------- """ if len(self._values) > 0: b = False else: b = True return b def is_full(self): """ ------------------------------------------------------- Efficiency:O(1) ------------------------------------------------------- Determines if the set is full. In a full set, no slot in _values is None. Use: full = source.is_full() ------------------------------------------------------- Returns: True if the set is full, False otherwise. ------------------------------------------------------- """ def __len__(self): """ ------------------------------------------------------- Efficiency: ------------------------------------------------------- Returns the number of non-None values in the set. Use: n = len(source) ------------------------------------------------------- Returns: the number of values in the set. ------------------------------------------------------- """ # your code here def _linear_search(self, key): """ ------------------------------------------------------- Efficiency: ------------------------------------------------------- Searches for the occurrence of key in the set. Skips over None entries. (Private helper method - used only by other ADT methods.) Use: i = self._linear_search(key) ------------------------------------------------------- Parameters: key - a partial data element (?) Returns: i - the index of key in the set, -1 if key is not found (int) ------------------------------------------------------- """ # your code here
from copy import deepcopy
"""
The PyDev module 'test_Set.py' contains a few sample tests for some of the Set
methods. The method 'print_set' is a testing method that shows you the complete
contents of a Set object in human-readable form and can also be used for testing.
"""
class Set:
"""
-------------------------------------------------------
Data structure that contains a set of unique values,
i.e. no values are repeated in a Set.
Values stored in fixed-length Python list like in the Circular Queue.
Do not use Python list methods that change the length of the list:
append, insert, remove, pop, extend, delete
Empty slots contain None.
-------------------------------------------------------
Examples of Set attributes:
_values = [None, None, None, None], _max_size = 4, _count = 0, _slot = 0
_values = [1, None, 9, None], _max_size = 4, _count = 2, _slot = 1
_values = [1, None, 9, 3], _max_size = 4, _count = 3, _slot = 1
_values = [1, 4, None, 3], _max_size = 4, _count = 3, _slot = 2
_values = [1, 4, 9, 3], _max_size = 4, _count = 4, _slot = None
-------------------------------------------------------
"""
# Default maximum size when max_size parameter is not provided
DEFAULT_SIZE = 10
def __init__(self, max_size=DEFAULT_SIZE):
"""
-------------------------------------------------------
Efficiency:
-------------------------------------------------------
Initializes an empty Set.
Use: target = Set(max_size)
Use: target = Set() # uses DEFAULT_SIZE
-------------------------------------------------------
Parameters:
max_size - maximum size of the set (int > 0)
Returns:
a new Set object (Set)
-------------------------------------------------------
"""
# Maximum size of Python list to store data.
self._max_size = max_size
# Python list that stores data - initialized to list of None.
self._values = [None] * self._max_size
# First available index for adding values -set to None if Set is full.
self._slot = 0
# Number of unique values in Set. Cannot exceed _max_size.
self._count = 0
def is_empty(self):
"""
-------------------------------------------------------
Efficiency:O(1)
-------------------------------------------------------
Determines if the set is empty. In an empty set, all slots
in _values contain None.
Use: empty = source.is_empty()
-------------------------------------------------------
Returns:
True if the set is empty, False otherwise.
-------------------------------------------------------
"""
if len(self._values) > 0:
b = False
else:
b = True
return b
def is_full(self):
"""
-------------------------------------------------------
Efficiency:O(1)
-------------------------------------------------------
Determines if the set is full. In a full set, no slot
in _values is None.
Use: full = source.is_full()
-------------------------------------------------------
Returns:
True if the set is full, False otherwise.
-------------------------------------------------------
"""
def __len__(self):
"""
-------------------------------------------------------
Efficiency:
-------------------------------------------------------
Returns the number of non-None values in the set.
Use: n = len(source)
-------------------------------------------------------
Returns:
the number of values in the set.
-------------------------------------------------------
"""
# your code here
def _linear_search(self, key):
"""
-------------------------------------------------------
Efficiency:
-------------------------------------------------------
Searches for the occurrence of key in the set. Skips over None entries.
(Private helper method - used only by other ADT methods.)
Use: i = self._linear_search(key)
-------------------------------------------------------
Parameters:
key - a partial data element (?)
Returns:
i - the index of key in the set, -1 if key is not found (int)
-------------------------------------------------------
"""
# your code here
Step by step
Solved in 2 steps
