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 is_int 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, buckets, key): 47 48 "Return the index and entry index as a tuple in 'buckets' for 'key'." 49 50 # Find an index identifying the bucket involved. 51 52 index = self._get_index(buckets, key) 53 54 # Find the entry index within the bucket of the key. 55 56 i = self._find_entry(buckets, key, index) 57 58 return index, i 59 60 def _get_index(self, buckets, key): 61 62 """ 63 Find in 'buckets' the given 'key', returning an index or raising 64 TypeError. 65 """ 66 67 index = key.__hash__() 68 69 if not is_int(index): 70 raise TypeError 71 72 return index % len(self.buckets) 73 74 def _find_entry(self, buckets, key, index): 75 76 """ 77 Search in 'buckets' for 'key', using an 'index' identifying the bucket 78 involved. 79 80 Method to be overridden by subclasses. 81 """ 82 83 pass 84 85 def _items(self): 86 87 "Return the values stored in all buckets." 88 89 l = [] 90 for bucket in self.buckets: 91 l += bucket 92 return l 93 94 def _remove_entry(self, key): 95 96 "Remove the entry associated with the given 'key'." 97 98 index, i = self._get_entry(self.buckets, key) 99 100 if index is None or i is None: 101 raise KeyError, key 102 103 del self.buckets[index][i] 104 self.size -= 1 105 106 def _resize(self, capacity): 107 108 """ 109 Resize the hashtable to have the given 'capacity'. 110 Method to be overridden by subclasses. 111 """ 112 113 pass 114 115 # Public special methods. 116 117 def __len__(self): 118 119 "Return the number of items in the mapping." 120 121 n = 0 122 for bucket in self.buckets: 123 n += bucket.__len__() 124 return n 125 126 # Public conventional methods. 127 128 def clear(self): 129 130 "Reset the dictionary to an empty state." 131 132 self.size = 0 133 self.buckets = self._get_buckets(0) 134 135 # vim: tabstop=4 expandtab shiftwidth=4
