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

a Set class for python (Python recipe) by Thomas Heller
ActiveState Code (http://code.activestate.com/recipes/52258/)

A Set is a collection of items containing no duplicates.

Python, 46 lines
Download
 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
class Set:
    """A Set is a collection of items with no particular ordering,
    containing no dulicates."""
    def __init__(self, *args):
        self._dict = {}
        for arg in args:
            self.add(arg)

    def __repr__(self):
        import string
        return "%s(%s)" % (self.__class__.__name__,
                           string.join(map(repr, self._dict.values()), ', '))

    def extend(self, args):
        """Add several items at once."""
        for arg in args:
            self.add(arg)

    def add(self, item):
        """Add one item to the set."""
        self._dict[item] = item

    def remove(self, item):
        """Remove an item from the set."""
        del self._dict[item]

    def contains(self, item):
        """Check whether the set contains a certain item."""
        return self._dict.has_key(item)

    # Higher performance member-test for python 2.0 and above
    __contains__ = contains

    def __getitem__(self, index):
        """Support the 'for item in set:' protocol."""
        return self._dict.keys()[index]

    def __len__(self):
        """Return the number of items in the set."""
        return len(self._dict)

    def items(self):
        """Return a list containing all items."""
        return self._dict.keys()

# class Set()
Tags: oop

5 comments

Michael Strasser 23 years, 1 month ago  # | flag

Typo in __getitem__ definition. You accidentally forgot to close the doc string's triple quote:

"""Support the 'for item in set:' protocol."

instead of:

"""Support the 'for item in set:' protocol."""

Michael Strasser

Jay O'Connor 23 years, 1 month ago  # | flag

Close to a Bag. Since you are using dictionary keys to maintain uniqueness, you can add a value that would be a count of how many 'occurances' of a given object have been added to the Set, which would make it a Bag Jay O'Connor

Vivian De Smedt 23 years, 1 month ago  # | flag

union, substraction and intersection. Maybe it could be usefull to overload the operator (+, -, |, &, ^) to performe the classical set operations.

Here is a naive version of these operators.

def __add__(self, set):
        """Return the union of the set and an another set."""
        result = Set()
        for i in self:
            result.add(i)
        for i in set:
            result.add(i)
        return result

    def __sub__(self, set):
        """Return the difference between the set and an another set."""
        result = Set()
        for i in self:
            result.add(i)
        for i in set:
            if i in result:
                result.remove(i)
        return result

    def __and__(self, set):
        """Return the intersection of the set and an another set."""
        if len(self) < len(set):
            a = self
            b = set
        else:
            a = set
            b = self
        result = Set()
        for i in a:
            if i in b:
                result.add(i)
        return result

    __or__ = __add__

    def __xor__(self, set):
        """Return the union of the set and an another set but their intersection."""
        result = Set()
        for i in self:
            result.add(i)
        for i in set:
            if i in result:
                result.remove(i)
            else:
                result.add(i)
        return result

Vivian De Smedt

Alex Martelli 23 years, 1 month ago  # | flag

the contain method MUST use .has_key, NOT the in operator. The contain method must check self.dict.has_key(whatever) [which is O(1)], NOT whatever in self.dict.keys() [which is O(N)...]. Alex Martelli

Thomas Heller (author) 23 years ago  # | flag

Thanks, Alex, for the tip. Thomas Heller

Created by Thomas Heller on Fri, 16 Mar 2001 (PSF)
◄ Python recipes (4591) ►
◄ Thomas Heller's recipes (6) ►

Required Modules

Other Information and Tasks