1 #!/usr/bin/env python 2 3 """ 4 Dictionary objects. 5 6 Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from __builtins__.iterator import itemiterator 23 from __builtins__.sequence import _max 24 import native 25 26 class dict: 27 28 "A dictionary representation mapping keys to values." 29 30 MISSING = object() 31 32 def __init__(self, args=None): 33 34 "Initialise the dictionary." 35 36 self.__data__ = self._get_data(args is not None and len(args) / 2 or 0) 37 38 if args is not None: 39 for key, value in args: 40 self.__setitem__(key, value) 41 42 def __str__(self): 43 44 "Return a string representation." 45 46 b = buffer() 47 b.append("{") 48 49 first = True 50 51 for key, value in self.items(): 52 if first: 53 first = False 54 else: 55 b.append(", ") 56 b.append(key.__repr__()) 57 b.append(" : ") 58 b.append(value.__repr__()) 59 60 b.append("}") 61 return str(b) 62 63 __repr__ = __str__ 64 65 def _get_data(self, capacity): 66 67 """ 68 Reserve an attribute for a hashtable reference along with some space 69 for elements. 70 """ 71 72 return native._dict_init(_max(capacity, 5)) 73 74 def _get_index(self, key): 75 76 "Check 'key' and return an index or raise TypeError." 77 78 index = key.__hash__() 79 if not native._isinstance(index, int): 80 raise TypeError 81 82 return index 83 84 def _find_entry(self, key, index): 85 86 "Search for 'key', using an 'index' identifying the bucket involved." 87 88 size = native._dict_bucketsize(self.__data__, index) 89 i = 0 90 91 while i < size: 92 found = native._dict_key(self.__data__, index, i) 93 if found == key: 94 return i 95 i += 1 96 97 return None 98 99 def _resize(self, capacity): 100 101 "Resize the hashtable to have the given 'capacity'." 102 103 newdata = self._get_data(capacity) 104 105 for key, value in self.items(): 106 self._setitem(newdata, key, value) 107 108 self.__data__ = newdata 109 110 def _setitem(self, data, key, value): 111 112 "Set in the 'data' an item having the given 'key' and 'value'." 113 114 # Find an index identifying the bucket involved. 115 116 index = self._get_index(key) 117 118 # Find the entry index within the bucket of the key. 119 120 i = self._find_entry(key, index) 121 122 # With no existing entry, append to the bucket. 123 124 if i is None: 125 native._dict_additem(data, index, key, value) 126 127 # With an existing entry, replace the item. 128 129 else: 130 native._dict_setitem(data, index, i, key, value) 131 132 def __setitem__(self, key, value): 133 134 "Set a mapping from 'key' to 'value' in the dictionary." 135 136 size = native._dict_items(self.__data__) 137 capacity = native._dict_buckets(self.__data__) 138 139 if size > capacity: 140 self._resize(capacity * 2) 141 142 self._setitem(self.__data__, key, value) 143 144 def __delitem__(self, key, value): pass 145 146 def __getitem__(self, key, default=MISSING): 147 148 """ 149 Return the value stored for 'key'. If 'key' does not have an entry in 150 the dictionary, a KeyError will be raised unless 'default' is specified. 151 In which case, 'default' will be returned instead. 152 """ 153 154 # Find an index identifying the bucket involved. 155 156 index = self._get_index(key) 157 158 # Find the entry index within the bucket of the key. 159 160 i = self._find_entry(key, index) 161 162 # With no entry index, either raise an exception or return the default. 163 164 if i is None: 165 if default is self.MISSING: 166 raise KeyError(key) 167 else: 168 return default 169 170 # With a valid entry index, obtain the corresponding value. 171 172 else: 173 return native._dict_value(self.__data__, index, i) 174 175 def clear(self): pass 176 def has_key(self): pass 177 178 def keys(self): 179 180 "Return the keys for this dictionary." 181 182 return native._dict_keys(self.__data__) 183 184 def values(self): 185 186 "Return the values in this dictionary." 187 188 return native._dict_values(self.__data__) 189 190 def items(self): 191 192 "Return the items, each being a (key, value) tuple, in this dictionary." 193 194 return zip([self.keys(), self.values()]) 195 196 def get(self, key): pass 197 def setdefault(self, key, value): pass 198 def update(self, other): pass 199 200 def __iter__(self): 201 202 "Return an iterator." 203 204 return itemiterator(self.keys()) 205 206 # vim: tabstop=4 expandtab shiftwidth=4