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