1.1 --- a/micropython/table.py Sun Oct 21 02:25:25 2007 +0200
1.2 +++ b/micropython/table.py Sun Oct 21 20:05:42 2007 +0200
1.3 @@ -9,6 +9,35 @@
1.4 except NameError:
1.5 from sets import Set as set
1.6
1.7 +class List:
1.8 +
1.9 + """
1.10 + A displaced list containing attribute details and an index mapping names to
1.11 + offsets in the list.
1.12 + """
1.13 +
1.14 + def __init__(self, displaced, offsets, names):
1.15 + self.displaced = displaced
1.16 + self.offsets = offsets
1.17 + self.names = names
1.18 + self.names_index = {}
1.19 + for i, name in enumerate(self.names):
1.20 + self.names_index[name] = i
1.21 +
1.22 + def access(self, objname, attrname):
1.23 + obj_offset = self.offsets.get(objname)
1.24 + attr_index = self.names_index.get(attrname)
1.25 + if obj_offset is None or attr_index is None:
1.26 + return None
1.27 +
1.28 + element = self.displaced[obj_offset + attr_index]
1.29 + if element is not None:
1.30 + offset, details = element
1.31 + if offset == obj_offset:
1.32 + return details
1.33 +
1.34 + return None
1.35 +
1.36 class Table:
1.37
1.38 "A lookup table."
1.39 @@ -18,22 +47,107 @@
1.40 self.table = {}
1.41 self.names = []
1.42
1.43 - def add(self, class_name, attributes):
1.44 - self.table[class_name] = attributes
1.45 + def add(self, objname, attributes):
1.46 +
1.47 + "For the given 'objname' add the given 'attributes' to the table."
1.48 +
1.49 + self.table[objname] = attributes
1.50 for name, origin in attributes.items():
1.51 self.attributes.add(name)
1.52
1.53 def attribute_names(self):
1.54 +
1.55 + "Return the attribute names used in the table."
1.56 +
1.57 self.names = self.names or list(self.attributes)
1.58 return self.names
1.59
1.60 def as_matrix(self):
1.61 +
1.62 + """
1.63 + Return the table as a matrix mapping object names to lists of attributes
1.64 + arranged in the order of the recorded attribute names.
1.65 + """
1.66 +
1.67 matrix = {}
1.68 - for class_name, attributes in self.table.items():
1.69 + for objname, attributes in self.table.items():
1.70 row = []
1.71 for name in self.attribute_names():
1.72 row.append(attributes.get(name))
1.73 - matrix[class_name] = row
1.74 + matrix[objname] = row
1.75 return matrix
1.76
1.77 + def as_list(self):
1.78 +
1.79 + """
1.80 + Return a displaced list object encoding the table in a more compact form
1.81 + than that provided by the matrix representation.
1.82 + """
1.83 +
1.84 + displaced = []
1.85 + offsets = {}
1.86 + offsets_used = set()
1.87 +
1.88 + # Visit each row of the matrix.
1.89 +
1.90 + for objname, attributes in self.as_matrix().items():
1.91 + len_displaced = len(displaced)
1.92 + len_attributes = len(attributes)
1.93 +
1.94 + # Try to fit the row into the list, starting from the beginning and
1.95 + # skipping places where an existing row has been fitted.
1.96 +
1.97 + for offset in xrange(0, len_displaced):
1.98 + if offset in offsets_used:
1.99 + continue
1.100 + if self._fit_row(offset, attributes, len_attributes, displaced, len_displaced):
1.101 + offsets_used.add(offset)
1.102 + offsets[objname] = offset
1.103 + self._add_row(offset, attributes, len_attributes, displaced, len_displaced)
1.104 + break
1.105 +
1.106 + # Where a row could not be fitted within the list, add it to the
1.107 + # end.
1.108 +
1.109 + else:
1.110 + offsets_used.add(len_displaced)
1.111 + offsets[objname] = len_displaced
1.112 + self._add_row(len_displaced, attributes, len_attributes, displaced, len_displaced)
1.113 +
1.114 + return List(displaced, offsets, self.names)
1.115 +
1.116 + def _fit_row(self, offset, attributes, len_attributes, displaced, len_displaced):
1.117 +
1.118 + """
1.119 + Fit, at the given 'offset', the row of 'attributes' having length
1.120 + 'len_attributes' in the 'displaced' list having length 'len_displaced'.
1.121 + Return a true value if this succeeded.
1.122 + """
1.123 +
1.124 + for i, attr in enumerate(attributes):
1.125 + if i + offset >= len_displaced:
1.126 + break
1.127 + element = displaced[i + offset]
1.128 + if attr is not None and element is not None:
1.129 + return 0
1.130 + return 1
1.131 +
1.132 + def _add_row(self, offset, attributes, len_attributes, displaced, len_displaced):
1.133 +
1.134 + """
1.135 + Add, at the given 'offset', the row of 'attributes' having length
1.136 + 'len_attributes' in the 'displaced' list having length 'len_displaced'.
1.137 + """
1.138 +
1.139 + # Extend the list if necessary.
1.140 +
1.141 + for i in xrange(0, offset + len_attributes - len_displaced):
1.142 + displaced.append(None)
1.143 +
1.144 + # Record the offset and attribute details in the list.
1.145 +
1.146 + for i, attr in enumerate(attributes):
1.147 + if attr is not None:
1.148 + displaced[offset+i] = offset, attr
1.149 +
1.150 # vim: tabstop=4 expandtab shiftwidth=4