1.1 --- a/lib/__builtins__/dict.py Fri Dec 02 22:26:53 2016 +0100
1.2 +++ b/lib/__builtins__/dict.py Sat Dec 03 01:23:18 2016 +0100
1.3 @@ -33,7 +33,8 @@
1.4
1.5 "Initialise the dictionary."
1.6
1.7 - self.__data__ = self._get_data(args is not None and len(args) / 2 or 0)
1.8 + self.size = 0
1.9 + self.buckets = self._get_buckets(args is not None and len(args) / 2 or 0)
1.10
1.11 if args is not None:
1.12 for key, value in args:
1.13 @@ -62,34 +63,41 @@
1.14
1.15 __repr__ = __str__
1.16
1.17 - def _get_data(self, capacity):
1.18 + def _get_buckets(self, capacity):
1.19
1.20 """
1.21 Reserve an attribute for a hashtable reference along with some space
1.22 for elements.
1.23 """
1.24
1.25 - return native._dict_init(_max(capacity, 5))
1.26 + buckets = []
1.27 + capacity = _max(capacity, 5)
1.28 + i = 0
1.29 +
1.30 + while i < capacity:
1.31 + buckets.append([])
1.32 + i += 1
1.33 +
1.34 + return buckets
1.35
1.36 def _get_index(self, key):
1.37
1.38 "Check 'key' and return an index or raise TypeError."
1.39
1.40 index = key.__hash__()
1.41 +
1.42 if not native._isinstance(index, int):
1.43 raise TypeError
1.44
1.45 - return index
1.46 + return index % len(self.buckets)
1.47
1.48 def _find_entry(self, key, index):
1.49
1.50 "Search for 'key', using an 'index' identifying the bucket involved."
1.51
1.52 - size = native._dict_bucketsize(self.__data__, index)
1.53 i = 0
1.54
1.55 - while i < size:
1.56 - found = native._dict_key(self.__data__, index, i)
1.57 + for found, value in self.buckets[index]:
1.58 if found == key:
1.59 return i
1.60 i += 1
1.61 @@ -100,16 +108,16 @@
1.62
1.63 "Resize the hashtable to have the given 'capacity'."
1.64
1.65 - newdata = self._get_data(capacity)
1.66 + buckets = self._get_buckets(capacity)
1.67
1.68 for key, value in self.items():
1.69 - self._setitem(newdata, key, value)
1.70 + self._setitem(buckets, key, value)
1.71
1.72 - self.__data__ = newdata
1.73 + self.buckets = buckets
1.74
1.75 - def _setitem(self, data, key, value):
1.76 + def _setitem(self, buckets, key, value):
1.77
1.78 - "Set in the 'data' an item having the given 'key' and 'value'."
1.79 + "Set in the 'buckets' an item having the given 'key' and 'value'."
1.80
1.81 # Find an index identifying the bucket involved.
1.82
1.83 @@ -122,24 +130,24 @@
1.84 # With no existing entry, append to the bucket.
1.85
1.86 if i is None:
1.87 - native._dict_additem(data, index, key, value)
1.88 + buckets[index].append((key, value))
1.89 + self.size += 1
1.90
1.91 # With an existing entry, replace the item.
1.92
1.93 else:
1.94 - native._dict_setitem(data, index, i, key, value)
1.95 + buckets[index][i] = key, value
1.96
1.97 def __setitem__(self, key, value):
1.98
1.99 "Set a mapping from 'key' to 'value' in the dictionary."
1.100
1.101 - size = native._dict_items(self.__data__)
1.102 - capacity = native._dict_buckets(self.__data__)
1.103 + capacity = len(self.buckets)
1.104
1.105 - if size > capacity:
1.106 + if self.size > capacity:
1.107 self._resize(capacity * 2)
1.108
1.109 - self._setitem(self.__data__, key, value)
1.110 + self._setitem(self.buckets, key, value)
1.111
1.112 def __delitem__(self, key, value): pass
1.113
1.114 @@ -170,7 +178,7 @@
1.115 # With a valid entry index, obtain the corresponding value.
1.116
1.117 else:
1.118 - return native._dict_value(self.__data__, index, i)
1.119 + return self.buckets[index][i][1]
1.120
1.121 def clear(self): pass
1.122 def has_key(self): pass
1.123 @@ -179,19 +187,28 @@
1.124
1.125 "Return the keys for this dictionary."
1.126
1.127 - return native._dict_keys(self.__data__)
1.128 + l = []
1.129 + for key, value in self.items():
1.130 + l.append(key)
1.131 + return l
1.132
1.133 def values(self):
1.134
1.135 "Return the values in this dictionary."
1.136
1.137 - return native._dict_values(self.__data__)
1.138 + l = []
1.139 + for key, value in self.items():
1.140 + l.append(value)
1.141 + return l
1.142
1.143 def items(self):
1.144
1.145 "Return the items, each being a (key, value) tuple, in this dictionary."
1.146
1.147 - return zip([self.keys(), self.values()])
1.148 + l = []
1.149 + for bucket in self.buckets:
1.150 + l += bucket
1.151 + return l
1.152
1.153 def get(self, key): pass
1.154 def setdefault(self, key, value): pass