Lichen

lib/__builtins__/mapping.py

932:c07b0dd14f85
10 months ago Paul Boddie Moved integer instantiation support to library functions.
     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