Welcome, guest | Sign In | My Account | Store | Cart

This is a pure Pythonic implementation of a set class. The syntax and methods implemented are, for the most part, borrowed from PEP 218 by Greg Wilson.

Python version: 2.2

Python, 130 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class Set:
    """The set class. It can contain mutable objects."""

    def __init__(self, seq = None):
        """The constructor. It can take any object giving an iterator as an optional
        argument to populate the new set."""
        self.elems = []
        if seq:
            for elem in seq:
                if elem not in self.elems:
                    self.elems.append(elem)

    def __str__(self):
        return "{%s}" % ", ".join(map(str, self.elems))


    def copy(self):
        """Shallow copy of a set object."""
        return Set(self.elems)

    def __contains__(self, elem):
        return elem in self.elems

    def __len__(self):
        return len(self.elems)

    def items(self):
        """Returns a list of the elements in the set."""
        return self.elems

    def add(self, elem):
        """Add one element to the set."""
        if elem not in self.elems:
            self.elems.append(elem)

    def remove(self, elem):
        """Remove an element from the set. Return an error if elem is not in the set."""
        try:
            self.elems.remove(elem)
        except ValueError:
            raise LookupError, "Object %s is not a member of the set." % str(elem)

    def discard(self, elem):
        """Remove an element from the set. Do nothing if elem is not in the set."""
        try:
            self.elems.remove(elem)
        except ValueError:
            pass

    #Define an iterator for a set.
    def __iter__(self):
        return iter(self.elems)

    #The basic binary operations with sets.
    def __or__(self, other):
        """Union of two sets."""
        ret = self.copy()
        for elem in other.elems:
            if elem not in ret:
                ret.elems.append(elem)
        return ret

    def __sub__(self, other):
        """Difference of two sets."""
        ret = self.copy()
        for elem in other.elems:
            ret.discard(elem)
        return ret

    def __and__(self, other):
        """Intersection of two sets."""
        ret = Set()
        for elem in self.elems:
            if elem in other.elems:
                ret.elems.append(elem)
        return ret

    def __add__(self, other):
        """Symmetric difference of two sets."""
        ret = Set()
        temp = other.copy()
        for elem in self.elems:
            if elem in temp.elems:
                temp.elems.remove(elem)
            else:
                ret.elems.append(elem)
        #Add remaining elements.
        for elem in temp.elems:
                ret.elems.append(elem)
        return ret

    def __mul__(self, other):
        """Cartesian product of two sets."""
        ret = Set()
        for elemself in self.elems:
            ret.elems.extend([(elemself, elemother) for elemother in other.elems])
        return ret

    #Some of the binary comparisons.
    def __lt__(self, other):
        """Returns 1 if the lhs set is contained but not equal to the rhs set."""
        if len(self.elems) < len(other.elems):
            temp = other.copy()
            for elem in self.elems:
                if elem in temp.elems:
                    temp.remove(elem)
                else:
                    return 0
            return len(temp.elems) == 0
        else:
            return 0

    def __le__(self, other):
        """Returns 1 if the lhs set is contained in the rhs set."""
        if len(self.elems) <= len(other.elems):
            ret = 1
            for elem in self.elems:
                if elem not in other.elems:
                    ret = 0
                    break
            return ret
        else:
            return 0

    def __eq__(self, other):
        """Returns 1 if the sets are equal."""
        if len(self.elems) != len(other.elems):
            return 0
        else:
            return len(self - other) == 0

Implementation Issues: To satisfy the requirement that a set can hold mutables we had to forego the dictionary implementation in favor of a list. This implies a loss of performance since every lookup operation is O(n) and not O(1).

Since there are several loops floating around, especially when binary operations are involved, speed could be gained by implementing this in a compiled language and then have it available in Python.

All the algorithms rely in making simple checks for equality. It is the responsability of the user to ensure that the objects he puts in a set provide the right notion of equality, that is, deep equality and not shallow.

Syntax Issues: The symmetric difference is denoted by + instead of ^. This is reasonable, not only because this notation is used throughout the mathematical community but also because symmetric difference has all the properties one could hope for a reasonable addition (e.g. commutativity, associativity, etc.).

6 comments

David Lees 19 years, 11 months ago  # | flag

Minor glitch. I think there is a pair of minor bugs. In order to try this class without getting a syntax error I had to change

del self.elems.remove(elem)

to

self.elems.remove(elem)

in both the remove and discard methods

Gonçalo Rodrigues (author) 19 years, 11 months ago  # | flag

Changed... You are absolutely right.

thwaps himself on the head for being so distracted

Gonçalo Rodrigues (author) 19 years, 11 months ago  # | flag

Added. took the opportunity of correcting the minor glitch and overloaded multiplication with cartesian product.

Martin Schmettow 18 years, 10 months ago  # | flag

sort is missing. Nearly trivial, but the sort method is missing. Suggestion:

def sort(self, func = cmp):
        self.elems.sort(func)
Tim Golden 18 years, 6 months ago  # | flag

For those of use who have to use Python 2.1 for some reason... ... could I suggest the following addition?

def __getitem__ (self, index):
  return self.elems[index]

This gives the class all that's needed to run under 2.1 (afaict). The __iter__ won't matter because 2.1 will just ignore it. I don't think that 2.2 will be bothered by the __getitem__ either: it just means that some can do a -- potentially meaningless -- lookup of a set item by index.

Gonçalo Rodrigues (author) 18 years, 6 months ago  # | flag

Not really. sets have no order and implementations are free to swap the order of the elements around as much as they want. It is only the fact that the underlying implementation uses a list that gives an idea of order. Just imagine a set for hashables-only implemented via dicts to see where I'm getting at. If you want a sorted list of the elements just ask for it:

lst = list(my_set)
lst.sort()
Created by Gonçalo Rodrigues on Wed, 9 Jan 2002 (PSF)
Python recipes (4591)
Gonçalo Rodrigues's recipes (9)

Required Modules

  • (none specified)

Other Information and Tasks