For the fall semester, we are supposed to think about how the arbitrary dimensional automaton class will be implemented as a polymorphic data structure. We want the class to be able to adapt its size to the dimensionality, so it grows linearly with the dimension but does not need to be recompiled for every different dimension.
Remember that the automaton is stored as a vector of states and the root label and will return the new state. We want to be able to index into this in constant time. The vector is size equal to the dimensionality. It seems like the vector class itself would be sufficient to make the class polymorphic, however we may want to use a hash structure to eliminate wasted space.
Posted by kernco at August 9, 2004 11:27 AMNot quite.
The automata (as tuples) can be implemented polymorphicly in this sense if we store then as a set of vectors. Since the component vectors can have any (constant) length the same class will work with automata of any dimension. (Viewed as tuples, vectors are polymorphic---have many forms---in the sense that they can represent tuples of any length.)
The issue is that, in order to access the automata in _constant_ (not linear) time, we have up until now structured them as multi-dimensional arrays, indexed by all but one of the components (for automata they were indexed by the states of the yield and the label of the root). In this realization, the number of dimensions of the array is proportional to the number of dimensions of the structures. Hence we can't just use a single class for automata of any dimension---the dimension actually shows up in the structure of the class declaration itself.
What we need is a way of accomplishing this direct access while still working with member variables that don't change type when the dimension changes.
Again, this is a place where we should be able to exploit the polymorphic nature of vectors. We do _not_ want to go back to using a hash.
Posted by: Jim at August 9, 2004 02:20 PM