1.1 --- a/lib/__builtins__/dict.py Sat Feb 04 22:26:23 2017 +0100
1.2 +++ b/lib/__builtins__/dict.py Sun Feb 05 00:25:59 2017 +0100
1.3 @@ -40,13 +40,16 @@
1.4
1.5 # Implementation methods.
1.6
1.7 - def _find_entry(self, key, index):
1.8 + def _find_entry(self, buckets, key, index):
1.9
1.10 - "Search for 'key', using an 'index' identifying the bucket involved."
1.11 + """
1.12 + Search in 'buckets' for 'key', using an 'index' identifying the bucket
1.13 + involved.
1.14 + """
1.15
1.16 i = 0
1.17
1.18 - for found, value in self.buckets[index]:
1.19 + for found, value in buckets[index]:
1.20 if found == key:
1.21 return i
1.22 i += 1
1.23 @@ -68,7 +71,7 @@
1.24
1.25 "Set in the 'buckets' an item having the given 'key' and 'value'."
1.26
1.27 - index, i = self._get_entry(key)
1.28 + index, i = self._get_entry(buckets, key)
1.29
1.30 # With no existing entry, append to the bucket.
1.31
1.32 @@ -146,13 +149,13 @@
1.33 the dictionary, 'default' will be returned instead.
1.34 """
1.35
1.36 - index, i = self._get_entry(key)
1.37 + index, i = self._get_entry(self.buckets, key)
1.38
1.39 # With no entry index, either raise an exception or return the default.
1.40
1.41 if i is None:
1.42 if default is self.MISSING:
1.43 - raise KeyError(key)
1.44 + raise KeyError, key
1.45 else:
1.46 return default
1.47
1.48 @@ -182,9 +185,25 @@
1.49
1.50 return self._items()
1.51
1.52 - def setdefault(self, key, value): pass
1.53 + def setdefault(self, key, value):
1.54 +
1.55 + """
1.56 + Set for 'key' the given 'value' only if no entry for 'key' is already
1.57 + present. Return the associated value for 'key', which will either be the
1.58 + existing value already present in the dictionary or the supplied 'value'
1.59 + that was given to establish an entry in the dictionary.
1.60 + """
1.61
1.62 - def update(self, other): pass
1.63 + if not self.has_key(key):
1.64 + self[key] = value
1.65 + return self.get(key)
1.66 +
1.67 + def update(self, other):
1.68 +
1.69 + "Update this dictionary with the items from 'other'."
1.70 +
1.71 + for key, value in other.items():
1.72 + self[key] = value
1.73
1.74 def values(self):
1.75
2.1 --- a/lib/__builtins__/mapping.py Sat Feb 04 22:26:23 2017 +0100
2.2 +++ b/lib/__builtins__/mapping.py Sun Feb 05 00:25:59 2017 +0100
2.3 @@ -43,23 +43,26 @@
2.4
2.5 return buckets
2.6
2.7 - def _get_entry(self, key):
2.8 + def _get_entry(self, buckets, key):
2.9
2.10 - "Return the index and entry index as a tuple for 'key'."
2.11 + "Return the index and entry index as a tuple in 'buckets' for 'key'."
2.12
2.13 # Find an index identifying the bucket involved.
2.14
2.15 - index = self._get_index(key)
2.16 + index = self._get_index(buckets, key)
2.17
2.18 # Find the entry index within the bucket of the key.
2.19
2.20 - i = self._find_entry(key, index)
2.21 + i = self._find_entry(buckets, key, index)
2.22
2.23 return index, i
2.24
2.25 - def _get_index(self, key):
2.26 + def _get_index(self, buckets, key):
2.27
2.28 - "Check 'key' and return an index or raise TypeError."
2.29 + """
2.30 + Find in 'buckets' the given 'key', returning an index or raising
2.31 + TypeError.
2.32 + """
2.33
2.34 index = key.__hash__()
2.35
2.36 @@ -68,10 +71,12 @@
2.37
2.38 return index % len(self.buckets)
2.39
2.40 - def _find_entry(self, key, index):
2.41 + def _find_entry(self, buckets, key, index):
2.42
2.43 """
2.44 - Search for 'key', using an 'index' identifying the bucket involved.
2.45 + Search in 'buckets' for 'key', using an 'index' identifying the bucket
2.46 + involved.
2.47 +
2.48 Method to be overridden by subclasses.
2.49 """
2.50
2.51 @@ -107,6 +112,17 @@
2.52
2.53 pass
2.54
2.55 + # Public special methods.
2.56 +
2.57 + def __len__(self):
2.58 +
2.59 + "Return the number of items in the mapping."
2.60 +
2.61 + n = 0
2.62 + for bucket in self.buckets:
2.63 + n += bucket.__len__()
2.64 + return n
2.65 +
2.66 # Public conventional methods.
2.67
2.68 def clear(self):
3.1 --- a/lib/__builtins__/set.py Sat Feb 04 22:26:23 2017 +0100
3.2 +++ b/lib/__builtins__/set.py Sun Feb 05 00:25:59 2017 +0100
3.3 @@ -19,7 +19,6 @@
3.4 this program. If not, see <http://www.gnu.org/licenses/>.
3.5 """
3.6
3.7 -from __builtins__.iteration.iterator import itemiterator
3.8 from __builtins__.mapping import hashtable
3.9
3.10 class frozenset(hashtable):
3.11 @@ -38,13 +37,16 @@
3.12
3.13 # Implementation methods.
3.14
3.15 - def _find_entry(self, value, index):
3.16 + def _find_entry(self, buckets, value, index):
3.17
3.18 - "Search for 'value', using an 'index' identifying the bucket involved."
3.19 + """
3.20 + Search in 'buckets' for 'value', using an 'index' identifying the bucket
3.21 + involved.
3.22 + """
3.23
3.24 i = 0
3.25
3.26 - for found in self.buckets[index]:
3.27 + for found in buckets[index]:
3.28 if found == value:
3.29 return i
3.30 i += 1
3.31 @@ -66,7 +68,7 @@
3.32
3.33 "Set in the 'buckets' an item having the given 'value'."
3.34
3.35 - index, i = self._get_entry(value)
3.36 + index, i = self._get_entry(buckets, value)
3.37
3.38 # With no existing entry, append to the bucket.
3.39
3.40 @@ -106,24 +108,104 @@
3.41
3.42 "Return whether 'value' is in the set."
3.43
3.44 - index, i = self._get_entry(value)
3.45 + index, i = self._get_entry(self.buckets, value)
3.46 return i is not None
3.47
3.48 def __iter__(self):
3.49
3.50 "Return an iterator."
3.51
3.52 - return itemiterator(list(self))
3.53 + return setiterator(self)
3.54
3.55 # Public conventional methods.
3.56
3.57 - def copy(self): pass
3.58 - def difference(self, other): pass
3.59 - def intersection(self, other): pass
3.60 - def issubset(self, other): pass
3.61 - def issuperset(self, other): pass
3.62 - def symmetric_difference(self, other): pass
3.63 - def union(self, other): pass
3.64 + def copy(self):
3.65 +
3.66 + "Return a copy of this set."
3.67 +
3.68 + result = set()
3.69 + result.update(self)
3.70 + return result
3.71 +
3.72 + def difference(self, other):
3.73 +
3.74 + """
3.75 + Return a set containing only those values in this set that are not in
3.76 + 'other'.
3.77 + """
3.78 +
3.79 + result = set()
3.80 +
3.81 + for value in self:
3.82 + if value not in other:
3.83 + result.add(value)
3.84 +
3.85 + return result
3.86 +
3.87 + def intersection(self, other):
3.88 +
3.89 + "Return a set containing only those values in this set and in 'other'."
3.90 +
3.91 + result = set()
3.92 +
3.93 + for value in self:
3.94 + if value in other:
3.95 + result.add(value)
3.96 +
3.97 + return result
3.98 +
3.99 + def issubset(self, other):
3.100 +
3.101 + "Return whether this set is a subset of 'other'."
3.102 +
3.103 + for value in self:
3.104 + if value not in other:
3.105 + return False
3.106 +
3.107 + return True
3.108 +
3.109 + def issuperset(self, other):
3.110 +
3.111 + "Return whether this set is a superset of 'other'."
3.112 +
3.113 + for value in other:
3.114 + if value not in self:
3.115 + return False
3.116 +
3.117 + return True
3.118 +
3.119 + def symmetric_difference(self, other):
3.120 +
3.121 + """
3.122 + Return a set containing only the values either in this set or in 'other'
3.123 + but not in both.
3.124 + """
3.125 +
3.126 + result = set()
3.127 +
3.128 + for value in self:
3.129 + if value not in other:
3.130 + result.add(value)
3.131 +
3.132 + for value in other:
3.133 + if value not in self:
3.134 + result.add(value)
3.135 +
3.136 + return result
3.137 +
3.138 + def union(self, other):
3.139 +
3.140 + "Return a set combining this set and 'other'."
3.141 +
3.142 + result = set()
3.143 +
3.144 + for value in self:
3.145 + result.add(value)
3.146 +
3.147 + for value in other:
3.148 + result.add(value)
3.149 +
3.150 + return result
3.151
3.152 class set(frozenset):
3.153
3.154 @@ -152,7 +234,12 @@
3.155
3.156 self._setitem(self.buckets, value)
3.157
3.158 - def difference_update(self, other): pass
3.159 + def difference_update(self, other):
3.160 +
3.161 + "Remove from this set all values from 'other'."
3.162 +
3.163 + for value in other:
3.164 + self.remove(value)
3.165
3.166 def discard(self, value):
3.167
3.168 @@ -163,9 +250,26 @@
3.169 except KeyError:
3.170 pass
3.171
3.172 - def intersection_update(self, other): pass
3.173 + def intersection_update(self, other):
3.174 +
3.175 + "Preserve in this set only values in this set found in 'other'."
3.176 +
3.177 + for value in self:
3.178 + if value not in other:
3.179 + self.remove(value)
3.180 +
3.181 + def pop(self):
3.182
3.183 - def pop(self): pass
3.184 + "Remove and return an arbitrary value."
3.185 +
3.186 + # Get the last element from the first non-empty bucket.
3.187 +
3.188 + for bucket in self.buckets:
3.189 + if bucket:
3.190 + self.size -= 1
3.191 + return bucket.pop()
3.192 +
3.193 + raise KeyError
3.194
3.195 def remove(self, value):
3.196
3.197 @@ -173,8 +277,59 @@
3.198
3.199 self._remove_entry(value)
3.200
3.201 - def symmetric_difference_update(self, other): pass
3.202 + def symmetric_difference_update(self, other):
3.203 +
3.204 + """
3.205 + Remove from this set all values found in 'other', adding values only
3.206 + found in 'other'.
3.207 + """
3.208 +
3.209 + to_add = other.difference(self)
3.210 + self.difference_update(other)
3.211 + self.update(to_add)
3.212 +
3.213 + def update(self, other):
3.214 +
3.215 + "Update this set using the contents of 'other'."
3.216 +
3.217 + for value in other:
3.218 + self.add(value)
3.219 +
3.220 +class setiterator:
3.221 +
3.222 + "An iterator for set types."
3.223 +
3.224 + def __init__(self, mapping):
3.225 +
3.226 + "Initialise the iterator with the given 'mapping'."
3.227
3.228 - def update(self, other): pass
3.229 + self.mapping = mapping
3.230 + self.index = 0
3.231 + self.i = 0
3.232 +
3.233 + def next(self):
3.234 +
3.235 + "Return the next value."
3.236 +
3.237 + while True:
3.238 +
3.239 + # Access the current bucket. If no such bucket exists, stop.
3.240 +
3.241 + try:
3.242 + bucket = self.mapping.buckets[self.index]
3.243 + except IndexError:
3.244 + raise StopIteration
3.245 +
3.246 + # Access the current item. If no such item exists, get another
3.247 + # bucket.
3.248 +
3.249 + try:
3.250 + value = bucket[self.i]
3.251 + self.i += 1
3.252 + return value
3.253 +
3.254 + except IndexError:
3.255 + self.index += 1
3.256 + self.i = 0
3.257
3.258 # vim: tabstop=4 expandtab shiftwidth=4
4.1 --- a/tests/set.py Sat Feb 04 22:26:23 2017 +0100
4.2 +++ b/tests/set.py Sun Feb 05 00:25:59 2017 +0100
4.3 @@ -3,19 +3,51 @@
4.4 s.add(20)
4.5 s.add("c")
4.6 s.add((1, 2))
4.7 +
4.8 print "# s:",
4.9 -print s
4.10 -print 10 in s
4.11 -print 20 in s
4.12 -print "c" in s
4.13 -print 30 in s
4.14 -print (1, 2) in s
4.15 +print s # set([10, 20, "c", (1, 2))
4.16 +print len(s) # 4
4.17 +print 10 in s # True
4.18 +print 20 in s # True
4.19 +print "c" in s # True
4.20 +print 30 in s # False
4.21 +print (1, 2) in s # True
4.22
4.23 s2 = set([10, 20, "c", (1, 2)])
4.24 +
4.25 print "# s2:",
4.26 -print s
4.27 -print 10 in s2
4.28 -print 20 in s2
4.29 -print "c" in s2
4.30 -print 30 in s2
4.31 -print (1, 2) in s2
4.32 +print s2 # set([10, 20, "c", (1, 2))
4.33 +print len(s2) # 4
4.34 +print 10 in s2 # True
4.35 +print 20 in s2 # True
4.36 +print "c" in s2 # True
4.37 +print 30 in s2 # False
4.38 +print (1, 2) in s2 # True
4.39 +
4.40 +a = set([1, 3, 5, 7, 9])
4.41 +b = set([1, 2, 3, 5, 7])
4.42 +
4.43 +aub = a.union(b)
4.44 +aib = a.intersection(b)
4.45 +adb = a.difference(b)
4.46 +asdb = a.symmetric_difference(b)
4.47 +
4.48 +print len(aub) # 6
4.49 +print len(aib) # 4
4.50 +print len(adb) # 1
4.51 +print len(asdb) # 2
4.52 +print
4.53 +print 1 in aub # True
4.54 +print 1 in aib # True
4.55 +print 1 in adb # False
4.56 +print 1 in asdb # True
4.57 +print
4.58 +print 2 in aub # True
4.59 +print 2 in aib # False
4.60 +print 2 in adb # False
4.61 +print 2 in asdb # False
4.62 +print
4.63 +print 9 in aub # True
4.64 +print 9 in aib # False
4.65 +print 9 in adb # True
4.66 +print 9 in asdb # False