patternpythonMinor
Set Class Implementation ADT
Viewed 0 times
implementationclasssetadt
Problem
Is the following functions implemented correctly for the set class?
Please let me know if any changes need to be made.
```
# Implementation of the Set ADT using a Python list.
class Set :
# Creates an empty set instance.
def __init__( self, *initElements ):
self._theElements = list()
for i in range(len(initElements)) :
self._theElements.add( initElements )
# Returns the number of items in the set.
def __len__( self ):
return len( self._theElements )
# Determines if an element is in the set.
def __contains__( self, element ):
return element in self._theElements
# Determines if the set is empty.
def isEmpty( self ):
return len(self._theElements) == 0
# Adds a new unique element to the set.
def add( self, element ):
if element not in self :
self._theElements.append( element )
# Removes an element from the set.
def remove( self, element ):
assert element in self, "The element must be in the set."
self._theElements.remove( element )
# Determines if this set is equal to setB.
def __eq__( self, setB ):
if len( self ) != len( setB ) :
return False
else :
return self.isSubsetOf( setB )
# Determines if this set is a subset of setB.
def isSubsetOf( self, setB ):
for element in self :
if element not in setB :
return False
return True
# Determines if this set is a proper subset of setB.
def isProperSubset( self, setB ):
for element in self :
if self != setB :
return True
return False
# Creates a new set from the union of this set and setB.
def union( self, setB ):
newSet = Set()
newSet._theElements.extend( self._theElements )
for element in setB :
if element not in self :
newSet._theElements.append( element )
re
Please let me know if any changes need to be made.
```
# Implementation of the Set ADT using a Python list.
class Set :
# Creates an empty set instance.
def __init__( self, *initElements ):
self._theElements = list()
for i in range(len(initElements)) :
self._theElements.add( initElements )
# Returns the number of items in the set.
def __len__( self ):
return len( self._theElements )
# Determines if an element is in the set.
def __contains__( self, element ):
return element in self._theElements
# Determines if the set is empty.
def isEmpty( self ):
return len(self._theElements) == 0
# Adds a new unique element to the set.
def add( self, element ):
if element not in self :
self._theElements.append( element )
# Removes an element from the set.
def remove( self, element ):
assert element in self, "The element must be in the set."
self._theElements.remove( element )
# Determines if this set is equal to setB.
def __eq__( self, setB ):
if len( self ) != len( setB ) :
return False
else :
return self.isSubsetOf( setB )
# Determines if this set is a subset of setB.
def isSubsetOf( self, setB ):
for element in self :
if element not in setB :
return False
return True
# Determines if this set is a proper subset of setB.
def isProperSubset( self, setB ):
for element in self :
if self != setB :
return True
return False
# Creates a new set from the union of this set and setB.
def union( self, setB ):
newSet = Set()
newSet._theElements.extend( self._theElements )
for element in setB :
if element not in self :
newSet._theElements.append( element )
re
Solution
Python already has built-in abstract base classes for sets and mutable sets — see the
Here's how you might extend the recipe to a mutable set:
It's also worth having a look at the implementation of the abstract base classes in
collections.abc module. There's even a recipe in the documentation for implementing an immutable set by inheriting from collections.abc.Set and storing the elements in a list.Here's how you might extend the recipe to a mutable set:
from collections.abc import MutableSet
class ListBasedMutableSet(MutableSet):
def __init__(self, iterable=()):
self.elements = []
for item in iterable:
self.add(item)
def __contains__(self, item):
return item in self.elements
def __iter__(self):
return iter(self.elements)
def __len__(self):
return len(self.elements)
def add(self, item):
if item not in self.elements:
self.elements.append(item)
def discard(self, item):
try:
del self.elements[self.elements.index(item)]
except ValueError:
passIt's also worth having a look at the implementation of the abstract base classes in
_collections_abc.py.Code Snippets
from collections.abc import MutableSet
class ListBasedMutableSet(MutableSet):
def __init__(self, iterable=()):
self.elements = []
for item in iterable:
self.add(item)
def __contains__(self, item):
return item in self.elements
def __iter__(self):
return iter(self.elements)
def __len__(self):
return len(self.elements)
def add(self, item):
if item not in self.elements:
self.elements.append(item)
def discard(self, item):
try:
del self.elements[self.elements.index(item)]
except ValueError:
passContext
StackExchange Code Review Q#84396, answer score: 4
Revisions (0)
No revisions yet.