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