1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lib/__builtins__/mapping.py Sat Feb 04 18:10:20 2017 +0100
1.3 @@ -0,0 +1,119 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +Mapping object support.
1.8 +
1.9 +Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>
1.10 +
1.11 +This program is free software; you can redistribute it and/or modify it under
1.12 +the terms of the GNU General Public License as published by the Free Software
1.13 +Foundation; either version 3 of the License, or (at your option) any later
1.14 +version.
1.15 +
1.16 +This program is distributed in the hope that it will be useful, but WITHOUT
1.17 +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.18 +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.19 +details.
1.20 +
1.21 +You should have received a copy of the GNU General Public License along with
1.22 +this program. If not, see <http://www.gnu.org/licenses/>.
1.23 +"""
1.24 +
1.25 +from __builtins__.span import _max
1.26 +from native import isinstance as _isinstance
1.27 +
1.28 +class hashtable:
1.29 +
1.30 + "A dictionary representation mapping keys to values."
1.31 +
1.32 + def _get_buckets(self, capacity):
1.33 +
1.34 + """
1.35 + Reserve an attribute for a hashtable reference along with some space
1.36 + for elements.
1.37 + """
1.38 +
1.39 + buckets = []
1.40 + capacity = _max(capacity, 5)
1.41 + i = 0
1.42 +
1.43 + while i < capacity:
1.44 + buckets.append([])
1.45 + i += 1
1.46 +
1.47 + return buckets
1.48 +
1.49 + def _get_entry(self, key):
1.50 +
1.51 + "Return the index and entry index as a tuple for 'key'."
1.52 +
1.53 + # Find an index identifying the bucket involved.
1.54 +
1.55 + index = self._get_index(key)
1.56 +
1.57 + # Find the entry index within the bucket of the key.
1.58 +
1.59 + i = self._find_entry(key, index)
1.60 +
1.61 + return index, i
1.62 +
1.63 + def _get_index(self, key):
1.64 +
1.65 + "Check 'key' and return an index or raise TypeError."
1.66 +
1.67 + index = key.__hash__()
1.68 +
1.69 + if not _isinstance(index, int):
1.70 + raise TypeError
1.71 +
1.72 + return index % len(self.buckets)
1.73 +
1.74 + def _find_entry(self, key, index):
1.75 +
1.76 + """
1.77 + Search for 'key', using an 'index' identifying the bucket involved.
1.78 + Method to be overridden by subclasses.
1.79 + """
1.80 +
1.81 + pass
1.82 +
1.83 + def _items(self):
1.84 +
1.85 + "Return the values stored in all buckets."
1.86 +
1.87 + l = []
1.88 + for bucket in self.buckets:
1.89 + l += bucket
1.90 + return l
1.91 +
1.92 + def _remove_entry(self, key):
1.93 +
1.94 + "Remove the entry associated with the given 'key'."
1.95 +
1.96 + index, i = self._get_entry(key)
1.97 +
1.98 + if index is None or i is None:
1.99 + raise KeyError, key
1.100 +
1.101 + del self.buckets[index][i]
1.102 + self.size -= 1
1.103 +
1.104 + def _resize(self, capacity):
1.105 +
1.106 + """
1.107 + Resize the hashtable to have the given 'capacity'.
1.108 + Method to be overridden by subclasses.
1.109 + """
1.110 +
1.111 + pass
1.112 +
1.113 + # Public conventional methods.
1.114 +
1.115 + def clear(self):
1.116 +
1.117 + "Reset the dictionary to an empty state."
1.118 +
1.119 + self.size = 0
1.120 + self.buckets = self._get_buckets(0)
1.121 +
1.122 +# vim: tabstop=4 expandtab shiftwidth=4