Lichen

lib/__builtins__/dict.py

932:c07b0dd14f85
10 months ago Paul Boddie Moved integer instantiation support to library functions.
     1 #!/usr/bin/env python     2      3 """     4 Dictionary objects.     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__.mapping import hashtable    23 from __builtins__.iteration.iterator import itemiterator    24     25 class dict(hashtable):    26     27     "A dictionary representation mapping keys to values."    28     29     MISSING = object()    30     31     def __init__(self, iterable=None):    32     33         "Initialise the dictionary with any given 'iterable'."    34     35         self.clear()    36     37         if iterable is not None:    38             for key, value in iterable:    39                 self.__setitem__(key, value)    40     41     # Implementation methods.    42     43     def _find_entry(self, buckets, key, index):    44     45         """    46         Search in 'buckets' for 'key', using an 'index' identifying the bucket    47         involved.    48         """    49     50         i = 0    51     52         for found, value in buckets[index]:    53             if found == key:    54                 return i    55             i += 1    56     57         return None    58     59     def _resize(self, capacity):    60     61         "Resize the hashtable to have the given 'capacity'."    62     63         buckets = self._get_buckets(capacity)    64     65         for key, value in self._items():    66             self._setitem(buckets, key, value)    67     68         self.buckets = buckets    69     70     def _setitem(self, buckets, key, value):    71     72         "Set in the 'buckets' an item having the given 'key' and 'value'."    73     74         index, i = self._get_entry(buckets, key)    75     76         # With no existing entry, append to the bucket.    77     78         if i is None:    79             buckets[index].append((key, value))    80             self.size += 1    81     82         # With an existing entry, replace the item.    83     84         else:    85             buckets[index][i] = key, value    86     87     # String representations.    88     89     def __str__(self):    90     91         "Return a string representation."    92     93         b = buffer()    94         b.append("{")    95     96         first = True    97     98         for key, value in self._items():    99             if first:   100                 first = False   101             else:   102                 b.append(", ")   103             b.append(key.__repr__())   104             b.append(" : ")   105             b.append(value.__repr__())   106    107         b.append("}")   108         return str(b)   109    110     __repr__ = __str__   111    112     # Public special methods.   113    114     def __delitem__(self, key):   115    116         "Remove the entry associated with the given 'key' from this dictionary."   117    118         self._remove_entry(key)   119    120     def __getitem__(self, key):   121    122         "Return the value associated with 'key' from the dictionary."   123    124         return self.get(key, self.MISSING)   125    126     def __iter__(self):   127    128         "Return an iterator."   129    130         return itemiterator(self.keys())   131    132     def __setitem__(self, key, value):   133    134         "Set a mapping from 'key' to 'value' in the dictionary."   135    136         capacity = len(self.buckets)   137    138         if self.size > capacity:   139             self._resize(capacity * 2)   140    141         self._setitem(self.buckets, key, value)   142    143     # Public conventional methods.   144    145     def get(self, key, default=None):   146    147         """   148         Return the value stored for 'key'. If 'key' does not have an entry in   149         the dictionary, 'default' will be returned instead.   150         """   151    152         index, i = self._get_entry(self.buckets, key)   153    154         # With no entry index, either raise an exception or return the default.   155    156         if i is None:   157             if default is self.MISSING:   158                 raise KeyError, key   159             else:   160                 return default   161    162         # With a valid entry index, obtain the corresponding value.   163    164         else:   165             return self.buckets[index][i][1]   166    167     def has_key(self, key):   168    169         "Return whether the given 'key' is used with this dictionary."   170    171         return self.get(key) and True or False   172    173     def keys(self):   174    175         "Return the keys for this dictionary."   176    177         l = []   178         for key, value in self._items():   179             l.append(key)   180         return l   181    182     def items(self):   183    184         "Return the items, each being a (key, value) tuple, in this dictionary."   185    186         return self._items()   187    188     def setdefault(self, key, value):   189    190         """   191         Set for 'key' the given 'value' only if no entry for 'key' is already   192         present. Return the associated value for 'key', which will either be the   193         existing value already present in the dictionary or the supplied 'value'   194         that was given to establish an entry in the dictionary.   195         """   196    197         if not self.has_key(key):   198             self[key] = value   199         return self.get(key)   200    201     def update(self, other):   202    203         "Update this dictionary with the items from 'other'."   204    205         for key, value in other.items():   206             self[key] = value   207    208     def values(self):   209    210         "Return the values in this dictionary."   211    212         l = []   213         for key, value in self._items():   214             l.append(value)   215         return l   216    217 # vim: tabstop=4 expandtab shiftwidth=4