1 #!/usr/bin/env python 2 3 """ 4 Dictionary objects. 5 6 Copyright (C) 2015, 2016 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__.iterator import listiterator 23 import native 24 25 class dict: 26 27 "A dictionary representation mapping keys to values." 28 29 MISSING = object() 30 31 def __init__(self, args=None): 32 33 "Initialise the dictionary." 34 35 # Reserve an attribute for a hashtable reference along with some space 36 # for elements. 37 38 self.__data__ = native._dict_init(args is not None and len(args) or 0) 39 40 if args is not None: 41 for key, value in args: 42 self.__setitem__(key, value) 43 44 def _get_index(self, key): 45 46 "Check 'key' and return an index or raise TypeError." 47 48 index = key.__hash__() 49 if not native._isinstance(index, int): 50 raise TypeError 51 52 return index 53 54 def _find_entry(self, key, index): 55 56 "Search for 'key', using an 'index' identifying the bucket involved." 57 58 size = native._dict_bucketsize(self, index) 59 i = 0 60 61 while i < size: 62 found = native._dict_key(self, index, i) 63 if found == key: 64 return i 65 i += 1 66 67 return None 68 69 def __setitem__(self, key, value): 70 71 "Set a mapping from 'key' to 'value' in the dictionary." 72 73 # Find an index identifying the bucket involved. 74 75 index = self._get_index(key) 76 77 # Find the entry index within the bucket of the key. 78 79 i = self._find_entry(key, index) 80 81 # With no existing entry, append to the bucket. 82 83 if i is None: 84 native._dict_additem(self, index, key, value) 85 86 # With an existing entry, replace the item. 87 88 else: 89 native._dict_setitem(self, index, i, key, value) 90 91 def __delitem__(self, key, value): pass 92 93 def __getitem__(self, key, default=MISSING): 94 95 """ 96 Return the value stored for 'key'. If 'key' does not have an entry in 97 the dictionary, a KeyError will be raised unless 'default' is specified. 98 In which case, 'default' will be returned instead. 99 """ 100 101 # Find an index identifying the bucket involved. 102 103 index = self._get_index(key) 104 105 # Find the entry index within the bucket of the key. 106 107 i = self._find_entry(key, index) 108 109 # With no entry index, either raise an exception or return the default. 110 111 if i is None: 112 if default is self.MISSING: 113 raise KeyError(key) 114 else: 115 return default 116 117 # With a valid entry index, obtain the corresponding value. 118 119 else: 120 return native._dict_value(self, index, i) 121 122 def clear(self): pass 123 def has_key(self): pass 124 125 def keys(self): 126 127 "Return the keys for this dictionary." 128 129 return native._dict_keys(self) 130 131 def values(self): 132 133 "Return the values in this dictionary." 134 135 return native._dict_values(self) 136 137 def items(self): 138 139 "Return the items, each being a (key, value) tuple, in this dictionary." 140 141 return zip([self.keys(), self.values()]) 142 143 def get(self, key): pass 144 def setdefault(self, key, value): pass 145 def update(self, other): pass 146 147 def __iter__(self): 148 149 "Return an iterator." 150 151 return listiterator(self.keys()) 152 153 # vim: tabstop=4 expandtab shiftwidth=4