1 #!/usr/bin/env python 2 3 """ 4 Dictionary objects. 5 6 Copyright (C) 2015, 2016, 2017 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__.mapping import hashtable 23 from __builtins__.iteration.iterator import itemiterator 24 25 class dict(hashtable): 26 27 "A dictionary representation mapping keys to values." 28 29 MISSING = object() 30 31 def __init__(self, iterable=None): 32 33 "Initialise the dictionary with any given 'iterable'." 34 35 self.clear() 36 37 if iterable is not None: 38 for key, value in iterable: 39 self.__setitem__(key, value) 40 41 # Implementation methods. 42 43 def _find_entry(self, buckets, key, index): 44 45 """ 46 Search in 'buckets' for 'key', using an 'index' identifying the bucket 47 involved. 48 """ 49 50 i = 0 51 52 for found, value in buckets[index]: 53 if found == key: 54 return i 55 i += 1 56 57 return None 58 59 def _resize(self, capacity): 60 61 "Resize the hashtable to have the given 'capacity'." 62 63 buckets = self._get_buckets(capacity) 64 65 for key, value in self._items(): 66 self._setitem(buckets, key, value) 67 68 self.buckets = buckets 69 70 def _setitem(self, buckets, key, value): 71 72 "Set in the 'buckets' an item having the given 'key' and 'value'." 73 74 index, i = self._get_entry(buckets, key) 75 76 # With no existing entry, append to the bucket. 77 78 if i is None: 79 buckets[index].append((key, value)) 80 self.size += 1 81 82 # With an existing entry, replace the item. 83 84 else: 85 buckets[index][i] = key, value 86 87 # String representations. 88 89 def __str__(self): 90 91 "Return a string representation." 92 93 b = buffer() 94 b.append("{") 95 96 first = True 97 98 for key, value in self._items(): 99 if first: 100 first = False 101 else: 102 b.append(", ") 103 b.append(key.__repr__()) 104 b.append(" : ") 105 b.append(value.__repr__()) 106 107 b.append("}") 108 return str(b) 109 110 __repr__ = __str__ 111 112 # Public special methods. 113 114 def __delitem__(self, key): 115 116 "Remove the entry associated with the given 'key' from this dictionary." 117 118 self._remove_entry(key) 119 120 def __getitem__(self, key): 121 122 "Return the value associated with 'key' from the dictionary." 123 124 return self.get(key, self.MISSING) 125 126 def __iter__(self): 127 128 "Return an iterator." 129 130 return itemiterator(self.keys()) 131 132 def __setitem__(self, key, value): 133 134 "Set a mapping from 'key' to 'value' in the dictionary." 135 136 capacity = len(self.buckets) 137 138 if self.size > capacity: 139 self._resize(capacity * 2) 140 141 self._setitem(self.buckets, key, value) 142 143 # Public conventional methods. 144 145 def get(self, key, default=None): 146 147 """ 148 Return the value stored for 'key'. If 'key' does not have an entry in 149 the dictionary, 'default' will be returned instead. 150 """ 151 152 index, i = self._get_entry(self.buckets, key) 153 154 # With no entry index, either raise an exception or return the default. 155 156 if i is None: 157 if default is self.MISSING: 158 raise KeyError, key 159 else: 160 return default 161 162 # With a valid entry index, obtain the corresponding value. 163 164 else: 165 return self.buckets[index][i][1] 166 167 def has_key(self, key): 168 169 "Return whether the given 'key' is used with this dictionary." 170 171 return self.get(key) and True or False 172 173 def keys(self): 174 175 "Return the keys for this dictionary." 176 177 l = [] 178 for key, value in self._items(): 179 l.append(key) 180 return l 181 182 def items(self): 183 184 "Return the items, each being a (key, value) tuple, in this dictionary." 185 186 return self._items() 187 188 def setdefault(self, key, value): 189 190 """ 191 Set for 'key' the given 'value' only if no entry for 'key' is already 192 present. Return the associated value for 'key', which will either be the 193 existing value already present in the dictionary or the supplied 'value' 194 that was given to establish an entry in the dictionary. 195 """ 196 197 if not self.has_key(key): 198 self[key] = value 199 return self.get(key) 200 201 def update(self, other): 202 203 "Update this dictionary with the items from 'other'." 204 205 for key, value in other.items(): 206 self[key] = value 207 208 def values(self): 209 210 "Return the values in this dictionary." 211 212 l = [] 213 for key, value in self._items(): 214 l.append(value) 215 return l 216 217 # vim: tabstop=4 expandtab shiftwidth=4