paul@5 | 1 | #!/usr/bin/env python |
paul@5 | 2 | |
paul@5 | 3 | """ |
paul@5 | 4 | Preparation of run-time attribute lookup tables. |
paul@8 | 5 | |
paul@63 | 6 | Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> |
paul@8 | 7 | |
paul@8 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@8 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@8 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@8 | 11 | version. |
paul@8 | 12 | |
paul@8 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@8 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@8 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@8 | 16 | details. |
paul@8 | 17 | |
paul@8 | 18 | You should have received a copy of the GNU General Public License along with |
paul@8 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@5 | 20 | """ |
paul@5 | 21 | |
paul@63 | 22 | from micropython.common import * |
paul@63 | 23 | |
paul@6 | 24 | class List: |
paul@6 | 25 | |
paul@6 | 26 | """ |
paul@6 | 27 | A displaced list containing attribute details and an index mapping names to |
paul@63 | 28 | offsets in the list. This is the optimised form of the table initially |
paul@63 | 29 | constructed to record object attributes. |
paul@6 | 30 | """ |
paul@6 | 31 | |
paul@7 | 32 | def __init__(self, names): |
paul@6 | 33 | self.names = names |
paul@7 | 34 | self.displaced = [] |
paul@7 | 35 | self.offsets = {} |
paul@7 | 36 | self.offsets_used = set() |
paul@7 | 37 | |
paul@6 | 38 | self.names_index = {} |
paul@6 | 39 | for i, name in enumerate(self.names): |
paul@6 | 40 | self.names_index[name] = i |
paul@6 | 41 | |
paul@7 | 42 | def __len__(self): |
paul@7 | 43 | return len(self.displaced) |
paul@7 | 44 | |
paul@119 | 45 | def __getitem__(self, i): |
paul@119 | 46 | return self.displaced[i] |
paul@119 | 47 | |
paul@7 | 48 | # Simulation methods. |
paul@7 | 49 | |
paul@6 | 50 | def access(self, objname, attrname): |
paul@6 | 51 | obj_offset = self.offsets.get(objname) |
paul@6 | 52 | attr_index = self.names_index.get(attrname) |
paul@6 | 53 | if obj_offset is None or attr_index is None: |
paul@6 | 54 | return None |
paul@6 | 55 | |
paul@6 | 56 | element = self.displaced[obj_offset + attr_index] |
paul@6 | 57 | if element is not None: |
paul@6 | 58 | offset, details = element |
paul@6 | 59 | if offset == obj_offset: |
paul@6 | 60 | return details |
paul@6 | 61 | |
paul@6 | 62 | return None |
paul@6 | 63 | |
paul@7 | 64 | def dir(self, objname): |
paul@7 | 65 | attributes = {} |
paul@7 | 66 | for name in self.names: |
paul@7 | 67 | attr = self.access(objname, name) |
paul@7 | 68 | if attr is not None: |
paul@7 | 69 | attributes[name] = attr |
paul@7 | 70 | return attributes |
paul@7 | 71 | |
paul@7 | 72 | # Update methods. |
paul@7 | 73 | |
paul@7 | 74 | def add(self, objname, attributes): |
paul@7 | 75 | |
paul@7 | 76 | "Add an entry for 'objname' with the given 'attributes'." |
paul@7 | 77 | |
paul@7 | 78 | len_displaced = len(self.displaced) |
paul@7 | 79 | len_attributes = len(attributes) |
paul@7 | 80 | |
paul@7 | 81 | # Try to fit the row into the list, starting from the beginning and |
paul@7 | 82 | # skipping places where an existing row has been fitted. |
paul@7 | 83 | |
paul@7 | 84 | for offset in xrange(0, len_displaced): |
paul@7 | 85 | if offset in self.offsets_used: |
paul@7 | 86 | continue |
paul@7 | 87 | if self._fit_row(offset, attributes, len_displaced): |
paul@7 | 88 | self.offsets_used.add(offset) |
paul@7 | 89 | self.offsets[objname] = offset |
paul@7 | 90 | self._add_row(offset, attributes, len_displaced) |
paul@7 | 91 | break |
paul@7 | 92 | |
paul@7 | 93 | # Where a row could not be fitted within the list, add it to the |
paul@7 | 94 | # end. |
paul@7 | 95 | |
paul@7 | 96 | else: |
paul@7 | 97 | self.offsets_used.add(len_displaced) |
paul@7 | 98 | self.offsets[objname] = len_displaced |
paul@7 | 99 | self._add_row(len_displaced, attributes, len_displaced) |
paul@7 | 100 | |
paul@7 | 101 | def _fit_row(self, offset, attributes, len_displaced): |
paul@7 | 102 | |
paul@7 | 103 | """ |
paul@7 | 104 | Fit, at the given 'offset', the row of 'attributes' in the displaced |
paul@7 | 105 | list having length 'len_displaced'. |
paul@7 | 106 | Return a true value if this succeeded. |
paul@7 | 107 | """ |
paul@7 | 108 | |
paul@7 | 109 | for i, attr in enumerate(attributes): |
paul@7 | 110 | if i + offset >= len_displaced: |
paul@7 | 111 | break |
paul@7 | 112 | element = self.displaced[i + offset] |
paul@7 | 113 | if attr is not None and element is not None: |
paul@7 | 114 | return 0 |
paul@7 | 115 | return 1 |
paul@7 | 116 | |
paul@7 | 117 | def _add_row(self, offset, attributes, len_displaced): |
paul@7 | 118 | |
paul@7 | 119 | """ |
paul@7 | 120 | Add, at the given 'offset', the row of 'attributes' in the displaced |
paul@7 | 121 | list having length 'len_displaced'. |
paul@7 | 122 | """ |
paul@7 | 123 | |
paul@7 | 124 | # Extend the list if necessary. |
paul@7 | 125 | |
paul@7 | 126 | for i in xrange(0, offset + len(attributes) - len_displaced): |
paul@7 | 127 | self.displaced.append(None) |
paul@7 | 128 | |
paul@7 | 129 | # Record the offset and attribute details in the list. |
paul@7 | 130 | |
paul@7 | 131 | for i, attr in enumerate(attributes): |
paul@7 | 132 | if attr is not None: |
paul@7 | 133 | self.displaced[offset+i] = offset, attr |
paul@7 | 134 | |
paul@5 | 135 | class Table: |
paul@5 | 136 | |
paul@5 | 137 | "A lookup table." |
paul@5 | 138 | |
paul@63 | 139 | TableError = TableError |
paul@63 | 140 | |
paul@5 | 141 | def __init__(self): |
paul@5 | 142 | self.attributes = set() |
paul@5 | 143 | self.table = {} |
paul@22 | 144 | self.objnames = [] |
paul@5 | 145 | self.names = [] |
paul@7 | 146 | self.displaced_list = None |
paul@5 | 147 | |
paul@6 | 148 | def add(self, objname, attributes): |
paul@6 | 149 | |
paul@6 | 150 | "For the given 'objname' add the given 'attributes' to the table." |
paul@6 | 151 | |
paul@6 | 152 | self.table[objname] = attributes |
paul@5 | 153 | for name, origin in attributes.items(): |
paul@5 | 154 | self.attributes.add(name) |
paul@5 | 155 | |
paul@7 | 156 | if self.displaced_list is not None: |
paul@7 | 157 | self.displaced_list.add(objname, self.matrix_row(attributes)) |
paul@7 | 158 | |
paul@22 | 159 | def object_names(self): |
paul@22 | 160 | |
paul@22 | 161 | "Return the object names used in the table." |
paul@22 | 162 | |
paul@22 | 163 | self.objnames = self.objnames or list(self.table.keys()) |
paul@22 | 164 | return self.objnames |
paul@22 | 165 | |
paul@5 | 166 | def attribute_names(self): |
paul@6 | 167 | |
paul@6 | 168 | "Return the attribute names used in the table." |
paul@6 | 169 | |
paul@5 | 170 | self.names = self.names or list(self.attributes) |
paul@5 | 171 | return self.names |
paul@5 | 172 | |
paul@22 | 173 | def get_code(self, name): |
paul@22 | 174 | |
paul@22 | 175 | "Return the code of the given 'name'." |
paul@22 | 176 | |
paul@63 | 177 | try: |
paul@63 | 178 | return self.object_names().index(name) |
paul@63 | 179 | except ValueError: |
paul@63 | 180 | raise TableError, "Name %r is not registered as an object in the table." % name |
paul@22 | 181 | |
paul@21 | 182 | def get_index(self, name): |
paul@21 | 183 | |
paul@21 | 184 | "Return the index of the given 'name'." |
paul@21 | 185 | |
paul@63 | 186 | try: |
paul@63 | 187 | return self.attribute_names().index(name) |
paul@63 | 188 | except ValueError: |
paul@63 | 189 | raise TableError, "Name %r is not registered as an attribute in the table." % name |
paul@21 | 190 | |
paul@5 | 191 | def as_matrix(self): |
paul@6 | 192 | |
paul@6 | 193 | """ |
paul@6 | 194 | Return the table as a matrix mapping object names to lists of attributes |
paul@6 | 195 | arranged in the order of the recorded attribute names. |
paul@6 | 196 | """ |
paul@6 | 197 | |
paul@5 | 198 | matrix = {} |
paul@6 | 199 | for objname, attributes in self.table.items(): |
paul@7 | 200 | matrix[objname] = self.matrix_row(attributes) |
paul@5 | 201 | return matrix |
paul@5 | 202 | |
paul@7 | 203 | def matrix_row(self, attributes): |
paul@7 | 204 | |
paul@7 | 205 | "Return a matrix row for the given 'attributes'." |
paul@7 | 206 | |
paul@7 | 207 | row = [] |
paul@7 | 208 | for name in self.attribute_names(): |
paul@7 | 209 | row.append(attributes.get(name)) |
paul@7 | 210 | return row |
paul@7 | 211 | |
paul@111 | 212 | def all_attribute_positions(self, name): |
paul@111 | 213 | |
paul@111 | 214 | """ |
paul@111 | 215 | Return a list of positions for the attribute with the given 'name' from |
paul@111 | 216 | all known objects. |
paul@111 | 217 | """ |
paul@111 | 218 | |
paul@111 | 219 | all = set() |
paul@111 | 220 | for attributes in self.table.values(): |
paul@111 | 221 | if attributes.has_key(name): |
paul@111 | 222 | all.add(attributes[name]) |
paul@111 | 223 | return all |
paul@111 | 224 | |
paul@111 | 225 | def all_possible_objects(self, names): |
paul@111 | 226 | |
paul@111 | 227 | """ |
paul@111 | 228 | Return a list of object names supporting the given attribute 'names'. |
paul@111 | 229 | """ |
paul@111 | 230 | |
paul@111 | 231 | possible = [] |
paul@111 | 232 | for objname, attributes in self.table.items(): |
paul@111 | 233 | found = 1 |
paul@111 | 234 | for name in names: |
paul@111 | 235 | if not attributes.has_key(name): |
paul@111 | 236 | found = 0 |
paul@111 | 237 | break |
paul@111 | 238 | if found: |
paul@111 | 239 | possible.append(objname) |
paul@111 | 240 | return possible |
paul@111 | 241 | |
paul@6 | 242 | def as_list(self): |
paul@6 | 243 | |
paul@6 | 244 | """ |
paul@6 | 245 | Return a displaced list object encoding the table in a more compact form |
paul@7 | 246 | than that provided by the matrix representation. This list will be |
paul@7 | 247 | updated with new entries if added to this object using the 'add' method. |
paul@6 | 248 | """ |
paul@6 | 249 | |
paul@7 | 250 | if self.displaced_list is None: |
paul@7 | 251 | self.displaced_list = List(self.attribute_names()) |
paul@6 | 252 | |
paul@7 | 253 | # Visit each row of the matrix. |
paul@6 | 254 | |
paul@7 | 255 | for objname, attributes in self.as_matrix().items(): |
paul@7 | 256 | self.displaced_list.add(objname, attributes) |
paul@6 | 257 | |
paul@7 | 258 | return self.displaced_list |
paul@6 | 259 | |
paul@5 | 260 | # vim: tabstop=4 expandtab shiftwidth=4 |