paul@5 | 1 | #!/usr/bin/env python |
paul@5 | 2 | |
paul@5 | 3 | """ |
paul@5 | 4 | Preparation of run-time attribute lookup tables. |
paul@5 | 5 | """ |
paul@5 | 6 | |
paul@5 | 7 | try: |
paul@5 | 8 | set |
paul@5 | 9 | except NameError: |
paul@5 | 10 | from sets import Set as set |
paul@5 | 11 | |
paul@6 | 12 | class List: |
paul@6 | 13 | |
paul@6 | 14 | """ |
paul@6 | 15 | A displaced list containing attribute details and an index mapping names to |
paul@6 | 16 | offsets in the list. |
paul@6 | 17 | """ |
paul@6 | 18 | |
paul@6 | 19 | def __init__(self, displaced, offsets, names): |
paul@6 | 20 | self.displaced = displaced |
paul@6 | 21 | self.offsets = offsets |
paul@6 | 22 | self.names = names |
paul@6 | 23 | self.names_index = {} |
paul@6 | 24 | for i, name in enumerate(self.names): |
paul@6 | 25 | self.names_index[name] = i |
paul@6 | 26 | |
paul@6 | 27 | def access(self, objname, attrname): |
paul@6 | 28 | obj_offset = self.offsets.get(objname) |
paul@6 | 29 | attr_index = self.names_index.get(attrname) |
paul@6 | 30 | if obj_offset is None or attr_index is None: |
paul@6 | 31 | return None |
paul@6 | 32 | |
paul@6 | 33 | element = self.displaced[obj_offset + attr_index] |
paul@6 | 34 | if element is not None: |
paul@6 | 35 | offset, details = element |
paul@6 | 36 | if offset == obj_offset: |
paul@6 | 37 | return details |
paul@6 | 38 | |
paul@6 | 39 | return None |
paul@6 | 40 | |
paul@5 | 41 | class Table: |
paul@5 | 42 | |
paul@5 | 43 | "A lookup table." |
paul@5 | 44 | |
paul@5 | 45 | def __init__(self): |
paul@5 | 46 | self.attributes = set() |
paul@5 | 47 | self.table = {} |
paul@5 | 48 | self.names = [] |
paul@5 | 49 | |
paul@6 | 50 | def add(self, objname, attributes): |
paul@6 | 51 | |
paul@6 | 52 | "For the given 'objname' add the given 'attributes' to the table." |
paul@6 | 53 | |
paul@6 | 54 | self.table[objname] = attributes |
paul@5 | 55 | for name, origin in attributes.items(): |
paul@5 | 56 | self.attributes.add(name) |
paul@5 | 57 | |
paul@5 | 58 | def attribute_names(self): |
paul@6 | 59 | |
paul@6 | 60 | "Return the attribute names used in the table." |
paul@6 | 61 | |
paul@5 | 62 | self.names = self.names or list(self.attributes) |
paul@5 | 63 | return self.names |
paul@5 | 64 | |
paul@5 | 65 | def as_matrix(self): |
paul@6 | 66 | |
paul@6 | 67 | """ |
paul@6 | 68 | Return the table as a matrix mapping object names to lists of attributes |
paul@6 | 69 | arranged in the order of the recorded attribute names. |
paul@6 | 70 | """ |
paul@6 | 71 | |
paul@5 | 72 | matrix = {} |
paul@6 | 73 | for objname, attributes in self.table.items(): |
paul@5 | 74 | row = [] |
paul@5 | 75 | for name in self.attribute_names(): |
paul@5 | 76 | row.append(attributes.get(name)) |
paul@6 | 77 | matrix[objname] = row |
paul@5 | 78 | return matrix |
paul@5 | 79 | |
paul@6 | 80 | def as_list(self): |
paul@6 | 81 | |
paul@6 | 82 | """ |
paul@6 | 83 | Return a displaced list object encoding the table in a more compact form |
paul@6 | 84 | than that provided by the matrix representation. |
paul@6 | 85 | """ |
paul@6 | 86 | |
paul@6 | 87 | displaced = [] |
paul@6 | 88 | offsets = {} |
paul@6 | 89 | offsets_used = set() |
paul@6 | 90 | |
paul@6 | 91 | # Visit each row of the matrix. |
paul@6 | 92 | |
paul@6 | 93 | for objname, attributes in self.as_matrix().items(): |
paul@6 | 94 | len_displaced = len(displaced) |
paul@6 | 95 | len_attributes = len(attributes) |
paul@6 | 96 | |
paul@6 | 97 | # Try to fit the row into the list, starting from the beginning and |
paul@6 | 98 | # skipping places where an existing row has been fitted. |
paul@6 | 99 | |
paul@6 | 100 | for offset in xrange(0, len_displaced): |
paul@6 | 101 | if offset in offsets_used: |
paul@6 | 102 | continue |
paul@6 | 103 | if self._fit_row(offset, attributes, len_attributes, displaced, len_displaced): |
paul@6 | 104 | offsets_used.add(offset) |
paul@6 | 105 | offsets[objname] = offset |
paul@6 | 106 | self._add_row(offset, attributes, len_attributes, displaced, len_displaced) |
paul@6 | 107 | break |
paul@6 | 108 | |
paul@6 | 109 | # Where a row could not be fitted within the list, add it to the |
paul@6 | 110 | # end. |
paul@6 | 111 | |
paul@6 | 112 | else: |
paul@6 | 113 | offsets_used.add(len_displaced) |
paul@6 | 114 | offsets[objname] = len_displaced |
paul@6 | 115 | self._add_row(len_displaced, attributes, len_attributes, displaced, len_displaced) |
paul@6 | 116 | |
paul@6 | 117 | return List(displaced, offsets, self.names) |
paul@6 | 118 | |
paul@6 | 119 | def _fit_row(self, offset, attributes, len_attributes, displaced, len_displaced): |
paul@6 | 120 | |
paul@6 | 121 | """ |
paul@6 | 122 | Fit, at the given 'offset', the row of 'attributes' having length |
paul@6 | 123 | 'len_attributes' in the 'displaced' list having length 'len_displaced'. |
paul@6 | 124 | Return a true value if this succeeded. |
paul@6 | 125 | """ |
paul@6 | 126 | |
paul@6 | 127 | for i, attr in enumerate(attributes): |
paul@6 | 128 | if i + offset >= len_displaced: |
paul@6 | 129 | break |
paul@6 | 130 | element = displaced[i + offset] |
paul@6 | 131 | if attr is not None and element is not None: |
paul@6 | 132 | return 0 |
paul@6 | 133 | return 1 |
paul@6 | 134 | |
paul@6 | 135 | def _add_row(self, offset, attributes, len_attributes, displaced, len_displaced): |
paul@6 | 136 | |
paul@6 | 137 | """ |
paul@6 | 138 | Add, at the given 'offset', the row of 'attributes' having length |
paul@6 | 139 | 'len_attributes' in the 'displaced' list having length 'len_displaced'. |
paul@6 | 140 | """ |
paul@6 | 141 | |
paul@6 | 142 | # Extend the list if necessary. |
paul@6 | 143 | |
paul@6 | 144 | for i in xrange(0, offset + len_attributes - len_displaced): |
paul@6 | 145 | displaced.append(None) |
paul@6 | 146 | |
paul@6 | 147 | # Record the offset and attribute details in the list. |
paul@6 | 148 | |
paul@6 | 149 | for i, attr in enumerate(attributes): |
paul@6 | 150 | if attr is not None: |
paul@6 | 151 | displaced[offset+i] = offset, attr |
paul@6 | 152 | |
paul@5 | 153 | # vim: tabstop=4 expandtab shiftwidth=4 |