1 #!/usr/bin/env python 2 3 """ 4 Preparation of run-time attribute lookup tables. 5 6 Copyright (C) 2007 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 try: 23 set 24 except NameError: 25 from sets import Set as set 26 27 class List: 28 29 """ 30 A displaced list containing attribute details and an index mapping names to 31 offsets in the list. 32 """ 33 34 def __init__(self, names): 35 self.names = names 36 self.displaced = [] 37 self.offsets = {} 38 self.offsets_used = set() 39 40 self.names_index = {} 41 for i, name in enumerate(self.names): 42 self.names_index[name] = i 43 44 def __len__(self): 45 return len(self.displaced) 46 47 # Simulation methods. 48 49 def access(self, objname, attrname): 50 obj_offset = self.offsets.get(objname) 51 attr_index = self.names_index.get(attrname) 52 if obj_offset is None or attr_index is None: 53 return None 54 55 element = self.displaced[obj_offset + attr_index] 56 if element is not None: 57 offset, details = element 58 if offset == obj_offset: 59 return details 60 61 return None 62 63 def dir(self, objname): 64 attributes = {} 65 for name in self.names: 66 attr = self.access(objname, name) 67 if attr is not None: 68 attributes[name] = attr 69 return attributes 70 71 # Update methods. 72 73 def add(self, objname, attributes): 74 75 "Add an entry for 'objname' with the given 'attributes'." 76 77 len_displaced = len(self.displaced) 78 len_attributes = len(attributes) 79 80 # Try to fit the row into the list, starting from the beginning and 81 # skipping places where an existing row has been fitted. 82 83 for offset in xrange(0, len_displaced): 84 if offset in self.offsets_used: 85 continue 86 if self._fit_row(offset, attributes, len_displaced): 87 self.offsets_used.add(offset) 88 self.offsets[objname] = offset 89 self._add_row(offset, attributes, len_displaced) 90 break 91 92 # Where a row could not be fitted within the list, add it to the 93 # end. 94 95 else: 96 self.offsets_used.add(len_displaced) 97 self.offsets[objname] = len_displaced 98 self._add_row(len_displaced, attributes, len_displaced) 99 100 def _fit_row(self, offset, attributes, len_displaced): 101 102 """ 103 Fit, at the given 'offset', the row of 'attributes' in the displaced 104 list having length 'len_displaced'. 105 Return a true value if this succeeded. 106 """ 107 108 for i, attr in enumerate(attributes): 109 if i + offset >= len_displaced: 110 break 111 element = self.displaced[i + offset] 112 if attr is not None and element is not None: 113 return 0 114 return 1 115 116 def _add_row(self, offset, attributes, len_displaced): 117 118 """ 119 Add, at the given 'offset', the row of 'attributes' in the displaced 120 list having length 'len_displaced'. 121 """ 122 123 # Extend the list if necessary. 124 125 for i in xrange(0, offset + len(attributes) - len_displaced): 126 self.displaced.append(None) 127 128 # Record the offset and attribute details in the list. 129 130 for i, attr in enumerate(attributes): 131 if attr is not None: 132 self.displaced[offset+i] = offset, attr 133 134 class Table: 135 136 "A lookup table." 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 return self.object_names().index(name) 175 176 def get_index(self, name): 177 178 "Return the index of the given 'name'." 179 180 return self.attribute_names().index(name) 181 182 def as_matrix(self): 183 184 """ 185 Return the table as a matrix mapping object names to lists of attributes 186 arranged in the order of the recorded attribute names. 187 """ 188 189 matrix = {} 190 for objname, attributes in self.table.items(): 191 matrix[objname] = self.matrix_row(attributes) 192 return matrix 193 194 def matrix_row(self, attributes): 195 196 "Return a matrix row for the given 'attributes'." 197 198 row = [] 199 for name in self.attribute_names(): 200 row.append(attributes.get(name)) 201 return row 202 203 def as_list(self): 204 205 """ 206 Return a displaced list object encoding the table in a more compact form 207 than that provided by the matrix representation. This list will be 208 updated with new entries if added to this object using the 'add' method. 209 """ 210 211 if self.displaced_list is None: 212 self.displaced_list = List(self.attribute_names()) 213 214 # Visit each row of the matrix. 215 216 for objname, attributes in self.as_matrix().items(): 217 self.displaced_list.add(objname, attributes) 218 219 return self.displaced_list 220 221 # vim: tabstop=4 expandtab shiftwidth=4