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