Chap.6: AVAILABLE CLASSESNote that for each class, the directories PTL/TTEST and PTL/MTEST provide a program which demonstrates the use of the class, and verifies that they work correctly. Tests in TTEST have explicitely coded multiple inheritance, tests in MTEST use the Template Manager. All iterators are smart iterators that permit one to remove() and delete() objects while traversing the data. You can easily add your own classes to the library - see Chap.9. When you receive the library, it will include the following classes: 6.1 COLLECTION or LINKED LIST (file collecti.h) 6.2 AGGREGATE, HIERARCHY, or ONE-TO-MANY (file aggregat.h) 6.3 ARRAY CONTAINER or BASIC DYNAMIC ARRAY (file arraycon.h) 6.4 ARRAY attached to an application class (file array.h) 6.5 POINTER ARRAY (file ptrarray.h) 6.6 pattern COMPOSITE (file composit.h) 6.7 pattern FLYWEIGHT (file flyweigh.h) 6.8 FINITE STATE MACHINE (file fsm.h) (6.1) COLLECTION or LINKED LIST (file collecti.h)In this data organization, each Parent keeps a doubly linked, intrusive, circular list of Children. Depending how you interpret this pattern, it can be used as a linked list, collection, sorted collection, or a set. It is one of the basic building blocks of numerous data structures and patterns. Class diagram:
Implementation:
In the the following description, we will often use P for the Parent class (for example Department), C for the child class (for example Employee), and i for the integer index, which is 0 most of the time. CONDITIONS FOR USING THIS PATTERN:
When you use the PatternManager, this happens automatically. AVAILABLE METHODS: template<class P,class C, int i=0> class Collection {
...
public:
cType *head(const pType *p) const; // head of the list
cType *tail(const pType *p) const; // tail of the list
cType *next(const cType *c) const; // next on the list
cType *prev(const cType *c) const; // previous on the list
void setTail(pType *p,cType *c) const; // set c to be the tail on p
void setHead(pType *p,cType *c) const; // set c to be the head on p
void addTail(pType *p,cType *c) const; // add c as new tail under p
void addHead(pType *p,cType *c) const; // add c as new head under p
void insert(pType *p,cType *c,cType *x) const; // insert x before c
void append(pType *p,cType *c,cType *x) const; // append x after c
void remove(pType *p,cType *c) const; // remove c from under p
void merge(cType *s,cType *t,pType *ps,pType *pt) const; // see below
void merge(pType *ps,pType *pt) const; // merge pt after ps
void split(cType *s,cType *t,pType *ps,pType *pt) const; // see below
void sort(pType *p,cmpType cmp) const; // sort using C::cmp()
void addSorted(pType *p,cType *c,cmpType cmp) const; //add,keep sorted
int count(const pType* p) const; // count of items
};
Situations which violate data integrity are detected. Examples: remove(p,c) or setHead(p,c) when c is not under p. For more details on error handling, see Chap.10. The function split(s,t,ps,pt) splits one collection into two, while the function merge(s,t,ps,pt) merges two collections into one. In both situations, two children (s and t) and their parents (ps and pt) are involved: Merging two collections:
Splitting a collection:
In the case of merging, s and t must be in different collections. The function disconnects s and t from their next neighbors v and u, and connects t to v, and s to u - see the figure. The new collection is under ps, and pt is empty. In the case of splitting, both s and t must be originally under ps, and pt must be an empty Parent. The function again disconnects v and t from their next neighbors v and u, and connects t to v and s to u. The result is two collections: one which contains s and u and remains under ps, and one which contains v and t and is assigned to pt. In either case, if s=t, no action is taken. It may interest you that, internally, a single algorithm provides both services. To make the interface easy to use, this general function is hidden behind merge() and split(). There is also a second function for merging two collections, void merge(pType *ps,pType *pt); which is the most frequently occuring situation. ORDER OF THE ITEMS IN THE COLLECTION: When you add items using addTail(), the iterator will return them in the same order (FIFO queue). When you add items using addHead(), the items will be stored in the reverse order (LIFO queue). Function sort() sorts the collection by a fast merging algorithm, which has a performance comparable to qsort() for arrays. The sort is controlled by the compare function int C::cmp(C *c1, C *c2), which is similar to the compare function required for qsort(). The result of cmp(c1,c2) must be < 0 when c1>c2, must be > 0 when c1>c2, and must be 0 when they are equal. We recommend that if you need sorting, you should make this function a static member function of class C. Function addSorted() adds an item to the collection so that its order is maintained. Since Collection is based on a linked list, this operation is relatively inefficient (i.e., it must traverse the list). Rather then using repeatedly addSorted(), it is much faster to use addTail() or addHead() and then sort the collection by calling sort(). Function count() returns the number of Children under Parent p. It is not efficient to store this value on each parent; therefore this value is calculated every time you ask for it, and it requires a full traversal of the list. ITERATOR: template<class P,class C, int i=0> class CollectionIterator {
...
public:
CollectionIterator(); // creates an iterator
C* begin(const pType *p); // starts the forward iteration (ITERATE)
C* end(const pType *p); // starts the reverse iteration (RETRACE)
C* const operator++(); // next object in the forward direction
C* const operator--(); // next object in the reverse direction
};
For examples of using this data structure, see ttest/collecti.cpp and mtest/collecti.cpp. The correct results are in ptl/out/collecti.out. (6.2) AGGREGATE or ONE_TO_MANY (file aggregat.h)This data organization is sometimes called a ONE_TO_MANY relation. For each Parent, it keeps a doubly linked, intrusive, circular list of Children. This pattern is very similar to the COLLECTION, except that each Child also keeps a pointer to its Parent. Internally, class Aggregate<> is derived from class Collection<>. The AGGREGATE represents a hierarchy of objects, and it is one of the most useful and most frequently used data structures. Examples: Department and Employees, CircuitBlock and its Terminals, Account and its Transactions. Class diagram:
Implementation:
In the the following description, we will often use P for the Parent class (for example, Department), C for the child class (for example, Employee), and i for the integer index, which is 0 most of the time. CONDITIONS FOR USING THIS PATTERN:
When you use the PatternManager, this happens automatically. AVAILABLE METHODS: Note that even though Aggregate is quite similar to Collection, the syntax of some functions is different. The reason is that, in Aggregate, children always know their parents, therefore the parents do not have to be given in operations like insert() or remove(). template<class P,class C, int i=0> class Aggregate {
...
public:
// methods which are the same as for Collection
cType *head(const pType *p) const; // head of the list
cType *tail(const pType *p) const; // tail of the list
cType *next(const cType *c) const; // next on the list
cType *prev(const cType *c) const; // previous on the list
void addTail(pType *p,cType *c) const; // add c as the new tail under p
void addHead(pType *p,cType *c) const; // add c as the new head under p
void setTail(cType* c) const; // set c to be the tail on p
void setHead(cType* c) const; // set c to be the head on p
void merge(pType *ps,pType *pt) const; // merge pt after ps
void addSorted(pType *p,cType *c,cmpType cmp) const; // add, keep sorted
void sort(pType *p,cmpType cmp) const; // sort collection using C::cmp()
int count(const pType* p) const; // count of items
// methods which are different from Collection
pType *parent(cType *c) const; // the parent of c
void insert(cType *c,cType *x) const; // insert x before c,under parent of c
void append(cType *c,cType *x) const; // append x after c, under parent of c
void remove(cType *c) const; // removes c from its parent
void merge(cType *s,cType *t) const; // - see the text
void split(cType *s,cType *t,pType *pt) const; // - see the text
// splits aggregate into two, pt must be a new, empty parent
};
For the description of the merge() and split() operations, and ordering of the items in the aggregate, see the equivalent functions in Collection, in Section 6.1. For Aggregate, the parents do not have to be given in some situations. The iterator is exactly the same as for the Collection, and is also internally implemented like it: template<class P,class C, int i=0> class AggregateIterator :
public CollectionIterator{};
The interface therefore appears to be like the following: template<class P,class C, int i=0> class AggregateIterator {
...
public:
// all same as for Collection
};
For examples of using this data structure, see ttest/aggregat.cpp and mtest/aggregat.cpp. The correct results are in ptl/out/aggregat.out. (6.3) ARRAY CONTAINER or BASIC DYNAMIC ARRAY (arraycon.h)This is a dynamic array in its classical (standard) template form. It is not implemented as a pattern: the data and all functions that control it are in the same class. It has been included for completeness, and also because we will need it for some more sophisticated array implementations. This array does many things; in contrast to STL and other libraries it is centered on implementation, and it lets YOU do what you want. You can control its order, sort it, use it as a collection or array of pointers or as a stack, and many other things. This class keeps an array of objects, which you can access with the operator[] as if it was a real array. The array starts with a certain size (either default or specified by the constructor), and as you access it, it automatically increases its size as needed. You can also control the size directly with certain commands. Normally, when a bigger size is needed, the array multiplies the current size by 2 until a sufficient size is reached. If you know the required size of the array, you can avoid excessive allocation by specifying it in the constructor, by calling grow(maxIndex), or accessing it like: x=myArray[maxIndex]; The array can be uninitialized, initialized to 0, or blank. This is applied not only to the original, starting array, but also to its unused portion as the array grows. You can specify the initialization method in one of the constructors. Class diagram:
Implementation:
where size is the currently allocated size of the array, and used is the number of items in the used part of the array. For example, if you accessed indexes 2,3, and 9, you will have used=10, based on the highest used index=9. Even though you never accessed items 0,1, etc., your current range is 0-9, therefore the array has 10 items. In the its current form, we did not provide iterators, because they seem unnecessary. You can traverse the used part of the array like this: for(i=0; i<myArray.used(); i++){ ...=myArray[i];}
or you can traverse any part without worrying about the size and allocation like this: for(i=0; i<25000; i++){ myArray[i]=...;}
Sorting is based on qsort, and expects the same style of compare function. We recommend that you code this function as a static function on the class of the object that is stored in the array. See function B::cmp() in the test program ttest/arraycon.cpp. When working with an array of pointers, declare it like this: class A;
Array<A*> myArray;
CONDITIONS FOR USING THIS PATTERN: This pattern does not involve inheritance. There is no need to use the Pattern() statement when you run with the Template Manager. AVAILABLE METHODS: template<class T> class ArrayContainer {
typedef int (*cmpType)(const void *, const void *);
...
public:
ArrayContainer(); // default starts with size=8, no initialization
ArrayContainer(unsigned int const startSize,unsigned int const ini);
// user-specified starting size and initialization
// ini=0 no initialization,ini=1 by 0,ini=2 by blank
virtual ~ArrayContainer();
unsigned int size(void) const; // returns the currently allocated size
unsigned int used(void) const; // returns the currently used range
T& operator[](const unsigned int k); // normal access to the array
void remove(const unsigned int k); // remove, shrink remaining part
void fastRemove(const unsigned int k); // without maintaining order
void insert(const unsigned int k,T *t); // insert, expand remainder
void push(T* e); // add e to the end as if a stack, increment 'used'
T* pop(void); // return the last item, decrement 'used'
int reduce(); // reduce the array to its used size
int cut(const unsigned int k); // cut the size up to index k
int grow(const unsigned int k); // grow to accomodate index k
void sort(cmpType cmp); // sort the array, using qsort
};
(6.4) ARRAY attached to an application class (file array.h)The dynamic array is one of the basic data organizations, like the linked list. Many data structures can be built with dynamic arrays. For example, most container class libraries such as STL, RogueWave tools.h++, and Microsoft MCF extensively use dynamic arrays. Class diagram:
Implementation:
Class Array<H,T,i> is essentially ArrayContainer<T> which was described in the previous section, but with a style of interface that fits intrusive data structures and patterns such as Collection<> or Aggregate<>. The array is attached to application class H, contains an array of Ts, and is managed by the manager class Array<H,T,i>. For the internal organization, look at class ArrayContainer<T>. The functions that control this data organization are similar to those available for ArrayContainer<>, except that the holder object must always be given. For example, to traverse the used part of the array, you do this: class Holder;
class Element;
Holder *hp;
Element *e;
Array<Holder,Element> myArray; // default i=0 not needed
...
for(i=0; i<myArray.used(h); i++) {
e = myArray.array(h)[i];
...
myArray.array(h)[i] = e;
}
Function initial() sets up the default starting size and initialization for all arrays within the class Array<H,T,i>. The array grows in multiples of 2 whenever operator[] or push() access an index which overflows the existing size. However, even when a big jump in size occurs, the new size is determined first and then only one allocation is performed. You can increase/decrease the size to a specific value using the functions grow() or cut(). CONDITIONS FOR USING THIS PATTERN:
For arrays of pointers, use Array<H,T*,i>, or even better, class PtrArray<H,T,i>. ITERATORS Currently none; use the for() loop as explained above. AVAILABLE METHODS: template<class H,class T,int i=0> class Array {
typedef int (*cmpType)(const void *, const void *);
....
public:
void initial(unsigned int const startSz,unsigned int const ini);
// startSz=starting size for all arrays,
// initialization: 0=no initialization,1=by NULL,2=by blank
unsigned int size(H* h) const; // returns currently allocated size
unsigned int used(H* h) const; // returns currently used size
hType& array(H *h); // main access to the array, to be used with []
void remove(H *h,const unsigned int k);
// remove item in position k and shrink remaining part
void fastRemove(H *h,const unsigned int k);
// remove item in position k without maintaining order
void insert(H *h,const unsigned int k,T *t);
// insert t into position k and expand remaining part
void push(H *h,T* e); // push e to the end, increment 'used'
T* pop(H *h); // pop the last item, decrement 'used'
int reduce(H *h); // reduce to the currently used size
int cut(H *h,const unsigned int k);
// cut the size to accomodate index k
int grow(H *h,const unsigned int k); // grow to accomodate index k
void sort(H *h,cmpType cmp); // sort using qsort and cmp()
};
Comments:
(6.5) POINTER ARRAY (file ptrarray.h)The previous chapter described DYNAMIC ARRAY, which also can store simple pointers (as an array of pointers). However, handling a pointer array through this generic class is not as easy as one would wish in the case of a simple item like a pointer. There are certain situations in which the number of '*' preceding some variables and parameters becomes confusing, or in which you simply want to pass a pointer in/out without going through a complicated interface. For this purpose, the PTL provides specially tuned class called PtrArray<>. PtrArray is derived from Array<>, and reuses many of its functions. The main differences are:
Internally, the PtrArray class is similar to Array, but note the difference in the parametrization - we have PtrArray<T>, but each element of the array is T* Class diagram:
Implementation:
CONDITIONS FOR USING THIS PATTERN: None. When using an index other than unsigned int, for example int or unsigned char, the compiler provides conversion automatically. ALGORITHM AND TRAVERSING THE ARRAY Size management is the same as for Array. The array is always initialized to NULL pointers. Traversing is the same as for Array. Calling set(i,NULL) for a position where the array is not NULL will decrement the count. Function sort() is the same as for Array; you may want to sort the array either by the value of the pointers or by some keys which are members of the objects to which the pointers lead. AVAILABLE METHODS: template<class E> class PtrArray : public Array<E*> {
typedef int (*cmpType)(const void *,const void *); // for sort
....
public:
// Methods which are new or different
PtrArray():Array<E*>(); // same size default as Array
PtrArray(const unsigned int s):Array<E*>(s); // given initial size
virtual ~PtrArray(); // because ~Array() is virtual
unsigned int count(); // count of pointers != NULL
E*& operator[](const unsigned int i); // use as you would intuitively
E *get(const unsigned int i); // returns pointer with index i
void set(const unsigned int i,E *e); // loads pointer e into index i
void push(E *e); // pushes pointer e onto stack
E *pop(void); // pops pointer from the stack
void clean(void); // removes all objects to which the pointers lead
E* remove(const unsigned int i); // removes pointer at i, returns it
void insert(const unsigned int i,E *e); // insert e to i, expand array
void initialize(unsigned int const code); // automatic,control disabled
// Same interface as for Array
int reduce(); // reduces the size to fit the useful part of the array
int cut(const unsigned int i); // cuts the size to accomodate index i
int grow(const unsigned int i); // grows the size to accomodate index i
void sort(cmpType cmp); // sorts the used part using qsort()
unsigned int size(void) const; // currently allocated size
unsigned int used(void) const; // highest index currently used}
};
For examples using this PtrArray, see ttest/ptrarray.cpp and mtest/ptrarray.cpp. The correct results are in ptl/out/ptrarray.out. (6.6) Pattern COMPOSITE (file composit.h)COMPOSITE is one of the most powerful design patterns. It implements an elegant and efficient hierarchy of objects, applicable to uncountable practical situations. For example, assume that you are designing a graphical editor which handles Pictures, Text, and Lines. Text and Line are basic units, but Pictures are composed of Text, Lines, and other Pictures. For example, a rectangle becomes a Picture which includes 4 lines, and a rectangle with text in it is a Picture which includes the Picture representing the rectangle, plus the text. To apply Composite to this example, we introduce a base class common to all these objects, and call it Graphic, and we assign a collection of Graphic objects to each Picture:
Only after you attempt to draw a pointer diagram of this arrangement, will you appreciate its beauty and simplicity. The essence of this pattern is
and its implementation depends only on how we implement the collection. Our template Composite<class Parent, class Child, int i> is based on the intrusive collection, Collection<class Parent, class Child, int i>, which is described in Section 6.1. If you prefer a container-based collection, you can design your own Composite class with PtrArray<> (see Section 6.5) For more details on this pattern, see reference [4], Chap.4 - p.163. CONDITIONS FOR USING THIS PATTERN:
virtual int P::isComposite(Composite<P,C,i> *c){c=c; return(1);}
virtual int C::isComposite(Composite<P,C,i> *c){c=c; return(0);}
When you use the Pattern Manager, all this happens automatically. AVAILABLE METHODS: COMPOSITE is derived from COLLECTION, and has all its methods. ITERATE and RETRACE traverse one level of the hierarchy. There are additional functions which traverse the entire hierarchy: depthFirst() traverses depth first and applies
function f() to every node; The function applied by these functions, int Child::f(const void *v), permits you to pass one or more parameters (possibly as a structure). The function should normally return 0; return=1 exits the traversal loop. template<class P,class C, int i=0> class Composite
: public Collection<P,C,i> {
...
public:
// methods inherited from Collection<>
cType *head(const pType *p) const; // head of the list
cType *tail(const pType *p) const; // tail of the list
cType *next(const cType *c) const; // next on the list
cType *prev(const cType *c) const; // previous on the list
void setTail(pType *p,cType *c) const; // set c to be the tail on p
void setHead(pType *p,cType *c) const; // set c to be the head on p
void addTail(pType *p,cType *c) const; // add c as new tail under p
void addHead(pType *p,cType *c) const; // add c as new head under p
void insert(pType *p,cType *c,cType *x) const; // insert x before c
void append(pType *p,cType *c,cType *x) const; // append x after c
void remove(pType *p,cType *c) const; // remove c from under p
void merge(cType *s,cType *t,pType *ps,pType *pt) const; // see below
void merge(pType *ps,pType *pt) const; // merge pt after ps
void split(cType *s,cType *t,pType *ps,pType *pt) const; // see below
void sort(pType *p,cmpType cmp)const; // sort one level using C::cmp()
void addSorted(pType *p,cType *c,cmpType cmp) const; // add, keep sorted
int count(const pType* p) const; // count children for this parent
typedef C* (*TravFun)(C*,void *);
// additional methods that traverse entire hierarchy
void dissolve(cType *c);
C *depthFirst(cType *c,TravFun f,void *v);
};
For examples using this data structure, see ttest/composit.cpp and mtest/composit.cpp. The correct results are in ptl/out/composit.out. (6.7) Pattern FLYWEIGHT (file flyweigh.h)Despite our regard for the authors of [4], we think that by using a different terminology, the description of this pattern in [4] p.195, can be improved. We will discuss the example of this pattern presented in [4], but will introduce more meaningful names for the classes participating in the pattern. If you are designing a text editor, the text will appear on the screen as rows of characters, and it seems natural to store the data internally in the same manner. However, you must be careful to minimize the storage: even relatively small documents will include thousands of characters. The flyweight pattern achieves this objective with the following arrangement:
Each Page has a collection (or a list) of Rows, and each Row has a collection of LightChar objects. LightChar is designed to take the minimum possible space, and stores the main bulk of text. Each LightChar refers to a HeavyChar object, which is the master template of the character. HeavyChar knows how to draw the character, its width and height, and other details. Most likely, you would represent each row as an array of bytes, where the integer stored in each byte is used as an index into the array of HeavyChar objects, one HeavyChar array for each available font. In this pattern, some of the important data are not stored but are calculated on the fly. For example, to draw a character, function HeavyChar::draw() needs to know the lower-left corner of the character, which is determined by its position in the row. The Row can calculate this information and pass it in some form (we will call this the "calculated state") to HeavyChar. On the other hand, when calculating the position, the Row needs to know the width of all the characters which are stored in HeavyChar (we will call this the "stored state"). Pattern flyweight is this combination of light/heavy objects with the action of passing the states back and forth.
For example, in the test problem ttest/flyweigh.cpp or mtest/flyweigh.cpp, the calculated state also includes the font. The start of the text set in italics is recorded by character '{', and the change to the normal text by '}'. The challenge of designing a library class for flyweight is the need to cover several different situations:
For this reason, our Flyweight has the following organization, which does not include an equivalent of class LightChar. It is simply assumed to be an integer of general size, and the size of integers it keeps depends on class Keeper (equivalent of Row), and whether they form an array, tree, or some other data structure.
Note that HeavyWeight::getFlyweightState() returns the StoredState, while Keeper::getFlyweightState() returns the CalculatedState. Keeper corresponds to Row from the previous example, and HeavyWeight corresponds to HeavyChar. StoredState and CalculatedState have the same meaning as before. Flyweight is the class representing the pattern itself, and it also keeps the array of HeavyWeights. As explained above, there is no equivalent of LightChar, which is assumed to be a general integer. Function fun(k,fi,kp) is an essential part of this pattern, because classes Keeper and HeavyWeight may communicate only through class Flyweight. For more detailed description, see below - AVAILABLE METHODS. CONDITIONS FOR USING THIS PATTERN:
It is recommended that Keeper be a friend of CalculatedState, and HeavyWeight be a friend of StoredState. When you use the Template Manager,all this happens automatically, including Keeper being a friend of CalculatedState, and HeavyWeight being a friend of StoredState. Abbreviations: #define kType FlyweightKeeper<K,H,C,S,i> #define hType FlyweightHeavy<K,H,C,S,i> #define fType Flyweight<K,H,C,S,i> #define aType ArrayContainer<H*> template<class K,class H,class C, class S,int i=0> class Flyweight
: public aType {
public:
Flyweight(); // default starting size (=10) of the HeavyWeight array
Flyweight(const unsigned int sz); // user-specified starting size
virtual ~Flyweight(){};
void add(H *const ip,const unsigned int k);
// record ip as reference No.k, but only if the position is free
void force(H *const ip,const unsigned int k){remove(k); add(ip,k);}
// record ip as reference No.k; when k used, remove the old ref.
void remove(const int k){(void)(((aType*)this)->remove(k));}
// remove the reference at k
void remove(const H *ip);
// search for this entry and remove it. Involves a linear search
void cleanHeavy(void); // destroy all HeavyWeight objects
S *getState(const unsigned int k); // get StoredState at reference k
int fun(const unsigned int k, int (H::*f)(C*), K *ep) const;
// key function in this pattern - see below
};
Function fun(k,fi,kp) is pivotal for the cooperation between Keeper and HeavyWeight, which can communicate only through class Flyweight. fun() finds the HeavyWeight under reference k, and applies to it the method HeavyWeight::f(). The pointer to the keeper is provided as an additional reference which fun() can use to obtain the current CalculatedState. fun() passes the pointer returned by f(). For examples using this data structure, see ttest/flyweigh.cpp and mtest/flyweigh.cpp. The correct results are in ptl/out/flyweigh.out. (6.8) FINITE STATE MACHINE- FSM (file fsm.h)A generic Finite State Machine was not included in the Pattern Book [4], and is not in any commonly used class library. And yet, it is a very important pattern, and many applications depend on its efficient implementation. Our class FSM allows you to create and dynamically modify your own finite state machines that are fast and efficient. The FSM class assumes that you have a special class for each of your states, with a common base state class. Similarly, you must have a special class for each of the input stimulae, with one common input base class. In many applications, these two classes will really represent an integer or only a byte, but having them as general classes allows you to implement complex and yet highly efficient state machines. State table:
Function table:
The FSM class is implementated as template FSM<F,S,I,T,D> with the following parameters: F = your finite state machine class
S = base class for all your state classes
I = base class for all your input classes
T = type for the internal table index, must be unsigned and able to
accomodate MAX(numInputs,numStates,numFuncts) entries.
D = integer id when using multiple parallel organizations (as for other
patterns).
As pointed out by J. Coplien (see [5]) this representation is rather unusual because your FSM class will inherit from a template which uses this class as one of the parameters, for example: class myFSM : public MSF<myFSM, myState, myInput, int, 0> { ... };
Your FSM class (myFSM) can have an arbitrary number of transition functions that look like this: S* myFSM::f(S*,void**). One function can be assigned to several transitions. The assignment of both functions and of target states is performend dynamically, while executing your program. Even though this concept is very general, you will find it simple to use once you go through the first example. Here is a state machine which describes the life of a typical university student. One night they go partying; the next day they are tired and study in the evening; they party the next day; and so on. The night before a test they do not go anywhere and try to learn everything at the last minute. When going to a party, they need some beer, and the night before the test, they drink a lot of coffee. If we describe this behavior as a finite state machine, we get the following classes (skipping some unimportant details): class Student : public FSM<Student,Party,Day,char> {
public:
static PartyOrNot *buyBeer(..);
static PartyOrNot *buyCoffee(..);
};
class PartyOrNot : public FSMstate<...> { ... };
class Day : public FSMinput<...> { ... };
class GoParty : public PartyOrNot { ... } goParty;
class StayHome : public PartyOrNot { ... } stayHome;
class NormalDay : public Day { ... } normalDay;
class BeforeTest : public Day { ... } beforeTest;
You configure the state machine dynamically in your program, using statements like this: addTrans(&normalDay, &goParty, &stayHome, NULL);
addTrans(&normalDay, &stayHome, &goParty, Student::buyBeer);
addTrans(&beforeTest, NULL, &stayHome, Student::buyCoffee);
The functions assigned to the Student class may change the state transition, even though they are not used in this way in this example. Function S* fire(I*) applies new input to the state machine, and returns its new state. Here is a more detailed description of the FSM<> class: template<class F,class S,class I,class T,int D=0> class FSM {
typedef S* (*FSMfun)(S*,void**);
...
public:
FSM(); // Creates a state machine with undefined state (NULL).
// Internal tables are initialized to the default size:
// 8 states, 8 inputs, 8 functions
FSM(int ns,int ni,int nf); // Same as the default constructor,
// but internal tables are initialized to the given sizes.
~FSM(); // behaviour as expected // functions to maintain the state machine:
void addTrans(I *i, S *s1, S *s2, FSMfun f); // add transition
// to state s2, when in state s1 and receiving input i.
// On this transition, f is executed first. If f returns
// a nonzero (State*), this state overwrites s2 and is
// used instead of s2. Function f can be used for other
// purposes without influencing the next state, and is
// always executed as a part of the transition, except when
// f=NULL is given.
// When i=NULL, this transition applies to all inputs.
// When s1=NULL, this transition applies to all current states.
// When s2=NULL, the transition will not change the state.
void remState(S *s); // remove state and all associated transitions
void remInput(I *i); // remove input and all associated transitions
void remTrans(I *i, S *s); // remove some or all transitions
// remTrans(NULL,NULL) will remove all recorded transitions
// functions to operate the state machine
void setState(S *s); // force the state machine into the given state
S *currentState(); // report the current state
S *fire(I *i); // apply input i, and transfer to the next state
};
Transition functions must either be free functions (not assigned to any class), or what we strongly recommend, static functions on your finite state machine class - just as we implemented functions buyBeer() and buyCoffee() above. In function S *f(S *s, void**); the first parameter is always automatically the current state. The second parameter (void**) provides a convenient way of passing one or more (an array of) additional objects of parameters. Function f() may, but need not, return a new state. For examples using this data structure, see ttest/fsm.cpp and mtest/fsm.cpp. The correct results are in ptl/out/fsm.out. |
