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

A Set is a collection of items containing no duplicates.

Python, 46 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
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()

5 comments

Michael Strasser 23 years 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 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 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 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

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