paul@6 | 1 | #!/usr/bin/env python |
paul@6 | 2 | |
paul@6 | 3 | """ |
paul@6 | 4 | Dictionary objects. |
paul@6 | 5 | |
paul@283 | 6 | Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk> |
paul@6 | 7 | |
paul@6 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@6 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@6 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@6 | 11 | version. |
paul@6 | 12 | |
paul@6 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@6 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@6 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@6 | 16 | details. |
paul@6 | 17 | |
paul@6 | 18 | You should have received a copy of the GNU General Public License along with |
paul@6 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@6 | 20 | """ |
paul@6 | 21 | |
paul@6 | 22 | from __builtins__.iterator import listiterator |
paul@283 | 23 | import native |
paul@6 | 24 | |
paul@283 | 25 | class dict: |
paul@283 | 26 | |
paul@283 | 27 | "A dictionary representation mapping keys to values." |
paul@283 | 28 | |
paul@283 | 29 | MISSING = object() |
paul@283 | 30 | |
paul@283 | 31 | def __init__(self, args=None): |
paul@283 | 32 | |
paul@283 | 33 | "Initialise the dictionary." |
paul@283 | 34 | |
paul@283 | 35 | # Reserve an attribute for a hashtable reference along with some space |
paul@283 | 36 | # for elements. |
paul@283 | 37 | |
paul@283 | 38 | self.__data__ = native._dict_init(args is not None and len(args) or 0) |
paul@283 | 39 | |
paul@283 | 40 | if args is not None: |
paul@283 | 41 | for key, value in args: |
paul@283 | 42 | self.__setitem__(key, value) |
paul@283 | 43 | |
paul@283 | 44 | def _get_index(self, key): |
paul@283 | 45 | |
paul@283 | 46 | "Check 'key' and return an index or raise TypeError." |
paul@283 | 47 | |
paul@283 | 48 | index = key.__hash__() |
paul@283 | 49 | if not native._isinstance(index, int): |
paul@283 | 50 | raise TypeError |
paul@283 | 51 | |
paul@283 | 52 | return index |
paul@283 | 53 | |
paul@283 | 54 | def _find_entry(self, key, index): |
paul@283 | 55 | |
paul@283 | 56 | "Search for 'key', using an 'index' identifying the bucket involved." |
paul@283 | 57 | |
paul@283 | 58 | size = native._dict_bucketsize(self, index) |
paul@283 | 59 | i = 0 |
paul@283 | 60 | |
paul@283 | 61 | while i < size: |
paul@283 | 62 | found = native._dict_key(self, index, i) |
paul@283 | 63 | if found == key: |
paul@283 | 64 | return i |
paul@283 | 65 | i += 1 |
paul@283 | 66 | |
paul@283 | 67 | return None |
paul@283 | 68 | |
paul@283 | 69 | def __setitem__(self, key, value): |
paul@283 | 70 | |
paul@283 | 71 | "Set a mapping from 'key' to 'value' in the dictionary." |
paul@283 | 72 | |
paul@283 | 73 | # Find an index identifying the bucket involved. |
paul@283 | 74 | |
paul@283 | 75 | index = self._get_index(key) |
paul@283 | 76 | |
paul@283 | 77 | # Find the entry index within the bucket of the key. |
paul@283 | 78 | |
paul@283 | 79 | i = self._find_entry(key, index) |
paul@283 | 80 | |
paul@283 | 81 | # With no existing entry, append to the bucket. |
paul@283 | 82 | |
paul@283 | 83 | if i is None: |
paul@283 | 84 | native._dict_additem(self, index, key, value) |
paul@283 | 85 | |
paul@283 | 86 | # With an existing entry, replace the item. |
paul@283 | 87 | |
paul@283 | 88 | else: |
paul@283 | 89 | native._dict_setitem(self, index, i, key, value) |
paul@283 | 90 | |
paul@6 | 91 | def __delitem__(self, key, value): pass |
paul@6 | 92 | |
paul@283 | 93 | def __getitem__(self, key, default=MISSING): |
paul@283 | 94 | |
paul@283 | 95 | """ |
paul@283 | 96 | Return the value stored for 'key'. If 'key' does not have an entry in |
paul@283 | 97 | the dictionary, a KeyError will be raised unless 'default' is specified. |
paul@283 | 98 | In which case, 'default' will be returned instead. |
paul@283 | 99 | """ |
paul@283 | 100 | |
paul@283 | 101 | # Find an index identifying the bucket involved. |
paul@283 | 102 | |
paul@283 | 103 | index = self._get_index(key) |
paul@283 | 104 | |
paul@283 | 105 | # Find the entry index within the bucket of the key. |
paul@283 | 106 | |
paul@283 | 107 | i = self._find_entry(key, index) |
paul@283 | 108 | |
paul@283 | 109 | # With no entry index, either raise an exception or return the default. |
paul@283 | 110 | |
paul@283 | 111 | if i is None: |
paul@283 | 112 | if default is self.MISSING: |
paul@288 | 113 | raise KeyError(key) |
paul@283 | 114 | else: |
paul@283 | 115 | return default |
paul@283 | 116 | |
paul@283 | 117 | # With a valid entry index, obtain the corresponding value. |
paul@283 | 118 | |
paul@283 | 119 | else: |
paul@283 | 120 | return native._dict_value(self, index, i) |
paul@6 | 121 | |
paul@6 | 122 | def clear(self): pass |
paul@6 | 123 | def has_key(self): pass |
paul@283 | 124 | |
paul@283 | 125 | def keys(self): |
paul@283 | 126 | |
paul@283 | 127 | "Return the keys for this dictionary." |
paul@283 | 128 | |
paul@283 | 129 | return native._dict_keys(self) |
paul@283 | 130 | |
paul@283 | 131 | def values(self): |
paul@283 | 132 | |
paul@283 | 133 | "Return the values in this dictionary." |
paul@283 | 134 | |
paul@283 | 135 | return native._dict_values(self) |
paul@283 | 136 | |
paul@288 | 137 | def items(self): |
paul@288 | 138 | |
paul@288 | 139 | "Return the items, each being a (key, value) tuple, in this dictionary." |
paul@288 | 140 | |
paul@288 | 141 | return zip([self.keys(), self.values()]) |
paul@288 | 142 | |
paul@6 | 143 | def get(self, key): pass |
paul@6 | 144 | def setdefault(self, key, value): pass |
paul@6 | 145 | def update(self, other): pass |
paul@6 | 146 | |
paul@6 | 147 | def __iter__(self): |
paul@6 | 148 | |
paul@6 | 149 | "Return an iterator." |
paul@6 | 150 | |
paul@6 | 151 | return listiterator(self.keys()) |
paul@6 | 152 | |
paul@6 | 153 | # vim: tabstop=4 expandtab shiftwidth=4 |