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