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.size = 0 37 self.buckets = self._get_buckets(args is not None and len(args) / 2 or 0) 38 39 if args is not None: 40 for key, value in args: 41 self.__setitem__(key, value) 42 43 def __str__(self): 44 45 "Return a string representation." 46 47 b = buffer() 48 b.append("{") 49 50 first = True 51 52 for key, value in self.items(): 53 if first: 54 first = False 55 else: 56 b.append(", ") 57 b.append(key.__repr__()) 58 b.append(" : ") 59 b.append(value.__repr__()) 60 61 b.append("}") 62 return str(b) 63 64 __repr__ = __str__ 65 66 def _get_buckets(self, capacity): 67 68 """ 69 Reserve an attribute for a hashtable reference along with some space 70 for elements. 71 """ 72 73 buckets = [] 74 capacity = _max(capacity, 5) 75 i = 0 76 77 while i < capacity: 78 buckets.append([]) 79 i += 1 80 81 return buckets 82 83 def _get_index(self, key): 84 85 "Check 'key' and return an index or raise TypeError." 86 87 index = key.__hash__() 88 89 if not native.isinstance(index, int): 90 raise TypeError 91 92 return index % len(self.buckets) 93 94 def _find_entry(self, key, index): 95 96 "Search for 'key', using an 'index' identifying the bucket involved." 97 98 i = 0 99 100 for found, value in self.buckets[index]: 101 if found == key: 102 return i 103 i += 1 104 105 return None 106 107 def _resize(self, capacity): 108 109 "Resize the hashtable to have the given 'capacity'." 110 111 buckets = self._get_buckets(capacity) 112 113 for key, value in self.items(): 114 self._setitem(buckets, key, value) 115 116 self.buckets = buckets 117 118 def _setitem(self, buckets, key, value): 119 120 "Set in the 'buckets' an item having the given 'key' and 'value'." 121 122 # Find an index identifying the bucket involved. 123 124 index = self._get_index(key) 125 126 # Find the entry index within the bucket of the key. 127 128 i = self._find_entry(key, index) 129 130 # With no existing entry, append to the bucket. 131 132 if i is None: 133 buckets[index].append((key, value)) 134 self.size += 1 135 136 # With an existing entry, replace the item. 137 138 else: 139 buckets[index][i] = key, value 140 141 def __setitem__(self, key, value): 142 143 "Set a mapping from 'key' to 'value' in the dictionary." 144 145 capacity = len(self.buckets) 146 147 if self.size > capacity: 148 self._resize(capacity * 2) 149 150 self._setitem(self.buckets, key, value) 151 152 def __delitem__(self, key, value): pass 153 154 def __getitem__(self, key, default=MISSING): 155 156 """ 157 Return the value stored for 'key'. If 'key' does not have an entry in 158 the dictionary, a KeyError will be raised unless 'default' is specified. 159 In which case, 'default' will be returned instead. 160 """ 161 162 # Find an index identifying the bucket involved. 163 164 index = self._get_index(key) 165 166 # Find the entry index within the bucket of the key. 167 168 i = self._find_entry(key, index) 169 170 # With no entry index, either raise an exception or return the default. 171 172 if i is None: 173 if default is self.MISSING: 174 raise KeyError(key) 175 else: 176 return default 177 178 # With a valid entry index, obtain the corresponding value. 179 180 else: 181 return self.buckets[index][i][1] 182 183 def clear(self): pass 184 def has_key(self): pass 185 186 def keys(self): 187 188 "Return the keys for this dictionary." 189 190 l = [] 191 for key, value in self.items(): 192 l.append(key) 193 return l 194 195 def values(self): 196 197 "Return the values in this dictionary." 198 199 l = [] 200 for key, value in self.items(): 201 l.append(value) 202 return l 203 204 def items(self): 205 206 "Return the items, each being a (key, value) tuple, in this dictionary." 207 208 l = [] 209 for bucket in self.buckets: 210 l += bucket 211 return l 212 213 def get(self, key): pass 214 def setdefault(self, key, value): pass 215 def update(self, other): pass 216 217 def __iter__(self): 218 219 "Return an iterator." 220 221 return itemiterator(self.keys()) 222 223 # vim: tabstop=4 expandtab shiftwidth=4