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
|
# Copyright 2001 by Tarjei Mikkelsen. All rights reserved.
# This code is part of the Biopython distribution and governed by its
# license. Please see the LICENSE file that should have been included
# as part of this package.
class HashSet:
"""A set abstraction supporting the basic set operations.
This implementation requires that all elements are hashable,
which implies that elements must not mutate while contained.
"""
def __init__(self, elements = []):
"""Initializes a new HashSet."""
self.__elements = {}
for e in elements:
self.__elements[e] = 1
def __contains__(self, element):
"""Returns true iff this set contains element."""
return self.__elements.has_key(element)
def __eq__(self, set):
"""Returns true iff x == y for all elements in self, set."""
if not isinstance(set, HashSet):
return 0
for x in self.list():
if not (x in set): return 0
for x in set.list():
if not (x in self): return 0
return 1
def __len__(self):
"""Returns the number of elements in this set."""
return len(self.__elements)
def __ne__(self, set):
"""Returns true iff this set is not equal to set."""
return not self.__eq__(set)
def __repr__(self):
"""Returns a debugging string representation of this set."""
return "HashSet(" + repr(self.list()) + ")"
def __str__(self):
"""Returns a string representation of this set."""
return "{" + ",".join(map(str, self.list())) + "}"
# Element access:
def add(self, element):
"""Adds element to this set."""
self.__elements[element] = 1
def contains(self, element):
"""Returns true iff this set contains element."""
return self.__contains__(element)
def remove(self, element):
"""Removes element from this set."""
try:
del self.__elements[element]
except KeyError:
pass
def list(self):
"""Returns the elements of this set in a list."""
return self.__elements.keys()
# Information:
def empty(self):
"""Returns true iff this set is empty."""
return len(self.__elements) == 0
# Set operations:
def union(self, s):
"""Returns the union of this set and s."""
return HashSet(self.list() + s.list())
def intersection(self, s):
"""Returns the intersection of this set and s."""
return HashSet(filter(lambda e,s=s: e in s, self.list()))
def difference(self, s):
"""Returns the difference of this set and s."""
return HashSet(filter(lambda e,s=s: e not in s, self.list()))
def cartesian(self,s):
"""Returns the Cartesian product of this set and s."""
p = []
for i in self.list():
for j in s.list():
p.append((i,j))
return HashSet(p)
|
