# HG changeset patch
# User Paul Boddie <paul@boddie.org.uk>
# Date 1486228220 -3600
# Node ID 0495cc21f241dd3bb0e446240a51a7cd83addd06
# Parent  1211f066046bee785ea065968956997d988c6f92
Introduced generic mapping support for dictionaries and sets.

diff -r 1211f066046b -r 0495cc21f241 lib/__builtins__/dict.py
--- a/lib/__builtins__/dict.py	Sat Feb 04 17:49:34 2017 +0100
+++ b/lib/__builtins__/dict.py	Sat Feb 04 18:10:20 2017 +0100
@@ -3,7 +3,7 @@
 """
 Dictionary objects.
 
-Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk>
+Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
 
 This program is free software; you can redistribute it and/or modify it under
 the terms of the GNU General Public License as published by the Free Software
@@ -19,90 +19,26 @@
 this program.  If not, see <http://www.gnu.org/licenses/>.
 """
 
+from __builtins__.mapping import hashtable
 from __builtins__.iteration.iterator import itemiterator
-from __builtins__.span import _max
-from native import isinstance as _isinstance
 
-class dict:
+class dict(hashtable):
 
     "A dictionary representation mapping keys to values."
 
     MISSING = object()
 
-    def __init__(self, args=None):
+    def __init__(self, iterable=None):
 
-        "Initialise the dictionary."
+        "Initialise the dictionary with any given 'iterable'."
 
         self.clear()
 
-        if args is not None:
-            for key, value in args:
+        if iterable is not None:
+            for key, value in iterable:
                 self.__setitem__(key, value)
 
-    def __str__(self):
-
-        "Return a string representation."
-
-        b = buffer()
-        b.append("{")
-
-        first = True
-
-        for key, value in self.items():
-            if first:
-                first = False
-            else:
-                b.append(", ")
-            b.append(key.__repr__())
-            b.append(" : ")
-            b.append(value.__repr__())
-
-        b.append("}")
-        return str(b)
-
-    __repr__ = __str__
-
-    def _get_buckets(self, capacity):
-
-        """
-        Reserve an attribute for a hashtable reference along with some space
-        for elements.
-        """
-
-        buckets = []
-        capacity = _max(capacity, 5)
-        i = 0
-
-        while i < capacity:
-            buckets.append([])
-            i += 1
-
-        return buckets
-
-    def _get_entry(self, key):
-
-        "Return the index and entry index as a tuple for 'key'."
-
-        # Find an index identifying the bucket involved.
-
-        index = self._get_index(key)
-
-        # Find the entry index within the bucket of the key.
-
-        i = self._find_entry(key, index)
-
-        return index, i
-
-    def _get_index(self, key):
-
-        "Check 'key' and return an index or raise TypeError."
-
-        index = key.__hash__()
-
-        if not _isinstance(index, int):
-            raise TypeError
-
-        return index % len(self.buckets)
+    # Implementation methods.
 
     def _find_entry(self, key, index):
 
@@ -123,7 +59,7 @@
 
         buckets = self._get_buckets(capacity)
 
-        for key, value in self.items():
+        for key, value in self._items():
             self._setitem(buckets, key, value)
 
         self.buckets = buckets
@@ -145,19 +81,38 @@
         else:
             buckets[index][i] = key, value
 
+    # String representations.
+
+    def __str__(self):
+
+        "Return a string representation."
+
+        b = buffer()
+        b.append("{")
+
+        first = True
+
+        for key, value in self._items():
+            if first:
+                first = False
+            else:
+                b.append(", ")
+            b.append(key.__repr__())
+            b.append(" : ")
+            b.append(value.__repr__())
+
+        b.append("}")
+        return str(b)
+
+    __repr__ = __str__
+
     # Public special methods.
 
     def __delitem__(self, key):
 
         "Remove the entry associated with the given 'key' from this dictionary."
 
-        index, i = self._get_entry(key)
-
-        if index is None or i is None:
-            raise KeyError, key
-
-        del self.buckets[index][i]
-        self.size -= 1
+        self._remove_entry(key)
 
     def __getitem__(self, key):
 
@@ -184,13 +139,6 @@
 
     # Public conventional methods.
 
-    def clear(self):
-
-        "Reset the dictionary to an empty state."
-
-        self.size = 0
-        self.buckets = self._get_buckets(0)
-
     def get(self, key, default=None):
 
         """
@@ -224,7 +172,7 @@
         "Return the keys for this dictionary."
 
         l = []
-        for key, value in self.items():
+        for key, value in self._items():
             l.append(key)
         return l
 
@@ -232,10 +180,7 @@
 
         "Return the items, each being a (key, value) tuple, in this dictionary."
 
-        l = []
-        for bucket in self.buckets:
-            l += bucket
-        return l
+        return self._items()
 
     def setdefault(self, key, value): pass
 
@@ -246,7 +191,7 @@
         "Return the values in this dictionary."
 
         l = []
-        for key, value in self.items():
+        for key, value in self._items():
             l.append(value)
         return l
 
diff -r 1211f066046b -r 0495cc21f241 lib/__builtins__/mapping.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lib/__builtins__/mapping.py	Sat Feb 04 18:10:20 2017 +0100
@@ -0,0 +1,119 @@
+#!/usr/bin/env python
+
+"""
+Mapping object support.
+
+Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+details.
+
+You should have received a copy of the GNU General Public License along with
+this program.  If not, see <http://www.gnu.org/licenses/>.
+"""
+
+from __builtins__.span import _max
+from native import isinstance as _isinstance
+
+class hashtable:
+
+    "A dictionary representation mapping keys to values."
+
+    def _get_buckets(self, capacity):
+
+        """
+        Reserve an attribute for a hashtable reference along with some space
+        for elements.
+        """
+
+        buckets = []
+        capacity = _max(capacity, 5)
+        i = 0
+
+        while i < capacity:
+            buckets.append([])
+            i += 1
+
+        return buckets
+
+    def _get_entry(self, key):
+
+        "Return the index and entry index as a tuple for 'key'."
+
+        # Find an index identifying the bucket involved.
+
+        index = self._get_index(key)
+
+        # Find the entry index within the bucket of the key.
+
+        i = self._find_entry(key, index)
+
+        return index, i
+
+    def _get_index(self, key):
+
+        "Check 'key' and return an index or raise TypeError."
+
+        index = key.__hash__()
+
+        if not _isinstance(index, int):
+            raise TypeError
+
+        return index % len(self.buckets)
+
+    def _find_entry(self, key, index):
+
+        """
+        Search for 'key', using an 'index' identifying the bucket involved.
+        Method to be overridden by subclasses.
+        """
+
+        pass
+
+    def _items(self):
+
+        "Return the values stored in all buckets."
+
+        l = []
+        for bucket in self.buckets:
+            l += bucket
+        return l
+
+    def _remove_entry(self, key):
+
+        "Remove the entry associated with the given 'key'."
+
+        index, i = self._get_entry(key)
+
+        if index is None or i is None:
+            raise KeyError, key
+
+        del self.buckets[index][i]
+        self.size -= 1
+
+    def _resize(self, capacity):
+
+        """
+        Resize the hashtable to have the given 'capacity'.
+        Method to be overridden by subclasses.
+        """
+
+        pass
+
+    # Public conventional methods.
+
+    def clear(self):
+
+        "Reset the dictionary to an empty state."
+
+        self.size = 0
+        self.buckets = self._get_buckets(0)
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r 1211f066046b -r 0495cc21f241 lib/__builtins__/set.py
--- a/lib/__builtins__/set.py	Sat Feb 04 17:49:34 2017 +0100
+++ b/lib/__builtins__/set.py	Sat Feb 04 18:10:20 2017 +0100
@@ -20,22 +20,94 @@
 """
 
 from __builtins__.iteration.iterator import itemiterator
+from __builtins__.mapping import hashtable
 
-class frozenset:
-    def __init__(self, iterable): pass
+class frozenset(hashtable):
+
+    "An immutable set representation holding a collection of distinct values."
+
+    def __init__(self, iterable=None):
+
+        "Initialise the set with any given 'iterable'."
+
+        self.clear()
+
+        if iterable is not None:
+            for value in iterable:
+                self._setitem(self.buckets, value)
+
+    # Implementation methods.
+
+    def _find_entry(self, value, index):
+
+        "Search for 'value', using an 'index' identifying the bucket involved."
+
+        i = 0
+
+        for found in self.buckets[index]:
+            if found == value:
+                return i
+            i += 1
+
+        return None
+
+    def _resize(self, capacity):
+
+        "Resize the hashtable to have the given 'capacity'."
+
+        buckets = self._get_buckets(capacity)
+
+        for value in self._items():
+            self._setitem(buckets, value)
+
+        self.buckets = buckets
+
+    def _setitem(self, buckets, value):
 
-class set:
-    def __init__(self, iterable): pass
-    def add(self, item): pass
-    def clear(self): pass
-    def copy(self): pass
-    def difference(self, other): pass
-    def difference_update(self, other): pass
-    def discard(self, item): pass
-    def intersection(self, other): pass
-    def intersection_update(self, other): pass
-    def issubset(self, other): pass
-    def issuperset(self, other): pass
+        "Set in the 'buckets' an item having the given 'value'."
+
+        index, i = self._get_entry(value)
+
+        # With no existing entry, append to the bucket.
+
+        if i is None:
+            buckets[index].append(value)
+            self.size += 1
+
+        # With an existing entry, replace the item.
+
+        else:
+            buckets[index][i] = value
+
+    # String representations.
+
+    def _str(self, name):
+
+        "Return a string representation."
+
+        b = buffer()
+        b.append(name)
+        b.append("(")
+        b.append(self._items().__repr__())
+        b.append(")")
+        return str(b)
+
+    def __str__(self):
+
+        "Return a string representation."
+
+        return self._str("frozenset")
+
+    __repr__ = __str__
+
+    # Public special methods.
+
+    def __contains__(self, value):
+
+        "Return whether 'value' is in the set."
+
+        index, i = self._get_entry(value)
+        return i is not None
 
     def __iter__(self):
 
@@ -43,11 +115,66 @@
 
         return itemiterator(list(self))
 
-    def pop(self): pass
-    def remove(self, item): pass
+    # 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
+
+class set(frozenset):
+
+    "A mutable set representation holding a collection of distinct values."
+
+    # String representation methods.
+
+    def __str__(self):
+
+        "Return a string representation."
+
+        return self._str("set")
+
+    __repr__ = __str__
+
+    # Public conventional methods.
+
+    def add(self, value):
+
+        "Add the given 'value' to the set."
+
+        capacity = len(self.buckets)
+
+        if self.size > capacity:
+            self._resize(capacity * 2)
+
+        self._setitem(self.buckets, value)
+
+    def difference_update(self, other): pass
+
+    def discard(self, value):
+
+        "Remove 'value' from the set, if present."
+
+        try:
+            self.remove(value)
+        except KeyError:
+            pass
+
+    def intersection_update(self, other): pass
+
+    def pop(self): pass
+
+    def remove(self, value):
+
+        "Remove 'value' from the set."
+
+        self._remove_entry(value)
+
     def symmetric_difference_update(self, other): pass
-    def union(self, other): pass
+
     def update(self, other): pass
 
 # vim: tabstop=4 expandtab shiftwidth=4
diff -r 1211f066046b -r 0495cc21f241 tests/set.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/set.py	Sat Feb 04 18:10:20 2017 +0100
@@ -0,0 +1,21 @@
+s = set()
+s.add(10)
+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
+
+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