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, key, index): 44 45 "Search for 'key', using an 'index' identifying the bucket involved." 46 47 i = 0 48 49 for found, value in self.buckets[index]: 50 if found == key: 51 return i 52 i += 1 53 54 return None 55 56 def _resize(self, capacity): 57 58 "Resize the hashtable to have the given 'capacity'." 59 60 buckets = self._get_buckets(capacity) 61 62 for key, value in self._items(): 63 self._setitem(buckets, key, value) 64 65 self.buckets = buckets 66 67 def _setitem(self, buckets, key, value): 68 69 "Set in the 'buckets' an item having the given 'key' and 'value'." 70 71 index, i = self._get_entry(key) 72 73 # With no existing entry, append to the bucket. 74 75 if i is None: 76 buckets[index].append((key, value)) 77 self.size += 1 78 79 # With an existing entry, replace the item. 80 81 else: 82 buckets[index][i] = key, value 83 84 # String representations. 85 86 def __str__(self): 87 88 "Return a string representation." 89 90 b = buffer() 91 b.append("{") 92 93 first = True 94 95 for key, value in self._items(): 96 if first: 97 first = False 98 else: 99 b.append(", ") 100 b.append(key.__repr__()) 101 b.append(" : ") 102 b.append(value.__repr__()) 103 104 b.append("}") 105 return str(b) 106 107 __repr__ = __str__ 108 109 # Public special methods. 110 111 def __delitem__(self, key): 112 113 "Remove the entry associated with the given 'key' from this dictionary." 114 115 self._remove_entry(key) 116 117 def __getitem__(self, key): 118 119 "Return the value associated with 'key' from the dictionary." 120 121 return self.get(key, self.MISSING) 122 123 def __iter__(self): 124 125 "Return an iterator." 126 127 return itemiterator(self.keys()) 128 129 def __setitem__(self, key, value): 130 131 "Set a mapping from 'key' to 'value' in the dictionary." 132 133 capacity = len(self.buckets) 134 135 if self.size > capacity: 136 self._resize(capacity * 2) 137 138 self._setitem(self.buckets, key, value) 139 140 # Public conventional methods. 141 142 def get(self, key, default=None): 143 144 """ 145 Return the value stored for 'key'. If 'key' does not have an entry in 146 the dictionary, 'default' will be returned instead. 147 """ 148 149 index, i = self._get_entry(key) 150 151 # With no entry index, either raise an exception or return the default. 152 153 if i is None: 154 if default is self.MISSING: 155 raise KeyError(key) 156 else: 157 return default 158 159 # With a valid entry index, obtain the corresponding value. 160 161 else: 162 return self.buckets[index][i][1] 163 164 def has_key(self, key): 165 166 "Return whether the given 'key' is used with this dictionary." 167 168 return self.get(key) and True or False 169 170 def keys(self): 171 172 "Return the keys for this dictionary." 173 174 l = [] 175 for key, value in self._items(): 176 l.append(key) 177 return l 178 179 def items(self): 180 181 "Return the items, each being a (key, value) tuple, in this dictionary." 182 183 return self._items() 184 185 def setdefault(self, key, value): pass 186 187 def update(self, other): pass 188 189 def values(self): 190 191 "Return the values in this dictionary." 192 193 l = [] 194 for key, value in self._items(): 195 l.append(value) 196 return l 197 198 # vim: tabstop=4 expandtab shiftwidth=4