1.1 --- a/lib/__builtins__/dict.py Tue Nov 29 23:13:18 2016 +0100
1.2 +++ b/lib/__builtins__/dict.py Wed Nov 30 16:18:17 2016 +0100
1.3 @@ -3,7 +3,7 @@
1.4 """
1.5 Dictionary objects.
1.6
1.7 -Copyright (C) 2015 Paul Boddie <paul@boddie.org.uk>
1.8 +Copyright (C) 2015, 2016 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 @@ -20,20 +20,120 @@
1.13 """
1.14
1.15 from __builtins__.iterator import listiterator
1.16 +import native
1.17
1.18 -class dict(object):
1.19 - def __init__(self, *args): pass
1.20 - def __setitem__(self, key, value): pass
1.21 +class dict:
1.22 +
1.23 + "A dictionary representation mapping keys to values."
1.24 +
1.25 + MISSING = object()
1.26 +
1.27 + def __init__(self, args=None):
1.28 +
1.29 + "Initialise the dictionary."
1.30 +
1.31 + # Reserve an attribute for a hashtable reference along with some space
1.32 + # for elements.
1.33 +
1.34 + self.__data__ = native._dict_init(args is not None and len(args) or 0)
1.35 +
1.36 + if args is not None:
1.37 + for key, value in args:
1.38 + self.__setitem__(key, value)
1.39 +
1.40 + def _get_index(self, key):
1.41 +
1.42 + "Check 'key' and return an index or raise TypeError."
1.43 +
1.44 + index = key.__hash__()
1.45 + if not native._isinstance(index, int):
1.46 + raise TypeError
1.47 +
1.48 + return index
1.49 +
1.50 + def _find_entry(self, key, index):
1.51 +
1.52 + "Search for 'key', using an 'index' identifying the bucket involved."
1.53 +
1.54 + size = native._dict_bucketsize(self, index)
1.55 + i = 0
1.56 +
1.57 + while i < size:
1.58 + found = native._dict_key(self, index, i)
1.59 + if found == key:
1.60 + return i
1.61 + i += 1
1.62 +
1.63 + return None
1.64 +
1.65 + def __setitem__(self, key, value):
1.66 +
1.67 + "Set a mapping from 'key' to 'value' in the dictionary."
1.68 +
1.69 + # Find an index identifying the bucket involved.
1.70 +
1.71 + index = self._get_index(key)
1.72 +
1.73 + # Find the entry index within the bucket of the key.
1.74 +
1.75 + i = self._find_entry(key, index)
1.76 +
1.77 + # With no existing entry, append to the bucket.
1.78 +
1.79 + if i is None:
1.80 + native._dict_additem(self, index, key, value)
1.81 +
1.82 + # With an existing entry, replace the item.
1.83 +
1.84 + else:
1.85 + native._dict_setitem(self, index, i, key, value)
1.86 +
1.87 def __delitem__(self, key, value): pass
1.88
1.89 - def __getitem__(self, key):
1.90 - # Note usage.
1.91 - KeyError
1.92 + def __getitem__(self, key, default=MISSING):
1.93 +
1.94 + """
1.95 + Return the value stored for 'key'. If 'key' does not have an entry in
1.96 + the dictionary, a KeyError will be raised unless 'default' is specified.
1.97 + In which case, 'default' will be returned instead.
1.98 + """
1.99 +
1.100 + # Find an index identifying the bucket involved.
1.101 +
1.102 + index = self._get_index(key)
1.103 +
1.104 + # Find the entry index within the bucket of the key.
1.105 +
1.106 + i = self._find_entry(key, index)
1.107 +
1.108 + # With no entry index, either raise an exception or return the default.
1.109 +
1.110 + if i is None:
1.111 + if default is self.MISSING:
1.112 + raise KeyError
1.113 + else:
1.114 + return default
1.115 +
1.116 + # With a valid entry index, obtain the corresponding value.
1.117 +
1.118 + else:
1.119 + return native._dict_value(self, index, i)
1.120
1.121 def clear(self): pass
1.122 def has_key(self): pass
1.123 - def keys(self): pass
1.124 - def values(self): pass
1.125 +
1.126 + def keys(self):
1.127 +
1.128 + "Return the keys for this dictionary."
1.129 +
1.130 + return native._dict_keys(self)
1.131 +
1.132 + def values(self):
1.133 +
1.134 + "Return the values in this dictionary."
1.135 +
1.136 + return native._dict_values(self)
1.137 +
1.138 def items(self): pass
1.139 def get(self, key): pass
1.140 def setdefault(self, key, value): pass