HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Set Class Implementation ADT

Submitted by: @import:stackexchange-codereview··
0
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

Solution

Python already has built-in abstract base classes for sets and mutable sets — see the 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:
            pass


It'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:
            pass

Context

StackExchange Code Review Q#84396, answer score: 4

Revisions (0)

No revisions yet.