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 _items(self): 75 76 "Return the values stored in all buckets." 77 78 l = [] 79 for bucket in self.buckets: 80 l += bucket 81 return l 82 83 def _remove_entry(self, key): 84 85 "Remove the entry associated with the given 'key'." 86 87 index, i = self._get_entry(self.buckets, key) 88 89 if index is None or i is None: 90 raise KeyError, key 91 92 del self.buckets[index][i] 93 self.size -= 1 94 95 # Methods implemented by subclasses: 96 97 # _find_entry(self, buckets, key, index) 98 # _resize(self, capacity) 99 100 # Public special methods. 101 102 def __len__(self): 103 104 "Return the number of items in the mapping." 105 106 n = 0 107 for bucket in self.buckets: 108 n += bucket.__len__() 109 return n 110 111 # Public conventional methods. 112 113 def clear(self): 114 115 "Reset the dictionary to an empty state." 116 117 self.size = 0 118 self.buckets = self._get_buckets(0) 119 120 # vim: tabstop=4 expandtab shiftwidth=4