1 #!/usr/bin/env python 2 3 """ 4 Mapping object support. 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__.span import _max 23 from native import isinstance as _isinstance 24 25 class hashtable: 26 27 "A dictionary representation mapping keys to values." 28 29 def _get_buckets(self, capacity): 30 31 """ 32 Reserve an attribute for a hashtable reference along with some space 33 for elements. 34 """ 35 36 buckets = [] 37 capacity = _max(capacity, 5) 38 i = 0 39 40 while i < capacity: 41 buckets.append([]) 42 i += 1 43 44 return buckets 45 46 def _get_entry(self, key): 47 48 "Return the index and entry index as a tuple for 'key'." 49 50 # Find an index identifying the bucket involved. 51 52 index = self._get_index(key) 53 54 # Find the entry index within the bucket of the key. 55 56 i = self._find_entry(key, index) 57 58 return index, i 59 60 def _get_index(self, key): 61 62 "Check 'key' and return an index or raise TypeError." 63 64 index = key.__hash__() 65 66 if not _isinstance(index, int): 67 raise TypeError 68 69 return index % len(self.buckets) 70 71 def _find_entry(self, key, index): 72 73 """ 74 Search for 'key', using an 'index' identifying the bucket involved. 75 Method to be overridden by subclasses. 76 """ 77 78 pass 79 80 def _items(self): 81 82 "Return the values stored in all buckets." 83 84 l = [] 85 for bucket in self.buckets: 86 l += bucket 87 return l 88 89 def _remove_entry(self, key): 90 91 "Remove the entry associated with the given 'key'." 92 93 index, i = self._get_entry(key) 94 95 if index is None or i is None: 96 raise KeyError, key 97 98 del self.buckets[index][i] 99 self.size -= 1 100 101 def _resize(self, capacity): 102 103 """ 104 Resize the hashtable to have the given 'capacity'. 105 Method to be overridden by subclasses. 106 """ 107 108 pass 109 110 # Public conventional methods. 111 112 def clear(self): 113 114 "Reset the dictionary to an empty state." 115 116 self.size = 0 117 self.buckets = self._get_buckets(0) 118 119 # vim: tabstop=4 expandtab shiftwidth=4