# Imports from copy import deepcopy class _Set_Node: def __init__(self, value, next_): """ ------------------------------------------------------- Initializes a Set node that contains a copy of value and a link to another Set node. Use: node = _Set_Node(value, next_) ------------------------------------------------------- Parameters: value - value for node (?) next_ - another Set node (_Set_Node) Returns: a new _Set_Node object (_Set_Node) ------------------------------------------------------- """ self._value = deepcopy(value) self._next = next_ class Set: def __init__(self): """ ------------------------------------------------------- Initializes an empty Set. Use: target = Set() ------------------------------------------------------- """ self._front = None self._count = 0 def is_empty(self): """ ------------------------------------------------------- Determines if Set is empty. Use: empty = source.is_empty() ------------------------------------------------------- Returns: True if Set is empty, False otherwise. ------------------------------------------------------- """ # your code here return def __len__(self): """ ------------------------------------------------------- Returns the number of values in Set. Use: n = len(source) ------------------------------------------------------- Returns: the number of values in Set. ------------------------------------------------------- """ # your code here return def _linear_search(self, key): """ ------------------------------------------------------- Searches for key in Set. (Private helper method) Use: prev, curr = self._linear_search(key) ------------------------------------------------------- Parameters: key - a partial data element (?) Returns: prev - pointer to node prev to the node containing key (_Set_Node) curr - pointer to node containing key, None if not found (_Set_Node) ------------------------------------------------------- """ # your code here return def add(self, value): """ ------------------------------------------------------- Adds value to end of Set. Values may appear only once in the Set. Use: added = source.add(value) ------------------------------------------------------- Parameters: value - a comparable data element (?) Returns: added - True if value is added to Set, False otherwise (boolean) ------------------------------------------------------- """ # your code here return def remove(self, key): """ ------------------------------------------------------- Finds, removes, and returns value in Set that matches key. Returns None if no matching value. Use: value = source.remove(key) ------------------------------------------------------- Parameters: key - a partial data element (?) Returns: value - the value matching key, otherwise None (?) ------------------------------------------------------- """ # your code here return def remove_front(self): """ ------------------------------------------------------- Removes and returns first value in Set. Use: value = source.remove_front() ------------------------------------------------------- Returns: value - first value in Set (?) ------------------------------------------------------- """ assert self._front is not None, "Cannot remove from an empty set" # your code here return def find(self, key): """ ------------------------------------------------------- Returns a copy of value in Set that matches key, None if key is not found. Use: value = source.find(key) ------------------------------------------------------- Parameters: key - a partial data element (?) Returns: value - a copy of value matching key, otherwise None (?) ------------------------------------------------------- """ # your code here return
# Imports
from copy import deepcopy
class _Set_Node:
def __init__(self, value, next_):
"""
-------------------------------------------------------
Initializes a Set node that contains a copy of value
and a link to another Set node.
Use: node = _Set_Node(value, next_)
-------------------------------------------------------
Parameters:
value - value for node (?)
next_ - another Set node (_Set_Node)
Returns:
a new _Set_Node object (_Set_Node)
-------------------------------------------------------
"""
self._value = deepcopy(value)
self._next = next_
class Set:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty Set.
Use: target = Set()
-------------------------------------------------------
"""
self._front = None
self._count = 0
def is_empty(self):
"""
-------------------------------------------------------
Determines if Set is empty.
Use: empty = source.is_empty()
-------------------------------------------------------
Returns:
True if Set is empty, False otherwise.
-------------------------------------------------------
"""
# your code here
return
def __len__(self):
"""
-------------------------------------------------------
Returns the number of values in Set.
Use: n = len(source)
-------------------------------------------------------
Returns:
the number of values in Set.
-------------------------------------------------------
"""
# your code here
return
def _linear_search(self, key):
"""
-------------------------------------------------------
Searches for key in Set.
(Private helper method)
Use: prev, curr = self._linear_search(key)
-------------------------------------------------------
Parameters:
key - a partial data element (?)
Returns:
prev - pointer to node prev to the node containing key (_Set_Node)
curr - pointer to node containing key, None if not found (_Set_Node)
-------------------------------------------------------
"""
# your code here
return
def add(self, value):
"""
-------------------------------------------------------
Adds value to end of Set. Values may appear only once in the Set.
Use: added = source.add(value)
-------------------------------------------------------
Parameters:
value - a comparable data element (?)
Returns:
added - True if value is added to Set, False otherwise (boolean)
-------------------------------------------------------
"""
# your code here
return
def remove(self, key):
"""
-------------------------------------------------------
Finds, removes, and returns value in Set that matches key.
Returns None if no matching value.
Use: value = source.remove(key)
-------------------------------------------------------
Parameters:
key - a partial data element (?)
Returns:
value - the value matching key, otherwise None (?)
-------------------------------------------------------
"""
# your code here
return
def remove_front(self):
"""
-------------------------------------------------------
Removes and returns first value in Set.
Use: value = source.remove_front()
-------------------------------------------------------
Returns:
value - first value in Set (?)
-------------------------------------------------------
"""
assert self._front is not None, "Cannot remove from an empty set"
# your code here
return
def find(self, key):
"""
-------------------------------------------------------
Returns a copy of value in Set that matches key, None
if key is not found.
Use: value = source.find(key)
-------------------------------------------------------
Parameters:
key - a partial data element (?)
Returns:
value - a copy of value matching key, otherwise None (?)
-------------------------------------------------------
"""
# your code here
return
Step by step
Solved in 2 steps
