1.1 --- a/lib/__builtins__/dict.py Sat Feb 04 17:49:34 2017 +0100
1.2 +++ b/lib/__builtins__/dict.py Sat Feb 04 18:10:20 2017 +0100
1.3 @@ -3,7 +3,7 @@
1.4 """
1.5 Dictionary objects.
1.6
1.7 -Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk>
1.8 +Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
1.9
1.10 This program is free software; you can redistribute it and/or modify it under
1.11 the terms of the GNU General Public License as published by the Free Software
1.12 @@ -19,90 +19,26 @@
1.13 this program. If not, see <http://www.gnu.org/licenses/>.
1.14 """
1.15
1.16 +from __builtins__.mapping import hashtable
1.17 from __builtins__.iteration.iterator import itemiterator
1.18 -from __builtins__.span import _max
1.19 -from native import isinstance as _isinstance
1.20
1.21 -class dict:
1.22 +class dict(hashtable):
1.23
1.24 "A dictionary representation mapping keys to values."
1.25
1.26 MISSING = object()
1.27
1.28 - def __init__(self, args=None):
1.29 + def __init__(self, iterable=None):
1.30
1.31 - "Initialise the dictionary."
1.32 + "Initialise the dictionary with any given 'iterable'."
1.33
1.34 self.clear()
1.35
1.36 - if args is not None:
1.37 - for key, value in args:
1.38 + if iterable is not None:
1.39 + for key, value in iterable:
1.40 self.__setitem__(key, value)
1.41
1.42 - def __str__(self):
1.43 -
1.44 - "Return a string representation."
1.45 -
1.46 - b = buffer()
1.47 - b.append("{")
1.48 -
1.49 - first = True
1.50 -
1.51 - for key, value in self.items():
1.52 - if first:
1.53 - first = False
1.54 - else:
1.55 - b.append(", ")
1.56 - b.append(key.__repr__())
1.57 - b.append(" : ")
1.58 - b.append(value.__repr__())
1.59 -
1.60 - b.append("}")
1.61 - return str(b)
1.62 -
1.63 - __repr__ = __str__
1.64 -
1.65 - def _get_buckets(self, capacity):
1.66 -
1.67 - """
1.68 - Reserve an attribute for a hashtable reference along with some space
1.69 - for elements.
1.70 - """
1.71 -
1.72 - buckets = []
1.73 - capacity = _max(capacity, 5)
1.74 - i = 0
1.75 -
1.76 - while i < capacity:
1.77 - buckets.append([])
1.78 - i += 1
1.79 -
1.80 - return buckets
1.81 -
1.82 - def _get_entry(self, key):
1.83 -
1.84 - "Return the index and entry index as a tuple for 'key'."
1.85 -
1.86 - # Find an index identifying the bucket involved.
1.87 -
1.88 - index = self._get_index(key)
1.89 -
1.90 - # Find the entry index within the bucket of the key.
1.91 -
1.92 - i = self._find_entry(key, index)
1.93 -
1.94 - return index, i
1.95 -
1.96 - def _get_index(self, key):
1.97 -
1.98 - "Check 'key' and return an index or raise TypeError."
1.99 -
1.100 - index = key.__hash__()
1.101 -
1.102 - if not _isinstance(index, int):
1.103 - raise TypeError
1.104 -
1.105 - return index % len(self.buckets)
1.106 + # Implementation methods.
1.107
1.108 def _find_entry(self, key, index):
1.109
1.110 @@ -123,7 +59,7 @@
1.111
1.112 buckets = self._get_buckets(capacity)
1.113
1.114 - for key, value in self.items():
1.115 + for key, value in self._items():
1.116 self._setitem(buckets, key, value)
1.117
1.118 self.buckets = buckets
1.119 @@ -145,19 +81,38 @@
1.120 else:
1.121 buckets[index][i] = key, value
1.122
1.123 + # String representations.
1.124 +
1.125 + def __str__(self):
1.126 +
1.127 + "Return a string representation."
1.128 +
1.129 + b = buffer()
1.130 + b.append("{")
1.131 +
1.132 + first = True
1.133 +
1.134 + for key, value in self._items():
1.135 + if first:
1.136 + first = False
1.137 + else:
1.138 + b.append(", ")
1.139 + b.append(key.__repr__())
1.140 + b.append(" : ")
1.141 + b.append(value.__repr__())
1.142 +
1.143 + b.append("}")
1.144 + return str(b)
1.145 +
1.146 + __repr__ = __str__
1.147 +
1.148 # Public special methods.
1.149
1.150 def __delitem__(self, key):
1.151
1.152 "Remove the entry associated with the given 'key' from this dictionary."
1.153
1.154 - index, i = self._get_entry(key)
1.155 -
1.156 - if index is None or i is None:
1.157 - raise KeyError, key
1.158 -
1.159 - del self.buckets[index][i]
1.160 - self.size -= 1
1.161 + self._remove_entry(key)
1.162
1.163 def __getitem__(self, key):
1.164
1.165 @@ -184,13 +139,6 @@
1.166
1.167 # Public conventional methods.
1.168
1.169 - def clear(self):
1.170 -
1.171 - "Reset the dictionary to an empty state."
1.172 -
1.173 - self.size = 0
1.174 - self.buckets = self._get_buckets(0)
1.175 -
1.176 def get(self, key, default=None):
1.177
1.178 """
1.179 @@ -224,7 +172,7 @@
1.180 "Return the keys for this dictionary."
1.181
1.182 l = []
1.183 - for key, value in self.items():
1.184 + for key, value in self._items():
1.185 l.append(key)
1.186 return l
1.187
1.188 @@ -232,10 +180,7 @@
1.189
1.190 "Return the items, each being a (key, value) tuple, in this dictionary."
1.191
1.192 - l = []
1.193 - for bucket in self.buckets:
1.194 - l += bucket
1.195 - return l
1.196 + return self._items()
1.197
1.198 def setdefault(self, key, value): pass
1.199
1.200 @@ -246,7 +191,7 @@
1.201 "Return the values in this dictionary."
1.202
1.203 l = []
1.204 - for key, value in self.items():
1.205 + for key, value in self._items():
1.206 l.append(value)
1.207 return l
1.208
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lib/__builtins__/mapping.py Sat Feb 04 18:10:20 2017 +0100
2.3 @@ -0,0 +1,119 @@
2.4 +#!/usr/bin/env python
2.5 +
2.6 +"""
2.7 +Mapping object support.
2.8 +
2.9 +Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
2.10 +
2.11 +This program is free software; you can redistribute it and/or modify it under
2.12 +the terms of the GNU General Public License as published by the Free Software
2.13 +Foundation; either version 3 of the License, or (at your option) any later
2.14 +version.
2.15 +
2.16 +This program is distributed in the hope that it will be useful, but WITHOUT
2.17 +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
2.18 +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
2.19 +details.
2.20 +
2.21 +You should have received a copy of the GNU General Public License along with
2.22 +this program. If not, see <http://www.gnu.org/licenses/>.
2.23 +"""
2.24 +
2.25 +from __builtins__.span import _max
2.26 +from native import isinstance as _isinstance
2.27 +
2.28 +class hashtable:
2.29 +
2.30 + "A dictionary representation mapping keys to values."
2.31 +
2.32 + def _get_buckets(self, capacity):
2.33 +
2.34 + """
2.35 + Reserve an attribute for a hashtable reference along with some space
2.36 + for elements.
2.37 + """
2.38 +
2.39 + buckets = []
2.40 + capacity = _max(capacity, 5)
2.41 + i = 0
2.42 +
2.43 + while i < capacity:
2.44 + buckets.append([])
2.45 + i += 1
2.46 +
2.47 + return buckets
2.48 +
2.49 + def _get_entry(self, key):
2.50 +
2.51 + "Return the index and entry index as a tuple for 'key'."
2.52 +
2.53 + # Find an index identifying the bucket involved.
2.54 +
2.55 + index = self._get_index(key)
2.56 +
2.57 + # Find the entry index within the bucket of the key.
2.58 +
2.59 + i = self._find_entry(key, index)
2.60 +
2.61 + return index, i
2.62 +
2.63 + def _get_index(self, key):
2.64 +
2.65 + "Check 'key' and return an index or raise TypeError."
2.66 +
2.67 + index = key.__hash__()
2.68 +
2.69 + if not _isinstance(index, int):
2.70 + raise TypeError
2.71 +
2.72 + return index % len(self.buckets)
2.73 +
2.74 + def _find_entry(self, key, index):
2.75 +
2.76 + """
2.77 + Search for 'key', using an 'index' identifying the bucket involved.
2.78 + Method to be overridden by subclasses.
2.79 + """
2.80 +
2.81 + pass
2.82 +
2.83 + def _items(self):
2.84 +
2.85 + "Return the values stored in all buckets."
2.86 +
2.87 + l = []
2.88 + for bucket in self.buckets:
2.89 + l += bucket
2.90 + return l
2.91 +
2.92 + def _remove_entry(self, key):
2.93 +
2.94 + "Remove the entry associated with the given 'key'."
2.95 +
2.96 + index, i = self._get_entry(key)
2.97 +
2.98 + if index is None or i is None:
2.99 + raise KeyError, key
2.100 +
2.101 + del self.buckets[index][i]
2.102 + self.size -= 1
2.103 +
2.104 + def _resize(self, capacity):
2.105 +
2.106 + """
2.107 + Resize the hashtable to have the given 'capacity'.
2.108 + Method to be overridden by subclasses.
2.109 + """
2.110 +
2.111 + pass
2.112 +
2.113 + # Public conventional methods.
2.114 +
2.115 + def clear(self):
2.116 +
2.117 + "Reset the dictionary to an empty state."
2.118 +
2.119 + self.size = 0
2.120 + self.buckets = self._get_buckets(0)
2.121 +
2.122 +# vim: tabstop=4 expandtab shiftwidth=4
3.1 --- a/lib/__builtins__/set.py Sat Feb 04 17:49:34 2017 +0100
3.2 +++ b/lib/__builtins__/set.py Sat Feb 04 18:10:20 2017 +0100
3.3 @@ -20,22 +20,94 @@
3.4 """
3.5
3.6 from __builtins__.iteration.iterator import itemiterator
3.7 +from __builtins__.mapping import hashtable
3.8
3.9 -class frozenset:
3.10 - def __init__(self, iterable): pass
3.11 +class frozenset(hashtable):
3.12 +
3.13 + "An immutable set representation holding a collection of distinct values."
3.14 +
3.15 + def __init__(self, iterable=None):
3.16 +
3.17 + "Initialise the set with any given 'iterable'."
3.18 +
3.19 + self.clear()
3.20 +
3.21 + if iterable is not None:
3.22 + for value in iterable:
3.23 + self._setitem(self.buckets, value)
3.24 +
3.25 + # Implementation methods.
3.26 +
3.27 + def _find_entry(self, value, index):
3.28 +
3.29 + "Search for 'value', using an 'index' identifying the bucket involved."
3.30 +
3.31 + i = 0
3.32 +
3.33 + for found in self.buckets[index]:
3.34 + if found == value:
3.35 + return i
3.36 + i += 1
3.37 +
3.38 + return None
3.39 +
3.40 + def _resize(self, capacity):
3.41 +
3.42 + "Resize the hashtable to have the given 'capacity'."
3.43 +
3.44 + buckets = self._get_buckets(capacity)
3.45 +
3.46 + for value in self._items():
3.47 + self._setitem(buckets, value)
3.48 +
3.49 + self.buckets = buckets
3.50 +
3.51 + def _setitem(self, buckets, value):
3.52
3.53 -class set:
3.54 - def __init__(self, iterable): pass
3.55 - def add(self, item): pass
3.56 - def clear(self): pass
3.57 - def copy(self): pass
3.58 - def difference(self, other): pass
3.59 - def difference_update(self, other): pass
3.60 - def discard(self, item): pass
3.61 - def intersection(self, other): pass
3.62 - def intersection_update(self, other): pass
3.63 - def issubset(self, other): pass
3.64 - def issuperset(self, other): pass
3.65 + "Set in the 'buckets' an item having the given 'value'."
3.66 +
3.67 + index, i = self._get_entry(value)
3.68 +
3.69 + # With no existing entry, append to the bucket.
3.70 +
3.71 + if i is None:
3.72 + buckets[index].append(value)
3.73 + self.size += 1
3.74 +
3.75 + # With an existing entry, replace the item.
3.76 +
3.77 + else:
3.78 + buckets[index][i] = value
3.79 +
3.80 + # String representations.
3.81 +
3.82 + def _str(self, name):
3.83 +
3.84 + "Return a string representation."
3.85 +
3.86 + b = buffer()
3.87 + b.append(name)
3.88 + b.append("(")
3.89 + b.append(self._items().__repr__())
3.90 + b.append(")")
3.91 + return str(b)
3.92 +
3.93 + def __str__(self):
3.94 +
3.95 + "Return a string representation."
3.96 +
3.97 + return self._str("frozenset")
3.98 +
3.99 + __repr__ = __str__
3.100 +
3.101 + # Public special methods.
3.102 +
3.103 + def __contains__(self, value):
3.104 +
3.105 + "Return whether 'value' is in the set."
3.106 +
3.107 + index, i = self._get_entry(value)
3.108 + return i is not None
3.109
3.110 def __iter__(self):
3.111
3.112 @@ -43,11 +115,66 @@
3.113
3.114 return itemiterator(list(self))
3.115
3.116 - def pop(self): pass
3.117 - def remove(self, item): pass
3.118 + # Public conventional methods.
3.119 +
3.120 + def copy(self): pass
3.121 + def difference(self, other): pass
3.122 + def intersection(self, other): pass
3.123 + def issubset(self, other): pass
3.124 + def issuperset(self, other): pass
3.125 def symmetric_difference(self, other): pass
3.126 + def union(self, other): pass
3.127 +
3.128 +class set(frozenset):
3.129 +
3.130 + "A mutable set representation holding a collection of distinct values."
3.131 +
3.132 + # String representation methods.
3.133 +
3.134 + def __str__(self):
3.135 +
3.136 + "Return a string representation."
3.137 +
3.138 + return self._str("set")
3.139 +
3.140 + __repr__ = __str__
3.141 +
3.142 + # Public conventional methods.
3.143 +
3.144 + def add(self, value):
3.145 +
3.146 + "Add the given 'value' to the set."
3.147 +
3.148 + capacity = len(self.buckets)
3.149 +
3.150 + if self.size > capacity:
3.151 + self._resize(capacity * 2)
3.152 +
3.153 + self._setitem(self.buckets, value)
3.154 +
3.155 + def difference_update(self, other): pass
3.156 +
3.157 + def discard(self, value):
3.158 +
3.159 + "Remove 'value' from the set, if present."
3.160 +
3.161 + try:
3.162 + self.remove(value)
3.163 + except KeyError:
3.164 + pass
3.165 +
3.166 + def intersection_update(self, other): pass
3.167 +
3.168 + def pop(self): pass
3.169 +
3.170 + def remove(self, value):
3.171 +
3.172 + "Remove 'value' from the set."
3.173 +
3.174 + self._remove_entry(value)
3.175 +
3.176 def symmetric_difference_update(self, other): pass
3.177 - def union(self, other): pass
3.178 +
3.179 def update(self, other): pass
3.180
3.181 # vim: tabstop=4 expandtab shiftwidth=4
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/tests/set.py Sat Feb 04 18:10:20 2017 +0100
4.3 @@ -0,0 +1,21 @@
4.4 +s = set()
4.5 +s.add(10)
4.6 +s.add(20)
4.7 +s.add("c")
4.8 +s.add((1, 2))
4.9 +print "# s:",
4.10 +print s
4.11 +print 10 in s
4.12 +print 20 in s
4.13 +print "c" in s
4.14 +print 30 in s
4.15 +print (1, 2) in s
4.16 +
4.17 +s2 = set([10, 20, "c", (1, 2)])
4.18 +print "# s2:",
4.19 +print s
4.20 +print 10 in s2
4.21 +print 20 in s2
4.22 +print "c" in s2
4.23 +print 30 in s2
4.24 +print (1, 2) in s2