1.1 --- a/lib/__builtins__/set.py Sat Feb 04 22:26:23 2017 +0100
1.2 +++ b/lib/__builtins__/set.py Sun Feb 05 00:25:59 2017 +0100
1.3 @@ -19,7 +19,6 @@
1.4 this program. If not, see <http://www.gnu.org/licenses/>.
1.5 """
1.6
1.7 -from __builtins__.iteration.iterator import itemiterator
1.8 from __builtins__.mapping import hashtable
1.9
1.10 class frozenset(hashtable):
1.11 @@ -38,13 +37,16 @@
1.12
1.13 # Implementation methods.
1.14
1.15 - def _find_entry(self, value, index):
1.16 + def _find_entry(self, buckets, value, index):
1.17
1.18 - "Search for 'value', using an 'index' identifying the bucket involved."
1.19 + """
1.20 + Search in 'buckets' for 'value', using an 'index' identifying the bucket
1.21 + involved.
1.22 + """
1.23
1.24 i = 0
1.25
1.26 - for found in self.buckets[index]:
1.27 + for found in buckets[index]:
1.28 if found == value:
1.29 return i
1.30 i += 1
1.31 @@ -66,7 +68,7 @@
1.32
1.33 "Set in the 'buckets' an item having the given 'value'."
1.34
1.35 - index, i = self._get_entry(value)
1.36 + index, i = self._get_entry(buckets, value)
1.37
1.38 # With no existing entry, append to the bucket.
1.39
1.40 @@ -106,24 +108,104 @@
1.41
1.42 "Return whether 'value' is in the set."
1.43
1.44 - index, i = self._get_entry(value)
1.45 + index, i = self._get_entry(self.buckets, value)
1.46 return i is not None
1.47
1.48 def __iter__(self):
1.49
1.50 "Return an iterator."
1.51
1.52 - return itemiterator(list(self))
1.53 + return setiterator(self)
1.54
1.55 # Public conventional methods.
1.56
1.57 - def copy(self): pass
1.58 - def difference(self, other): pass
1.59 - def intersection(self, other): pass
1.60 - def issubset(self, other): pass
1.61 - def issuperset(self, other): pass
1.62 - def symmetric_difference(self, other): pass
1.63 - def union(self, other): pass
1.64 + def copy(self):
1.65 +
1.66 + "Return a copy of this set."
1.67 +
1.68 + result = set()
1.69 + result.update(self)
1.70 + return result
1.71 +
1.72 + def difference(self, other):
1.73 +
1.74 + """
1.75 + Return a set containing only those values in this set that are not in
1.76 + 'other'.
1.77 + """
1.78 +
1.79 + result = set()
1.80 +
1.81 + for value in self:
1.82 + if value not in other:
1.83 + result.add(value)
1.84 +
1.85 + return result
1.86 +
1.87 + def intersection(self, other):
1.88 +
1.89 + "Return a set containing only those values in this set and in 'other'."
1.90 +
1.91 + result = set()
1.92 +
1.93 + for value in self:
1.94 + if value in other:
1.95 + result.add(value)
1.96 +
1.97 + return result
1.98 +
1.99 + def issubset(self, other):
1.100 +
1.101 + "Return whether this set is a subset of 'other'."
1.102 +
1.103 + for value in self:
1.104 + if value not in other:
1.105 + return False
1.106 +
1.107 + return True
1.108 +
1.109 + def issuperset(self, other):
1.110 +
1.111 + "Return whether this set is a superset of 'other'."
1.112 +
1.113 + for value in other:
1.114 + if value not in self:
1.115 + return False
1.116 +
1.117 + return True
1.118 +
1.119 + def symmetric_difference(self, other):
1.120 +
1.121 + """
1.122 + Return a set containing only the values either in this set or in 'other'
1.123 + but not in both.
1.124 + """
1.125 +
1.126 + result = set()
1.127 +
1.128 + for value in self:
1.129 + if value not in other:
1.130 + result.add(value)
1.131 +
1.132 + for value in other:
1.133 + if value not in self:
1.134 + result.add(value)
1.135 +
1.136 + return result
1.137 +
1.138 + def union(self, other):
1.139 +
1.140 + "Return a set combining this set and 'other'."
1.141 +
1.142 + result = set()
1.143 +
1.144 + for value in self:
1.145 + result.add(value)
1.146 +
1.147 + for value in other:
1.148 + result.add(value)
1.149 +
1.150 + return result
1.151
1.152 class set(frozenset):
1.153
1.154 @@ -152,7 +234,12 @@
1.155
1.156 self._setitem(self.buckets, value)
1.157
1.158 - def difference_update(self, other): pass
1.159 + def difference_update(self, other):
1.160 +
1.161 + "Remove from this set all values from 'other'."
1.162 +
1.163 + for value in other:
1.164 + self.remove(value)
1.165
1.166 def discard(self, value):
1.167
1.168 @@ -163,9 +250,26 @@
1.169 except KeyError:
1.170 pass
1.171
1.172 - def intersection_update(self, other): pass
1.173 + def intersection_update(self, other):
1.174 +
1.175 + "Preserve in this set only values in this set found in 'other'."
1.176 +
1.177 + for value in self:
1.178 + if value not in other:
1.179 + self.remove(value)
1.180 +
1.181 + def pop(self):
1.182
1.183 - def pop(self): pass
1.184 + "Remove and return an arbitrary value."
1.185 +
1.186 + # Get the last element from the first non-empty bucket.
1.187 +
1.188 + for bucket in self.buckets:
1.189 + if bucket:
1.190 + self.size -= 1
1.191 + return bucket.pop()
1.192 +
1.193 + raise KeyError
1.194
1.195 def remove(self, value):
1.196
1.197 @@ -173,8 +277,59 @@
1.198
1.199 self._remove_entry(value)
1.200
1.201 - def symmetric_difference_update(self, other): pass
1.202 + def symmetric_difference_update(self, other):
1.203 +
1.204 + """
1.205 + Remove from this set all values found in 'other', adding values only
1.206 + found in 'other'.
1.207 + """
1.208 +
1.209 + to_add = other.difference(self)
1.210 + self.difference_update(other)
1.211 + self.update(to_add)
1.212 +
1.213 + def update(self, other):
1.214 +
1.215 + "Update this set using the contents of 'other'."
1.216 +
1.217 + for value in other:
1.218 + self.add(value)
1.219 +
1.220 +class setiterator:
1.221 +
1.222 + "An iterator for set types."
1.223 +
1.224 + def __init__(self, mapping):
1.225 +
1.226 + "Initialise the iterator with the given 'mapping'."
1.227
1.228 - def update(self, other): pass
1.229 + self.mapping = mapping
1.230 + self.index = 0
1.231 + self.i = 0
1.232 +
1.233 + def next(self):
1.234 +
1.235 + "Return the next value."
1.236 +
1.237 + while True:
1.238 +
1.239 + # Access the current bucket. If no such bucket exists, stop.
1.240 +
1.241 + try:
1.242 + bucket = self.mapping.buckets[self.index]
1.243 + except IndexError:
1.244 + raise StopIteration
1.245 +
1.246 + # Access the current item. If no such item exists, get another
1.247 + # bucket.
1.248 +
1.249 + try:
1.250 + value = bucket[self.i]
1.251 + self.i += 1
1.252 + return value
1.253 +
1.254 + except IndexError:
1.255 + self.index += 1
1.256 + self.i = 0
1.257
1.258 # vim: tabstop=4 expandtab shiftwidth=4