# HG changeset patch # User Paul Boddie # Date 1486250759 -3600 # Node ID 8df59b6c2c681efcb600f001ad4b462f98b440b1 # Parent b7334adb7dec68d7ffc81d5960cc67898b976929 Fixed internal mapping methods to accept explicit bucket sequences, preventing confusion when searching for entries in one set of buckets while attempting to populate another. Implemented various dictionary and set methods. Added set iteration support. Expanded the test of sets. diff -r b7334adb7dec -r 8df59b6c2c68 lib/__builtins__/dict.py --- a/lib/__builtins__/dict.py Sat Feb 04 22:26:23 2017 +0100 +++ b/lib/__builtins__/dict.py Sun Feb 05 00:25:59 2017 +0100 @@ -40,13 +40,16 @@ # Implementation methods. - def _find_entry(self, key, index): + def _find_entry(self, buckets, key, index): - "Search for 'key', using an 'index' identifying the bucket involved." + """ + Search in 'buckets' for 'key', using an 'index' identifying the bucket + involved. + """ i = 0 - for found, value in self.buckets[index]: + for found, value in buckets[index]: if found == key: return i i += 1 @@ -68,7 +71,7 @@ "Set in the 'buckets' an item having the given 'key' and 'value'." - index, i = self._get_entry(key) + index, i = self._get_entry(buckets, key) # With no existing entry, append to the bucket. @@ -146,13 +149,13 @@ the dictionary, 'default' will be returned instead. """ - index, i = self._get_entry(key) + index, i = self._get_entry(self.buckets, key) # With no entry index, either raise an exception or return the default. if i is None: if default is self.MISSING: - raise KeyError(key) + raise KeyError, key else: return default @@ -182,9 +185,25 @@ return self._items() - def setdefault(self, key, value): pass + def setdefault(self, key, value): + + """ + Set for 'key' the given 'value' only if no entry for 'key' is already + present. Return the associated value for 'key', which will either be the + existing value already present in the dictionary or the supplied 'value' + that was given to establish an entry in the dictionary. + """ - def update(self, other): pass + if not self.has_key(key): + self[key] = value + return self.get(key) + + def update(self, other): + + "Update this dictionary with the items from 'other'." + + for key, value in other.items(): + self[key] = value def values(self): diff -r b7334adb7dec -r 8df59b6c2c68 lib/__builtins__/mapping.py --- a/lib/__builtins__/mapping.py Sat Feb 04 22:26:23 2017 +0100 +++ b/lib/__builtins__/mapping.py Sun Feb 05 00:25:59 2017 +0100 @@ -43,23 +43,26 @@ return buckets - def _get_entry(self, key): + def _get_entry(self, buckets, key): - "Return the index and entry index as a tuple for 'key'." + "Return the index and entry index as a tuple in 'buckets' for 'key'." # Find an index identifying the bucket involved. - index = self._get_index(key) + index = self._get_index(buckets, key) # Find the entry index within the bucket of the key. - i = self._find_entry(key, index) + i = self._find_entry(buckets, key, index) return index, i - def _get_index(self, key): + def _get_index(self, buckets, key): - "Check 'key' and return an index or raise TypeError." + """ + Find in 'buckets' the given 'key', returning an index or raising + TypeError. + """ index = key.__hash__() @@ -68,10 +71,12 @@ return index % len(self.buckets) - def _find_entry(self, key, index): + def _find_entry(self, buckets, key, index): """ - Search for 'key', using an 'index' identifying the bucket involved. + Search in 'buckets' for 'key', using an 'index' identifying the bucket + involved. + Method to be overridden by subclasses. """ @@ -107,6 +112,17 @@ pass + # Public special methods. + + def __len__(self): + + "Return the number of items in the mapping." + + n = 0 + for bucket in self.buckets: + n += bucket.__len__() + return n + # Public conventional methods. def clear(self): diff -r b7334adb7dec -r 8df59b6c2c68 lib/__builtins__/set.py --- a/lib/__builtins__/set.py Sat Feb 04 22:26:23 2017 +0100 +++ b/lib/__builtins__/set.py Sun Feb 05 00:25:59 2017 +0100 @@ -19,7 +19,6 @@ this program. If not, see . """ -from __builtins__.iteration.iterator import itemiterator from __builtins__.mapping import hashtable class frozenset(hashtable): @@ -38,13 +37,16 @@ # Implementation methods. - def _find_entry(self, value, index): + def _find_entry(self, buckets, value, index): - "Search for 'value', using an 'index' identifying the bucket involved." + """ + Search in 'buckets' for 'value', using an 'index' identifying the bucket + involved. + """ i = 0 - for found in self.buckets[index]: + for found in buckets[index]: if found == value: return i i += 1 @@ -66,7 +68,7 @@ "Set in the 'buckets' an item having the given 'value'." - index, i = self._get_entry(value) + index, i = self._get_entry(buckets, value) # With no existing entry, append to the bucket. @@ -106,24 +108,104 @@ "Return whether 'value' is in the set." - index, i = self._get_entry(value) + index, i = self._get_entry(self.buckets, value) return i is not None def __iter__(self): "Return an iterator." - return itemiterator(list(self)) + return setiterator(self) # Public conventional methods. - def copy(self): pass - def difference(self, other): pass - def intersection(self, other): pass - def issubset(self, other): pass - def issuperset(self, other): pass - def symmetric_difference(self, other): pass - def union(self, other): pass + def copy(self): + + "Return a copy of this set." + + result = set() + result.update(self) + return result + + def difference(self, other): + + """ + Return a set containing only those values in this set that are not in + 'other'. + """ + + result = set() + + for value in self: + if value not in other: + result.add(value) + + return result + + def intersection(self, other): + + "Return a set containing only those values in this set and in 'other'." + + result = set() + + for value in self: + if value in other: + result.add(value) + + return result + + def issubset(self, other): + + "Return whether this set is a subset of 'other'." + + for value in self: + if value not in other: + return False + + return True + + def issuperset(self, other): + + "Return whether this set is a superset of 'other'." + + for value in other: + if value not in self: + return False + + return True + + def symmetric_difference(self, other): + + """ + Return a set containing only the values either in this set or in 'other' + but not in both. + """ + + result = set() + + for value in self: + if value not in other: + result.add(value) + + for value in other: + if value not in self: + result.add(value) + + return result + + def union(self, other): + + "Return a set combining this set and 'other'." + + result = set() + + for value in self: + result.add(value) + + for value in other: + result.add(value) + + return result class set(frozenset): @@ -152,7 +234,12 @@ self._setitem(self.buckets, value) - def difference_update(self, other): pass + def difference_update(self, other): + + "Remove from this set all values from 'other'." + + for value in other: + self.remove(value) def discard(self, value): @@ -163,9 +250,26 @@ except KeyError: pass - def intersection_update(self, other): pass + def intersection_update(self, other): + + "Preserve in this set only values in this set found in 'other'." + + for value in self: + if value not in other: + self.remove(value) + + def pop(self): - def pop(self): pass + "Remove and return an arbitrary value." + + # Get the last element from the first non-empty bucket. + + for bucket in self.buckets: + if bucket: + self.size -= 1 + return bucket.pop() + + raise KeyError def remove(self, value): @@ -173,8 +277,59 @@ self._remove_entry(value) - def symmetric_difference_update(self, other): pass + def symmetric_difference_update(self, other): + + """ + Remove from this set all values found in 'other', adding values only + found in 'other'. + """ + + to_add = other.difference(self) + self.difference_update(other) + self.update(to_add) + + def update(self, other): + + "Update this set using the contents of 'other'." + + for value in other: + self.add(value) + +class setiterator: + + "An iterator for set types." + + def __init__(self, mapping): + + "Initialise the iterator with the given 'mapping'." - def update(self, other): pass + self.mapping = mapping + self.index = 0 + self.i = 0 + + def next(self): + + "Return the next value." + + while True: + + # Access the current bucket. If no such bucket exists, stop. + + try: + bucket = self.mapping.buckets[self.index] + except IndexError: + raise StopIteration + + # Access the current item. If no such item exists, get another + # bucket. + + try: + value = bucket[self.i] + self.i += 1 + return value + + except IndexError: + self.index += 1 + self.i = 0 # vim: tabstop=4 expandtab shiftwidth=4 diff -r b7334adb7dec -r 8df59b6c2c68 tests/set.py --- a/tests/set.py Sat Feb 04 22:26:23 2017 +0100 +++ b/tests/set.py Sun Feb 05 00:25:59 2017 +0100 @@ -3,19 +3,51 @@ s.add(20) s.add("c") s.add((1, 2)) + print "# s:", -print s -print 10 in s -print 20 in s -print "c" in s -print 30 in s -print (1, 2) in s +print s # set([10, 20, "c", (1, 2)) +print len(s) # 4 +print 10 in s # True +print 20 in s # True +print "c" in s # True +print 30 in s # False +print (1, 2) in s # True s2 = set([10, 20, "c", (1, 2)]) + print "# s2:", -print s -print 10 in s2 -print 20 in s2 -print "c" in s2 -print 30 in s2 -print (1, 2) in s2 +print s2 # set([10, 20, "c", (1, 2)) +print len(s2) # 4 +print 10 in s2 # True +print 20 in s2 # True +print "c" in s2 # True +print 30 in s2 # False +print (1, 2) in s2 # True + +a = set([1, 3, 5, 7, 9]) +b = set([1, 2, 3, 5, 7]) + +aub = a.union(b) +aib = a.intersection(b) +adb = a.difference(b) +asdb = a.symmetric_difference(b) + +print len(aub) # 6 +print len(aib) # 4 +print len(adb) # 1 +print len(asdb) # 2 +print +print 1 in aub # True +print 1 in aib # True +print 1 in adb # False +print 1 in asdb # True +print +print 2 in aub # True +print 2 in aib # False +print 2 in adb # False +print 2 in asdb # False +print +print 9 in aub # True +print 9 in aib # False +print 9 in adb # True +print 9 in asdb # False