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.names = [] 142 self.displaced_list = None 143 144 def add(self, objname, attributes): 145 146 "For the given 'objname' add the given 'attributes' to the table." 147 148 self.table[objname] = attributes 149 for name, origin in attributes.items(): 150 self.attributes.add(name) 151 152 if self.displaced_list is not None: 153 self.displaced_list.add(objname, self.matrix_row(attributes)) 154 155 def attribute_names(self): 156 157 "Return the attribute names used in the table." 158 159 self.names = self.names or list(self.attributes) 160 return self.names 161 162 def get_index(self, name): 163 164 "Return the index of the given 'name'." 165 166 return self.attribute_names().index(name) 167 168 def as_matrix(self): 169 170 """ 171 Return the table as a matrix mapping object names to lists of attributes 172 arranged in the order of the recorded attribute names. 173 """ 174 175 matrix = {} 176 for objname, attributes in self.table.items(): 177 matrix[objname] = self.matrix_row(attributes) 178 return matrix 179 180 def matrix_row(self, attributes): 181 182 "Return a matrix row for the given 'attributes'." 183 184 row = [] 185 for name in self.attribute_names(): 186 row.append(attributes.get(name)) 187 return row 188 189 def as_list(self): 190 191 """ 192 Return a displaced list object encoding the table in a more compact form 193 than that provided by the matrix representation. This list will be 194 updated with new entries if added to this object using the 'add' method. 195 """ 196 197 if self.displaced_list is None: 198 self.displaced_list = List(self.attribute_names()) 199 200 # Visit each row of the matrix. 201 202 for objname, attributes in self.as_matrix().items(): 203 self.displaced_list.add(objname, attributes) 204 205 return self.displaced_list 206 207 # vim: tabstop=4 expandtab shiftwidth=4