1.1 --- a/lib/__builtins__/set.py Sat Feb 04 17:49:34 2017 +0100
1.2 +++ b/lib/__builtins__/set.py Sat Feb 04 18:10:20 2017 +0100
1.3 @@ -20,22 +20,94 @@
1.4 """
1.5
1.6 from __builtins__.iteration.iterator import itemiterator
1.7 +from __builtins__.mapping import hashtable
1.8
1.9 -class frozenset:
1.10 - def __init__(self, iterable): pass
1.11 +class frozenset(hashtable):
1.12 +
1.13 + "An immutable set representation holding a collection of distinct values."
1.14 +
1.15 + def __init__(self, iterable=None):
1.16 +
1.17 + "Initialise the set with any given 'iterable'."
1.18 +
1.19 + self.clear()
1.20 +
1.21 + if iterable is not None:
1.22 + for value in iterable:
1.23 + self._setitem(self.buckets, value)
1.24 +
1.25 + # Implementation methods.
1.26 +
1.27 + def _find_entry(self, value, index):
1.28 +
1.29 + "Search for 'value', using an 'index' identifying the bucket involved."
1.30 +
1.31 + i = 0
1.32 +
1.33 + for found in self.buckets[index]:
1.34 + if found == value:
1.35 + return i
1.36 + i += 1
1.37 +
1.38 + return None
1.39 +
1.40 + def _resize(self, capacity):
1.41 +
1.42 + "Resize the hashtable to have the given 'capacity'."
1.43 +
1.44 + buckets = self._get_buckets(capacity)
1.45 +
1.46 + for value in self._items():
1.47 + self._setitem(buckets, value)
1.48 +
1.49 + self.buckets = buckets
1.50 +
1.51 + def _setitem(self, buckets, value):
1.52
1.53 -class set:
1.54 - def __init__(self, iterable): pass
1.55 - def add(self, item): pass
1.56 - def clear(self): pass
1.57 - def copy(self): pass
1.58 - def difference(self, other): pass
1.59 - def difference_update(self, other): pass
1.60 - def discard(self, item): pass
1.61 - def intersection(self, other): pass
1.62 - def intersection_update(self, other): pass
1.63 - def issubset(self, other): pass
1.64 - def issuperset(self, other): pass
1.65 + "Set in the 'buckets' an item having the given 'value'."
1.66 +
1.67 + index, i = self._get_entry(value)
1.68 +
1.69 + # With no existing entry, append to the bucket.
1.70 +
1.71 + if i is None:
1.72 + buckets[index].append(value)
1.73 + self.size += 1
1.74 +
1.75 + # With an existing entry, replace the item.
1.76 +
1.77 + else:
1.78 + buckets[index][i] = value
1.79 +
1.80 + # String representations.
1.81 +
1.82 + def _str(self, name):
1.83 +
1.84 + "Return a string representation."
1.85 +
1.86 + b = buffer()
1.87 + b.append(name)
1.88 + b.append("(")
1.89 + b.append(self._items().__repr__())
1.90 + b.append(")")
1.91 + return str(b)
1.92 +
1.93 + def __str__(self):
1.94 +
1.95 + "Return a string representation."
1.96 +
1.97 + return self._str("frozenset")
1.98 +
1.99 + __repr__ = __str__
1.100 +
1.101 + # Public special methods.
1.102 +
1.103 + def __contains__(self, value):
1.104 +
1.105 + "Return whether 'value' is in the set."
1.106 +
1.107 + index, i = self._get_entry(value)
1.108 + return i is not None
1.109
1.110 def __iter__(self):
1.111
1.112 @@ -43,11 +115,66 @@
1.113
1.114 return itemiterator(list(self))
1.115
1.116 - def pop(self): pass
1.117 - def remove(self, item): pass
1.118 + # Public conventional methods.
1.119 +
1.120 + def copy(self): pass
1.121 + def difference(self, other): pass
1.122 + def intersection(self, other): pass
1.123 + def issubset(self, other): pass
1.124 + def issuperset(self, other): pass
1.125 def symmetric_difference(self, other): pass
1.126 + def union(self, other): pass
1.127 +
1.128 +class set(frozenset):
1.129 +
1.130 + "A mutable set representation holding a collection of distinct values."
1.131 +
1.132 + # String representation methods.
1.133 +
1.134 + def __str__(self):
1.135 +
1.136 + "Return a string representation."
1.137 +
1.138 + return self._str("set")
1.139 +
1.140 + __repr__ = __str__
1.141 +
1.142 + # Public conventional methods.
1.143 +
1.144 + def add(self, value):
1.145 +
1.146 + "Add the given 'value' to the set."
1.147 +
1.148 + capacity = len(self.buckets)
1.149 +
1.150 + if self.size > capacity:
1.151 + self._resize(capacity * 2)
1.152 +
1.153 + self._setitem(self.buckets, value)
1.154 +
1.155 + def difference_update(self, other): pass
1.156 +
1.157 + def discard(self, value):
1.158 +
1.159 + "Remove 'value' from the set, if present."
1.160 +
1.161 + try:
1.162 + self.remove(value)
1.163 + except KeyError:
1.164 + pass
1.165 +
1.166 + def intersection_update(self, other): pass
1.167 +
1.168 + def pop(self): pass
1.169 +
1.170 + def remove(self, value):
1.171 +
1.172 + "Remove 'value' from the set."
1.173 +
1.174 + self._remove_entry(value)
1.175 +
1.176 def symmetric_difference_update(self, other): pass
1.177 - def union(self, other): pass
1.178 +
1.179 def update(self, other): pass
1.180
1.181 # vim: tabstop=4 expandtab shiftwidth=4