Set Class Implementation ADT

Question

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 )
    return newSet                           

   # Creates a new set from the intersection: self set and setB.
   def intersect( self, setB ):
    newSet = Set()
    for i in range(self._theElements) :
        for j in range(setB._theElements) :
            if self._theElements[i] == setB._theElements[j] :
                self.theElements.append(setB)
    return newSet

# Creates a new set from the difference: self set and setB.
def difference( self, setB ):
    newSet = Set()
    newSet._theElements.extend( self._theElements )
    for element in setB :
        if element in self :
            newSet._theElements.remove( element )
    return newSet

 # Creates the iterator for the self
def __iter__( self ):
    return iter(self._theElements)

Answer 1

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.

Answer 2

I'd recommend that you read PEP 8, which contains the community style guide for Python code. Pythonistas get very picky about code formatting and style conventions. In particular, see Pet Peeves, which recommends against writing:

def len( self ):
    return len( self.theElements )

in favor of:

def len(self):
    return len(self.theElements)

without the extra whitespace inside the parentheses.

Of course, a foolish consistency is the hobgoblin of small minds, but it's good to be aware of PEP 8 so that when you go against it, you do so knowingly and for a good reason.

The community is sort of lukewarm on using an initial underscore to indicate a "private" member check this and note how ambivalent everyone seems about the convention. After spending some time with Clojure, I never use any kind of "private" modifier in Python, but I'm sort of an extremist in that regard, and it can be useful if you're writing code that will be used by lots of other people.

On to more specific things. The list constructor can take another iterable as a parameter, and will automatically add all the elements of that iterable to the newly created list. So you could write your __init__ method like this:

def __init__(self, *args):
    self._theElements = list(args)

It seems unnecessary to use an assertion to have remove require that items to be removed are actually in the set. Assertions are typically more for checking that things which should never happen ever haven't happened; they essentially say "This condition is so disastrous that if it does happen, the entire system should just die", and as such, they're usually more useful in development, where you want the entire system to die so you can debug your code.

Your code using the set might not ever need to care that it tried to remove something which hadn't been added, in which case you could write something like this:

def remove(self, element):
    try:
        self._theElements.remove(element)
    except ValueError:
        pass

Or there might be some cases where you need to care. Then I'd recommend something like this:

def remove(self, element):
    try:
        self._theElements.remove(element)
    except ValueError:
         raise ValueError("The element {0} is not in the set".format(element))

Or like this, with return codes:

def remove(self, element):
    try:
        self._theElements.remove(element)
    except ValueError:
        return None
    else:
        # Executed when no exceptions raised.
        return self

The main argument in favor of the second version is that with this, users of the set can sometimes care that the item they tried to delete wasn't in the set, and other times can ignore it. The first version forces them to always care. Also note that I threw a new ValueError in the first version so I could add a more descriptive message.

I favor one of these three options because I can't foresee many circumstances where the set not containing the element you tried to delete is so disastrous that the entire system should just die. But if that is what you want, you can still have the client code kill the entire system on a ValueError or on a return value of None.

If you're interested in extending this class, there are a few tricks you could play around with that might help performance in some cases. One would be to keep your list of elements sorted, and use a binary search to check if the set contains a particular element. You could have add sort the list, and then have __contains__ call out to a binary search function. This will also make searching for duplicates faster. If you're dealing with custom objects, you can make them sortable like this.

For the most part, you've done a good job implementing a set ADT and have exercised a lot of the neat OO features of Python, like overriding __contains__. The issues I brought up are pretty minor in all. If you ever really need a set in Python, though, I recommend using the built-in set; it's backed by a C hash table and is amazingly fast, as Python code goes.

Answer 3

If you're looking to reinvent the wheel using fundamental types supported by Python, a dictionary would have more appropriate performance characteristics than a list. In particular, you get constant-time lookups of dictionary keys. Basically, a set is just a dictionary in which you care only about the keys and not the values.

Lest you think that using a dict is cheating, bear in mind that every object in Python is dictionary-like. Simply calling a method on an object uses object.__getattribute__(), which is essentially a dictionary lookup.

Answer 4

There are couple of points i would make different.

Equality means each member of both sets must be equal, having a set, subset of an another doesn't mean they are equal.

In python sets data are sorted. We can take advantage of sorted data in __eq__ method.

Also union could be simplified as in following.

import itertools

class Set:
    def __init__(self, *xs):
        seen = []
        for x in xs:
            if x not in seen:
                seen.append(x)
        self.data = sorted(seen)

    def __eq__(self, other):
        if len(self) != len(other):
            return False
        eq_pairs = list(itertools.takewhile(lambda pair: pair[0] == pair[1], zip(self, other)))
        return len(eq_pairs) == len(self)

    def union(self, other):
        return Set(*(self.data + other.data))