paul@542 | 1 | #!/usr/bin/env python |
paul@542 | 2 | |
paul@542 | 3 | """ |
paul@542 | 4 | Mapping object support. |
paul@542 | 5 | |
paul@542 | 6 | Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk> |
paul@542 | 7 | |
paul@542 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@542 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@542 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@542 | 11 | version. |
paul@542 | 12 | |
paul@542 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@542 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@542 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@542 | 16 | details. |
paul@542 | 17 | |
paul@542 | 18 | You should have received a copy of the GNU General Public License along with |
paul@542 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@542 | 20 | """ |
paul@542 | 21 | |
paul@542 | 22 | from __builtins__.span import _max |
paul@787 | 23 | from native import is_int |
paul@542 | 24 | |
paul@542 | 25 | class hashtable: |
paul@542 | 26 | |
paul@542 | 27 | "A dictionary representation mapping keys to values." |
paul@542 | 28 | |
paul@542 | 29 | def _get_buckets(self, capacity): |
paul@542 | 30 | |
paul@542 | 31 | """ |
paul@542 | 32 | Reserve an attribute for a hashtable reference along with some space |
paul@542 | 33 | for elements. |
paul@542 | 34 | """ |
paul@542 | 35 | |
paul@542 | 36 | buckets = [] |
paul@542 | 37 | capacity = _max(capacity, 5) |
paul@542 | 38 | i = 0 |
paul@542 | 39 | |
paul@542 | 40 | while i < capacity: |
paul@542 | 41 | buckets.append([]) |
paul@542 | 42 | i += 1 |
paul@542 | 43 | |
paul@542 | 44 | return buckets |
paul@542 | 45 | |
paul@544 | 46 | def _get_entry(self, buckets, key): |
paul@542 | 47 | |
paul@544 | 48 | "Return the index and entry index as a tuple in 'buckets' for 'key'." |
paul@542 | 49 | |
paul@542 | 50 | # Find an index identifying the bucket involved. |
paul@542 | 51 | |
paul@544 | 52 | index = self._get_index(buckets, key) |
paul@542 | 53 | |
paul@542 | 54 | # Find the entry index within the bucket of the key. |
paul@542 | 55 | |
paul@544 | 56 | i = self._find_entry(buckets, key, index) |
paul@542 | 57 | |
paul@542 | 58 | return index, i |
paul@542 | 59 | |
paul@544 | 60 | def _get_index(self, buckets, key): |
paul@542 | 61 | |
paul@544 | 62 | """ |
paul@544 | 63 | Find in 'buckets' the given 'key', returning an index or raising |
paul@544 | 64 | TypeError. |
paul@544 | 65 | """ |
paul@542 | 66 | |
paul@542 | 67 | index = key.__hash__() |
paul@542 | 68 | |
paul@787 | 69 | if not is_int(index): |
paul@542 | 70 | raise TypeError |
paul@542 | 71 | |
paul@542 | 72 | return index % len(self.buckets) |
paul@542 | 73 | |
paul@542 | 74 | def _items(self): |
paul@542 | 75 | |
paul@542 | 76 | "Return the values stored in all buckets." |
paul@542 | 77 | |
paul@542 | 78 | l = [] |
paul@542 | 79 | for bucket in self.buckets: |
paul@542 | 80 | l += bucket |
paul@542 | 81 | return l |
paul@542 | 82 | |
paul@542 | 83 | def _remove_entry(self, key): |
paul@542 | 84 | |
paul@542 | 85 | "Remove the entry associated with the given 'key'." |
paul@542 | 86 | |
paul@547 | 87 | index, i = self._get_entry(self.buckets, key) |
paul@542 | 88 | |
paul@542 | 89 | if index is None or i is None: |
paul@542 | 90 | raise KeyError, key |
paul@542 | 91 | |
paul@542 | 92 | del self.buckets[index][i] |
paul@542 | 93 | self.size -= 1 |
paul@542 | 94 | |
paul@816 | 95 | # Methods implemented by subclasses: |
paul@542 | 96 | |
paul@816 | 97 | # _find_entry(self, buckets, key, index) |
paul@816 | 98 | # _resize(self, capacity) |
paul@542 | 99 | |
paul@544 | 100 | # Public special methods. |
paul@544 | 101 | |
paul@544 | 102 | def __len__(self): |
paul@544 | 103 | |
paul@544 | 104 | "Return the number of items in the mapping." |
paul@544 | 105 | |
paul@544 | 106 | n = 0 |
paul@544 | 107 | for bucket in self.buckets: |
paul@544 | 108 | n += bucket.__len__() |
paul@544 | 109 | return n |
paul@544 | 110 | |
paul@542 | 111 | # Public conventional methods. |
paul@542 | 112 | |
paul@542 | 113 | def clear(self): |
paul@542 | 114 | |
paul@542 | 115 | "Reset the dictionary to an empty state." |
paul@542 | 116 | |
paul@542 | 117 | self.size = 0 |
paul@542 | 118 | self.buckets = self._get_buckets(0) |
paul@542 | 119 | |
paul@542 | 120 | # vim: tabstop=4 expandtab shiftwidth=4 |