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