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 itemiterator 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 __str__(self): 45 46 "Return a string representation." 47 48 b = buffer() 49 b.append("{") 50 51 first = True 52 53 for key, value in self.items(): 54 if first: 55 first = False 56 else: 57 b.append(", ") 58 b.append(key.__repr__()) 59 b.append(" : ") 60 b.append(value.__repr__()) 61 62 b.append("}") 63 return str(b) 64 65 __repr__ = __str__ 66 67 def _get_index(self, key): 68 69 "Check 'key' and return an index or raise TypeError." 70 71 index = key.__hash__() 72 if not native._isinstance(index, int): 73 raise TypeError 74 75 return index 76 77 def _find_entry(self, key, index): 78 79 "Search for 'key', using an 'index' identifying the bucket involved." 80 81 size = native._dict_bucketsize(self, index) 82 i = 0 83 84 while i < size: 85 found = native._dict_key(self, index, i) 86 if found == key: 87 return i 88 i += 1 89 90 return None 91 92 def __setitem__(self, key, value): 93 94 "Set a mapping from 'key' to 'value' in the dictionary." 95 96 # Find an index identifying the bucket involved. 97 98 index = self._get_index(key) 99 100 # Find the entry index within the bucket of the key. 101 102 i = self._find_entry(key, index) 103 104 # With no existing entry, append to the bucket. 105 106 if i is None: 107 native._dict_additem(self, index, key, value) 108 109 # With an existing entry, replace the item. 110 111 else: 112 native._dict_setitem(self, index, i, key, value) 113 114 def __delitem__(self, key, value): pass 115 116 def __getitem__(self, key, default=MISSING): 117 118 """ 119 Return the value stored for 'key'. If 'key' does not have an entry in 120 the dictionary, a KeyError will be raised unless 'default' is specified. 121 In which case, 'default' will be returned instead. 122 """ 123 124 # Find an index identifying the bucket involved. 125 126 index = self._get_index(key) 127 128 # Find the entry index within the bucket of the key. 129 130 i = self._find_entry(key, index) 131 132 # With no entry index, either raise an exception or return the default. 133 134 if i is None: 135 if default is self.MISSING: 136 raise KeyError(key) 137 else: 138 return default 139 140 # With a valid entry index, obtain the corresponding value. 141 142 else: 143 return native._dict_value(self, index, i) 144 145 def clear(self): pass 146 def has_key(self): pass 147 148 def keys(self): 149 150 "Return the keys for this dictionary." 151 152 return native._dict_keys(self) 153 154 def values(self): 155 156 "Return the values in this dictionary." 157 158 return native._dict_values(self) 159 160 def items(self): 161 162 "Return the items, each being a (key, value) tuple, in this dictionary." 163 164 return zip([self.keys(), self.values()]) 165 166 def get(self, key): pass 167 def setdefault(self, key, value): pass 168 def update(self, other): pass 169 170 def __iter__(self): 171 172 "Return an iterator." 173 174 return itemiterator(self.keys()) 175 176 # vim: tabstop=4 expandtab shiftwidth=4